blob: 661e5c2a8e2a49e30d2fe3895f234e321ec81c71 [file] [log] [blame]
Sasha Levind9b482c2012-10-30 14:45:57 -04001/*
2 * Statically sized hash table implementation
3 * (C) 2012 Sasha Levin <levinsasha928@gmail.com>
4 */
5
6#ifndef _LINUX_HASHTABLE_H
7#define _LINUX_HASHTABLE_H
8
9#include <linux/list.h>
10#include <linux/types.h>
11#include <linux/kernel.h>
12#include <linux/hash.h>
13#include <linux/rculist.h>
14
15#define DEFINE_HASHTABLE(name, bits) \
16 struct hlist_head name[1 << (bits)] = \
17 { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
18
Eric Dumazet6180d9d2015-11-18 06:31:01 -080019#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
Sasha Levind9b482c2012-10-30 14:45:57 -040023#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
33static 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 */
75static inline bool hash_hashed(struct hlist_node *node)
76{
77 return !hlist_unhashed(node);
78}
79
80static 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 */
104static 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 */
113static 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
Sasha Levind9b482c2012-10-30 14:45:57 -0400122 * @obj: the type * to use as a loop cursor for each entry
123 * @member: the name of the hlist_node within the struct
124 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800125#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)
Sasha Levind9b482c2012-10-30 14:45:57 -0400129
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
Sasha Levind9b482c2012-10-30 14:45:57 -0400134 * @obj: the type * to use as a loop cursor for each entry
135 * @member: the name of the hlist_node within the struct
136 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800137#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)
Sasha Levind9b482c2012-10-30 14:45:57 -0400141
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
Sasha Levind9b482c2012-10-30 14:45:57 -0400147 * @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 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800151#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)
Sasha Levind9b482c2012-10-30 14:45:57 -0400155
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
Sasha Levind9b482c2012-10-30 14:45:57 -0400161 * @member: the name of the hlist_node within the struct
162 * @key: the key of the objects to iterate over
163 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800164#define hash_for_each_possible(name, obj, member, key) \
165 hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
Sasha Levind9b482c2012-10-30 14:45:57 -0400166
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
Sasha Levind9b482c2012-10-30 14:45:57 -0400173 * @member: the name of the hlist_node within the struct
174 * @key: the key of the objects to iterate over
175 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800176#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)
Sasha Levind9b482c2012-10-30 14:45:57 -0400179
180/**
Alexey Kardashevskiy81fcfb82013-08-28 18:37:39 +1000181 * 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/**
Sasha Levind9b482c2012-10-30 14:45:57 -0400196 * 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
Sasha Levind9b482c2012-10-30 14:45:57 -0400200 * @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 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800204#define hash_for_each_possible_safe(name, obj, tmp, member, key) \
205 hlist_for_each_entry_safe(obj, tmp,\
Sasha Levind9b482c2012-10-30 14:45:57 -0400206 &name[hash_min(key, HASH_BITS(name))], member)
207
208
209#endif