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 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