Хеш-таблица в ядре Linux

Question

Есть ли в ядре Linux универсальная реализация хеш-таблицы для использования в коде ядра?Я знаю, что доступны связанные списки, красно-черные деревья и радикальные деревья, но я не нашел ссылки на реализацию универсальной хеш-таблицы, хотя я знаю, что хеш-таблицы интенсивно используются в ядре ядра.

Answer 1

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

---

Ядро 3.7 +

Общая реализация была введена Сашей Левиным в 2012 году и объединена для ядра 3.7.

---

Старые ядра

Ядро (по состоянию на 2.6.38) не включает в себя реализацию универсальной хеш-таблицы, но включает в себя несколько частей:

• hlist_*/HLIST_* в list.h - структуры списков с двойными связями в виде одной указки и макросы, используемые для хэш-блоков. ( ответ ниже от adobriyan )
• hash.h включает в себя процедуры хеширования для целых, длинных и указателей. В этой статье , написанной Чаком Левером, рассматривается эффективность этих подпрограмм.
• См. pid_hash в pid.c для примера, созданного из этих примитивов.

uthash - это общая хеш-таблица для C, реализованная как макросы, определенные в одном заголовочном файле. Это решение может быть подходящим для многих сторонних модулей ядра (например, драйверов устройств). Однако опора на uthash может помешать объединению модуля.

Answer 2

Не существует универсального кода хеш-таблицы.

Но посмотрите, как используется HLIST_*/hlist_* материал.