| blob | b2fdacdf00f48ce5665ca7f1292dee40bc7788fa |
1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
2 * reiser4/README */
4 /* A hash table class that uses hash chains (singly-linked) and is
5 parametrized to provide type safety. */
7 #ifndef __REISER4_TYPE_SAFE_HASH_H__
8 #define __REISER4_TYPE_SAFE_HASH_H__
12 #include <asm/errno.h>
13 /* Step 1: Use TYPE_SAFE_HASH_DECLARE() to define the TABLE and LINK objects
14 based on the object type. You need to declare the item type before
15 this definition, define it after this definition. */
16 #define TYPE_SAFE_HASH_DECLARE(PREFIX,ITEM_TYPE) \
17 \
18 typedef struct PREFIX##_hash_table_ PREFIX##_hash_table; \
19 typedef struct PREFIX##_hash_link_ PREFIX##_hash_link; \
20 \
21 struct PREFIX##_hash_table_ \
22 { \
23 ITEM_TYPE **_table; \
24 __u32 _buckets; \
25 }; \
26 \
27 struct PREFIX##_hash_link_ \
28 { \
29 ITEM_TYPE *_next; \
30 }
32 /* Step 2: Define the object type of the hash: give it field of type
33 PREFIX_hash_link. */
35 /* Step 3: Use TYPE_SAFE_HASH_DEFINE to define the hash table interface using
36 the type and field name used in step 3. The arguments are:
38 ITEM_TYPE The item type being hashed
39 KEY_TYPE The type of key being hashed
40 KEY_NAME The name of the key field within the item
41 LINK_NAME The name of the link field within the item, which you must make type PREFIX_hash_link)
42 HASH_FUNC The name of the hash function (or macro, takes const pointer to key)
43 EQ_FUNC The name of the equality function (or macro, takes const pointer to two keys)
45 It implements these functions:
47 prefix_hash_init Initialize the table given its size.
48 prefix_hash_insert Insert an item
49 prefix_hash_insert_index Insert an item w/ precomputed hash_index
50 prefix_hash_find Find an item by key
51 prefix_hash_find_index Find an item w/ precomputed hash_index
52 prefix_hash_remove Remove an item, returns 1 if found, 0 if not found
53 prefix_hash_remove_index Remove an item w/ precomputed hash_index
55 If you'd like something to be done differently, feel free to ask me
56 for modifications. Additional features that could be added but
57 have not been:
59 prefix_hash_remove_key Find and remove an item by key
60 prefix_hash_remove_key_index Find and remove an item by key w/ precomputed hash_index
62 The hash_function currently receives only the key as an argument,
63 meaning it must somehow know the number of buckets. If this is a
64 problem let me know.
66 This hash table uses a single-linked hash chain. This means
67 insertion is fast but deletion requires searching the chain.
69 There is also the doubly-linked hash chain approach, under which
70 deletion requires no search but the code is longer and it takes two
71 pointers per item.
73 The circularly-linked approach has the shortest code but requires
74 two pointers per bucket, doubling the size of the bucket array (in
75 addition to two pointers per item).
76 */
77 #define TYPE_SAFE_HASH_DEFINE(PREFIX,ITEM_TYPE,KEY_TYPE,KEY_NAME,LINK_NAME,HASH_FUNC,EQ_FUNC) \
78 \
79 static __inline__ void \
80 PREFIX##_check_hash (PREFIX##_hash_table *table UNUSED_ARG, \
81 __u32 hash UNUSED_ARG) \
82 { \
84 } \
85 \
86 static __inline__ int \
87 PREFIX##_hash_init (PREFIX##_hash_table *hash, \
88 __u32 buckets) \
89 { \
90 hash->_table = (ITEM_TYPE**) KMALLOC (sizeof (ITEM_TYPE*) * buckets); \
91 hash->_buckets = buckets; \
92 if (hash->_table == NULL) \
93 { \
94 return RETERR(-ENOMEM); \
95 } \
96 memset (hash->_table, 0, sizeof (ITEM_TYPE*) * buckets); \
98 return 0; \
99 } \
100 \
101 static __inline__ void \
102 PREFIX##_hash_done (PREFIX##_hash_table *hash) \
103 { \
104 if (REISER4_DEBUG && hash->_table != NULL) { \
105 __u32 i; \
106 for (i = 0 ; i < hash->_buckets ; ++ i) \
108 } \
109 if (hash->_table != NULL) \
110 KFREE (hash->_table, sizeof (ITEM_TYPE*) * hash->_buckets); \
111 hash->_table = NULL; \
112 } \
113 \
114 static __inline__ void \
115 PREFIX##_hash_prefetch_next (ITEM_TYPE *item) \
116 { \
117 prefetch(item->LINK_NAME._next); \
118 } \
119 \
120 static __inline__ void \
121 PREFIX##_hash_prefetch_bucket (PREFIX##_hash_table *hash, \
122 __u32 index) \
123 { \
124 prefetch(hash->_table[index]); \
125 } \
126 \
127 static __inline__ ITEM_TYPE* \
128 PREFIX##_hash_find_index (PREFIX##_hash_table *hash, \
129 __u32 hash_index, \
130 KEY_TYPE const *find_key) \
131 { \
132 ITEM_TYPE *item; \
133 \
134 PREFIX##_check_hash(hash, hash_index); \
135 \
136 for (item = hash->_table[hash_index]; \
137 item != NULL; \
138 item = item->LINK_NAME._next) \
139 { \
140 prefetch(item->LINK_NAME._next); \
141 prefetch(item->LINK_NAME._next + offsetof(ITEM_TYPE, KEY_NAME)); \
142 if (EQ_FUNC (& item->KEY_NAME, find_key)) \
143 { \
144 return item; \
145 } \
146 } \
147 \
148 return NULL; \
149 } \
150 \
151 static __inline__ ITEM_TYPE* \
152 PREFIX##_hash_find_index_lru (PREFIX##_hash_table *hash, \
153 __u32 hash_index, \
154 KEY_TYPE const *find_key) \
155 { \
156 ITEM_TYPE ** item = &hash->_table[hash_index]; \
157 \
158 PREFIX##_check_hash(hash, hash_index); \
159 \
160 while (*item != NULL) { \
161 prefetch(&(*item)->LINK_NAME._next); \
162 if (EQ_FUNC (&(*item)->KEY_NAME, find_key)) { \
163 ITEM_TYPE *found; \
164 \
165 found = *item; \
166 *item = found->LINK_NAME._next; \
167 found->LINK_NAME._next = hash->_table[hash_index]; \
168 hash->_table[hash_index] = found; \
169 return found; \
170 } \
171 item = &(*item)->LINK_NAME._next; \
172 } \
173 return NULL; \
174 } \
175 \
176 static __inline__ int \
177 PREFIX##_hash_remove_index (PREFIX##_hash_table *hash, \
178 __u32 hash_index, \
179 ITEM_TYPE *del_item) \
180 { \
181 ITEM_TYPE ** hash_item_p = &hash->_table[hash_index]; \
182 \
183 PREFIX##_check_hash(hash, hash_index); \
184 \
185 while (*hash_item_p != NULL) { \
186 prefetch(&(*hash_item_p)->LINK_NAME._next); \
187 if (*hash_item_p == del_item) { \
188 *hash_item_p = (*hash_item_p)->LINK_NAME._next; \
189 return 1; \
190 } \
191 hash_item_p = &(*hash_item_p)->LINK_NAME._next; \
192 } \
193 return 0; \
194 } \
195 \
196 static __inline__ void \
197 PREFIX##_hash_insert_index (PREFIX##_hash_table *hash, \
198 __u32 hash_index, \
199 ITEM_TYPE *ins_item) \
200 { \
201 PREFIX##_check_hash(hash, hash_index); \
202 \
203 ins_item->LINK_NAME._next = hash->_table[hash_index]; \
204 hash->_table[hash_index] = ins_item; \
205 } \
206 \
207 static __inline__ void \
208 PREFIX##_hash_insert_index_rcu (PREFIX##_hash_table *hash, \
209 __u32 hash_index, \
210 ITEM_TYPE *ins_item) \
211 { \
212 PREFIX##_check_hash(hash, hash_index); \
213 \
214 ins_item->LINK_NAME._next = hash->_table[hash_index]; \
215 smp_wmb(); \
216 hash->_table[hash_index] = ins_item; \
217 } \
218 \
219 static __inline__ ITEM_TYPE* \
220 PREFIX##_hash_find (PREFIX##_hash_table *hash, \
221 KEY_TYPE const *find_key) \
222 { \
223 return PREFIX##_hash_find_index (hash, HASH_FUNC(hash, find_key), find_key); \
224 } \
225 \
226 static __inline__ ITEM_TYPE* \
227 PREFIX##_hash_find_lru (PREFIX##_hash_table *hash, \
228 KEY_TYPE const *find_key) \
229 { \
230 return PREFIX##_hash_find_index_lru (hash, HASH_FUNC(hash, find_key), find_key); \
231 } \
232 \
233 static __inline__ int \
234 PREFIX##_hash_remove (PREFIX##_hash_table *hash, \
235 ITEM_TYPE *del_item) \
236 { \
237 return PREFIX##_hash_remove_index (hash, \
238 HASH_FUNC(hash, &del_item->KEY_NAME), del_item); \
239 } \
240 \
241 static __inline__ int \
242 PREFIX##_hash_remove_rcu (PREFIX##_hash_table *hash, \
243 ITEM_TYPE *del_item) \
244 { \
245 return PREFIX##_hash_remove (hash, del_item); \
246 } \
247 \
248 static __inline__ void \
249 PREFIX##_hash_insert (PREFIX##_hash_table *hash, \
250 ITEM_TYPE *ins_item) \
251 { \
252 return PREFIX##_hash_insert_index (hash, \
253 HASH_FUNC(hash, &ins_item->KEY_NAME), ins_item); \
254 } \
255 \
256 static __inline__ void \
257 PREFIX##_hash_insert_rcu (PREFIX##_hash_table *hash, \
258 ITEM_TYPE *ins_item) \
259 { \
260 return PREFIX##_hash_insert_index_rcu (hash, HASH_FUNC(hash, &ins_item->KEY_NAME), \
261 ins_item); \
262 } \
263 \
264 static __inline__ ITEM_TYPE * \
265 PREFIX##_hash_first (PREFIX##_hash_table *hash, __u32 ind) \
266 { \
267 ITEM_TYPE *first; \
268 \
269 for (first = NULL; ind < hash->_buckets; ++ ind) { \
270 first = hash->_table[ind]; \
271 if (first != NULL) \
272 break; \
273 } \
274 return first; \
275 } \
276 \
277 static __inline__ ITEM_TYPE * \
278 PREFIX##_hash_next (PREFIX##_hash_table *hash, \
279 ITEM_TYPE *item) \
280 { \
281 ITEM_TYPE *next; \
282 \
283 if (item == NULL) \
284 return NULL; \
285 next = item->LINK_NAME._next; \
286 if (next == NULL) \
287 next = PREFIX##_hash_first (hash, HASH_FUNC(hash, &item->KEY_NAME) + 1); \
288 return next; \
289 } \
290 \
291 typedef struct {} PREFIX##_hash_dummy
293 #define for_all_ht_buckets(table, head) \
294 for ((head) = &(table) -> _table[ 0 ] ; \
295 (head) != &(table) -> _table[ (table) -> _buckets ] ; ++ (head))
297 #define for_all_in_bucket(bucket, item, next, field) \
298 for ((item) = *(bucket), (next) = (item) ? (item) -> field._next : NULL ; \
299 (item) != NULL ; \
300 (item) = (next), (next) = (item) ? (item) -> field._next : NULL )
302 #define for_all_in_htable(table, prefix, item, next) \
303 for ((item) = prefix ## _hash_first ((table), 0), \
304 (next) = prefix ## _hash_next ((table), (item)) ; \
305 (item) != NULL ; \
306 (item) = (next), \
307 (next) = prefix ## _hash_next ((table), (item)))
309 /* __REISER4_TYPE_SAFE_HASH_H__ */
310 #endif
312 /* Make Linus happy.
313 Local variables:
314 c-indentation-style: "K&R"
315 mode-name: "LC"
316 c-basic-offset: 8
317 tab-width: 8
318 fill-column: 120
319 End:
320 */