39d47cb625bb158871d21652c53efcea16542281
[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 "alloc.h"
25 #include "hash.h"
26 #include "quicksort.h"
27 #include "str.h"
28
29 /* Hash table. */
30 struct hsh_table
31   {
32     size_t used;                /* Number of filled entries. */
33     size_t size;                /* Number of entries (a power of 2). */
34     void **entries;             /* Hash table proper. */
35
36     void *param;
37     hsh_compare_func *compare;
38     hsh_hash_func *hash;
39     hsh_free_func *free;
40   };
41
42 /* Note for constructing hash functions:
43
44    You can store the hash values in the records, then compare hash
45    values (in the compare function) before bothering to compare keys.
46    Hash values can simply be returned from the records instead of
47    recalculating when rehashing. */
48
49 /* Debugging note:
50
51    Since hash_probe and hash_find take void * pointers, it's easy to
52    pass a void ** to your data by accidentally inserting an `&'
53    reference operator where one shouldn't go.  It took me an hour to
54    hunt down a bug like that once. */
55 \f
56 /* Prime numbers and hash functions. */
57
58 /* Returns smallest power of 2 greater than X. */
59 static size_t
60 next_power_of_2 (size_t x) 
61 {
62   assert (x != 0);
63
64   for (;;) 
65     {
66       /* Turn off rightmost 1-bit in x. */
67       size_t y = x & (x - 1);
68
69       /* If y is 0 then x only had a single 1-bit. */
70       if (y == 0)
71         return 2 * x;
72
73       /* Otherwise turn off the next. */
74       x = y;
75     }
76 }
77
78 /* Colin Plumb's "one-at-a-time" hash, for bytes. */
79 unsigned
80 hsh_hash_bytes (const void *buf_, size_t size)
81 {
82   const unsigned char *buf = buf_;
83   unsigned hash = 0;
84   while (size-- > 0) 
85     {
86       hash += *buf++;
87       hash += (hash << 10);
88       hash ^= (hash >> 6);
89     } 
90   hash += (hash << 3);
91   hash ^= (hash >> 11);
92   hash += (hash << 15);
93   return hash;
94
95
96 /* Colin Plumb's "one-at-a-time" hash, for strings. */
97 unsigned
98 hsh_hash_string (const char *s_) 
99 {
100   const unsigned char *s = s_;
101   unsigned hash = 0;
102   while (*s != '\0') 
103     {
104       hash += *s++;
105       hash += (hash << 10);
106       hash ^= (hash >> 6);
107     } 
108   hash += (hash << 3);
109   hash ^= (hash >> 11);
110   hash += (hash << 15);
111   return hash;
112 }
113
114 /* Hash for ints. */
115 unsigned
116 hsh_hash_int (int i) 
117 {
118   return hsh_hash_bytes (&i, sizeof i);
119 }
120 \f
121 /* Hash tables. */
122
123 /* Creates a hash table with at least M entries.  COMPARE is a
124    function that compares two entries and returns 0 if they are
125    identical, nonzero otherwise; HASH returns a nonnegative hash value
126    for an entry; FREE destroys an entry. */
127 struct hsh_table *
128 hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
129             hsh_free_func *free, void *param)
130 {
131   struct hsh_table *h = xmalloc (sizeof *h);
132   int i;
133
134   h->used = 0;
135   h->size = next_power_of_2 (size);
136   h->entries = xmalloc (sizeof *h->entries * h->size);
137   for (i = 0; i < h->size; i++)
138     h->entries[i] = NULL;
139   h->param = param;
140   h->compare = compare;
141   h->hash = hash;
142   h->free = free;
143   return h;
144 }
145
146 /* Destroys the contents of table H. */
147 void
148 hsh_clear (struct hsh_table *h)
149 {
150   int i;
151
152   if (h->free)
153     for (i = 0; i < h->size; i++)
154       if (h->entries[i] != NULL)
155         h->free (h->entries[i], h->param);
156
157   for (i = 0; i < h->size; i++)
158     h->entries[i] = NULL;
159 }
160
161 /* Destroys table H and all its contents. */
162 void
163 hsh_destroy (struct hsh_table *h)
164 {
165   int i;
166
167   if (h == NULL)
168     return;
169   if (h->free)
170     for (i = 0; i < h->size; i++)
171       if (h->entries[i] != NULL)
172         h->free (h->entries[i], h->param);
173   free (h->entries);
174   free (h);
175 }
176
177 /* Changes the capacity of H to NEW_SIZE. */
178 static void
179 hsh_rehash (struct hsh_table *h, size_t new_size)
180 {
181   void **begin = h->entries;
182   void **end = &h->entries[h->size];
183   void **table_p;
184   int i;
185
186   h->size = new_size;
187   h->entries = xmalloc (sizeof *h->entries * h->size);
188   for (i = 0; i < h->size; i++)
189     h->entries[i] = NULL;
190   for (table_p = begin; table_p < end; table_p++)
191     {
192       void **entry;
193
194       if (*table_p == NULL)
195         continue;
196       entry = &h->entries[h->hash (*table_p, h->param) & (h->size - 1)];
197       while (*entry)
198         if (--entry < h->entries)
199           entry = &h->entries[h->size - 1];
200       *entry = *table_p;
201     }
202   free (begin);
203 }
204
205 /* hsh_sort() helper function that ensures NULLs are sorted after the
206    rest of the table. */
207 static int
208 sort_nulls_last (const void *a_, const void *b_, void *h_)
209 {
210   void *a = *(void **) a_;
211   void *b = *(void **) b_;
212   struct hsh_table *h = h_;
213
214   if (a != NULL) 
215     {
216       if (b != NULL)
217         return h->compare (a, b, h->param);
218       else
219         return -1;
220     }
221   else
222     {
223       if (b != NULL)
224         return +1;
225       else
226         return 0;
227     }
228 }
229
230 /* Sorts hash table H based on hash comparison function.  NULLs
231    are sent to the end of the table.  The resultant table is
232    returned (it is guaranteed to be NULL-terminated).  H should
233    not be used again as a hash table until and unless hsh_clear()
234    called. */
235 void **
236 hsh_sort (struct hsh_table *h)
237 {
238   quicksort (h->entries, h->size, sizeof *h->entries, sort_nulls_last, h);
239   return h->entries;
240 }
241 \f
242 /* Hash entries. */
243
244 /* Searches hash table H for TARGET.  If found, returns a pointer to a
245    pointer to that entry; otherwise returns a pointer to a NULL entry
246    which _must_ be used to insert a new entry having the same key
247    data.  */
248 inline void **
249 hsh_probe (struct hsh_table *h, const void *target)
250 {
251   void **entry;
252
253   /* Order of these statements is important! */
254   if (h->used > h->size / 2)
255     hsh_rehash (h, h->size * 2);
256   entry = &h->entries[h->hash (target, h->param) & (h->size - 1)];
257
258   while (*entry)
259     {
260       if (!h->compare (*entry, target, h->param))
261         return entry;
262       if (--entry < h->entries)
263         entry = &h->entries[h->size - 1];
264     }
265   h->used++;
266   return entry;
267 }
268
269 /* Locates an entry matching TARGET.  Returns a pointer to the
270    entry, or a null pointer on failure. */
271 static inline void **
272 locate_matching_entry (struct hsh_table *h, const void *target) 
273 {
274   void **entry = &h->entries[h->hash (target, h->param) & (h->size - 1)];
275
276   while (*entry)
277     {
278       if (!h->compare (*entry, target, h->param))
279         return entry;
280       if (--entry < h->entries)
281         entry = &h->entries[h->size - 1];
282     }
283   return NULL;
284 }
285
286 /* Returns the entry in hash table H that matches TARGET, or NULL
287    if there is none. */
288 void *
289 hsh_find (struct hsh_table *h, const void *target)
290 {
291   void **entry = locate_matching_entry (h, target);
292   return entry != NULL ? *entry : NULL;
293 }
294
295 /* Deletes the entry in hash table H that matches TARGET.
296    Returns nonzero if an entry was deleted.
297
298    Note: this function is very slow because it rehashes the
299    entire table.  Don't use this hash table implementation if
300    deletion is a common operation. */
301 int
302 hsh_delete (struct hsh_table *h, const void *target) 
303 {
304   void **entry = locate_matching_entry (h, target);
305   if (h->free != NULL) 
306     {
307       h->free (*entry, h->param);
308       *entry = 0;
309       hsh_rehash (h, h->size);
310       return 1;
311     }
312   else
313     return 0;
314 }
315 \f
316 /* Iteration. */
317
318 /* Finds and returns an entry in TABLE, and initializes ITER for
319    use with hsh_next().  If TABLE is empty, returns a null
320    pointer. */
321 void *
322 hsh_first (struct hsh_table *h, struct hsh_iterator *iter) 
323 {
324   assert (h != NULL);
325   assert (iter != NULL);
326
327   iter->next = 0;
328   return hsh_next (h, iter);
329 }
330
331 /* Iterates through TABLE with iterator ITER.  Returns the next
332    entry in TABLE, or a null pointer after the last entry.
333
334    Entries are returned in an undefined order.  Modifying TABLE
335    during iteration may cause some entries to be returned
336    multiple times or not at all. */
337 void *
338 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
339 {
340   size_t i;
341
342   assert (h != NULL);
343   assert (iter != NULL);
344   assert (iter->next <= h->size);
345
346   for (i = iter->next; i < h->size; i++)
347     if (h->entries[i])
348       {
349         iter->next = i + 1;
350         return h->entries[i];
351       }
352
353   iter->next = h->size;
354   return NULL;
355 }
356 \f
357 /* Returns the number of items in H. */
358 size_t 
359 hsh_count (struct hsh_table *h) 
360 {
361   assert (h != NULL);
362   
363   return h->used;
364 }
365 \f
366 /* Debug helpers. */
367
368 #if GLOBAL_DEBUGGING
369 #undef NDEBUG
370 #include <assert.h>
371 #include <stdio.h>
372
373 /* Displays contents of hash table H on stdout. */
374 void
375 hsh_dump (struct hsh_table *h)
376 {
377   void **entry = h->entries;
378   int i;
379
380   printf (_("hash table:"));
381   for (i = 0; i < h->size; i++)
382     printf (" %p", *entry++);
383   printf ("\n");
384 }
385
386 /* This wrapper around hsh_probe() assures that it returns a pointer
387    to a NULL pointer.  This function is used when it is known that the
388    entry to be inserted does not already exist in the table. */
389 void
390 hsh_force_insert (struct hsh_table *h, void *p)
391 {
392   void **pp = hsh_probe (h, p);
393   assert (*pp == NULL);
394   *pp = p;
395 }
396
397 /* This wrapper around hsh_find() assures that it returns non-NULL.
398    This function is for use when it is known that the entry being
399    searched for must exist in the table. */
400 void *
401 hsh_force_find (struct hsh_table *h, const void *target)
402 {
403   void *found = hsh_find (h, target);
404   assert (found != NULL);
405   return found;
406 }
407
408 /* This wrapper for hsh_delete() verifies that an item really was
409    deleted. */
410 void
411 hsh_force_delete (struct hsh_table *h, const void *target)
412 {
413   int found = hsh_delete (h, target);
414   assert (found != 0);
415 }
416 #endif