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 29static 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 */ 71static inline bool hash_hashed(struct hlist_node *node) 72{ 73 return !hlist_unhashed(node); 74} 75 76static 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 */ 100static 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 */ 109static 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_rcu_notrace - iterate over all possible objects hashing 178 * to the same bucket in an rcu enabled hashtable in a rcu enabled hashtable 179 * @name: hashtable to iterate 180 * @obj: the type * to use as a loop cursor for each entry 181 * @member: the name of the hlist_node within the struct 182 * @key: the key of the objects to iterate over 183 * 184 * This is the same as hash_for_each_possible_rcu() except that it does 185 * not do any RCU debugging or tracing. 186 */ 187#define hash_for_each_possible_rcu_notrace(name, obj, member, key) \ 188 hlist_for_each_entry_rcu_notrace(obj, \ 189 &name[hash_min(key, HASH_BITS(name))], member) 190 191/** 192 * hash_for_each_possible_safe - iterate over all possible objects hashing to the 193 * same bucket safe against removals 194 * @name: hashtable to iterate 195 * @obj: the type * to use as a loop cursor for each entry 196 * @tmp: a &struct used for temporary storage 197 * @member: the name of the hlist_node within the struct 198 * @key: the key of the objects to iterate over 199 */ 200#define hash_for_each_possible_safe(name, obj, tmp, member, key) \ 201 hlist_for_each_entry_safe(obj, tmp,\ 202 &name[hash_min(key, HASH_BITS(name))], member) 203 204 205#endif 206