hashtable.h

  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/hash.h>
 14#include <linux/rculist.h>
 15
 16#define DEFINE_HASHTABLE(name, bits)						\
 17	struct hlist_head name[1 << (bits)] =					\
 18			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
 19
 20#define DEFINE_READ_MOSTLY_HASHTABLE(name, bits)				\
 21	struct hlist_head name[1 << (bits)] __read_mostly =			\
 22			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
 23
 24#define DECLARE_HASHTABLE(name, bits)                                   	\
 25	struct hlist_head name[1 << (bits)]
 26
 27#define HASH_SIZE(name) (ARRAY_SIZE(name))
 28#define HASH_BITS(name) ilog2(HASH_SIZE(name))
 29
 30/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
 31#define hash_min(val, bits)							\
 32	(sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
 33
 34static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
 35{
 36	unsigned int i;
 37
 38	for (i = 0; i < sz; i++)
 39		INIT_HLIST_HEAD(&ht[i]);
 40}
 41
 42/**
 43 * hash_init - initialize a hash table
 44 * @hashtable: hashtable to be initialized
 45 *
 46 * Calculates the size of the hashtable from the given parameter, otherwise
 47 * same as hash_init_size.
 48 *
 49 * This has to be a macro since HASH_BITS() will not work on pointers since
 50 * it calculates the size during preprocessing.
 51 */
 52#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
 53
 54/**
 55 * hash_add - add an object to a hashtable
 56 * @hashtable: hashtable to add to
 57 * @node: the &struct hlist_node of the object to be added
 58 * @key: the key of the object to be added
 59 */
 60#define hash_add(hashtable, node, key)						\
 61	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
 62
 63/**
 64 * hash_add_rcu - add an object to a rcu enabled hashtable
 65 * @hashtable: hashtable to add to
 66 * @node: the &struct hlist_node of the object to be added
 67 * @key: the key of the object to be added
 68 */
 69#define hash_add_rcu(hashtable, node, key)					\
 70	hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
 71
 72/**
 73 * hash_hashed - check whether an object is in any hashtable
 74 * @node: the &struct hlist_node of the object to be checked
 75 */
 76static inline bool hash_hashed(struct hlist_node *node)
 77{
 78	return !hlist_unhashed(node);
 79}
 80
 81static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
 82{
 83	unsigned int i;
 84
 85	for (i = 0; i < sz; i++)
 86		if (!hlist_empty(&ht[i]))
 87			return false;
 88
 89	return true;
 90}
 91
 92/**
 93 * hash_empty - check whether a hashtable is empty
 94 * @hashtable: hashtable to check
 95 *
 96 * This has to be a macro since HASH_BITS() will not work on pointers since
 97 * it calculates the size during preprocessing.
 98 */
 99#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
100
101/**
102 * hash_del - remove an object from a hashtable
103 * @node: &struct hlist_node of the object to remove
104 */
105static inline void hash_del(struct hlist_node *node)
106{
107	hlist_del_init(node);
108}
109
110/**
111 * hash_del_rcu - remove an object from a rcu enabled hashtable
112 * @node: &struct hlist_node of the object to remove
113 */
114static inline void hash_del_rcu(struct hlist_node *node)
115{
116	hlist_del_init_rcu(node);
117}
118
119/**
120 * hash_for_each - iterate over a hashtable
121 * @name: hashtable to iterate
122 * @bkt: integer to use as bucket loop cursor
123 * @obj: the type * to use as a loop cursor for each entry
124 * @member: the name of the hlist_node within the struct
125 */
126#define hash_for_each(name, bkt, obj, member)				\
127	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
128			(bkt)++)\
129		hlist_for_each_entry(obj, &name[bkt], member)
130
131/**
132 * hash_for_each_rcu - iterate over a rcu enabled hashtable
133 * @name: hashtable to iterate
134 * @bkt: integer to use as bucket loop cursor
135 * @obj: the type * to use as a loop cursor for each entry
136 * @member: the name of the hlist_node within the struct
137 */
138#define hash_for_each_rcu(name, bkt, obj, member)			\
139	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
140			(bkt)++)\
141		hlist_for_each_entry_rcu(obj, &name[bkt], member)
142
143/**
144 * hash_for_each_safe - iterate over a hashtable safe against removal of
145 * hash entry
146 * @name: hashtable to iterate
147 * @bkt: integer to use as bucket loop cursor
148 * @tmp: a &struct hlist_node used for temporary storage
149 * @obj: the type * to use as a loop cursor for each entry
150 * @member: the name of the hlist_node within the struct
151 */
152#define hash_for_each_safe(name, bkt, tmp, obj, member)			\
153	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
154			(bkt)++)\
155		hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
156
157/**
158 * hash_for_each_possible - iterate over all possible objects hashing to the
159 * same bucket
160 * @name: hashtable to iterate
161 * @obj: the type * to use as a loop cursor for each entry
162 * @member: the name of the hlist_node within the struct
163 * @key: the key of the objects to iterate over
164 */
165#define hash_for_each_possible(name, obj, member, key)			\
166	hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
167
168/**
169 * hash_for_each_possible_rcu - iterate over all possible objects hashing to the
170 * same bucket in an rcu enabled hashtable
171 * @name: hashtable to iterate
172 * @obj: the type * to use as a loop cursor for each entry
173 * @member: the name of the hlist_node within the struct
174 * @key: the key of the objects to iterate over
175 */
176#define hash_for_each_possible_rcu(name, obj, member, key, cond...)	\
177	hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\
178		member, ## cond)
179
180/**
181 * hash_for_each_possible_rcu_notrace - iterate over all possible objects hashing
182 * to the same bucket in an rcu enabled hashtable in a rcu enabled hashtable
183 * @name: hashtable to iterate
184 * @obj: the type * to use as a loop cursor for each entry
185 * @member: the name of the hlist_node within the struct
186 * @key: the key of the objects to iterate over
187 *
188 * This is the same as hash_for_each_possible_rcu() except that it does
189 * not do any RCU debugging or tracing.
190 */
191#define hash_for_each_possible_rcu_notrace(name, obj, member, key) \
192	hlist_for_each_entry_rcu_notrace(obj, \
193		&name[hash_min(key, HASH_BITS(name))], member)
194
195/**
196 * hash_for_each_possible_safe - iterate over all possible objects hashing to the
197 * same bucket safe against removals
198 * @name: hashtable to iterate
199 * @obj: the type * to use as a loop cursor for each entry
200 * @tmp: a &struct hlist_node used for temporary storage
201 * @member: the name of the hlist_node within the struct
202 * @key: the key of the objects to iterate over
203 */
204#define hash_for_each_possible_safe(name, obj, tmp, member, key)	\
205	hlist_for_each_entry_safe(obj, tmp,\
206		&name[hash_min(key, HASH_BITS(name))], member)
207
208
209#endif