]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
1698872b JP |
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 | ||
1698872b JP |
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 |