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 * @name: hashtable to iterate 171 * @obj: the type * to use as a loop cursor for each entry 172 * @member: the name of the hlist_node within the struct 173 * @key: the key of the objects to iterate over 174 */ 175 #define hash_for_each_possible_rcu(name, obj, member, key) \ 176 hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\ 177 member) 178 179 /** 180 * hash_for_each_possible_rcu_notrace - iterate over all possible objects hashing 181 * to the same bucket in an rcu enabled hashtable in a rcu enabled hashtable 182 * @name: hashtable to iterate 183 * @obj: the type * to use as a loop cursor for each entry 184 * @member: the name of the hlist_node within the struct 185 * @key: the key of the objects to iterate over 186 * 187 * This is the same as hash_for_each_possible_rcu() except that it does 188 * not do any RCU debugging or tracing. 189 */ 190 #define hash_for_each_possible_rcu_notrace(name, obj, member, key) \ 191 hlist_for_each_entry_rcu_notrace(obj, \ 192 &name[hash_min(key, HASH_BITS(name))], member) 193 194 /** 195 * hash_for_each_possible_safe - iterate over all possible objects hashing to the 196 * same bucket safe against removals 197 * @name: hashtable to iterate 198 * @obj: the type * to use as a loop cursor for each entry 199 * @tmp: a &struct used for temporary storage 200 * @member: the name of the hlist_node within the struct 201 * @key: the key of the objects to iterate over 202 */ 203 #define hash_for_each_possible_safe(name, obj, tmp, member, key) \ 204 hlist_for_each_entry_safe(obj, tmp,\ 205 &name[hash_min(key, HASH_BITS(name))], member) 206 207 208 #endif 209