1
2
3
4
5
6
7
8
9
10
11#ifndef _SS_HASHTAB_H_
12#define _SS_HASHTAB_H_
13
14#include <linux/types.h>
15#include <linux/errno.h>
16#include <linux/sched.h>
17
18#define HASHTAB_MAX_NODES U32_MAX
19
20struct hashtab_key_params {
21 u32 (*hash)(const void *key);
22 int (*cmp)(const void *key1, const void *key2);
23
24};
25
26struct hashtab_node {
27 void *key;
28 void *datum;
29 struct hashtab_node *next;
30};
31
32struct hashtab {
33 struct hashtab_node **htable;
34 u32 size;
35 u32 nel;
36};
37
38struct hashtab_info {
39 u32 slots_used;
40 u32 max_chain_len;
41};
42
43
44
45
46
47
48int hashtab_init(struct hashtab *h, u32 nel_hint);
49
50int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
51 void *key, void *datum);
52
53
54
55
56
57
58
59
60
61static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
62 struct hashtab_key_params key_params)
63{
64 u32 hvalue;
65 struct hashtab_node *prev, *cur;
66
67 cond_resched();
68
69 if (!h->size || h->nel == HASHTAB_MAX_NODES)
70 return -EINVAL;
71
72 hvalue = key_params.hash(key) & (h->size - 1);
73 prev = NULL;
74 cur = h->htable[hvalue];
75 while (cur) {
76 int cmp = key_params.cmp(key, cur->key);
77
78 if (cmp == 0)
79 return -EEXIST;
80 if (cmp < 0)
81 break;
82 prev = cur;
83 cur = cur->next;
84 }
85
86 return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
87 key, datum);
88}
89
90
91
92
93
94
95
96static inline void *hashtab_search(struct hashtab *h, const void *key,
97 struct hashtab_key_params key_params)
98{
99 u32 hvalue;
100 struct hashtab_node *cur;
101
102 if (!h->size)
103 return NULL;
104
105 hvalue = key_params.hash(key) & (h->size - 1);
106 cur = h->htable[hvalue];
107 while (cur) {
108 int cmp = key_params.cmp(key, cur->key);
109
110 if (cmp == 0)
111 return cur->datum;
112 if (cmp < 0)
113 break;
114 cur = cur->next;
115 }
116 return NULL;
117}
118
119
120
121
122void hashtab_destroy(struct hashtab *h);
123
124
125
126
127
128
129
130
131
132
133
134
135int hashtab_map(struct hashtab *h,
136 int (*apply)(void *k, void *d, void *args),
137 void *args);
138
139
140void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
141
142#endif
143