libiberty/hashtab.c

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