lib/hashtable.h

   1 /*
   2  *      Sherlock Library -- Universal Hash Table
   3  *
   4  *      (c) 2002 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 /*
   8  *  This is not a normal header file, it's a generator of hash tables.
   9  *  Each time you include it with parameters set in the corresponding
  10  *  preprocessor macros, it generates a hash table with the parameters
  11  *  given.
  12  *
  13  *  You need to specify:
  14  *
  15  *  HASH_NODE           data type where a node dwells (usually a struct).
  16  *  HASH_PREFIX(x)      macro to add a name prefix (used on all global names
  17  *                      defined by the hash table generator).
  18  *
  19  *  Then decide on type of keys:
  20  *
  21  *  HASH_KEY_ATOMIC=f   use node->f as a key of an atomic type (i.e.,
  22  *                      a type which can be compared using `==')
  23  *                      HASH_ATOMIC_TYPE (defaults to int).
  24  *  | HASH_KEY_STRING=f use node->f as a string key, allocated
  25  *                      separately from the rest of the node.
  26  *  | HASH_KEY_ENDSTRING=f use node->f as a string key, allocated
  27  *                      automatically at the end of the node struct
  28  *                      (to be declared as "char f[1]" at the end).
  29  *  | HASH_KEY_COMPLEX  use a multi-component key; as the name suggests,
  30  *                      the passing of parameters is a bit complex then.
  31  *                      The HASH_KEY_COMPLEX(x) macro should expand to
  32  *                      `x k1, x k2, ... x kn' and you should also define:
  33  *    HASH_KEY_DECL     declaration of function parameters in which key
  34  *                      should be passed to all hash table operations.
  35  *                      That is, `type1 k1, type2 k2, ... typen kn'.
  36  *                      With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
  37  *                      are mandatory.
  38  *
  39  *  Then specify what operations you request (all names are automatically
  40  *  prefixed by calling HASH_PREFIX):
  41  *
  42  *  <always defined>    init() -- initialize the hash table.
  43  *  HASH_WANT_CLEANUP   cleanup() -- deallocate the hash table.
  44  *  HASH_WANT_FIND      node *find(key) -- find node with the specified
  45  *                      key, return NULL if no such node exists.
  46  *  HASH_WANT_NEW       node *new(key) -- create new node with given key.
  47  *                      Doesn't check whether it already exists.
  48  *  HASH_WANT_LOOKUP    node *lookup(key) -- find node with given key,
  49  *                      if it doesn't exist, create it. Defining
  50  *                      HASH_GIVE_INIT_DATA is strongly recommended.
  51  *  HASH_WANT_DELETE    int delete(key) -- delete and deallocate node
  52  *                      with given key. Returns success.
  53  *  HASH_WANT_REMOVE    remove(node *) -- delete and deallocate given node.
  54  *
  55  *  You can also supply several functions:
  56  *
  57  *  HASH_GIVE_HASHFN    unsigned int hash(key) -- calculate hash value of key.
  58  *                      We have sensible default hash functions for strings
  59  *                      and integers.
  60  *  HASH_GIVE_EQ        int eq(key1, key2) -- return whether keys are equal.
  61  *                      By default, we use == for atomic types and either
  62  *                      strcmp or strcasecmp for strings.
  63  *  HASH_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
  64  *                      node should be allocated for dynamic data. Default=0
  65  *                      or length of the string with HASH_KEY_ENDSTRING.
  66  *  HASH_GIVE_INIT_KEY  void init_key(node *,key) -- initialize key in a newly
  67  *                      created node. Defaults: assignment for atomic keys
  68  *                      and static strings, strcpy for end-allocated strings.
  69  *  HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
  70  *                      newly created node. Very useful for lookup operations.
  71  *  HASH_GIVE_ALLOC     void *alloc(unsigned int size) -- allocate space for
  72  *                      a node. Default is either normal or pooled allocation
  73  *                      depending on whether we want deletions.
  74  *                      void free(void *) -- the converse.
  75  *
  76  *  ... and a couple of extra parameters:
  77  *
  78  *  HASH_NOCASE         string comparisons should be case-insensitive.
  79  *  HASH_DEFAULT_SIZE=n initially, use hash table of approx. `n' entries.
  80  *  HASH_CONSERVE_SPACE use as little space as possible.
  81  *  HASH_FN_BITS=n      The hash function gives only `n' significant bits.
  82  *  HASH_ATOMIC_TYPE=t  Atomic values are of type `t' instead of int.
  83  *  HASH_USE_POOL=pool  Allocate all nodes from given mempool.
  84  *                      Collides with delete/remove functions.
  85  *
  86  *  You also get a iterator macro at no extra charge:
  87  *
  88  *  HASH_FOR_ALL(hash_prefix, variable)
  89  *    {
  90  *      // node *variable gets declared automatically
  91  *      do_something_with_node(variable);
  92  *      // use HASH_BREAK and HASH_CONTINUE instead of break and continue
  93  *      // you must not alter contents of the hash table here
  94  *    }
  95  *  HASH_END_FOR;
  96  *
  97  *  Then include <lib/hashtable.h> and voila, you have a hash table
  98  *  suiting all your needs (at least those which you've revealed :) ).
  99  *
 100  *  After including this file, all parameter macros are automatically
 101  *  undef'd.
 102  */
 103
 104 #ifndef _SHERLOCK_HASHFUNC_H
 105 #include "lib/hashfunc.h"
 106 #endif
 107
 108 #include <string.h>
 109
 110 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
 111 #error Some of the mandatory configuration macros are missing.
 112 #endif
 113
 114 #define P(x) HASH_PREFIX(x)
 115
 116 /* Declare buckets and the hash table */
 117
 118 typedef HASH_NODE P(node);
 119
 120 typedef struct P(bucket) {
 121   struct P(bucket) *next;
 122 #ifndef HASH_CONSERVE_SPACE
 123   uns hash;
 124 #endif
 125   P(node) n;
 126 } P(bucket);
 127
 128 struct P(table) {
 129   uns hash_size;
 130   uns hash_count, hash_max, hash_min, hash_hard_max;
 131   P(bucket) **ht;
 132 } P(table);
 133
 134 #define T P(table)
 135
 136 /* Preset parameters */
 137
 138 #if defined(HASH_KEY_ATOMIC)
 139
 140 #define HASH_KEY(x) x HASH_KEY_ATOMIC
 141
 142 #ifndef HASH_ATOMIC_TYPE
 143 #  define HASH_ATOMIC_TYPE int
 144 #endif
 145 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
 146
 147 #ifndef HASH_GIVE_HASHFN
 148 #  define HASH_GIVE_HASHFN
 149    static inline int P(hash) (HASH_ATOMIC_TYPE x)
 150    { return hash_int(x); }
 151 #endif
 152
 153 #ifndef HASH_GIVE_EQ
 154 #  define HASH_GIVE_EQ
 155    static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
 156    { return x == y; }
 157 #endif
 158
 159 #ifndef HASH_GIVE_INIT_KEY
 160 #  define HASH_GIVE_INIT_KEY
 161    static inline void P(init_key) (P(node) *n, HASH_ATOMIC_TYPE k)
 162    { HASH_KEY(n->) = k; }
 163 #endif
 164
 165 #ifndef HASH_CONSERVE_SPACE
 166 #define HASH_CONSERVE_SPACE
 167 #endif
 168
 169 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 170
 171 #ifdef HASH_KEY_STRING
 172 #  define HASH_KEY(x) x HASH_KEY_STRING
 173 #  ifndef HASH_GIVE_INIT_KEY
 174 #    define HASH_GIVE_INIT_KEY
 175      static inline void P(init_key) (P(node) *n, char *k)
 176      { HASH_KEY(n->) = k; }
 177 #  endif
 178 #else
 179 #  define HASH_KEY(x) x HASH_KEY_ENDSTRING
 180 #  define HASH_GIVE_EXTRA_SIZE
 181    static inline int P(extra_size) (char *k)
 182    { return strlen(k); }
 183 #  ifndef HASH_GIVE_INIT_KEY
 184 #    define HASH_GIVE_INIT_KEY
 185      static inline void P(init_key) (P(node) *n, char *k)
 186      { strcpy(HASH_KEY(n->), k); }
 187 #  endif
 188 #endif
 189 #define HASH_KEY_DECL char *HASH_KEY( )
 190
 191 #ifndef HASH_GIVE_HASHFN
 192 #define HASH_GIVE_HASHFN
 193   static inline uns P(hash) (char *k)
 194    {
 195 #    ifdef HASH_NOCASE
 196        return hash_string_nocase(k);
 197 #    else
 198        return hash_string(k);
 199 #    endif
 200    }
 201 #endif
 202
 203 #ifndef HASH_GIVE_EQ
 204 #  define HASH_GIVE_EQ
 205    static inline int P(eq) (char *x, char *y)
 206    {
 207 #    ifdef HASH_NOCASE
 208        return !strcasecmp(x,y);
 209 #    else
 210        return !strcmp(x,y);
 211 #    endif
 212    }
 213 #endif
 214
 215 #elif defined(HASH_KEY_COMPLEX)
 216
 217 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
 218
 219 #else
 220 #error You forgot to set the hash key type.
 221 #endif
 222
 223 /* Defaults for missing parameters */
 224
 225 #ifndef HASH_GIVE_HASHFN
 226 #error Unable to determine which hash function to use.
 227 #endif
 228
 229 #ifndef HASH_GIVE_EQ
 230 #error Unable to determine how to compare two keys.
 231 #endif
 232
 233 #ifdef HASH_GIVE_EXTRA_SIZE
 234 /* This trickery is needed to avoid `unused parameter' warnings */
 235 #define HASH_EXTRA_SIZE P(extra_size)
 236 #else
 237 /*
 238  *  Beware, C macros are expanded iteratively, not recursively,
 239  *  hence we get only a _single_ argument, although the expansion
 240  *  of HASH_KEY contains commas.
 241  */
 242 #define HASH_EXTRA_SIZE(x) 0
 243 #endif
 244
 245 #ifndef HASH_GIVE_INIT_KEY
 246 #error Unable to determine how to initialize keys.
 247 #endif
 248
 249 #ifndef HASH_GIVE_INIT_DATA
 250 static inline void P(init_data) (P(node) *n UNUSED)
 251 {
 252 }
 253 #endif
 254
 255 #include <stdlib.h>
 256
 257 #ifndef HASH_GIVE_ALLOC
 258 #ifdef HASH_USE_POOL
 259
 260 static inline void * P(alloc) (unsigned int size)
 261 { return mp_alloc_fast(HASH_USE_POOL, size); }
 262
 263 #else
 264
 265 static inline void * P(alloc) (unsigned int size)
 266 { return xmalloc(size); }
 267
 268 static inline void P(free) (void *x)
 269 { xfree(x); }
 270
 271 #endif
 272 #endif
 273
 274 #ifndef HASH_DEFAULT_SIZE
 275 #define HASH_DEFAULT_SIZE 32
 276 #endif
 277
 278 #ifndef HASH_FN_BITS
 279 #define HASH_FN_BITS 32
 280 #endif
 281
 282 /* Now the operations */
 283
 284 static void P(alloc_table) (void)
 285 {
 286   T.hash_size = nextprime(T.hash_size);
 287   T.ht = xmalloc(sizeof(void *) * T.hash_size);
 288   bzero(T.ht, sizeof(void *) * T.hash_size);
 289   if (2*T.hash_size < T.hash_hard_max)
 290     T.hash_max = 2*T.hash_size;
 291   else
 292     T.hash_max = ~0U;
 293   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
 294     T.hash_min = T.hash_size/4;
 295   else
 296     T.hash_min = 0;
 297 }
 298
 299 static void P(init) (void)
 300 {
 301   T.hash_count = 0;
 302   T.hash_size = HASH_DEFAULT_SIZE;
 303 #if HASH_FN_BITS < 28
 304   T.hash_hard_max = 1 << HASH_FN_BITS;
 305 #else
 306   T.hash_hard_max = 1 << 28;
 307 #endif
 308   P(alloc_table)();
 309 }
 310
 311 #ifdef HASH_WANT_CLEANUP
 312 static void P(cleanup) (void)
 313 {
 314 #ifndef HASH_USE_POOL
 315   uns i;
 316   P(bucket) *b, *bb;
 317
 318   for (i=0; i<T.hash_size; i++)
 319     for (b=T.ht[i]; b; b=bb)
 320       {
 321         bb = b->next;
 322         P(free)(b);
 323       }
 324 #endif
 325   xfree(T.ht);
 326 }
 327 #endif
 328
 329 static inline uns P(bucket_hash) (P(bucket) *b)
 330 {
 331 #ifdef HASH_CONSERVE_SPACE
 332   return P(hash)(HASH_KEY(b->n.));
 333 #else
 334   return b->hash;
 335 #endif
 336 }
 337
 338 static void P(rehash) (uns size)
 339 {
 340   P(bucket) *b, *nb;
 341   P(bucket) **oldt = T.ht, **newt;
 342   uns oldsize = T.hash_size;
 343   uns i, h;
 344
 345   // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
 346   T.hash_size = size;
 347   P(alloc_table)();
 348   newt = T.ht;
 349   for (i=0; i<oldsize; i++)
 350     {
 351       b = oldt[i];
 352       while (b)
 353         {
 354           nb = b->next;
 355           h = P(bucket_hash)(b) % T.hash_size;
 356           b->next = newt[h];
 357           newt[h] = b;
 358           b = nb;
 359         }
 360     }
 361   xfree(oldt);
 362 }
 363
 364 #ifdef HASH_WANT_FIND
 365 static P(node) * P(find) (HASH_KEY_DECL)
 366 {
 367   uns h0 = P(hash) (HASH_KEY( ));
 368   uns h = h0 % T.hash_size;
 369   P(bucket) *b;
 370
 371   for (b=T.ht[h]; b; b=b->next)
 372     {
 373       if (
 374 #ifndef HASH_CONSERVE_SPACE
 375           b->hash == h0 &&
 376 #endif
 377           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 378         return &b->n;
 379     }
 380   return NULL;
 381 }
 382 #endif
 383
 384 #ifdef HASH_WANT_NEW
 385 static P(node) * P(new) (HASH_KEY_DECL)
 386 {
 387   uns h0, h;
 388   P(bucket) *b;
 389
 390   h0 = P(hash) (HASH_KEY( ));
 391   h = h0 % T.hash_size;
 392   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 393   b->next = T.ht[h];
 394   T.ht[h] = b;
 395 #ifndef HASH_CONSERVE_SPACE
 396   b->hash = h0;
 397 #endif
 398   P(init_key)(&b->n, HASH_KEY( ));
 399   P(init_data)(&b->n);
 400   if (T.hash_count++ >= T.hash_max)
 401     P(rehash)(2*T.hash_size);
 402   return &b->n;
 403 }
 404 #endif
 405
 406 #ifdef HASH_WANT_LOOKUP
 407 static P(node) * P(lookup) (HASH_KEY_DECL)
 408 {
 409   uns h0 = P(hash) (HASH_KEY( ));
 410   uns h = h0 % T.hash_size;
 411   P(bucket) *b;
 412
 413   for (b=T.ht[h]; b; b=b->next)
 414     {
 415       if (
 416 #ifndef HASH_CONSERVE_SPACE
 417           b->hash == h0 &&
 418 #endif
 419           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 420         return &b->n;
 421     }
 422
 423   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 424   b->next = T.ht[h];
 425   T.ht[h] = b;
 426 #ifndef HASH_CONSERVE_SPACE
 427   b->hash = h0;
 428 #endif
 429   P(init_key)(&b->n, HASH_KEY( ));
 430   P(init_data)(&b->n);
 431   if (T.hash_count++ >= T.hash_max)
 432     P(rehash)(2*T.hash_size);
 433   return &b->n;
 434 }
 435 #endif
 436
 437 #ifdef HASH_WANT_DELETE
 438 static int P(delete) (HASH_KEY_DECL)
 439 {
 440   uns h0 = P(hash) (HASH_KEY( ));
 441   uns h = h0 % T.hash_size;
 442   P(bucket) *b, **bb;
 443
 444   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
 445     {
 446       if (
 447 #ifndef HASH_CONSERVE_SPACE
 448           b->hash == h0 &&
 449 #endif
 450           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 451         {
 452           *bb = b->next;
 453           P(free)(b);
 454           if (--T.hash_count < T.hash_min)
 455             P(rehash)(T.hash_size/2);
 456           return 1;
 457         }
 458     }
 459   return 0;
 460 }
 461 #endif
 462
 463 #ifdef HASH_WANT_REMOVE
 464 static void P(remove) (P(node) *n)
 465 {
 466   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
 467   uns h0 = P(bucket_hash)(x);
 468   uns h = h0 % T.hash_size;
 469   P(bucket) *b, **bb;
 470
 471   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
 472     ;
 473   ASSERT(b);
 474   *bb = b->next;
 475   P(free)(b);
 476   if (--T.hash_count < T.hash_min)
 477     P(rehash)(T.hash_size/2);
 478 }
 479 #endif
 480
 481 /* And the iterator */
 482
 483 #ifndef HASH_FOR_ALL
 484
 485 #define HASH_FOR_ALL(h_px, h_var)                                                       \
 486 do {                                                                                    \
 487   uns h_slot;                                                                           \
 488   struct HASH_GLUE(h_px,bucket) *h_buck;                                                \
 489   for (h_slot=0; h_slot < HASH_GLUE(h_px,table).hash_size; h_slot++)                    \
 490     for (h_buck = HASH_GLUE(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next)      \
 491       {                                                                                 \
 492         HASH_GLUE(h_px,node) *h_var = &h_buck->n;
 493 #define HASH_END_FOR } } while(0)
 494 #define HASH_BREAK
 495 #define HASH_CONTINUE continue
 496 #define HASH_GLUE(x,y) x##_##y
 497
 498 #endif
 499
 500 /* Finally, undefine all the parameters */
 501
 502 #undef P
 503 #undef T
 504
 505 #undef HASH_ATOMIC_TYPE
 506 #undef HASH_CONSERVE_SPACE
 507 #undef HASH_DEFAULT_SIZE
 508 #undef HASH_EXTRA_SIZE
 509 #undef HASH_FN_BITS
 510 #undef HASH_GIVE_ALLOC
 511 #undef HASH_GIVE_EQ
 512 #undef HASH_GIVE_EXTRA_SIZE
 513 #undef HASH_GIVE_HASHFN
 514 #undef HASH_GIVE_INIT_DATA
 515 #undef HASH_GIVE_INIT_KEY
 516 #undef HASH_KEY
 517 #undef HASH_KEY_ATOMIC
 518 #undef HASH_KEY_COMPLEX
 519 #undef HASH_KEY_DECL
 520 #undef HASH_KEY_ENDSTRING
 521 #undef HASH_KEY_STRING
 522 #undef HASH_NOCASE
 523 #undef HASH_NODE
 524 #undef HASH_PREFIX
 525 #undef HASH_USE_POOL
 526 #undef HASH_WANT_CLEANUP
 527 #undef HASH_WANT_DELETE
 528 #undef HASH_WANT_FIND
 529 #undef HASH_WANT_LOOKUP
 530 #undef HASH_WANT_NEW
 531 #undef HASH_WANT_REMOVE