libiberty/hashtab.c

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