hash.c

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