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 #include <stdio.h>
  49
  50 #include "libiberty.h"
  51 #include "hashtab.h"
  52
  53 /* This macro defines reserved value for empty table entry. */
  54
  55 #define EMPTY_ENTRY    ((PTR) 0)
  56
  57 /* This macro defines reserved value for table entry which contained
  58    a deleted element. */
  59
  60 #define DELETED_ENTRY  ((PTR) 1)
  61
  62 static unsigned long higher_prime_number PARAMS ((unsigned long));
  63 static hashval_t hash_pointer PARAMS ((const void *));
  64 static int eq_pointer PARAMS ((const void *, const void *));
  65 static int htab_expand PARAMS ((htab_t));
  66 static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
  67
  68 /* At some point, we could make these be NULL, and modify the
  69    hash-table routines to handle NULL specially; that would avoid
  70    function-call overhead for the common case of hashing pointers.  */
  71 htab_hash htab_hash_pointer = hash_pointer;
  72 htab_eq htab_eq_pointer = eq_pointer;
  73
  74 /* The following function returns a nearest prime number which is
  75    greater than N, and near a power of two. */
  76
  77 static unsigned long
  78 higher_prime_number (n)
  79      unsigned long n;
  80 {
  81   /* These are primes that are near, but slightly smaller than, a
  82      power of two.  */
  83   static const unsigned long primes[] = {
  84     (unsigned long) 7,
  85     (unsigned long) 13,
  86     (unsigned long) 31,
  87     (unsigned long) 61,
  88     (unsigned long) 127,
  89     (unsigned long) 251,
  90     (unsigned long) 509,
  91     (unsigned long) 1021,
  92     (unsigned long) 2039,
  93     (unsigned long) 4093,
  94     (unsigned long) 8191,
  95     (unsigned long) 16381,
  96     (unsigned long) 32749,
  97     (unsigned long) 65521,
  98     (unsigned long) 131071,
  99     (unsigned long) 262139,
 100     (unsigned long) 524287,
 101     (unsigned long) 1048573,
 102     (unsigned long) 2097143,
 103     (unsigned long) 4194301,
 104     (unsigned long) 8388593,
 105     (unsigned long) 16777213,
 106     (unsigned long) 33554393,
 107     (unsigned long) 67108859,
 108     (unsigned long) 134217689,
 109     (unsigned long) 268435399,
 110     (unsigned long) 536870909,
 111     (unsigned long) 1073741789,
 112     (unsigned long) 2147483647,
 113                                         /* 4294967291L */
 114     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
 115   };
 116
 117   const unsigned long *low = &primes[0];
 118   const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
 119
 120   while (low != high)
 121     {
 122       const unsigned long *mid = low + (high - low) / 2;
 123       if (n > *mid)
 124         low = mid + 1;
 125       else
 126         high = mid;
 127     }
 128
 129   /* If we've run out of primes, abort.  */
 130   if (n > *low)
 131     {
 132       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 133       abort ();
 134     }
 135
 136   return *low;
 137 }
 138
 139 /* Returns a hash code for P.  */
 140
 141 static hashval_t
 142 hash_pointer (p)
 143      const PTR p;
 144 {
 145   return (hashval_t) ((long)p >> 3);
 146 }
 147
 148 /* Returns non-zero if P1 and P2 are equal.  */
 149
 150 static int
 151 eq_pointer (p1, p2)
 152      const PTR p1;
 153      const PTR p2;
 154 {
 155   return p1 == p2;
 156 }
 157
 158 /* This function creates table with length slightly longer than given
 159    source length.  Created hash table is initiated as empty (all the
 160    hash table entries are EMPTY_ENTRY).  The function returns the
 161    created hash table, or NULL if memory allocation fails.  */
 162
 163 htab_t
 164 htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
 165      size_t size;
 166      htab_hash hash_f;
 167      htab_eq eq_f;
 168      htab_del del_f;
 169      htab_alloc alloc_f;
 170      htab_free free_f;
 171 {
 172   htab_t result;
 173
 174   size = higher_prime_number (size);
 175   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
 176   if (result == NULL)
 177     return NULL;
 178   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 179   if (result->entries == NULL)
 180     {
 181       if (free_f != NULL)
 182         (*free_f) (result);
 183       return NULL;
 184     }
 185   result->size = size;
 186   result->hash_f = hash_f;
 187   result->eq_f = eq_f;
 188   result->del_f = del_f;
 189   result->alloc_f = alloc_f;
 190   result->free_f = free_f;
 191   return result;
 192 }
 193
 194 /* As above, but use the variants of alloc_f and free_f which accept
 195    an extra argument.  */
 196
 197 htab_t
 198 htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f,
 199                       free_f)
 200      size_t size;
 201      htab_hash hash_f;
 202      htab_eq eq_f;
 203      htab_del del_f;
 204      PTR alloc_arg;
 205      htab_alloc_with_arg alloc_f;
 206      htab_free_with_arg free_f;
 207 {
 208   htab_t result;
 209
 210   size = higher_prime_number (size);
 211   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 212   if (result == NULL)
 213     return NULL;
 214   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 215   if (result->entries == NULL)
 216     {
 217       if (free_f != NULL)
 218         (*free_f) (alloc_arg, result);
 219       return NULL;
 220     }
 221   result->size = size;
 222   result->hash_f = hash_f;
 223   result->eq_f = eq_f;
 224   result->del_f = del_f;
 225   result->alloc_arg = alloc_arg;
 226   result->alloc_with_arg_f = alloc_f;
 227   result->free_with_arg_f = free_f;
 228   return result;
 229 }
 230
 231 /* Update the function pointers and allocation parameter in the htab_t.  */
 232
 233 void
 234 htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f)
 235      htab_t htab;
 236      htab_hash hash_f;
 237      htab_eq eq_f;
 238      htab_del del_f;
 239      PTR alloc_arg;
 240      htab_alloc_with_arg alloc_f;
 241      htab_free_with_arg free_f;
 242 {
 243   htab->hash_f = hash_f;
 244   htab->eq_f = eq_f;
 245   htab->del_f = del_f;
 246   htab->alloc_arg = alloc_arg;
 247   htab->alloc_with_arg_f = alloc_f;
 248   htab->free_with_arg_f = free_f;
 249 }
 250
 251 /* These functions exist solely for backward compatibility.  */
 252
 253 #undef htab_create
 254 htab_t
 255 htab_create (size, hash_f, eq_f, del_f)
 256      size_t size;
 257      htab_hash hash_f;
 258      htab_eq eq_f;
 259      htab_del del_f;
 260 {
 261   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 262 }
 263
 264 htab_t
 265 htab_try_create (size, hash_f, eq_f, del_f)
 266      size_t size;
 267      htab_hash hash_f;
 268      htab_eq eq_f;
 269      htab_del del_f;
 270 {
 271   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 272 }
 273
 274 /* This function frees all memory allocated for given hash table.
 275    Naturally the hash table must already exist. */
 276
 277 void
 278 htab_delete (htab)
 279      htab_t htab;
 280 {
 281   int i;
 282
 283   if (htab->del_f)
 284     for (i = htab->size - 1; i >= 0; i--)
 285       if (htab->entries[i] != EMPTY_ENTRY
 286           && htab->entries[i] != DELETED_ENTRY)
 287         (*htab->del_f) (htab->entries[i]);
 288
 289   if (htab->free_f != NULL)
 290     {
 291       (*htab->free_f) (htab->entries);
 292       (*htab->free_f) (htab);
 293     }
 294   else if (htab->free_with_arg_f != NULL)
 295     {
 296       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
 297       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 298     }
 299 }
 300
 301 /* This function clears all entries in the given hash table.  */
 302
 303 void
 304 htab_empty (htab)
 305      htab_t htab;
 306 {
 307   int i;
 308
 309   if (htab->del_f)
 310     for (i = htab->size - 1; i >= 0; i--)
 311       if (htab->entries[i] != EMPTY_ENTRY
 312           && htab->entries[i] != DELETED_ENTRY)
 313         (*htab->del_f) (htab->entries[i]);
 314
 315   memset (htab->entries, 0, htab->size * sizeof (PTR));
 316 }
 317
 318 /* Similar to htab_find_slot, but without several unwanted side effects:
 319     - Does not call htab->eq_f when it finds an existing entry.
 320     - Does not change the count of elements/searches/collisions in the
 321       hash table.
 322    This function also assumes there are no deleted entries in the table.
 323    HASH is the hash value for the element to be inserted.  */
 324
 325 static PTR *
 326 find_empty_slot_for_expand (htab, hash)
 327      htab_t htab;
 328      hashval_t hash;
 329 {
 330   size_t size = htab->size;
 331   unsigned int index = hash % size;
 332   PTR *slot = htab->entries + index;
 333   hashval_t hash2;
 334
 335   if (*slot == EMPTY_ENTRY)
 336     return slot;
 337   else if (*slot == DELETED_ENTRY)
 338     abort ();
 339
 340   hash2 = 1 + hash % (size - 2);
 341   for (;;)
 342     {
 343       index += hash2;
 344       if (index >= size)
 345         index -= size;
 346
 347       slot = htab->entries + index;
 348       if (*slot == EMPTY_ENTRY)
 349         return slot;
 350       else if (*slot == DELETED_ENTRY)
 351         abort ();
 352     }
 353 }
 354
 355 /* The following function changes size of memory allocated for the
 356    entries and repeatedly inserts the table elements.  The occupancy
 357    of the table after the call will be about 50%.  Naturally the hash
 358    table must already exist.  Remember also that the place of the
 359    table entries is changed.  If memory allocation failures are allowed,
 360    this function will return zero, indicating that the table could not be
 361    expanded.  If all goes well, it will return a non-zero value.  */
 362
 363 static int
 364 htab_expand (htab)
 365      htab_t htab;
 366 {
 367   PTR *oentries;
 368   PTR *olimit;
 369   PTR *p;
 370   PTR *nentries;
 371   size_t nsize;
 372
 373   oentries = htab->entries;
 374   olimit = oentries + htab->size;
 375
 376   /* Resize only when table after removal of unused elements is either
 377      too full or too empty.  */
 378   if ((htab->n_elements - htab->n_deleted) * 2 > htab->size
 379       || ((htab->n_elements - htab->n_deleted) * 8 < htab->size
 380           && htab->size > 32))
 381     nsize = higher_prime_number ((htab->n_elements - htab->n_deleted) * 2);
 382   else
 383     nsize = htab->size;
 384
 385   if (htab->alloc_with_arg_f != NULL)
 386     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 387                                                   sizeof (PTR *));
 388   else
 389     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 390   if (nentries == NULL)
 391     return 0;
 392   htab->entries = nentries;
 393   htab->size = nsize;
 394
 395   htab->n_elements -= htab->n_deleted;
 396   htab->n_deleted = 0;
 397
 398   p = oentries;
 399   do
 400     {
 401       PTR x = *p;
 402
 403       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 404         {
 405           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 406
 407           *q = x;
 408         }
 409
 410       p++;
 411     }
 412   while (p < olimit);
 413
 414   if (htab->free_f != NULL)
 415     (*htab->free_f) (oentries);
 416   else if (htab->free_with_arg_f != NULL)
 417     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 418   return 1;
 419 }
 420
 421 /* This function searches for a hash table entry equal to the given
 422    element.  It cannot be used to insert or delete an element.  */
 423
 424 PTR
 425 htab_find_with_hash (htab, element, hash)
 426      htab_t htab;
 427      const PTR element;
 428      hashval_t hash;
 429 {
 430   unsigned int index;
 431   hashval_t hash2;
 432   size_t size;
 433   PTR entry;
 434
 435   htab->searches++;
 436   size = htab->size;
 437   index = hash % size;
 438
 439   entry = htab->entries[index];
 440   if (entry == EMPTY_ENTRY
 441       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 442     return entry;
 443
 444   hash2 = 1 + hash % (size - 2);
 445
 446   for (;;)
 447     {
 448       htab->collisions++;
 449       index += hash2;
 450       if (index >= size)
 451         index -= size;
 452
 453       entry = htab->entries[index];
 454       if (entry == EMPTY_ENTRY
 455           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 456         return entry;
 457     }
 458 }
 459
 460 /* Like htab_find_slot_with_hash, but compute the hash value from the
 461    element.  */
 462
 463 PTR
 464 htab_find (htab, element)
 465      htab_t htab;
 466      const PTR element;
 467 {
 468   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 469 }
 470
 471 /* This function searches for a hash table slot containing an entry
 472    equal to the given element.  To delete an entry, call this with
 473    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 474    after doing some checks).  To insert an entry, call this with
 475    INSERT = 1, then write the value you want into the returned slot.
 476    When inserting an entry, NULL may be returned if memory allocation
 477    fails.  */
 478
 479 PTR *
 480 htab_find_slot_with_hash (htab, element, hash, insert)
 481      htab_t htab;
 482      const PTR element;
 483      hashval_t hash;
 484      enum insert_option insert;
 485 {
 486   PTR *first_deleted_slot;
 487   unsigned int index;
 488   hashval_t hash2;
 489   size_t size;
 490   PTR entry;
 491
 492   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 493       && htab_expand (htab) == 0)
 494     return NULL;
 495
 496   size = htab->size;
 497   index = hash % size;
 498
 499   htab->searches++;
 500   first_deleted_slot = NULL;
 501
 502   entry = htab->entries[index];
 503   if (entry == EMPTY_ENTRY)
 504     goto empty_entry;
 505   else if (entry == DELETED_ENTRY)
 506     first_deleted_slot = &htab->entries[index];
 507   else if ((*htab->eq_f) (entry, element))
 508     return &htab->entries[index];
 509
 510   hash2 = 1 + hash % (size - 2);
 511   for (;;)
 512     {
 513       htab->collisions++;
 514       index += hash2;
 515       if (index >= size)
 516         index -= size;
 517
 518       entry = htab->entries[index];
 519       if (entry == EMPTY_ENTRY)
 520         goto empty_entry;
 521       else if (entry == DELETED_ENTRY)
 522         {
 523           if (!first_deleted_slot)
 524             first_deleted_slot = &htab->entries[index];
 525         }
 526       else if ((*htab->eq_f) (entry, element))
 527         return &htab->entries[index];
 528     }
 529
 530  empty_entry:
 531   if (insert == NO_INSERT)
 532     return NULL;
 533
 534   htab->n_elements++;
 535
 536   if (first_deleted_slot)
 537     {
 538       *first_deleted_slot = EMPTY_ENTRY;
 539       return first_deleted_slot;
 540     }
 541
 542   return &htab->entries[index];
 543 }
 544
 545 /* Like htab_find_slot_with_hash, but compute the hash value from the
 546    element.  */
 547
 548 PTR *
 549 htab_find_slot (htab, element, insert)
 550      htab_t htab;
 551      const PTR element;
 552      enum insert_option insert;
 553 {
 554   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 555                                    insert);
 556 }
 557
 558 /* This function deletes an element with the given value from hash
 559    table.  If there is no matching element in the hash table, this
 560    function does nothing.  */
 561
 562 void
 563 htab_remove_elt (htab, element)
 564      htab_t htab;
 565      PTR element;
 566 {
 567   PTR *slot;
 568
 569   slot = htab_find_slot (htab, element, NO_INSERT);
 570   if (*slot == EMPTY_ENTRY)
 571     return;
 572
 573   if (htab->del_f)
 574     (*htab->del_f) (*slot);
 575
 576   *slot = DELETED_ENTRY;
 577   htab->n_deleted++;
 578 }
 579
 580 /* This function clears a specified slot in a hash table.  It is
 581    useful when you've already done the lookup and don't want to do it
 582    again.  */
 583
 584 void
 585 htab_clear_slot (htab, slot)
 586      htab_t htab;
 587      PTR *slot;
 588 {
 589   if (slot < htab->entries || slot >= htab->entries + htab->size
 590       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 591     abort ();
 592
 593   if (htab->del_f)
 594     (*htab->del_f) (*slot);
 595
 596   *slot = DELETED_ENTRY;
 597   htab->n_deleted++;
 598 }
 599
 600 /* This function scans over the entire hash table calling
 601    CALLBACK for each live entry.  If CALLBACK returns false,
 602    the iteration stops.  INFO is passed as CALLBACK's second
 603    argument.  */
 604
 605 void
 606 htab_traverse_noresize (htab, callback, info)
 607      htab_t htab;
 608      htab_trav callback;
 609      PTR info;
 610 {
 611   PTR *slot;
 612   PTR *limit;
 613
 614   slot = htab->entries;
 615   limit = slot + htab->size;
 616
 617   do
 618     {
 619       PTR x = *slot;
 620
 621       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 622         if (!(*callback) (slot, info))
 623           break;
 624     }
 625   while (++slot < limit);
 626 }
 627
 628 /* Like htab_traverse_noresize, but does resize the table when it is
 629    too empty to improve effectivity of subsequent calls.  */
 630
 631 void
 632 htab_traverse (htab, callback, info)
 633      htab_t htab;
 634      htab_trav callback;
 635      PTR info;
 636 {
 637   if ((htab->n_elements - htab->n_deleted) * 8 < htab->size)
 638     htab_expand (htab);
 639
 640   htab_traverse_noresize (htab, callback, info);
 641 }
 642
 643 /* Return the current size of given hash table. */
 644
 645 size_t
 646 htab_size (htab)
 647      htab_t htab;
 648 {
 649   return htab->size;
 650 }
 651
 652 /* Return the current number of elements in given hash table. */
 653
 654 size_t
 655 htab_elements (htab)
 656      htab_t htab;
 657 {
 658   return htab->n_elements - htab->n_deleted;
 659 }
 660
 661 /* Return the fraction of fixed collisions during all work with given
 662    hash table. */
 663
 664 double
 665 htab_collisions (htab)
 666      htab_t htab;
 667 {
 668   if (htab->searches == 0)
 669     return 0.0;
 670
 671   return (double) htab->collisions / (double) htab->searches;
 672 }
 673
 674 /* Hash P as a null-terminated string.
 675
 676    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 677    to applicability, though note that unlike hashtable.c, this hash table
 678    implementation re-hashes rather than chain buckets.
 679
 680    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 681    From: Zack Weinberg <zackw@panix.com>
 682    Date: Fri, 17 Aug 2001 02:15:56 -0400
 683
 684    I got it by extracting all the identifiers from all the source code
 685    I had lying around in mid-1999, and testing many recurrences of
 686    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 687    prime numbers or the appropriate identity.  This was the best one.
 688    I don't remember exactly what constituted "best", except I was
 689    looking at bucket-length distributions mostly.
 690
 691    So it should be very good at hashing identifiers, but might not be
 692    as good at arbitrary strings.
 693
 694    I'll add that it thoroughly trounces the hash functions recommended
 695    for this use at http://burtleburtle.net/bob/hash/index.html, both
 696    on speed and bucket distribution.  I haven't tried it against the
 697    function they just started using for Perl's hashes.  */
 698
 699 hashval_t
 700 htab_hash_string (p)
 701      const PTR p;
 702 {
 703   const unsigned char *str = (const unsigned char *) p;
 704   hashval_t r = 0;
 705   unsigned char c;
 706
 707   while ((c = *str++) != 0)
 708     r = r * 67 + c - 113;
 709
 710   return r;
 711 }