--- /dev/null
+/* PSPP - computes sample statistics.
+ Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
+ Written by Ben Pfaff <blp@gnu.org>.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
+
+#include <config.h>
+#include "hash.h"
+#include "message.h"
+#include <assert.h>
+#include <ctype.h>
+#include <limits.h>
+#include <stdlib.h>
+#include "array.h"
+#include "alloc.h"
+#include <stdbool.h>
+#include "misc.h"
+#include "str.h"
+
+#include "gettext.h"
+#define _(msgid) gettext (msgid)
+
+/* Note for constructing hash functions:
+
+ You can store the hash values in the records, then compare hash
+ values (in the compare function) before bothering to compare keys.
+ Hash values can simply be returned from the records instead of
+ recalculating when rehashing. */
+
+/* Debugging note:
+
+ Since hash_probe and hash_find take void * pointers, it's easy to
+ pass a void ** to your data by accidentally inserting an `&'
+ reference operator where one shouldn't go. It took me an hour to
+ hunt down a bug like that once. */
+\f
+/* Prime numbers and hash functions. */
+
+/* Returns smallest power of 2 greater than X. */
+static size_t
+next_power_of_2 (size_t x)
+{
+ assert (x != 0);
+
+ for (;;)
+ {
+ /* Turn off rightmost 1-bit in x. */
+ size_t y = x & (x - 1);
+
+ /* If y is 0 then x only had a single 1-bit. */
+ if (y == 0)
+ return 2 * x;
+
+ /* Otherwise turn off the next. */
+ x = y;
+ }
+}
+
+/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
+#define FNV_32_PRIME 16777619u
+#define FNV_32_BASIS 2166136261u
+
+/* Fowler-Noll-Vo 32-bit hash, for bytes. */
+unsigned
+hsh_hash_bytes (const void *buf_, size_t size)
+{
+ const unsigned char *buf = (const unsigned char *) buf_;
+ unsigned hash;
+
+ assert (buf != NULL);
+
+ hash = FNV_32_BASIS;
+ while (size-- > 0)
+ hash = (hash * FNV_32_PRIME) ^ *buf++;
+
+ return hash;
+}
+
+/* Fowler-Noll-Vo 32-bit hash, for strings. */
+unsigned
+hsh_hash_string (const char *s_)
+{
+ const unsigned char *s = (const unsigned char *) s_;
+ unsigned hash;
+
+ assert (s != NULL);
+
+ hash = FNV_32_BASIS;
+ while (*s != '\0')
+ hash = (hash * FNV_32_PRIME) ^ *s++;
+
+ return hash;
+}
+
+/* Fowler-Noll-Vo 32-bit hash, for case-insensitive strings. */
+unsigned
+hsh_hash_case_string (const char *s_)
+{
+ const unsigned char *s = (const unsigned char *) s_;
+ unsigned hash;
+
+ assert (s != NULL);
+
+ hash = FNV_32_BASIS;
+ while (*s != '\0')
+ hash = (hash * FNV_32_PRIME) ^ toupper (*s++);
+
+ return hash;
+}
+
+/* Hash for ints. */
+unsigned
+hsh_hash_int (int i)
+{
+ return hsh_hash_bytes (&i, sizeof i);
+}
+
+/* Hash for double. */
+unsigned
+hsh_hash_double (double d)
+{
+ if (!isnan (d))
+ return hsh_hash_bytes (&d, sizeof d);
+ else
+ return 0;
+}
+\f
+/* Hash tables. */
+
+/* Hash table. */
+struct hsh_table
+ {
+ size_t used; /* Number of filled entries. */
+ size_t size; /* Number of entries (a power of 2). */
+ void **entries; /* Hash table proper. */
+
+ void *aux; /* Auxiliary data for comparison functions. */
+ hsh_compare_func *compare;
+ hsh_hash_func *hash;
+ hsh_free_func *free;
+
+#ifndef NDEBUG
+ /* Set to false if hsh_data() or hsh_sort() has been called,
+ so that most hsh_*() functions may no longer be called. */
+ bool hash_ordered;
+#endif
+ };
+
+/* Creates a hash table with at least M entries. COMPARE is a
+ function that compares two entries and returns 0 if they are
+ identical, nonzero otherwise; HASH returns a nonnegative hash value
+ for an entry; FREE destroys an entry. */
+struct hsh_table *
+hsh_create (int size, hsh_compare_func *compare, hsh_hash_func *hash,
+ hsh_free_func *free, void *aux)
+{
+ struct hsh_table *h;
+ int i;
+
+ assert (compare != NULL);
+ assert (hash != NULL);
+
+ h = xmalloc (sizeof *h);
+ h->used = 0;
+ if (size < 4)
+ size = 4;
+ h->size = next_power_of_2 (size);
+ h->entries = xnmalloc (h->size, sizeof *h->entries);
+ for (i = 0; i < h->size; i++)
+ h->entries[i] = NULL;
+ h->aux = aux;
+ h->compare = compare;
+ h->hash = hash;
+ h->free = free;
+#ifndef NDEBUG
+ h->hash_ordered = true;
+#endif
+ return h;
+}
+
+/* Destroys the contents of table H. */
+void
+hsh_clear (struct hsh_table *h)
+{
+ int i;
+
+ assert (h != NULL);
+ if (h->free)
+ for (i = 0; i < h->size; i++)
+ if (h->entries[i] != NULL)
+ h->free (h->entries[i], h->aux);
+
+ for (i = 0; i < h->size; i++)
+ h->entries[i] = NULL;
+
+ h->used = 0;
+
+#ifndef NDEBUG
+ h->hash_ordered = true;
+#endif
+}
+
+/* Destroys table H and all its contents. */
+void
+hsh_destroy (struct hsh_table *h)
+{
+ int i;
+
+ if (h != NULL)
+ {
+ if (h->free)
+ for (i = 0; i < h->size; i++)
+ if (h->entries[i] != NULL)
+ h->free (h->entries[i], h->aux);
+ free (h->entries);
+ free (h);
+ }
+}
+
+/* Locates an entry matching TARGET. Returns a pointer to the
+ entry, or a null pointer on failure. */
+static inline unsigned
+locate_matching_entry (struct hsh_table *h, const void *target)
+{
+ unsigned i = h->hash (target, h->aux);
+
+ assert (h->hash_ordered);
+ for (;;)
+ {
+ void *entry;
+ i &= h->size - 1;
+ entry = h->entries[i];
+ if (entry == NULL || !h->compare (entry, target, h->aux))
+ return i;
+ i--;
+ }
+}
+
+/* Changes the capacity of H to NEW_SIZE, which must be a
+ positive power of 2 at least as large as the number of
+ elements in H. */
+static void
+rehash (struct hsh_table *h, size_t new_size)
+{
+ void **begin, **end, **table_p;
+ int i;
+
+ assert (h != NULL);
+ assert (new_size >= h->used);
+
+ /* Verify that NEW_SIZE is a positive power of 2. */
+ assert (new_size > 0 && (new_size & (new_size - 1)) == 0);
+
+ begin = h->entries;
+ end = begin + h->size;
+
+ h->size = new_size;
+ h->entries = xnmalloc (h->size, sizeof *h->entries);
+ for (i = 0; i < h->size; i++)
+ h->entries[i] = NULL;
+ for (table_p = begin; table_p < end; table_p++)
+ {
+ void *entry = *table_p;
+ if (entry != NULL)
+ h->entries[locate_matching_entry (h, entry)] = entry;
+ }
+ free (begin);
+
+#ifndef NDEBUG
+ h->hash_ordered = true;
+#endif
+}
+
+/* A "algo_predicate_func" that returns nonzero if DATA points
+ to a non-null void. */
+static int
+not_null (const void *data_, void *aux UNUSED)
+{
+ void *const *data = data_;
+
+ return *data != NULL;
+}
+
+/* Compacts hash table H and returns a pointer to its data. The
+ returned data consists of hsh_count(H) non-null pointers, in
+ no particular order, followed by a null pointer.
+
+ After calling this function, only hsh_destroy() and
+ hsh_count() should be applied to H. hsh_first() and
+ hsh_next() could also be used, but you're better off just
+ iterating through the returned array.
+
+ This function is intended for use in situations where data
+ processing occurs in two phases. In the first phase, data is
+ added, removed, and searched for within a hash table. In the
+ second phase, the contents of the hash table are output and
+ the hash property itself is no longer of interest.
+
+ Use hsh_sort() instead, if the second phase wants data in
+ sorted order. Use hsh_data_copy() or hsh_sort_copy() instead,
+ if the second phase still needs to search the hash table. */
+void *const *
+hsh_data (struct hsh_table *h)
+{
+ size_t n;
+
+ assert (h != NULL);
+ n = partition (h->entries, h->size, sizeof *h->entries, not_null, NULL);
+ assert (n == h->used);
+#ifndef NDEBUG
+ h->hash_ordered = false;
+#endif
+ return h->entries;
+}
+
+/* Dereferences void ** pointers and passes them to the hash
+ comparison function. */
+static int
+comparison_helper (const void *a_, const void *b_, void *h_)
+{
+ void *const *a = a_;
+ void *const *b = b_;
+ struct hsh_table *h = h_;
+
+ assert(a);
+ assert(b);
+
+ return h->compare (*a, *b, h->aux);
+}
+
+/* Sorts hash table H based on hash comparison function. The
+ returned data consists of hsh_count(H) non-null pointers,
+ sorted in order of the hash comparison function, followed by a
+ null pointer.
+
+ After calling this function, only hsh_destroy() and
+ hsh_count() should be applied to H. hsh_first() and
+ hsh_next() could also be used, but you're better off just
+ iterating through the returned array.
+
+ This function is intended for use in situations where data
+ processing occurs in two phases. In the first phase, data is
+ added, removed, and searched for within a hash table. In the
+ second phase, the contents of the hash table are output and
+ the hash property itself is no longer of interest.
+
+ Use hsh_data() instead, if the second phase doesn't need the
+ data in any particular order. Use hsh_data_copy() or
+ hsh_sort_copy() instead, if the second phase still needs to
+ search the hash table. */
+void *const *
+hsh_sort (struct hsh_table *h)
+{
+ assert (h != NULL);
+
+ hsh_data (h);
+ sort (h->entries, h->used, sizeof *h->entries, comparison_helper, h);
+ return h->entries;
+}
+
+/* Makes and returns a copy of the pointers to the data in H.
+ The returned data consists of hsh_count(H) non-null pointers,
+ in no particular order, followed by a null pointer. The hash
+ table is not modified. The caller is responsible for freeing
+ the allocated data.
+
+ If you don't need to search or modify the hash table, then
+ hsh_data() is a more efficient choice. */
+void **
+hsh_data_copy (struct hsh_table *h)
+{
+ void **copy;
+
+ assert (h != NULL);
+ copy = xnmalloc ((h->used + 1), sizeof *copy);
+ copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL);
+ copy[h->used] = NULL;
+ return copy;
+}
+
+/* Makes and returns a copy of the pointers to the data in H.
+ The returned data consists of hsh_count(H) non-null pointers,
+ sorted in order of the hash comparison function, followed by a
+ null pointer. The hash table is not modified. The caller is
+ responsible for freeing the allocated data.
+
+ If you don't need to search or modify the hash table, then
+ hsh_sort() is a more efficient choice. */
+void **
+hsh_sort_copy (struct hsh_table *h)
+{
+ void **copy;
+
+ assert (h != NULL);
+ copy = hsh_data_copy (h);
+ sort (copy, h->used, sizeof *copy, comparison_helper, h);
+ return copy;
+}
+\f
+/* Hash entries. */
+
+/* Searches hash table H for TARGET. If found, returns a pointer
+ to a pointer to that entry; otherwise returns a pointer to a
+ NULL entry which *must* be used to insert a new entry having
+ the same key data. */
+inline void **
+hsh_probe (struct hsh_table *h, const void *target)
+{
+ unsigned i;
+
+ assert (h != NULL);
+ assert (target != NULL);
+ assert (h->hash_ordered);
+
+ if (h->used > h->size / 2)
+ rehash (h, h->size * 2);
+ i = locate_matching_entry (h, target);
+ if (h->entries[i] == NULL)
+ h->used++;
+ return &h->entries[i];
+}
+
+/* Searches hash table H for TARGET. If not found, inserts
+ TARGET and returns a null pointer. If found, returns the
+ match, without replacing it in the table. */
+void *
+hsh_insert (struct hsh_table *h, void *target)
+{
+ void **entry;
+
+ assert (h != NULL);
+ assert (target != NULL);
+
+ entry = hsh_probe (h, target);
+ if (*entry == NULL)
+ {
+ *entry = target;
+ return NULL;
+ }
+ else
+ return *entry;
+}
+
+/* Searches hash table H for TARGET. If not found, inserts
+ TARGET and returns a null pointer. If found, returns the
+ match, after replacing it in the table by TARGET. */
+void *
+hsh_replace (struct hsh_table *h, void *target)
+{
+ void **entry = hsh_probe (h, target);
+ void *old = *entry;
+ *entry = target;
+ return old;
+}
+
+/* Returns the entry in hash table H that matches TARGET, or NULL
+ if there is none. */
+void *
+hsh_find (struct hsh_table *h, const void *target)
+{
+ return h->entries[locate_matching_entry (h, target)];
+}
+
+/* Deletes the entry in hash table H that matches TARGET.
+ Returns nonzero if an entry was deleted.
+
+ Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
+ Because our load factor is at most 1/2, the average number of
+ moves that this algorithm makes should be at most 2 - ln 2 ~=
+ 1.65. */
+int
+hsh_delete (struct hsh_table *h, const void *target)
+{
+ unsigned i = locate_matching_entry (h, target);
+ if (h->entries[i] != NULL)
+ {
+ h->used--;
+ if (h->free != NULL)
+ h->free (h->entries[i], h->aux);
+
+ for (;;)
+ {
+ unsigned r;
+ ptrdiff_t j;
+
+ h->entries[i] = NULL;
+ j = i;
+ do
+ {
+ i = (i - 1) & (h->size - 1);
+ if (h->entries[i] == NULL)
+ return 1;
+
+ r = h->hash (h->entries[i], h->aux) & (h->size - 1);
+ }
+ while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
+ h->entries[j] = h->entries[i];
+ }
+ }
+ else
+ return 0;
+}
+\f
+/* Iteration. */
+
+/* Finds and returns an entry in TABLE, and initializes ITER for
+ use with hsh_next(). If TABLE is empty, returns a null
+ pointer. */
+void *
+hsh_first (struct hsh_table *h, struct hsh_iterator *iter)
+{
+ assert (h != NULL);
+ assert (iter != NULL);
+
+ iter->next = 0;
+ return hsh_next (h, iter);
+}
+
+/* Iterates through TABLE with iterator ITER. Returns the next
+ entry in TABLE, or a null pointer after the last entry.
+
+ Entries are returned in an undefined order. Modifying TABLE
+ during iteration may cause some entries to be returned
+ multiple times or not at all. */
+void *
+hsh_next (struct hsh_table *h, struct hsh_iterator *iter)
+{
+ size_t i;
+
+ assert (h != NULL);
+ assert (iter != NULL);
+ assert (iter->next <= h->size);
+
+ for (i = iter->next; i < h->size; i++)
+ if (h->entries[i])
+ {
+ iter->next = i + 1;
+ return h->entries[i];
+ }
+
+ iter->next = h->size;
+ return NULL;
+}
+\f
+/* Returns the number of items in H. */
+size_t
+hsh_count (struct hsh_table *h)
+{
+ assert (h != NULL);
+
+ return h->used;
+}
+\f
+/* Debug helpers. */
+
+#if GLOBAL_DEBUGGING
+#undef NDEBUG
+#include "message.h"
+#include <stdio.h>
+
+/* Displays contents of hash table H on stdout. */
+void
+hsh_dump (struct hsh_table *h)
+{
+ void **entry = h->entries;
+ int i;
+
+ printf (_("hash table:"));
+ for (i = 0; i < h->size; i++)
+ printf (" %p", *entry++);
+ printf ("\n");
+}
+
+/* This wrapper around hsh_probe() assures that it returns a pointer
+ to a NULL pointer. This function is used when it is known that the
+ entry to be inserted does not already exist in the table. */
+void
+hsh_force_insert (struct hsh_table *h, void *p)
+{
+ void **pp = hsh_probe (h, p);
+ assert (*pp == NULL);
+ *pp = p;
+}
+
+/* This wrapper around hsh_find() assures that it returns non-NULL.
+ This function is for use when it is known that the entry being
+ searched for must exist in the table. */
+void *
+hsh_force_find (struct hsh_table *h, const void *target)
+{
+ void *found = hsh_find (h, target);
+ assert (found != NULL);
+ return found;
+}
+
+/* This wrapper for hsh_delete() verifies that an item really was
+ deleted. */
+void
+hsh_force_delete (struct hsh_table *h, const void *target)
+{
+ int found = hsh_delete (h, target);
+ assert (found != 0);
+}
+#endif
projects / pspp-builds.git / blobdiff