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 "alloc.h"
  25 #include "hash.h"
  26
  27 /* Note for constructing hash functions:
  28
  29    You can store the hash values in the records, then compare hash
  30    values (in the compare function) before bothering to compare keys.
  31    Hash values can simply be returned from the records instead of
  32    recalculating when rehashing. */
  33
  34 /* Debugging note:
  35
  36    Since hash_probe and hash_find take void * pointers, it's easy to
  37    pass a void ** to your data by accidentally inserting an `&'
  38    reference operator where one shouldn't go.  It took me an hour to
  39    hunt down a bug like that once. */
  40 \f
  41 /* Prime numbers and hash functions. */
  42
  43 static int hsh_prime_tab[] =
  44 {
  45   13, 31, 47, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411,
  46   32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319,
  47   8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
  48   536870923, 1073741827, INT_MAX,
  49 };
  50
  51 /* Returns pointer into hsh_prime_tab[], pointing to the first prime
  52    in the table greater than X. */
  53 int *
  54 hsh_next_prime (int x)
  55 {
  56   int *p;
  57
  58   assert (x >= 0);
  59
  60   for (p = hsh_prime_tab; *p < x; p++)
  61     ;
  62
  63   assert (*p != INT_MAX);
  64
  65   return p;
  66 }
  67
  68 /* P.J. Weinberger's hash function, recommended by the Red Dragon
  69    Book.  Hashes the d-string between S1 and S2.  Returns unbounded
  70    nonnegative result. */
  71 int
  72 hashpjw_d (const char *s1, const char *s2)
  73 {
  74   const char *p;
  75   unsigned g, h;
  76
  77   for (h = 0, p = s1; p < s2; p++)
  78     {
  79       h = (h << 4) + *(unsigned char *) p;
  80       g = h & 0xf0000000;
  81       h ^= (g >> 24) | g;
  82     }
  83   return abs ((int) h);
  84 }
  85
  86 /* Alternate entry point for hashpjw_d() that takes an s-string. */
  87 int
  88 hashpjw (const char *s)
  89 {
  90   return hashpjw_d (s, &s[strlen (s)]);
  91 }
  92 \f
  93 /*hash tables. */
  94
  95 /* Creates a hash table with at least M entries.  COMPARE is a
  96    function that compares two entries and returns 0 if they are
  97    identical, nonzero otherwise; HASH returns a nonnegative hash value
  98    for an entry; FREE destroys an entry. */
  99 struct hsh_table *
 100 hsh_create (int m,
 101             int (*compare) (const void *, const void *, void *param),
 102             unsigned (*hash) (const void *, void *param),
 103             void (*free) (void *, void *param),
 104             void *param)
 105 {
 106   struct hsh_table *h = xmalloc (sizeof *h);
 107   int i;
 108
 109   h->n = 0;
 110   h->mp = hsh_next_prime (m);
 111   h->m = *h->mp++;
 112   h->table = xmalloc (sizeof *h->table * h->m);
 113   for (i = 0; i < h->m; i++)
 114     h->table[i] = NULL;
 115   h->param = param;
 116   h->compare = compare;
 117   h->hash = hash;
 118   h->free = free;
 119   return h;
 120 }
 121
 122 /* Destroys the contents of table H. */
 123 void
 124 hsh_clear (struct hsh_table *h)
 125 {
 126   int i;
 127
 128   if (h->free)
 129     for (i = 0; i < h->m; i++)
 130       h->free (h->table[i], h->param);
 131
 132   if (h->m >= 128)
 133     {
 134       free (h->table);
 135       h->mp = hsh_next_prime (31);
 136       h->m = *h->mp++;
 137       h->table = xmalloc (sizeof *h->table * h->m);
 138     }
 139
 140   for (i = 0; i < h->m; i++)
 141     h->table[i] = NULL;
 142 }
 143
 144 /* Destroys table H and all its contents. */
 145 void
 146 hsh_destroy (struct hsh_table *h)
 147 {
 148   int i;
 149
 150   if (h == NULL)
 151     return;
 152   if (h->free)
 153     for (i = 0; i < h->m; i++)
 154       {
 155         void *p = h->table[i];
 156         if (p)
 157           h->free (p, h->param);
 158       }
 159   free (h->table);
 160   free (h);
 161 }
 162
 163 /* Increases the capacity of H. */
 164 void
 165 hsh_rehash (struct hsh_table *h)
 166 {
 167   void **begin = h->table;
 168   void **end = &h->table[h->m];
 169   void **table_p;
 170   int i;
 171
 172   h->m = *h->mp++;
 173   h->table = xmalloc (sizeof *h->table * h->m);
 174   for (i = 0; i < h->m; i++)
 175     h->table[i] = NULL;
 176   for (table_p = begin; table_p < end; table_p++)
 177     {
 178       void **entry;
 179
 180       if (*table_p == NULL)
 181         continue;
 182       entry = &h->table[h->hash (*table_p, h->param) % h->m];
 183       while (*entry)
 184         if (--entry < h->table)
 185           entry = &h->table[h->m - 1];
 186       *entry = *table_p;
 187     }
 188   free (begin);
 189 }
 190
 191 /* Static variables for hsh_sort(). */
 192 static void *hsh_param;
 193 static int (*hsh_compare) (const void *, const void *, void *param);
 194
 195 /* hsh_sort() helper function that ensures NULLs are sorted after the
 196    rest of the table. */
 197 static int
 198 internal_comparison_fn (const void *pa, const void *pb)
 199 {
 200   void *a = *(void **) pa;
 201   void *b = *(void **) pb;
 202   return a == NULL ? 1 : (b == NULL ? -1 : hsh_compare (a, b, hsh_param));
 203 }
 204
 205 /* Sorts hash table H based on function COMPARE.  NULLs are sent to
 206    the end of the table.  The resultant table is returned (it is
 207    guaranteed to be NULL-terminated).  H should not be used again as a
 208    hash table until and unless hsh_clear() called. */
 209 void **
 210 hsh_sort (struct hsh_table *h,
 211           int (*compare) (const void *, const void *, void *param))
 212 {
 213 #if GLOBAL_DEBUGGING
 214   static int reentrant;
 215   if (reentrant)
 216     abort ();
 217   reentrant++;
 218 #endif
 219   hsh_param = h->param;
 220   hsh_compare = compare ? compare : h->compare;
 221   qsort (h->table, h->m, sizeof *h->table, internal_comparison_fn);
 222 #if GLOBAL_DEBUGGING
 223   reentrant--;
 224 #endif
 225   return h->table;
 226 }
 227 \f
 228 /* Hash entries. */
 229
 230 /* Searches hash table H for TARGET.  If found, returns a pointer to a
 231    pointer to that entry; otherwise returns a pointer to a NULL entry
 232    which _must_ be used to insert a new entry having the same key
 233    data.  */
 234 inline void **
 235 hsh_probe (struct hsh_table *h, const void *target)
 236 {
 237   void **entry;
 238
 239   /* Order of these statements is important! */
 240   if (h->n > h->m / 2)
 241     hsh_rehash (h);
 242   entry = &h->table[h->hash (target, h->param) % h->m];
 243
 244   while (*entry)
 245     {
 246       if (!h->compare (*entry, target, h->param))
 247         return entry;
 248
 249       if (--entry < h->table)
 250         entry = &h->table[h->m - 1];
 251     }
 252   h->n++;
 253   return entry;
 254 }
 255
 256 /* Returns the entry in hash table H that matches TARGET, NULL if
 257    there is none. */
 258 void *
 259 hsh_find (struct hsh_table *h, const void *target)
 260 {
 261   void **entry = &h->table[h->hash (target, h->param) % h->m];
 262
 263   while (*entry)
 264     {
 265       if (!h->compare (*entry, target, h->param))
 266         return *entry;
 267       if (--entry < h->table)
 268         entry = &h->table[h->m - 1];
 269     }
 270   return NULL;
 271 }
 272
 273 /* Iterates throught hash table TABLE with iterator ITER.  Returns the
 274    next non-NULL entry in TABLE, or NULL after the last non-NULL
 275    entry.  After NULL is returned, ITER is returned to a condition in
 276    which hsh_foreach() will return the first non-NULL entry if any on
 277    the next call.  Do not add entries to TABLE between call to
 278    hsh_foreach() between NULL returns.
 279
 280    Before calling hsh_foreach with a particular iterator for the first
 281    time, you must initialize the iterator with a call to
 282    hsh_iterator_init.  */
 283 void *
 284 hsh_foreach (struct hsh_table *table, struct hsh_iterator *iter)
 285 {
 286   int i;
 287
 288   if (!table)
 289     return NULL;
 290   if (!iter->init)
 291     {
 292       iter->init = 1;
 293       iter->next = 0;
 294     }
 295   for (i = iter->next; i < table->m; i++)
 296     if (table->table[i])
 297       {
 298         iter->next = i + 1;
 299         return table->table[i];
 300       }
 301   iter->init = 0;
 302   return NULL;
 303 }
 304
 305 #if GLOBAL_DEBUGGING
 306 #include <stdio.h>
 307
 308 /* Displays contents of hash table H on stdout. */
 309 void
 310 hsh_dump (struct hsh_table *h)
 311 {
 312   void **entry = h->table;
 313   int i;
 314
 315   printf (_("hash table:"));
 316   for (i = 0; i < h->m; i++)
 317     printf (" %p", *entry++);
 318   printf ("\n");
 319 }
 320
 321 /* This wrapper around hsh_probe() assures that it returns a pointer
 322    to a NULL pointer.  This function is used when it is known that the
 323    entry to be inserted does not already exist in the table. */
 324 void
 325 force_hsh_insert (struct hsh_table *h, void *p)
 326 {
 327   void **pp = hsh_probe (h, p);
 328   if (*pp != NULL)
 329     assert (0);
 330   *pp = p;
 331 }
 332
 333 /* This wrapper around hsh_find() assures that it returns non-NULL.
 334    This function is for use when it is known that the entry being
 335    searched for must exist in the table. */
 336 void *
 337 force_hsh_find (struct hsh_table *h, const void *p)
 338 {
 339   p = hsh_find (h, p);
 340   if (p == NULL)
 341     assert (0);
 342   return (void *) p;
 343 }
 344 #endif