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 <assert.h>
  22 #include <limits.h>
  23 #include <stdlib.h>
  24 #include "algorithm.h"
  25 #include "alloc.h"
  26 #include "hash.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 /* Colin Plumb's "one-at-a-time" hash, for bytes. */
  80 unsigned
  81 hsh_hash_bytes (const void *buf_, size_t size)
  82 {
  83   const unsigned char *buf = buf_;
  84   unsigned hash = 0;
  85
  86   assert (buf != NULL);
  87   while (size-- > 0)
  88     {
  89       hash += *buf++;
  90       hash += (hash << 10);
  91       hash ^= (hash >> 6);
  92     }
  93   hash += (hash << 3);
  94   hash ^= (hash >> 11);
  95   hash += (hash << 15);
  96   return hash;
  97 }
  98
  99 /* Colin Plumb's "one-at-a-time" hash, for strings. */
 100 unsigned
 101 hsh_hash_string (const char *s_)
 102 {
 103   const unsigned char *s = s_;
 104   unsigned hash = 0;
 105
 106   assert (s != NULL);
 107   while (*s != '\0')
 108     {
 109       hash += *s++;
 110       hash += (hash << 10);
 111       hash ^= (hash >> 6);
 112     }
 113   hash += (hash << 3);
 114   hash ^= (hash >> 11);
 115   hash += (hash << 15);
 116   return hash;
 117 }
 118
 119 /* Hash for ints. */
 120 unsigned
 121 hsh_hash_int (int i)
 122 {
 123   return hsh_hash_bytes (&i, sizeof i);
 124 }
 125
 126 /* Hash for double. */
 127 unsigned
 128 hsh_hash_double (double d)
 129 {
 130   if (!isnan (d))
 131     return hsh_hash_bytes (&d, sizeof d);
 132   else
 133     return 0;
 134 }
 135 \f
 136 /* Hash tables. */
 137
 138 /* Creates a hash table with at least M entries.  COMPARE is a
 139    function that compares two entries and returns 0 if they are
 140    identical, nonzero otherwise; HASH returns a nonnegative hash value
 141    for an entry; FREE destroys an entry. */
 142 struct hsh_table *
 143 hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
 144             hsh_free_func *free, void *aux)
 145 {
 146   struct hsh_table *h;
 147   int i;
 148
 149   assert (size > 0);
 150   assert (compare != NULL);
 151   assert (hash != NULL);
 152
 153   h = xmalloc (sizeof *h);
 154   h->used = 0;
 155   if (size < 4)
 156     size = 4;
 157   h->size = next_power_of_2 (size);
 158   h->entries = xmalloc (sizeof *h->entries * h->size);
 159   for (i = 0; i < h->size; i++)
 160     h->entries[i] = NULL;
 161   h->aux = aux;
 162   h->compare = compare;
 163   h->hash = hash;
 164   h->free = free;
 165   return h;
 166 }
 167
 168 /* Destroys the contents of table H. */
 169 void
 170 hsh_clear (struct hsh_table *h)
 171 {
 172   int i;
 173
 174   assert (h != NULL);
 175   if (h->free)
 176     for (i = 0; i < h->size; i++)
 177       if (h->entries[i] != NULL)
 178         h->free (h->entries[i], h->aux);
 179
 180   for (i = 0; i < h->size; i++)
 181     h->entries[i] = NULL;
 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     {
 220       void **entry;
 221
 222       if (*table_p == NULL)
 223         continue;
 224       entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
 225       while (*entry)
 226         if (--entry < h->entries)
 227           entry = &h->entries[h->size - 1];
 228       *entry = *table_p;
 229     }
 230   free (begin);
 231 }
 232
 233 /* A "algo_predicate_func" that returns nonzero if DATA points
 234    to a non-null void. */
 235 static int
 236 not_null (const void *data_, void *aux unused)
 237 {
 238   void *const *data = data_;
 239
 240   return *data != NULL;
 241 }
 242
 243 /* Compacts hash table H and returns a pointer to its data.  The
 244    returned data consists of hsh_count(H) non-null pointers, in
 245    no particular order, followed by a null pointer.  After
 246    calling this function, only hsh_destroy() and hsh_count() may
 247    be applied to H. */
 248 void **
 249 hsh_data (struct hsh_table *h)
 250 {
 251   size_t n;
 252
 253   assert (h != NULL);
 254   n = partition (h->entries, h->size, sizeof *h->entries,
 255                  not_null, NULL);
 256   assert (n == h->used);
 257   return h->entries;
 258 }
 259
 260 /* Dereferences void ** pointers and passes them to the hash
 261    comparison function. */
 262 int
 263 comparison_helper (const void *a_, const void *b_, void *h_)
 264 {
 265   void *const *a = a_;
 266   void *const *b = b_;
 267   struct hsh_table *h = h_;
 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)
 345         entry = &h->entries[h->size - 1];
 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)
 396         entry = &h->entries[h->size - 1];
 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    Note: this function is very slow because it rehashes the
 414    entire table.  Don't use this hash table implementation if
 415    deletion is a common operation. */
 416 int
 417 hsh_delete (struct hsh_table *h, const void *target)
 418 {
 419   void **entry = locate_matching_entry (h, target);
 420   if (entry != NULL)
 421     {
 422       if (h->free != NULL)
 423         h->free (*entry, h->aux);
 424       *entry = 0;
 425       hsh_rehash (h, h->size);
 426       return 1;
 427     }
 428   else
 429     return 0;
 430 }
 431 \f
 432 /* Iteration. */
 433
 434 /* Finds and returns an entry in TABLE, and initializes ITER for
 435    use with hsh_next().  If TABLE is empty, returns a null
 436    pointer. */
 437 void *
 438 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
 439 {
 440   assert (h != NULL);
 441   assert (iter != NULL);
 442
 443   iter->next = 0;
 444   return hsh_next (h, iter);
 445 }
 446
 447 /* Iterates through TABLE with iterator ITER.  Returns the next
 448    entry in TABLE, or a null pointer after the last entry.
 449
 450    Entries are returned in an undefined order.  Modifying TABLE
 451    during iteration may cause some entries to be returned
 452    multiple times or not at all. */
 453 void *
 454 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
 455 {
 456   size_t i;
 457
 458   assert (h != NULL);
 459   assert (iter != NULL);
 460   assert (iter->next <= h->size);
 461
 462   for (i = iter->next; i < h->size; i++)
 463     if (h->entries[i])
 464       {
 465         iter->next = i + 1;
 466         return h->entries[i];
 467       }
 468
 469   iter->next = h->size;
 470   return NULL;
 471 }
 472 \f
 473 /* Returns the number of items in H. */
 474 size_t
 475 hsh_count (struct hsh_table *h)
 476 {
 477   assert (h != NULL);
 478
 479   return h->used;
 480 }
 481 \f
 482 /* Debug helpers. */
 483
 484 #if GLOBAL_DEBUGGING
 485 #undef NDEBUG
 486 #include <assert.h>
 487 #include <stdio.h>
 488
 489 /* Displays contents of hash table H on stdout. */
 490 void
 491 hsh_dump (struct hsh_table *h)
 492 {
 493   void **entry = h->entries;
 494   int i;
 495
 496   printf (_("hash table:"));
 497   for (i = 0; i < h->size; i++)
 498     printf (" %p", *entry++);
 499   printf ("\n");
 500 }
 501
 502 /* This wrapper around hsh_probe() assures that it returns a pointer
 503    to a NULL pointer.  This function is used when it is known that the
 504    entry to be inserted does not already exist in the table. */
 505 void
 506 hsh_force_insert (struct hsh_table *h, void *p)
 507 {
 508   void **pp = hsh_probe (h, p);
 509   assert (*pp == NULL);
 510   *pp = p;
 511 }
 512
 513 /* This wrapper around hsh_find() assures that it returns non-NULL.
 514    This function is for use when it is known that the entry being
 515    searched for must exist in the table. */
 516 void *
 517 hsh_force_find (struct hsh_table *h, const void *target)
 518 {
 519   void *found = hsh_find (h, target);
 520   assert (found != NULL);
 521   return found;
 522 }
 523
 524 /* This wrapper for hsh_delete() verifies that an item really was
 525    deleted. */
 526 void
 527 hsh_force_delete (struct hsh_table *h, const void *target)
 528 {
 529   int found = hsh_delete (h, target);
 530   assert (found != 0);
 531 }
 532 #endif