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., 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA. */
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
#include <config.h>
+#include "hash.h"
+#include "error.h"
#include <assert.h>
+#include <ctype.h>
#include <limits.h>
#include <stdlib.h>
#include "algorithm.h"
#include "alloc.h"
-#include "hash.h"
+#include <stdbool.h>
#include "misc.h"
#include "str.h"
-/* 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;
- };
+#include "gettext.h"
+#define _(msgid) gettext (msgid)
/* Note for constructing hash functions:
}
}
-/* Colin Plumb's "one-at-a-time" hash, for bytes. */
+/* 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 = buf_;
- unsigned hash = 0;
+ unsigned hash;
assert (buf != NULL);
- while (size-- > 0)
- {
- hash += *buf++;
- hash += (hash << 10);
- hash ^= (hash >> 6);
- }
- hash += (hash << 3);
- hash ^= (hash >> 11);
- hash += (hash << 15);
+
+ hash = FNV_32_BASIS;
+ while (size-- > 0)
+ hash = (hash * FNV_32_PRIME) ^ *buf++;
+
return hash;
}
-/* Colin Plumb's "one-at-a-time" hash, for strings. */
+/* Fowler-Noll-Vo 32-bit hash, for strings. */
unsigned
hsh_hash_string (const char *s_)
{
const unsigned char *s = s_;
- unsigned hash = 0;
+ unsigned hash;
assert (s != NULL);
- while (*s != '\0')
- {
- hash += *s++;
- hash += (hash << 10);
- hash ^= (hash >> 6);
- }
- hash += (hash << 3);
- hash ^= (hash >> 11);
- hash += (hash << 15);
+
+ 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 = s_;
+ unsigned hash;
+
+ assert (s != NULL);
+
+ hash = FNV_32_BASIS;
+ while (*s != '\0')
+ hash = (hash * FNV_32_PRIME) ^ toupper (*s++);
+
return hash;
}
\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
struct hsh_table *h;
int i;
- assert (size > 0);
assert (compare != NULL);
assert (hash != NULL);
h->compare = compare;
h->hash = hash;
h->free = free;
+#ifndef NDEBUG
+ h->hash_ordered = true;
+#endif
return h;
}
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. */
}
}
-/* Changes the capacity of H to NEW_SIZE. */
+/* 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
-hsh_rehash (struct hsh_table *h, size_t new_size)
+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->entries = xmalloc (sizeof *h->entries * h->size);
for (i = 0; i < h->size; i++)
h->entries[i] = NULL;
- for (table_p = begin; table_p < end; table_p++)
+ for (table_p = begin; table_p < end; table_p++)
{
- void **entry;
-
- if (*table_p == NULL)
- continue;
- entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
- while (*entry)
- if (--entry < h->entries)
- entry = &h->entries[h->size - 1];
- *entry = *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)
+not_null (const void *data_, void *aux UNUSED)
{
void *const *data = data_;
/* 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() may
- be applied to H. */
-void **
+ 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);
+ 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. */
-int
+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() may be applied to H. */
-void **
+ 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);
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. */
+ 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)
{
assert (h != NULL);
copy = xmalloc ((h->used + 1) * sizeof *copy);
- copy_if (h->entries, h->size, sizeof *h->entries, copy,
- not_null, NULL);
+ copy_if (h->entries, h->size, sizeof *h->entries, copy, not_null, NULL);
copy[h->used] = NULL;
return copy;
}
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. */
+ 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)
{
inline void **
hsh_probe (struct hsh_table *h, const void *target)
{
- void **entry;
-
+ unsigned i;
+
assert (h != NULL);
assert (target != NULL);
+ assert (h->hash_ordered);
- /* Order of these statements is important! */
if (h->used > h->size / 2)
- hsh_rehash (h, h->size * 2);
- entry = &h->entries[h->hash (target, h->aux) & (h->size - 1)];
-
- while (*entry)
- {
- if (!h->compare (*entry, target, h->aux))
- return entry;
- if (--entry < h->entries)
- entry = &h->entries[h->size - 1];
- }
- h->used++;
- return entry;
+ 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
return old;
}
-/* Locates an entry matching TARGET. Returns a pointer to the
- entry, or a null pointer on failure. */
-static inline void **
-locate_matching_entry (struct hsh_table *h, const void *target)
-{
- void **entry = &h->entries[h->hash (target, h->aux) & (h->size - 1)];
-
- while (*entry)
- {
- if (!h->compare (*entry, target, h->aux))
- return entry;
- if (--entry < h->entries)
- entry = &h->entries[h->size - 1];
- }
- return NULL;
-}
-
/* 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)
{
- void **entry = locate_matching_entry (h, target);
- return entry != NULL ? *entry : NULL;
+ 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.
- Note: this function is very slow because it rehashes the
- entire table. Don't use this hash table implementation if
- deletion is a common operation. */
+ 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)
{
- void **entry = locate_matching_entry (h, target);
- if (entry != NULL)
+ unsigned i = locate_matching_entry (h, target);
+ if (h->entries[i] != NULL)
{
+ h->used--;
if (h->free != NULL)
- h->free (*entry, h->aux);
- *entry = 0;
- hsh_rehash (h, h->size);
- return 1;
+ 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;
#if GLOBAL_DEBUGGING
#undef NDEBUG
-#include <assert.h>
+#include "error.h"
#include <stdio.h>
/* Displays contents of hash table H on stdout. */
projects / pspp-builds.git / blobdiff