src/libpspp/hash.c

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