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