~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/include/linux/hashtable.h

Version: ~ [ linux-5.5-rc7 ] ~ [ linux-5.4.13 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.97 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.166 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.210 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.210 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.81 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /* SPDX-License-Identifier: GPL-2.0 */
  2 /*
  3  * Statically sized hash table implementation
  4  * (C) 2012  Sasha Levin <levinsasha928@gmail.com>
  5  */
  6 
  7 #ifndef _LINUX_HASHTABLE_H
  8 #define _LINUX_HASHTABLE_H
  9 
 10 #include <linux/list.h>
 11 #include <linux/types.h>
 12 #include <linux/kernel.h>
 13 #include <linux/bitops.h>
 14 #include <linux/hash.h>
 15 #include <linux/log2.h>
 16 
 17 #define DEFINE_HASHTABLE(name, bits)                                            \
 18         struct hlist_head name[1 << (bits)] =                                   \
 19                         { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
 20 
 21 #define DECLARE_HASHTABLE(name, bits)                                           \
 22         struct hlist_head name[1 << (bits)]
 23 
 24 #define HASH_SIZE(name) (ARRAY_SIZE(name))
 25 #define HASH_BITS(name) ilog2(HASH_SIZE(name))
 26 
 27 /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
 28 #define hash_min(val, bits)                                                     \
 29         (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
 30 
 31 static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
 32 {
 33         unsigned int i;
 34 
 35         for (i = 0; i < sz; i++)
 36                 INIT_HLIST_HEAD(&ht[i]);
 37 }
 38 
 39 /**
 40  * hash_init - initialize a hash table
 41  * @hashtable: hashtable to be initialized
 42  *
 43  * Calculates the size of the hashtable from the given parameter, otherwise
 44  * same as hash_init_size.
 45  *
 46  * This has to be a macro since HASH_BITS() will not work on pointers since
 47  * it calculates the size during preprocessing.
 48  */
 49 #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
 50 
 51 /**
 52  * hash_add - add an object to a hashtable
 53  * @hashtable: hashtable to add to
 54  * @node: the &struct hlist_node of the object to be added
 55  * @key: the key of the object to be added
 56  */
 57 #define hash_add(hashtable, node, key)                                          \
 58         hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
 59 
 60 /**
 61  * hash_hashed - check whether an object is in any hashtable
 62  * @node: the &struct hlist_node of the object to be checked
 63  */
 64 static inline bool hash_hashed(struct hlist_node *node)
 65 {
 66         return !hlist_unhashed(node);
 67 }
 68 
 69 static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
 70 {
 71         unsigned int i;
 72 
 73         for (i = 0; i < sz; i++)
 74                 if (!hlist_empty(&ht[i]))
 75                         return false;
 76 
 77         return true;
 78 }
 79 
 80 /**
 81  * hash_empty - check whether a hashtable is empty
 82  * @hashtable: hashtable to check
 83  *
 84  * This has to be a macro since HASH_BITS() will not work on pointers since
 85  * it calculates the size during preprocessing.
 86  */
 87 #define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
 88 
 89 /**
 90  * hash_del - remove an object from a hashtable
 91  * @node: &struct hlist_node of the object to remove
 92  */
 93 static inline void hash_del(struct hlist_node *node)
 94 {
 95         hlist_del_init(node);
 96 }
 97 
 98 /**
 99  * hash_for_each - iterate over a hashtable
100  * @name: hashtable to iterate
101  * @bkt: integer to use as bucket loop cursor
102  * @obj: the type * to use as a loop cursor for each entry
103  * @member: the name of the hlist_node within the struct
104  */
105 #define hash_for_each(name, bkt, obj, member)                           \
106         for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
107                         (bkt)++)\
108                 hlist_for_each_entry(obj, &name[bkt], member)
109 
110 /**
111  * hash_for_each_safe - iterate over a hashtable safe against removal of
112  * hash entry
113  * @name: hashtable to iterate
114  * @bkt: integer to use as bucket loop cursor
115  * @tmp: a &struct used for temporary storage
116  * @obj: the type * to use as a loop cursor for each entry
117  * @member: the name of the hlist_node within the struct
118  */
119 #define hash_for_each_safe(name, bkt, tmp, obj, member)                 \
120         for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
121                         (bkt)++)\
122                 hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
123 
124 /**
125  * hash_for_each_possible - iterate over all possible objects hashing to the
126  * same bucket
127  * @name: hashtable to iterate
128  * @obj: the type * to use as a loop cursor for each entry
129  * @member: the name of the hlist_node within the struct
130  * @key: the key of the objects to iterate over
131  */
132 #define hash_for_each_possible(name, obj, member, key)                  \
133         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
134 
135 /**
136  * hash_for_each_possible_safe - iterate over all possible objects hashing to the
137  * same bucket safe against removals
138  * @name: hashtable to iterate
139  * @obj: the type * to use as a loop cursor for each entry
140  * @tmp: a &struct used for temporary storage
141  * @member: the name of the hlist_node within the struct
142  * @key: the key of the objects to iterate over
143  */
144 #define hash_for_each_possible_safe(name, obj, tmp, member, key)        \
145         hlist_for_each_entry_safe(obj, tmp,\
146                 &name[hash_min(key, HASH_BITS(name))], member)
147 
148 
149 #endif
150 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp