Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ядро 3.7 +

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

Предыдущие ядра

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

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

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

Ответ 2

Нет общего кода хэш-таблицы.

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