2 * Sherlock Library -- Universal Hash Table
4 * (c) 2002 Martin Mares <mj@ucw.cz>
5 * (c) 2002 Robert Spalek <robert@ucw.cz>
9 * This is not a normal header file, it's a generator of hash tables.
10 * Each time you include it with parameters set in the corresponding
11 * preprocessor macros, it generates a hash table with the parameters
14 * You need to specify:
16 * HASH_NODE data type where a node dwells (usually a struct).
17 * HASH_PREFIX(x) macro to add a name prefix (used on all global names
18 * defined by the hash table generator).
20 * Then decide on type of keys:
22 * HASH_KEY_ATOMIC=f use node->f as a key of an atomic type (i.e.,
23 * a type which can be compared using `==')
24 * HASH_ATOMIC_TYPE (defaults to int).
25 * | HASH_KEY_STRING=f use node->f as a string key, allocated
26 * separately from the rest of the node.
27 * | HASH_KEY_ENDSTRING=f use node->f as a string key, allocated
28 * automatically at the end of the node struct
29 * (to be declared as "char f[1]" at the end).
30 * | HASH_KEY_COMPLEX use a multi-component key; as the name suggests,
31 * the passing of parameters is a bit complex then.
32 * The HASH_KEY_COMPLEX(x) macro should expand to
33 * `x k1, x k2, ... x kn' and you should also define:
34 * HASH_KEY_DECL declaration of function parameters in which key
35 * should be passed to all hash table operations.
36 * That is, `type1 k1, type2 k2, ... typen kn'.
37 * With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
40 * Then specify what operations you request (all names are automatically
41 * prefixed by calling HASH_PREFIX):
43 * <always defined> init() -- initialize the hash table.
44 * HASH_WANT_CLEANUP cleanup() -- deallocate the hash table.
45 * HASH_WANT_FIND node *find(key) -- find first node with the specified
46 * key, return NULL if no such node exists.
47 * HASH_WANT_FIND_NEXT node *find(key, node *start) -- find next node with
48 * the specified key, return NULL if no such node exists.
49 * HASH_WANT_NEW node *new(key) -- create new node with given key.
50 * Doesn't check whether it already exists.
51 * HASH_WANT_LOOKUP node *lookup(key) -- find node with given key,
52 * if it doesn't exist, create it. Defining
53 * HASH_GIVE_INIT_DATA is strongly recommended.
54 * HASH_WANT_DELETE int delete(key) -- delete and deallocate node
55 * with given key. Returns success.
56 * HASH_WANT_REMOVE remove(node *) -- delete and deallocate given node.
58 * You can also supply several functions:
60 * HASH_GIVE_HASHFN unsigned int hash(key) -- calculate hash value of key.
61 * We have sensible default hash functions for strings
63 * HASH_GIVE_EQ int eq(key1, key2) -- return whether keys are equal.
64 * By default, we use == for atomic types and either
65 * strcmp or strcasecmp for strings.
66 * HASH_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
67 * node should be allocated for dynamic data. Default=0
68 * or length of the string with HASH_KEY_ENDSTRING.
69 * HASH_GIVE_INIT_KEY void init_key(node *,key) -- initialize key in a newly
70 * created node. Defaults: assignment for atomic keys
71 * and static strings, strcpy for end-allocated strings.
72 * HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
73 * newly created node. Very useful for lookup operations.
74 * HASH_GIVE_ALLOC void *alloc(unsigned int size) -- allocate space for
75 * a node. Default is either normal or pooled allocation
76 * depending on whether we want deletions.
77 * void free(void *) -- the converse.
79 * ... and a couple of extra parameters:
81 * HASH_NOCASE string comparisons should be case-insensitive.
82 * HASH_DEFAULT_SIZE=n initially, use hash table of approx. `n' entries.
83 * HASH_CONSERVE_SPACE use as little space as possible.
84 * HASH_FN_BITS=n The hash function gives only `n' significant bits.
85 * HASH_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
86 * HASH_USE_POOL=pool Allocate all nodes from given mempool.
87 * Collides with delete/remove functions.
89 * You also get a iterator macro at no extra charge:
91 * HASH_FOR_ALL(hash_prefix, variable)
93 * // node *variable gets declared automatically
94 * do_something_with_node(variable);
95 * // use HASH_BREAK and HASH_CONTINUE instead of break and continue
96 * // you must not alter contents of the hash table here
100 * Then include <lib/hashtable.h> and voila, you have a hash table
101 * suiting all your needs (at least those which you've revealed :) ).
103 * After including this file, all parameter macros are automatically
107 #ifndef _SHERLOCK_HASHFUNC_H
108 #include "lib/hashfunc.h"
113 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
114 #error Some of the mandatory configuration macros are missing.
117 #define P(x) HASH_PREFIX(x)
119 /* Declare buckets and the hash table */
121 typedef HASH_NODE P(node);
123 typedef struct P(bucket) {
124 struct P(bucket) *next;
125 #ifndef HASH_CONSERVE_SPACE
133 uns hash_count, hash_max, hash_min, hash_hard_max;
139 /* Preset parameters */
141 #if defined(HASH_KEY_ATOMIC)
143 #define HASH_KEY(x) x HASH_KEY_ATOMIC
145 #ifndef HASH_ATOMIC_TYPE
146 # define HASH_ATOMIC_TYPE int
148 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
150 #ifndef HASH_GIVE_HASHFN
151 # define HASH_GIVE_HASHFN
152 static inline int P(hash) (HASH_ATOMIC_TYPE x)
153 { return hash_int(x); }
157 # define HASH_GIVE_EQ
158 static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
162 #ifndef HASH_GIVE_INIT_KEY
163 # define HASH_GIVE_INIT_KEY
164 static inline void P(init_key) (P(node) *n, HASH_ATOMIC_TYPE k)
165 { HASH_KEY(n->) = k; }
168 #ifndef HASH_CONSERVE_SPACE
169 #define HASH_CONSERVE_SPACE
172 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
174 #ifdef HASH_KEY_STRING
175 # define HASH_KEY(x) x HASH_KEY_STRING
176 # ifndef HASH_GIVE_INIT_KEY
177 # define HASH_GIVE_INIT_KEY
178 static inline void P(init_key) (P(node) *n, char *k)
179 { HASH_KEY(n->) = k; }
182 # define HASH_KEY(x) x HASH_KEY_ENDSTRING
183 # define HASH_GIVE_EXTRA_SIZE
184 static inline int P(extra_size) (char *k)
185 { return strlen(k); }
186 # ifndef HASH_GIVE_INIT_KEY
187 # define HASH_GIVE_INIT_KEY
188 static inline void P(init_key) (P(node) *n, char *k)
189 { strcpy(HASH_KEY(n->), k); }
192 #define HASH_KEY_DECL char *HASH_KEY( )
194 #ifndef HASH_GIVE_HASHFN
195 #define HASH_GIVE_HASHFN
196 static inline uns P(hash) (char *k)
199 return hash_string_nocase(k);
201 return hash_string(k);
207 # define HASH_GIVE_EQ
208 static inline int P(eq) (char *x, char *y)
211 return !strcasecmp(x,y);
218 #elif defined(HASH_KEY_COMPLEX)
220 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
223 #error You forgot to set the hash key type.
226 /* Defaults for missing parameters */
228 #ifndef HASH_GIVE_HASHFN
229 #error Unable to determine which hash function to use.
233 #error Unable to determine how to compare two keys.
236 #ifdef HASH_GIVE_EXTRA_SIZE
237 /* This trickery is needed to avoid `unused parameter' warnings */
238 #define HASH_EXTRA_SIZE P(extra_size)
241 * Beware, C macros are expanded iteratively, not recursively,
242 * hence we get only a _single_ argument, although the expansion
243 * of HASH_KEY contains commas.
245 #define HASH_EXTRA_SIZE(x) 0
248 #ifndef HASH_GIVE_INIT_KEY
249 #error Unable to determine how to initialize keys.
252 #ifndef HASH_GIVE_INIT_DATA
253 static inline void P(init_data) (P(node) *n UNUSED)
260 #ifndef HASH_GIVE_ALLOC
263 static inline void * P(alloc) (unsigned int size)
264 { return mp_alloc_fast(HASH_USE_POOL, size); }
268 static inline void * P(alloc) (unsigned int size)
269 { return xmalloc(size); }
271 static inline void P(free) (void *x)
277 #ifndef HASH_DEFAULT_SIZE
278 #define HASH_DEFAULT_SIZE 32
282 #define HASH_FN_BITS 32
285 /* Now the operations */
287 static void P(alloc_table) (void)
289 T.hash_size = nextprime(T.hash_size);
290 T.ht = xmalloc(sizeof(void *) * T.hash_size);
291 bzero(T.ht, sizeof(void *) * T.hash_size);
292 if (2*T.hash_size < T.hash_hard_max)
293 T.hash_max = 2*T.hash_size;
296 if (T.hash_size/2 > HASH_DEFAULT_SIZE)
297 T.hash_min = T.hash_size/4;
302 static void P(init) (void)
305 T.hash_size = HASH_DEFAULT_SIZE;
306 #if HASH_FN_BITS < 28
307 T.hash_hard_max = 1 << HASH_FN_BITS;
309 T.hash_hard_max = 1 << 28;
314 #ifdef HASH_WANT_CLEANUP
315 static void P(cleanup) (void)
317 #ifndef HASH_USE_POOL
321 for (i=0; i<T.hash_size; i++)
322 for (b=T.ht[i]; b; b=bb)
332 static inline uns P(bucket_hash) (P(bucket) *b)
334 #ifdef HASH_CONSERVE_SPACE
335 return P(hash)(HASH_KEY(b->n.));
341 static void P(rehash) (uns size)
344 P(bucket) **oldt = T.ht, **newt;
345 uns oldsize = T.hash_size;
348 // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
352 for (i=0; i<oldsize; i++)
358 h = P(bucket_hash)(b) % T.hash_size;
367 #ifdef HASH_WANT_FIND
368 static P(node) * P(find) (HASH_KEY_DECL)
370 uns h0 = P(hash) (HASH_KEY( ));
371 uns h = h0 % T.hash_size;
374 for (b=T.ht[h]; b; b=b->next)
377 #ifndef HASH_CONSERVE_SPACE
380 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
387 #ifdef HASH_WANT_FIND_NEXT
388 static P(node) * P(find_next) (HASH_KEY_DECL, P(node) *start)
390 #ifndef HASH_CONSERVE_SPACE
391 uns h0 = P(hash) (HASH_KEY( ));
393 P(bucket) *b = SKIP_BACK(P(bucket), n, start);
398 #ifndef HASH_CONSERVE_SPACE
401 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
409 static P(node) * P(new) (HASH_KEY_DECL)
414 h0 = P(hash) (HASH_KEY( ));
415 h = h0 % T.hash_size;
416 b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
419 #ifndef HASH_CONSERVE_SPACE
422 P(init_key)(&b->n, HASH_KEY( ));
424 if (T.hash_count++ >= T.hash_max)
425 P(rehash)(2*T.hash_size);
430 #ifdef HASH_WANT_LOOKUP
431 static P(node) * P(lookup) (HASH_KEY_DECL)
433 uns h0 = P(hash) (HASH_KEY( ));
434 uns h = h0 % T.hash_size;
437 for (b=T.ht[h]; b; b=b->next)
440 #ifndef HASH_CONSERVE_SPACE
443 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
447 b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
450 #ifndef HASH_CONSERVE_SPACE
453 P(init_key)(&b->n, HASH_KEY( ));
455 if (T.hash_count++ >= T.hash_max)
456 P(rehash)(2*T.hash_size);
461 #ifdef HASH_WANT_DELETE
462 static int P(delete) (HASH_KEY_DECL)
464 uns h0 = P(hash) (HASH_KEY( ));
465 uns h = h0 % T.hash_size;
468 for (bb=&T.ht[h]; b=*bb; bb=&b->next)
471 #ifndef HASH_CONSERVE_SPACE
474 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
478 if (--T.hash_count < T.hash_min)
479 P(rehash)(T.hash_size/2);
487 #ifdef HASH_WANT_REMOVE
488 static void P(remove) (P(node) *n)
490 P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
491 uns h0 = P(bucket_hash)(x);
492 uns h = h0 % T.hash_size;
495 for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
500 if (--T.hash_count < T.hash_min)
501 P(rehash)(T.hash_size/2);
505 /* And the iterator */
509 #define HASH_FOR_ALL(h_px, h_var) \
512 struct HASH_GLUE(h_px,bucket) *h_buck; \
513 for (h_slot=0; h_slot < HASH_GLUE(h_px,table).hash_size; h_slot++) \
514 for (h_buck = HASH_GLUE(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next) \
516 HASH_GLUE(h_px,node) *h_var = &h_buck->n;
517 #define HASH_END_FOR } } while(0)
519 #define HASH_CONTINUE continue
520 #define HASH_GLUE(x,y) x##_##y
524 /* Finally, undefine all the parameters */
529 #undef HASH_ATOMIC_TYPE
530 #undef HASH_CONSERVE_SPACE
531 #undef HASH_DEFAULT_SIZE
532 #undef HASH_EXTRA_SIZE
534 #undef HASH_GIVE_ALLOC
536 #undef HASH_GIVE_EXTRA_SIZE
537 #undef HASH_GIVE_HASHFN
538 #undef HASH_GIVE_INIT_DATA
539 #undef HASH_GIVE_INIT_KEY
541 #undef HASH_KEY_ATOMIC
542 #undef HASH_KEY_COMPLEX
544 #undef HASH_KEY_ENDSTRING
545 #undef HASH_KEY_STRING
550 #undef HASH_WANT_CLEANUP
551 #undef HASH_WANT_DELETE
552 #undef HASH_WANT_FIND
553 #undef HASH_WANT_FIND_NEXT
554 #undef HASH_WANT_LOOKUP
556 #undef HASH_WANT_REMOVE