From 71958e114d118392a1db807962381b632b0e0615 Mon Sep 17 00:00:00 2001 From: Ari Johnson Date: Tue, 10 May 2011 19:42:04 -0400 Subject: [PATCH] Update to latest PennMUSH hashtab code, with one bugfix. refs #235 --- src/htab.c | 51 ++++++++++++++++++++++++--------------------------- 1 file changed, 24 insertions(+), 27 deletions(-) diff --git a/src/htab.c b/src/htab.c index 0d8a347..5835e65 100644 --- a/src/htab.c +++ b/src/htab.c @@ -7,7 +7,7 @@ * to resolve collisions. This gives an O(1) worse-case performance * (As well as best, of course), compared to the worst-case O(N) of * chained or linear probing tables. - * + * * A lookup will require at most X hash functions and string * comparisions. The old tables had, with data used by Penn, 1 hash * function and up to 6 or 7 comparisions in the worst case. Best case @@ -53,7 +53,7 @@ #endif #include "conf.h" #include "externs.h" - +#include "log.h" #include "htab.h" #include "mymalloc.h" @@ -266,7 +266,7 @@ penn_hash(const char *key, int len) return hash; } -typedef uint32_t (*hash_func) (const char *, int); +typedef uint32_t(*hash_func) (const char *, int); hash_func hash_functions[] = { hsieh_hash, @@ -419,7 +419,6 @@ next_prime_after(unsigned int val) /** Initialize a hashtable. * \param htab pointer to hash table to initialize. * \param size size of hashtable. - * \param data_size size of an individual datum to store in the table. */ void hash_init(HASHTAB *htab, int size, void (*free_data) (void *)) @@ -503,7 +502,8 @@ hash_insert(HASHTAB *htab, const char *key, void *data) /* At this point, we've bumped BUMP_LIMIT times. Probably in a loop. Find the first empty bucket, add the last bumped to, and - return failure. */ + return failure. The table will have to be resized now to restore + the hash. */ for (n = 0; n < htab->hashsize; n++) if (htab->buckets[n].key == NULL) { htab->buckets[n] = bump; @@ -554,9 +554,7 @@ real_hash_resize(HASHTAB *htab, int newsize, int hashfunc_offset) htab->hashsize = newsize; htab->hashfunc_offset = hashfunc_offset; for (i = 0; i < oldsize; i++) { - if (oldarr[i].key) { - if (!hash_insert(htab, oldarr[i].key, oldarr[i].data)) { /* Couldn't fit an element in. Try with different hash functions. */ mush_free(htab->buckets, "hash.buckets"); @@ -596,34 +594,29 @@ hash_resize(HASHTAB *htab, int size) * \param htab pointer to hash table. * \param key key string to store data under. * \param hashdata void pointer to data to be stored. - * \param extra_size unused. * \retval false failure. * \retval true success. */ bool hash_add(HASHTAB *htab, const char *key, void *hashdata) { - const char *keycopy; + char *keycopy; if (hash_find(htab, key) != NULL) return false; - htab->entries += 1; - keycopy = mush_strdup(key, "hash.key"); + if (htab->entries == htab->hashsize) + real_hash_resize(htab, next_prime_after(floor(htab->hashsize * 1.15)), + htab->hashfunc_offset); - while (1) { - if (!hash_insert(htab, keycopy, hashdata)) { - first_offset = -1; - resize_calls = 0; - if (!real_hash_resize(htab, htab->hashsize, - (htab->hashfunc_offset + 1) % NHASH_MOD)) { - htab->entries -= 1; - return false; - } - } else - break; + htab->entries += 1; + if (!hash_insert(htab, keycopy, hashdata)) { + first_offset = -1; + resize_calls = 0; + real_hash_resize(htab, htab->hashsize, + (htab->hashfunc_offset + 1) % NHASH_MOD); } return true; } @@ -675,7 +668,7 @@ hash_flush(HASHTAB *htab, int size) } /** Return the first entry of a hash table. - * This function is used with hash_nextentry() to iterate through a + * This function is used with hash_nextentry() to iterate through a * hash table. * \param htab pointer to hash table. * \return first hash table entry. @@ -694,7 +687,7 @@ hash_firstentry(HASHTAB *htab) } /** Return the first key of a hash table. - * This function is used with hash_nextentry_key() to iterate through a + * This function is used with hash_nextentry_key() to iterate through a * hash table. * \param htab pointer to hash table. * \return first hash table key. @@ -713,7 +706,7 @@ hash_firstentry_key(HASHTAB *htab) } /** Return the next entry of a hash table. - * This function is used with hash_firstentry() to iterate through a + * This function is used with hash_firstentry() to iterate through a * hash table. hash_firstentry() must be called before calling * this function. * \param htab pointer to hash table. @@ -734,7 +727,7 @@ hash_nextentry(HASHTAB *htab) } /** Return the next key of a hash table. - * This function is used with hash_firstentry{,_key}() to iterate through a + * This function is used with hash_firstentry{,_key}() to iterate through a * hash table. hash_firstentry{,_key}() must be called before calling * this function. * \param htab pointer to hash table. @@ -772,7 +765,7 @@ hash_stats_header(dbref player) void hash_stats(dbref player, HASHTAB *htab, const char *hname) { - int n; + int n, entries = 0; size_t bytes; unsigned int compares[3] = { 0, 0, 0 }; @@ -787,6 +780,7 @@ hash_stats(dbref player, HASHTAB *htab, const char *hname) int i; int len = strlen(htab->buckets[n].key); bytes += len + 1; + entries += 1; for (i = 0; i < 3; i++) { hash_func hash = hash_functions[(i + htab->hashfunc_offset) % NHASH_MOD]; @@ -801,4 +795,7 @@ hash_stats(dbref player, HASHTAB *htab, const char *hname) "%-11s %7d %7d %7u %7u %7u %7u", hname, htab->hashsize, htab->entries, compares[0], compares[1], compares[2], (unsigned int) bytes); + if (entries != htab->entries) + notify_format(player, "Mismatch in size: %d expected, %d found!", + htab->entries, entries); } -- 2.30.2