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