Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 5056 | serge | 1 | /* |
| 2 | * Statically sized hash table implementation |
||
| 3 | * (C) 2012 Sasha Levin |
||
| 4 | */ |
||
| 5 | |||
| 6 | #ifndef _LINUX_HASHTABLE_H |
||
| 7 | #define _LINUX_HASHTABLE_H |
||
| 8 | |||
| 9 | #include |
||
| 10 | #include |
||
| 11 | #include |
||
| 12 | #include |
||
| 13 | #include |
||
| 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 | |||
| 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 | */ |
||
| 71 | static inline bool hash_hashed(struct hlist_node *node) |
||
| 72 | { |
||
| 73 | return !hlist_unhashed(node); |
||
| 74 | } |
||
| 75 | |||
| 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 | */ |
||
| 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 | */ |
||
| 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_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 |