libiberty/hashtab.c

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