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 "hash.h"
  22 #include "error.h"
  23 #include <limits.h>
  24 #include <stdlib.h>
  25 #include "algorithm.h"
  26 #include "alloc.h"
  27 #include "misc.h"
  28 #include "str.h"
  29
  30 /* Hash table. */
  31 struct hsh_table
  32   {
  33     size_t used;                /* Number of filled entries. */
  34     size_t size;                /* Number of entries (a power of 2). */
  35     void **entries;             /* Hash table proper. */
  36
  37     void *aux;                  /* Auxiliary data for comparison functions. */
  38     hsh_compare_func *compare;
  39     hsh_hash_func *hash;
  40     hsh_free_func *free;
  41   };
  42
  43 /* Note for constructing hash functions:
  44
  45    You can store the hash values in the records, then compare hash
  46    values (in the compare function) before bothering to compare keys.
  47    Hash values can simply be returned from the records instead of
  48    recalculating when rehashing. */
  49
  50 /* Debugging note:
  51
  52    Since hash_probe and hash_find take void * pointers, it's easy to
  53    pass a void ** to your data by accidentally inserting an `&'
  54    reference operator where one shouldn't go.  It took me an hour to
  55    hunt down a bug like that once. */
  56 \f
  57 /* Prime numbers and hash functions. */
  58
  59 /* Returns smallest power of 2 greater than X. */
  60 static size_t
  61 next_power_of_2 (size_t x)
  62 {
  63   assert (x != 0);
  64
  65   for (;;)
  66     {
  67       /* Turn off rightmost 1-bit in x. */
  68       size_t y = x & (x - 1);
  69
  70       /* If y is 0 then x only had a single 1-bit. */
  71       if (y == 0)
  72         return 2 * x;
  73
  74       /* Otherwise turn off the next. */
  75       x = y;
  76     }
  77 }
  78
  79 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
  80 #define FNV_32_PRIME 16777619u
  81 #define FNV_32_BASIS 2166136261u
  82
  83 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
  84 unsigned
  85 hsh_hash_bytes (const void *buf_, size_t size)
  86 {
  87   const unsigned char *buf = buf_;
  88   unsigned hash;
  89
  90   assert (buf != NULL);
  91
  92   hash = FNV_32_BASIS;
  93   while (size-- > 0)
  94     hash = (hash * FNV_32_PRIME) ^ *buf++;
  95
  96   return hash;
  97 }
  98
  99 /* Fowler-Noll-Vo 32-bit hash, for strings. */
 100 unsigned
 101 hsh_hash_string (const char *s_)
 102 {
 103   const unsigned char *s = s_;
 104   unsigned hash;
 105
 106   assert (s != NULL);
 107
 108   hash = FNV_32_BASIS;
 109   while (*s != '\0')
 110     hash = (hash * FNV_32_PRIME) ^ *s++;
 111
 112   return hash;
 113 }
 114
 115 /* Hash for ints. */
 116 unsigned
 117 hsh_hash_int (int i)
 118 {
 119   return hsh_hash_bytes (&i, sizeof i);
 120 }
 121
 122 /* Hash for double. */
 123 unsigned
 124 hsh_hash_double (double d)
 125 {
 126   if (!isnan (d))
 127     return hsh_hash_bytes (&d, sizeof d);
 128   else
 129     return 0;
 130 }
 131 \f
 132 /* Hash tables. */
 133
 134 /* Creates a hash table with at least M entries.  COMPARE is a
 135    function that compares two entries and returns 0 if they are
 136    identical, nonzero otherwise; HASH returns a nonnegative hash value
 137    for an entry; FREE destroys an entry. */
 138 struct hsh_table *
 139 hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
 140             hsh_free_func *free, void *aux)
 141 {
 142   struct hsh_table *h;
 143   int i;
 144
 145   assert (size > 0);
 146   assert (compare != NULL);
 147   assert (hash != NULL);
 148
 149   h = xmalloc (sizeof *h);
 150   h->used = 0;
 151   if (size < 4)
 152     size = 4;
 153   h->size = next_power_of_2 (size);
 154   h->entries = xmalloc (sizeof *h->entries * h->size);
 155   for (i = 0; i < h->size; i++)
 156     h->entries[i] = NULL;
 157   h->aux = aux;
 158   h->compare = compare;
 159   h->hash = hash;
 160   h->free = free;
 161   return h;
 162 }
 163
 164 /* Destroys the contents of table H. */
 165 void
 166 hsh_clear (struct hsh_table *h)
 167 {
 168   int i;
 169
 170   assert (h != NULL);
 171   if (h->free)
 172     for (i = 0; i < h->size; i++)
 173       if (h->entries[i] != NULL)
 174         h->free (h->entries[i], h->aux);
 175
 176   for (i = 0; i < h->size; i++)
 177     h->entries[i] = NULL;
 178 }
 179
 180 /* Destroys table H and all its contents. */
 181 void
 182 hsh_destroy (struct hsh_table *h)
 183 {
 184   int i;
 185
 186   if (h != NULL)
 187     {
 188       if (h->free)
 189         for (i = 0; i < h->size; i++)
 190           if (h->entries[i] != NULL)
 191             h->free (h->entries[i], h->aux);
 192       free (h->entries);
 193       free (h);
 194     }
 195 }
 196
 197 /* Changes the capacity of H to NEW_SIZE. */
 198 static void
 199 hsh_rehash (struct hsh_table *h, size_t new_size)
 200 {
 201   void **begin, **end, **table_p;
 202   int i;
 203
 204   assert (h != NULL);
 205   assert (new_size >= h->used);
 206
 207   begin = h->entries;
 208   end = begin + h->size;
 209
 210   h->size = new_size;
 211   h->entries = xmalloc (sizeof *h->entries * h->size);
 212   for (i = 0; i < h->size; i++)
 213     h->entries[i] = NULL;
 214   for (table_p = begin; table_p < end; table_p++)
 215     if (*table_p != NULL)
 216       {
 217         void **entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
 218         while (*entry != NULL)
 219           if (++entry >= h->entries + h->size)
 220             entry = h->entries;
 221         *entry = *table_p;
 222       }
 223   free (begin);
 224 }
 225
 226 /* A "algo_predicate_func" that returns nonzero if DATA points
 227    to a non-null void. */
 228 static int
 229 not_null (const void *data_, void *aux UNUSED)
 230 {
 231   void *const *data = data_;
 232
 233   return *data != NULL;
 234 }
 235
 236 /* Compacts hash table H and returns a pointer to its data.  The
 237    returned data consists of hsh_count(H) non-null pointers, in
 238    no particular order, followed by a null pointer.  After
 239    calling this function, only hsh_destroy() and hsh_count() may
 240    be applied to H. */
 241 void **
 242 hsh_data (struct hsh_table *h)
 243 {
 244   size_t n;
 245
 246   assert (h != NULL);
 247   n = partition (h->entries, h->size, sizeof *h->entries,
 248                  not_null, NULL);
 249   assert (n == h->used);
 250   return h->entries;
 251 }
 252
 253 /* Dereferences void ** pointers and passes them to the hash
 254    comparison function. */
 255 static int
 256 comparison_helper (const void *a_, const void *b_, void *h_)
 257 {
 258   void *const *a = a_;
 259   void *const *b = b_;
 260   struct hsh_table *h = h_;
 261
 262   return h->compare (*a, *b, h->aux);
 263 }
 264
 265 /* Sorts hash table H based on hash comparison function.  The
 266    returned data consists of hsh_count(H) non-null pointers,
 267    sorted in order of the hash comparison function, followed by a
 268    null pointer.  After calling this function, only hsh_destroy()
 269    and hsh_count() may be applied to H. */
 270 void **
 271 hsh_sort (struct hsh_table *h)
 272 {
 273   assert (h != NULL);
 274
 275   hsh_data (h);
 276   sort (h->entries, h->used, sizeof *h->entries, comparison_helper, h);
 277   return h->entries;
 278 }
 279
 280 /* Makes and returns a copy of the pointers to the data in H.
 281    The returned data consists of hsh_count(H) non-null pointers,
 282    in no particular order, followed by a null pointer.  The hash
 283    table is not modified.  The caller is responsible for freeing
 284    the allocated data. */
 285 void **
 286 hsh_data_copy (struct hsh_table *h)
 287 {
 288   void **copy;
 289
 290   assert (h != NULL);
 291   copy = xmalloc ((h->used + 1) * sizeof *copy);
 292   copy_if (h->entries, h->size, sizeof *h->entries, copy,
 293            not_null, NULL);
 294   copy[h->used] = NULL;
 295   return copy;
 296 }
 297
 298 /* Makes and returns a copy of the pointers to the data in H.
 299    The returned data consists of hsh_count(H) non-null pointers,
 300    sorted in order of the hash comparison function, followed by a
 301    null pointer.  The hash table is not modified.  The caller is
 302    responsible for freeing the allocated data. */
 303 void **
 304 hsh_sort_copy (struct hsh_table *h)
 305 {
 306   void **copy;
 307
 308   assert (h != NULL);
 309   copy = hsh_data_copy (h);
 310   sort (copy, h->used, sizeof *copy, comparison_helper, h);
 311   return copy;
 312 }
 313 \f
 314 /* Hash entries. */
 315
 316 /* Searches hash table H for TARGET.  If found, returns a pointer
 317    to a pointer to that entry; otherwise returns a pointer to a
 318    NULL entry which *must* be used to insert a new entry having
 319    the same key data.  */
 320 inline void **
 321 hsh_probe (struct hsh_table *h, const void *target)
 322 {
 323   void **entry;
 324
 325   assert (h != NULL);
 326   assert (target != NULL);
 327
 328   /* Order of these statements is important! */
 329   if (h->used > h->size / 2)
 330     hsh_rehash (h, h->size * 2);
 331   entry = &h->entries[h->hash (target, h->aux) & (h->size - 1)];
 332
 333   while (*entry)
 334     {
 335       if (!h->compare (*entry, target, h->aux))
 336         return entry;
 337       if (++entry >= h->entries + h->size)
 338         entry = h->entries;
 339     }
 340   h->used++;
 341   return entry;
 342 }
 343
 344 /* Searches hash table H for TARGET.  If not found, inserts
 345    TARGET and returns a null pointer.  If found, returns the
 346    match, without replacing it in the table. */
 347 void *
 348 hsh_insert (struct hsh_table *h, void *target)
 349 {
 350   void **entry;
 351
 352   assert (h != NULL);
 353   assert (target != NULL);
 354
 355   entry = hsh_probe (h, target);
 356   if (*entry == NULL)
 357     {
 358       *entry = target;
 359       return NULL;
 360     }
 361   else
 362     return *entry;
 363 }
 364
 365 /* Searches hash table H for TARGET.  If not found, inserts
 366    TARGET and returns a null pointer.  If found, returns the
 367    match, after replacing it in the table by TARGET. */
 368 void *
 369 hsh_replace (struct hsh_table *h, void *target)
 370 {
 371   void **entry = hsh_probe (h, target);
 372   void *old = *entry;
 373   *entry = target;
 374   return old;
 375 }
 376
 377 /* Locates an entry matching TARGET.  Returns a pointer to the
 378    entry, or a null pointer on failure. */
 379 static inline void **
 380 locate_matching_entry (struct hsh_table *h, const void *target)
 381 {
 382   void **entry = &h->entries[h->hash (target, h->aux) & (h->size - 1)];
 383
 384   while (*entry)
 385     {
 386       if (!h->compare (*entry, target, h->aux))
 387         return entry;
 388       if (++entry >= h->entries + h->size)
 389         entry = h->entries;
 390     }
 391   return NULL;
 392 }
 393
 394 /* Returns the entry in hash table H that matches TARGET, or NULL
 395    if there is none. */
 396 void *
 397 hsh_find (struct hsh_table *h, const void *target)
 398 {
 399   void **entry = locate_matching_entry (h, target);
 400   return entry != NULL ? *entry : NULL;
 401 }
 402
 403 /* Deletes the entry in hash table H that matches TARGET.
 404    Returns nonzero if an entry was deleted.
 405
 406    Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
 407    Because our load factor is at most 1/2, the average number of
 408    moves that this algorithm makes should be at most 2 - ln 2 ~=
 409    1.65.
 410
 411    Not well tested. */
 412 int
 413 hsh_delete (struct hsh_table *h, const void *target)
 414 {
 415   void **entry = locate_matching_entry (h, target);
 416   if (entry != NULL)
 417     {
 418       ptrdiff_t i;
 419
 420       h->used--;
 421       if (h->free != NULL)
 422         h->free (*entry, h->aux);
 423       *entry = 0;
 424
 425       i = entry - h->entries;
 426       for (;;)
 427         {
 428           unsigned r;
 429           ptrdiff_t j = i;
 430
 431           do
 432             {
 433               if (--i < 0)
 434                 i = h->size - 1;
 435               if (h->entries[i] == NULL)
 436                 return 1;
 437
 438               r = h->hash (h->entries[i], h->aux) & (h->size - 1);
 439             }
 440           while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
 441           h->entries[i] = h->entries[j];
 442         }
 443     }
 444   else
 445     return 0;
 446 }
 447 \f
 448 /* Iteration. */
 449
 450 /* Finds and returns an entry in TABLE, and initializes ITER for
 451    use with hsh_next().  If TABLE is empty, returns a null
 452    pointer. */
 453 void *
 454 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
 455 {
 456   assert (h != NULL);
 457   assert (iter != NULL);
 458
 459   iter->next = 0;
 460   return hsh_next (h, iter);
 461 }
 462
 463 /* Iterates through TABLE with iterator ITER.  Returns the next
 464    entry in TABLE, or a null pointer after the last entry.
 465
 466    Entries are returned in an undefined order.  Modifying TABLE
 467    during iteration may cause some entries to be returned
 468    multiple times or not at all. */
 469 void *
 470 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
 471 {
 472   size_t i;
 473
 474   assert (h != NULL);
 475   assert (iter != NULL);
 476   assert (iter->next <= h->size);
 477
 478   for (i = iter->next; i < h->size; i++)
 479     if (h->entries[i])
 480       {
 481         iter->next = i + 1;
 482         return h->entries[i];
 483       }
 484
 485   iter->next = h->size;
 486   return NULL;
 487 }
 488 \f
 489 /* Returns the number of items in H. */
 490 size_t
 491 hsh_count (struct hsh_table *h)
 492 {
 493   assert (h != NULL);
 494
 495   return h->used;
 496 }
 497 \f
 498 /* Debug helpers. */
 499
 500 #if GLOBAL_DEBUGGING
 501 #undef NDEBUG
 502 #include "error.h"
 503 #include <stdio.h>
 504
 505 /* Displays contents of hash table H on stdout. */
 506 void
 507 hsh_dump (struct hsh_table *h)
 508 {
 509   void **entry = h->entries;
 510   int i;
 511
 512   printf (_("hash table:"));
 513   for (i = 0; i < h->size; i++)
 514     printf (" %p", *entry++);
 515   printf ("\n");
 516 }
 517
 518 /* This wrapper around hsh_probe() assures that it returns a pointer
 519    to a NULL pointer.  This function is used when it is known that the
 520    entry to be inserted does not already exist in the table. */
 521 void
 522 hsh_force_insert (struct hsh_table *h, void *p)
 523 {
 524   void **pp = hsh_probe (h, p);
 525   assert (*pp == NULL);
 526   *pp = p;
 527 }
 528
 529 /* This wrapper around hsh_find() assures that it returns non-NULL.
 530    This function is for use when it is known that the entry being
 531    searched for must exist in the table. */
 532 void *
 533 hsh_force_find (struct hsh_table *h, const void *target)
 534 {
 535   void *found = hsh_find (h, target);
 536   assert (found != NULL);
 537   return found;
 538 }
 539
 540 /* This wrapper for hsh_delete() verifies that an item really was
 541    deleted. */
 542 void
 543 hsh_force_delete (struct hsh_table *h, const void *target)
 544 {
 545   int found = hsh_delete (h, target);
 546   assert (found != 0);
 547 }
 548 #endif