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