API change: pass the hash value in to search/lookup.

This avoids re-hashing the key for the common use case of searching for the
key's presence, then creating the entry if it isn't.

7 files changed, 42 insertions, 58 deletions

diff --git a/hash_table.c b/hash_table.c
index 991f02b..33de524 100644
--- a/hash_table.c
+++ b/hash_table.c
@@ -96,8 +96,7 @@ entry_is_present(struct hash_entry *entry)
 }
 
 struct hash_table *
-hash_table_create(uint32_t (*hash_function)(const void *key),
-		  int key_equals_function(const void *a,
+hash_table_create(int key_equals_function(const void *a,
 					  const void *b))
 {
 	struct hash_table *ht;
@@ -110,7 +109,6 @@ hash_table_create(uint32_t (*hash_function)(const void *key),
 	ht->size = hash_sizes[ht->size_index].size;
 	ht->rehash = hash_sizes[ht->size_index].rehash;
 	ht->max_entries = hash_sizes[ht->size_index].max_entries;
-	ht->hash_function = hash_function;
 	ht->key_equals_function = key_equals_function;
 	ht->table = calloc(ht->size, sizeof(*ht->table));
 	ht->entries = 0;
@@ -150,11 +148,10 @@ hash_table_destroy(struct hash_table *ht,
 }
 
 struct hash_entry *
-hash_table_search(struct hash_table *ht, const void *key)
+hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
 {
-	uint32_t hash, hash_address;
+	uint32_t hash_address;
 
-	hash = ht->hash_function(key);
 	hash_address = hash % ht->size;
 	do {
 		struct hash_entry *entry = ht->table + hash_address;
@@ -198,7 +195,8 @@ hash_table_expand(struct hash_table *ht)
 	     entry != old_ht.table + old_ht.size;
 	     entry++) {
 		if (entry_is_present(entry)) {
-			hash_table_insert(ht, entry->key, entry->data);
+			hash_table_insert(ht, entry->hash,
+					  entry->key, entry->data);
 		}
 	}
 
@@ -206,15 +204,15 @@ hash_table_expand(struct hash_table *ht)
 }
 
 struct hash_entry *
-hash_table_insert(struct hash_table *ht, const void *key, void *data)
+hash_table_insert(struct hash_table *ht, uint32_t hash,
+		  const void *key, void *data)
 {
-	uint32_t hash, hash_address;
+	uint32_t hash_address;
 
 	if (ht->entries >= ht->max_entries) {
 		hash_table_expand(ht);
 	}
 
-	hash = ht->hash_function(key);
 	hash_address = hash % ht->size;
 	do {
 		struct hash_entry *entry = ht->table + hash_address;
diff --git a/hash_table.h b/hash_table.h
index e013458..5cc71b2 100644
--- a/hash_table.h
+++ b/hash_table.h
@@ -44,15 +44,15 @@ struct hash_table {
 	uint32_t entries;
 };
 
-struct hash_table *hash_table_create(uint32_t (*hash_function)(const void *key),
-				     int (*key_equals_function)(const void *a,
+struct hash_table *hash_table_create(int (*key_equals_function)(const void *a,
 								const void *b));
 void hash_table_destroy(struct hash_table *ht,
 			void (*delete_function)(struct hash_entry *entry));
 
-struct hash_entry *hash_table_insert(struct hash_table *ht, const void *key,
-				     void *data);
-struct hash_entry *hash_table_search(struct hash_table *ht, const void *key);
+struct hash_entry *hash_table_insert(struct hash_table *ht, uint32_t hash,
+				     const void *key, void *data);
+struct hash_entry *hash_table_search(struct hash_table *ht, uint32_t hash,
+				     const void *key);
 void hash_table_remove(struct hash_table *ht, struct hash_entry *entry);
 
 struct hash_entry *hash_table_next_entry(struct hash_table *ht,
diff --git a/tests/delete_and_lookup.c b/tests/delete_and_lookup.c
index c4fe555..0515ed5 100644
--- a/tests/delete_and_lookup.c
+++ b/tests/delete_and_lookup.c
@@ -46,25 +46,27 @@ main(int argc, char **argv)
 	struct hash_table *ht;
 	const char *str1 = "test1";
 	const char *str2 = "test2";
+	uint32_t hash_str1 = badhash(str1);
+	uint32_t hash_str2 = badhash(str2);
 	struct hash_entry *entry;
 
-	ht = hash_table_create(badhash, string_key_equals);
+	ht = hash_table_create(string_key_equals);
 
-	hash_table_insert(ht, str1, NULL);
-	hash_table_insert(ht, str2, NULL);
+	hash_table_insert(ht, hash_str1, str1, NULL);
+	hash_table_insert(ht, hash_str2, str2, NULL);
 
-	entry = hash_table_search(ht, str1);
-	assert(strcmp(entry->key, str1) == 0);
-
-	entry = hash_table_search(ht, str2);
+	entry = hash_table_search(ht, hash_str2, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
-	hash_table_remove(ht, hash_table_search(ht, str1));
+	entry = hash_table_search(ht, hash_str1, str1);
+	assert(strcmp(entry->key, str1) == 0);
+
+	hash_table_remove(ht, entry);
 
-	entry = hash_table_search(ht, str1);
+	entry = hash_table_search(ht, hash_str1, str1);
 	assert(entry == NULL);
 
-	entry = hash_table_search(ht, str2);
+	entry = hash_table_search(ht, hash_str2, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
 	hash_table_destroy(NULL, NULL);
diff --git a/tests/destroy_callback.c b/tests/destroy_callback.c
index 4e7ed32..c6d7e3c 100644
--- a/tests/destroy_callback.c
+++ b/tests/destroy_callback.c
@@ -51,11 +51,13 @@ int
 main(int argc, char **argv)
 {
 	struct hash_table *ht;
+	uint32_t hash_str1 = fnv1_hash_string(str1);
+	uint32_t hash_str2 = fnv1_hash_string(str2);
 
-	ht = hash_table_create(fnv1_hash_string, string_key_equals);
+	ht = hash_table_create(string_key_equals);
 
-	hash_table_insert(ht, str1, NULL);
-	hash_table_insert(ht, str2, NULL);
+	hash_table_insert(ht, hash_str1, str1, NULL);
+	hash_table_insert(ht, hash_str2, str2, NULL);
 
 	hash_table_destroy(ht, delete_callback);
 
diff --git a/tests/insert_and_lookup.c b/tests/insert_and_lookup.c
index 2c287b6..9ed036b 100644
--- a/tests/insert_and_lookup.c
+++ b/tests/insert_and_lookup.c
@@ -37,17 +37,19 @@ main(int argc, char **argv)
 	struct hash_table *ht;
 	const char *str1 = "test1";
 	const char *str2 = "test2";
+	uint32_t hash_str1 = fnv1_hash_string(str1);
+	uint32_t hash_str2 = fnv1_hash_string(str2);
 	struct hash_entry *entry;
 
-	ht = hash_table_create(fnv1_hash_string, string_key_equals);
+	ht = hash_table_create(string_key_equals);
 
-	hash_table_insert(ht, str1, NULL);
-	hash_table_insert(ht, str2, NULL);
+	hash_table_insert(ht, hash_str1, str1, NULL);
+	hash_table_insert(ht, hash_str2, str2, NULL);
 
-	entry = hash_table_search(ht, str1);
+	entry = hash_table_search(ht, hash_str1, str1);
 	assert(strcmp(entry->key, str1) == 0);
 
-	entry = hash_table_search(ht, str2);
+	entry = hash_table_search(ht, hash_str2, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
 	hash_table_destroy(NULL, NULL);
diff --git a/tests/insert_many.c b/tests/insert_many.c
index ef54e02..b027d23 100644
--- a/tests/insert_many.c
+++ b/tests/insert_many.c
@@ -31,16 +31,6 @@
 #include "hash_table.h"
 #include "fnv_hash.h"
 
-static uint32_t
-uint32_t_key_hash(const void *key)
-{
-	/* Note that we're using the address of the key instead of the
-	 * perfectly-hashed 32-bit value in the key, in order to trigger
-	 * collisions.
-	 */
-	return (uint32_t)(uintptr_t)key;
-}
-
 static int
 uint32_t_key_equals(const void *a, const void *b)
 {
@@ -56,16 +46,16 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i;
 
-	ht = hash_table_create(uint32_t_key_hash, uint32_t_key_equals);
+	ht = hash_table_create(uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		hash_table_insert(ht, keys + i, NULL);
+		hash_table_insert(ht, i, keys + i, NULL);
 	}
 
 	for (i = 0; i < size; i++) {
-		entry = hash_table_search(ht, keys + i);
+		entry = hash_table_search(ht, i, keys + i);
 		assert(entry);
 		assert(*(uint32_t *)entry->key == i);
 	}
diff --git a/tests/random_entry.c b/tests/random_entry.c
index 3f51088..796461b 100644
--- a/tests/random_entry.c
+++ b/tests/random_entry.c
@@ -37,16 +37,6 @@ key_value(const void *key)
 	return *(uint32_t *)key;
 }
 
-static uint32_t
-uint32_t_key_hash(const void *key)
-{
-	/* Note that we're using the address of the key instead of the
-	 * perfectly-hashed 32-bit value in the key, in order to trigger
-	 * collisions.
-	 */
-	return (uint32_t)(uintptr_t)key;
-}
-
 static int
 uint32_t_key_equals(const void *a, const void *b)
 {
@@ -68,12 +58,12 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i, random_value;
 
-	ht = hash_table_create(uint32_t_key_hash, uint32_t_key_equals);
+	ht = hash_table_create(uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		hash_table_insert(ht, keys + i, NULL);
+		hash_table_insert(ht, i, keys + i, NULL);
 	}
 
 	/* Test the no-predicate case. */