Пулированный связный список
Решил поделиться недавно написанной библиотекой для организации связного списка. Реализация должна была производить минимум операций по выделению и освобождению памяти при частых операциях по добавлению, удалению и перемещению элементов внутри списка.
Основная идея, заложенная в реализацию — это использование пула выделенной памяти. Моя библиотека, реализующая пул памяти, не подразумевает повторное использование памяти, которая была освобождена всвязи с удалением элемента. Писать универсальную библиотеку, которая позволяла бы использовать память повторно, не посчитал целесообразным, потому как под разные данные выделяется память разного размера и контроль за свободными кусками снизит производительность пула. В случае со связными списками, мы имеем дело с кусками памяти одного размера, а потому проблем с контролем освобождённых кусков памяти нет.
В результате получилась библиотека со следующим набором функций:
cor_list_t *cor_list_init(int size);
int cor_list_pool_expand(cor_list_t *l);
void cor_list_destroy(cor_list_t *l);
cor_list_init — инициализация списка заданного размера (минимальный размер установлен в 16 элементов). Каждый раз, при добавлении нового элемента, когда не останеться свободных, пул будет расширятся на заданный размер. Размер стоит подобрать так, чтобы операции расширения были как можно более редкими.
cor_list_pool_expand — расширение списка. Эта функция вызывается при вставке новых элементов, если свободных нет. Принудительно вызывать эту функцию не требуется.
cor_list_destroy — освобождение памяти, занятой списком.
Остальные функции работы со списком написаны в виде макросов, для увеличения скорости работы:
#define cor_list_insert_head(_pv, _l)
#define cor_list_insert_tail(_pv, _l)
#define cor_list_insert_after(_pv1, _pv2, _l)
#define cor_list_insert_before(_pv1, _pv2, _l)
#define cor_list_delete(_pv, _l)
#define cor_list_move_head(_pv, _l)
#define cor_list_move_tail(_pv, _l)
#define cor_list_first(_pv, _l)
#define cor_list_last(_pv, _l)
#define cor_list_next(_pv)
#define cor_list_prev(_pv)
#define cor_list_value(_pv)
cor_list_insert_head — вставка новго элемента (_pv) в начало списка (_l). _pv — это указатель, который указывает на встравленный элемент.
cor_list_insert_tail — вставка нового элемента (_pv) в конец списка (_l).
cor_list_insert_after — вставка нового элемента (_pv1) после элемента (_pv2) в списке (_l).
cor_list_insert_before — вставка нового элемента (_pv1) перед элементом (_pv2) в списке (_l).
cor_list_delete — удаление элемента (_pv) из списка (_l).
cor_list_move_head — перемещение элемента (_pv) в начало списка (_l).
cor_list_move_tail — перемещение элемента (_pv) в конец списка (_l).
cor_list_first — получение в _pv первого элемента в списке (_l).
cor_list_last — получение в _pv последнего элемента в списке (_l).
cor_list_next — получение в _pv элемента, следующего за элементом _pv. Т.е. в _pv передаётся текущий элемент, и в него же сохраняется следующий. Если достигнут конец списка, возвращается NULL.
cor_list_prev — получение в _pv элемента, предыдущего, по отношению к элементу _pv.
cor_list_value — получение значения элемента _pv.
Исходники: cor_list.h, cor_list.c.
Если кому-то пригодится, буду рад 
Tags: c, оптимизация, программирование, связные списки, структуры данных
