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