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