From 30d855c079a1aef97aa348e7e25cd46175bfe1a1 Mon Sep 17 00:00:00 2001 From: David Given Date: Sat, 17 Dec 2016 10:30:27 +0100 Subject: [PATCH] Hash table sizes now must be a power of two (saves a modulus instruction); optimise key comparison (if the two keys are identical, we don't need to call the comparator). --- modules/src/data/hashtable.c | 18 ++++++++++++++---- modules/src/data/hashtable.h | 2 +- 2 files changed, 15 insertions(+), 5 deletions(-) diff --git a/modules/src/data/hashtable.c b/modules/src/data/hashtable.c index 8e43d9e8c..b76df03b8 100644 --- a/modules/src/data/hashtable.c +++ b/modules/src/data/hashtable.c @@ -64,7 +64,7 @@ void hashtable_rebucket(struct hashtable* ht, unsigned int num_buckets) while (old_buckets[i]) { struct hashnode* hn = old_buckets[i]; - uint32_t hash = ht->hashfunction(hn->key) % num_buckets; + uint32_t hash = ht->hashfunction(hn->key) & (num_buckets-1); old_buckets[i] = hn->next; hn->next = ht->buckets[hash]; @@ -81,11 +81,21 @@ static struct hashnode** findnodep(struct hashtable* ht, void* key) struct hashnode** hnp; lazy_init(ht); - hash = ht->hashfunction(key) % ht->num_buckets; + hash = ht->hashfunction(key) & (ht->num_buckets-1); hnp = &ht->buckets[hash]; - while (*hnp && !ht->cmpfunction((*hnp)->key, key)) + for (;;) + { + void* k; + + if (!*hnp) + break; + k = (*hnp)->key; + if ((k == key) || ht->cmpfunction(k, key)) + break; + hnp = &(*hnp)->next; + } return hnp; } @@ -98,7 +108,7 @@ void* hashtable_put(struct hashtable* ht, void* key, void* value) { if (ht->size == (ht->num_buckets*2)) { - hashtable_rebucket(ht, ht->num_buckets*3 + 1); + hashtable_rebucket(ht, ht->num_buckets*4); return hashtable_put(ht, key, value); } diff --git a/modules/src/data/hashtable.h b/modules/src/data/hashtable.h index 47304110e..f5617b3f5 100644 --- a/modules/src/data/hashtable.h +++ b/modules/src/data/hashtable.h @@ -11,7 +11,7 @@ extern bool standard_pointer_comparison_function(void* key1, void* key2); struct hashtable { - unsigned int num_buckets; + unsigned int num_buckets; /* power of 2 */ hashfunction_t* hashfunction; cmpfunction_t* cmpfunction; struct hashnode** buckets; -- 2.34.1