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