src/hash.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
   3    Written by Ben Pfaff <blp@gnu.org>.
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    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
  18    02111-1307, USA. */
  19
  20 #include <config.h>
  21 #include <assert.h>
  22 #include <limits.h>
  23 #include <stdlib.h>
  24 #include "alloc.h"
  25 #include "hash.h"
  26 #include "quicksort.h"
  27 #include "str.h"
  28
  29 /* Hash table. */
  30 struct hsh_table
  31   {
  32     size_t used;                /* Number of filled entries. */
  33     size_t size;                /* Number of entries (a power of 2). */
  34     void **entries;             /* Hash table proper. */
  35
  36     void *param;
  37     hsh_compare_func *compare;
  38     hsh_hash_func *hash;
  39     hsh_free_func *free;
  40   };
  41
  42 /* Note for constructing hash functions:
  43
  44    You can store the hash values in the records, then compare hash
  45    values (in the compare function) before bothering to compare keys.
  46    Hash values can simply be returned from the records instead of
  47    recalculating when rehashing. */
  48
  49 /* Debugging note:
  50
  51    Since hash_probe and hash_find take void * pointers, it's easy to
  52    pass a void ** to your data by accidentally inserting an `&'
  53    reference operator where one shouldn't go.  It took me an hour to
  54    hunt down a bug like that once. */
  55 \f
  56 /* Prime numbers and hash functions. */
  57
  58 /* Returns smallest power of 2 greater than X. */
  59 static size_t
  60 next_power_of_2 (size_t x)
  61 {
  62   assert (x != 0);
  63
  64   for (;;)
  65     {
  66       /* Turn off rightmost 1-bit in x. */
  67       size_t y = x & (x - 1);
  68
  69       /* If y is 0 then x only had a single 1-bit. */
  70       if (y == 0)
  71         return 2 * x;
  72
  73       /* Otherwise turn off the next. */
  74       x = y;
  75     }
  76 }
  77
  78 /* Colin Plumb's "one-at-a-time" hash, for bytes. */
  79 unsigned
  80 hsh_hash_bytes (const void *buf_, size_t size)
  81 {
  82   const unsigned char *buf = buf_;
  83   unsigned hash = 0;
  84   while (size-- > 0)
  85     {
  86       hash += *buf++;
  87       hash += (hash << 10);
  88       hash ^= (hash >> 6);
  89     }
  90   hash += (hash << 3);
  91   hash ^= (hash >> 11);
  92   hash += (hash << 15);
  93   return hash;
  94 }
  95
  96 /* Colin Plumb's "one-at-a-time" hash, for strings. */
  97 unsigned
  98 hsh_hash_string (const char *s_)
  99 {
 100   const unsigned char *s = s_;
 101   unsigned hash = 0;
 102   while (*s != '\0')
 103     {
 104       hash += *s++;
 105       hash += (hash << 10);
 106       hash ^= (hash >> 6);
 107     }
 108   hash += (hash << 3);
 109   hash ^= (hash >> 11);
 110   hash += (hash << 15);
 111   return hash;
 112 }
 113
 114 /* Hash for ints. */
 115 unsigned
 116 hsh_hash_int (int i)
 117 {
 118   return hsh_hash_bytes (&i, sizeof i);
 119 }
 120 \f
 121 /* Hash tables. */
 122
 123 /* Creates a hash table with at least M entries.  COMPARE is a
 124    function that compares two entries and returns 0 if they are
 125    identical, nonzero otherwise; HASH returns a nonnegative hash value
 126    for an entry; FREE destroys an entry. */
 127 struct hsh_table *
 128 hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
 129             hsh_free_func *free, void *param)
 130 {
 131   struct hsh_table *h = xmalloc (sizeof *h);
 132   int i;
 133
 134   h->used = 0;
 135   h->size = next_power_of_2 (size);
 136   h->entries = xmalloc (sizeof *h->entries * h->size);
 137   for (i = 0; i < h->size; i++)
 138     h->entries[i] = NULL;
 139   h->param = param;
 140   h->compare = compare;
 141   h->hash = hash;
 142   h->free = free;
 143   return h;
 144 }
 145
 146 /* Destroys the contents of table H. */
 147 void
 148 hsh_clear (struct hsh_table *h)
 149 {
 150   int i;
 151
 152   if (h->free)
 153     for (i = 0; i < h->size; i++)
 154       if (h->entries[i] != NULL)
 155         h->free (h->entries[i], h->param);
 156
 157   for (i = 0; i < h->size; i++)
 158     h->entries[i] = NULL;
 159 }
 160
 161 /* Destroys table H and all its contents. */
 162 void
 163 hsh_destroy (struct hsh_table *h)
 164 {
 165   int i;
 166
 167   if (h == NULL)
 168     return;
 169   if (h->free)
 170     for (i = 0; i < h->size; i++)
 171       if (h->entries[i] != NULL)
 172         h->free (h->entries[i], h->param);
 173   free (h->entries);
 174   free (h);
 175 }
 176
 177 /* Changes the capacity of H to NEW_SIZE. */
 178 static void
 179 hsh_rehash (struct hsh_table *h, size_t new_size)
 180 {
 181   void **begin = h->entries;
 182   void **end = &h->entries[h->size];
 183   void **table_p;
 184   int i;
 185
 186   h->size = new_size;
 187   h->entries = xmalloc (sizeof *h->entries * h->size);
 188   for (i = 0; i < h->size; i++)
 189     h->entries[i] = NULL;
 190   for (table_p = begin; table_p < end; table_p++)
 191     {
 192       void **entry;
 193
 194       if (*table_p == NULL)
 195         continue;
 196       entry = &h->entries[h->hash (*table_p, h->param) & (h->size - 1)];
 197       while (*entry)
 198         if (--entry < h->entries)
 199           entry = &h->entries[h->size - 1];
 200       *entry = *table_p;
 201     }
 202   free (begin);
 203 }
 204
 205 /* hsh_sort() helper function that ensures NULLs are sorted after the
 206    rest of the table. */
 207 static int
 208 sort_nulls_last (const void *a_, const void *b_, void *h_)
 209 {
 210   void *a = *(void **) a_;
 211   void *b = *(void **) b_;
 212   struct hsh_table *h = h_;
 213
 214   if (a != NULL)
 215     {
 216       if (b != NULL)
 217         return h->compare (a, b, h->param);
 218       else
 219         return -1;
 220     }
 221   else
 222     {
 223       if (b != NULL)
 224         return +1;
 225       else
 226         return 0;
 227     }
 228 }
 229
 230 /* Sorts hash table H based on hash comparison function.  NULLs
 231    are sent to the end of the table.  The resultant table is
 232    returned (it is guaranteed to be NULL-terminated).  H should
 233    not be used again as a hash table until and unless hsh_clear()
 234    called. */
 235 void **
 236 hsh_sort (struct hsh_table *h)
 237 {
 238   quicksort (h->entries, h->size, sizeof *h->entries, sort_nulls_last, h);
 239   return h->entries;
 240 }
 241 \f
 242 /* Hash entries. */
 243
 244 /* Searches hash table H for TARGET.  If found, returns a pointer to a
 245    pointer to that entry; otherwise returns a pointer to a NULL entry
 246    which _must_ be used to insert a new entry having the same key
 247    data.  */
 248 inline void **
 249 hsh_probe (struct hsh_table *h, const void *target)
 250 {
 251   void **entry;
 252
 253   /* Order of these statements is important! */
 254   if (h->used > h->size / 2)
 255     hsh_rehash (h, h->size * 2);
 256   entry = &h->entries[h->hash (target, h->param) & (h->size - 1)];
 257
 258   while (*entry)
 259     {
 260       if (!h->compare (*entry, target, h->param))
 261         return entry;
 262       if (--entry < h->entries)
 263         entry = &h->entries[h->size - 1];
 264     }
 265   h->used++;
 266   return entry;
 267 }
 268
 269 /* Locates an entry matching TARGET.  Returns a pointer to the
 270    entry, or a null pointer on failure. */
 271 static inline void **
 272 locate_matching_entry (struct hsh_table *h, const void *target)
 273 {
 274   void **entry = &h->entries[h->hash (target, h->param) & (h->size - 1)];
 275
 276   while (*entry)
 277     {
 278       if (!h->compare (*entry, target, h->param))
 279         return entry;
 280       if (--entry < h->entries)
 281         entry = &h->entries[h->size - 1];
 282     }
 283   return NULL;
 284 }
 285
 286 /* Returns the entry in hash table H that matches TARGET, or NULL
 287    if there is none. */
 288 void *
 289 hsh_find (struct hsh_table *h, const void *target)
 290 {
 291   void **entry = locate_matching_entry (h, target);
 292   return entry != NULL ? *entry : NULL;
 293 }
 294
 295 /* Deletes the entry in hash table H that matches TARGET.
 296    Returns nonzero if an entry was deleted.
 297
 298    Note: this function is very slow because it rehashes the
 299    entire table.  Don't use this hash table implementation if
 300    deletion is a common operation. */
 301 int
 302 hsh_delete (struct hsh_table *h, const void *target)
 303 {
 304   void **entry = locate_matching_entry (h, target);
 305   if (h->free != NULL)
 306     {
 307       h->free (*entry, h->param);
 308       *entry = 0;
 309       hsh_rehash (h, h->size);
 310       return 1;
 311     }
 312   else
 313     return 0;
 314 }
 315 \f
 316 /* Iteration. */
 317
 318 /* Finds and returns an entry in TABLE, and initializes ITER for
 319    use with hsh_next().  If TABLE is empty, returns a null
 320    pointer. */
 321 void *
 322 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
 323 {
 324   assert (h != NULL);
 325   assert (iter != NULL);
 326
 327   iter->next = 0;
 328   return hsh_next (h, iter);
 329 }
 330
 331 /* Iterates through TABLE with iterator ITER.  Returns the next
 332    entry in TABLE, or a null pointer after the last entry.
 333
 334    Entries are returned in an undefined order.  Modifying TABLE
 335    during iteration may cause some entries to be returned
 336    multiple times or not at all. */
 337 void *
 338 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
 339 {
 340   size_t i;
 341
 342   assert (h != NULL);
 343   assert (iter != NULL);
 344   assert (iter->next <= h->size);
 345
 346   for (i = iter->next; i < h->size; i++)
 347     if (h->entries[i])
 348       {
 349         iter->next = i + 1;
 350         return h->entries[i];
 351       }
 352
 353   iter->next = h->size;
 354   return NULL;
 355 }
 356 \f
 357 /* Returns the number of items in H. */
 358 size_t
 359 hsh_count (struct hsh_table *h)
 360 {
 361   assert (h != NULL);
 362
 363   return h->used;
 364 }
 365 \f
 366 /* Debug helpers. */
 367
 368 #if GLOBAL_DEBUGGING
 369 #undef NDEBUG
 370 #include <assert.h>
 371 #include <stdio.h>
 372
 373 /* Displays contents of hash table H on stdout. */
 374 void
 375 hsh_dump (struct hsh_table *h)
 376 {
 377   void **entry = h->entries;
 378   int i;
 379
 380   printf (_("hash table:"));
 381   for (i = 0; i < h->size; i++)
 382     printf (" %p", *entry++);
 383   printf ("\n");
 384 }
 385
 386 /* This wrapper around hsh_probe() assures that it returns a pointer
 387    to a NULL pointer.  This function is used when it is known that the
 388    entry to be inserted does not already exist in the table. */
 389 void
 390 hsh_force_insert (struct hsh_table *h, void *p)
 391 {
 392   void **pp = hsh_probe (h, p);
 393   assert (*pp == NULL);
 394   *pp = p;
 395 }
 396
 397 /* This wrapper around hsh_find() assures that it returns non-NULL.
 398    This function is for use when it is known that the entry being
 399    searched for must exist in the table. */
 400 void *
 401 hsh_force_find (struct hsh_table *h, const void *target)
 402 {
 403   void *found = hsh_find (h, target);
 404   assert (found != NULL);
 405   return found;
 406 }
 407
 408 /* This wrapper for hsh_delete() verifies that an item really was
 409    deleted. */
 410 void
 411 hsh_force_delete (struct hsh_table *h, const void *target)
 412 {
 413   int found = hsh_delete (h, target);
 414   assert (found != 0);
 415 }
 416 #endif