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 `n' entries.
  80  *                      The `n' has to be a power of two.
  81  *  HASH_CONSERVE_SPACE use as little space as possible.
  82  *  HASH_FN_BITS=n      The hash function gives only `n' significant bits.
  83  *  HASH_ATOMIC_TYPE=t  Atomic values are of type `t' instead of int.
  84  *  HASH_USE_POOL=pool  Allocate all nodes from given mempool.
  85  *                      Collides with delete/remove functions.
  86  *
  87  *  You also get a iterator macro at no extra charge:
  88  *
  89  *  HASH_FOR_ALL(hash_prefix, variable)
  90  *    {
  91  *      // node *variable gets declared automatically
  92  *      do_something_with_node(variable);
  93  *      // use HASH_BREAK and HASH_CONTINUE instead of break and continue
  94  *      // you must not alter contents of the hash table here
  95  *    }
  96  *  HASH_END_FOR;
  97  *
  98  *  Then include <lib/hashtable.h> and voila, you have a hash table
  99  *  suiting all your needs (at least those which you've revealed :) ).
 100  *
 101  *  After including this file, all parameter macros are automatically
 102  *  undef'd.
 103  */
 104
 105 #ifndef _SHERLOCK_HASHFUNC_H
 106 #include "lib/hashfunc.h"
 107 #endif
 108
 109 #include <string.h>
 110
 111 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
 112 #error Some of the mandatory configuration macros are missing.
 113 #endif
 114
 115 #define P(x) HASH_PREFIX(x)
 116
 117 /* Declare buckets and the hash table */
 118
 119 typedef HASH_NODE P(node);
 120
 121 typedef struct P(bucket) {
 122   struct P(bucket) *next;
 123 #ifndef HASH_CONSERVE_SPACE
 124   uns hash;
 125 #endif
 126   P(node) n;
 127 } P(bucket);
 128
 129 struct P(table) {
 130   uns hash_size;
 131   uns hash_count, hash_max, hash_min, hash_hard_max, hash_mask;
 132   P(bucket) **ht;
 133 } P(table);
 134
 135 #define T P(table)
 136
 137 /* Preset parameters */
 138
 139 #if defined(HASH_KEY_ATOMIC)
 140
 141 #define HASH_KEY(x) x HASH_KEY_ATOMIC
 142
 143 #ifndef HASH_ATOMIC_TYPE
 144 #  define HASH_ATOMIC_TYPE int
 145 #endif
 146 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
 147
 148 #ifndef HASH_GIVE_HASHFN
 149 #  define HASH_GIVE_HASHFN
 150    static inline int P(hash) (HASH_ATOMIC_TYPE x)
 151    { return hash_int(x); }
 152 #endif
 153
 154 #ifndef HASH_GIVE_EQ
 155 #  define HASH_GIVE_EQ
 156    static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
 157    { return x == y; }
 158 #endif
 159
 160 #ifndef HASH_GIVE_INIT_KEY
 161 #  define HASH_GIVE_INIT_KEY
 162    static inline void P(init_key) (P(node) *n, HASH_ATOMIC_TYPE k)
 163    { HASH_KEY(n->) = k; }
 164 #endif
 165
 166 #ifndef HASH_CONSERVE_SPACE
 167 #define HASH_CONSERVE_SPACE
 168 #endif
 169
 170 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 171
 172 #ifdef HASH_KEY_STRING
 173 #  define HASH_KEY(x) x HASH_KEY_STRING
 174 #  ifndef HASH_GIVE_INIT_KEY
 175 #    define HASH_GIVE_INIT_KEY
 176      static inline void P(init_key) (P(node) *n, char *k)
 177      { HASH_KEY(n->) = k; }
 178 #  endif
 179 #else
 180 #  define HASH_KEY(x) x HASH_KEY_ENDSTRING
 181 #  define HASH_GIVE_EXTRA_SIZE
 182    static inline int P(extra_size) (char *k)
 183    { return strlen(k); }
 184 #  ifndef HASH_GIVE_INIT_KEY
 185 #    define HASH_GIVE_INIT_KEY
 186      static inline void P(init_key) (P(node) *n, char *k)
 187      { strcpy(HASH_KEY(n->), k); }
 188 #  endif
 189 #endif
 190 #define HASH_KEY_DECL char *HASH_KEY( )
 191
 192 #ifndef HASH_GIVE_HASHFN
 193 #define HASH_GIVE_HASHFN
 194   static inline uns P(hash) (char *k)
 195    {
 196 #    ifdef HASH_NOCASE
 197        return hash_string_nocase(k);
 198 #    else
 199        return hash_string(k);
 200 #    endif
 201    }
 202 #endif
 203
 204 #ifndef HASH_GIVE_EQ
 205 #  define HASH_GIVE_EQ
 206    static inline int P(eq) (char *x, char *y)
 207    {
 208 #    ifdef HASH_NOCASE
 209        return !strcasecmp(x,y);
 210 #    else
 211        return !strcmp(x,y);
 212 #    endif
 213    }
 214 #endif
 215
 216 #elif defined(HASH_KEY_COMPLEX)
 217
 218 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
 219
 220 #else
 221 #error You forgot to set the hash key type.
 222 #endif
 223
 224 /* Defaults for missing parameters */
 225
 226 #ifndef HASH_GIVE_HASHFN
 227 #error Unable to determine which hash function to use.
 228 #endif
 229
 230 #ifndef HASH_GIVE_EQ
 231 #error Unable to determine how to compare two keys.
 232 #endif
 233
 234 #ifdef HASH_GIVE_EXTRA_SIZE
 235 /* This trickery is needed to avoid `unused parameter' warnings */
 236 #define HASH_EXTRA_SIZE P(extra_size)
 237 #else
 238 /*
 239  *  Beware, C macros are expanded iteratively, not recursively,
 240  *  hence we get only a _single_ argument, although the expansion
 241  *  of HASH_KEY contains commas.
 242  */
 243 #define HASH_EXTRA_SIZE(x) 0
 244 #endif
 245
 246 #ifndef HASH_GIVE_INIT_KEY
 247 #error Unable to determine how to initialize keys.
 248 #endif
 249
 250 #ifndef HASH_GIVE_INIT_DATA
 251 static inline void P(init_data) (P(node) *n UNUSED)
 252 {
 253 }
 254 #endif
 255
 256 #include <stdlib.h>
 257
 258 #ifndef HASH_GIVE_ALLOC
 259 #ifdef HASH_USE_POOL
 260
 261 static inline void * P(alloc) (unsigned int size)
 262 { return mp_alloc_fast(HASH_USE_POOL, size); }
 263
 264 #else
 265
 266 static inline void * P(alloc) (unsigned int size)
 267 { return xmalloc(size); }
 268
 269 static inline void P(free) (void *x)
 270 { xfree(x); }
 271
 272 #endif
 273 #endif
 274
 275 #ifndef HASH_DEFAULT_SIZE
 276 #define HASH_DEFAULT_SIZE 32
 277 #endif
 278
 279 #ifndef HASH_FN_BITS
 280 #define HASH_FN_BITS 32
 281 #endif
 282
 283 /* Now the operations */
 284
 285 static void P(alloc_table) (void)
 286 {
 287   T.ht = xmalloc(sizeof(void *) * T.hash_size);
 288   bzero(T.ht, sizeof(void *) * T.hash_size);
 289   T.hash_max = T.hash_size * 2;
 290   if (T.hash_max > T.hash_hard_max)
 291     T.hash_max = T.hash_hard_max;
 292   T.hash_min = T.hash_size / 4;
 293   T.hash_mask = T.hash_size - 1;
 294 }
 295
 296 static void P(init) (void)
 297 {
 298   T.hash_count = 0;
 299   T.hash_size = HASH_DEFAULT_SIZE;
 300 #if HASH_FN_BITS < 28
 301   T.hash_hard_max = 1 << HASH_FN_BITS;
 302 #else
 303   T.hash_hard_max = 1 << 28;
 304 #endif
 305   P(alloc_table)();
 306 }
 307
 308 #ifdef HASH_WANT_CLEANUP
 309 static void P(cleanup) (void)
 310 {
 311 #ifndef HASH_USE_POOL
 312   uns i;
 313   P(bucket) *b, *bb;
 314
 315   for (i=0; i<T.hash_size; i++)
 316     for (b=T.ht[i]; b; b=bb)
 317       {
 318         bb = b->next;
 319         P(free)(b);
 320       }
 321 #endif
 322   xfree(T.ht);
 323 }
 324 #endif
 325
 326 static inline uns P(bucket_hash) (P(bucket) *b)
 327 {
 328 #ifdef HASH_CONSERVE_SPACE
 329   return P(hash)(HASH_KEY(b->n.));
 330 #else
 331   return b->hash;
 332 #endif
 333 }
 334
 335 static void P(rehash) (uns size)
 336 {
 337   P(bucket) *b, *nb;
 338   P(bucket) **oldt = T.ht, **newt;
 339   uns oldsize = T.hash_size;
 340   uns i, h;
 341
 342   // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
 343   T.hash_size = size;
 344   P(alloc_table)();
 345   newt = T.ht;
 346   for (i=0; i<oldsize; i++)
 347     {
 348       b = oldt[i];
 349       while (b)
 350         {
 351           nb = b->next;
 352           h = P(bucket_hash)(b) & T.hash_mask;
 353           b->next = newt[h];
 354           newt[h] = b;
 355           b = nb;
 356         }
 357     }
 358   xfree(oldt);
 359 }
 360
 361 #ifdef HASH_WANT_FIND
 362 static P(node) * P(find) (HASH_KEY_DECL)
 363 {
 364   uns h0 = P(hash) (HASH_KEY( ));
 365   uns h = h0 & T.hash_mask;
 366   P(bucket) *b;
 367
 368   for (b=T.ht[h]; b; b=b->next)
 369     {
 370       if (
 371 #ifndef HASH_CONSERVE_SPACE
 372           b->hash == h0 &&
 373 #endif
 374           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 375         return &b->n;
 376     }
 377   return NULL;
 378 }
 379 #endif
 380
 381 #ifdef HASH_WANT_NEW
 382 static P(node) * P(new) (HASH_KEY_DECL)
 383 {
 384   uns h0, h;
 385   P(bucket) *b;
 386
 387   h0 = P(hash) (HASH_KEY( ));
 388   h = h0 & T.hash_mask;
 389   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 390   b->next = T.ht[h];
 391   T.ht[h] = b;
 392 #ifndef HASH_CONSERVE_SPACE
 393   b->hash = h0;
 394 #endif
 395   P(init_key)(&b->n, HASH_KEY( ));
 396   P(init_data)(&b->n);
 397   if (T.hash_count++ >= T.hash_max)
 398     P(rehash)(2*T.hash_size);
 399   return &b->n;
 400 }
 401 #endif
 402
 403 #ifdef HASH_WANT_LOOKUP
 404 static P(node) * P(lookup) (HASH_KEY_DECL)
 405 {
 406   uns h0 = P(hash) (HASH_KEY( ));
 407   uns h = h0 & T.hash_mask;
 408   P(bucket) *b;
 409
 410   for (b=T.ht[h]; b; b=b->next)
 411     {
 412       if (
 413 #ifndef HASH_CONSERVE_SPACE
 414           b->hash == h0 &&
 415 #endif
 416           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 417         return &b->n;
 418     }
 419
 420   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 421   b->next = T.ht[h];
 422   T.ht[h] = b;
 423 #ifndef HASH_CONSERVE_SPACE
 424   b->hash = h0;
 425 #endif
 426   P(init_key)(&b->n, HASH_KEY( ));
 427   P(init_data)(&b->n);
 428   if (T.hash_count++ >= T.hash_max)
 429     P(rehash)(2*T.hash_size);
 430   return &b->n;
 431 }
 432 #endif
 433
 434 #ifdef HASH_WANT_DELETE
 435 static int P(delete) (HASH_KEY_DECL)
 436 {
 437   uns h0 = P(hash) (HASH_KEY( ));
 438   uns h = h0 & T.hash_mask;
 439   P(bucket) *b, **bb;
 440
 441   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
 442     {
 443       if (
 444 #ifndef HASH_CONSERVE_SPACE
 445           b->hash == h0 &&
 446 #endif
 447           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 448         {
 449           *bb = b->next;
 450           P(free)(b);
 451           if (--T.hash_count < T.hash_min)
 452             P(rehash)(T.hash_size/2);
 453           return 1;
 454         }
 455     }
 456   return 0;
 457 }
 458 #endif
 459
 460 #ifdef HASH_WANT_REMOVE
 461 static void P(remove) (P(node) *n)
 462 {
 463   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
 464   uns h0 = P(bucket_hash)(x);
 465   uns h = h0 & T.hash_mask;
 466   P(bucket) *b, **bb;
 467
 468   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
 469     ;
 470   ASSERT(b);
 471   *bb = b->next;
 472   P(free)(b);
 473   if (--T.hash_count < T.hash_min)
 474     P(rehash)(T.hash_size/2);
 475 }
 476 #endif
 477
 478 /* And the iterator */
 479
 480 #ifndef HASH_FOR_ALL
 481
 482 #define HASH_FOR_ALL(h_px, h_var)                                                       \
 483 do {                                                                                    \
 484   uns h_slot;                                                                           \
 485   struct HASH_GLUE(h_px,bucket) *h_buck;                                                \
 486   for (h_slot=0; h_slot < HASH_GLUE(h_px,table).hash_size; h_slot++)                    \
 487     for (h_buck = HASH_GLUE(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next)      \
 488       {                                                                                 \
 489         HASH_GLUE(h_px,node) *h_var = &h_buck->n;
 490 #define HASH_END_FOR } } while(0)
 491 #define HASH_BREAK
 492 #define HASH_CONTINUE continue
 493 #define HASH_GLUE(x,y) x##_##y
 494
 495 #endif
 496
 497 /* Finally, undefine all the parameters */
 498
 499 #undef P
 500 #undef T
 501
 502 #undef HASH_ATOMIC_TYPE
 503 #undef HASH_CONSERVE_SPACE
 504 #undef HASH_DEFAULT_SIZE
 505 #undef HASH_EXTRA_SIZE
 506 #undef HASH_FN_BITS
 507 #undef HASH_GIVE_ALLOC
 508 #undef HASH_GIVE_EQ
 509 #undef HASH_GIVE_EXTRA_SIZE
 510 #undef HASH_GIVE_HASHFN
 511 #undef HASH_GIVE_INIT_DATA
 512 #undef HASH_GIVE_INIT_KEY
 513 #undef HASH_KEY
 514 #undef HASH_KEY_ATOMIC
 515 #undef HASH_KEY_COMPLEX
 516 #undef HASH_KEY_DECL
 517 #undef HASH_KEY_ENDSTRING
 518 #undef HASH_KEY_STRING
 519 #undef HASH_NOCASE
 520 #undef HASH_NODE
 521 #undef HASH_PREFIX
 522 #undef HASH_USE_POOL
 523 #undef HASH_WANT_CLEANUP
 524 #undef HASH_WANT_DELETE
 525 #undef HASH_WANT_FIND
 526 #undef HASH_WANT_LOOKUP
 527 #undef HASH_WANT_NEW
 528 #undef HASH_WANT_REMOVE