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