Replace safe_strcmp with g_strcmp0.
[pspp-builds.git] / src / libpspp / hash.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 1997-9, 2000, 2008 Free Software Foundation, Inc.
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, either version 3 of the License, or
7    (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18 #include <stdbool.h>
19 #include "hash.h"
20 #include "message.h"
21 #include <assert.h>
22 #include <limits.h>
23 #include <stdbool.h>
24 #include <stdlib.h>
25 #include "array.h"
26 #include "compiler.h"
27 #include "misc.h"
28 #include "str.h"
29 #include "pool.h"
30
31 #include "xalloc.h"
32
33 #include "gettext.h"
34 #define _(msgid) gettext (msgid)
35
36 /* Note for constructing hash functions:
37
38    You can store the hash values in the records, then compare hash
39    values (in the compare function) before bothering to compare keys.
40    Hash values can simply be returned from the records instead of
41    recalculating when rehashing. */
42
43 /* Debugging note:
44
45    Since hash_probe and hash_find take void * pointers, it's easy to
46    pass a void ** to your data by accidentally inserting an `&'
47    reference operator where one shouldn't go.  It took me an hour to
48    hunt down a bug like that once. */
49 \f
50 /* Prime numbers and hash functions. */
51
52 /* Returns smallest power of 2 greater than X. */
53 static size_t
54 next_power_of_2 (size_t x)
55 {
56   assert (x != 0);
57
58   for (;;)
59     {
60       /* Turn off rightmost 1-bit in x. */
61       size_t y = x & (x - 1);
62
63       /* If y is 0 then x only had a single 1-bit. */
64       if (y == 0)
65         return 2 * x;
66
67       /* Otherwise turn off the next. */
68       x = y;
69     }
70 }
71
72 \f
73 /* Hash tables. */
74
75 /* Hash table. */
76 struct hsh_table
77   {
78     size_t used;                /* Number of filled entries. */
79     size_t size;                /* Number of entries (a power of 2). */
80     void **entries;             /* Hash table proper. */
81
82     const void *aux;            /* Auxiliary data for comparison functions. */
83     hsh_compare_func *compare;
84     hsh_hash_func *hash;
85     hsh_free_func *free;
86
87 #ifndef NDEBUG
88     /* Set to false if hsh_data() or hsh_sort() has been called,
89        so that most hsh_*() functions may no longer be called. */
90     bool hash_ordered;
91 #endif
92
93     struct pool *pool;         /* The pool used for this hash table */
94   };
95
96 struct hsh_table *
97 hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
98             hsh_free_func *free, const void *aux)
99 {
100   return hsh_create_pool (NULL, size, compare, hash, free, aux);
101 }
102
103
104
105 /* Creates a hash table with at least M entries.  COMPARE is a
106    function that compares two entries and returns 0 if they are
107    identical, nonzero otherwise; HASH returns a nonnegative hash value
108    for an entry; FREE destroys an entry. */
109 struct hsh_table *
110 hsh_create_pool (struct pool *pool, int size,
111                  hsh_compare_func *compare, hsh_hash_func *hash,
112                  hsh_free_func *free, const void *aux)
113 {
114   struct hsh_table *h;
115   int i;
116
117   assert (compare != NULL);
118   assert (hash != NULL);
119
120   h = pool_malloc (pool, sizeof *h);
121   h->pool = pool;
122   h->used = 0;
123   if (size < 4)
124     size = 4;
125   h->size = next_power_of_2 (size);
126   h->entries = pool_nmalloc (pool, h->size, sizeof *h->entries);
127   for (i = 0; i < h->size; i++)
128     h->entries[i] = NULL;
129   h->aux = aux;
130   h->compare = compare;
131   h->hash = hash;
132   h->free = free;
133 #ifndef NDEBUG
134   h->hash_ordered = true;
135 #endif
136   return h;
137 }
138
139 /* Destroys the contents of table H. */
140 void
141 hsh_clear (struct hsh_table *h)
142 {
143   int i;
144
145   assert (h != NULL);
146   if (h->free)
147     for (i = 0; i < h->size; i++)
148       if (h->entries[i] != NULL)
149         h->free (h->entries[i], h->aux);
150
151   for (i = 0; i < h->size; i++)
152     h->entries[i] = NULL;
153
154   h->used = 0;
155
156 #ifndef NDEBUG
157   h->hash_ordered = true;
158 #endif
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     {
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->aux);
173       pool_free (h->pool, h->entries);
174       pool_free (h->pool, h);
175     }
176 }
177
178 /* Locates an entry matching TARGET.  Returns the index for the
179    entry, if found, or the index of an empty entry that indicates
180    where TARGET should go, otherwise. */
181 static inline unsigned
182 locate_matching_entry (struct hsh_table *h, const void *target)
183 {
184   unsigned i = h->hash (target, h->aux);
185
186   assert (h->hash_ordered);
187   for (;;)
188     {
189       void *entry;
190       i &= h->size - 1;
191       entry = h->entries[i];
192       if (entry == NULL || !h->compare (entry, target, h->aux))
193         return i;
194       i--;
195     }
196 }
197
198 /* Returns the index of an empty entry that indicates
199    where TARGET should go, assuming that TARGET is not equal to
200    any item already in the hash table. */
201 static inline unsigned
202 locate_empty_entry (struct hsh_table *h, const void *target)
203 {
204   unsigned i = h->hash (target, h->aux);
205
206   assert (h->hash_ordered);
207   for (;;)
208     {
209       i &= h->size - 1;
210       if (h->entries[i] == NULL)
211         return i;
212       i--;
213     }
214 }
215
216 /* Changes the capacity of H to NEW_SIZE, which must be a
217    positive power of 2 at least as large as the number of
218    elements in H. */
219 static void
220 rehash (struct hsh_table *h, size_t new_size)
221 {
222   void **begin, **end, **table_p;
223   int i;
224
225   assert (h != NULL);
226   assert (new_size >= h->used);
227
228   /* Verify that NEW_SIZE is a positive power of 2. */
229   assert (new_size > 0 && (new_size & (new_size - 1)) == 0);
230
231   begin = h->entries;
232   end = begin + h->size;
233
234   h->size = new_size;
235   h->entries = pool_nmalloc (h->pool, h->size, sizeof *h->entries);
236   for (i = 0; i < h->size; i++)
237     h->entries[i] = NULL;
238   for (table_p = begin; table_p < end; table_p++)
239     {
240       void *entry = *table_p;
241       if (entry != NULL)
242         h->entries[locate_empty_entry (h, entry)] = entry;
243     }
244   pool_free (h->pool, begin);
245
246 #ifndef NDEBUG
247   h->hash_ordered = true;
248 #endif
249 }
250
251 /* A "algo_predicate_func" that returns true if DATA points
252    to a non-null void. */
253 static bool
254 not_null (const void *data_, const void *aux UNUSED)
255 {
256   void *const *data = data_;
257
258   return *data != NULL;
259 }
260
261 /* Compacts hash table H and returns a pointer to its data.  The
262    returned data consists of hsh_count(H) non-null pointers, in
263    no particular order, followed by a null pointer.
264
265    After calling this function, only hsh_destroy() and
266    hsh_count() should be applied to H.  hsh_first() and
267    hsh_next() could also be used, but you're better off just
268    iterating through the returned array.
269
270    This function is intended for use in situations where data
271    processing occurs in two phases.  In the first phase, data is
272    added, removed, and searched for within a hash table.  In the
273    second phase, the contents of the hash table are output and
274    the hash property itself is no longer of interest.
275
276    Use hsh_sort() instead, if the second phase wants data in
277    sorted order.  Use hsh_data_copy() or hsh_sort_copy() instead,
278    if the second phase still needs to search the hash table. */
279 void *const *
280 hsh_data (struct hsh_table *h)
281 {
282   size_t n;
283
284   assert (h != NULL);
285   n = partition (h->entries, h->size, sizeof *h->entries, not_null, NULL);
286   assert (n == h->used);
287 #ifndef NDEBUG
288   h->hash_ordered = false;
289 #endif
290   return h->entries;
291 }
292
293 /* Dereferences void ** pointers and passes them to the hash
294    comparison function. */
295 static int
296 comparison_helper (const void *a_, const void *b_, const void *h_)
297 {
298   void *const *a = a_;
299   void *const *b = b_;
300   const struct hsh_table *h = h_;
301
302   assert(a);
303   assert(b);
304
305   return h->compare (*a, *b, h->aux);
306 }
307
308 /* Sorts hash table H based on hash comparison function.  The
309    returned data consists of hsh_count(H) non-null pointers,
310    sorted in order of the hash comparison function, followed by a
311    null pointer.
312
313    After calling this function, only hsh_destroy() and
314    hsh_count() should be applied to H.  hsh_first() and
315    hsh_next() could also be used, but you're better off just
316    iterating through the returned array.
317
318    This function is intended for use in situations where data
319    processing occurs in two phases.  In the first phase, data is
320    added, removed, and searched for within a hash table.  In the
321    second phase, the contents of the hash table are output and
322    the hash property itself is no longer of interest.
323
324    Use hsh_data() instead, if the second phase doesn't need the
325    data in any particular order.  Use hsh_data_copy() or
326    hsh_sort_copy() instead, if the second phase still needs to
327    search the hash table. */
328 void *const *
329 hsh_sort (struct hsh_table *h)
330 {
331   assert (h != NULL);
332
333   hsh_data (h);
334   sort (h->entries, h->used, sizeof *h->entries, comparison_helper, h);
335   return h->entries;
336 }
337
338 /* Makes and returns a copy of the pointers to the data in H.
339    The returned data consists of hsh_count(H) non-null pointers,
340    in no particular order, followed by a null pointer.  The hash
341    table is not modified.  The caller is responsible for freeing
342    the allocated data.
343
344    If you don't need to search or modify the hash table, then
345    hsh_data() is a more efficient choice. */
346 void **
347 hsh_data_copy (struct hsh_table *h)
348 {
349   void **copy;
350
351   assert (h != NULL);
352   copy = pool_nmalloc (h->pool, (h->used + 1), sizeof *copy);
353   copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL);
354   copy[h->used] = NULL;
355   return copy;
356 }
357
358 /* Makes and returns a copy of the pointers to the data in H.
359    The returned data consists of hsh_count(H) non-null pointers,
360    sorted in order of the hash comparison function, followed by a
361    null pointer.  The hash table is not modified.  The caller is
362    responsible for freeing the allocated data.
363
364    If you don't need to search or modify the hash table, then
365    hsh_sort() is a more efficient choice. */
366 void **
367 hsh_sort_copy (struct hsh_table *h)
368 {
369   void **copy;
370
371   assert (h != NULL);
372   copy = hsh_data_copy (h);
373   sort (copy, h->used, sizeof *copy, comparison_helper, h);
374   return copy;
375 }
376 \f
377 /* Hash entries. */
378
379 /* Searches hash table H for TARGET.  If found, returns a pointer
380    to a pointer to that entry; otherwise returns a pointer to a
381    NULL entry which *must* be used to insert a new entry having
382    the same key data.  */
383 void **
384 hsh_probe (struct hsh_table *h, const void *target)
385 {
386   unsigned i;
387
388   assert (h != NULL);
389   assert (target != NULL);
390   assert (h->hash_ordered);
391
392   if (h->used > h->size / 2)
393     rehash (h, h->size * 2);
394   i = locate_matching_entry (h, target);
395   if (h->entries[i] == NULL)
396     h->used++;
397   return &h->entries[i];
398 }
399
400 /* Searches hash table H for TARGET.  If not found, inserts
401    TARGET and returns a null pointer.  If found, returns the
402    match, without replacing it in the table. */
403 void *
404 hsh_insert (struct hsh_table *h, void *target)
405 {
406   void **entry;
407
408   assert (h != NULL);
409   assert (target != NULL);
410
411   entry = hsh_probe (h, target);
412   if (*entry == NULL)
413     {
414       *entry = target;
415       return NULL;
416     }
417   else
418     return *entry;
419 }
420
421 /* Searches hash table H for TARGET.  If not found, inserts
422    TARGET and returns a null pointer.  If found, returns the
423    match, after replacing it in the table by TARGET. */
424 void *
425 hsh_replace (struct hsh_table *h, void *target)
426 {
427   void **entry = hsh_probe (h, target);
428   void *old = *entry;
429   *entry = target;
430   return old;
431 }
432
433 /* Returns the entry in hash table H that matches TARGET, or NULL
434    if there is none. */
435 void *
436 hsh_find (struct hsh_table *h, const void *target)
437 {
438   return h->entries[locate_matching_entry (h, target)];
439 }
440
441 /* Deletes the entry in hash table H that matches TARGET.
442    Returns true if an entry was deleted.
443
444    Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
445    Because our load factor is at most 1/2, the average number of
446    moves that this algorithm makes should be at most 2 - ln 2 ~=
447    1.65. */
448 bool
449 hsh_delete (struct hsh_table *h, const void *target)
450 {
451   unsigned i = locate_matching_entry (h, target);
452   if (h->entries[i] != NULL)
453     {
454       h->used--;
455       if (h->free != NULL)
456         h->free (h->entries[i], h->aux);
457
458       for (;;)
459         {
460           unsigned r;
461           ptrdiff_t j;
462
463           h->entries[i] = NULL;
464           j = i;
465           do
466             {
467               i = (i - 1) & (h->size - 1);
468               if (h->entries[i] == NULL)
469                 return true;
470
471               r = h->hash (h->entries[i], h->aux) & (h->size - 1);
472             }
473           while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
474           h->entries[j] = h->entries[i];
475         }
476     }
477   else
478     return false;
479 }
480 \f
481 /* Iteration. */
482
483 /* Finds and returns an entry in TABLE, and initializes ITER for
484    use with hsh_next().  If TABLE is empty, returns a null
485    pointer. */
486 void *
487 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
488 {
489   assert (h != NULL);
490   assert (iter != NULL);
491
492   iter->next = 0;
493   return hsh_next (h, iter);
494 }
495
496 /* Iterates through TABLE with iterator ITER.  Returns the next
497    entry in TABLE, or a null pointer after the last entry.
498
499    Entries are returned in an undefined order.  Modifying TABLE
500    during iteration may cause some entries to be returned
501    multiple times or not at all. */
502 void *
503 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
504 {
505   size_t i;
506
507   assert (h != NULL);
508   assert (iter != NULL);
509   assert (iter->next <= h->size);
510
511   for (i = iter->next; i < h->size; i++)
512     if (h->entries[i])
513       {
514         iter->next = i + 1;
515         return h->entries[i];
516       }
517
518   iter->next = h->size;
519   return NULL;
520 }
521 \f
522 /* Returns the number of items in H. */
523 size_t
524 hsh_count (struct hsh_table *h)
525 {
526   assert (h != NULL);
527
528   return h->used;
529 }
530 \f
531 /* Debug helpers. */
532
533 #if DEBUGGING
534 #undef NDEBUG
535 #include "message.h"
536 #include <stdio.h>
537
538 /* Displays contents of hash table H on stdout. */
539 void
540 hsh_dump (struct hsh_table *h)
541 {
542   void **entry = h->entries;
543   int i;
544
545   printf (_("hash table:"));
546   for (i = 0; i < h->size; i++)
547     printf (" %p", *entry++);
548   printf ("\n");
549 }
550
551 /* This wrapper around hsh_probe() assures that it returns a pointer
552    to a NULL pointer.  This function is used when it is known that the
553    entry to be inserted does not already exist in the table. */
554 void
555 hsh_force_insert (struct hsh_table *h, void *p)
556 {
557   void **pp = hsh_probe (h, p);
558   assert (*pp == NULL);
559   *pp = p;
560 }
561
562 /* This wrapper around hsh_find() assures that it returns non-NULL.
563    This function is for use when it is known that the entry being
564    searched for must exist in the table. */
565 void *
566 hsh_force_find (struct hsh_table *h, const void *target)
567 {
568   void *found = hsh_find (h, target);
569   assert (found != NULL);
570   return found;
571 }
572
573 /* This wrapper for hsh_delete() verifies that an item really was
574    deleted. */
575 void
576 hsh_force_delete (struct hsh_table *h, const void *target)
577 {
578   int found = hsh_delete (h, target);
579   assert (found != 0);
580 }
581 #endif