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