Debian Codegraph @

include/hashtable.h

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