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