Commit | Line | Data |
---|---|---|
d9b482c8 SL |
1 | /* |
2 | * Statically sized hash table implementation | |
3 | * (C) 2012 Sasha Levin <levinsasha928@gmail.com> | |
4 | */ | |
5 | ||
6 | #ifndef _LINUX_HASHTABLE_H | |
7 | #define _LINUX_HASHTABLE_H | |
8 | ||
9 | #include <linux/list.h> | |
10 | #include <linux/types.h> | |
11 | #include <linux/kernel.h> | |
12 | #include <linux/hash.h> | |
13 | #include <linux/rculist.h> | |
14 | ||
15 | #define DEFINE_HASHTABLE(name, bits) \ | |
16 | struct hlist_head name[1 << (bits)] = \ | |
17 | { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT } | |
18 | ||
19 | #define DECLARE_HASHTABLE(name, bits) \ | |
20 | struct hlist_head name[1 << (bits)] | |
21 | ||
22 | #define HASH_SIZE(name) (ARRAY_SIZE(name)) | |
23 | #define HASH_BITS(name) ilog2(HASH_SIZE(name)) | |
24 | ||
25 | /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ | |
26 | #define hash_min(val, bits) \ | |
27 | (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits)) | |
28 | ||
29 | static inline void __hash_init(struct hlist_head *ht, unsigned int sz) | |
30 | { | |
31 | unsigned int i; | |
32 | ||
33 | for (i = 0; i < sz; i++) | |
34 | INIT_HLIST_HEAD(&ht[i]); | |
35 | } | |
36 | ||
37 | /** | |
38 | * hash_init - initialize a hash table | |
39 | * @hashtable: hashtable to be initialized | |
40 | * | |
41 | * Calculates the size of the hashtable from the given parameter, otherwise | |
42 | * same as hash_init_size. | |
43 | * | |
44 | * This has to be a macro since HASH_BITS() will not work on pointers since | |
45 | * it calculates the size during preprocessing. | |
46 | */ | |
47 | #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable)) | |
48 | ||
49 | /** | |
50 | * hash_add - add an object to a hashtable | |
51 | * @hashtable: hashtable to add to | |
52 | * @node: the &struct hlist_node of the object to be added | |
53 | * @key: the key of the object to be added | |
54 | */ | |
55 | #define hash_add(hashtable, node, key) \ | |
56 | hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]) | |
57 | ||
58 | /** | |
59 | * hash_add_rcu - add an object to a rcu enabled hashtable | |
60 | * @hashtable: hashtable to add to | |
61 | * @node: the &struct hlist_node of the object to be added | |
62 | * @key: the key of the object to be added | |
63 | */ | |
64 | #define hash_add_rcu(hashtable, node, key) \ | |
65 | hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]) | |
66 | ||
67 | /** | |
68 | * hash_hashed - check whether an object is in any hashtable | |
69 | * @node: the &struct hlist_node of the object to be checked | |
70 | */ | |
71 | static inline bool hash_hashed(struct hlist_node *node) | |
72 | { | |
73 | return !hlist_unhashed(node); | |
74 | } | |
75 | ||
76 | static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz) | |
77 | { | |
78 | unsigned int i; | |
79 | ||
80 | for (i = 0; i < sz; i++) | |
81 | if (!hlist_empty(&ht[i])) | |
82 | return false; | |
83 | ||
84 | return true; | |
85 | } | |
86 | ||
87 | /** | |
88 | * hash_empty - check whether a hashtable is empty | |
89 | * @hashtable: hashtable to check | |
90 | * | |
91 | * This has to be a macro since HASH_BITS() will not work on pointers since | |
92 | * it calculates the size during preprocessing. | |
93 | */ | |
94 | #define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable)) | |
95 | ||
96 | /** | |
97 | * hash_del - remove an object from a hashtable | |
98 | * @node: &struct hlist_node of the object to remove | |
99 | */ | |
100 | static inline void hash_del(struct hlist_node *node) | |
101 | { | |
102 | hlist_del_init(node); | |
103 | } | |
104 | ||
105 | /** | |
106 | * hash_del_rcu - remove an object from a rcu enabled hashtable | |
107 | * @node: &struct hlist_node of the object to remove | |
108 | */ | |
109 | static inline void hash_del_rcu(struct hlist_node *node) | |
110 | { | |
111 | hlist_del_init_rcu(node); | |
112 | } | |
113 | ||
114 | /** | |
115 | * hash_for_each - iterate over a hashtable | |
116 | * @name: hashtable to iterate | |
117 | * @bkt: integer to use as bucket loop cursor | |
d9b482c8 SL |
118 | * @obj: the type * to use as a loop cursor for each entry |
119 | * @member: the name of the hlist_node within the struct | |
120 | */ | |
b67bfe0d SL |
121 | #define hash_for_each(name, bkt, obj, member) \ |
122 | for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\ | |
123 | (bkt)++)\ | |
124 | hlist_for_each_entry(obj, &name[bkt], member) | |
d9b482c8 SL |
125 | |
126 | /** | |
127 | * hash_for_each_rcu - iterate over a rcu enabled hashtable | |
128 | * @name: hashtable to iterate | |
129 | * @bkt: integer to use as bucket loop cursor | |
d9b482c8 SL |
130 | * @obj: the type * to use as a loop cursor for each entry |
131 | * @member: the name of the hlist_node within the struct | |
132 | */ | |
b67bfe0d SL |
133 | #define hash_for_each_rcu(name, bkt, obj, member) \ |
134 | for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\ | |
135 | (bkt)++)\ | |
136 | hlist_for_each_entry_rcu(obj, &name[bkt], member) | |
d9b482c8 SL |
137 | |
138 | /** | |
139 | * hash_for_each_safe - iterate over a hashtable safe against removal of | |
140 | * hash entry | |
141 | * @name: hashtable to iterate | |
142 | * @bkt: integer to use as bucket loop cursor | |
d9b482c8 SL |
143 | * @tmp: a &struct used for temporary storage |
144 | * @obj: the type * to use as a loop cursor for each entry | |
145 | * @member: the name of the hlist_node within the struct | |
146 | */ | |
b67bfe0d SL |
147 | #define hash_for_each_safe(name, bkt, tmp, obj, member) \ |
148 | for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\ | |
149 | (bkt)++)\ | |
150 | hlist_for_each_entry_safe(obj, tmp, &name[bkt], member) | |
d9b482c8 SL |
151 | |
152 | /** | |
153 | * hash_for_each_possible - iterate over all possible objects hashing to the | |
154 | * same bucket | |
155 | * @name: hashtable to iterate | |
156 | * @obj: the type * to use as a loop cursor for each entry | |
d9b482c8 SL |
157 | * @member: the name of the hlist_node within the struct |
158 | * @key: the key of the objects to iterate over | |
159 | */ | |
b67bfe0d SL |
160 | #define hash_for_each_possible(name, obj, member, key) \ |
161 | hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member) | |
d9b482c8 SL |
162 | |
163 | /** | |
164 | * hash_for_each_possible_rcu - iterate over all possible objects hashing to the | |
165 | * same bucket in an rcu enabled hashtable | |
166 | * in a rcu enabled hashtable | |
167 | * @name: hashtable to iterate | |
168 | * @obj: the type * to use as a loop cursor for each entry | |
d9b482c8 SL |
169 | * @member: the name of the hlist_node within the struct |
170 | * @key: the key of the objects to iterate over | |
171 | */ | |
b67bfe0d SL |
172 | #define hash_for_each_possible_rcu(name, obj, member, key) \ |
173 | hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\ | |
174 | member) | |
d9b482c8 | 175 | |
81fcfb81 AK |
176 | /** |
177 | * hash_for_each_possible_rcu_notrace - iterate over all possible objects hashing | |
178 | * to the same bucket in an rcu enabled hashtable in a rcu enabled hashtable | |
179 | * @name: hashtable to iterate | |
180 | * @obj: the type * to use as a loop cursor for each entry | |
181 | * @member: the name of the hlist_node within the struct | |
182 | * @key: the key of the objects to iterate over | |
183 | * | |
184 | * This is the same as hash_for_each_possible_rcu() except that it does | |
185 | * not do any RCU debugging or tracing. | |
186 | */ | |
187 | #define hash_for_each_possible_rcu_notrace(name, obj, member, key) \ | |
188 | hlist_for_each_entry_rcu_notrace(obj, \ | |
189 | &name[hash_min(key, HASH_BITS(name))], member) | |
190 | ||
d9b482c8 SL |
191 | /** |
192 | * hash_for_each_possible_safe - iterate over all possible objects hashing to the | |
193 | * same bucket safe against removals | |
194 | * @name: hashtable to iterate | |
195 | * @obj: the type * to use as a loop cursor for each entry | |
d9b482c8 SL |
196 | * @tmp: a &struct used for temporary storage |
197 | * @member: the name of the hlist_node within the struct | |
198 | * @key: the key of the objects to iterate over | |
199 | */ | |
b67bfe0d SL |
200 | #define hash_for_each_possible_safe(name, obj, tmp, member, key) \ |
201 | hlist_for_each_entry_safe(obj, tmp,\ | |
d9b482c8 SL |
202 | &name[hash_min(key, HASH_BITS(name))], member) |
203 | ||
204 | ||
205 | #endif |