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