libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001, 2002 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 /* These functions exist solely for backward compatibility.  */
 195
 196 #undef htab_create
 197 htab_t
 198 htab_create (size, hash_f, eq_f, del_f)
 199      size_t size;
 200      htab_hash hash_f;
 201      htab_eq eq_f;
 202      htab_del del_f;
 203 {
 204   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 205 }
 206
 207 htab_t
 208 htab_try_create (size, hash_f, eq_f, del_f)
 209      size_t size;
 210      htab_hash hash_f;
 211      htab_eq eq_f;
 212      htab_del del_f;
 213 {
 214   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 215 }
 216
 217 /* This function frees all memory allocated for given hash table.
 218    Naturally the hash table must already exist. */
 219
 220 void
 221 htab_delete (htab)
 222      htab_t htab;
 223 {
 224   int i;
 225
 226   if (htab->del_f)
 227     for (i = htab->size - 1; i >= 0; i--)
 228       if (htab->entries[i] != EMPTY_ENTRY
 229           && htab->entries[i] != DELETED_ENTRY)
 230         (*htab->del_f) (htab->entries[i]);
 231
 232   if (htab->free_f != NULL)
 233     {
 234       (*htab->free_f) (htab->entries);
 235       (*htab->free_f) (htab);
 236     }
 237 }
 238
 239 /* This function clears all entries in the given hash table.  */
 240
 241 void
 242 htab_empty (htab)
 243      htab_t htab;
 244 {
 245   int i;
 246
 247   if (htab->del_f)
 248     for (i = htab->size - 1; i >= 0; i--)
 249       if (htab->entries[i] != EMPTY_ENTRY
 250           && htab->entries[i] != DELETED_ENTRY)
 251         (*htab->del_f) (htab->entries[i]);
 252
 253   memset (htab->entries, 0, htab->size * sizeof (PTR));
 254 }
 255
 256 /* Similar to htab_find_slot, but without several unwanted side effects:
 257     - Does not call htab->eq_f when it finds an existing entry.
 258     - Does not change the count of elements/searches/collisions in the
 259       hash table.
 260    This function also assumes there are no deleted entries in the table.
 261    HASH is the hash value for the element to be inserted.  */
 262
 263 static PTR *
 264 find_empty_slot_for_expand (htab, hash)
 265      htab_t htab;
 266      hashval_t hash;
 267 {
 268   size_t size = htab->size;
 269   unsigned int index = hash % size;
 270   PTR *slot = htab->entries + index;
 271   hashval_t hash2;
 272
 273   if (*slot == EMPTY_ENTRY)
 274     return slot;
 275   else if (*slot == DELETED_ENTRY)
 276     abort ();
 277
 278   hash2 = 1 + hash % (size - 2);
 279   for (;;)
 280     {
 281       index += hash2;
 282       if (index >= size)
 283         index -= size;
 284
 285       slot = htab->entries + index;
 286       if (*slot == EMPTY_ENTRY)
 287         return slot;
 288       else if (*slot == DELETED_ENTRY)
 289         abort ();
 290     }
 291 }
 292
 293 /* The following function changes size of memory allocated for the
 294    entries and repeatedly inserts the table elements.  The occupancy
 295    of the table after the call will be about 50%.  Naturally the hash
 296    table must already exist.  Remember also that the place of the
 297    table entries is changed.  If memory allocation failures are allowed,
 298    this function will return zero, indicating that the table could not be
 299    expanded.  If all goes well, it will return a non-zero value.  */
 300
 301 static int
 302 htab_expand (htab)
 303      htab_t htab;
 304 {
 305   PTR *oentries;
 306   PTR *olimit;
 307   PTR *p;
 308   PTR *nentries;
 309   size_t nsize;
 310
 311   oentries = htab->entries;
 312   olimit = oentries + htab->size;
 313
 314   nsize = higher_prime_number (htab->size * 2);
 315
 316   nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR));
 317   if (nentries == NULL)
 318     return 0;
 319   htab->entries = nentries;
 320   htab->size = nsize;
 321
 322   htab->n_elements -= htab->n_deleted;
 323   htab->n_deleted = 0;
 324
 325   p = oentries;
 326   do
 327     {
 328       PTR x = *p;
 329
 330       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 331         {
 332           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 333
 334           *q = x;
 335         }
 336
 337       p++;
 338     }
 339   while (p < olimit);
 340
 341   if (htab->free_f != NULL)
 342     (*htab->free_f) (oentries);
 343   return 1;
 344 }
 345
 346 /* This function searches for a hash table entry equal to the given
 347    element.  It cannot be used to insert or delete an element.  */
 348
 349 PTR
 350 htab_find_with_hash (htab, element, hash)
 351      htab_t htab;
 352      const PTR element;
 353      hashval_t hash;
 354 {
 355   unsigned int index;
 356   hashval_t hash2;
 357   size_t size;
 358   PTR entry;
 359
 360   htab->searches++;
 361   size = htab->size;
 362   index = hash % size;
 363
 364   entry = htab->entries[index];
 365   if (entry == EMPTY_ENTRY
 366       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 367     return entry;
 368
 369   hash2 = 1 + hash % (size - 2);
 370
 371   for (;;)
 372     {
 373       htab->collisions++;
 374       index += hash2;
 375       if (index >= size)
 376         index -= size;
 377
 378       entry = htab->entries[index];
 379       if (entry == EMPTY_ENTRY
 380           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 381         return entry;
 382     }
 383 }
 384
 385 /* Like htab_find_slot_with_hash, but compute the hash value from the
 386    element.  */
 387
 388 PTR
 389 htab_find (htab, element)
 390      htab_t htab;
 391      const PTR element;
 392 {
 393   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 394 }
 395
 396 /* This function searches for a hash table slot containing an entry
 397    equal to the given element.  To delete an entry, call this with
 398    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 399    after doing some checks).  To insert an entry, call this with
 400    INSERT = 1, then write the value you want into the returned slot.
 401    When inserting an entry, NULL may be returned if memory allocation
 402    fails.  */
 403
 404 PTR *
 405 htab_find_slot_with_hash (htab, element, hash, insert)
 406      htab_t htab;
 407      const PTR element;
 408      hashval_t hash;
 409      enum insert_option insert;
 410 {
 411   PTR *first_deleted_slot;
 412   unsigned int index;
 413   hashval_t hash2;
 414   size_t size;
 415   PTR entry;
 416
 417   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 418       && htab_expand (htab) == 0)
 419     return NULL;
 420
 421   size = htab->size;
 422   index = hash % size;
 423
 424   htab->searches++;
 425   first_deleted_slot = NULL;
 426
 427   entry = htab->entries[index];
 428   if (entry == EMPTY_ENTRY)
 429     goto empty_entry;
 430   else if (entry == DELETED_ENTRY)
 431     first_deleted_slot = &htab->entries[index];
 432   else if ((*htab->eq_f) (entry, element))
 433     return &htab->entries[index];
 434
 435   hash2 = 1 + hash % (size - 2);
 436   for (;;)
 437     {
 438       htab->collisions++;
 439       index += hash2;
 440       if (index >= size)
 441         index -= size;
 442
 443       entry = htab->entries[index];
 444       if (entry == EMPTY_ENTRY)
 445         goto empty_entry;
 446       else if (entry == DELETED_ENTRY)
 447         {
 448           if (!first_deleted_slot)
 449             first_deleted_slot = &htab->entries[index];
 450         }
 451       else if ((*htab->eq_f) (entry, element))
 452         return &htab->entries[index];
 453     }
 454
 455  empty_entry:
 456   if (insert == NO_INSERT)
 457     return NULL;
 458
 459   htab->n_elements++;
 460
 461   if (first_deleted_slot)
 462     {
 463       *first_deleted_slot = EMPTY_ENTRY;
 464       return first_deleted_slot;
 465     }
 466
 467   return &htab->entries[index];
 468 }
 469
 470 /* Like htab_find_slot_with_hash, but compute the hash value from the
 471    element.  */
 472
 473 PTR *
 474 htab_find_slot (htab, element, insert)
 475      htab_t htab;
 476      const PTR element;
 477      enum insert_option insert;
 478 {
 479   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 480                                    insert);
 481 }
 482
 483 /* This function deletes an element with the given value from hash
 484    table.  If there is no matching element in the hash table, this
 485    function does nothing.  */
 486
 487 void
 488 htab_remove_elt (htab, element)
 489      htab_t htab;
 490      PTR element;
 491 {
 492   PTR *slot;
 493
 494   slot = htab_find_slot (htab, element, NO_INSERT);
 495   if (*slot == EMPTY_ENTRY)
 496     return;
 497
 498   if (htab->del_f)
 499     (*htab->del_f) (*slot);
 500
 501   *slot = DELETED_ENTRY;
 502   htab->n_deleted++;
 503 }
 504
 505 /* This function clears a specified slot in a hash table.  It is
 506    useful when you've already done the lookup and don't want to do it
 507    again.  */
 508
 509 void
 510 htab_clear_slot (htab, slot)
 511      htab_t htab;
 512      PTR *slot;
 513 {
 514   if (slot < htab->entries || slot >= htab->entries + htab->size
 515       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 516     abort ();
 517
 518   if (htab->del_f)
 519     (*htab->del_f) (*slot);
 520
 521   *slot = DELETED_ENTRY;
 522   htab->n_deleted++;
 523 }
 524
 525 /* This function scans over the entire hash table calling
 526    CALLBACK for each live entry.  If CALLBACK returns false,
 527    the iteration stops.  INFO is passed as CALLBACK's second
 528    argument.  */
 529
 530 void
 531 htab_traverse (htab, callback, info)
 532      htab_t htab;
 533      htab_trav callback;
 534      PTR info;
 535 {
 536   PTR *slot = htab->entries;
 537   PTR *limit = slot + htab->size;
 538
 539   do
 540     {
 541       PTR x = *slot;
 542
 543       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 544         if (!(*callback) (slot, info))
 545           break;
 546     }
 547   while (++slot < limit);
 548 }
 549
 550 /* Return the current size of given hash table. */
 551
 552 size_t
 553 htab_size (htab)
 554      htab_t htab;
 555 {
 556   return htab->size;
 557 }
 558
 559 /* Return the current number of elements in given hash table. */
 560
 561 size_t
 562 htab_elements (htab)
 563      htab_t htab;
 564 {
 565   return htab->n_elements - htab->n_deleted;
 566 }
 567
 568 /* Return the fraction of fixed collisions during all work with given
 569    hash table. */
 570
 571 double
 572 htab_collisions (htab)
 573      htab_t htab;
 574 {
 575   if (htab->searches == 0)
 576     return 0.0;
 577
 578   return (double) htab->collisions / (double) htab->searches;
 579 }
 580
 581 /* Hash P as a null-terminated string.
 582
 583    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 584    to applicability, though note that unlike hashtable.c, this hash table
 585    implementation re-hashes rather than chain buckets.
 586
 587    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 588    From: Zack Weinberg <zackw@panix.com>
 589    Date: Fri, 17 Aug 2001 02:15:56 -0400
 590
 591    I got it by extracting all the identifiers from all the source code
 592    I had lying around in mid-1999, and testing many recurrences of
 593    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 594    prime numbers or the appropriate identity.  This was the best one.
 595    I don't remember exactly what constituted "best", except I was
 596    looking at bucket-length distributions mostly.
 597
 598    So it should be very good at hashing identifiers, but might not be
 599    as good at arbitrary strings.
 600
 601    I'll add that it thoroughly trounces the hash functions recommended
 602    for this use at http://burtleburtle.net/bob/hash/index.html, both
 603    on speed and bucket distribution.  I haven't tried it against the
 604    function they just started using for Perl's hashes.  */
 605
 606 hashval_t
 607 htab_hash_string (p)
 608      const PTR p;
 609 {
 610   const unsigned char *str = (const unsigned char *) p;
 611   hashval_t r = 0;
 612   unsigned char c;
 613
 614   while ((c = *str++) != 0)
 615     r = r * 67 + c - 113;
 616
 617   return r;
 618 }