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  * @node: the &struct list_head to use as a loop cursor for each entry
 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(name, bkt, node, obj, member)                             \
 123         for ((bkt) = 0, node = NULL; node == NULL && (bkt) < HASH_SIZE(name); (bkt)++)\
 124                 hlist_for_each_entry(obj, node, &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  * @node: the &struct list_head to use as a loop cursor for each entry
 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  */
 134 #define hash_for_each_rcu(name, bkt, node, obj, member)                         \
 135         for ((bkt) = 0, node = NULL; node == NULL && (bkt) < HASH_SIZE(name); (bkt)++)\
 136                 hlist_for_each_entry_rcu(obj, node, &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  * @node: the &struct list_head to use as a loop cursor for each entry
 144  * @tmp: a &struct used for temporary storage
 145  * @obj: the type * to use as a loop cursor for each entry
 146  * @member: the name of the hlist_node within the struct
 147  */
 148 #define hash_for_each_safe(name, bkt, node, tmp, obj, member)                   \
 149         for ((bkt) = 0, node = NULL; node == NULL && (bkt) < HASH_SIZE(name); (bkt)++)\
 150                 hlist_for_each_entry_safe(obj, node, 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  * @node: the &struct list_head to use as a loop cursor for each entry
 158  * @member: the name of the hlist_node within the struct
 159  * @key: the key of the objects to iterate over
 160  */
 161 #define hash_for_each_possible(name, obj, node, member, key)                    \
 162         hlist_for_each_entry(obj, node, &name[hash_min(key, HASH_BITS(name))], member)
 163
 164 /**
 165  * hash_for_each_possible_rcu - iterate over all possible objects hashing to the
 166  * same bucket in an rcu enabled hashtable
 167  * in a rcu enabled hashtable
 168  * @name: hashtable to iterate
 169  * @obj: the type * to use as a loop cursor for each entry
 170  * @node: the &struct list_head to use as a loop cursor for each entry
 171  * @member: the name of the hlist_node within the struct
 172  * @key: the key of the objects to iterate over
 173  */
 174 #define hash_for_each_possible_rcu(name, obj, node, member, key)                \
 175         hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, HASH_BITS(name))], member)
 176
 177 /**
 178  * hash_for_each_possible_safe - iterate over all possible objects hashing to the
 179  * same bucket safe against removals
 180  * @name: hashtable to iterate
 181  * @obj: the type * to use as a loop cursor for each entry
 182  * @node: the &struct list_head to use as a loop cursor for each entry
 183  * @tmp: a &struct used for temporary storage
 184  * @member: the name of the hlist_node within the struct
 185  * @key: the key of the objects to iterate over
 186  */
 187 #define hash_for_each_possible_safe(name, obj, node, tmp, member, key)          \
 188         hlist_for_each_entry_safe(obj, node, tmp,                               \
 189                 &name[hash_min(key, HASH_BITS(name))], member)
 190
 191
 192 #endif