tools/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001 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 #include <sys/types.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37 #include <stdio.h>
  38 #include "tools/hashtab.h"
  39
  40 /* This macro defines reserved value for empty table entry. */
  41
  42 #define EMPTY_ENTRY    ((void *) 0)
  43
  44 /* This macro defines reserved value for table entry which contained
  45    a deleted element. */
  46
  47 #define DELETED_ENTRY  ((void *) 1)
  48
  49 static unsigned long higher_prime_number (unsigned long);
  50 static hashval_t hash_pointer (const void *);
  51 static int eq_pointer (const void *, const void *);
  52 static int htab_expand (htab_t);
  53 static void **find_empty_slot_for_expand  (htab_t, hashval_t);
  54
  55 /* At some point, we could make these be NULL, and modify the
  56    hash-table routines to handle NULL specially; that would avoid
  57    function-call overhead for the common case of hashing pointers.  */
  58 htab_hash htab_hash_pointer = hash_pointer;
  59 htab_eq htab_eq_pointer = eq_pointer;
  60
  61 /* The following function returns a nearest prime number which is
  62    greater than N, and near a power of two. */
  63
  64 static unsigned long
  65 higher_prime_number (n)
  66      unsigned long n;
  67 {
  68   /* These are primes that are near, but slightly smaller than, a
  69      power of two.  */
  70   static unsigned long primes[] = {
  71     (unsigned long) 2,
  72     (unsigned long) 7,
  73     (unsigned long) 13,
  74     (unsigned long) 31,
  75     (unsigned long) 61,
  76     (unsigned long) 127,
  77     (unsigned long) 251,
  78     (unsigned long) 509,
  79     (unsigned long) 1021,
  80     (unsigned long) 2039,
  81     (unsigned long) 4093,
  82     (unsigned long) 8191,
  83     (unsigned long) 16381,
  84     (unsigned long) 32749,
  85     (unsigned long) 65521,
  86     (unsigned long) 131071,
  87     (unsigned long) 262139,
  88     (unsigned long) 524287,
  89     (unsigned long) 1048573,
  90     (unsigned long) 2097143,
  91     (unsigned long) 4194301,
  92     (unsigned long) 8388593,
  93     (unsigned long) 16777213,
  94     (unsigned long) 33554393,
  95     (unsigned long) 67108859,
  96     (unsigned long) 134217689,
  97     (unsigned long) 268435399,
  98     (unsigned long) 536870909,
  99     (unsigned long) 1073741789,
 100     (unsigned long) 2147483647,
 101                                         /* 4294967291L */
 102     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
 103   };
 104
 105   unsigned long* low = &primes[0];
 106   unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])];
 107
 108   while (low != high)
 109     {
 110       unsigned long* mid = low + (high - low) / 2;
 111       if (n > *mid)
 112         low = mid + 1;
 113       else
 114         high = mid;
 115     }
 116
 117   /* If we've run out of primes, abort.  */
 118   if (n > *low)
 119     {
 120       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 121       abort ();
 122     }
 123
 124   return *low;
 125 }
 126
 127 /* Returns a hash code for P.  */
 128
 129 static hashval_t
 130 hash_pointer (p)
 131      const void * p;
 132 {
 133   return (hashval_t) ((long)p >> 3);
 134 }
 135
 136 /* Returns non-zero if P1 and P2 are equal.  */
 137
 138 static int
 139 eq_pointer (p1, p2)
 140      const void * p1;
 141      const void * p2;
 142 {
 143   return p1 == p2;
 144 }
 145
 146 /* This function creates table with length slightly longer than given
 147    source length.  The created hash table is initiated as empty (all the
 148    hash table entries are EMPTY_ENTRY).  The function returns the created
 149    hash table.  Memory allocation may fail; it may return NULL.  */
 150
 151 htab_t
 152 htab_try_create (size, hash_f, eq_f, del_f)
 153      size_t size;
 154      htab_hash hash_f;
 155      htab_eq eq_f;
 156      htab_del del_f;
 157 {
 158   htab_t result;
 159
 160   size = higher_prime_number (size);
 161   result = (htab_t) calloc (1, sizeof (struct htab));
 162   if (result == NULL)
 163     return NULL;
 164
 165   result->entries = (void **) calloc (size, sizeof (void *));
 166   if (result->entries == NULL)
 167     {
 168       free (result);
 169       return NULL;
 170     }
 171
 172   result->size = size;
 173   result->hash_f = hash_f;
 174   result->eq_f = eq_f;
 175   result->del_f = del_f;
 176   result->return_allocation_failure = 1;
 177   return result;
 178 }
 179
 180 /* This function frees all memory allocated for given hash table.
 181    Naturally the hash table must already exist. */
 182
 183 void
 184 htab_delete (htab)
 185      htab_t htab;
 186 {
 187   int i;
 188
 189   if (htab->del_f)
 190     for (i = htab->size - 1; i >= 0; i--)
 191       if (htab->entries[i] != EMPTY_ENTRY
 192           && htab->entries[i] != DELETED_ENTRY)
 193         (*htab->del_f) (htab->entries[i]);
 194
 195   free (htab->entries);
 196   free (htab);
 197 }
 198
 199 /* This function clears all entries in the given hash table.  */
 200
 201 void
 202 htab_empty (htab)
 203      htab_t htab;
 204 {
 205   int i;
 206
 207   if (htab->del_f)
 208     for (i = htab->size - 1; i >= 0; i--)
 209       if (htab->entries[i] != EMPTY_ENTRY
 210           && htab->entries[i] != DELETED_ENTRY)
 211         (*htab->del_f) (htab->entries[i]);
 212
 213   memset (htab->entries, 0, htab->size * sizeof (void *));
 214 }
 215
 216 /* Similar to htab_find_slot, but without several unwanted side effects:
 217     - Does not call htab->eq_f when it finds an existing entry.
 218     - Does not change the count of elements/searches/collisions in the
 219       hash table.
 220    This function also assumes there are no deleted entries in the table.
 221    HASH is the hash value for the element to be inserted.  */
 222
 223 static void **
 224 find_empty_slot_for_expand (htab, hash)
 225      htab_t htab;
 226      hashval_t hash;
 227 {
 228   size_t size = htab->size;
 229   hashval_t hash2 = 1 + hash % (size - 2);
 230   unsigned int index = hash % size;
 231
 232   for (;;)
 233     {
 234       void **slot = htab->entries + index;
 235
 236       if (*slot == EMPTY_ENTRY)
 237         return slot;
 238       else if (*slot == DELETED_ENTRY)
 239         abort ();
 240
 241       index += hash2;
 242       if (index >= size)
 243         index -= size;
 244     }
 245 }
 246
 247 /* The following function changes size of memory allocated for the
 248    entries and repeatedly inserts the table elements.  The occupancy
 249    of the table after the call will be about 50%.  Naturally the hash
 250    table must already exist.  Remember also that the place of the
 251    table entries is changed.  If memory allocation failures are allowed,
 252    this function will return zero, indicating that the table could not be
 253    expanded.  If all goes well, it will return a non-zero value.  */
 254
 255 static int
 256 htab_expand (htab)
 257      htab_t htab;
 258 {
 259   void **oentries;
 260   void **olimit;
 261   void **p;
 262
 263   oentries = htab->entries;
 264   olimit = oentries + htab->size;
 265
 266   htab->size = higher_prime_number (htab->size * 2);
 267
 268   if (htab->return_allocation_failure)
 269     {
 270       void **nentries = (void **) calloc (htab->size, sizeof (void **));
 271       if (nentries == NULL)
 272         return 0;
 273       htab->entries = nentries;
 274     }
 275
 276   htab->n_elements -= htab->n_deleted;
 277   htab->n_deleted = 0;
 278
 279   p = oentries;
 280   do
 281     {
 282       void * x = *p;
 283
 284       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 285         {
 286           void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 287
 288           *q = x;
 289         }
 290
 291       p++;
 292     }
 293   while (p < olimit);
 294
 295   free (oentries);
 296   return 1;
 297 }
 298
 299 /* This function searches for a hash table entry equal to the given
 300    element.  It cannot be used to insert or delete an element.  */
 301
 302 void *
 303 htab_find_with_hash (htab, element, hash)
 304      htab_t htab;
 305      const void * element;
 306      hashval_t hash;
 307 {
 308   unsigned int index;
 309   hashval_t hash2;
 310   size_t size;
 311   void * entry;
 312
 313   htab->searches++;
 314   size = htab->size;
 315   index = hash % size;
 316
 317   entry = htab->entries[index];
 318   if (entry == EMPTY_ENTRY
 319       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 320     return entry;
 321
 322   hash2 = 1 + hash % (size - 2);
 323
 324   for (;;)
 325     {
 326       htab->collisions++;
 327       index += hash2;
 328       if (index >= size)
 329         index -= size;
 330
 331       entry = htab->entries[index];
 332       if (entry == EMPTY_ENTRY
 333           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 334         return entry;
 335     }
 336 }
 337
 338 /* Like htab_find_slot_with_hash, but compute the hash value from the
 339    element.  */
 340
 341 void *
 342 htab_find (htab, element)
 343      htab_t htab;
 344      const void * element;
 345 {
 346   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 347 }
 348
 349 /* This function searches for a hash table slot containing an entry
 350    equal to the given element.  To delete an entry, call this with
 351    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 352    after doing some checks).  To insert an entry, call this with
 353    INSERT = 1, then write the value you want into the returned slot.
 354    When inserting an entry, NULL may be returned if memory allocation
 355    fails.  */
 356
 357 void **
 358 htab_find_slot_with_hash (htab, element, hash, insert)
 359      htab_t htab;
 360      const void * element;
 361      hashval_t hash;
 362      enum insert_option insert;
 363 {
 364   void **first_deleted_slot;
 365   unsigned int index;
 366   hashval_t hash2;
 367   size_t size;
 368
 369   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 370       && htab_expand (htab) == 0)
 371     return NULL;
 372
 373   size = htab->size;
 374   hash2 = 1 + hash % (size - 2);
 375   index = hash % size;
 376
 377   htab->searches++;
 378   first_deleted_slot = NULL;
 379
 380   for (;;)
 381     {
 382       void * entry = htab->entries[index];
 383       if (entry == EMPTY_ENTRY)
 384         {
 385           if (insert == NO_INSERT)
 386             return NULL;
 387
 388           htab->n_elements++;
 389
 390           if (first_deleted_slot)
 391             {
 392               *first_deleted_slot = EMPTY_ENTRY;
 393               return first_deleted_slot;
 394             }
 395
 396           return &htab->entries[index];
 397         }
 398
 399       if (entry == DELETED_ENTRY)
 400         {
 401           if (!first_deleted_slot)
 402             first_deleted_slot = &htab->entries[index];
 403         }
 404       else  if ((*htab->eq_f) (entry, element))
 405         return &htab->entries[index];
 406
 407       htab->collisions++;
 408       index += hash2;
 409       if (index >= size)
 410         index -= size;
 411     }
 412 }
 413
 414 /* Like htab_find_slot_with_hash, but compute the hash value from the
 415    element.  */
 416
 417 void **
 418 htab_find_slot (htab, element, insert)
 419      htab_t htab;
 420      const void * element;
 421      enum insert_option insert;
 422 {
 423   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 424                                    insert);
 425 }
 426
 427 /* This function deletes an element with the given value from hash
 428    table.  If there is no matching element in the hash table, this
 429    function does nothing.  */
 430
 431 void
 432 htab_remove_elt (htab, element)
 433      htab_t htab;
 434      void * element;
 435 {
 436   void **slot;
 437
 438   slot = htab_find_slot (htab, element, NO_INSERT);
 439   if (*slot == EMPTY_ENTRY)
 440     return;
 441
 442   if (htab->del_f)
 443     (*htab->del_f) (*slot);
 444
 445   *slot = DELETED_ENTRY;
 446   htab->n_deleted++;
 447 }
 448
 449 /* This function clears a specified slot in a hash table.  It is
 450    useful when you've already done the lookup and don't want to do it
 451    again.  */
 452
 453 void
 454 htab_clear_slot (htab, slot)
 455      htab_t htab;
 456      void **slot;
 457 {
 458   if (slot < htab->entries || slot >= htab->entries + htab->size
 459       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 460     abort ();
 461
 462   if (htab->del_f)
 463     (*htab->del_f) (*slot);
 464
 465   *slot = DELETED_ENTRY;
 466   htab->n_deleted++;
 467 }
 468
 469 /* This function scans over the entire hash table calling
 470    CALLBACK for each live entry.  If CALLBACK returns false,
 471    the iteration stops.  INFO is passed as CALLBACK's second
 472    argument.  */
 473
 474 void
 475 htab_traverse (htab, callback, info)
 476      htab_t htab;
 477      htab_trav callback;
 478      void * info;
 479 {
 480   void **slot = htab->entries;
 481   void **limit = slot + htab->size;
 482
 483   do
 484     {
 485       void * x = *slot;
 486
 487       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 488         if (!(*callback) (slot, info))
 489           break;
 490     }
 491   while (++slot < limit);
 492 }
 493
 494 /* Return the current size of given hash table. */
 495
 496 size_t
 497 htab_size (htab)
 498      htab_t htab;
 499 {
 500   return htab->size;
 501 }
 502
 503 /* Return the current number of elements in given hash table. */
 504
 505 size_t
 506 htab_elements (htab)
 507      htab_t htab;
 508 {
 509   return htab->n_elements - htab->n_deleted;
 510 }
 511
 512 /* Return the fraction of fixed collisions during all work with given
 513    hash table. */
 514
 515 double
 516 htab_collisions (htab)
 517      htab_t htab;
 518 {
 519   if (htab->searches == 0)
 520     return 0.0;
 521
 522   return (double) htab->collisions / (double) htab->searches;
 523 }