Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[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   if ( size ==  0 ) 
146     return NULL;
147
148   assert (compare != NULL);
149   assert (hash != NULL);
150   
151   h = xmalloc (sizeof *h);
152   h->used = 0;
153   if (size < 4)
154     size = 4;
155   h->size = next_power_of_2 (size);
156   h->entries = xmalloc (sizeof *h->entries * h->size);
157   for (i = 0; i < h->size; i++)
158     h->entries[i] = NULL;
159   h->aux = aux;
160   h->compare = compare;
161   h->hash = hash;
162   h->free = free;
163   return h;
164 }
165
166 /* Destroys the contents of table H. */
167 void
168 hsh_clear (struct hsh_table *h)
169 {
170   int i;
171
172   assert (h != NULL);
173   if (h->free)
174     for (i = 0; i < h->size; i++)
175       if (h->entries[i] != NULL)
176         h->free (h->entries[i], h->aux);
177
178   for (i = 0; i < h->size; i++)
179     h->entries[i] = NULL;
180
181   h->used = 0;
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     if (*table_p != NULL)
220       {
221         void **entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
222         while (*entry != NULL)
223           if (++entry >= h->entries + h->size)
224             entry = h->entries;
225         *entry = *table_p;
226       }
227   free (begin);
228 }
229
230 /* A "algo_predicate_func" that returns nonzero if DATA points
231    to a non-null void. */
232 static int
233 not_null (const void *data_, void *aux UNUSED) 
234 {
235   void *const *data = data_;
236
237   return *data != NULL;
238 }
239
240 /* Compacts hash table H and returns a pointer to its data.  The
241    returned data consists of hsh_count(H) non-null pointers, in
242    no particular order, followed by a null pointer.  After
243    calling this function, only hsh_destroy() and hsh_count() may
244    be applied to H. */
245 void **
246 hsh_data (struct hsh_table *h) 
247 {
248   size_t n;
249
250   assert (h != NULL);
251   n = partition (h->entries, h->size, sizeof *h->entries,
252                  not_null, NULL);
253   assert (n == h->used);
254   return h->entries;
255 }
256
257 /* Dereferences void ** pointers and passes them to the hash
258    comparison function. */
259 static int
260 comparison_helper (const void *a_, const void *b_, void *h_) 
261 {
262   void *const *a = a_;
263   void *const *b = b_;
264   struct hsh_table *h = h_;
265
266   assert(a);
267   assert(b);
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 + h->size)
345         entry = h->entries;
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 + h->size)
396         entry = h->entries;
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    Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
414    Because our load factor is at most 1/2, the average number of
415    moves that this algorithm makes should be at most 2 - ln 2 ~=
416    1.65.
417
418    Not well tested. */
419 int
420 hsh_delete (struct hsh_table *h, const void *target) 
421 {
422   void **entry = locate_matching_entry (h, target);
423   if (entry != NULL) 
424     {
425       ptrdiff_t i;
426       
427       h->used--;
428       if (h->free != NULL)
429         h->free (*entry, h->aux);
430       *entry = 0;
431
432       i = entry - h->entries;
433       for (;;) 
434         {
435           unsigned r;
436           ptrdiff_t j = i;
437
438           do 
439             {
440               if (--i < 0)
441                 i = h->size - 1;
442               if (h->entries[i] == NULL)
443                 return 1;
444               
445               r = h->hash (h->entries[i], h->aux) & (h->size - 1);
446             }
447           while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
448           h->entries[i] = h->entries[j]; 
449         }
450     }
451   else
452     return 0;
453 }
454 \f
455 /* Iteration. */
456
457 /* Finds and returns an entry in TABLE, and initializes ITER for
458    use with hsh_next().  If TABLE is empty, returns a null
459    pointer. */
460 void *
461 hsh_first (struct hsh_table *h, struct hsh_iterator *iter) 
462 {
463   assert (h != NULL);
464   assert (iter != NULL);
465
466   iter->next = 0;
467   return hsh_next (h, iter);
468 }
469
470 /* Iterates through TABLE with iterator ITER.  Returns the next
471    entry in TABLE, or a null pointer after the last entry.
472
473    Entries are returned in an undefined order.  Modifying TABLE
474    during iteration may cause some entries to be returned
475    multiple times or not at all. */
476 void *
477 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
478 {
479   size_t i;
480
481   assert (h != NULL);
482   assert (iter != NULL);
483   assert (iter->next <= h->size);
484
485   for (i = iter->next; i < h->size; i++)
486     if (h->entries[i])
487       {
488         iter->next = i + 1;
489         return h->entries[i];
490       }
491
492   iter->next = h->size;
493   return NULL;
494 }
495 \f
496 /* Returns the number of items in H. */
497 size_t 
498 hsh_count (struct hsh_table *h) 
499 {
500   assert (h != NULL);
501   
502   return h->used;
503 }
504 \f
505 /* Debug helpers. */
506
507 #if GLOBAL_DEBUGGING
508 #undef NDEBUG
509 #include "error.h"
510 #include <stdio.h>
511
512 /* Displays contents of hash table H on stdout. */
513 void
514 hsh_dump (struct hsh_table *h)
515 {
516   void **entry = h->entries;
517   int i;
518
519   printf (_("hash table:"));
520   for (i = 0; i < h->size; i++)
521     printf (" %p", *entry++);
522   printf ("\n");
523 }
524
525 /* This wrapper around hsh_probe() assures that it returns a pointer
526    to a NULL pointer.  This function is used when it is known that the
527    entry to be inserted does not already exist in the table. */
528 void
529 hsh_force_insert (struct hsh_table *h, void *p)
530 {
531   void **pp = hsh_probe (h, p);
532   assert (*pp == NULL);
533   *pp = p;
534 }
535
536 /* This wrapper around hsh_find() assures that it returns non-NULL.
537    This function is for use when it is known that the entry being
538    searched for must exist in the table. */
539 void *
540 hsh_force_find (struct hsh_table *h, const void *target)
541 {
542   void *found = hsh_find (h, target);
543   assert (found != NULL);
544   return found;
545 }
546
547 /* This wrapper for hsh_delete() verifies that an item really was
548    deleted. */
549 void
550 hsh_force_delete (struct hsh_table *h, const void *target)
551 {
552   int found = hsh_delete (h, target);
553   assert (found != 0);
554 }
555 #endif