include/linux/hashtable.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /*
0003  * Statically sized hash table implementation
0004  * (C) 2012  Sasha Levin <levinsasha928@gmail.com>
0005  */
0006
0007 #ifndef _LINUX_HASHTABLE_H
0008 #define _LINUX_HASHTABLE_H
0009
0010 #include <linux/list.h>
0011 #include <linux/types.h>
0012 #include <linux/kernel.h>
0013 #include <linux/hash.h>
0014 #include <linux/rculist.h>
0015
0016 #define DEFINE_HASHTABLE(name, bits)                        \
0017     struct hlist_head name[1 << (bits)] =                   \
0018             { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
0019
0020 #define DEFINE_READ_MOSTLY_HASHTABLE(name, bits)                \
0021     struct hlist_head name[1 << (bits)] __read_mostly =         \
0022             { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
0023
0024 #define DECLARE_HASHTABLE(name, bits)                                       \
0025     struct hlist_head name[1 << (bits)]
0026
0027 #define HASH_SIZE(name) (ARRAY_SIZE(name))
0028 #define HASH_BITS(name) ilog2(HASH_SIZE(name))
0029
0030 /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
0031 #define hash_min(val, bits)                         \
0032     (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
0033
0034 static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
0035 {
0036     unsigned int i;
0037
0038     for (i = 0; i < sz; i++)
0039         INIT_HLIST_HEAD(&ht[i]);
0040 }
0041
0042 /**
0043  * hash_init - initialize a hash table
0044  * @hashtable: hashtable to be initialized
0045  *
0046  * Calculates the size of the hashtable from the given parameter, otherwise
0047  * same as hash_init_size.
0048  *
0049  * This has to be a macro since HASH_BITS() will not work on pointers since
0050  * it calculates the size during preprocessing.
0051  */
0052 #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
0053
0054 /**
0055  * hash_add - add an object to a hashtable
0056  * @hashtable: hashtable to add to
0057  * @node: the &struct hlist_node of the object to be added
0058  * @key: the key of the object to be added
0059  */
0060 #define hash_add(hashtable, node, key)                      \
0061     hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
0062
0063 /**
0064  * hash_add_rcu - add an object to a rcu enabled hashtable
0065  * @hashtable: hashtable to add to
0066  * @node: the &struct hlist_node of the object to be added
0067  * @key: the key of the object to be added
0068  */
0069 #define hash_add_rcu(hashtable, node, key)                  \
0070     hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
0071
0072 /**
0073  * hash_hashed - check whether an object is in any hashtable
0074  * @node: the &struct hlist_node of the object to be checked
0075  */
0076 static inline bool hash_hashed(struct hlist_node *node)
0077 {
0078     return !hlist_unhashed(node);
0079 }
0080
0081 static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
0082 {
0083     unsigned int i;
0084
0085     for (i = 0; i < sz; i++)
0086         if (!hlist_empty(&ht[i]))
0087             return false;
0088
0089     return true;
0090 }
0091
0092 /**
0093  * hash_empty - check whether a hashtable is empty
0094  * @hashtable: hashtable to check
0095  *
0096  * This has to be a macro since HASH_BITS() will not work on pointers since
0097  * it calculates the size during preprocessing.
0098  */
0099 #define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
0100
0101 /**
0102  * hash_del - remove an object from a hashtable
0103  * @node: &struct hlist_node of the object to remove
0104  */
0105 static inline void hash_del(struct hlist_node *node)
0106 {
0107     hlist_del_init(node);
0108 }
0109
0110 /**
0111  * hash_del_rcu - remove an object from a rcu enabled hashtable
0112  * @node: &struct hlist_node of the object to remove
0113  */
0114 static inline void hash_del_rcu(struct hlist_node *node)
0115 {
0116     hlist_del_init_rcu(node);
0117 }
0118
0119 /**
0120  * hash_for_each - iterate over a hashtable
0121  * @name: hashtable to iterate
0122  * @bkt: integer to use as bucket loop cursor
0123  * @obj: the type * to use as a loop cursor for each entry
0124  * @member: the name of the hlist_node within the struct
0125  */
0126 #define hash_for_each(name, bkt, obj, member)               \
0127     for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
0128             (bkt)++)\
0129         hlist_for_each_entry(obj, &name[bkt], member)
0130
0131 /**
0132  * hash_for_each_rcu - iterate over a rcu enabled hashtable
0133  * @name: hashtable to iterate
0134  * @bkt: integer to use as bucket loop cursor
0135  * @obj: the type * to use as a loop cursor for each entry
0136  * @member: the name of the hlist_node within the struct
0137  */
0138 #define hash_for_each_rcu(name, bkt, obj, member)           \
0139     for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
0140             (bkt)++)\
0141         hlist_for_each_entry_rcu(obj, &name[bkt], member)
0142
0143 /**
0144  * hash_for_each_safe - iterate over a hashtable safe against removal of
0145  * hash entry
0146  * @name: hashtable to iterate
0147  * @bkt: integer to use as bucket loop cursor
0148  * @tmp: a &struct hlist_node used for temporary storage
0149  * @obj: the type * to use as a loop cursor for each entry
0150  * @member: the name of the hlist_node within the struct
0151  */
0152 #define hash_for_each_safe(name, bkt, tmp, obj, member)         \
0153     for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
0154             (bkt)++)\
0155         hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
0156
0157 /**
0158  * hash_for_each_possible - iterate over all possible objects hashing to the
0159  * same bucket
0160  * @name: hashtable to iterate
0161  * @obj: the type * to use as a loop cursor for each entry
0162  * @member: the name of the hlist_node within the struct
0163  * @key: the key of the objects to iterate over
0164  */
0165 #define hash_for_each_possible(name, obj, member, key)          \
0166     hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
0167
0168 /**
0169  * hash_for_each_possible_rcu - iterate over all possible objects hashing to the
0170  * same bucket in an rcu enabled hashtable
0171  * @name: hashtable to iterate
0172  * @obj: the type * to use as a loop cursor for each entry
0173  * @member: the name of the hlist_node within the struct
0174  * @key: the key of the objects to iterate over
0175  */
0176 #define hash_for_each_possible_rcu(name, obj, member, key, cond...) \
0177     hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\
0178         member, ## cond)
0179
0180 /**
0181  * hash_for_each_possible_rcu_notrace - iterate over all possible objects hashing
0182  * to the same bucket in an rcu enabled hashtable in a rcu enabled hashtable
0183  * @name: hashtable to iterate
0184  * @obj: the type * to use as a loop cursor for each entry
0185  * @member: the name of the hlist_node within the struct
0186  * @key: the key of the objects to iterate over
0187  *
0188  * This is the same as hash_for_each_possible_rcu() except that it does
0189  * not do any RCU debugging or tracing.
0190  */
0191 #define hash_for_each_possible_rcu_notrace(name, obj, member, key) \
0192     hlist_for_each_entry_rcu_notrace(obj, \
0193         &name[hash_min(key, HASH_BITS(name))], member)
0194
0195 /**
0196  * hash_for_each_possible_safe - iterate over all possible objects hashing to the
0197  * same bucket safe against removals
0198  * @name: hashtable to iterate
0199  * @obj: the type * to use as a loop cursor for each entry
0200  * @tmp: a &struct hlist_node used for temporary storage
0201  * @member: the name of the hlist_node within the struct
0202  * @key: the key of the objects to iterate over
0203  */
0204 #define hash_for_each_possible_safe(name, obj, tmp, member, key)    \
0205     hlist_for_each_entry_safe(obj, tmp,\
0206         &name[hash_min(key, HASH_BITS(name))], member)
0207
0208
0209 #endif