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., 59 Temple Place - Suite 330, Boston, MA
  18    02111-1307, USA. */
  19
  20 #include <config.h>
  21 #include "hash.h"
  22 #include <assert.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   assert (size > 0);
 146   assert (compare != NULL);
 147   assert (hash != NULL);
 148
 149   h = xmalloc (sizeof *h);
 150   h->used = 0;
 151   if (size < 4)
 152     size = 4;
 153   h->size = next_power_of_2 (size);
 154   h->entries = xmalloc (sizeof *h->entries * h->size);
 155   for (i = 0; i < h->size; i++)
 156     h->entries[i] = NULL;
 157   h->aux = aux;
 158   h->compare = compare;
 159   h->hash = hash;
 160   h->free = free;
 161   return h;
 162 }
 163
 164 /* Destroys the contents of table H. */
 165 void
 166 hsh_clear (struct hsh_table *h)
 167 {
 168   int i;
 169
 170   assert (h != NULL);
 171   if (h->free)
 172     for (i = 0; i < h->size; i++)
 173       if (h->entries[i] != NULL)
 174         h->free (h->entries[i], h->aux);
 175
 176   for (i = 0; i < h->size; i++)
 177     h->entries[i] = NULL;
 178 }
 179
 180 /* Destroys table H and all its contents. */
 181 void
 182 hsh_destroy (struct hsh_table *h)
 183 {
 184   int i;
 185
 186   if (h != NULL)
 187     {
 188       if (h->free)
 189         for (i = 0; i < h->size; i++)
 190           if (h->entries[i] != NULL)
 191             h->free (h->entries[i], h->aux);
 192       free (h->entries);
 193       free (h);
 194     }
 195 }
 196
 197 /* Changes the capacity of H to NEW_SIZE. */
 198 static void
 199 hsh_rehash (struct hsh_table *h, size_t new_size)
 200 {
 201   void **begin, **end, **table_p;
 202   int i;
 203
 204   assert (h != NULL);
 205   assert (new_size >= h->used);
 206
 207   begin = h->entries;
 208   end = begin + h->size;
 209
 210   h->size = new_size;
 211   h->entries = xmalloc (sizeof *h->entries * h->size);
 212   for (i = 0; i < h->size; i++)
 213     h->entries[i] = NULL;
 214   for (table_p = begin; table_p < end; table_p++)
 215     {
 216       void **entry;
 217
 218       if (*table_p == NULL)
 219         continue;
 220       entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
 221       while (*entry)
 222         if (--entry < h->entries)
 223           entry = &h->entries[h->size - 1];
 224       *entry = *table_p;
 225     }
 226   free (begin);
 227 }
 228
 229 /* A "algo_predicate_func" that returns nonzero if DATA points
 230    to a non-null void. */
 231 static int
 232 not_null (const void *data_, void *aux unused)
 233 {
 234   void *const *data = data_;
 235
 236   return *data != NULL;
 237 }
 238
 239 /* Compacts hash table H and returns a pointer to its data.  The
 240    returned data consists of hsh_count(H) non-null pointers, in
 241    no particular order, followed by a null pointer.  After
 242    calling this function, only hsh_destroy() and hsh_count() may
 243    be applied to H. */
 244 void **
 245 hsh_data (struct hsh_table *h)
 246 {
 247   size_t n;
 248
 249   assert (h != NULL);
 250   n = partition (h->entries, h->size, sizeof *h->entries,
 251                  not_null, NULL);
 252   assert (n == h->used);
 253   return h->entries;
 254 }
 255
 256 /* Dereferences void ** pointers and passes them to the hash
 257    comparison function. */
 258 static int
 259 comparison_helper (const void *a_, const void *b_, void *h_)
 260 {
 261   void *const *a = a_;
 262   void *const *b = b_;
 263   struct hsh_table *h = h_;
 264
 265   return h->compare (*a, *b, h->aux);
 266 }
 267
 268 /* Sorts hash table H based on hash comparison function.  The
 269    returned data consists of hsh_count(H) non-null pointers,
 270    sorted in order of the hash comparison function, followed by a
 271    null pointer.  After calling this function, only hsh_destroy()
 272    and hsh_count() may be applied to H. */
 273 void **
 274 hsh_sort (struct hsh_table *h)
 275 {
 276   assert (h != NULL);
 277
 278   hsh_data (h);
 279   sort (h->entries, h->used, sizeof *h->entries, comparison_helper, h);
 280   return h->entries;
 281 }
 282
 283 /* Makes and returns a copy of the pointers to the data in H.
 284    The returned data consists of hsh_count(H) non-null pointers,
 285    in no particular order, followed by a null pointer.  The hash
 286    table is not modified.  The caller is responsible for freeing
 287    the allocated data. */
 288 void **
 289 hsh_data_copy (struct hsh_table *h)
 290 {
 291   void **copy;
 292
 293   assert (h != NULL);
 294   copy = xmalloc ((h->used + 1) * sizeof *copy);
 295   copy_if (h->entries, h->size, sizeof *h->entries, copy,
 296            not_null, NULL);
 297   copy[h->used] = NULL;
 298   return copy;
 299 }
 300
 301 /* Makes and returns a copy of the pointers to the data in H.
 302    The returned data consists of hsh_count(H) non-null pointers,
 303    sorted in order of the hash comparison function, followed by a
 304    null pointer.  The hash table is not modified.  The caller is
 305    responsible for freeing the allocated data. */
 306 void **
 307 hsh_sort_copy (struct hsh_table *h)
 308 {
 309   void **copy;
 310
 311   assert (h != NULL);
 312   copy = hsh_data_copy (h);
 313   sort (copy, h->used, sizeof *copy, comparison_helper, h);
 314   return copy;
 315 }
 316 \f
 317 /* Hash entries. */
 318
 319 /* Searches hash table H for TARGET.  If found, returns a pointer
 320    to a pointer to that entry; otherwise returns a pointer to a
 321    NULL entry which *must* be used to insert a new entry having
 322    the same key data.  */
 323 inline void **
 324 hsh_probe (struct hsh_table *h, const void *target)
 325 {
 326   void **entry;
 327
 328   assert (h != NULL);
 329   assert (target != NULL);
 330
 331   /* Order of these statements is important! */
 332   if (h->used > h->size / 2)
 333     hsh_rehash (h, h->size * 2);
 334   entry = &h->entries[h->hash (target, h->aux) & (h->size - 1)];
 335
 336   while (*entry)
 337     {
 338       if (!h->compare (*entry, target, h->aux))
 339         return entry;
 340       if (--entry < h->entries)
 341         entry = &h->entries[h->size - 1];
 342     }
 343   h->used++;
 344   return entry;
 345 }
 346
 347 /* Searches hash table H for TARGET.  If not found, inserts
 348    TARGET and returns a null pointer.  If found, returns the
 349    match, without replacing it in the table. */
 350 void *
 351 hsh_insert (struct hsh_table *h, void *target)
 352 {
 353   void **entry;
 354
 355   assert (h != NULL);
 356   assert (target != NULL);
 357
 358   entry = hsh_probe (h, target);
 359   if (*entry == NULL)
 360     {
 361       *entry = target;
 362       return NULL;
 363     }
 364   else
 365     return *entry;
 366 }
 367
 368 /* Searches hash table H for TARGET.  If not found, inserts
 369    TARGET and returns a null pointer.  If found, returns the
 370    match, after replacing it in the table by TARGET. */
 371 void *
 372 hsh_replace (struct hsh_table *h, void *target)
 373 {
 374   void **entry = hsh_probe (h, target);
 375   void *old = *entry;
 376   *entry = target;
 377   return old;
 378 }
 379
 380 /* Locates an entry matching TARGET.  Returns a pointer to the
 381    entry, or a null pointer on failure. */
 382 static inline void **
 383 locate_matching_entry (struct hsh_table *h, const void *target)
 384 {
 385   void **entry = &h->entries[h->hash (target, h->aux) & (h->size - 1)];
 386
 387   while (*entry)
 388     {
 389       if (!h->compare (*entry, target, h->aux))
 390         return entry;
 391       if (--entry < h->entries)
 392         entry = &h->entries[h->size - 1];
 393     }
 394   return NULL;
 395 }
 396
 397 /* Returns the entry in hash table H that matches TARGET, or NULL
 398    if there is none. */
 399 void *
 400 hsh_find (struct hsh_table *h, const void *target)
 401 {
 402   void **entry = locate_matching_entry (h, target);
 403   return entry != NULL ? *entry : NULL;
 404 }
 405
 406 /* Deletes the entry in hash table H that matches TARGET.
 407    Returns nonzero if an entry was deleted.
 408
 409    Note: this function is very slow because it rehashes the
 410    entire table.  Don't use this hash table implementation if
 411    deletion is a common operation. */
 412 int
 413 hsh_delete (struct hsh_table *h, const void *target)
 414 {
 415   void **entry = locate_matching_entry (h, target);
 416   if (entry != NULL)
 417     {
 418       if (h->free != NULL)
 419         h->free (*entry, h->aux);
 420       *entry = 0;
 421       hsh_rehash (h, h->size);
 422       return 1;
 423     }
 424   else
 425     return 0;
 426 }
 427 \f
 428 /* Iteration. */
 429
 430 /* Finds and returns an entry in TABLE, and initializes ITER for
 431    use with hsh_next().  If TABLE is empty, returns a null
 432    pointer. */
 433 void *
 434 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
 435 {
 436   assert (h != NULL);
 437   assert (iter != NULL);
 438
 439   iter->next = 0;
 440   return hsh_next (h, iter);
 441 }
 442
 443 /* Iterates through TABLE with iterator ITER.  Returns the next
 444    entry in TABLE, or a null pointer after the last entry.
 445
 446    Entries are returned in an undefined order.  Modifying TABLE
 447    during iteration may cause some entries to be returned
 448    multiple times or not at all. */
 449 void *
 450 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
 451 {
 452   size_t i;
 453
 454   assert (h != NULL);
 455   assert (iter != NULL);
 456   assert (iter->next <= h->size);
 457
 458   for (i = iter->next; i < h->size; i++)
 459     if (h->entries[i])
 460       {
 461         iter->next = i + 1;
 462         return h->entries[i];
 463       }
 464
 465   iter->next = h->size;
 466   return NULL;
 467 }
 468 \f
 469 /* Returns the number of items in H. */
 470 size_t
 471 hsh_count (struct hsh_table *h)
 472 {
 473   assert (h != NULL);
 474
 475   return h->used;
 476 }
 477 \f
 478 /* Debug helpers. */
 479
 480 #if GLOBAL_DEBUGGING
 481 #undef NDEBUG
 482 #include <assert.h>
 483 #include <stdio.h>
 484
 485 /* Displays contents of hash table H on stdout. */
 486 void
 487 hsh_dump (struct hsh_table *h)
 488 {
 489   void **entry = h->entries;
 490   int i;
 491
 492   printf (_("hash table:"));
 493   for (i = 0; i < h->size; i++)
 494     printf (" %p", *entry++);
 495   printf ("\n");
 496 }
 497
 498 /* This wrapper around hsh_probe() assures that it returns a pointer
 499    to a NULL pointer.  This function is used when it is known that the
 500    entry to be inserted does not already exist in the table. */
 501 void
 502 hsh_force_insert (struct hsh_table *h, void *p)
 503 {
 504   void **pp = hsh_probe (h, p);
 505   assert (*pp == NULL);
 506   *pp = p;
 507 }
 508
 509 /* This wrapper around hsh_find() assures that it returns non-NULL.
 510    This function is for use when it is known that the entry being
 511    searched for must exist in the table. */
 512 void *
 513 hsh_force_find (struct hsh_table *h, const void *target)
 514 {
 515   void *found = hsh_find (h, target);
 516   assert (found != NULL);
 517   return found;
 518 }
 519
 520 /* This wrapper for hsh_delete() verifies that an item really was
 521    deleted. */
 522 void
 523 hsh_force_delete (struct hsh_table *h, const void *target)
 524 {
 525   int found = hsh_delete (h, target);
 526   assert (found != 0);
 527 }
 528 #endif