1 /* 2 * Statically sized hash table implementation 3 * (C) 2012 Sasha Levin <[email protected]> 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/bitops.h> 13 #include <linux/hash.h> 14 #include <linux/log2.h> 15 16 #ifndef ARRAY_SIZE 17 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) 18 #endif 19 20 #define DEFINE_HASHTABLE(name, bits) \ 21 struct hlist_head name[1 << (bits)] = \ 22 { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT } 23 24 #define DECLARE_HASHTABLE(name, bits) \ 25 struct hlist_head name[1 << (bits)] 26 27 #define HASH_SIZE(name) (ARRAY_SIZE(name)) 28 #define HASH_BITS(name) ilog2(HASH_SIZE(name)) 29 30 /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ 31 #define hash_min(val, bits) \ 32 (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits)) 33 34 static inline void __hash_init(struct hlist_head *ht, unsigned int sz) 35 { 36 unsigned int i; 37 38 for (i = 0; i < sz; i++) 39 INIT_HLIST_HEAD(&ht[i]); 40 } 41 42 /** 43 * hash_init - initialize a hash table 44 * @hashtable: hashtable to be initialized 45 * 46 * Calculates the size of the hashtable from the given parameter, otherwise 47 * same as hash_init_size. 48 * 49 * This has to be a macro since HASH_BITS() will not work on pointers since 50 * it calculates the size during preprocessing. 51 */ 52 #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable)) 53 54 /** 55 * hash_add - add an object to a hashtable 56 * @hashtable: hashtable to add to 57 * @node: the &struct hlist_node of the object to be added 58 * @key: the key of the object to be added 59 */ 60 #define hash_add(hashtable, node, key) \ 61 hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]) 62 63 /** 64 * hash_hashed - check whether an object is in any hashtable 65 * @node: the &struct hlist_node of the object to be checked 66 */ 67 static inline bool hash_hashed(struct hlist_node *node) 68 { 69 return !hlist_unhashed(node); 70 } 71 72 static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz) 73 { 74 unsigned int i; 75 76 for (i = 0; i < sz; i++) 77 if (!hlist_empty(&ht[i])) 78 return false; 79 80 return true; 81 } 82 83 /** 84 * hash_empty - check whether a hashtable is empty 85 * @hashtable: hashtable to check 86 * 87 * This has to be a macro since HASH_BITS() will not work on pointers since 88 * it calculates the size during preprocessing. 89 */ 90 #define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable)) 91 92 /** 93 * hash_del - remove an object from a hashtable 94 * @node: &struct hlist_node of the object to remove 95 */ 96 static inline void hash_del(struct hlist_node *node) 97 { 98 hlist_del_init(node); 99 } 100 101 /** 102 * hash_for_each - iterate over a hashtable 103 * @name: hashtable to iterate 104 * @bkt: integer to use as bucket loop cursor 105 * @obj: the type * to use as a loop cursor for each entry 106 * @member: the name of the hlist_node within the struct 107 */ 108 #define hash_for_each(name, bkt, obj, member) \ 109 for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\ 110 (bkt)++)\ 111 hlist_for_each_entry(obj, &name[bkt], member) 112 113 /** 114 * hash_for_each_safe - iterate over a hashtable safe against removal of 115 * hash entry 116 * @name: hashtable to iterate 117 * @bkt: integer to use as bucket loop cursor 118 * @tmp: a &struct used for temporary storage 119 * @obj: the type * to use as a loop cursor for each entry 120 * @member: the name of the hlist_node within the struct 121 */ 122 #define hash_for_each_safe(name, bkt, tmp, obj, member) \ 123 for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\ 124 (bkt)++)\ 125 hlist_for_each_entry_safe(obj, tmp, &name[bkt], member) 126 127 /** 128 * hash_for_each_possible - iterate over all possible objects hashing to the 129 * same bucket 130 * @name: hashtable to iterate 131 * @obj: the type * to use as a loop cursor for each entry 132 * @member: the name of the hlist_node within the struct 133 * @key: the key of the objects to iterate over 134 */ 135 #define hash_for_each_possible(name, obj, member, key) \ 136 hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member) 137 138 /** 139 * hash_for_each_possible_safe - iterate over all possible objects hashing to the 140 * same bucket safe against removals 141 * @name: hashtable to iterate 142 * @obj: the type * to use as a loop cursor for each entry 143 * @tmp: a &struct used for temporary storage 144 * @member: the name of the hlist_node within the struct 145 * @key: the key of the objects to iterate over 146 */ 147 #define hash_for_each_possible_safe(name, obj, tmp, member, key) \ 148 hlist_for_each_entry_safe(obj, tmp,\ 149 &name[hash_min(key, HASH_BITS(name))], member) 150 151 152 #endif 153