multilar(3) FreeBSD Library Functions Manual multilar(3) NAME multilar_create, multilar_destroy, multilar_getix, multilar_insert, multilar_add, multilar_dump, multilar_displine, multilar_walk -- библио- тека для работы с массивами, размещенными в памяти разорвано. LIBRARY library ``libmultilar'' SYNOPSIS #include #include #include #include mular_descriptor * mular_create(u_int32_t flags, int lemax, size_t unit, size_t *size); void mular_destroy(mular_descriptor *mular); void * mular_getix(mular_descriptor *mular, size_t indx); void * mular_insert(mular_descriptor *mular, size_t indx); void * mular_add(mular_descriptor *mular); void mular_dump(mular_descriptor *mular, FILE *out); void mular_displine(mular_descriptor *mular, size_t reli, size_t mindx, mular_indir *idx, int level, FILE *out, size_t flag); int mular_walk(mular_descriptor *mular, size_t mindx, mular_indir *idx, int level, FILE *out, void (*beg) (mular_descriptor *mular, size_t mindx, mular_indir *idx, int level, FILE *out), void (*end) (mular_descriptor *mular, size_t mindx, mular_indir *idx, int level, int ex, FILE *out), int (*before) (mular_descriptor *mular, size_t mindx, void *elem, size_t length, FILE *out), int (*each) (mular_descriptor *mular, size_t mindx, void *elem, FILE *out), int (*after) (mular_descriptor *mular, size_t mindx, void *elem, size_t length, FILE *out)); DESCRIPTION Библиотека предназначена для построения массива из неизвестного заранее количества элементов. Вместо настоящего массива в памяти создается по мере заполнения множество мелких массивов и индексирующее их дерево, при этом практически не делается realloc(). Функция mular_create() создает описатель такой структуры. flags копируется в результат без изменения. unit указывает размер каждого элемента массива, lemax задает максимальный уровень дерева хранения, если size не NULL, то должно указывать на массив размеров (в элементах) каждого уровня хранилища начиная с 1. Если этот массив не задан, перед использованием результата выполнения надо запол- нить массив размеров уровней самостоятельно. Для первого уровня размер элемента unit, для остальных sizeof(mular_indir), который на i386 равен 8. Таким образом, при использовании страниц структуры размером в стра- ницу памяти и максимальном уровне 3 элементы этого массива могут быть {1024, 512, 512}, что обеспечит максимум 268435456 мест для юнитов и зай- мет 1Гбайт под юниты и при этом 2Мбайт под обеспечивающую структуру. На практике размещение может быть не столь эффективным. Если выделенного размера недостаточно, то при размешении очередного юнита будет произведен realloc() самого верхнего уровня с увеличением его вдвое каждый раз, когда не хватит места, поэтому стоит предусмотреть достаточно высокий максимальный уровень хранения. Реально уровень поддерживается по возмож- ности низким и повышается только при необходимости, поэтому задание высо- кого уровня не приводит к излишней неэффективноти при небольшом количе- стве юнитов. Если задать максимальный уровень 1, то это обозначает, что все юниты будут храниться в едином массиве, который при необходимости будет увели- чиваться вдвое всякий раз при нехватке места. Если задать unit равным 0, то реально в качестве размера юнита будет использоваться размер указателя на исполняющей платформе, и будут установлены биты MULAR_PFRE | MULAR_SWP1 | MULAR_SWP2 в флагах структуры. mular_destroy() освобождает память, в том числе при необходимости вызы- вает процедуры освобождения памяти для юнитов. mular_getix() выдает адрес юнита с индексом indx в памяти. При пере- стройке структуры хранения адрес может стать неверным. mular_insert() единственная процедура, которая может поменять структуру хранеения. Она смещает все элементы массива, начиная с заданного индекса, вверх на 1 и выдает адрес освободившегося юнита. Естественно, при боль- шом количестве юнитов к перемещению не происходит перемещения всех затро- нутых юнитов, кроме случая с максимальным уровнем хранения 1, а меняется структура хранения так, что бы индексы юнитов увеличились по возможности без их перемещения. mular_add() вызывает mular_insert() с indx равным минимальному свободному индексу в массиве. Индекс, который будет выдан новому элементу возвра- щает перед вызовом mular_add() макрокоманда MULAR_NEXT с аргументом *mular_descriptor. mular_dump() выводит структуру хранения в человеческом виде в файл out. mular_displine() пока не описана. mular_walk() производит обход структуры хранения, вызывая в соответствую- щих местах соответствующие процедуры из параметров :-((( mular_destroy() и mular_dump() реализованы этой процедурой, см. исходники. Определены макрокоманды с параметрами типа *mular_descriptor - MULAR_NEXT возвращает количество размещенных элементов (или, что тоже самое, номер следующего элемента при добавлении в конец), MULAR_SIZE возвращает размер структуры-аргумента. Макрос нужен из-за того, что размер структуры, которую возвращает mular_create(), зависит от параметров. Параметр flags предназначен для описания объекта mular. Его биты: #define MULAR_SWP1 0x00000001 #define MULAR_SWP2 0x00000002 #define MULAR_SWP4 0x00000004 #define MULAR_SWP8 0x00000008 #define MULAR_SWAP 0x0000000f #define MULAR_DUAD 0x00000010 #define MULAR_HEXU 0x00000020 #define MULAR_CHAR 0x00000040 #define MULAR_PDMP 0x00000100 #define MULAR_PFRE 0x00000200 #define MULAR_FIXD 0x00000400 #define MULAR_ZERO 0x00000800 #define MULAR_HALF 0x00002000 #define MULAR_STRI 0x00004000 #define MULAR_UPPE 0x00008000 #define BLIN_VER1 0x01000000 #define BLIN_VER2 0x02000000 #define BLIN_VER3 0x04000000 #define BLIN_VER4 0x08000000 #define BLIN_VER5 0x10000000 MULAR_SWP1 Менять порядок пар байтов при HEX дампе MULAR_SWP2 Менять порядок пар полуслов при HEX дампе MULAR_SWP4 Менять порядок пар слов при HEX дампе MULAR_SWP8 Менять порядок пар двойных слов при HEX дампе MULAR_DUAD Распечатывать адреса вместо индексов MULAR_HEXU Распечатывать unitы в HEX MULAR_CHAR Распечатывать unitы в char* MULAR_PDMP Если имеется процедура todump() для распечатки юнита в mular_dump(), то ей передается не адрес юнита, а указатель, который хранится в юните. MULAR_PFRE Если имеется процедура tofree() для освобождения юнита в mular_destroy(), то ей передается не адрес юнита, а указа- тель, который хранится в юните. MULAR_FIXD Структура хранения зафиксирована. Этот бит не дает mular_insert() вставить новый юнит. MULAR_ZERO Обнулять выданные юниты MULAR_HALF Всегда делить уровень пополам при нехватке места в нем MULAR_STRI Строго следовать правилам деления MULAR_UPPE При попадании на границу уровней выбирать верхний BLIN_VER1 включает печать сообщений в stderr об ошибках. BLIN_VER2 и выше предназначены для отладки. Остальные поля должны быть установлены в 0. Биты MULAR_SWP1, MULAR_SWP2, MULAR_SWP4, MULAR_SWP8, MULAR_DUAD, MULAR_HEXU, MULAR_CHAR, MULAR_PDMP используются только процедурой mular_dump(). Биты MULAR_HALF, MULAR_STRI, MULAR_UPPE используются при конструировании структуры хранения по мере ее роста. Если юниты добавляются только в начало или только в конец массива, то установка MULAR_STRI приведет к максимально эффективному использованию памяти. Бит MULAR_HALF влияет на эффективность структуры хранения при случайном поступлении элементов и мало влияет при относительно упорядоченном. MULAR_UPPE наоборот, влияет на эффективность структуры хранения при относительно упорядоченном поступлении элементов и мало влияет при случайном. RETURN VALUES Результатом выполнения функции mular_create() является следующая струк- тура: typedef struct { mular_indir top; // Блок самого верхнего уровня size_t unit; // Размер юнита void *(*tofree)(void*); // Процедура освобождения памяти юнита void (*todump)(FILE*, void*); // Процедура распечатки юнита FILE *debugo; // Not used void *sema; // Not used u_int32_t flags; // Флаги u_int16_t lemax; // Максимальный уровень косвенности u_int16_t level; // Реальный уровень косвенности size_t size[1]; // размеры сегментов } mular_descriptor; Функция mular_getix() возвращавет адрес найденного юнита. Функции mular_insert() и mular_add() возвращают адрес созданного места для юнита. Функция mular_walk() возвращает 0 при успехе и не нулевое значение при неудаче, при этом устанавливается значение errno. ERRORS Ошибки могут возникать при выполнении процедур из Standard C Library (libc, -lc) а так же устанавливаться: [ENOMEM] недостаточно памяти. [EINVAL] Неверные параметры вызова. SEE ALSO malloc(3), free(3). BUGS Нельзя устанавливать любой размер уровня меньше 2, но это не проверяется. Флаги MULAR_PDMP и MULAR_PFRE обозначают, что в юните хранится указатель. Никаких специальных проверок при этом не делается. MULAR_SWPX требует соответствующего выравнивания юнита. Проверено по диагонали, см. test.sh дистрибутива. Документация ни к черту. AUTHOR Aleksandr A. Babaylov (aka @BABOLO) .@babolo.ru http://www.babolo.ru/ 29 April 2005