1 /* PSPP - computes sample statistics.
2 Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
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.
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.
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., 51 Franklin Street, Fifth Floor, Boston, MA
35 #define _(msgid) gettext (msgid)
37 /* Note for constructing hash functions:
39 You can store the hash values in the records, then compare hash
40 values (in the compare function) before bothering to compare keys.
41 Hash values can simply be returned from the records instead of
42 recalculating when rehashing. */
46 Since hash_probe and hash_find take void * pointers, it's easy to
47 pass a void ** to your data by accidentally inserting an `&'
48 reference operator where one shouldn't go. It took me an hour to
49 hunt down a bug like that once. */
51 /* Prime numbers and hash functions. */
53 /* Returns smallest power of 2 greater than X. */
55 next_power_of_2 (size_t x)
61 /* Turn off rightmost 1-bit in x. */
62 size_t y = x & (x - 1);
64 /* If y is 0 then x only had a single 1-bit. */
68 /* Otherwise turn off the next. */
73 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
74 #define FNV_32_PRIME 16777619u
75 #define FNV_32_BASIS 2166136261u
77 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
79 hsh_hash_bytes (const void *buf_, size_t size)
81 const unsigned char *buf = (const unsigned char *) buf_;
88 hash = (hash * FNV_32_PRIME) ^ *buf++;
93 /* Fowler-Noll-Vo 32-bit hash, for strings. */
95 hsh_hash_string (const char *s_)
97 const unsigned char *s = (const unsigned char *) s_;
104 hash = (hash * FNV_32_PRIME) ^ *s++;
109 /* Fowler-Noll-Vo 32-bit hash, for case-insensitive strings. */
111 hsh_hash_case_string (const char *s_)
113 const unsigned char *s = (const unsigned char *) s_;
120 hash = (hash * FNV_32_PRIME) ^ toupper (*s++);
129 return hsh_hash_bytes (&i, sizeof i);
132 /* Hash for double. */
134 hsh_hash_double (double d)
137 return hsh_hash_bytes (&d, sizeof d);
147 size_t used; /* Number of filled entries. */
148 size_t size; /* Number of entries (a power of 2). */
149 void **entries; /* Hash table proper. */
151 void *aux; /* Auxiliary data for comparison functions. */
152 hsh_compare_func *compare;
157 /* Set to false if hsh_data() or hsh_sort() has been called,
158 so that most hsh_*() functions may no longer be called. */
163 /* Creates a hash table with at least M entries. COMPARE is a
164 function that compares two entries and returns 0 if they are
165 identical, nonzero otherwise; HASH returns a nonnegative hash value
166 for an entry; FREE destroys an entry. */
168 hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
169 hsh_free_func *free, void *aux)
174 assert (compare != NULL);
175 assert (hash != NULL);
177 h = xmalloc (sizeof *h);
181 h->size = next_power_of_2 (size);
182 h->entries = xnmalloc (h->size, sizeof *h->entries);
183 for (i = 0; i < h->size; i++)
184 h->entries[i] = NULL;
186 h->compare = compare;
190 h->hash_ordered = true;
195 /* Destroys the contents of table H. */
197 hsh_clear (struct hsh_table *h)
203 for (i = 0; i < h->size; i++)
204 if (h->entries[i] != NULL)
205 h->free (h->entries[i], h->aux);
207 for (i = 0; i < h->size; i++)
208 h->entries[i] = NULL;
213 h->hash_ordered = true;
217 /* Destroys table H and all its contents. */
219 hsh_destroy (struct hsh_table *h)
226 for (i = 0; i < h->size; i++)
227 if (h->entries[i] != NULL)
228 h->free (h->entries[i], h->aux);
234 /* Locates an entry matching TARGET. Returns a pointer to the
235 entry, or a null pointer on failure. */
236 static inline unsigned
237 locate_matching_entry (struct hsh_table *h, const void *target)
239 unsigned i = h->hash (target, h->aux);
241 assert (h->hash_ordered);
246 entry = h->entries[i];
247 if (entry == NULL || !h->compare (entry, target, h->aux))
253 /* Changes the capacity of H to NEW_SIZE, which must be a
254 positive power of 2 at least as large as the number of
257 rehash (struct hsh_table *h, size_t new_size)
259 void **begin, **end, **table_p;
263 assert (new_size >= h->used);
265 /* Verify that NEW_SIZE is a positive power of 2. */
266 assert (new_size > 0 && (new_size & (new_size - 1)) == 0);
269 end = begin + h->size;
272 h->entries = xnmalloc (h->size, sizeof *h->entries);
273 for (i = 0; i < h->size; i++)
274 h->entries[i] = NULL;
275 for (table_p = begin; table_p < end; table_p++)
277 void *entry = *table_p;
279 h->entries[locate_matching_entry (h, entry)] = entry;
284 h->hash_ordered = true;
288 /* A "algo_predicate_func" that returns nonzero if DATA points
289 to a non-null void. */
291 not_null (const void *data_, void *aux UNUSED)
293 void *const *data = data_;
295 return *data != NULL;
298 /* Compacts hash table H and returns a pointer to its data. The
299 returned data consists of hsh_count(H) non-null pointers, in
300 no particular order, followed by a null pointer.
302 After calling this function, only hsh_destroy() and
303 hsh_count() should be applied to H. hsh_first() and
304 hsh_next() could also be used, but you're better off just
305 iterating through the returned array.
307 This function is intended for use in situations where data
308 processing occurs in two phases. In the first phase, data is
309 added, removed, and searched for within a hash table. In the
310 second phase, the contents of the hash table are output and
311 the hash property itself is no longer of interest.
313 Use hsh_sort() instead, if the second phase wants data in
314 sorted order. Use hsh_data_copy() or hsh_sort_copy() instead,
315 if the second phase still needs to search the hash table. */
317 hsh_data (struct hsh_table *h)
322 n = partition (h->entries, h->size, sizeof *h->entries, not_null, NULL);
323 assert (n == h->used);
325 h->hash_ordered = false;
330 /* Dereferences void ** pointers and passes them to the hash
331 comparison function. */
333 comparison_helper (const void *a_, const void *b_, void *h_)
337 struct hsh_table *h = h_;
342 return h->compare (*a, *b, h->aux);
345 /* Sorts hash table H based on hash comparison function. The
346 returned data consists of hsh_count(H) non-null pointers,
347 sorted in order of the hash comparison function, followed by a
350 After calling this function, only hsh_destroy() and
351 hsh_count() should be applied to H. hsh_first() and
352 hsh_next() could also be used, but you're better off just
353 iterating through the returned array.
355 This function is intended for use in situations where data
356 processing occurs in two phases. In the first phase, data is
357 added, removed, and searched for within a hash table. In the
358 second phase, the contents of the hash table are output and
359 the hash property itself is no longer of interest.
361 Use hsh_data() instead, if the second phase doesn't need the
362 data in any particular order. Use hsh_data_copy() or
363 hsh_sort_copy() instead, if the second phase still needs to
364 search the hash table. */
366 hsh_sort (struct hsh_table *h)
371 sort (h->entries, h->used, sizeof *h->entries, comparison_helper, h);
375 /* Makes and returns a copy of the pointers to the data in H.
376 The returned data consists of hsh_count(H) non-null pointers,
377 in no particular order, followed by a null pointer. The hash
378 table is not modified. The caller is responsible for freeing
381 If you don't need to search or modify the hash table, then
382 hsh_data() is a more efficient choice. */
384 hsh_data_copy (struct hsh_table *h)
389 copy = xnmalloc ((h->used + 1), sizeof *copy);
390 copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL);
391 copy[h->used] = NULL;
395 /* Makes and returns a copy of the pointers to the data in H.
396 The returned data consists of hsh_count(H) non-null pointers,
397 sorted in order of the hash comparison function, followed by a
398 null pointer. The hash table is not modified. The caller is
399 responsible for freeing the allocated data.
401 If you don't need to search or modify the hash table, then
402 hsh_sort() is a more efficient choice. */
404 hsh_sort_copy (struct hsh_table *h)
409 copy = hsh_data_copy (h);
410 sort (copy, h->used, sizeof *copy, comparison_helper, h);
416 /* Searches hash table H for TARGET. If found, returns a pointer
417 to a pointer to that entry; otherwise returns a pointer to a
418 NULL entry which *must* be used to insert a new entry having
419 the same key data. */
421 hsh_probe (struct hsh_table *h, const void *target)
426 assert (target != NULL);
427 assert (h->hash_ordered);
429 if (h->used > h->size / 2)
430 rehash (h, h->size * 2);
431 i = locate_matching_entry (h, target);
432 if (h->entries[i] == NULL)
434 return &h->entries[i];
437 /* Searches hash table H for TARGET. If not found, inserts
438 TARGET and returns a null pointer. If found, returns the
439 match, without replacing it in the table. */
441 hsh_insert (struct hsh_table *h, void *target)
446 assert (target != NULL);
448 entry = hsh_probe (h, target);
458 /* Searches hash table H for TARGET. If not found, inserts
459 TARGET and returns a null pointer. If found, returns the
460 match, after replacing it in the table by TARGET. */
462 hsh_replace (struct hsh_table *h, void *target)
464 void **entry = hsh_probe (h, target);
470 /* Returns the entry in hash table H that matches TARGET, or NULL
473 hsh_find (struct hsh_table *h, const void *target)
475 return h->entries[locate_matching_entry (h, target)];
478 /* Deletes the entry in hash table H that matches TARGET.
479 Returns nonzero if an entry was deleted.
481 Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
482 Because our load factor is at most 1/2, the average number of
483 moves that this algorithm makes should be at most 2 - ln 2 ~=
486 hsh_delete (struct hsh_table *h, const void *target)
488 unsigned i = locate_matching_entry (h, target);
489 if (h->entries[i] != NULL)
493 h->free (h->entries[i], h->aux);
500 h->entries[i] = NULL;
504 i = (i - 1) & (h->size - 1);
505 if (h->entries[i] == NULL)
508 r = h->hash (h->entries[i], h->aux) & (h->size - 1);
510 while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
511 h->entries[j] = h->entries[i];
520 /* Finds and returns an entry in TABLE, and initializes ITER for
521 use with hsh_next(). If TABLE is empty, returns a null
524 hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
527 assert (iter != NULL);
530 return hsh_next (h, iter);
533 /* Iterates through TABLE with iterator ITER. Returns the next
534 entry in TABLE, or a null pointer after the last entry.
536 Entries are returned in an undefined order. Modifying TABLE
537 during iteration may cause some entries to be returned
538 multiple times or not at all. */
540 hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
545 assert (iter != NULL);
546 assert (iter->next <= h->size);
548 for (i = iter->next; i < h->size; i++)
552 return h->entries[i];
555 iter->next = h->size;
559 /* Returns the number of items in H. */
561 hsh_count (struct hsh_table *h)
575 /* Displays contents of hash table H on stdout. */
577 hsh_dump (struct hsh_table *h)
579 void **entry = h->entries;
582 printf (_("hash table:"));
583 for (i = 0; i < h->size; i++)
584 printf (" %p", *entry++);
588 /* This wrapper around hsh_probe() assures that it returns a pointer
589 to a NULL pointer. This function is used when it is known that the
590 entry to be inserted does not already exist in the table. */
592 hsh_force_insert (struct hsh_table *h, void *p)
594 void **pp = hsh_probe (h, p);
595 assert (*pp == NULL);
599 /* This wrapper around hsh_find() assures that it returns non-NULL.
600 This function is for use when it is known that the entry being
601 searched for must exist in the table. */
603 hsh_force_find (struct hsh_table *h, const void *target)
605 void *found = hsh_find (h, target);
606 assert (found != NULL);
610 /* This wrapper for hsh_delete() verifies that an item really was
613 hsh_force_delete (struct hsh_table *h, const void *target)
615 int found = hsh_delete (h, target);