1 /* SPDX-License-Identifier: GPL-2.0 */ 1
2 /*
3 * Statically sized hash table implementation
4 * (C) 2012 Sasha Levin <levinsasha928@gmail.
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)
19
20 #define DEFINE_READ_MOSTLY_HASHTABLE(name, bit
21 struct hlist_head name[1 << (bits)] __
22 { [0 ... ((1 << (bits)
23
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
31 #define hash_min(val, bits)
32 (sizeof(val) <= 4 ? hash_32(val, bits)
33
34 static inline void __hash_init(struct hlist_he
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 t
47 * same as hash_init_size.
48 *
49 * This has to be a macro since HASH_BITS() wi
50 * it calculates the size during preprocessing
51 */
52 #define hash_init(hashtable) __hash_init(hasht
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
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_m
62
63 /**
64 * hash_add_rcu - add an object to a rcu enabl
65 * @hashtable: hashtable to add to
66 * @node: the &struct hlist_node of the object
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[ha
71
72 /**
73 * hash_hashed - check whether an object is in
74 * @node: the &struct hlist_node of the object
75 */
76 static inline bool hash_hashed(struct hlist_no
77 {
78 return !hlist_unhashed(node);
79 }
80
81 static inline bool __hash_empty(struct hlist_h
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 e
94 * @hashtable: hashtable to check
95 *
96 * This has to be a macro since HASH_BITS() wi
97 * it calculates the size during preprocessing
98 */
99 #define hash_empty(hashtable) __hash_empty(has
100
101 /**
102 * hash_del - remove an object from a hashtabl
103 * @node: &struct hlist_node of the object to
104 */
105 static inline void hash_del(struct hlist_node
106 {
107 hlist_del_init(node);
108 }
109
110 /**
111 * hash_del_rcu - remove an object from a rcu
112 * @node: &struct hlist_node of the object to
113 */
114 static inline void hash_del_rcu(struct hlist_n
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
123 * @obj: the type * to use as a loop cursor fo
124 * @member: the name of the hlist_node within
125 */
126 #define hash_for_each(name, bkt, obj, member)
127 for ((bkt) = 0, obj = NULL; obj == NUL
128 (bkt)++)\
129 hlist_for_each_entry(obj, &nam
130
131 /**
132 * hash_for_each_rcu - iterate over a rcu enab
133 * @name: hashtable to iterate
134 * @bkt: integer to use as bucket loop cursor
135 * @obj: the type * to use as a loop cursor fo
136 * @member: the name of the hlist_node within
137 */
138 #define hash_for_each_rcu(name, bkt, obj, memb
139 for ((bkt) = 0, obj = NULL; obj == NUL
140 (bkt)++)\
141 hlist_for_each_entry_rcu(obj,
142
143 /**
144 * hash_for_each_safe - iterate over a hashtab
145 * hash entry
146 * @name: hashtable to iterate
147 * @bkt: integer to use as bucket loop cursor
148 * @tmp: a &struct hlist_node used for tempora
149 * @obj: the type * to use as a loop cursor fo
150 * @member: the name of the hlist_node within
151 */
152 #define hash_for_each_safe(name, bkt, tmp, obj
153 for ((bkt) = 0, obj = NULL; obj == NUL
154 (bkt)++)\
155 hlist_for_each_entry_safe(obj,
156
157 /**
158 * hash_for_each_possible - iterate over all p
159 * same bucket
160 * @name: hashtable to iterate
161 * @obj: the type * to use as a loop cursor fo
162 * @member: the name of the hlist_node within
163 * @key: the key of the objects to iterate ove
164 */
165 #define hash_for_each_possible(name, obj, memb
166 hlist_for_each_entry(obj, &name[hash_m
167
168 /**
169 * hash_for_each_possible_rcu - iterate over a
170 * same bucket in an rcu enabled hashtable
171 * @name: hashtable to iterate
172 * @obj: the type * to use as a loop cursor fo
173 * @member: the name of the hlist_node within
174 * @key: the key of the objects to iterate ove
175 */
176 #define hash_for_each_possible_rcu(name, obj,
177 hlist_for_each_entry_rcu(obj, &name[ha
178 member, ## cond)
179
180 /**
181 * hash_for_each_possible_rcu_notrace - iterat
182 * to the same bucket in an rcu enabled hashta
183 * @name: hashtable to iterate
184 * @obj: the type * to use as a loop cursor fo
185 * @member: the name of the hlist_node within
186 * @key: the key of the objects to iterate ove
187 *
188 * This is the same as hash_for_each_possible_
189 * not do any RCU debugging or tracing.
190 */
191 #define hash_for_each_possible_rcu_notrace(nam
192 hlist_for_each_entry_rcu_notrace(obj,
193 &name[hash_min(key, HASH_BITS(
194
195 /**
196 * hash_for_each_possible_safe - iterate over
197 * same bucket safe against removals
198 * @name: hashtable to iterate
199 * @obj: the type * to use as a loop cursor fo
200 * @tmp: a &struct hlist_node used for tempora
201 * @member: the name of the hlist_node within
202 * @key: the key of the objects to iterate ove
203 */
204 #define hash_for_each_possible_safe(name, obj,
205 hlist_for_each_entry_safe(obj, tmp,\
206 &name[hash_min(key, HASH_BITS(
207
208
209 #endif
210
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.