Не унылый пост о списках и деревьях поиска в языке 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 <stdio.h>
#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 <stdio.h>
#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: простой вывод текста мною была реализована небольшая библиотека для работы с матрицами и векторами.

Дополнение: Памятка по работе кучи и пирамидальной сортировки