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