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 #ifdef HAVE_STDLIB_H
  39 #include <stdlib.h>
  40 #endif
  41
  42 #include <stdio.h>
  43
  44 #include "libiberty.h"
  45 #include "hashtab.h"
  46
  47 /* The following variable is used for debugging. Its value is number
  48    of all calls of `find_hash_table_entry' for all hash tables. */
  49
  50 static int all_searches = 0;
  51
  52 /* The following variable is used for debugging. Its value is number
  53    of collisions fixed for time of work with all hash tables. */
  54
  55 static int all_collisions = 0;
  56
  57 /* The following variable is used for debugging. Its value is number
  58    of all table expansions fixed for time of work with all hash
  59    tables. */
  60
  61 static int all_expansions = 0;
  62
  63 /* This macro defines reserved value for empty table entry. */
  64
  65 #define EMPTY_ENTRY    NULL
  66
  67 /* This macro defines reserved value for table entry which contained
  68    a deleted element. */
  69
  70 #define DELETED_ENTRY  ((void *) 1)
  71
  72 /* The following function returns the nearest prime number which is
  73    greater than given source number. */
  74
  75 static unsigned long
  76 higher_prime_number (number)
  77      unsigned long number;
  78 {
  79   unsigned long i;
  80
  81   for (number = (number / 2) * 2 + 3;; number += 2)
  82     {
  83       for (i = 3; i * i <= number; i += 2)
  84         if (number % i == 0)
  85           break;
  86       if (i * i > number)
  87         return number;
  88     }
  89 }
  90
  91 /* This function creates table with length slightly longer than given
  92    source length.  Created hash table is initiated as empty (all the
  93    hash table entries are EMPTY_ENTRY).  The function returns the
  94    created hash table. */
  95
  96 hash_table_t
  97 create_hash_table (size, hash_function, eq_function)
  98      size_t size;
  99      unsigned (*hash_function) PARAMS ((hash_table_entry_t));
 100      int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t));
 101 {
 102   hash_table_t result;
 103
 104   size = higher_prime_number (size);
 105   result = (hash_table_t) xmalloc (sizeof (*result));
 106   result->entries
 107     = (hash_table_entry_t *) xmalloc (size * sizeof (hash_table_entry_t));
 108   result->size = size;
 109   result->hash_function = hash_function;
 110   result->eq_function = eq_function;
 111   result->number_of_elements = 0;
 112   result->number_of_deleted_elements = 0;
 113   result->searches = 0;
 114   result->collisions = 0;
 115   memset (result->entries, 0, size * sizeof (hash_table_entry_t));
 116   return result;
 117 }
 118
 119 /* This function frees all memory allocated for given hash table.
 120    Naturally the hash table must already exist. */
 121
 122 void
 123 delete_hash_table (htab)
 124      hash_table_t htab;
 125 {
 126   free (htab->entries);
 127   free (htab);
 128 }
 129
 130 /* This function clears all entries in the given hash table.  */
 131
 132 void
 133 empty_hash_table (htab)
 134      hash_table_t htab;
 135 {
 136   memset (htab->entries, 0, htab->size * sizeof (hash_table_entry_t));
 137 }
 138
 139 /* The following function changes size of memory allocated for the
 140    entries and repeatedly inserts the table elements.  The occupancy
 141    of the table after the call will be about 50%.  Naturally the hash
 142    table must already exist.  Remember also that the place of the
 143    table entries is changed. */
 144
 145 static void
 146 expand_hash_table (htab)
 147      hash_table_t htab;
 148 {
 149   hash_table_t new_htab;
 150   hash_table_entry_t *entry_ptr;
 151   hash_table_entry_t *new_entry_ptr;
 152
 153   new_htab = create_hash_table (htab->number_of_elements * 2,
 154                                 htab->hash_function, htab->eq_function);
 155   for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
 156        entry_ptr++)
 157     if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
 158       {
 159         new_entry_ptr = find_hash_table_entry (new_htab, *entry_ptr, 1);
 160         *new_entry_ptr = (*entry_ptr);
 161       }
 162   free (htab->entries);
 163   *htab = (*new_htab);
 164   free (new_htab);
 165 }
 166
 167 /* This function searches for hash table entry which contains element
 168    equal to given value or empty entry in which given value can be
 169    placed (if the element with given value does not exist in the
 170    table).  The function works in two regimes.  The first regime is
 171    used only for search.  The second is used for search and
 172    reservation empty entry for given value.  The table is expanded if
 173    occupancy (taking into accout also deleted elements) is more than
 174    75%.  Naturally the hash table must already exist.  If reservation
 175    flag is TRUE then the element with given value should be inserted
 176    into the table entry before another call of
 177    `find_hash_table_entry'. */
 178
 179 hash_table_entry_t *
 180 find_hash_table_entry (htab, element, reserve)
 181      hash_table_t htab;
 182      hash_table_entry_t element;
 183      int reserve;
 184 {
 185   hash_table_entry_t *entry_ptr;
 186   hash_table_entry_t *first_deleted_entry_ptr;
 187   unsigned index, hash_value, secondary_hash_value;
 188
 189   if (htab->size * 3 <= htab->number_of_elements * 4)
 190     {
 191       all_expansions++;
 192       expand_hash_table (htab);
 193     }
 194   hash_value = (*htab->hash_function) (element);
 195   secondary_hash_value = 1 + hash_value % (htab->size - 2);
 196   index = hash_value % htab->size;
 197   htab->searches++;
 198   all_searches++;
 199   first_deleted_entry_ptr = NULL;
 200   for (;;htab->collisions++, all_collisions++)
 201     {
 202       entry_ptr = htab->entries + index;
 203       if (*entry_ptr == EMPTY_ENTRY)
 204         {
 205           if (reserve)
 206             {
 207               htab->number_of_elements++;
 208               if (first_deleted_entry_ptr != NULL)
 209                 {
 210                   entry_ptr = first_deleted_entry_ptr;
 211                   *entry_ptr = EMPTY_ENTRY;
 212                 }
 213             }
 214           break;
 215         }
 216       else if (*entry_ptr != DELETED_ENTRY)
 217         {
 218           if ((*htab->eq_function) (*entry_ptr, element))
 219             break;
 220         }
 221       else if (first_deleted_entry_ptr == NULL)
 222         first_deleted_entry_ptr = entry_ptr;
 223       index += secondary_hash_value;
 224       if (index >= htab->size)
 225         index -= htab->size;
 226     }
 227   return entry_ptr;
 228 }
 229
 230 /* This function deletes element with given value from hash table.
 231    The hash table entry value will be `DELETED_ENTRY' after the
 232    function call.  Naturally the hash table must already exist.  Hash
 233    table entry for given value should be not empty (or deleted). */
 234
 235 void
 236 remove_element_from_hash_table_entry (htab, element)
 237      hash_table_t htab;
 238      hash_table_entry_t element;
 239 {
 240   hash_table_entry_t *entry_ptr;
 241
 242   entry_ptr = find_hash_table_entry (htab, element, 0);
 243   *entry_ptr = DELETED_ENTRY;
 244   htab->number_of_deleted_elements++;
 245 }
 246
 247 /* This function clears a specified slot in a hash table.
 248    It is useful when you've already done the lookup and don't want to
 249    do it again.  */
 250
 251 void
 252 clear_hash_table_slot (htab, slot)
 253      hash_table_t htab;
 254      hash_table_entry_t *slot;
 255 {
 256   if (slot < htab->entries || slot >= htab->entries + htab->size
 257       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 258     abort ();
 259   *slot = DELETED_ENTRY;
 260   htab->number_of_deleted_elements++;
 261 }
 262
 263 /* This function scans over the entire hash table calling
 264    CALLBACK for each live entry.  If CALLBACK returns false,
 265    the iteration stops.  INFO is passed as CALLBACK's second
 266    argument.  */
 267
 268 void
 269 traverse_hash_table (htab, callback, info)
 270      hash_table_t htab;
 271      int (*callback) PARAMS ((hash_table_entry_t, void *));
 272      void *info;
 273 {
 274   hash_table_entry_t *entry_ptr;
 275   for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
 276        entry_ptr++)
 277     if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
 278       if (!callback (*entry_ptr, info))
 279         break;
 280 }
 281
 282 /* The following function returns current size of given hash table. */
 283
 284 size_t
 285 hash_table_size (htab)
 286      hash_table_t htab;
 287 {
 288   return htab->size;
 289 }
 290
 291 /* The following function returns current number of elements in given
 292    hash table. */
 293
 294 size_t
 295 hash_table_elements_number (htab)
 296      hash_table_t htab;
 297 {
 298   return htab->number_of_elements - htab->number_of_deleted_elements;
 299 }
 300
 301 /* The following function returns number of percents of fixed
 302    collisions during all work with given hash table. */
 303
 304 int
 305 hash_table_collisions (htab)
 306      hash_table_t htab;
 307 {
 308   int searches;
 309
 310   searches = htab->searches;
 311   if (searches == 0)
 312     searches++;
 313   return htab->collisions * 100 / searches;
 314 }
 315
 316 /* The following function returns number of percents of fixed
 317    collisions during all work with all hash tables. */
 318
 319 int
 320 all_hash_table_collisions ()
 321 {
 322   int searches;
 323
 324   searches = all_searches;
 325   if (searches == 0)
 326     searches++;
 327   return all_collisions * 100 / searches;
 328 }