Branch data 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 : 504 : static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
35 : : {
36 : 308 : unsigned int i;
37 : :
38 [ + + # # ]: 28728 : for (i = 0; i < sz; i++)
39 : 28224 : 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 : 0 : static inline bool hash_hashed(struct hlist_node *node)
77 : : {
78 [ # # ]: 0 : 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 : 53667 : static inline void hash_del(struct hlist_node *node)
106 : : {
107 [ + - + - : 53667 : hlist_del_init(node);
+ - # # ]
108 : 28 : }
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 : 0 : static inline void hash_del_rcu(struct hlist_node *node)
115 : : {
116 [ # # ]: 0 : 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 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) \
177 : : hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\
178 : : member)
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 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
|
