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
 310   oentries = htab->entries;
 311   olimit = oentries + htab->size;
 312
 313   htab->size = higher_prime_number (htab->size * 2);
 314
 315   nentries = (PTR *) (*htab->alloc_f) (htab->size, sizeof (PTR *));
 316   if (nentries == NULL)
 317     return 0;
 318   htab->entries = nentries;
 319
 320   htab->n_elements -= htab->n_deleted;
 321   htab->n_deleted = 0;
 322
 323   p = oentries;
 324   do
 325     {
 326       PTR x = *p;
 327
 328       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 329         {
 330           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 331
 332           *q = x;
 333         }
 334
 335       p++;
 336     }
 337   while (p < olimit);
 338
 339   if (htab->free_f != NULL)
 340     (*htab->free_f) (oentries);
 341   return 1;
 342 }
 343
 344 /* This function searches for a hash table entry equal to the given
 345    element.  It cannot be used to insert or delete an element.  */
 346
 347 PTR
 348 htab_find_with_hash (htab, element, hash)
 349      htab_t htab;
 350      const PTR element;
 351      hashval_t hash;
 352 {
 353   unsigned int index;
 354   hashval_t hash2;
 355   size_t size;
 356   PTR entry;
 357
 358   htab->searches++;
 359   size = htab->size;
 360   index = hash % size;
 361
 362   entry = htab->entries[index];
 363   if (entry == EMPTY_ENTRY
 364       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 365     return entry;
 366
 367   hash2 = 1 + hash % (size - 2);
 368
 369   for (;;)
 370     {
 371       htab->collisions++;
 372       index += hash2;
 373       if (index >= size)
 374         index -= size;
 375
 376       entry = htab->entries[index];
 377       if (entry == EMPTY_ENTRY
 378           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 379         return entry;
 380     }
 381 }
 382
 383 /* Like htab_find_slot_with_hash, but compute the hash value from the
 384    element.  */
 385
 386 PTR
 387 htab_find (htab, element)
 388      htab_t htab;
 389      const PTR element;
 390 {
 391   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 392 }
 393
 394 /* This function searches for a hash table slot containing an entry
 395    equal to the given element.  To delete an entry, call this with
 396    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 397    after doing some checks).  To insert an entry, call this with
 398    INSERT = 1, then write the value you want into the returned slot.
 399    When inserting an entry, NULL may be returned if memory allocation
 400    fails.  */
 401
 402 PTR *
 403 htab_find_slot_with_hash (htab, element, hash, insert)
 404      htab_t htab;
 405      const PTR element;
 406      hashval_t hash;
 407      enum insert_option insert;
 408 {
 409   PTR *first_deleted_slot;
 410   unsigned int index;
 411   hashval_t hash2;
 412   size_t size;
 413   PTR entry;
 414
 415   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 416       && htab_expand (htab) == 0)
 417     return NULL;
 418
 419   size = htab->size;
 420   index = hash % size;
 421
 422   htab->searches++;
 423   first_deleted_slot = NULL;
 424
 425   entry = htab->entries[index];
 426   if (entry == EMPTY_ENTRY)
 427     goto empty_entry;
 428   else if (entry == DELETED_ENTRY)
 429     first_deleted_slot = &htab->entries[index];
 430   else if ((*htab->eq_f) (entry, element))
 431     return &htab->entries[index];
 432
 433   hash2 = 1 + hash % (size - 2);
 434   for (;;)
 435     {
 436       htab->collisions++;
 437       index += hash2;
 438       if (index >= size)
 439         index -= size;
 440
 441       entry = htab->entries[index];
 442       if (entry == EMPTY_ENTRY)
 443         goto empty_entry;
 444       else if (entry == DELETED_ENTRY)
 445         {
 446           if (!first_deleted_slot)
 447             first_deleted_slot = &htab->entries[index];
 448         }
 449       else if ((*htab->eq_f) (entry, element))
 450         return &htab->entries[index];
 451     }
 452
 453  empty_entry:
 454   if (insert == NO_INSERT)
 455     return NULL;
 456
 457   htab->n_elements++;
 458
 459   if (first_deleted_slot)
 460     {
 461       *first_deleted_slot = EMPTY_ENTRY;
 462       return first_deleted_slot;
 463     }
 464
 465   return &htab->entries[index];
 466 }
 467
 468 /* Like htab_find_slot_with_hash, but compute the hash value from the
 469    element.  */
 470
 471 PTR *
 472 htab_find_slot (htab, element, insert)
 473      htab_t htab;
 474      const PTR element;
 475      enum insert_option insert;
 476 {
 477   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 478                                    insert);
 479 }
 480
 481 /* This function deletes an element with the given value from hash
 482    table.  If there is no matching element in the hash table, this
 483    function does nothing.  */
 484
 485 void
 486 htab_remove_elt (htab, element)
 487      htab_t htab;
 488      PTR element;
 489 {
 490   PTR *slot;
 491
 492   slot = htab_find_slot (htab, element, NO_INSERT);
 493   if (*slot == EMPTY_ENTRY)
 494     return;
 495
 496   if (htab->del_f)
 497     (*htab->del_f) (*slot);
 498
 499   *slot = DELETED_ENTRY;
 500   htab->n_deleted++;
 501 }
 502
 503 /* This function clears a specified slot in a hash table.  It is
 504    useful when you've already done the lookup and don't want to do it
 505    again.  */
 506
 507 void
 508 htab_clear_slot (htab, slot)
 509      htab_t htab;
 510      PTR *slot;
 511 {
 512   if (slot < htab->entries || slot >= htab->entries + htab->size
 513       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 514     abort ();
 515
 516   if (htab->del_f)
 517     (*htab->del_f) (*slot);
 518
 519   *slot = DELETED_ENTRY;
 520   htab->n_deleted++;
 521 }
 522
 523 /* This function scans over the entire hash table calling
 524    CALLBACK for each live entry.  If CALLBACK returns false,
 525    the iteration stops.  INFO is passed as CALLBACK's second
 526    argument.  */
 527
 528 void
 529 htab_traverse (htab, callback, info)
 530      htab_t htab;
 531      htab_trav callback;
 532      PTR info;
 533 {
 534   PTR *slot = htab->entries;
 535   PTR *limit = slot + htab->size;
 536
 537   do
 538     {
 539       PTR x = *slot;
 540
 541       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 542         if (!(*callback) (slot, info))
 543           break;
 544     }
 545   while (++slot < limit);
 546 }
 547
 548 /* Return the current size of given hash table. */
 549
 550 size_t
 551 htab_size (htab)
 552      htab_t htab;
 553 {
 554   return htab->size;
 555 }
 556
 557 /* Return the current number of elements in given hash table. */
 558
 559 size_t
 560 htab_elements (htab)
 561      htab_t htab;
 562 {
 563   return htab->n_elements - htab->n_deleted;
 564 }
 565
 566 /* Return the fraction of fixed collisions during all work with given
 567    hash table. */
 568
 569 double
 570 htab_collisions (htab)
 571      htab_t htab;
 572 {
 573   if (htab->searches == 0)
 574     return 0.0;
 575
 576   return (double) htab->collisions / (double) htab->searches;
 577 }
 578
 579 /* Hash P as a null-terminated string.
 580
 581    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 582    to applicability, though note that unlike hashtable.c, this hash table
 583    implementation re-hashes rather than chain buckets.
 584
 585    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 586    From: Zack Weinberg <zackw@panix.com>
 587    Date: Fri, 17 Aug 2001 02:15:56 -0400
 588
 589    I got it by extracting all the identifiers from all the source code
 590    I had lying around in mid-1999, and testing many recurrences of
 591    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 592    prime numbers or the appropriate identity.  This was the best one.
 593    I don't remember exactly what constituted "best", except I was
 594    looking at bucket-length distributions mostly.
 595
 596    So it should be very good at hashing identifiers, but might not be
 597    as good at arbitrary strings.
 598
 599    I'll add that it thoroughly trounces the hash functions recommended
 600    for this use at http://burtleburtle.net/bob/hash/index.html, both
 601    on speed and bucket distribution.  I haven't tried it against the
 602    function they just started using for Perl's hashes.  */
 603
 604 hashval_t
 605 htab_hash_string (p)
 606      const PTR p;
 607 {
 608   const unsigned char *str = (const unsigned char *) p;
 609   hashval_t r = 0;
 610   unsigned char c;
 611
 612   while ((c = *str++) != 0)
 613     r = r * 67 + c - 113;
 614
 615   return r;
 616 }