一、前言 #
内核里面实现哈希表很简单粗暴，使用一个数组作为hash查找，每一个元素里面就是一个链表。
二、示例 #
1. 内核标准实现 #
1#include <linux/hashtable.h>
2#include <linux/printk.h>
3
4// 定义2^3的hash表，也就是8个桶
5DEFINE_HASHTABLE(test_hash_table, 3);
6
7typedef struct test_hash_node {
8 struct hlist_node list;
9 int key;
10 int value;
11} test_hash_node_t;
12
13void test_hash(void) {
14 test_hash_node_t item[10];
15 test_hash_node_t *entry;
16 size_t i;
17 int key;
18
19 // DEFINE_HASHTABLE定义的不用初始化
20 // DECLARE_HASHTABLE定义的一定要初始化，默认的table中的first可能没有清零，导致后面遍历崩掉
21 // hash_init(test_hash_table);
22
23 for (i = 0; i < 10; i++) {
24 entry = &item[i];
25 // 初始化node，也就是将两个指针清零
26 INIT_HLIST_NODE(&entry->list);
27
28 entry->key = i;
29 entry->value = i;
30 // 插入hash表
31 hash_add(test_hash_table, &entry->list, entry->key);
32 }
33
34 // 查询
35 key = 5;
36 hash_for_each_possible(test_hash_table, entry, list, key) {
37 if (entry->key == key) {
38 printk("key: %d, value: %d\n", entry->key, entry->value);
39 }
40 }
41
42 // 遍历所有的key
43 hash_for_each(test_hash_table, i, entry, list) {
44 printk("hash idx %ld, key: %d, value: %d\n", i, entry->key, entry->value);
45 }
46}
2. 使用hlist自定义实现 #
- 自定义实现可以自定义hash表长度、添加锁等操作，默认的hash表不能处理锁
1#include <linux/list.h>
2#include <linux/printk.h>
3
4#define TEST_HASH_SIZE 5
5
6typedef struct test_hash_node {
7 struct hlist_node list;
8 int key;
9 int value;
10} test_hash_node_t;
11
12typedef struct test_hashinfo {
13 struct hlist_head hash[TEST_HASH_SIZE];
14} test_hashinfo_t;
15
16static inline int test_hash_fun(unsigned int key) {
17 return key % TEST_HASH_SIZE;
18}
19
20void test_hash(void) {
21 test_hashinfo_t table;
22 test_hash_node_t item[10];
23 test_hash_node_t *entry;
24 struct hlist_head *head;
25 size_t i;
26 int key;
27
28 // 一定要初始化，默认的table中的first可能没有清零，导致后面遍历崩掉
29 for (i = 0; i < ARRAY_SIZE(table.hash); i++) {
30 INIT_HLIST_HEAD(&table.hash[i]);
31 }
32
33 for (i = 0; i < 10; i++) {
34 entry = &item[i];
35 // 初始化node，也就是将两个指针清零
36 INIT_HLIST_NODE(entry);
37
38 entry->key = i;
39 entry->value = i;
40 // 插入hash表，找到hash对应的桶
41 head = &table.hash[test_hash_fun(item[i]->key)];
42 // 添加到hash桶的头部
43 hlist_add_head(entry->list, head);
44 }
45
46 // 查询
47 key = 5;
48 // 先找到桶
49 head = &table.hash[test_hash_fun(key)];
50 // 遍历链表找到元素
51 hlist_for_each_entry(entry, head, list) {
52 if (entry->key == key) {
53 printk("find key %d, value %d\n", entry->key, entry->value);
54 break;
55 }
56 }
57}
3. 使用hlist_bl自定义实现，每个桶一个自旋锁 #
1#include <linux/hashtable.h>
2#include <linux/list_bl.h>
3#include <linux/printk.h>
4
5/********** 这一部分可以写到hashtable_bl.h中 start **********/
6#define DEFINE_HASHTABLE_BL(name, bits) \
7 struct hlist_bl_head name[1 << (bits)] = {[0 ...((1 << (bits)) - 1)] = HLIST_HEAD_INIT}
8
9#define DEFINE_READ_MOSTLY_HASHTABLE_BL(name, bits) \
10 struct hlist_bl_head name[1 << (bits)] __read_mostly = {[0 ...((1 << (bits)) - 1)] = HLIST_HEAD_INIT}
11
12#define DECLARE_HASHTABLE_BL(name, bits) struct hlist_bl_head name[1 << (bits)]
13
14static inline void __hash_init_bl(struct hlist_bl_head *ht, unsigned int sz) {
15 unsigned int i;
16
17 for (i = 0; i < sz; i++) INIT_HLIST_HEAD(&ht[i]);
18}
19
20#define hash_init_bl(hashtable) __hash_init_bl(hashtable, HASH_SIZE(hashtable))
21
22// 获取key对应的头节点
23#define hash_get_head(hashtable, key) (&hashtable[hash_min(key, HASH_BITS(hashtable))])
24
25/**
26 * hash_add - add an object to a hashtable
27 * @hashtable: hashtable to add to
28 * @node: the &struct hlist_node of the object to be added
29 * @key: the key of the object to be added
30 */
31#define hash_add_bl(hashtable, node, key) \
32 ({ \
33 struct hlist_bl_head *__mptr = hash_get_head(hashtable, key); \
34 hlist_bl_lock(__mptr); \
35 hlist_bl_add_head(node, __mptr); \
36 hlist_bl_unlock(__mptr); \
37 })
38
39/**
40 * hash_for_each_safe - iterate over a hashtable safe against removal of
41 * hash entry
42 * @name: hashtable to iterate
43 * @bkt: integer to use as bucket loop cursor
44 * @tmp: a &struct used for temporary storage
45 * @pos: the &struct hlist_bl_node to use as a loop cursor.
46 * @obj: the type * to use as a loop cursor for each entry
47 * @member: the name of the hlist_node within the struct
48 */
49#define hash_for_each_safe_bl(name, bkt, tmp, pos, obj, member) \
50 for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++) \
51 hlist_bl_for_each_entry_safe(obj, pos, tmp, &name[bkt], member)
52/********** 这一部分可以写到hashtable_bl.h中 end **********/
53
54// 定义链表元素节点
55typedef struct test_hash_node {
56 struct hlist_bl_node list;
57 int key;
58 int value;
59} test_hash_node_t;
60
61// 定义hash表
62static DEFINE_HASHTABLE_BL(table, 10); // 这里会自动初始化
63
64void test_hash(void) {
65 test_hash_node_t item[10];
66 test_hash_node_t *entry;
67 struct hlist_bl_head *head;
68 struct hlist_bl_node *node;
69 size_t i;
70 int key;
71
72 for (i = 0; i < 10; i++) {
73 entry = &item[i];
74 // 初始化node，也就是将两个指针清零
75 INIT_HLIST_BL_NODE(&entry->list);
76
77 entry->key = i;
78 entry->value = i;
79 // 插入hash表
80 hash_add_bl(table, &entry->list, entry->key);
81 }
82
83 // 查询
84 key = 5;
85 head = hash_get_head(table, key);
86 // 遍历链表找到元素
87 hlist_bl_lock(head);
88 hlist_bl_for_each_entry(entry, node, head, list) {
89 if (entry->key == key) {
90 printk("find key %d, value %d\n", entry->key, entry->value);
91 break;
92 }
93 }
94 hlist_bl_unlock(head);
95
96 // 遍历所有table，不加锁清理
97 hash_for_each_safe_bl(toa_ipv6_table, idx, tmp, node, entry, list) {
98 hlist_bl_del(node);
99 }
100}