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