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