C map / hash-table, в котором заданы целые числа и карты для обозначения пустых указателей

Question

Я переписываю облегченный сервер изображений, написанный на Python, используя epoll в c (не в c ++). Я хочу написать (или использовать существующую) очень простую карту или хэш-таблицу, которая отображает целочисленные ключи (файловые дескрипторы) для аннулирования указателей. Какой хороший способ сделать это? Мне не нужно поддерживать какие-либо общие типы ключей или даже строк. У меня есть одна идея:

// Initialize map.
size_t map_size = 50;
void ** map = (void **)malloc(sizeof(void *) * map_size);
memset((void *)map, 0, map_size);

// Set values for keys 3, 20, 67
int key_a = 3;
int key_b = 20;
int key_c = 67;
void * value_a = ...;
void * value_b = ...;
void * value_c = ...;

// NOTE: This does not take into account conflicting keys. I would probably solve
// that using an array or linked-list and comparing keys.
map[key_a % map_size] = value_a;
map[key_b % map_size] = value_b;
map[key_c % map_size] = value_c;

Это разумно или есть намного лучшие способы сделать это? Или кто-то может направить меня в правильном направлении, чтобы найти ответ?

Answer 1

Используйте общедоступную реализацию универсальной C-хеш-таблицы в кодовой базе Ruby - st.c .

Answer 2

Файловые дескрипторы - это маленькие целые числа в большинстве систем, и они часто являются смежными, так как они используются в качестве индексов внутри ядра.Поэтому я предлагаю просто создать массив из 0..maxfd (динамически растущий) и использовать дескриптор файла как целое число - без хеширования.системы, которые используют разные стратегии для выделения файловых дескрипторов, например, прерывание, если оно больше 2 ^ 20.

Answer 3

Нет ничего плохого в использовании простого модуля в качестве «алгоритма хеширования», но он работает хорошо, только если вы знаете, что результаты будут равномерно распределены. В вашем случае, однако, технически вы не можете рассчитывать на это с помощью файловых дескрипторов, поскольку нет конкретной гарантии того, какие номера вы получите после вызовов open / fopen.

Существуют очень простые алгоритмы хеширования, которые довольно быстры и работают достаточно хорошо для общих случаев использования. Вы могли бы рассмотреть семейство FNV , или даже простой хэш Пирсона.

Тем не менее, мне немного любопытно, почему вы хотите, чтобы хеш-таблица была отключена от файловых дескрипторов. Это кажется странной деталью дизайна и заставляет меня думать, что вы что-то слишком усложняете.

Answer 4

Другие подняли хорошие вопросы о том, действительно ли это то, что вы хотите сделать, но просто чтобы ответить на ваш непосредственный вопрос, хеш-таблицы glibc должны быть доступны в большинстве систем.Обратите внимание, что вы почти наверняка захотите использовать варианты _r (hcreate_r, hsearch_r, hdestroy_r), поскольку ванильные версии создают и обрабатывают одну глобальную хеш-таблицу.