libiberty/hashtab.c

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