f42901ea8e5479d42c6f0ee0ad0e3c603badc1a6
[pspp] / 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
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 "error.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