Не унылый пост о списках и деревьях поиска в языке C
27 июля 2016
Те-еретики часто критикуют язык C за то, что якобы в нем все ну очень плохо с контейнерами, и было бы здорово иметь в языке какой-то аналог STL. Мол, либо приходится все хранить по указателям, либо писать свой кодогенератор на Python, что-то в таком духе. Сегодня мы убедимся, что все это неправда.
Нет велосипедам!
Далее предполагается, что вы знаете, что такое односвязные и двусвязные списки, а также чем RB-деревья отличаются от AVL-деревьев. На эту тему есть великое множество замечательных книг, как на русском, так и на английском языке (например, Кормен). Пересказывать их нет смысла, так как пересказ едва ли окажется лучше оригинала.
Писать, разумеется, будем не с нуля, а возьмем уже готовое решение. Их существует довольно много. Не редко советуют GLib, хорошие примеры использования которого приводятся, например, здесь. Также заслуживает внимания библиотека qLibc.
Но я пошел несколько иным путем. Так как на момент написания этих строк я много ковыряюсь в коде PostgreSQL, то решил создать отдельный репозиторий на GitHub с реализацией одно- и двусвязных списков, а также RB-деревьев, из этого проекта. Во-первых, с этим кодом я лично неплохо знаком. Во-вторых, вряд ли удастся найти реализацию контейнеров, превосходящую реализацию PostgreSQL по стабильности и/или скорости, а также имеющую при этом лицензию MIT или BSD.
В данном контексте также хотелось бы осветить интересный вопрос — какие деревья поиска когда следует использовать? Не могу сказать, что я лично собаку съел на деревьях поиска, но, насколько мои знакомые программисты на C/C++ и я можем судить, ситуация следующая.
Самыми популярными деревьями поиска являются AVL- и RB-деревья. Асимптотически они одинаковые. AVL-деревья всегда сбалансированы. RB-деревья приблизительно сбалансированы, зато делают меньше поворотов при вставке и удалении элементов. Поэтому AVL-деревья выгодно использовать, если вы часто ищите по дереву и редко его изменяете. Если же дерево изменяется часто, а поиск по нему происходит сравнительно редко, выигрывают RB-деревья. Разницы между AVL- и RB-деревьями в плане потребления памяти нет. Любые детали реализации на практики несущественны из-за выравниваня структур.
Кроме того, в последнее время часто делают in-memory B-деревья. Они имеют меньшие накладные расходы по памяти и лучше помещаются в кэши. При достаточно большом количестве элементов (десятки тысяч) они работают лучше, чем AVL- и RB-деревья. Проблема с B-деревьями в том, что при добавлении и удалении элементов становятся невалидными ранее полученные ссылки на элементы дерева. У AVL- и RB-деревьев такой проблемы нет.
Важно! Впрочем, это зависит от конкретной реализации. Для реализации RB-деревьев, рассмотренной в настоящем посте, на момент написания этих строк утверждение касательно сохранения валидности ссылок, увы, не верно.
Односвязные и двусвязные списки
Начнем с простого. Ниже приводится пример использования односвязных списков. С двусвязными списками работа осуществляется так же, только операций доступно несколько больше, так как список эффективно обходится в обратном порядке.
#include <stdlib.h>
#include <string.h>
#include "deps/algorithms/include/ilist.h"
typedef struct
{
slist_node node;
char data[128];
} ListItemData;
typedef ListItemData *ListItem;
void main()
{
slist_iter iter;
ListItemData item1, item2, item3;
ListItem tmp;
slist_head head;
slist_init(&head);
strcpy(item1.data, "first item");
strcpy(item2.data, "second item");
strcpy(item3.data, "third item");
printf("is empty before: %d\n", slist_is_empty(&head));
slist_push_head(&head, (slist_node*)&item1);
slist_push_head(&head, (slist_node*)&item2);
slist_push_head(&head, (slist_node*)&item3);
printf("is empty after: %d\n", slist_is_empty(&head));
slist_foreach(iter, &head)
{
tmp = (ListItem) iter.cur;
printf("tmp->data = %s\n", tmp->data);
}
tmp = (ListItem) slist_pop_head_node(&head);
printf("After slist_pop_head_node call tmp->data = %s\n", tmp->data);
slist_foreach(iter, &head)
{
tmp = (ListItem) iter.cur;
printf("tmp->data = %s\n", tmp->data);
}
}
Заметьте, что slist_node node включается прямо в начало нашей структуры, благодаря чему, помимо прочего, указатель на нее можно кастовать в slist_node* и обратно. При использовании этого подхода не требуется делать лишние хождения по указателям или генерировать код для каждой новой структуры, которую мы хотим положить в список. Все гениальное — просто!
Красно-черные деревья
Для RB-деревьев ситуация аналогичная:
#include <stdlib.h>
#include <string.h>
#include "deps/algorithms/include/rbtree.h"
typedef struct
{
RBNode node;
char data[128];
} TreeItemData;
typedef TreeItemData *TreeItem;
static int
tree_comparator(const RBNode* a, const RBNode* b, void* arg)
{
return strcmp(((const TreeItem)a)->data, ((const TreeItem)b)->data);
}
static void
tree_combiner(RBNode* existing, const RBNode* newdata, void* arg)
{
/* do nothing */
}
static RBNode*
tree_allocfunc(void* arg)
{
return malloc(sizeof(TreeItemData));
}
static void
tree_freefunc(RBNode* node, void* arg)
{
free(node);
}
void main()
{
RBTree tree;
bool isNew;
TreeItemData item;
TreeItem tmp;
rb_create(&tree, sizeof(TreeItemData),
tree_comparator, tree_combiner,
tree_allocfunc, tree_freefunc, NULL);
printf("is empty before: %d\n", rb_leftmost(&tree) == NULL);
strcpy(item.data, "first item");
rb_insert(&tree, (RBNode*)&item, &isNew);
strcpy(item.data, "second item");
rb_insert(&tree, (RBNode*)&item, &isNew);
strcpy(item.data, "third item");
rb_insert(&tree, (RBNode*)&item, &isNew);
printf("is empty after: %d\n", rb_leftmost(&tree) == NULL);
rb_begin_iterate(&tree, LeftRightWalk);
while(tmp = (TreeItem)rb_iterate(&tree))
{
printf("tmp->data = %s\n", tmp->data);
}
strcpy(item.data, "second item");
tmp = (TreeItem)rb_find(&tree, (RBNode*)&item);
if(tmp)
{
printf("second item found, deleting\n");
rb_delete(&tree, (RBNode*)tmp);
}
else
{
printf("second item not found! :(\n");
}
printf("is empty before: %d\n", rb_leftmost(&tree) == NULL);
/* rb_begin_iterate + rb_iterate doesn't work here! */
while(tmp = (TreeItem)rb_leftmost(&tree))
{
printf("tmp->data = %s\n", tmp->data);
rb_delete(&tree, (RBNode*)tmp);
}
printf("is empty after: %d\n", rb_leftmost(&tree) == NULL);
}
На основе RB-деревьев легко создаются эффективные map’ы и set’ы, как с повторяющимися элементами, так и без, а также разряженные матрицы, графы, и, возможно, еще какие-то полезные вещи, о которых я сейчас не могу вспомнить. В сочетании со списками, а также массивами, которые в языке есть из коробки, мы получаем практически все мыслимые контейнеры, которые нам когда-либо могут пригодиться на практике. Спросите любого программиста на языке Python! (На самом деле это, конечно же, не совсем так. Например, эффективные очереди с приоритетами реализуются поверх структуры данных heap.)
Заключение
Контейнеры в языке C не только не имеют каких-то накладных расходов по памяти или связанных с лишними хождениями по ссылкам, но и, в отличие от языка C++, прекрасно работают без кодогенерации, а следовательно не замедляют компиляцию проекта, не приводят к нечитаемым сообщениям об ошибках и распуханию бинарника. Единственный нюанс заключается в том, что на границе работы с контейнером приходится кастовать типы. Но, по моему опыту, (1) отсутствие типизированных контейнеров на практике не создает такой уж большой проблемы, а иногда и решает проблемы за счет большей гибкости, (2) те же списки, массивы / вектора, и так далее, быстрее и проще закодировать заново, чем использовать библиотеки, сохранив при этом типизированность.
Исходники к этой заметке вы найдете здесь и здесь. Помимо списков и деревьев в репозитории вы найдете реализацию хэш-таблиц на основе кода к заметке Реализация хэш-таблиц, почти как в Perl. Если вы хотите посмотреть, что еще можно легко выковырять из PostgreSQL, вам сюда. Код для выковыривания из ядра Linux находится здесь и здесь, но лицензия, увы, GPL.
Если вас интересуют другие реализации алгоритмов на чистом C, обратите внимание на заметку Эллиптическая криптография на практике. Кроме того, для поста Продолжаем изучение OpenGL: простой вывод текста мною была реализована небольшая библиотека для работы с матрицами и векторами.
А какие библиотеки контейнеров вы используете, программируя на C?
Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.