Когда я работал над программой для маршрутизации трафика через DNS-запросы, мне нужно было проверять наличие доменов в заранее определенном списке. В языке Си нет стандартной библиотеки для работы с хеш-таблицами, поэтому обычно используются сторонние решения или создаются собственные. Я попробовал несколько готовых реализаций, но оказалось, что они недостаточно эффективны для моих нужд, так как требовали слишком много памяти. В итоге я разработал свою собственную хеш-таблицу.
Критерии:
Избежать оверхеда на большое количество
malloc.Иметь возможность быстрого перехода по элементам списка коллизий.
Иметь потокобезопасную версию.
Чтобы удовлетворить оба критерия, была создана нестандартная реализация хеш-таблицы. Она представляет собой длинный массив, где каждый элемент является структурой с двумя полями: индекс следующего элемента в списке коллизий и сами данные.
Эта реализация объединяет сильные стороны открытой адресации и адресации списком. На 64-битных системах использование int32_t для индексов экономит 4 байта на каждом элементе массива, хотя и ограничивает максимальное количество элементов до 2^31 (2147483648). Однако этого объема вполне достаточно для большинства практических задач.
По сравнению с открытой адресацией, наша реализация не уступает в эффективности использования памяти. Для оптимальной работы открытой адресации также требуется хранить вычисленные хеш-значения вместе с данными, а каждое такое значение занимает те же 4 байта, что и индекс на следующий элемент.
Описание хеш-таблицы
Как уже было сказано выше структура элемента массива состоит из двух полей:
typedef struct __attribute__((packed)) elem {
int32_t next;
char data;
} elem_t;То что data имеет размер char не страшно. В C99, есть структуры переменного размера, но в C89 нет. Поэтому для совместимости C89 началом данных является переменная data.
Для того чтобы хеш-таблица могла работать с любыми типами данных, необходимо реализовать механизмы для вычисления хеш-значений и сравнения данных на основе callback-функций. Однако может возникнуть ситуация, когда мы добавляем элементы одного типа, а ищем элементы другого. Именно такой сценарий был реализован в моей программе для обработки DNS-запросов. Поэтому пришлось предусмотреть отдельные callback-функции для операций добавления, поиска и удаления.
add_hash_t add_hash;
add_cmp_t add_cmp;
find_hash_t find_hash;
find_cmp_t find_cmp;
del_hash_t del_hash;
del_cmp_t del_cmp;Добавление элемента
Сначала вычисляем хеш-значение для добавляемого элемента и находим остаток от деления на размер хеш-таблицы — этот результат будет называться потенциальным индексом элемента.
При добавлении элемента возможны три сценария:
-
Индекс не занят, просто добавляем элемент на этот индекс.
Добавление на не занятое место -
Если индекс уже занят другим элементом, у которого потенциальный индекс совпадает с потенциальным индексом добавляемого элемента, то возникает коллизия. В этом случае мы проходим по списку коллизий до конца, пока не найдем первый свободный индекс. Затем обновляем последний элемент списка, указав, что следующим после него идет найденный нами новый элемент. После этого добавляемый элемент помещается на найденную позицию.
Добавление в коллизию -
Если индекс занят элементом, чей потенциальный индекс отличается от потенциального индекса добавляемого элемента, это означает, что при предыдущем добавлении мы заняли "чужую" ячейку. Тогда нам нужно найти элемент, который стоит перед нашим "чужим" элементом в списке коллизий. Далее следует найти для "чужого" элемента новое свободное место и переместить его туда, обновив ссылку у предыдущего элемента в списке. После этого добавляемый элемент можно поместить на освободившееся место.
Добавление в место занятое "чужим"
Как использовать
Примеры использования есть в файле test/test.c. Опишу что делает каждая функция из array_hashmap.h:
array_hashmap_t array_hashmap_init(int32_t hashmap_size, double max_load,
int32_t type_size);Принимает:
Максимальное количество элементов в хеш-таблице.
Максимальный коэффициент заполненности (значение от 0 до 1).
Размер типа данных, которые будут храниться в хеш-таблице.
Возвращает:
Указатель на хеш-таблицу array_hashmap_t.
void array_hashmap_set_func(array_hashmap_t,
add_hash_t, add_cmp_t,
find_hash_t, find_cmp_t,
del_hash_t, del_cmp_t);Принимает:
Указатель на хеш-таблицу array_hashmap_t.
Для добавления: одна функция для расчёта хеш-значения, другая для сравнения двух элементов.
Для поиска: аналогично, две функции — для хеш-значения и сравнения.
Для удаления: снова пара функций — для хеш-значения и сравнения элементов.
array_hashmap_ret_t array_hashmap_add_elem(array_hashmap_t, const void *add_elem_data,
void *res_elem_data, on_already_in_t);Принимает:
Указатель на хеш-таблицу array_hashmap_t.
Указатель на добавляемый элемент – элемент, который нужно попробовать добавить в таблицу.
Указатель, куда будет записан либо вставленный элемент, либо тот, что уже находится на данной позиции, если таковой существует.
Указатель на функцию, которая определяет, какой элемент оставить в таблице: новый или существующий. Этот параметр полезен, например, для частичной перезаписи значений.
Возвращает:
Добавлен элемент или он уже присутствует.
array_hashmap_ret_t array_hashmap_find_elem(array_hashmap_t,
const void *find_elem_data,
void *res_elem_data);Принимает:
Указатель на хеш-таблицу array_hashmap_t.
Указатель на искомый элемент.
Указатель, куда будет записан найденный элемент, если он существует.
Возвращает:
Найден элемент или нет.
array_hashmap_ret_t array_hashmap_del_elem(array_hashmap_t, const void *del_elem_data,
void *res_elem_data);Принимает:
Указатель на хеш-таблицу array_hashmap_t.
Указатель на удаляемый элемент.
Указатель, куда будет записан удаленный элемент, если он существует.
Возвращает:
Удален элемент или нет.
deled_count array_hashmap_del_elem_by_func(array_hashmap_t, del_func_t);
Принимает:
Указатель на хеш-таблицу array_hashmap_t.
Указатель на функцию, которая будет вызываться для каждого элемента в хеш-таблице. Эта функция должна решать, удалять текущий элемент или нет.
Возвращает:
Количество удаленных элементов.
void array_hashmap_del(array_hashmap_t *);Принимает:
Указатель на хеш-таблицу array_hashmap_t.
Включение потокобезопасной версии
Включить потокобезопасную версию можно передав опцию компиляции THREAD_SAFETY.
Проверить с какой версией собрана библиотека можно через функцию:
bool array_hashmap_is_thread_safety(array_hashmap_t map_struct_c);Тестирование
Такие универсальные библиотеки требуют тщательного тестирования. Поскольку моя программа работает с доменами, тесты также проводились на их основе. Для экономии памяти я храню домены в виде единого длинного массива, где они расположены последовательно. В хеш-таблице сохраняются не указатели на начало строк, а смещения начала каждой строки относительно начала массива. Здесь проявляется различие между операциями добавления и поиска: добавляемые элементы находятся в основном массиве, тогда как искомые элементы могут отсутствовать, поэтому для поиска передаются указатели на строки. Кроме смещения начала строки, дополнительно сохраняется временная метка, обозначающая условное "время".
Как проводилось тестирование:
Добавить элементов
Убедиться что все элементы добавились в хеш-таблицу
Убедиться что заведомо отсутствующих элементов нет в хеш-таблице
Обновить поле "время" для всех элементов
Убедиться что все поля "время" обновились
Удалить каждый элемент
Убедиться что все элементы удалены
Добавить элементов
Удалить все элементы через функцию
Убедиться что все элементы удалены
Все эти тестирования проводились для разной заполненности хеш-таблицы от 1% до 100%.
Так же есть тестирование потокобезопасной версии:
Создается три потока, один будет добавлять элементы, один будет искать элементы, один удалять элементы.
Основной поток раз в секунду создает и удаляет хеш-таблицу.
Так же проводилось тестирование с использованием AddressSanitizer и MemorySanitizer.
Таблица тестирования
Все тесты были пройдены. А так же моя хеш-таблицу уже больше двух лет работает в мой программе, за это время проблем не наблюдалось.