Line data Source code
1 : /* SPDX-License-Identifier: GPL-2.0 */
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 :
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 :
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 9 : static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
35 : {
36 0 : unsigned int i;
37 :
38 585 : for (i = 0; i < sz; i++)
39 576 : 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 2010 : static inline void hash_del(struct hlist_node *node)
106 : {
107 4018 : 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
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 : */
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)
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
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 : */
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)
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
148 : * @tmp: a &struct hlist_node used for temporary storage
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 : */
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)
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
162 : * @member: the name of the hlist_node within the struct
163 : * @key: the key of the objects to iterate over
164 : */
165 : #define hash_for_each_possible(name, obj, member, key) \
166 : hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
167 :
168 : /**
169 : * hash_for_each_possible_rcu - iterate over all possible objects hashing to the
170 : * same bucket in an rcu enabled hashtable
171 : * @name: hashtable to iterate
172 : * @obj: the type * to use as a loop cursor for each entry
173 : * @member: the name of the hlist_node within the struct
174 : * @key: the key of the objects to iterate over
175 : */
176 : #define hash_for_each_possible_rcu(name, obj, member, key, cond...) \
177 : hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\
178 : member, ## cond)
179 :
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 :
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
200 : * @tmp: a &struct hlist_node 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 : */
204 : #define hash_for_each_possible_safe(name, obj, tmp, member, key) \
205 : hlist_for_each_entry_safe(obj, tmp,\
206 : &name[hash_min(key, HASH_BITS(name))], member)
207 :
208 :
209 : #endif
|
