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)
  92      size_t size;
  93      htab_hash hash_f;
  94      htab_eq eq_f;
  95 {
  96   htab_t result;
  97
  98   size = higher_prime_number (size);
  99   result = (htab_t) xcalloc (1, sizeof (struct htab));
 100   result->entries = (void **) xcalloc (size, sizeof (void *));
 101   result->size = size;
 102   result->hash_f = hash_f;
 103   result->eq_f = eq_f;
 104   return result;
 105 }
 106
 107 /* This function frees all memory allocated for given hash table.
 108    Naturally the hash table must already exist. */
 109
 110 void
 111 htab_delete (htab)
 112      htab_t htab;
 113 {
 114   free (htab->entries);
 115   free (htab);
 116 }
 117
 118 /* This function clears all entries in the given hash table.  */
 119
 120 void
 121 htab_empty (htab)
 122      htab_t htab;
 123 {
 124   memset (htab->entries, 0, htab->size * sizeof (void *));
 125 }
 126
 127 /* The following function changes size of memory allocated for the
 128    entries and repeatedly inserts the table elements.  The occupancy
 129    of the table after the call will be about 50%.  Naturally the hash
 130    table must already exist.  Remember also that the place of the
 131    table entries is changed. */
 132
 133 static void
 134 htab_expand (htab)
 135      htab_t htab;
 136 {
 137   void **oentries;
 138   void **olimit;
 139   void **p;
 140
 141   oentries = htab->entries;
 142   olimit = oentries + htab->size;
 143
 144   htab->size = higher_prime_number (htab->size * 2);
 145   htab->entries = xcalloc (htab->size, sizeof (void **));
 146
 147   htab->n_elements -= htab->n_deleted;
 148   htab->n_deleted = 0;
 149
 150   p = oentries;
 151   do
 152     {
 153       void *x = *p;
 154       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 155         {
 156           void **q = htab_find_slot (htab, x, 1);
 157           *q = x;
 158         }
 159       p++;
 160     }
 161   while (p < olimit);
 162   free (oentries);
 163 }
 164
 165 /* This function searches for a hash table entry equal to the given
 166    element.  It cannot be used to insert or delete an element.  */
 167
 168 void *
 169 htab_find (htab, element)
 170      htab_t htab;
 171      const void *element;
 172 {
 173   unsigned int index, hash, hash2;
 174   size_t size;
 175
 176   htab->searches++;
 177   size = htab->size;
 178   hash = (*htab->hash_f) (element);
 179   hash2 = 1 + hash % (size - 2);
 180   index = hash % size;
 181
 182   for (;;)
 183     {
 184       void *entry = htab->entries[index];
 185       if (entry == EMPTY_ENTRY)
 186         return NULL;
 187       else if (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))
 188         return entry;
 189
 190       htab->collisions++;
 191       index += hash2;
 192       if (index >= size)
 193         index -= size;
 194     }
 195 }
 196
 197 /* This function searches for a hash table slot containing an entry
 198    equal to the given element.  To delete an entry, call this with
 199    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 200    after doing some checks).  To insert an entry, call this with
 201    INSERT = 1, then write the value you want into the returned slot.  */
 202
 203 void **
 204 htab_find_slot (htab, element, insert)
 205      htab_t htab;
 206      const void *element;
 207      int insert;
 208 {
 209   void **first_deleted_slot;
 210   unsigned int index, hash, hash2;
 211   size_t size;
 212
 213   if (insert && htab->size * 3 <= htab->n_elements * 4)
 214     htab_expand (htab);
 215
 216   size = htab->size;
 217   hash = (*htab->hash_f) (element);
 218   hash2 = 1 + hash % (size - 2);
 219   index = hash % size;
 220
 221   htab->searches++;
 222   first_deleted_slot = NULL;
 223
 224   for (;;)
 225     {
 226       void *entry = htab->entries[index];
 227       if (entry == EMPTY_ENTRY)
 228         {
 229           if (!insert)
 230             return NULL;
 231
 232           htab->n_elements++;
 233
 234           if (first_deleted_slot)
 235             {
 236               *first_deleted_slot = EMPTY_ENTRY;
 237               return first_deleted_slot;
 238             }
 239
 240           return &htab->entries[index];
 241         }
 242
 243       if (entry == DELETED_ENTRY)
 244         {
 245           if (!first_deleted_slot)
 246             first_deleted_slot = &htab->entries[index];
 247         }
 248       else
 249         {
 250           if ((*htab->eq_f) (entry, element))
 251             return &htab->entries[index];
 252         }
 253
 254       htab->collisions++;
 255       index += hash2;
 256       if (index >= size)
 257         index -= size;
 258     }
 259 }
 260
 261 /* This function deletes an element with the given value from hash
 262    table.  If there is no matching element in the hash table, this
 263    function does nothing.  */
 264
 265 void
 266 htab_remove_elt (htab, element)
 267      htab_t htab;
 268      void *element;
 269 {
 270   void **slot;
 271
 272   slot = htab_find_slot (htab, element, 0);
 273   if (*slot == EMPTY_ENTRY)
 274     return;
 275
 276   *slot = DELETED_ENTRY;
 277   htab->n_deleted++;
 278 }
 279
 280 /* This function clears a specified slot in a hash table.  It is
 281    useful when you've already done the lookup and don't want to do it
 282    again.  */
 283
 284 void
 285 htab_clear_slot (htab, slot)
 286      htab_t htab;
 287      void **slot;
 288 {
 289   if (slot < htab->entries || slot >= htab->entries + htab->size
 290       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 291     abort ();
 292   *slot = DELETED_ENTRY;
 293   htab->n_deleted++;
 294 }
 295
 296 /* This function scans over the entire hash table calling
 297    CALLBACK for each live entry.  If CALLBACK returns false,
 298    the iteration stops.  INFO is passed as CALLBACK's second
 299    argument.  */
 300
 301 void
 302 htab_traverse (htab, callback, info)
 303      htab_t htab;
 304      htab_trav callback;
 305      void *info;
 306 {
 307   void **slot, **limit;
 308   slot = htab->entries;
 309   limit = slot + htab->size;
 310   do
 311     {
 312       void *x = *slot;
 313       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 314         if (!(*callback) (x, info))
 315           break;
 316     }
 317   while (++slot < limit);
 318 }
 319
 320 /* The following function returns current size of given hash table. */
 321
 322 size_t
 323 htab_size (htab)
 324      htab_t htab;
 325 {
 326   return htab->size;
 327 }
 328
 329 /* The following function returns current number of elements in given
 330    hash table. */
 331
 332 size_t
 333 htab_elements (htab)
 334      htab_t htab;
 335 {
 336   return htab->n_elements - htab->n_deleted;
 337 }
 338
 339 /* The following function returns number of percents of fixed
 340    collisions during all work with given hash table. */
 341
 342 double
 343 htab_collisions (htab)
 344      htab_t htab;
 345 {
 346   int searches;
 347
 348   searches = htab->searches;
 349   if (searches == 0)
 350     return 0.0;
 351   return (double)htab->collisions / (double)searches;
 352 }