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