hash.c

   1 /* hash.c -- hash table maintenance
   2    Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc.
   3    Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
   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 "make.h"
  21 #include "hash.h"
  22
  23 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
  24 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
  25 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
  26 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
  27
  28 static void hash_rehash __P((struct hash_table* ht));
  29 static unsigned long round_up_2 __P((unsigned long rough));
  30
  31 /* Implement double hashing with open addressing.  The table size is
  32    always a power of two.  The secondary (`increment') hash function
  33    is forced to return an odd-value, in order to be relatively prime
  34    to the table size.  This guarantees that the increment can
  35    potentially hit every slot in the table during collision
  36    resolution.  */
  37
  38 void *hash_deleted_item = &hash_deleted_item;
  39
  40 /* Force the table size to be a power of two, possibly rounding up the
  41    given size.  */
  42
  43 void
  44 hash_init (struct hash_table *ht, unsigned long size,
  45            hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
  46 {
  47   ht->ht_size = round_up_2 (size);
  48   ht->ht_empty_slots = ht->ht_size;
  49   ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
  50   if (ht->ht_vec == 0)
  51     {
  52       fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"),
  53                ht->ht_size * sizeof(struct token *));
  54       exit (1);
  55     }
  56
  57   ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
  58   ht->ht_fill = 0;
  59   ht->ht_collisions = 0;
  60   ht->ht_lookups = 0;
  61   ht->ht_rehashes = 0;
  62   ht->ht_hash_1 = hash_1;
  63   ht->ht_hash_2 = hash_2;
  64   ht->ht_compare = hash_cmp;
  65 }
  66
  67 /* Load an array of items into `ht'.  */
  68
  69 void
  70 hash_load (struct hash_table *ht, void *item_table,
  71            unsigned long cardinality, unsigned long size)
  72 {
  73   char *items = (char *) item_table;
  74   while (cardinality--)
  75     {
  76       hash_insert (ht, items);
  77       items += size;
  78     }
  79 }
  80
  81 /* Returns the address of the table slot matching `key'.  If `key' is
  82    not found, return the address of an empty slot suitable for
  83    inserting `key'.  The caller is responsible for incrementing
  84    ht_fill on insertion.  */
  85
  86 void **
  87 hash_find_slot (struct hash_table *ht, const void *key)
  88 {
  89   void **slot;
  90   void **deleted_slot = 0;
  91   unsigned int hash_2 = 0;
  92   unsigned int hash_1 = (*ht->ht_hash_1) (key);
  93
  94   ht->ht_lookups++;
  95   for (;;)
  96     {
  97       hash_1 &= (ht->ht_size - 1);
  98       slot = &ht->ht_vec[hash_1];
  99
 100       if (*slot == 0)
 101         return (deleted_slot ? deleted_slot : slot);
 102       if (*slot == hash_deleted_item)
 103         {
 104           if (deleted_slot == 0)
 105             deleted_slot = slot;
 106         }
 107       else
 108         {
 109           if (key == *slot)
 110             return slot;
 111           if ((*ht->ht_compare) (key, *slot) == 0)
 112             return slot;
 113           ht->ht_collisions++;
 114         }
 115       if (!hash_2)
 116           hash_2 = (*ht->ht_hash_2) (key) | 1;
 117       hash_1 += hash_2;
 118     }
 119 }
 120
 121 void *
 122 hash_find_item (struct hash_table *ht, const void *key)
 123 {
 124   void **slot = hash_find_slot (ht, key);
 125   return ((HASH_VACANT (*slot)) ? 0 : *slot);
 126 }
 127
 128 void *
 129 hash_insert (struct hash_table *ht, void *item)
 130 {
 131   void **slot = hash_find_slot (ht, item);
 132   void *old_item = slot ? *slot : 0;
 133   hash_insert_at (ht, item, slot);
 134   return ((HASH_VACANT (old_item)) ? 0 : old_item);
 135 }
 136
 137 void *
 138 hash_insert_at (struct hash_table *ht, void *item, const void *slot)
 139 {
 140   void *old_item = *(void **) slot;
 141   if (HASH_VACANT (old_item))
 142     {
 143       ht->ht_fill++;
 144       if (old_item == 0)
 145         ht->ht_empty_slots--;
 146       old_item = item;
 147     }
 148   *(void const **) slot = item;
 149   if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
 150     {
 151       hash_rehash (ht);
 152       return (void *) hash_find_slot (ht, item);
 153     }
 154   else
 155     return (void *) slot;
 156 }
 157
 158 void *
 159 hash_delete (struct hash_table *ht, const void *item)
 160 {
 161   void **slot = hash_find_slot (ht, item);
 162   return hash_delete_at (ht, slot);
 163 }
 164
 165 void *
 166 hash_delete_at (struct hash_table *ht, const void *slot)
 167 {
 168   void *item = *(void **) slot;
 169   if (!HASH_VACANT (item))
 170     {
 171       *(void const **) slot = hash_deleted_item;
 172       ht->ht_fill--;
 173       return item;
 174     }
 175   else
 176     return 0;
 177 }
 178
 179 void
 180 hash_free_items (struct hash_table *ht)
 181 {
 182   void **vec = ht->ht_vec;
 183   void **end = &vec[ht->ht_size];
 184   for (; vec < end; vec++)
 185     {
 186       void *item = *vec;
 187       if (!HASH_VACANT (item))
 188         free (item);
 189       *vec = 0;
 190     }
 191   ht->ht_fill = 0;
 192   ht->ht_empty_slots = ht->ht_size;
 193 }
 194
 195 void
 196 hash_delete_items (struct hash_table *ht)
 197 {
 198   void **vec = ht->ht_vec;
 199   void **end = &vec[ht->ht_size];
 200   for (; vec < end; vec++)
 201     *vec = 0;
 202   ht->ht_fill = 0;
 203   ht->ht_collisions = 0;
 204   ht->ht_lookups = 0;
 205   ht->ht_rehashes = 0;
 206   ht->ht_empty_slots = ht->ht_size;
 207 }
 208
 209 void
 210 hash_free (struct hash_table *ht, int free_items)
 211 {
 212   if (free_items)
 213     hash_free_items (ht);
 214   else
 215     {
 216       ht->ht_fill = 0;
 217       ht->ht_empty_slots = ht->ht_size;
 218     }
 219   free (ht->ht_vec);
 220   ht->ht_vec = 0;
 221   ht->ht_capacity = 0;
 222 }
 223
 224 void
 225 hash_map (struct hash_table *ht, hash_map_func_t map)
 226 {
 227   void **slot;
 228   void **end = &ht->ht_vec[ht->ht_size];
 229
 230   for (slot = ht->ht_vec; slot < end; slot++)
 231     {
 232       if (!HASH_VACANT (*slot))
 233         (*map) (*slot);
 234     }
 235 }
 236
 237 void
 238 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
 239 {
 240   void **slot;
 241   void **end = &ht->ht_vec[ht->ht_size];
 242
 243   for (slot = ht->ht_vec; slot < end; slot++)
 244     {
 245       if (!HASH_VACANT (*slot))
 246         (*map) (*slot, arg);
 247     }
 248 }
 249
 250 /* Double the size of the hash table in the event of overflow... */
 251
 252 static void
 253 hash_rehash (struct hash_table *ht)
 254 {
 255   unsigned long old_ht_size = ht->ht_size;
 256   void **old_vec = ht->ht_vec;
 257   void **ovp;
 258
 259   if (ht->ht_fill >= ht->ht_capacity)
 260     {
 261       ht->ht_size *= 2;
 262       ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
 263     }
 264   ht->ht_rehashes++;
 265   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
 266
 267   for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
 268     {
 269       if (! HASH_VACANT (*ovp))
 270         {
 271           void **slot = hash_find_slot (ht, *ovp);
 272           *slot = *ovp;
 273         }
 274     }
 275   ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
 276   free (old_vec);
 277 }
 278
 279 void
 280 hash_print_stats (struct hash_table *ht, FILE *out_FILE)
 281 {
 282   /* GKM FIXME: honor NO_FLOAT */
 283   fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
 284            100.0 * (double) ht->ht_fill / (double) ht->ht_size);
 285   fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
 286   fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
 287            (ht->ht_lookups
 288             ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
 289             : 0));
 290 }
 291
 292 /* Dump all items into a NULL-terminated vector.  Use the
 293    user-supplied vector, or malloc one.  */
 294
 295 void **
 296 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
 297 {
 298   void **vector;
 299   void **slot;
 300   void **end = &ht->ht_vec[ht->ht_size];
 301
 302   if (vector_0 == 0)
 303     vector_0 = MALLOC (void *, ht->ht_fill + 1);
 304   vector = vector_0;
 305
 306   for (slot = ht->ht_vec; slot < end; slot++)
 307     if (!HASH_VACANT (*slot))
 308       *vector++ = *slot;
 309   *vector = 0;
 310
 311   if (compare)
 312     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
 313   return vector_0;
 314 }
 315
 316 /* Round a given number up to the nearest power of 2. */
 317
 318 static unsigned long
 319 round_up_2 (unsigned long n)
 320 {
 321   n |= (n >> 1);
 322   n |= (n >> 2);
 323   n |= (n >> 4);
 324   n |= (n >> 8);
 325   n |= (n >> 16);
 326
 327 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
 328   /* We only need this on systems where unsigned long is >32 bits.  */
 329   n |= (n >> 32);
 330 #endif
 331
 332   return n + 1;
 333 }