libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
   5
   6 This file is part of the libiberty library.
   7 Libiberty is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU Library General Public
   9 License as published by the Free Software Foundation; either
  10 version 2 of the License, or (at your option) any later version.
  11
  12 Libiberty is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 Library General Public License for more details.
  16
  17 You should have received a copy of the GNU Library General Public
  18 License along with libiberty; see the file COPYING.LIB.  If
  19 not, write to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 /* This package implements basic hash table functionality.  It is possible
  23    to search for an entry, create an entry and destroy an entry.
  24
  25    Elements in the table are generic pointers.
  26
  27    The size of the table is not fixed; if the occupancy of the table
  28    grows too high the hash table will be expanded.
  29
  30    The abstract data implementation is based on generalized Algorithm D
  31    from Knuth's book "The art of computer programming".  Hash table is
  32    expanded by creation of new hash table and transferring elements from
  33    the old table to the new table. */
  34
  35 #ifdef HAVE_CONFIG_H
  36 #include "config.h"
  37 #endif
  38
  39 #include <sys/types.h>
  40
  41 #ifdef HAVE_STDLIB_H
  42 #include <stdlib.h>
  43 #endif
  44 #ifdef HAVE_STRING_H
  45 #include <string.h>
  46 #endif
  47 #ifdef HAVE_MALLOC_H
  48 #include <malloc.h>
  49 #endif
  50 #ifdef HAVE_LIMITS_H
  51 #include <limits.h>
  52 #endif
  53 #ifdef HAVE_STDINT_H
  54 #include <stdint.h>
  55 #endif
  56
  57 #include <stdio.h>
  58
  59 #include "libiberty.h"
  60 #include "ansidecl.h"
  61 #include "hashtab.h"
  62
  63 #ifndef CHAR_BIT
  64 #define CHAR_BIT 8
  65 #endif
  66
  67 /* This macro defines reserved value for empty table entry. */
  68
  69 #define EMPTY_ENTRY    ((PTR) 0)
  70
  71 /* This macro defines reserved value for table entry which contained
  72    a deleted element. */
  73
  74 #define DELETED_ENTRY  ((PTR) 1)
  75
  76 static unsigned int higher_prime_index (unsigned long);
  77 static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int);
  78 static hashval_t htab_mod (hashval_t, htab_t);
  79 static hashval_t htab_mod_m2 (hashval_t, htab_t);
  80 static hashval_t hash_pointer (const void *);
  81 static int eq_pointer (const void *, const void *);
  82 static int htab_expand (htab_t);
  83 static PTR *find_empty_slot_for_expand (htab_t, hashval_t);
  84
  85 /* At some point, we could make these be NULL, and modify the
  86    hash-table routines to handle NULL specially; that would avoid
  87    function-call overhead for the common case of hashing pointers.  */
  88 htab_hash htab_hash_pointer = hash_pointer;
  89 htab_eq htab_eq_pointer = eq_pointer;
  90
  91 /* Table of primes and multiplicative inverses.
  92
  93    Note that these are not minimally reduced inverses.  Unlike when generating
  94    code to divide by a constant, we want to be able to use the same algorithm
  95    all the time.  All of these inverses (are implied to) have bit 32 set.
  96
  97    For the record, here's the function that computed the table; it's a
  98    vastly simplified version of the function of the same name from gcc.  */
  99
 100 #if 0
 101 unsigned int
 102 ceil_log2 (unsigned int x)
 103 {
 104   int i;
 105   for (i = 31; i >= 0 ; --i)
 106     if (x > (1u << i))
 107       return i+1;
 108   abort ();
 109 }
 110
 111 unsigned int
 112 choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
 113 {
 114   unsigned long long mhigh;
 115   double nx;
 116   int lgup, post_shift;
 117   int pow, pow2;
 118   int n = 32, precision = 32;
 119
 120   lgup = ceil_log2 (d);
 121   pow = n + lgup;
 122   pow2 = n + lgup - precision;
 123
 124   nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
 125   mhigh = nx / d;
 126
 127   *shiftp = lgup - 1;
 128   *mlp = mhigh;
 129   return mhigh >> 32;
 130 }
 131 #endif
 132
 133 struct prime_ent
 134 {
 135   hashval_t prime;
 136   hashval_t inv;
 137   hashval_t inv_m2;     /* inverse of prime-2 */
 138   hashval_t shift;
 139 };
 140
 141 static struct prime_ent const prime_tab[] = {
 142   {          7, 0x24924925, 0x9999999b, 2 },
 143   {         13, 0x3b13b13c, 0x745d1747, 3 },
 144   {         31, 0x08421085, 0x1a7b9612, 4 },
 145   {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
 146   {        127, 0x02040811, 0x0624dd30, 6 },
 147   {        251, 0x05197f7e, 0x073260a5, 7 },
 148   {        509, 0x01824366, 0x02864fc8, 8 },
 149   {       1021, 0x00c0906d, 0x014191f7, 9 },
 150   {       2039, 0x0121456f, 0x0161e69e, 10 },
 151   {       4093, 0x00300902, 0x00501908, 11 },
 152   {       8191, 0x00080041, 0x00180241, 12 },
 153   {      16381, 0x000c0091, 0x00140191, 13 },
 154   {      32749, 0x002605a5, 0x002a06e6, 14 },
 155   {      65521, 0x000f00e2, 0x00110122, 15 },
 156   {     131071, 0x00008001, 0x00018003, 16 },
 157   {     262139, 0x00014002, 0x0001c004, 17 },
 158   {     524287, 0x00002001, 0x00006001, 18 },
 159   {    1048573, 0x00003001, 0x00005001, 19 },
 160   {    2097143, 0x00004801, 0x00005801, 20 },
 161   {    4194301, 0x00000c01, 0x00001401, 21 },
 162   {    8388593, 0x00001e01, 0x00002201, 22 },
 163   {   16777213, 0x00000301, 0x00000501, 23 },
 164   {   33554393, 0x00001381, 0x00001481, 24 },
 165   {   67108859, 0x00000141, 0x000001c1, 25 },
 166   {  134217689, 0x000004e1, 0x00000521, 26 },
 167   {  268435399, 0x00000391, 0x000003b1, 27 },
 168   {  536870909, 0x00000019, 0x00000029, 28 },
 169   { 1073741789, 0x0000008d, 0x00000095, 29 },
 170   { 2147483647, 0x00000003, 0x00000007, 30 },
 171   /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
 172   { 0xfffffffb, 0x00000006, 0x00000008, 31 }
 173 };
 174
 175 /* The following function returns an index into the above table of the
 176    nearest prime number which is greater than N, and near a power of two. */
 177
 178 static unsigned int
 179 higher_prime_index (unsigned long n)
 180 {
 181   unsigned int low = 0;
 182   unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
 183
 184   while (low != high)
 185     {
 186       unsigned int mid = low + (high - low) / 2;
 187       if (n > prime_tab[mid].prime)
 188         low = mid + 1;
 189       else
 190         high = mid;
 191     }
 192
 193   /* If we've run out of primes, abort.  */
 194   if (n > prime_tab[low].prime)
 195     {
 196       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 197       abort ();
 198     }
 199
 200   return low;
 201 }
 202
 203 /* Returns a hash code for P.  */
 204
 205 static hashval_t
 206 hash_pointer (const PTR p)
 207 {
 208   return (hashval_t) ((long)p >> 3);
 209 }
 210
 211 /* Returns non-zero if P1 and P2 are equal.  */
 212
 213 static int
 214 eq_pointer (const PTR p1, const PTR p2)
 215 {
 216   return p1 == p2;
 217 }
 218
 219
 220 /* The parens around the function names in the next two definitions
 221    are essential in order to prevent macro expansions of the name.
 222    The bodies, however, are expanded as expected, so they are not
 223    recursive definitions.  */
 224
 225 /* Return the current size of given hash table.  */
 226
 227 #define htab_size(htab)  ((htab)->size)
 228
 229 size_t
 230 (htab_size) (htab_t htab)
 231 {
 232   return htab_size (htab);
 233 }
 234
 235 /* Return the current number of elements in given hash table. */
 236
 237 #define htab_elements(htab)  ((htab)->n_elements - (htab)->n_deleted)
 238
 239 size_t
 240 (htab_elements) (htab_t htab)
 241 {
 242   return htab_elements (htab);
 243 }
 244
 245 /* Return X % Y.  */
 246
 247 static inline hashval_t
 248 htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
 249 {
 250   /* The multiplicative inverses computed above are for 32-bit types, and
 251      requires that we be able to compute a highpart multiply.  */
 252 #ifdef UNSIGNED_64BIT_TYPE
 253   __extension__ typedef UNSIGNED_64BIT_TYPE ull;
 254   if (sizeof (hashval_t) * CHAR_BIT <= 32)
 255     {
 256       hashval_t t1, t2, t3, t4, q, r;
 257
 258       t1 = ((ull)x * inv) >> 32;
 259       t2 = x - t1;
 260       t3 = t2 >> 1;
 261       t4 = t1 + t3;
 262       q  = t4 >> shift;
 263       r  = x - (q * y);
 264
 265       return r;
 266     }
 267 #endif
 268
 269   /* Otherwise just use the native division routines.  */
 270   return x % y;
 271 }
 272
 273 /* Compute the primary hash for HASH given HTAB's current size.  */
 274
 275 static inline hashval_t
 276 htab_mod (hashval_t hash, htab_t htab)
 277 {
 278   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
 279   return htab_mod_1 (hash, p->prime, p->inv, p->shift);
 280 }
 281
 282 /* Compute the secondary hash for HASH given HTAB's current size.  */
 283
 284 static inline hashval_t
 285 htab_mod_m2 (hashval_t hash, htab_t htab)
 286 {
 287   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
 288   return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
 289 }
 290
 291 /* This function creates table with length slightly longer than given
 292    source length.  Created hash table is initiated as empty (all the
 293    hash table entries are EMPTY_ENTRY).  The function returns the
 294    created hash table, or NULL if memory allocation fails.  */
 295
 296 htab_t
 297 htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f,
 298                    htab_del del_f, htab_alloc alloc_f, htab_free free_f)
 299 {
 300   htab_t result;
 301   unsigned int size_prime_index;
 302
 303   size_prime_index = higher_prime_index (size);
 304   size = prime_tab[size_prime_index].prime;
 305
 306   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
 307   if (result == NULL)
 308     return NULL;
 309   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 310   if (result->entries == NULL)
 311     {
 312       if (free_f != NULL)
 313         (*free_f) (result);
 314       return NULL;
 315     }
 316   result->size = size;
 317   result->size_prime_index = size_prime_index;
 318   result->hash_f = hash_f;
 319   result->eq_f = eq_f;
 320   result->del_f = del_f;
 321   result->alloc_f = alloc_f;
 322   result->free_f = free_f;
 323   return result;
 324 }
 325
 326 /* As above, but use the variants of alloc_f and free_f which accept
 327    an extra argument.  */
 328
 329 htab_t
 330 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f,
 331                       htab_del del_f, void *alloc_arg,
 332                       htab_alloc_with_arg alloc_f,
 333                       htab_free_with_arg free_f)
 334 {
 335   htab_t result;
 336   unsigned int size_prime_index;
 337
 338   size_prime_index = higher_prime_index (size);
 339   size = prime_tab[size_prime_index].prime;
 340
 341   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 342   if (result == NULL)
 343     return NULL;
 344   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 345   if (result->entries == NULL)
 346     {
 347       if (free_f != NULL)
 348         (*free_f) (alloc_arg, result);
 349       return NULL;
 350     }
 351   result->size = size;
 352   result->size_prime_index = size_prime_index;
 353   result->hash_f = hash_f;
 354   result->eq_f = eq_f;
 355   result->del_f = del_f;
 356   result->alloc_arg = alloc_arg;
 357   result->alloc_with_arg_f = alloc_f;
 358   result->free_with_arg_f = free_f;
 359   return result;
 360 }
 361
 362 /* Update the function pointers and allocation parameter in the htab_t.  */
 363
 364 void
 365 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
 366                        htab_del del_f, PTR alloc_arg,
 367                        htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
 368 {
 369   htab->hash_f = hash_f;
 370   htab->eq_f = eq_f;
 371   htab->del_f = del_f;
 372   htab->alloc_arg = alloc_arg;
 373   htab->alloc_with_arg_f = alloc_f;
 374   htab->free_with_arg_f = free_f;
 375 }
 376
 377 /* These functions exist solely for backward compatibility.  */
 378
 379 #undef htab_create
 380 htab_t
 381 htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
 382 {
 383   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 384 }
 385
 386 htab_t
 387 htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
 388 {
 389   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 390 }
 391
 392 /* This function frees all memory allocated for given hash table.
 393    Naturally the hash table must already exist. */
 394
 395 void
 396 htab_delete (htab_t htab)
 397 {
 398   size_t size = htab_size (htab);
 399   PTR *entries = htab->entries;
 400   int i;
 401
 402   if (htab->del_f)
 403     for (i = size - 1; i >= 0; i--)
 404       if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
 405         (*htab->del_f) (entries[i]);
 406
 407   if (htab->free_f != NULL)
 408     {
 409       (*htab->free_f) (entries);
 410       (*htab->free_f) (htab);
 411     }
 412   else if (htab->free_with_arg_f != NULL)
 413     {
 414       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
 415       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 416     }
 417 }
 418
 419 /* This function clears all entries in the given hash table.  */
 420
 421 void
 422 htab_empty (htab_t htab)
 423 {
 424   size_t size = htab_size (htab);
 425   PTR *entries = htab->entries;
 426   int i;
 427
 428   if (htab->del_f)
 429     for (i = size - 1; i >= 0; i--)
 430       if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
 431         (*htab->del_f) (entries[i]);
 432
 433   memset (entries, 0, size * sizeof (PTR));
 434 }
 435
 436 /* Similar to htab_find_slot, but without several unwanted side effects:
 437     - Does not call htab->eq_f when it finds an existing entry.
 438     - Does not change the count of elements/searches/collisions in the
 439       hash table.
 440    This function also assumes there are no deleted entries in the table.
 441    HASH is the hash value for the element to be inserted.  */
 442
 443 static PTR *
 444 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
 445 {
 446   hashval_t index = htab_mod (hash, htab);
 447   size_t size = htab_size (htab);
 448   PTR *slot = htab->entries + index;
 449   hashval_t hash2;
 450
 451   if (*slot == EMPTY_ENTRY)
 452     return slot;
 453   else if (*slot == DELETED_ENTRY)
 454     abort ();
 455
 456   hash2 = htab_mod_m2 (hash, htab);
 457   for (;;)
 458     {
 459       index += hash2;
 460       if (index >= size)
 461         index -= size;
 462
 463       slot = htab->entries + index;
 464       if (*slot == EMPTY_ENTRY)
 465         return slot;
 466       else if (*slot == DELETED_ENTRY)
 467         abort ();
 468     }
 469 }
 470
 471 /* The following function changes size of memory allocated for the
 472    entries and repeatedly inserts the table elements.  The occupancy
 473    of the table after the call will be about 50%.  Naturally the hash
 474    table must already exist.  Remember also that the place of the
 475    table entries is changed.  If memory allocation failures are allowed,
 476    this function will return zero, indicating that the table could not be
 477    expanded.  If all goes well, it will return a non-zero value.  */
 478
 479 static int
 480 htab_expand (htab_t htab)
 481 {
 482   PTR *oentries;
 483   PTR *olimit;
 484   PTR *p;
 485   PTR *nentries;
 486   size_t nsize, osize, elts;
 487   unsigned int oindex, nindex;
 488
 489   oentries = htab->entries;
 490   oindex = htab->size_prime_index;
 491   osize = htab->size;
 492   olimit = oentries + osize;
 493   elts = htab_elements (htab);
 494
 495   /* Resize only when table after removal of unused elements is either
 496      too full or too empty.  */
 497   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 498     {
 499       nindex = higher_prime_index (elts * 2);
 500       nsize = prime_tab[nindex].prime;
 501     }
 502   else
 503     {
 504       nindex = oindex;
 505       nsize = osize;
 506     }
 507
 508   if (htab->alloc_with_arg_f != NULL)
 509     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 510                                                   sizeof (PTR *));
 511   else
 512     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 513   if (nentries == NULL)
 514     return 0;
 515   htab->entries = nentries;
 516   htab->size = nsize;
 517   htab->size_prime_index = nindex;
 518   htab->n_elements -= htab->n_deleted;
 519   htab->n_deleted = 0;
 520
 521   p = oentries;
 522   do
 523     {
 524       PTR x = *p;
 525
 526       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 527         {
 528           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 529
 530           *q = x;
 531         }
 532
 533       p++;
 534     }
 535   while (p < olimit);
 536
 537   if (htab->free_f != NULL)
 538     (*htab->free_f) (oentries);
 539   else if (htab->free_with_arg_f != NULL)
 540     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 541   return 1;
 542 }
 543
 544 /* This function searches for a hash table entry equal to the given
 545    element.  It cannot be used to insert or delete an element.  */
 546
 547 PTR
 548 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
 549 {
 550   hashval_t index, hash2;
 551   size_t size;
 552   PTR entry;
 553
 554   htab->searches++;
 555   size = htab_size (htab);
 556   index = htab_mod (hash, htab);
 557
 558   entry = htab->entries[index];
 559   if (entry == EMPTY_ENTRY
 560       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 561     return entry;
 562
 563   hash2 = htab_mod_m2 (hash, htab);
 564   for (;;)
 565     {
 566       htab->collisions++;
 567       index += hash2;
 568       if (index >= size)
 569         index -= size;
 570
 571       entry = htab->entries[index];
 572       if (entry == EMPTY_ENTRY
 573           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 574         return entry;
 575     }
 576 }
 577
 578 /* Like htab_find_slot_with_hash, but compute the hash value from the
 579    element.  */
 580
 581 PTR
 582 htab_find (htab_t htab, const PTR element)
 583 {
 584   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 585 }
 586
 587 /* This function searches for a hash table slot containing an entry
 588    equal to the given element.  To delete an entry, call this with
 589    insert=NO_INSERT, then call htab_clear_slot on the slot returned
 590    (possibly after doing some checks).  To insert an entry, call this
 591    with insert=INSERT, then write the value you want into the returned
 592    slot.  When inserting an entry, NULL may be returned if memory
 593    allocation fails.  */
 594
 595 PTR *
 596 htab_find_slot_with_hash (htab_t htab, const PTR element,
 597                           hashval_t hash, enum insert_option insert)
 598 {
 599   PTR *first_deleted_slot;
 600   hashval_t index, hash2;
 601   size_t size;
 602   PTR entry;
 603
 604   size = htab_size (htab);
 605   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 606     {
 607       if (htab_expand (htab) == 0)
 608         return NULL;
 609       size = htab_size (htab);
 610     }
 611
 612   index = htab_mod (hash, htab);
 613
 614   htab->searches++;
 615   first_deleted_slot = NULL;
 616
 617   entry = htab->entries[index];
 618   if (entry == EMPTY_ENTRY)
 619     goto empty_entry;
 620   else if (entry == DELETED_ENTRY)
 621     first_deleted_slot = &htab->entries[index];
 622   else if ((*htab->eq_f) (entry, element))
 623     return &htab->entries[index];
 624
 625   hash2 = htab_mod_m2 (hash, htab);
 626   for (;;)
 627     {
 628       htab->collisions++;
 629       index += hash2;
 630       if (index >= size)
 631         index -= size;
 632
 633       entry = htab->entries[index];
 634       if (entry == EMPTY_ENTRY)
 635         goto empty_entry;
 636       else if (entry == DELETED_ENTRY)
 637         {
 638           if (!first_deleted_slot)
 639             first_deleted_slot = &htab->entries[index];
 640         }
 641       else if ((*htab->eq_f) (entry, element))
 642         return &htab->entries[index];
 643     }
 644
 645  empty_entry:
 646   if (insert == NO_INSERT)
 647     return NULL;
 648
 649   if (first_deleted_slot)
 650     {
 651       htab->n_deleted--;
 652       *first_deleted_slot = EMPTY_ENTRY;
 653       return first_deleted_slot;
 654     }
 655
 656   htab->n_elements++;
 657   return &htab->entries[index];
 658 }
 659
 660 /* Like htab_find_slot_with_hash, but compute the hash value from the
 661    element.  */
 662
 663 PTR *
 664 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
 665 {
 666   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 667                                    insert);
 668 }
 669
 670 /* This function deletes an element with the given value from hash
 671    table (the hash is computed from the element).  If there is no matching
 672    element in the hash table, this function does nothing.  */
 673
 674 void
 675 htab_remove_elt (htab_t htab, PTR element)
 676 {
 677   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
 678 }
 679
 680
 681 /* This function deletes an element with the given value from hash
 682    table.  If there is no matching element in the hash table, this
 683    function does nothing.  */
 684
 685 void
 686 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
 687 {
 688   PTR *slot;
 689
 690   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
 691   if (*slot == EMPTY_ENTRY)
 692     return;
 693
 694   if (htab->del_f)
 695     (*htab->del_f) (*slot);
 696
 697   *slot = DELETED_ENTRY;
 698   htab->n_deleted++;
 699 }
 700
 701 /* This function clears a specified slot in a hash table.  It is
 702    useful when you've already done the lookup and don't want to do it
 703    again.  */
 704
 705 void
 706 htab_clear_slot (htab_t htab, PTR *slot)
 707 {
 708   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
 709       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 710     abort ();
 711
 712   if (htab->del_f)
 713     (*htab->del_f) (*slot);
 714
 715   *slot = DELETED_ENTRY;
 716   htab->n_deleted++;
 717 }
 718
 719 /* This function scans over the entire hash table calling
 720    CALLBACK for each live entry.  If CALLBACK returns false,
 721    the iteration stops.  INFO is passed as CALLBACK's second
 722    argument.  */
 723
 724 void
 725 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
 726 {
 727   PTR *slot;
 728   PTR *limit;
 729
 730   slot = htab->entries;
 731   limit = slot + htab_size (htab);
 732
 733   do
 734     {
 735       PTR x = *slot;
 736
 737       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 738         if (!(*callback) (slot, info))
 739           break;
 740     }
 741   while (++slot < limit);
 742 }
 743
 744 /* Like htab_traverse_noresize, but does resize the table when it is
 745    too empty to improve effectivity of subsequent calls.  */
 746
 747 void
 748 htab_traverse (htab_t htab, htab_trav callback, PTR info)
 749 {
 750   if (htab_elements (htab) * 8 < htab_size (htab))
 751     htab_expand (htab);
 752
 753   htab_traverse_noresize (htab, callback, info);
 754 }
 755
 756 /* Return the fraction of fixed collisions during all work with given
 757    hash table. */
 758
 759 double
 760 htab_collisions (htab_t htab)
 761 {
 762   if (htab->searches == 0)
 763     return 0.0;
 764
 765   return (double) htab->collisions / (double) htab->searches;
 766 }
 767
 768 /* Hash P as a null-terminated string.
 769
 770    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 771    to applicability, though note that unlike hashtable.c, this hash table
 772    implementation re-hashes rather than chain buckets.
 773
 774    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 775    From: Zack Weinberg <zackw@panix.com>
 776    Date: Fri, 17 Aug 2001 02:15:56 -0400
 777
 778    I got it by extracting all the identifiers from all the source code
 779    I had lying around in mid-1999, and testing many recurrences of
 780    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 781    prime numbers or the appropriate identity.  This was the best one.
 782    I don't remember exactly what constituted "best", except I was
 783    looking at bucket-length distributions mostly.
 784
 785    So it should be very good at hashing identifiers, but might not be
 786    as good at arbitrary strings.
 787
 788    I'll add that it thoroughly trounces the hash functions recommended
 789    for this use at http://burtleburtle.net/bob/hash/index.html, both
 790    on speed and bucket distribution.  I haven't tried it against the
 791    function they just started using for Perl's hashes.  */
 792
 793 hashval_t
 794 htab_hash_string (const PTR p)
 795 {
 796   const unsigned char *str = (const unsigned char *) p;
 797   hashval_t r = 0;
 798   unsigned char c;
 799
 800   while ((c = *str++) != 0)
 801     r = r * 67 + c - 113;
 802
 803   return r;
 804 }
 805
 806 /* DERIVED FROM:
 807 --------------------------------------------------------------------
 808 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
 809 hash(), hash2(), hash3, and mix() are externally useful functions.
 810 Routines to test the hash are included if SELF_TEST is defined.
 811 You can use this free for any purpose.  It has no warranty.
 812 --------------------------------------------------------------------
 813 */
 814
 815 /*
 816 --------------------------------------------------------------------
 817 mix -- mix 3 32-bit values reversibly.
 818 For every delta with one or two bit set, and the deltas of all three
 819   high bits or all three low bits, whether the original value of a,b,c
 820   is almost all zero or is uniformly distributed,
 821 * If mix() is run forward or backward, at least 32 bits in a,b,c
 822   have at least 1/4 probability of changing.
 823 * If mix() is run forward, every bit of c will change between 1/3 and
 824   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 825 mix() was built out of 36 single-cycle latency instructions in a
 826   structure that could supported 2x parallelism, like so:
 827       a -= b;
 828       a -= c; x = (c>>13);
 829       b -= c; a ^= x;
 830       b -= a; x = (a<<8);
 831       c -= a; b ^= x;
 832       c -= b; x = (b>>13);
 833       ...
 834   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 835   of that parallelism.  They've also turned some of those single-cycle
 836   latency instructions into multi-cycle latency instructions.  Still,
 837   this is the fastest good hash I could find.  There were about 2^^68
 838   to choose from.  I only looked at a billion or so.
 839 --------------------------------------------------------------------
 840 */
 841 /* same, but slower, works on systems that might have 8 byte hashval_t's */
 842 #define mix(a,b,c) \
 843 { \
 844   a -= b; a -= c; a ^= (c>>13); \
 845   b -= c; b -= a; b ^= (a<< 8); \
 846   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 847   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 848   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 849   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 850   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 851   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 852   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 853 }
 854
 855 /*
 856 --------------------------------------------------------------------
 857 hash() -- hash a variable-length key into a 32-bit value
 858   k     : the key (the unaligned variable-length array of bytes)
 859   len   : the length of the key, counting by bytes
 860   level : can be any 4-byte value
 861 Returns a 32-bit value.  Every bit of the key affects every bit of
 862 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 863 About 36+6len instructions.
 864
 865 The best hash table sizes are powers of 2.  There is no need to do
 866 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 867 use a bitmask.  For example, if you need only 10 bits, do
 868   h = (h & hashmask(10));
 869 In which case, the hash table should have hashsize(10) elements.
 870
 871 If you are hashing n strings (ub1 **)k, do it like this:
 872   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 873
 874 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 875 code any way you wish, private, educational, or commercial.  It's free.
 876
 877 See http://burtleburtle.net/bob/hash/evahash.html
 878 Use for hash table lookup, or anything where one collision in 2^32 is
 879 acceptable.  Do NOT use for cryptographic purposes.
 880 --------------------------------------------------------------------
 881 */
 882
 883 hashval_t
 884 iterative_hash (const PTR k_in /* the key */,
 885                 register size_t  length /* the length of the key */,
 886                 register hashval_t initval /* the previous hash, or
 887                                               an arbitrary value */)
 888 {
 889   register const unsigned char *k = (const unsigned char *)k_in;
 890   register hashval_t a,b,c,len;
 891
 892   /* Set up the internal state */
 893   len = length;
 894   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 895   c = initval;           /* the previous hash value */
 896
 897   /*---------------------------------------- handle most of the key */
 898 #ifndef WORDS_BIGENDIAN
 899   /* On a little-endian machine, if the data is 4-byte aligned we can hash
 900      by word for better speed.  This gives nondeterministic results on
 901      big-endian machines.  */
 902   if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
 903     while (len >= 12)    /* aligned */
 904       {
 905         a += *(hashval_t *)(k+0);
 906         b += *(hashval_t *)(k+4);
 907         c += *(hashval_t *)(k+8);
 908         mix(a,b,c);
 909         k += 12; len -= 12;
 910       }
 911   else /* unaligned */
 912 #endif
 913     while (len >= 12)
 914       {
 915         a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
 916         b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
 917         c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
 918         mix(a,b,c);
 919         k += 12; len -= 12;
 920       }
 921
 922   /*------------------------------------- handle the last 11 bytes */
 923   c += length;
 924   switch(len)              /* all the case statements fall through */
 925     {
 926     case 11: c+=((hashval_t)k[10]<<24);
 927     case 10: c+=((hashval_t)k[9]<<16);
 928     case 9 : c+=((hashval_t)k[8]<<8);
 929       /* the first byte of c is reserved for the length */
 930     case 8 : b+=((hashval_t)k[7]<<24);
 931     case 7 : b+=((hashval_t)k[6]<<16);
 932     case 6 : b+=((hashval_t)k[5]<<8);
 933     case 5 : b+=k[4];
 934     case 4 : a+=((hashval_t)k[3]<<24);
 935     case 3 : a+=((hashval_t)k[2]<<16);
 936     case 2 : a+=((hashval_t)k[1]<<8);
 937     case 1 : a+=k[0];
 938       /* case 0: nothing left to add */
 939     }
 940   mix(a,b,c);
 941   /*-------------------------------------------- report the result */
 942   return c;
 943 }