lib/hashtable.h

   1 /*
   2  *      Sherlock Library -- Universal Hash Table
   3  *
   4  *      (c) 2002 Martin Mares <mj@ucw.cz>
   5  *      (c) 2002 Robert Spalek <robert@ucw.cz>
   6  */
   7
   8 /*
   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
  12  *  given.
  13  *
  14  *  You need to specify:
  15  *
  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).
  19  *
  20  *  Then decide on type of keys:
  21  *
  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
  38  *                      are mandatory.
  39  *
  40  *  Then specify what operations you request (all names are automatically
  41  *  prefixed by calling HASH_PREFIX):
  42  *
  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.
  57  *
  58  *  You can also supply several functions:
  59  *
  60  *  HASH_GIVE_HASHFN    unsigned int hash(key) -- calculate hash value of key.
  61  *                      We have sensible default hash functions for strings
  62  *                      and integers.
  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.
  78  *
  79  *  ... and a couple of extra parameters:
  80  *
  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.
  88  *
  89  *  You also get a iterator macro at no extra charge:
  90  *
  91  *  HASH_FOR_ALL(hash_prefix, variable)
  92  *    {
  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
  97  *    }
  98  *  HASH_END_FOR;
  99  *
 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 :) ).
 102  *
 103  *  After including this file, all parameter macros are automatically
 104  *  undef'd.
 105  */
 106
 107 #ifndef _SHERLOCK_HASHFUNC_H
 108 #include "lib/hashfunc.h"
 109 #endif
 110
 111 #include <string.h>
 112
 113 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
 114 #error Some of the mandatory configuration macros are missing.
 115 #endif
 116
 117 #define P(x) HASH_PREFIX(x)
 118
 119 /* Declare buckets and the hash table */
 120
 121 typedef HASH_NODE P(node);
 122
 123 typedef struct P(bucket) {
 124   struct P(bucket) *next;
 125 #ifndef HASH_CONSERVE_SPACE
 126   uns hash;
 127 #endif
 128   P(node) n;
 129 } P(bucket);
 130
 131 struct P(table) {
 132   uns hash_size;
 133   uns hash_count, hash_max, hash_min, hash_hard_max;
 134   P(bucket) **ht;
 135 } P(table);
 136
 137 #define T P(table)
 138
 139 /* Preset parameters */
 140
 141 #if defined(HASH_KEY_ATOMIC)
 142
 143 #define HASH_KEY(x) x HASH_KEY_ATOMIC
 144
 145 #ifndef HASH_ATOMIC_TYPE
 146 #  define HASH_ATOMIC_TYPE int
 147 #endif
 148 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
 149
 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); }
 154 #endif
 155
 156 #ifndef HASH_GIVE_EQ
 157 #  define HASH_GIVE_EQ
 158    static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
 159    { return x == y; }
 160 #endif
 161
 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; }
 166 #endif
 167
 168 #ifndef HASH_CONSERVE_SPACE
 169 #define HASH_CONSERVE_SPACE
 170 #endif
 171
 172 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 173
 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; }
 180 #  endif
 181 #else
 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); }
 190 #  endif
 191 #endif
 192 #define HASH_KEY_DECL char *HASH_KEY( )
 193
 194 #ifndef HASH_GIVE_HASHFN
 195 #define HASH_GIVE_HASHFN
 196   static inline uns P(hash) (char *k)
 197    {
 198 #    ifdef HASH_NOCASE
 199        return hash_string_nocase(k);
 200 #    else
 201        return hash_string(k);
 202 #    endif
 203    }
 204 #endif
 205
 206 #ifndef HASH_GIVE_EQ
 207 #  define HASH_GIVE_EQ
 208    static inline int P(eq) (char *x, char *y)
 209    {
 210 #    ifdef HASH_NOCASE
 211        return !strcasecmp(x,y);
 212 #    else
 213        return !strcmp(x,y);
 214 #    endif
 215    }
 216 #endif
 217
 218 #elif defined(HASH_KEY_COMPLEX)
 219
 220 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
 221
 222 #else
 223 #error You forgot to set the hash key type.
 224 #endif
 225
 226 /* Defaults for missing parameters */
 227
 228 #ifndef HASH_GIVE_HASHFN
 229 #error Unable to determine which hash function to use.
 230 #endif
 231
 232 #ifndef HASH_GIVE_EQ
 233 #error Unable to determine how to compare two keys.
 234 #endif
 235
 236 #ifdef HASH_GIVE_EXTRA_SIZE
 237 /* This trickery is needed to avoid `unused parameter' warnings */
 238 #define HASH_EXTRA_SIZE P(extra_size)
 239 #else
 240 /*
 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.
 244  */
 245 #define HASH_EXTRA_SIZE(x) 0
 246 #endif
 247
 248 #ifndef HASH_GIVE_INIT_KEY
 249 #error Unable to determine how to initialize keys.
 250 #endif
 251
 252 #ifndef HASH_GIVE_INIT_DATA
 253 static inline void P(init_data) (P(node) *n UNUSED)
 254 {
 255 }
 256 #endif
 257
 258 #include <stdlib.h>
 259
 260 #ifndef HASH_GIVE_ALLOC
 261 #ifdef HASH_USE_POOL
 262
 263 static inline void * P(alloc) (unsigned int size)
 264 { return mp_alloc_fast(HASH_USE_POOL, size); }
 265
 266 #else
 267
 268 static inline void * P(alloc) (unsigned int size)
 269 { return xmalloc(size); }
 270
 271 static inline void P(free) (void *x)
 272 { xfree(x); }
 273
 274 #endif
 275 #endif
 276
 277 #ifndef HASH_DEFAULT_SIZE
 278 #define HASH_DEFAULT_SIZE 32
 279 #endif
 280
 281 #ifndef HASH_FN_BITS
 282 #define HASH_FN_BITS 32
 283 #endif
 284
 285 /* Now the operations */
 286
 287 static void P(alloc_table) (void)
 288 {
 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;
 294   else
 295     T.hash_max = ~0U;
 296   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
 297     T.hash_min = T.hash_size/4;
 298   else
 299     T.hash_min = 0;
 300 }
 301
 302 static void P(init) (void)
 303 {
 304   T.hash_count = 0;
 305   T.hash_size = HASH_DEFAULT_SIZE;
 306 #if HASH_FN_BITS < 28
 307   T.hash_hard_max = 1 << HASH_FN_BITS;
 308 #else
 309   T.hash_hard_max = 1 << 28;
 310 #endif
 311   P(alloc_table)();
 312 }
 313
 314 #ifdef HASH_WANT_CLEANUP
 315 static void P(cleanup) (void)
 316 {
 317 #ifndef HASH_USE_POOL
 318   uns i;
 319   P(bucket) *b, *bb;
 320
 321   for (i=0; i<T.hash_size; i++)
 322     for (b=T.ht[i]; b; b=bb)
 323       {
 324         bb = b->next;
 325         P(free)(b);
 326       }
 327 #endif
 328   xfree(T.ht);
 329 }
 330 #endif
 331
 332 static inline uns P(bucket_hash) (P(bucket) *b)
 333 {
 334 #ifdef HASH_CONSERVE_SPACE
 335   return P(hash)(HASH_KEY(b->n.));
 336 #else
 337   return b->hash;
 338 #endif
 339 }
 340
 341 static void P(rehash) (uns size)
 342 {
 343   P(bucket) *b, *nb;
 344   P(bucket) **oldt = T.ht, **newt;
 345   uns oldsize = T.hash_size;
 346   uns i, h;
 347
 348   // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
 349   T.hash_size = size;
 350   P(alloc_table)();
 351   newt = T.ht;
 352   for (i=0; i<oldsize; i++)
 353     {
 354       b = oldt[i];
 355       while (b)
 356         {
 357           nb = b->next;
 358           h = P(bucket_hash)(b) % T.hash_size;
 359           b->next = newt[h];
 360           newt[h] = b;
 361           b = nb;
 362         }
 363     }
 364   xfree(oldt);
 365 }
 366
 367 #ifdef HASH_WANT_FIND
 368 static P(node) * P(find) (HASH_KEY_DECL)
 369 {
 370   uns h0 = P(hash) (HASH_KEY( ));
 371   uns h = h0 % T.hash_size;
 372   P(bucket) *b;
 373
 374   for (b=T.ht[h]; b; b=b->next)
 375     {
 376       if (
 377 #ifndef HASH_CONSERVE_SPACE
 378           b->hash == h0 &&
 379 #endif
 380           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 381         return &b->n;
 382     }
 383   return NULL;
 384 }
 385 #endif
 386
 387 #ifdef HASH_WANT_FIND_NEXT
 388 static P(node) * P(find_next) (HASH_KEY_DECL, P(node) *start)
 389 {
 390 #ifndef HASH_CONSERVE_SPACE
 391   uns h0 = P(hash) (HASH_KEY( ));
 392 #endif
 393   P(bucket) *b = SKIP_BACK(P(bucket), n, start);
 394
 395   for (; b; b=b->next)
 396     {
 397       if (
 398 #ifndef HASH_CONSERVE_SPACE
 399           b->hash == h0 &&
 400 #endif
 401           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 402         return &b->n;
 403     }
 404   return NULL;
 405 }
 406 #endif
 407
 408 #ifdef HASH_WANT_NEW
 409 static P(node) * P(new) (HASH_KEY_DECL)
 410 {
 411   uns h0, h;
 412   P(bucket) *b;
 413
 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( )));
 417   b->next = T.ht[h];
 418   T.ht[h] = b;
 419 #ifndef HASH_CONSERVE_SPACE
 420   b->hash = h0;
 421 #endif
 422   P(init_key)(&b->n, HASH_KEY( ));
 423   P(init_data)(&b->n);
 424   if (T.hash_count++ >= T.hash_max)
 425     P(rehash)(2*T.hash_size);
 426   return &b->n;
 427 }
 428 #endif
 429
 430 #ifdef HASH_WANT_LOOKUP
 431 static P(node) * P(lookup) (HASH_KEY_DECL)
 432 {
 433   uns h0 = P(hash) (HASH_KEY( ));
 434   uns h = h0 % T.hash_size;
 435   P(bucket) *b;
 436
 437   for (b=T.ht[h]; b; b=b->next)
 438     {
 439       if (
 440 #ifndef HASH_CONSERVE_SPACE
 441           b->hash == h0 &&
 442 #endif
 443           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 444         return &b->n;
 445     }
 446
 447   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 448   b->next = T.ht[h];
 449   T.ht[h] = b;
 450 #ifndef HASH_CONSERVE_SPACE
 451   b->hash = h0;
 452 #endif
 453   P(init_key)(&b->n, HASH_KEY( ));
 454   P(init_data)(&b->n);
 455   if (T.hash_count++ >= T.hash_max)
 456     P(rehash)(2*T.hash_size);
 457   return &b->n;
 458 }
 459 #endif
 460
 461 #ifdef HASH_WANT_DELETE
 462 static int P(delete) (HASH_KEY_DECL)
 463 {
 464   uns h0 = P(hash) (HASH_KEY( ));
 465   uns h = h0 % T.hash_size;
 466   P(bucket) *b, **bb;
 467
 468   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
 469     {
 470       if (
 471 #ifndef HASH_CONSERVE_SPACE
 472           b->hash == h0 &&
 473 #endif
 474           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 475         {
 476           *bb = b->next;
 477           P(free)(b);
 478           if (--T.hash_count < T.hash_min)
 479             P(rehash)(T.hash_size/2);
 480           return 1;
 481         }
 482     }
 483   return 0;
 484 }
 485 #endif
 486
 487 #ifdef HASH_WANT_REMOVE
 488 static void P(remove) (P(node) *n)
 489 {
 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;
 493   P(bucket) *b, **bb;
 494
 495   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
 496     ;
 497   ASSERT(b);
 498   *bb = b->next;
 499   P(free)(b);
 500   if (--T.hash_count < T.hash_min)
 501     P(rehash)(T.hash_size/2);
 502 }
 503 #endif
 504
 505 /* And the iterator */
 506
 507 #ifndef HASH_FOR_ALL
 508
 509 #define HASH_FOR_ALL(h_px, h_var)                                                       \
 510 do {                                                                                    \
 511   uns h_slot;                                                                           \
 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)      \
 515       {                                                                                 \
 516         HASH_GLUE(h_px,node) *h_var = &h_buck->n;
 517 #define HASH_END_FOR } } while(0)
 518 #define HASH_BREAK
 519 #define HASH_CONTINUE continue
 520 #define HASH_GLUE(x,y) x##_##y
 521
 522 #endif
 523
 524 /* Finally, undefine all the parameters */
 525
 526 #undef P
 527 #undef T
 528
 529 #undef HASH_ATOMIC_TYPE
 530 #undef HASH_CONSERVE_SPACE
 531 #undef HASH_DEFAULT_SIZE
 532 #undef HASH_EXTRA_SIZE
 533 #undef HASH_FN_BITS
 534 #undef HASH_GIVE_ALLOC
 535 #undef HASH_GIVE_EQ
 536 #undef HASH_GIVE_EXTRA_SIZE
 537 #undef HASH_GIVE_HASHFN
 538 #undef HASH_GIVE_INIT_DATA
 539 #undef HASH_GIVE_INIT_KEY
 540 #undef HASH_KEY
 541 #undef HASH_KEY_ATOMIC
 542 #undef HASH_KEY_COMPLEX
 543 #undef HASH_KEY_DECL
 544 #undef HASH_KEY_ENDSTRING
 545 #undef HASH_KEY_STRING
 546 #undef HASH_NOCASE
 547 #undef HASH_NODE
 548 #undef HASH_PREFIX
 549 #undef HASH_USE_POOL
 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
 555 #undef HASH_WANT_NEW
 556 #undef HASH_WANT_REMOVE