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 a pointer to the
 235    entry, or a null pointer on failure. */
 236 static inline unsigned
 237 locate_matching_entry (struct hsh_table *h, const void *target)
 238 {
 239   unsigned i = h->hash (target, h->aux);
 240
 241   assert (h->hash_ordered);
 242   for (;;)
 243     {
 244       void *entry;
 245       i &= h->size - 1;
 246       entry = h->entries[i];
 247       if (entry == NULL || !h->compare (entry, target, h->aux))
 248         return i;
 249       i--;
 250     }
 251 }
 252
 253 /* Changes the capacity of H to NEW_SIZE, which must be a
 254    positive power of 2 at least as large as the number of
 255    elements in H. */
 256 static void
 257 rehash (struct hsh_table *h, size_t new_size)
 258 {
 259   void **begin, **end, **table_p;
 260   int i;
 261
 262   assert (h != NULL);
 263   assert (new_size >= h->used);
 264
 265   /* Verify that NEW_SIZE is a positive power of 2. */
 266   assert (new_size > 0 && (new_size & (new_size - 1)) == 0);
 267
 268   begin = h->entries;
 269   end = begin + h->size;
 270
 271   h->size = new_size;
 272   h->entries = xnmalloc (h->size, sizeof *h->entries);
 273   for (i = 0; i < h->size; i++)
 274     h->entries[i] = NULL;
 275   for (table_p = begin; table_p < end; table_p++)
 276     {
 277       void *entry = *table_p;
 278       if (entry != NULL)
 279         h->entries[locate_matching_entry (h, entry)] = entry;
 280     }
 281   free (begin);
 282
 283 #ifndef NDEBUG
 284   h->hash_ordered = true;
 285 #endif
 286 }
 287
 288 /* A "algo_predicate_func" that returns nonzero if DATA points
 289    to a non-null void. */
 290 static int
 291 not_null (const void *data_, void *aux UNUSED)
 292 {
 293   void *const *data = data_;
 294
 295   return *data != NULL;
 296 }
 297
 298 /* Compacts hash table H and returns a pointer to its data.  The
 299    returned data consists of hsh_count(H) non-null pointers, in
 300    no particular order, followed by a null pointer.
 301
 302    After calling this function, only hsh_destroy() and
 303    hsh_count() should be applied to H.  hsh_first() and
 304    hsh_next() could also be used, but you're better off just
 305    iterating through the returned array.
 306
 307    This function is intended for use in situations where data
 308    processing occurs in two phases.  In the first phase, data is
 309    added, removed, and searched for within a hash table.  In the
 310    second phase, the contents of the hash table are output and
 311    the hash property itself is no longer of interest.
 312
 313    Use hsh_sort() instead, if the second phase wants data in
 314    sorted order.  Use hsh_data_copy() or hsh_sort_copy() instead,
 315    if the second phase still needs to search the hash table. */
 316 void *const *
 317 hsh_data (struct hsh_table *h)
 318 {
 319   size_t n;
 320
 321   assert (h != NULL);
 322   n = partition (h->entries, h->size, sizeof *h->entries, not_null, NULL);
 323   assert (n == h->used);
 324 #ifndef NDEBUG
 325   h->hash_ordered = false;
 326 #endif
 327   return h->entries;
 328 }
 329
 330 /* Dereferences void ** pointers and passes them to the hash
 331    comparison function. */
 332 static int
 333 comparison_helper (const void *a_, const void *b_, void *h_)
 334 {
 335   void *const *a = a_;
 336   void *const *b = b_;
 337   struct hsh_table *h = h_;
 338
 339   assert(a);
 340   assert(b);
 341
 342   return h->compare (*a, *b, h->aux);
 343 }
 344
 345 /* Sorts hash table H based on hash comparison function.  The
 346    returned data consists of hsh_count(H) non-null pointers,
 347    sorted in order of the hash comparison function, followed by a
 348    null pointer.
 349
 350    After calling this function, only hsh_destroy() and
 351    hsh_count() should be applied to H.  hsh_first() and
 352    hsh_next() could also be used, but you're better off just
 353    iterating through the returned array.
 354
 355    This function is intended for use in situations where data
 356    processing occurs in two phases.  In the first phase, data is
 357    added, removed, and searched for within a hash table.  In the
 358    second phase, the contents of the hash table are output and
 359    the hash property itself is no longer of interest.
 360
 361    Use hsh_data() instead, if the second phase doesn't need the
 362    data in any particular order.  Use hsh_data_copy() or
 363    hsh_sort_copy() instead, if the second phase still needs to
 364    search the hash table. */
 365 void *const *
 366 hsh_sort (struct hsh_table *h)
 367 {
 368   assert (h != NULL);
 369
 370   hsh_data (h);
 371   sort (h->entries, h->used, sizeof *h->entries, comparison_helper, h);
 372   return h->entries;
 373 }
 374
 375 /* Makes and returns a copy of the pointers to the data in H.
 376    The returned data consists of hsh_count(H) non-null pointers,
 377    in no particular order, followed by a null pointer.  The hash
 378    table is not modified.  The caller is responsible for freeing
 379    the allocated data.
 380
 381    If you don't need to search or modify the hash table, then
 382    hsh_data() is a more efficient choice. */
 383 void **
 384 hsh_data_copy (struct hsh_table *h)
 385 {
 386   void **copy;
 387
 388   assert (h != NULL);
 389   copy = xnmalloc ((h->used + 1), sizeof *copy);
 390   copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL);
 391   copy[h->used] = NULL;
 392   return copy;
 393 }
 394
 395 /* Makes and returns a copy of the pointers to the data in H.
 396    The returned data consists of hsh_count(H) non-null pointers,
 397    sorted in order of the hash comparison function, followed by a
 398    null pointer.  The hash table is not modified.  The caller is
 399    responsible for freeing the allocated data.
 400
 401    If you don't need to search or modify the hash table, then
 402    hsh_sort() is a more efficient choice. */
 403 void **
 404 hsh_sort_copy (struct hsh_table *h)
 405 {
 406   void **copy;
 407
 408   assert (h != NULL);
 409   copy = hsh_data_copy (h);
 410   sort (copy, h->used, sizeof *copy, comparison_helper, h);
 411   return copy;
 412 }
 413 \f
 414 /* Hash entries. */
 415
 416 /* Searches hash table H for TARGET.  If found, returns a pointer
 417    to a pointer to that entry; otherwise returns a pointer to a
 418    NULL entry which *must* be used to insert a new entry having
 419    the same key data.  */
 420 inline void **
 421 hsh_probe (struct hsh_table *h, const void *target)
 422 {
 423   unsigned i;
 424
 425   assert (h != NULL);
 426   assert (target != NULL);
 427   assert (h->hash_ordered);
 428
 429   if (h->used > h->size / 2)
 430     rehash (h, h->size * 2);
 431   i = locate_matching_entry (h, target);
 432   if (h->entries[i] == NULL)
 433     h->used++;
 434   return &h->entries[i];
 435 }
 436
 437 /* Searches hash table H for TARGET.  If not found, inserts
 438    TARGET and returns a null pointer.  If found, returns the
 439    match, without replacing it in the table. */
 440 void *
 441 hsh_insert (struct hsh_table *h, void *target)
 442 {
 443   void **entry;
 444
 445   assert (h != NULL);
 446   assert (target != NULL);
 447
 448   entry = hsh_probe (h, target);
 449   if (*entry == NULL)
 450     {
 451       *entry = target;
 452       return NULL;
 453     }
 454   else
 455     return *entry;
 456 }
 457
 458 /* Searches hash table H for TARGET.  If not found, inserts
 459    TARGET and returns a null pointer.  If found, returns the
 460    match, after replacing it in the table by TARGET. */
 461 void *
 462 hsh_replace (struct hsh_table *h, void *target)
 463 {
 464   void **entry = hsh_probe (h, target);
 465   void *old = *entry;
 466   *entry = target;
 467   return old;
 468 }
 469
 470 /* Returns the entry in hash table H that matches TARGET, or NULL
 471    if there is none. */
 472 void *
 473 hsh_find (struct hsh_table *h, const void *target)
 474 {
 475   return h->entries[locate_matching_entry (h, target)];
 476 }
 477
 478 /* Deletes the entry in hash table H that matches TARGET.
 479    Returns nonzero if an entry was deleted.
 480
 481    Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
 482    Because our load factor is at most 1/2, the average number of
 483    moves that this algorithm makes should be at most 2 - ln 2 ~=
 484    1.65. */
 485 int
 486 hsh_delete (struct hsh_table *h, const void *target)
 487 {
 488   unsigned i = locate_matching_entry (h, target);
 489   if (h->entries[i] != NULL)
 490     {
 491       h->used--;
 492       if (h->free != NULL)
 493         h->free (h->entries[i], h->aux);
 494
 495       for (;;)
 496         {
 497           unsigned r;
 498           ptrdiff_t j;
 499
 500           h->entries[i] = NULL;
 501           j = i;
 502           do
 503             {
 504               i = (i - 1) & (h->size - 1);
 505               if (h->entries[i] == NULL)
 506                 return 1;
 507
 508               r = h->hash (h->entries[i], h->aux) & (h->size - 1);
 509             }
 510           while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
 511           h->entries[j] = h->entries[i];
 512         }
 513     }
 514   else
 515     return 0;
 516 }
 517 \f
 518 /* Iteration. */
 519
 520 /* Finds and returns an entry in TABLE, and initializes ITER for
 521    use with hsh_next().  If TABLE is empty, returns a null
 522    pointer. */
 523 void *
 524 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
 525 {
 526   assert (h != NULL);
 527   assert (iter != NULL);
 528
 529   iter->next = 0;
 530   return hsh_next (h, iter);
 531 }
 532
 533 /* Iterates through TABLE with iterator ITER.  Returns the next
 534    entry in TABLE, or a null pointer after the last entry.
 535
 536    Entries are returned in an undefined order.  Modifying TABLE
 537    during iteration may cause some entries to be returned
 538    multiple times or not at all. */
 539 void *
 540 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
 541 {
 542   size_t i;
 543
 544   assert (h != NULL);
 545   assert (iter != NULL);
 546   assert (iter->next <= h->size);
 547
 548   for (i = iter->next; i < h->size; i++)
 549     if (h->entries[i])
 550       {
 551         iter->next = i + 1;
 552         return h->entries[i];
 553       }
 554
 555   iter->next = h->size;
 556   return NULL;
 557 }
 558 \f
 559 /* Returns the number of items in H. */
 560 size_t
 561 hsh_count (struct hsh_table *h)
 562 {
 563   assert (h != NULL);
 564
 565   return h->used;
 566 }
 567 \f
 568 /* Debug helpers. */
 569
 570 #if DEBUGGING
 571 #undef NDEBUG
 572 #include "message.h"
 573 #include <stdio.h>
 574
 575 /* Displays contents of hash table H on stdout. */
 576 void
 577 hsh_dump (struct hsh_table *h)
 578 {
 579   void **entry = h->entries;
 580   int i;
 581
 582   printf (_("hash table:"));
 583   for (i = 0; i < h->size; i++)
 584     printf (" %p", *entry++);
 585   printf ("\n");
 586 }
 587
 588 /* This wrapper around hsh_probe() assures that it returns a pointer
 589    to a NULL pointer.  This function is used when it is known that the
 590    entry to be inserted does not already exist in the table. */
 591 void
 592 hsh_force_insert (struct hsh_table *h, void *p)
 593 {
 594   void **pp = hsh_probe (h, p);
 595   assert (*pp == NULL);
 596   *pp = p;
 597 }
 598
 599 /* This wrapper around hsh_find() assures that it returns non-NULL.
 600    This function is for use when it is known that the entry being
 601    searched for must exist in the table. */
 602 void *
 603 hsh_force_find (struct hsh_table *h, const void *target)
 604 {
 605   void *found = hsh_find (h, target);
 606   assert (found != NULL);
 607   return found;
 608 }
 609
 610 /* This wrapper for hsh_delete() verifies that an item really was
 611    deleted. */
 612 void
 613 hsh_force_delete (struct hsh_table *h, const void *target)
 614 {
 615   int found = hsh_delete (h, target);
 616   assert (found != 0);
 617 }
 618 #endif