lib/hash.c

   1 /* hash.c -- hash table maintenance
   2    Copyright (C) 1995 Free Software Foundation, Inc.
   3    Written by Greg McGary <gkm@gnu.ai.mit.edu>
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 */
  19
  20 #include <config.h>
  21 #include <stdio.h>
  22 #include "hash.h"
  23 #include "error.h"
  24 #include "system.h"
  25 #include "xalloc.h"
  26
  27 static void hash_rehash __P((struct hash_table* ht));
  28 static unsigned long round_up_2 __P((unsigned long rough));
  29
  30 /* Implement double hashing with open addressing.  The table size is
  31    always a power of two.  The secondary (`increment') hash function
  32    is forced to return an odd-value, in order to be relatively prime
  33    to the table size.  This guarantees that the increment can
  34    potentially hit every slot in the table during collision
  35    resolution.  */
  36
  37 void *hash_deleted_item = &hash_deleted_item;
  38
  39 /* Force the table size to be a power of two, possibly rounding up the
  40    given size.  */
  41
  42 void
  43 hash_init (struct hash_table* ht, unsigned long size,
  44            hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
  45 {
  46   ht->ht_size = round_up_2 (size);
  47   if (ht->ht_size > (128 * 1024)) /* prevent size from getting out of hand */
  48     ht->ht_size /= 2;
  49   ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
  50   if (ht->ht_vec == 0)
  51     error (1, 0, _("can't allocate %ld bytes for hash table: memory exhausted"),
  52            ht->ht_size * sizeof(struct token *));
  53   ht->ht_capacity = ht->ht_size * 15 / 16; /* 93.75% loading factor */
  54   ht->ht_fill = 0;
  55   ht->ht_collisions = 0;
  56   ht->ht_lookups = 0;
  57   ht->ht_rehashes = 0;
  58   ht->ht_hash_1 = hash_1;
  59   ht->ht_hash_2 = hash_2;
  60   ht->ht_compare = hash_cmp;
  61 }
  62
  63 /* Load an array of items into `ht'.  */
  64
  65 void
  66 hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size)
  67 {
  68   char *items = (char *) item_table;
  69   while (cardinality--)
  70     {
  71       hash_insert (ht, items);
  72       items += size;
  73     }
  74 }
  75
  76 /* Returns the address of the table slot matching `key'.  If `key' is
  77    not found, return the address of an empty slot suitable for
  78    inserting `key'.  The caller is responsible for incrementing
  79    ht_fill on insertion.  */
  80
  81 void **
  82 hash_find_slot (struct hash_table* ht, void const *key)
  83 {
  84   void **slot;
  85   void **deleted_slot = 0;
  86   unsigned int hash_2 = 0;
  87   unsigned int hash_1 = (*ht->ht_hash_1) (key);
  88
  89   ht->ht_lookups++;
  90   for (;;)
  91     {
  92       hash_1 %= ht->ht_size;
  93       slot = &ht->ht_vec[hash_1];
  94
  95       if (*slot == 0)
  96         return slot;
  97       if (*slot == hash_deleted_item)
  98         {
  99           if (deleted_slot == 0)
 100             deleted_slot = slot;
 101         }
 102       else
 103         {
 104           if (key == *slot)
 105             return slot;
 106           if ((*ht->ht_compare) (key, *slot) == 0)
 107             return slot;
 108           ht->ht_collisions++;
 109         }
 110       if (!hash_2)
 111           hash_2 = (*ht->ht_hash_2) (key) | 1;
 112       hash_1 += hash_2;
 113     }
 114 }
 115
 116 void *
 117 hash_find_item (struct hash_table* ht, void const *key)
 118 {
 119   void **slot = hash_find_slot (ht, key);
 120   return ((HASH_VACANT (*slot)) ? 0 : *slot);
 121 }
 122
 123 void *
 124 hash_insert (struct hash_table* ht, void *item)
 125 {
 126   void **slot = hash_find_slot (ht, item);
 127   return hash_insert_at (ht, item, slot);
 128 }
 129
 130 void *
 131 hash_insert_at (struct hash_table* ht, void *item, void const *slot)
 132 {
 133   void *old_item = *(void **) slot;
 134   if (HASH_VACANT (old_item))
 135     {
 136       ht->ht_fill++;
 137       old_item = item;
 138     }
 139   *(void const **) slot = item;
 140   if (ht->ht_fill >= ht->ht_capacity)
 141     hash_rehash (ht);
 142   return old_item;
 143 }
 144
 145 void *
 146 hash_delete (struct hash_table* ht, void const *item)
 147 {
 148   void **slot = hash_find_slot (ht, item);
 149   return hash_delete_at (ht, slot);
 150 }
 151
 152 void *
 153 hash_delete_at (struct hash_table* ht, void const *slot)
 154 {
 155   void *item = *(void **) slot;
 156   if (!HASH_VACANT (item))
 157     {
 158       *(void const **) slot = hash_deleted_item;
 159       ht->ht_fill--;
 160       return item;
 161     }
 162   else
 163     return 0;
 164 }
 165
 166 void
 167 hash_free_items (struct hash_table* ht)
 168 {
 169   void **vec = ht->ht_vec;
 170   void **end = &vec[ht->ht_size];
 171   for (; vec < end; vec++)
 172     {
 173       void *item = *vec;
 174       if (!HASH_VACANT (item))
 175         free (item);
 176       *vec = 0;
 177     }
 178   ht->ht_fill = 0;
 179 }
 180
 181 void
 182 hash_delete_items (struct hash_table* ht)
 183 {
 184   void **vec = ht->ht_vec;
 185   void **end = &vec[ht->ht_size];
 186   for (; vec < end; vec++)
 187     *vec = 0;
 188   ht->ht_fill = 0;
 189   ht->ht_collisions = 0;
 190   ht->ht_lookups = 0;
 191   ht->ht_rehashes = 0;
 192 }
 193
 194 void
 195 hash_free (struct hash_table* ht, int free_items)
 196 {
 197   if (free_items)
 198     hash_free_items (ht);
 199   free (ht->ht_vec);
 200   ht->ht_vec = 0;
 201   ht->ht_fill = 0;
 202   ht->ht_capacity = 0;
 203 }
 204
 205 void
 206 hash_map (struct hash_table *ht, hash_map_func_t map)
 207 {
 208   void **slot;
 209   void **end = &ht->ht_vec[ht->ht_size];
 210
 211   for (slot = ht->ht_vec; slot < end; slot++)
 212     {
 213       if (!HASH_VACANT (*slot))
 214         (*map) (*slot);
 215     }
 216 }
 217
 218 /* Double the size of the hash table in the event of overflow... */
 219
 220 static void
 221 hash_rehash (struct hash_table* ht)
 222 {
 223   unsigned long old_ht_size = ht->ht_size;
 224   void **old_vec = ht->ht_vec;
 225   void **ovp;
 226   void **slot;
 227
 228   ht->ht_size *= 2;
 229   ht->ht_rehashes++;
 230   ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
 231   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
 232
 233   for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
 234     {
 235       if (*ovp == 0)
 236         continue;
 237       slot = hash_find_slot (ht, *ovp);
 238       *slot = *ovp;
 239     }
 240   free (old_vec);
 241 }
 242
 243 void
 244 hash_print_stats (struct hash_table *ht, FILE *out_FILE)
 245 {
 246   fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
 247            100.0 * (double) ht->ht_fill / (double) ht->ht_size);
 248   fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
 249   fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
 250            (ht->ht_lookups
 251             ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
 252             : 0));
 253 }
 254
 255 /* Dump all items into a NULL-terminated vector.  Use the
 256    user-supplied vector, or malloc one.  */
 257
 258 void**
 259 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
 260 {
 261   void **vector;
 262   void **slot;
 263   void **end = &ht->ht_vec[ht->ht_size];
 264
 265   if (vector_0 == 0)
 266     vector_0 = MALLOC (void *, ht->ht_fill + 1);
 267   vector = vector_0;
 268
 269   for (slot = ht->ht_vec; slot < end; slot++)
 270     if (!HASH_VACANT (*slot))
 271       *vector++ = *slot;
 272   *vector = 0;
 273
 274   if (compare)
 275     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
 276   return vector_0;
 277 }
 278
 279 /* Round a given number up to the nearest power of 2. */
 280
 281 static unsigned long
 282 round_up_2 (unsigned long rough)
 283 {
 284   int round;
 285
 286   round = 1;
 287   while (rough)
 288     {
 289       round <<= 1;
 290       rough >>= 1;
 291     }
 292   return round;
 293 }