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