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., 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, 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 PARAMS ((unsigned long));
  77 static hashval_t htab_mod_1 PARAMS ((hashval_t, hashval_t, hashval_t, int));
  78 static hashval_t htab_mod PARAMS ((hashval_t, htab_t));
  79 static hashval_t htab_mod_m2 PARAMS ((hashval_t, htab_t));
  80 static hashval_t hash_pointer PARAMS ((const void *));
  81 static int eq_pointer PARAMS ((const void *, const void *));
  82 static int htab_expand PARAMS ((htab_t));
  83 static PTR *find_empty_slot_for_expand  PARAMS ((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 (n)
 180      unsigned long n;
 181 {
 182   unsigned int low = 0;
 183   unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
 184
 185   while (low != high)
 186     {
 187       unsigned int mid = low + (high - low) / 2;
 188       if (n > prime_tab[mid].prime)
 189         low = mid + 1;
 190       else
 191         high = mid;
 192     }
 193
 194   /* If we've run out of primes, abort.  */
 195   if (n > prime_tab[low].prime)
 196     {
 197       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 198       abort ();
 199     }
 200
 201   return low;
 202 }
 203
 204 /* Returns a hash code for P.  */
 205
 206 static hashval_t
 207 hash_pointer (p)
 208      const PTR p;
 209 {
 210   return (hashval_t) ((long)p >> 3);
 211 }
 212
 213 /* Returns non-zero if P1 and P2 are equal.  */
 214
 215 static int
 216 eq_pointer (p1, p2)
 217      const PTR p1;
 218      const PTR p2;
 219 {
 220   return p1 == p2;
 221 }
 222
 223 /* Return the current size of given hash table. */
 224
 225 inline size_t
 226 htab_size (htab)
 227      htab_t htab;
 228 {
 229   return htab->size;
 230 }
 231
 232 /* Return the current number of elements in given hash table. */
 233
 234 inline size_t
 235 htab_elements (htab)
 236      htab_t htab;
 237 {
 238   return htab->n_elements - htab->n_deleted;
 239 }
 240
 241 /* Return X % Y.  */
 242
 243 static inline hashval_t
 244 htab_mod_1 (x, y, inv, shift)
 245      hashval_t x, y, inv;
 246      int shift;
 247 {
 248   /* The multiplicative inverses computed above are for 32-bit types, and
 249      requires that we be able to compute a highpart multiply.  */
 250 #ifdef UNSIGNED_64BIT_TYPE
 251   __extension__ typedef UNSIGNED_64BIT_TYPE ull;
 252   if (sizeof (hashval_t) * CHAR_BIT <= 32)
 253     {
 254       hashval_t t1, t2, t3, t4, q, r;
 255
 256       t1 = ((ull)x * inv) >> 32;
 257       t2 = x - t1;
 258       t3 = t2 >> 1;
 259       t4 = t1 + t3;
 260       q  = t4 >> shift;
 261       r  = x - (q * y);
 262
 263       return r;
 264     }
 265 #endif
 266
 267   /* Otherwise just use the native division routines.  */
 268   return x % y;
 269 }
 270
 271 /* Compute the primary hash for HASH given HTAB's current size.  */
 272
 273 static inline hashval_t
 274 htab_mod (hash, htab)
 275      hashval_t hash;
 276      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 (hash, htab)
 286      hashval_t hash;
 287      htab_t htab;
 288 {
 289   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
 290   return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
 291 }
 292
 293 /* This function creates table with length slightly longer than given
 294    source length.  Created hash table is initiated as empty (all the
 295    hash table entries are EMPTY_ENTRY).  The function returns the
 296    created hash table, or NULL if memory allocation fails.  */
 297
 298 htab_t
 299 htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
 300      size_t size;
 301      htab_hash hash_f;
 302      htab_eq eq_f;
 303      htab_del del_f;
 304      htab_alloc alloc_f;
 305      htab_free free_f;
 306 {
 307   htab_t result;
 308   unsigned int size_prime_index;
 309
 310   size_prime_index = higher_prime_index (size);
 311   size = prime_tab[size_prime_index].prime;
 312
 313   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
 314   if (result == NULL)
 315     return NULL;
 316   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 317   if (result->entries == NULL)
 318     {
 319       if (free_f != NULL)
 320         (*free_f) (result);
 321       return NULL;
 322     }
 323   result->size = size;
 324   result->size_prime_index = size_prime_index;
 325   result->hash_f = hash_f;
 326   result->eq_f = eq_f;
 327   result->del_f = del_f;
 328   result->alloc_f = alloc_f;
 329   result->free_f = free_f;
 330   return result;
 331 }
 332
 333 /* As above, but use the variants of alloc_f and free_f which accept
 334    an extra argument.  */
 335
 336 htab_t
 337 htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f,
 338                       free_f)
 339      size_t size;
 340      htab_hash hash_f;
 341      htab_eq eq_f;
 342      htab_del del_f;
 343      PTR alloc_arg;
 344      htab_alloc_with_arg alloc_f;
 345      htab_free_with_arg free_f;
 346 {
 347   htab_t result;
 348   unsigned int size_prime_index;
 349
 350   size_prime_index = higher_prime_index (size);
 351   size = prime_tab[size_prime_index].prime;
 352
 353   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 354   if (result == NULL)
 355     return NULL;
 356   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 357   if (result->entries == NULL)
 358     {
 359       if (free_f != NULL)
 360         (*free_f) (alloc_arg, result);
 361       return NULL;
 362     }
 363   result->size = size;
 364   result->size_prime_index = size_prime_index;
 365   result->hash_f = hash_f;
 366   result->eq_f = eq_f;
 367   result->del_f = del_f;
 368   result->alloc_arg = alloc_arg;
 369   result->alloc_with_arg_f = alloc_f;
 370   result->free_with_arg_f = free_f;
 371   return result;
 372 }
 373
 374 /* Update the function pointers and allocation parameter in the htab_t.  */
 375
 376 void
 377 htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f)
 378      htab_t htab;
 379      htab_hash hash_f;
 380      htab_eq eq_f;
 381      htab_del del_f;
 382      PTR alloc_arg;
 383      htab_alloc_with_arg alloc_f;
 384      htab_free_with_arg free_f;
 385 {
 386   htab->hash_f = hash_f;
 387   htab->eq_f = eq_f;
 388   htab->del_f = del_f;
 389   htab->alloc_arg = alloc_arg;
 390   htab->alloc_with_arg_f = alloc_f;
 391   htab->free_with_arg_f = free_f;
 392 }
 393
 394 /* These functions exist solely for backward compatibility.  */
 395
 396 #undef htab_create
 397 htab_t
 398 htab_create (size, hash_f, eq_f, del_f)
 399      size_t size;
 400      htab_hash hash_f;
 401      htab_eq eq_f;
 402      htab_del del_f;
 403 {
 404   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 405 }
 406
 407 htab_t
 408 htab_try_create (size, hash_f, eq_f, del_f)
 409      size_t size;
 410      htab_hash hash_f;
 411      htab_eq eq_f;
 412      htab_del del_f;
 413 {
 414   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 415 }
 416
 417 /* This function frees all memory allocated for given hash table.
 418    Naturally the hash table must already exist. */
 419
 420 void
 421 htab_delete (htab)
 422      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   if (htab->free_f != NULL)
 434     {
 435       (*htab->free_f) (entries);
 436       (*htab->free_f) (htab);
 437     }
 438   else if (htab->free_with_arg_f != NULL)
 439     {
 440       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
 441       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 442     }
 443 }
 444
 445 /* This function clears all entries in the given hash table.  */
 446
 447 void
 448 htab_empty (htab)
 449      htab_t htab;
 450 {
 451   size_t size = htab_size (htab);
 452   PTR *entries = htab->entries;
 453   int i;
 454
 455   if (htab->del_f)
 456     for (i = size - 1; i >= 0; i--)
 457       if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
 458         (*htab->del_f) (entries[i]);
 459
 460   memset (entries, 0, size * sizeof (PTR));
 461 }
 462
 463 /* Similar to htab_find_slot, but without several unwanted side effects:
 464     - Does not call htab->eq_f when it finds an existing entry.
 465     - Does not change the count of elements/searches/collisions in the
 466       hash table.
 467    This function also assumes there are no deleted entries in the table.
 468    HASH is the hash value for the element to be inserted.  */
 469
 470 static PTR *
 471 find_empty_slot_for_expand (htab, hash)
 472      htab_t htab;
 473      hashval_t hash;
 474 {
 475   hashval_t index = htab_mod (hash, htab);
 476   size_t size = htab_size (htab);
 477   PTR *slot = htab->entries + index;
 478   hashval_t hash2;
 479
 480   if (*slot == EMPTY_ENTRY)
 481     return slot;
 482   else if (*slot == DELETED_ENTRY)
 483     abort ();
 484
 485   hash2 = htab_mod_m2 (hash, htab);
 486   for (;;)
 487     {
 488       index += hash2;
 489       if (index >= size)
 490         index -= size;
 491
 492       slot = htab->entries + index;
 493       if (*slot == EMPTY_ENTRY)
 494         return slot;
 495       else if (*slot == DELETED_ENTRY)
 496         abort ();
 497     }
 498 }
 499
 500 /* The following function changes size of memory allocated for the
 501    entries and repeatedly inserts the table elements.  The occupancy
 502    of the table after the call will be about 50%.  Naturally the hash
 503    table must already exist.  Remember also that the place of the
 504    table entries is changed.  If memory allocation failures are allowed,
 505    this function will return zero, indicating that the table could not be
 506    expanded.  If all goes well, it will return a non-zero value.  */
 507
 508 static int
 509 htab_expand (htab)
 510      htab_t htab;
 511 {
 512   PTR *oentries;
 513   PTR *olimit;
 514   PTR *p;
 515   PTR *nentries;
 516   size_t nsize, osize, elts;
 517   unsigned int oindex, nindex;
 518
 519   oentries = htab->entries;
 520   oindex = htab->size_prime_index;
 521   osize = htab->size;
 522   olimit = oentries + osize;
 523   elts = htab_elements (htab);
 524
 525   /* Resize only when table after removal of unused elements is either
 526      too full or too empty.  */
 527   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 528     {
 529       nindex = higher_prime_index (elts * 2);
 530       nsize = prime_tab[nindex].prime;
 531     }
 532   else
 533     {
 534       nindex = oindex;
 535       nsize = osize;
 536     }
 537
 538   if (htab->alloc_with_arg_f != NULL)
 539     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 540                                                   sizeof (PTR *));
 541   else
 542     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 543   if (nentries == NULL)
 544     return 0;
 545   htab->entries = nentries;
 546   htab->size = nsize;
 547   htab->size_prime_index = nindex;
 548   htab->n_elements -= htab->n_deleted;
 549   htab->n_deleted = 0;
 550
 551   p = oentries;
 552   do
 553     {
 554       PTR x = *p;
 555
 556       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 557         {
 558           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 559
 560           *q = x;
 561         }
 562
 563       p++;
 564     }
 565   while (p < olimit);
 566
 567   if (htab->free_f != NULL)
 568     (*htab->free_f) (oentries);
 569   else if (htab->free_with_arg_f != NULL)
 570     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 571   return 1;
 572 }
 573
 574 /* This function searches for a hash table entry equal to the given
 575    element.  It cannot be used to insert or delete an element.  */
 576
 577 PTR
 578 htab_find_with_hash (htab, element, hash)
 579      htab_t htab;
 580      const PTR element;
 581      hashval_t hash;
 582 {
 583   hashval_t index, hash2;
 584   size_t size;
 585   PTR entry;
 586
 587   htab->searches++;
 588   size = htab_size (htab);
 589   index = htab_mod (hash, htab);
 590
 591   entry = htab->entries[index];
 592   if (entry == EMPTY_ENTRY
 593       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 594     return entry;
 595
 596   hash2 = htab_mod_m2 (hash, htab);
 597   for (;;)
 598     {
 599       htab->collisions++;
 600       index += hash2;
 601       if (index >= size)
 602         index -= size;
 603
 604       entry = htab->entries[index];
 605       if (entry == EMPTY_ENTRY
 606           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 607         return entry;
 608     }
 609 }
 610
 611 /* Like htab_find_slot_with_hash, but compute the hash value from the
 612    element.  */
 613
 614 PTR
 615 htab_find (htab, element)
 616      htab_t htab;
 617      const PTR element;
 618 {
 619   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 620 }
 621
 622 /* This function searches for a hash table slot containing an entry
 623    equal to the given element.  To delete an entry, call this with
 624    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 625    after doing some checks).  To insert an entry, call this with
 626    INSERT = 1, then write the value you want into the returned slot.
 627    When inserting an entry, NULL may be returned if memory allocation
 628    fails.  */
 629
 630 PTR *
 631 htab_find_slot_with_hash (htab, element, hash, insert)
 632      htab_t htab;
 633      const PTR element;
 634      hashval_t hash;
 635      enum insert_option insert;
 636 {
 637   PTR *first_deleted_slot;
 638   hashval_t index, hash2;
 639   size_t size;
 640   PTR entry;
 641
 642   size = htab_size (htab);
 643   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 644     {
 645       if (htab_expand (htab) == 0)
 646         return NULL;
 647       size = htab_size (htab);
 648     }
 649
 650   index = htab_mod (hash, htab);
 651
 652   htab->searches++;
 653   first_deleted_slot = NULL;
 654
 655   entry = htab->entries[index];
 656   if (entry == EMPTY_ENTRY)
 657     goto empty_entry;
 658   else if (entry == DELETED_ENTRY)
 659     first_deleted_slot = &htab->entries[index];
 660   else if ((*htab->eq_f) (entry, element))
 661     return &htab->entries[index];
 662
 663   hash2 = htab_mod_m2 (hash, htab);
 664   for (;;)
 665     {
 666       htab->collisions++;
 667       index += hash2;
 668       if (index >= size)
 669         index -= size;
 670
 671       entry = htab->entries[index];
 672       if (entry == EMPTY_ENTRY)
 673         goto empty_entry;
 674       else if (entry == DELETED_ENTRY)
 675         {
 676           if (!first_deleted_slot)
 677             first_deleted_slot = &htab->entries[index];
 678         }
 679       else if ((*htab->eq_f) (entry, element))
 680         return &htab->entries[index];
 681     }
 682
 683  empty_entry:
 684   if (insert == NO_INSERT)
 685     return NULL;
 686
 687   if (first_deleted_slot)
 688     {
 689       htab->n_deleted--;
 690       *first_deleted_slot = EMPTY_ENTRY;
 691       return first_deleted_slot;
 692     }
 693
 694   htab->n_elements++;
 695   return &htab->entries[index];
 696 }
 697
 698 /* Like htab_find_slot_with_hash, but compute the hash value from the
 699    element.  */
 700
 701 PTR *
 702 htab_find_slot (htab, element, insert)
 703      htab_t htab;
 704      const PTR element;
 705      enum insert_option insert;
 706 {
 707   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 708                                    insert);
 709 }
 710
 711 /* This function deletes an element with the given value from hash
 712    table (the hash is computed from the element).  If there is no matching
 713    element in the hash table, this function does nothing.  */
 714
 715 void
 716 htab_remove_elt (htab, element)
 717      htab_t htab;
 718      PTR element;
 719 {
 720   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
 721 }
 722
 723
 724 /* This function deletes an element with the given value from hash
 725    table.  If there is no matching element in the hash table, this
 726    function does nothing.  */
 727
 728 void
 729 htab_remove_elt_with_hash (htab, element, hash)
 730      htab_t htab;
 731      PTR element;
 732      hashval_t hash;
 733 {
 734   PTR *slot;
 735
 736   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
 737   if (*slot == EMPTY_ENTRY)
 738     return;
 739
 740   if (htab->del_f)
 741     (*htab->del_f) (*slot);
 742
 743   *slot = DELETED_ENTRY;
 744   htab->n_deleted++;
 745 }
 746
 747 /* This function clears a specified slot in a hash table.  It is
 748    useful when you've already done the lookup and don't want to do it
 749    again.  */
 750
 751 void
 752 htab_clear_slot (htab, slot)
 753      htab_t htab;
 754      PTR *slot;
 755 {
 756   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
 757       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 758     abort ();
 759
 760   if (htab->del_f)
 761     (*htab->del_f) (*slot);
 762
 763   *slot = DELETED_ENTRY;
 764   htab->n_deleted++;
 765 }
 766
 767 /* This function scans over the entire hash table calling
 768    CALLBACK for each live entry.  If CALLBACK returns false,
 769    the iteration stops.  INFO is passed as CALLBACK's second
 770    argument.  */
 771
 772 void
 773 htab_traverse_noresize (htab, callback, info)
 774      htab_t htab;
 775      htab_trav callback;
 776      PTR info;
 777 {
 778   PTR *slot;
 779   PTR *limit;
 780
 781   slot = htab->entries;
 782   limit = slot + htab_size (htab);
 783
 784   do
 785     {
 786       PTR x = *slot;
 787
 788       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 789         if (!(*callback) (slot, info))
 790           break;
 791     }
 792   while (++slot < limit);
 793 }
 794
 795 /* Like htab_traverse_noresize, but does resize the table when it is
 796    too empty to improve effectivity of subsequent calls.  */
 797
 798 void
 799 htab_traverse (htab, callback, info)
 800      htab_t htab;
 801      htab_trav callback;
 802      PTR info;
 803 {
 804   if (htab_elements (htab) * 8 < htab_size (htab))
 805     htab_expand (htab);
 806
 807   htab_traverse_noresize (htab, callback, info);
 808 }
 809
 810 /* Return the fraction of fixed collisions during all work with given
 811    hash table. */
 812
 813 double
 814 htab_collisions (htab)
 815      htab_t htab;
 816 {
 817   if (htab->searches == 0)
 818     return 0.0;
 819
 820   return (double) htab->collisions / (double) htab->searches;
 821 }
 822
 823 /* Hash P as a null-terminated string.
 824
 825    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 826    to applicability, though note that unlike hashtable.c, this hash table
 827    implementation re-hashes rather than chain buckets.
 828
 829    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 830    From: Zack Weinberg <zackw@panix.com>
 831    Date: Fri, 17 Aug 2001 02:15:56 -0400
 832
 833    I got it by extracting all the identifiers from all the source code
 834    I had lying around in mid-1999, and testing many recurrences of
 835    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 836    prime numbers or the appropriate identity.  This was the best one.
 837    I don't remember exactly what constituted "best", except I was
 838    looking at bucket-length distributions mostly.
 839
 840    So it should be very good at hashing identifiers, but might not be
 841    as good at arbitrary strings.
 842
 843    I'll add that it thoroughly trounces the hash functions recommended
 844    for this use at http://burtleburtle.net/bob/hash/index.html, both
 845    on speed and bucket distribution.  I haven't tried it against the
 846    function they just started using for Perl's hashes.  */
 847
 848 hashval_t
 849 htab_hash_string (p)
 850      const PTR p;
 851 {
 852   const unsigned char *str = (const unsigned char *) p;
 853   hashval_t r = 0;
 854   unsigned char c;
 855
 856   while ((c = *str++) != 0)
 857     r = r * 67 + c - 113;
 858
 859   return r;
 860 }
 861
 862 /* DERIVED FROM:
 863 --------------------------------------------------------------------
 864 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
 865 hash(), hash2(), hash3, and mix() are externally useful functions.
 866 Routines to test the hash are included if SELF_TEST is defined.
 867 You can use this free for any purpose.  It has no warranty.
 868 --------------------------------------------------------------------
 869 */
 870
 871 /*
 872 --------------------------------------------------------------------
 873 mix -- mix 3 32-bit values reversibly.
 874 For every delta with one or two bit set, and the deltas of all three
 875   high bits or all three low bits, whether the original value of a,b,c
 876   is almost all zero or is uniformly distributed,
 877 * If mix() is run forward or backward, at least 32 bits in a,b,c
 878   have at least 1/4 probability of changing.
 879 * If mix() is run forward, every bit of c will change between 1/3 and
 880   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 881 mix() was built out of 36 single-cycle latency instructions in a
 882   structure that could supported 2x parallelism, like so:
 883       a -= b;
 884       a -= c; x = (c>>13);
 885       b -= c; a ^= x;
 886       b -= a; x = (a<<8);
 887       c -= a; b ^= x;
 888       c -= b; x = (b>>13);
 889       ...
 890   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 891   of that parallelism.  They've also turned some of those single-cycle
 892   latency instructions into multi-cycle latency instructions.  Still,
 893   this is the fastest good hash I could find.  There were about 2^^68
 894   to choose from.  I only looked at a billion or so.
 895 --------------------------------------------------------------------
 896 */
 897 /* same, but slower, works on systems that might have 8 byte hashval_t's */
 898 #define mix(a,b,c) \
 899 { \
 900   a -= b; a -= c; a ^= (c>>13); \
 901   b -= c; b -= a; b ^= (a<< 8); \
 902   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 903   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 904   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 905   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 906   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 907   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 908   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 909 }
 910
 911 /*
 912 --------------------------------------------------------------------
 913 hash() -- hash a variable-length key into a 32-bit value
 914   k     : the key (the unaligned variable-length array of bytes)
 915   len   : the length of the key, counting by bytes
 916   level : can be any 4-byte value
 917 Returns a 32-bit value.  Every bit of the key affects every bit of
 918 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 919 About 36+6len instructions.
 920
 921 The best hash table sizes are powers of 2.  There is no need to do
 922 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 923 use a bitmask.  For example, if you need only 10 bits, do
 924   h = (h & hashmask(10));
 925 In which case, the hash table should have hashsize(10) elements.
 926
 927 If you are hashing n strings (ub1 **)k, do it like this:
 928   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 929
 930 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 931 code any way you wish, private, educational, or commercial.  It's free.
 932
 933 See http://burtleburtle.net/bob/hash/evahash.html
 934 Use for hash table lookup, or anything where one collision in 2^32 is
 935 acceptable.  Do NOT use for cryptographic purposes.
 936 --------------------------------------------------------------------
 937 */
 938
 939 hashval_t iterative_hash (k_in, length, initval)
 940      const PTR k_in;               /* the key */
 941      register size_t  length;      /* the length of the key */
 942      register hashval_t  initval;  /* the previous hash, or an arbitrary value */
 943 {
 944   register const unsigned char *k = (const unsigned char *)k_in;
 945   register hashval_t a,b,c,len;
 946
 947   /* Set up the internal state */
 948   len = length;
 949   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 950   c = initval;           /* the previous hash value */
 951
 952   /*---------------------------------------- handle most of the key */
 953 #ifndef WORDS_BIGENDIAN
 954   /* On a little-endian machine, if the data is 4-byte aligned we can hash
 955      by word for better speed.  This gives nondeterministic results on
 956      big-endian machines.  */
 957   if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
 958     while (len >= 12)    /* aligned */
 959       {
 960         a += *(hashval_t *)(k+0);
 961         b += *(hashval_t *)(k+4);
 962         c += *(hashval_t *)(k+8);
 963         mix(a,b,c);
 964         k += 12; len -= 12;
 965       }
 966   else /* unaligned */
 967 #endif
 968     while (len >= 12)
 969       {
 970         a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
 971         b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
 972         c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
 973         mix(a,b,c);
 974         k += 12; len -= 12;
 975       }
 976
 977   /*------------------------------------- handle the last 11 bytes */
 978   c += length;
 979   switch(len)              /* all the case statements fall through */
 980     {
 981     case 11: c+=((hashval_t)k[10]<<24);
 982     case 10: c+=((hashval_t)k[9]<<16);
 983     case 9 : c+=((hashval_t)k[8]<<8);
 984       /* the first byte of c is reserved for the length */
 985     case 8 : b+=((hashval_t)k[7]<<24);
 986     case 7 : b+=((hashval_t)k[6]<<16);
 987     case 6 : b+=((hashval_t)k[5]<<8);
 988     case 5 : b+=k[4];
 989     case 4 : a+=((hashval_t)k[3]<<24);
 990     case 3 : a+=((hashval_t)k[2]<<16);
 991     case 2 : a+=((hashval_t)k[1]<<8);
 992     case 1 : a+=k[0];
 993       /* case 0: nothing left to add */
 994     }
 995   mix(a,b,c);
 996   /*-------------------------------------------- report the result */
 997   return c;
 998 }