f6bad64b8889dbc2b3bf860924f8fc21d470489a
[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 <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