Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/include/linux/hashtable.h

  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 DEFINE_READ_MOSTLY_HASHTABLE(name, bits)                                \
 20         struct hlist_head name[1 << (bits)] __read_mostly =                     \
 21                         { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
 22 
 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
210 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us