ucw/hashtable.h

   1 /*
   2  *      UCW Library -- Universal Hash Table
   3  *
   4  *      (c) 2002--2004 Martin Mares <mj@ucw.cz>
   5  *      (c) 2002--2005 Robert Spalek <robert@ucw.cz>
   6  *      (c) 2010 Pavel Charvat <pchar@ucw.cz>
   7  *      (c) 2012 Tomas Valla <tom@ucw.cz>
   8  *
   9  *      This software may be freely distributed and used according to the terms
  10  *      of the GNU Lesser General Public License.
  11  */
  12
  13 /*
  14  *  This is not a normal header file, it's a generator of hash tables.
  15  *  Each time you include it with parameters set in the corresponding
  16  *  preprocessor macros, it generates a hash table with the parameters
  17  *  given.
  18  *
  19  *  You need to specify:
  20  *
  21  *  HASH_NODE           data type where a node dwells (usually a struct).
  22  *  HASH_PREFIX(x)      macro to add a name prefix (used on all global names
  23  *                      defined by the hash table generator).
  24  *
  25  *  Then decide on type of keys:
  26  *
  27  *  HASH_KEY_ATOMIC=f   use node->f as a key of an atomic type (i.e.,
  28  *                      a type which can be compared using `==')
  29  *                      HASH_ATOMIC_TYPE (defaults to int).
  30  *  | HASH_KEY_STRING=f use node->f as a string key, allocated
  31  *                      separately from the rest of the node.
  32  *  | HASH_KEY_ENDSTRING=f use node->f as a string key, allocated
  33  *                      automatically at the end of the node struct
  34  *                      (to be declared as "char f[1]" at the end).
  35  *  | HASH_KEY_COMPLEX  use a multi-component key; as the name suggests,
  36  *                      the passing of parameters is a bit complex then.
  37  *                      The HASH_KEY_COMPLEX(x) macro should expand to
  38  *                      `x k1, x k2, ... x kn' and you should also define:
  39  *    HASH_KEY_DECL     declaration of function parameters in which key
  40  *                      should be passed to all hash table operations.
  41  *                      That is, `type1 k1, type2 k2, ... typen kn'.
  42  *                      With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
  43  *                      are mandatory.
  44  *  | HASH_KEY_MEMORY=f use node->f as a raw data key, compared using
  45  *                      memcmp
  46  *    HASH_KEY_SIZE     the length of the key block
  47  *
  48  *  Then specify what operations you request (all names are automatically
  49  *  prefixed by calling HASH_PREFIX):
  50  *
  51  *  <always defined>    init() -- initialize the hash table.
  52  *  HASH_WANT_CLEANUP   cleanup() -- deallocate the hash table.
  53  *  HASH_WANT_FIND      node *find(key) -- find first node with the specified
  54  *                      key, return NULL if no such node exists.
  55  *  HASH_WANT_FIND_NEXT node *find(node *start) -- find next node with the
  56  *                      specified key, return NULL if no such node exists.
  57  *  HASH_WANT_NEW       node *new(key) -- create new node with given key.
  58  *                      Doesn't check whether it already exists.
  59  *  HASH_WANT_LOOKUP    node *lookup(key) -- find node with given key,
  60  *                      if it doesn't exist, create it. Defining
  61  *                      HASH_GIVE_INIT_DATA is strongly recommended.
  62  *                      Use HASH_LOOKUP_DETECT_NEW if you want to know
  63  *                      whether the node was newly created or not.
  64  *  HASH_WANT_DELETE    int delete(key) -- delete and deallocate node
  65  *                      with given key. Returns success.
  66  *  HASH_WANT_REMOVE    remove(node *) -- delete and deallocate given node.
  67  *
  68  *  You can also supply several functions:
  69  *
  70  *  HASH_GIVE_HASHFN    unsigned int hash(key) -- calculate hash value of key.
  71  *                      We have sensible default hash functions for strings
  72  *                      and integers.
  73  *  HASH_GIVE_EQ        int eq(key1, key2) -- return whether keys are equal.
  74  *                      By default, we use == for atomic types and either
  75  *                      strcmp or strcasecmp for strings.
  76  *  HASH_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
  77  *                      node should be allocated for dynamic data. Default=0
  78  *                      or length of the string with HASH_KEY_ENDSTRING.
  79  *  HASH_GIVE_INIT_KEY  void init_key(node *,key) -- initialize key in a newly
  80  *                      created node. Defaults: assignment for atomic keys
  81  *                      and static strings, strcpy for end-allocated strings.
  82  *  HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
  83  *                      newly created node. Very useful for lookup operations.
  84  *  HASH_GIVE_ALLOC     void *alloc(unsigned int size) -- allocate space for
  85  *                      a node. Default is xmalloc() or pooled allocation, depending
  86  *                      on HASH_USE_POOL, HASH_AUTO_POOL, HASH_USE_ELTPOOL
  87  *                      and HASH_AUTO_ELTPOOL switches. void free(void *) -- the converse.
  88  *  HASH_GIVE_TABLE_ALLOC void *table_alloc(unsigned int size), void *table_free(void *)
  89  *                      Allocate or free space for the table itself. Default is xmalloc()
  90  *                      or the functions defined by HASH_GIVE_ALLOC if HASH_TABLE_ALLOC is set.
  91  *
  92  *  ... and a couple of extra parameters:
  93  *
  94  *  HASH_NOCASE         String comparisons should be case-insensitive.
  95  *  HASH_DEFAULT_SIZE=n Initially, use hash table of approx. `n' entries.
  96  *  HASH_CONSERVE_SPACE Use as little space as possible.
  97  *  HASH_FN_BITS=n      The hash function gives only `n' significant bits.
  98  *  HASH_ATOMIC_TYPE=t  Atomic values are of type `t' instead of int.
  99  *  HASH_USE_POOL=pool  Allocate all nodes from given mempool. Note, however, that
 100  *                      deallocation is not supported by mempools, so delete/remove
 101  *                      will leak pool memory.
 102  *  HASH_AUTO_POOL=size Create a pool of the given block size automatically.
 103  *  HASH_USE_ELTPOOL=pool Allocate all nodes from given eltpool.
 104  *  HASH_AUTO_ELTPOOL=count Create an eltpool of the given number of elements in each chunk.
 105  *  HASH_ZERO_FILL      New entries should be initialized to all zeroes.
 106  *  HASH_TABLE_ALLOC    The hash table itself will be allocated and freed using
 107  *                      the same allocation functions as the nodes instead of
 108  *                      the default xmalloc().
 109  *  HASH_TABLE_GROWING  Never decrease the size of the hash table itself
 110  *  HASH_TABLE_DYNAMIC  Support multiple hash tables; the first parameter of all
 111  *                      hash table operations is struct HASH_PREFIX(table) *.
 112  *  HASH_TABLE_VARS     Extra variables to be defined in table structure
 113  *  HASH_LOOKUP_DETECT_NEW
 114  *                      the prototype for lookup is changed to node *lookup(key, int *new_item)
 115  *                      new_item must not be NULL and returns 1 whether lookup
 116  *                      just created a new item in the hashtable or 0 otherwise.
 117  *
 118  *  You also get a iterator macro at no extra charge:
 119  *
 120  *  HASH_FOR_ALL(hash_prefix, variable)
 121  *    {
 122  *      // node *variable gets declared automatically
 123  *      do_something_with_node(variable);
 124  *      // use HASH_BREAK and HASH_CONTINUE instead of break and continue
 125  *      // you must not alter contents of the hash table here
 126  *    }
 127  *  HASH_END_FOR;
 128  *
 129  *  (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
 130  *
 131  *  Then include <ucw/hashtable.h> and voila, you have a hash table
 132  *  suiting all your needs (at least those which you've revealed :) ).
 133  *
 134  *  After including this file, all parameter macros are automatically
 135  *  undef'd.
 136  */
 137
 138 #ifndef _UCW_HASHFUNC_H
 139 #include <ucw/hashfunc.h>
 140 #endif
 141
 142 #include <ucw/prime.h>
 143
 144 #include <string.h>
 145
 146 /* Initial setup of parameters */
 147
 148 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
 149 #error Some of the mandatory configuration macros are missing.
 150 #endif
 151
 152 #if defined(HASH_KEY_ATOMIC) && !defined(HASH_CONSERVE_SPACE)
 153 #define HASH_CONSERVE_SPACE
 154 #endif
 155
 156 #define P(x) HASH_PREFIX(x)
 157
 158 /* Declare buckets and the hash table */
 159
 160 typedef HASH_NODE P(node);
 161
 162 typedef struct P(bucket) {
 163   struct P(bucket) *next;
 164 #ifndef HASH_CONSERVE_SPACE
 165   uns hash;
 166 #endif
 167   P(node) n;
 168 } P(bucket);
 169
 170 struct P(table) {
 171 #ifdef HASH_TABLE_VARS
 172   HASH_TABLE_VARS
 173 #endif
 174   uns hash_size;
 175   uns hash_count, hash_max, hash_min, hash_hard_max;
 176   P(bucket) **ht;
 177 #ifdef HASH_AUTO_POOL
 178   struct mempool *pool;
 179 #endif
 180 #ifdef HASH_AUTO_ELTPOOL
 181   struct eltpool *eltpool;
 182 #endif
 183 };
 184
 185 #ifdef HASH_TABLE_DYNAMIC
 186 #define T (*table)
 187 #define TA struct P(table) *table
 188 #define TAC TA,
 189 #define TAU TA UNUSED
 190 #define TAUC TA UNUSED,
 191 #define TT table
 192 #define TTC table,
 193 #else
 194 struct P(table) P(table);
 195 #define T P(table)
 196 #define TA void
 197 #define TAC
 198 #define TAU void
 199 #define TAUC
 200 #define TT
 201 #define TTC
 202 #endif
 203
 204 /* Preset parameters */
 205
 206 #if defined(HASH_KEY_ATOMIC)
 207
 208 #define HASH_KEY(x) x HASH_KEY_ATOMIC
 209
 210 #ifndef HASH_ATOMIC_TYPE
 211 #  define HASH_ATOMIC_TYPE int
 212 #endif
 213 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
 214
 215 #ifndef HASH_GIVE_HASHFN
 216 #  define HASH_GIVE_HASHFN
 217    static inline int P(hash) (TAUC HASH_ATOMIC_TYPE x)
 218    { return ((sizeof(x) <= 4) ? hash_u32(x) : hash_u64(x)); }
 219 #endif
 220
 221 #ifndef HASH_GIVE_EQ
 222 #  define HASH_GIVE_EQ
 223    static inline int P(eq) (TAUC HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
 224    { return x == y; }
 225 #endif
 226
 227 #ifndef HASH_GIVE_INIT_KEY
 228 #  define HASH_GIVE_INIT_KEY
 229    static inline void P(init_key) (TAUC P(node) *n, HASH_ATOMIC_TYPE k)
 230    { HASH_KEY(n->) = k; }
 231 #endif
 232
 233 #elif defined(HASH_KEY_MEMORY)
 234
 235 #define HASH_KEY(x) x HASH_KEY_MEMORY
 236
 237 #define HASH_KEY_DECL byte HASH_KEY( )[HASH_KEY_SIZE]
 238
 239 #ifndef HASH_GIVE_HASHFN
 240 #  define HASH_GIVE_HASHFN
 241    static inline int P(hash) (TAUC byte *x)
 242    { return hash_block(x, HASH_KEY_SIZE); }
 243 #endif
 244
 245 #ifndef HASH_GIVE_EQ
 246 #  define HASH_GIVE_EQ
 247    static inline int P(eq) (TAUC byte *x, byte *y)
 248    { return !memcmp(x, y, HASH_KEY_SIZE); }
 249 #endif
 250
 251 #ifndef HASH_GIVE_INIT_KEY
 252 #  define HASH_GIVE_INIT_KEY
 253    static inline void P(init_key) (TAUC P(node) *n, byte *k)
 254    { memcpy(HASH_KEY(n->), k, HASH_KEY_SIZE); }
 255 #endif
 256
 257 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 258
 259 #ifdef HASH_KEY_STRING
 260 #  define HASH_KEY(x) x HASH_KEY_STRING
 261 #  ifndef HASH_GIVE_INIT_KEY
 262 #    define HASH_GIVE_INIT_KEY
 263      static inline void P(init_key) (TAUC P(node) *n, char *k)
 264      { HASH_KEY(n->) = k; }
 265 #  endif
 266 #else
 267 #  define HASH_KEY(x) x HASH_KEY_ENDSTRING
 268 #  define HASH_GIVE_EXTRA_SIZE
 269    static inline int P(extra_size) (TAUC char *k)
 270    { return strlen(k); }
 271 #  ifndef HASH_GIVE_INIT_KEY
 272 #    define HASH_GIVE_INIT_KEY
 273      static inline void P(init_key) (TAUC P(node) *n, char *k)
 274      { strcpy(HASH_KEY(n->), k); }
 275 #  endif
 276 #endif
 277 #define HASH_KEY_DECL char *HASH_KEY( )
 278
 279 #ifndef HASH_GIVE_HASHFN
 280 #define HASH_GIVE_HASHFN
 281   static inline uns P(hash) (TAUC char *k)
 282    {
 283 #    ifdef HASH_NOCASE
 284        return hash_string_nocase(k);
 285 #    else
 286        return hash_string(k);
 287 #    endif
 288    }
 289 #endif
 290
 291 #ifndef HASH_GIVE_EQ
 292 #  define HASH_GIVE_EQ
 293    static inline int P(eq) (TAUC char *x, char *y)
 294    {
 295 #    ifdef HASH_NOCASE
 296        return !strcasecmp(x,y);
 297 #    else
 298        return !strcmp(x,y);
 299 #    endif
 300    }
 301 #endif
 302
 303 #elif defined(HASH_KEY_COMPLEX)
 304
 305 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
 306
 307 #else
 308 #error You forgot to set the hash key type.
 309 #endif
 310
 311 /* Defaults for missing parameters */
 312
 313 #ifndef HASH_GIVE_HASHFN
 314 #error Unable to determine which hash function to use.
 315 #endif
 316
 317 #ifndef HASH_GIVE_EQ
 318 #error Unable to determine how to compare two keys.
 319 #endif
 320
 321 #ifdef HASH_GIVE_EXTRA_SIZE
 322 /* This trickery is needed to avoid `unused parameter' warnings */
 323 #define HASH_EXTRA_SIZE(x) P(extra_size)(TTC x)
 324 #else
 325 /*
 326  *  Beware, C macros are expanded iteratively, not recursively,
 327  *  hence we get only a _single_ argument, although the expansion
 328  *  of HASH_KEY contains commas.
 329  */
 330 #define HASH_EXTRA_SIZE(x) 0
 331 #endif
 332
 333 #ifndef HASH_GIVE_INIT_KEY
 334 #error Unable to determine how to initialize keys.
 335 #endif
 336
 337 #ifndef HASH_GIVE_INIT_DATA
 338 static inline void P(init_data) (TAUC P(node) *n UNUSED)
 339 {
 340 }
 341 #endif
 342
 343 #ifdef HASH_GIVE_ALLOC
 344 /* If the caller has requested to use his own allocation functions, do so */
 345 static inline void P(init_alloc) (TAU) { }
 346 static inline void P(cleanup_alloc) (TAU) { }
 347
 348 #elif defined(HASH_USE_POOL)
 349 /* If the caller has requested to use his mempool, do so */
 350 #include <ucw/mempool.h>
 351 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
 352 static inline void P(free) (TAUC void *x UNUSED) { }
 353 static inline void P(init_alloc) (TAU) { }
 354 static inline void P(cleanup_alloc) (TAU) { }
 355
 356 #elif defined(HASH_AUTO_POOL)
 357 /* Use our own pools */
 358 #include <ucw/mempool.h>
 359 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(T.pool, size); }
 360 static inline void P(free) (TAUC void *x UNUSED) { }
 361 static inline void P(init_alloc) (TAU) { T.pool = mp_new(HASH_AUTO_POOL); }
 362 static inline void P(cleanup_alloc) (TAU) { mp_delete(T.pool); }
 363 #define HASH_USE_POOL
 364
 365 #elif defined(HASH_USE_ELTPOOL)
 366 /* If the caller has requested to use his eltpool, do so */
 367 #include <ucw/eltpool.h>
 368 static inline void * P(alloc) (TAUC unsigned int size UNUSED) { ASSERT(size <= (HASH_USE_ELTPOOL)->elt_size); return ep_alloc(HASH_USE_ELTPOOL); }
 369 static inline void P(free) (TAUC void *x) { ep_free(HASH_USE_ELTPOOL, x); }
 370 static inline void P(init_alloc) (TAU) { }
 371 static inline void P(cleanup_alloc) (TAU) { }
 372
 373 #elif defined(HASH_AUTO_ELTPOOL)
 374 /* Use our own eltpools */
 375 #include <ucw/eltpool.h>
 376 static inline void * P(alloc) (TAUC unsigned int size UNUSED) { return ep_alloc(T.eltpool); }
 377 static inline void P(free) (TAUC void *x) { ep_free(T.eltpool, x); }
 378 static inline void P(init_alloc) (TAU) { T.eltpool = ep_new(sizeof(P(bucket)), HASH_AUTO_ELTPOOL); }
 379 static inline void P(cleanup_alloc) (TAU) { ep_delete(T.eltpool); }
 380 #define HASH_USE_ELTPOOL
 381
 382 #else
 383 /* The default allocation method */
 384 static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }
 385 static inline void P(free) (TAUC void *x) { xfree(x); }
 386 static inline void P(init_alloc) (TAU) { }
 387 static inline void P(cleanup_alloc) (TAU) { }
 388
 389 #endif
 390
 391 #if defined(HASH_USE_ELTPOOL) && defined(HASH_GIVE_EXTRA_SIZE)
 392 #error Eltpools not supported in combination with variable-sized nodes
 393 #endif
 394
 395 #ifdef HASH_GIVE_TABLE_ALLOC
 396 /* If the caller has requested to use his own allocation functions, do so */
 397 #elif defined(HASH_TABLE_ALLOC)
 398 #ifdef HASH_USE_ELTPOOL
 399 #error HASH_TABLE_ALLOC not supported in combination with eltpools
 400 #endif
 401 static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(TTC size); }
 402 static inline void P(table_free) (TAUC void *x) { P(free)(TTC x); }
 403 #else
 404 static inline void * P(table_alloc) (TAUC unsigned int size) { return xmalloc(size); }
 405 static inline void P(table_free) (TAUC void *x) { xfree(x); }
 406 #endif
 407
 408 #if defined(HASH_USE_POOL) && defined(HASH_TABLE_ALLOC) && !defined(HASH_TABLE_GROWING)
 409 #define HASH_TABLE_GROWING
 410 #endif
 411
 412 #ifndef HASH_DEFAULT_SIZE
 413 #define HASH_DEFAULT_SIZE 32
 414 #endif
 415
 416 #ifndef HASH_FN_BITS
 417 #define HASH_FN_BITS 32
 418 #endif
 419
 420 #ifdef HASH_ZERO_FILL
 421 static inline void * P(new_bucket)(TAUC uns size)
 422 {
 423   byte *buck = P(alloc)(TTC size);
 424   bzero(buck, size);
 425   return buck;
 426 }
 427 #else
 428 static inline void * P(new_bucket)(TAUC uns size) { return P(alloc)(TTC size); }
 429 #endif
 430
 431 /* Now the operations */
 432
 433 static void P(alloc_table) (TAU)
 434 {
 435   T.hash_size = next_table_prime(T.hash_size);
 436   T.ht = P(table_alloc)(TTC sizeof(void *) * T.hash_size);
 437   bzero(T.ht, sizeof(void *) * T.hash_size);
 438   if (2*T.hash_size < T.hash_hard_max)
 439     T.hash_max = 2*T.hash_size;
 440   else
 441     T.hash_max = ~0U;
 442 #ifndef HASH_TABLE_GROWING
 443   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
 444     T.hash_min = T.hash_size/4;
 445   else
 446 #endif
 447     T.hash_min = 0;
 448 }
 449
 450 /**
 451  * Initializes the hash table.
 452  * This one is available no matter what `HASH_WANT_` macros you defined or not.
 453  **/
 454 static void HASH_PREFIX(init)(TA)
 455 {
 456   T.hash_count = 0;
 457   T.hash_size = HASH_DEFAULT_SIZE;
 458 #if HASH_FN_BITS < 28
 459   T.hash_hard_max = 1 << HASH_FN_BITS;
 460 #else
 461   T.hash_hard_max = 1 << 28;
 462 #endif
 463   P(init_alloc)(TT);
 464   P(alloc_table)(TT);
 465 }
 466
 467 #ifdef HASH_WANT_CLEANUP
 468 /**
 469  * Deallocates the hash table, including the nodes.
 470  * It is available if you defined <<want_cleanup,`HASH_WANT_CLEANUP`>>.
 471  **/
 472 static void HASH_PREFIX(cleanup)(TA)
 473 {
 474 #ifndef HASH_USE_POOL
 475   uns i;
 476   P(bucket) *b, *bb;
 477
 478   for (i=0; i<T.hash_size; i++)
 479     for (b=T.ht[i]; b; b=bb)
 480       {
 481         bb = b->next;
 482         P(free)(TTC b);
 483       }
 484 #endif
 485   P(cleanup_alloc)(TT);
 486   P(table_free)(TTC T.ht);
 487 }
 488 #endif
 489
 490 static inline uns P(bucket_hash) (TAUC P(bucket) *b)
 491 {
 492 #ifdef HASH_CONSERVE_SPACE
 493   return P(hash)(TTC HASH_KEY(b->n.));
 494 #else
 495   return b->hash;
 496 #endif
 497 }
 498
 499 static void P(rehash) (TAC uns size)
 500 {
 501   P(bucket) *b, *nb;
 502   P(bucket) **oldt = T.ht, **newt;
 503   uns oldsize = T.hash_size;
 504   uns i, h;
 505
 506   DBG("Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
 507   T.hash_size = size;
 508   P(alloc_table)(TT);
 509   newt = T.ht;
 510   for (i=0; i<oldsize; i++)
 511     {
 512       b = oldt[i];
 513       while (b)
 514         {
 515           nb = b->next;
 516           h = P(bucket_hash)(TTC b) % T.hash_size;
 517           b->next = newt[h];
 518           newt[h] = b;
 519           b = nb;
 520         }
 521     }
 522   P(table_free)(TTC oldt);
 523 }
 524
 525 #ifdef HASH_WANT_FIND
 526 /**
 527  * Finds a node with given key (specified in the @HAS_KEY_DECL parameter).
 528  * If it does not exist, NULL is returned.
 529  *
 530  * Enabled by the <<want_find,`HASH_WANT_FIND`>> macro.
 531  **/
 532 static HASH_NODE* HASH_PREFIX(find)(TAC HASH_KEY_DECL)
 533 {
 534   uns h0 = P(hash) (TTC HASH_KEY( ));
 535   uns h = h0 % T.hash_size;
 536   P(bucket) *b;
 537
 538   for (b=T.ht[h]; b; b=b->next)
 539     {
 540       if (
 541 #ifndef HASH_CONSERVE_SPACE
 542           b->hash == h0 &&
 543 #endif
 544           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
 545         return &b->n;
 546     }
 547   return NULL;
 548 }
 549 #endif
 550
 551 #ifdef HASH_WANT_FIND_NEXT
 552 /**
 553  * Finds next node with the same key. Returns NULL if it does not exist.
 554  *
 555  * Enabled by the <<want_find_next,`HASH_WANT_FIND_NEXT`>> macro.
 556  **/
 557 static HASH_NODE* HASH_PREFIX(find_next)(TAC P(node) *start)
 558 {
 559 #ifndef HASH_CONSERVE_SPACE
 560   uns h0 = P(hash) (TTC HASH_KEY(start->));
 561 #endif
 562   P(bucket) *b = SKIP_BACK(P(bucket), n, start);
 563
 564   for (b=b->next; b; b=b->next)
 565     {
 566       if (
 567 #ifndef HASH_CONSERVE_SPACE
 568           b->hash == h0 &&
 569 #endif
 570           P(eq)(TTC HASH_KEY(start->), HASH_KEY(b->n.)))
 571         return &b->n;
 572     }
 573   return NULL;
 574 }
 575 #endif
 576
 577 #ifdef HASH_WANT_NEW
 578 /**
 579  * Generates a new node with a given key.
 580  *
 581  * Enabled by the <<want_new,`HASH_WANT_NEW`>> macro.
 582  **/
 583 static HASH_NODE * HASH_PREFIX(new)(TAC HASH_KEY_DECL)
 584 {
 585   uns h0, h;
 586   P(bucket) *b;
 587
 588   h0 = P(hash) (TTC HASH_KEY( ));
 589   h = h0 % T.hash_size;
 590   b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 591   b->next = T.ht[h];
 592   T.ht[h] = b;
 593 #ifndef HASH_CONSERVE_SPACE
 594   b->hash = h0;
 595 #endif
 596   P(init_key)(TTC &b->n, HASH_KEY( ));
 597   P(init_data)(TTC &b->n);
 598   if (T.hash_count++ >= T.hash_max)
 599     P(rehash)(TTC 2*T.hash_size);
 600   return &b->n;
 601 }
 602 #endif
 603
 604 #ifdef HASH_WANT_LOOKUP
 605 #ifdef HASH_LOOKUP_DETECT_NEW
 606 /**
 607  * Finds a node with a given key. If it does not exist, a new one is created.
 608  * It is strongly recommended to use <<give_init_data,`HASH_GIVE_INIT_DATA`>>.
 609  *
 610  * This one is enabled by the <<want_lookup,`HASH_WANT_LOOKUP`>> macro.
 611  * The @new_item argument is available only if <<lookup_detect_new,`HASH_LOOKUP_DETECT_NEW`>> was given.
 612  **/
 613 static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL, int *new_item)
 614 #else
 615 static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL)
 616 #endif
 617 {
 618   uns h0 = P(hash) (TTC HASH_KEY( ));
 619   uns h = h0 % T.hash_size;
 620   P(bucket) *b;
 621
 622   for (b=T.ht[h]; b; b=b->next)
 623     {
 624       if (
 625 #ifndef HASH_CONSERVE_SPACE
 626           b->hash == h0 &&
 627 #endif
 628           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.))) {
 629 #ifdef HASH_LOOKUP_DETECT_NEW
 630         *new_item = 0;
 631 #endif
 632         return &b->n;
 633       }
 634     }
 635
 636   b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 637   b->next = T.ht[h];
 638   T.ht[h] = b;
 639 #ifndef HASH_CONSERVE_SPACE
 640   b->hash = h0;
 641 #endif
 642   P(init_key)(TTC &b->n, HASH_KEY( ));
 643   P(init_data)(TTC &b->n);
 644   if (T.hash_count++ >= T.hash_max)
 645     P(rehash)(TTC 2*T.hash_size);
 646 #ifdef HASH_LOOKUP_DETECT_NEW
 647   *new_item = 1;
 648 #endif
 649   return &b->n;
 650 }
 651 #endif
 652
 653 #ifdef HASH_WANT_DELETE
 654 /**
 655  * Removes a node with the given key from hash table and deallocates it.
 656  *
 657  * Success is returned.
 658  *
 659  * This one is enabled by <<want_delete,`HASH_WANT_DELETE`>> macro.
 660  **/
 661 static int HASH_PREFIX(delete)(TAC HASH_KEY_DECL)
 662 {
 663   uns h0 = P(hash) (TTC HASH_KEY( ));
 664   uns h = h0 % T.hash_size;
 665   P(bucket) *b, **bb;
 666
 667   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
 668     {
 669       if (
 670 #ifndef HASH_CONSERVE_SPACE
 671           b->hash == h0 &&
 672 #endif
 673           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
 674         {
 675           *bb = b->next;
 676           P(free)(TTC b);
 677           T.hash_count--;
 678 #ifndef HASH_TABLE_GROWING
 679           if (T.hash_count < T.hash_min)
 680             P(rehash)(TTC T.hash_size/2);
 681 #endif
 682           return 1;
 683         }
 684     }
 685   return 0;
 686 }
 687 #endif
 688
 689 #ifdef HASH_WANT_REMOVE
 690 /**
 691  * Removes a given node and deallocates it.
 692  * It differs from <<fun__GENERIC_LINK|HASH_PREFIX|delete,`HASH_PREFIX(delete)()`>>
 693  * in its type of parameter -- this one deletes a specific node, that one looks for it by a key.
 694  *
 695  * Enabled by <<want_remove,`HASH_WANT_REMOVE`>> macro.
 696  **/
 697 static void HASH_PREFIX(remove)(TAC HASH_NODE *n)
 698 {
 699   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
 700   uns h0 = P(bucket_hash)(TTC x);
 701   uns h = h0 % T.hash_size;
 702   P(bucket) *b, **bb;
 703
 704   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
 705     ;
 706   ASSERT(b);
 707   *bb = b->next;
 708   P(free)(TTC b);
 709   T.hash_count--;
 710 #ifndef HASH_TABLE_GROWING
 711   if (T.hash_count < T.hash_min)
 712     P(rehash)(TTC T.hash_size/2);
 713 #endif
 714 }
 715 #endif
 716
 717 /* And the iterator */
 718
 719 #ifndef HASH_FOR_ALL
 720
 721 #define HASH_FOR_ALL_DYNAMIC(h_px, h_table, h_var)                                      \
 722 do {                                                                                    \
 723   uns h_slot;                                                                           \
 724   struct GLUE_(h_px,bucket) *h_buck;                                                    \
 725   for (h_slot=0; h_slot < (h_table)->hash_size; h_slot++)                               \
 726     for (h_buck = (h_table)->ht[h_slot]; h_buck; h_buck = h_buck->next)                 \
 727       {                                                                                 \
 728         GLUE_(h_px,node) *h_var = &h_buck->n;
 729 #define HASH_FOR_ALL(h_px, h_var) HASH_FOR_ALL_DYNAMIC(h_px, &GLUE_(h_px,table), h_var)
 730 #define HASH_END_FOR } } while(0)
 731 #define HASH_BREAK
 732 #define HASH_CONTINUE continue
 733
 734 #endif
 735
 736 /* Finally, undefine all the parameters */
 737
 738 #undef P
 739 #undef T
 740 #undef TA
 741 #undef TAC
 742 #undef TAU
 743 #undef TAUC
 744 #undef TT
 745 #undef TTC
 746
 747 #undef HASH_ATOMIC_TYPE
 748 #undef HASH_CONSERVE_SPACE
 749 #undef HASH_DEFAULT_SIZE
 750 #undef HASH_EXTRA_SIZE
 751 #undef HASH_FN_BITS
 752 #undef HASH_GIVE_ALLOC
 753 #undef HASH_GIVE_TABLE_ALLOC
 754 #undef HASH_GIVE_EQ
 755 #undef HASH_GIVE_EXTRA_SIZE
 756 #undef HASH_GIVE_HASHFN
 757 #undef HASH_GIVE_INIT_DATA
 758 #undef HASH_GIVE_INIT_KEY
 759 #undef HASH_KEY
 760 #undef HASH_KEY_ATOMIC
 761 #undef HASH_KEY_COMPLEX
 762 #undef HASH_KEY_DECL
 763 #undef HASH_KEY_ENDSTRING
 764 #undef HASH_KEY_STRING
 765 #undef HASH_KEY_MEMORY
 766 #undef HASH_KEY_SIZE
 767 #undef HASH_NOCASE
 768 #undef HASH_NODE
 769 #undef HASH_PREFIX
 770 #undef HASH_USE_POOL
 771 #undef HASH_AUTO_POOL
 772 #undef HASH_USE_ELTPOOL
 773 #undef HASH_AUTO_ELTPOOL
 774 #undef HASH_WANT_CLEANUP
 775 #undef HASH_WANT_DELETE
 776 #undef HASH_WANT_FIND
 777 #undef HASH_WANT_FIND_NEXT
 778 #undef HASH_WANT_LOOKUP
 779 #undef HASH_WANT_NEW
 780 #undef HASH_WANT_REMOVE
 781 #undef HASH_TABLE_ALLOC
 782 #undef HASH_TABLE_GROWING
 783 #undef HASH_TABLE_DYNAMIC
 784 #undef HASH_TABLE_VARS
 785 #undef HASH_ZERO_FILL
 786 #undef HASH_LOOKUP_DETECT_NEW