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