02111-1307, USA. */
#include <config.h>
-#include <assert.h>
+#include "hash.h"
+#include "error.h"
#include <limits.h>
#include <stdlib.h>
#include "algorithm.h"
#include "alloc.h"
-#include "hash.h"
#include "misc.h"
#include "str.h"
}
}
-/* 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;
}
struct hsh_table *h;
int i;
- assert (size > 0);
+ if ( size == 0 )
+ return NULL;
+
assert (compare != NULL);
assert (hash != NULL);
for (i = 0; i < h->size; i++)
h->entries[i] = NULL;
+
+ h->used = 0;
}
/* Destroys table H and all its contents. */
for (i = 0; i < h->size; i++)
h->entries[i] = NULL;
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;
- }
+ if (*table_p != NULL)
+ {
+ void **entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
+ while (*entry != NULL)
+ if (++entry >= h->entries + h->size)
+ entry = h->entries;
+ *entry = *table_p;
+ }
free (begin);
}
/* 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_;
/* 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);
}
{
if (!h->compare (*entry, target, h->aux))
return entry;
- if (--entry < h->entries)
- entry = &h->entries[h->size - 1];
+ if (++entry >= h->entries + h->size)
+ entry = h->entries;
}
h->used++;
return entry;
{
if (!h->compare (*entry, target, h->aux))
return entry;
- if (--entry < h->entries)
- entry = &h->entries[h->size - 1];
+ if (++entry >= h->entries + h->size)
+ entry = h->entries;
}
return NULL;
}
/* 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.
+
+ Not well tested. */
int
hsh_delete (struct hsh_table *h, const void *target)
{
void **entry = locate_matching_entry (h, target);
if (entry != NULL)
{
+ ptrdiff_t i;
+
+ h->used--;
if (h->free != NULL)
h->free (*entry, h->aux);
*entry = 0;
- hsh_rehash (h, h->size);
- return 1;
+
+ i = entry - h->entries;
+ for (;;)
+ {
+ unsigned r;
+ ptrdiff_t j = i;
+
+ do
+ {
+ if (--i < 0)
+ i = 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[i] = h->entries[j];
+ }
}
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. */