Teach the hash table itself to know its own hash function

Here, we change 'create' to accept the hash function.

This simplifies the interface for 'insert', 'search', 'contains', and
'remove' which no longer need to pass a hash value, making them more
convenient to use.

To avoid any reduction in performance, the previous interfaces for
'insert' and 'search' are still available as 'insert_pre_hashed' and
'search_pre_hashed'. This avoids redundant hashing in cases where the
caller already has a hash value. (The common case is to has once
before 'search_pre_hashed' and then reuse that value for
'insert_pre_hashed'.)

The implementation takes advantage of the 'insert_pre_hashed' version
when performing hash_rehash as part of resizing the table.

Note that 'remove' does not need a pre_hashed variant since 'remove'
is already a convenience function on top of 'remove_entry', and
'remove_entry' already has access to the hash value inside of the
entry.

Similarly, 'contains' does not need a pre_hashed variant since it is a
convnience function on top of 'search' which already has a
'search_pre_hashed' variant.

In this commit, the tests are modified such that roughly half of the
previous callers of 'search' and 'insert' are changed to the new
interface and the other half remain with the old interface (now named
'search_pre_hashed' and 'insert_pre_hashed').

v2: Make the new method call style consistent with the key equality
    method (change by anholt).

17 files changed, 107 insertions, 105 deletions

diff --git a/tests/collision.c b/tests/collision.c
index 2497fd9..7156257 100644
--- a/tests/collision.c
+++ b/tests/collision.c
@@ -41,38 +41,41 @@ main(int argc, char **argv)
 	uint32_t bad_hash = 5;
 	int i;
 
-	ht = hash_table_create(string_key_equals);
+	ht = hash_table_create(fnv1_hash_string, string_key_equals);
 
-	hash_table_insert(ht, bad_hash, str1, NULL);
-	hash_table_insert(ht, bad_hash, str2, NULL);
+	/* Add #1 and verify search. */
+	hash_table_insert_pre_hashed(ht, bad_hash, str1, NULL);
 
-	entry1 = hash_table_search(ht, bad_hash, str1);
+	entry1 = hash_table_search_pre_hashed(ht, bad_hash, str1);
 	assert(entry1->key == str1);
 
-	entry2 = hash_table_search(ht, bad_hash, str2);
+	/* Add #2 and verify search. */
+	hash_table_insert_pre_hashed(ht, bad_hash, str2, NULL);
+
+	entry2 = hash_table_search_pre_hashed(ht, bad_hash, str2);
 	assert(entry2->key == str2);
 
 	/* Check that we can still find #1 after inserting #2 */
-	entry1 = hash_table_search(ht, bad_hash, str1);
+	entry1 = hash_table_search_pre_hashed(ht, bad_hash, str1);
 	assert(entry1->key == str1);
 
 	/* Remove the collided entry and look again. */
 	hash_table_remove_entry(ht, entry1);
-	entry2 = hash_table_search(ht, bad_hash, str2);
+	entry2 = hash_table_search_pre_hashed(ht, bad_hash, str2);
 	assert(entry2->key == str2);
 
 	/* Put str1 back, then spam junk into the table to force a
 	 * resize and make sure we can still find them both.
 	 */
-	hash_table_insert(ht, bad_hash, str1, NULL);
+	hash_table_insert_pre_hashed(ht, bad_hash, str1, NULL);
 	for (i = 0; i < 100; i++) {
 		char *key = malloc(10);
 		sprintf(key, "spam%d", i);
-		hash_table_insert(ht, fnv1_hash_string(key), key, NULL);
+		hash_table_insert(ht, key, NULL);
 	}
-	entry1 = hash_table_search(ht, bad_hash, str1);
+	entry1 = hash_table_search_pre_hashed(ht, bad_hash, str1);
 	assert(entry1->key == str1);
-	entry2 = hash_table_search(ht, bad_hash, str2);
+	entry2 = hash_table_search_pre_hashed(ht, bad_hash, str2);
 	assert(entry2->key == str2);
 
 	hash_table_destroy(ht, NULL);
diff --git a/tests/delete_and_lookup.c b/tests/delete_and_lookup.c
index 1a07881..ab642e1 100644
--- a/tests/delete_and_lookup.c
+++ b/tests/delete_and_lookup.c
@@ -49,34 +49,33 @@ main(int argc, char **argv)
 	const char *str3 = "test3";
 	uint32_t hash_str1 = badhash(str1);
 	uint32_t hash_str2 = badhash(str2);
-	uint32_t hash_str3 = badhash(str3);
 	struct hash_entry *entry;
 
-	ht = hash_table_create(string_key_equals);
+	ht = hash_table_create(badhash, string_key_equals);
 
-	hash_table_insert(ht, hash_str1, str1, NULL);
-	hash_table_insert(ht, hash_str2, str2, NULL);
-	hash_table_insert(ht, hash_str3, str3, NULL);
+	hash_table_insert_pre_hashed(ht, hash_str1, str1, NULL);
+	hash_table_insert_pre_hashed(ht, hash_str2, str2, NULL);
+	hash_table_insert(ht, str3, NULL);
 
-	entry = hash_table_search(ht, hash_str3, str3);
+	entry = hash_table_search(ht, str3);
 	assert(strcmp(entry->key, str3) == 0);
 
-	entry = hash_table_search(ht, hash_str2, str2);
+	entry = hash_table_search_pre_hashed(ht, hash_str2, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
-	entry = hash_table_search(ht, hash_str1, str1);
+	entry = hash_table_search_pre_hashed(ht, hash_str1, str1);
 	assert(strcmp(entry->key, str1) == 0);
 
 	hash_table_remove_entry(ht, entry);
-	hash_table_remove(ht, hash_str2, str2);
+	hash_table_remove(ht, str2);
 
-	entry = hash_table_search(ht, hash_str1, str1);
+	entry = hash_table_search_pre_hashed(ht, hash_str1, str1);
 	assert(entry == NULL);
 
-	entry = hash_table_search(ht, hash_str2, str2);
+	entry = hash_table_search(ht, str2);
 	assert(entry == NULL);
 
-	entry = hash_table_search(ht, hash_str3, str3);
+	entry = hash_table_search(ht, str3);
 	assert(strcmp(entry->key, str3) == 0);
 
 	hash_table_destroy(ht, NULL);
diff --git a/tests/delete_management.c b/tests/delete_management.c
index 6a15691..88f8da5 100644
--- a/tests/delete_management.c
+++ b/tests/delete_management.c
@@ -29,8 +29,8 @@
 #include <string.h>
 #include <assert.h>
 #include "hash_table.h"
-#include "fnv_hash.h"
 
+/* Also doubles as hash function. */
 static uint32_t
 key_value(const void *key)
 {
@@ -52,22 +52,22 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i;
 
-	ht = hash_table_create(uint32_t_key_equals);
+	ht = hash_table_create(key_value, uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		hash_table_insert(ht, i, keys + i, NULL);
+		hash_table_insert_pre_hashed(ht, i, keys + i, NULL);
 
 		if (i >= 100) {
 			uint32_t delete_value = i - 100;
-			hash_table_remove(ht, delete_value, &delete_value);
+			hash_table_remove(ht, &delete_value);
 		}
 	}
 
 	/* Make sure that all our entries were present at the end. */
 	for (i = size - 100; i < size; i++) {
-		entry = hash_table_search(ht, i, keys + i);
+		entry = hash_table_search(ht, keys + i);
 		assert(entry);
 		assert(key_value(entry->key) == i);
 	}
diff --git a/tests/destroy_callback.c b/tests/destroy_callback.c
index c6d7e3c..785bd4d 100644
--- a/tests/destroy_callback.c
+++ b/tests/destroy_callback.c
@@ -52,12 +52,11 @@ 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(string_key_equals);
+	ht = hash_table_create(fnv1_hash_string, string_key_equals);
 
-	hash_table_insert(ht, hash_str1, str1, NULL);
-	hash_table_insert(ht, hash_str2, str2, NULL);
+	hash_table_insert_pre_hashed(ht, hash_str1, str1, NULL);
+	hash_table_insert(ht, str2, NULL);
 
 	hash_table_destroy(ht, delete_callback);
 
diff --git a/tests/insert_and_lookup.c b/tests/insert_and_lookup.c
index cfaa6c1..5643bac 100644
--- a/tests/insert_and_lookup.c
+++ b/tests/insert_and_lookup.c
@@ -38,18 +38,17 @@ main(int argc, char **argv)
 	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(string_key_equals);
+	ht = hash_table_create(fnv1_hash_string, string_key_equals);
 
-	hash_table_insert(ht, hash_str1, str1, NULL);
-	hash_table_insert(ht, hash_str2, str2, NULL);
+	hash_table_insert_pre_hashed(ht, hash_str1, str1, NULL);
+	hash_table_insert(ht, str2, NULL);
 
-	entry = hash_table_search(ht, hash_str1, str1);
+	entry = hash_table_search_pre_hashed(ht, hash_str1, str1);
 	assert(strcmp(entry->key, str1) == 0);
 
-	entry = hash_table_search(ht, hash_str2, str2);
+	entry = hash_table_search(ht, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
 	hash_table_destroy(ht, NULL);
diff --git a/tests/insert_many.c b/tests/insert_many.c
index b46922c..de5ab39 100644
--- a/tests/insert_many.c
+++ b/tests/insert_many.c
@@ -29,8 +29,8 @@
 #include <string.h>
 #include <assert.h>
 #include "hash_table.h"
-#include "fnv_hash.h"
 
+/* Also doubles as hash function. */
 static uint32_t
 key_value(const void *key)
 {
@@ -52,16 +52,16 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i;
 
-	ht = hash_table_create(uint32_t_key_equals);
+	ht = hash_table_create(key_value, uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		hash_table_insert(ht, i, keys + i, NULL);
+		hash_table_insert(ht, keys + i, NULL);
 	}
 
 	for (i = 0; i < size; i++) {
-		entry = hash_table_search(ht, i, keys + i);
+		entry = hash_table_search_pre_hashed(ht, i, keys + i);
 		assert(entry);
 		assert(key_value(entry->key) == i);
 	}
diff --git a/tests/random_entry.c b/tests/random_entry.c
index 747b566..863c32c 100644
--- a/tests/random_entry.c
+++ b/tests/random_entry.c
@@ -29,8 +29,8 @@
 #include <string.h>
 #include <assert.h>
 #include "hash_table.h"
-#include "fnv_hash.h"
 
+/* Also doubles as hash function. */
 static uint32_t
 key_value(const void *key)
 {
@@ -58,12 +58,12 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i, random_value;
 
-	ht = hash_table_create(uint32_t_key_equals);
+	ht = hash_table_create(key_value, uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		hash_table_insert(ht, i, keys + i, NULL);
+		hash_table_insert(ht, keys + i, NULL);
 	}
 
 	/* Test the no-predicate case. */
diff --git a/tests/remove_null.c b/tests/remove_null.c
index 0d9066d..bdb549a 100644
--- a/tests/remove_null.c
+++ b/tests/remove_null.c
@@ -36,7 +36,7 @@ main(int argc, char **argv)
 {
 	struct hash_table *ht;
 
-	ht = hash_table_create(string_key_equals);
+	ht = hash_table_create(fnv1_hash_string, string_key_equals);
 
 	hash_table_remove_entry(ht, NULL);
 
diff --git a/tests/replacement.c b/tests/replacement.c
index a78fb81..3e762b0 100644
--- a/tests/replacement.c
+++ b/tests/replacement.c
@@ -38,21 +38,27 @@ main(int argc, char **argv)
 	char *str1 = strdup("test1");
 	char *str2 = strdup("test1");
 	uint32_t hash_str1 = fnv1_hash_string(str1);
-	uint32_t hash_str2 = fnv1_hash_string(str2);
 	struct hash_entry *entry;
 
-	ht = hash_table_create(string_key_equals);
+	ht = hash_table_create(fnv1_hash_string, string_key_equals);
 
-	hash_table_insert(ht, hash_str1, str1, str1);
-	hash_table_insert(ht, hash_str2, str2, str2);
+	hash_table_insert_pre_hashed(ht, hash_str1, str1, str1);
+	hash_table_insert(ht, str2, str2);
 
-	entry = hash_table_search(ht, hash_str1, str1);
+	entry = hash_table_search_pre_hashed(ht, hash_str1, str1);
+	assert(entry);
+	assert(entry->data == str2);
+
+	entry = hash_table_search(ht, str1);
 	assert(entry);
 	assert(entry->data == str2);
 
 	hash_table_remove_entry(ht, entry);
 
-	entry = hash_table_search(ht, hash_str1, str1);
+	entry = hash_table_search_pre_hashed(ht, hash_str1, str1);
+	assert(!entry);
+
+	entry = hash_table_search(ht, str1);
 	assert(!entry);
 
 	hash_table_destroy(ht, NULL);
diff --git a/tests/set/delete_and_lookup.c b/tests/set/delete_and_lookup.c
index 93d3bc7..6031faf 100644
--- a/tests/set/delete_and_lookup.c
+++ b/tests/set/delete_and_lookup.c
@@ -48,41 +48,39 @@ main(int argc, char **argv)
 	const char *str2 = "test2";
 	const char *str3 = "test3";
 	uint32_t hash_str1 = badhash(str1);
-	uint32_t hash_str2 = badhash(str2);
-	uint32_t hash_str3 = badhash(str3);
 	struct set_entry *entry;
 
-	set = set_create(string_key_equals);
+	set = set_create(badhash, string_key_equals);
 
-	set_add(set, hash_str1, str1);
-	set_add(set, hash_str2, str2);
-	set_add(set, hash_str2, str3);
+	set_add_pre_hashed(set, hash_str1, str1);
+	set_add(set, str2);
+	set_add(set, str3);
 
-	assert(set_contains(set, hash_str3, str3));
-	entry = set_search(set, hash_str3, str3);
+	assert(set_contains(set, str3));
+	entry = set_search(set, str3);
 	assert(strcmp(entry->key, str3) == 0);
 
-	assert(set_contains(set, hash_str2, str2));
-	entry = set_search(set, hash_str2, str2);
+	assert(set_contains(set, str2));
+	entry = set_search(set, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
-	assert(set_contains(set, hash_str1, str1));
-	entry = set_search(set, hash_str1, str1);
+	assert(set_contains(set, str1));
+	entry = set_search_pre_hashed(set, hash_str1, str1);
 	assert(strcmp(entry->key, str1) == 0);
 
 	set_remove_entry(set, entry);
-	set_remove(set, hash_str2, str2);
+	set_remove(set, str2);
 
-	assert(!set_contains(set, hash_str1, str1));
-	entry = set_search(set, hash_str1, str1);
+	assert(!set_contains(set, str1));
+	entry = set_search_pre_hashed(set, hash_str1, str1);
 	assert(entry == NULL);
 
-	assert(!set_contains(set, hash_str2, str2));
-	entry = set_search(set, hash_str2, str2);
+	assert(!set_contains(set, str2));
+	entry = set_search(set, str2);
 	assert(entry == NULL);
 
-	assert(set_contains(set, hash_str3, str3));
-	entry = set_search(set, hash_str3, str3);
+	assert(set_contains(set, str3));
+	entry = set_search(set, str3);
 	assert(strcmp(entry->key, str3) == 0);
 
 	set_destroy(set, NULL);
diff --git a/tests/set/delete_management.c b/tests/set/delete_management.c
index 14f1fe1..e41e7ad 100644
--- a/tests/set/delete_management.c
+++ b/tests/set/delete_management.c
@@ -31,6 +31,7 @@
 #include "set.h"
 #include "fnv_hash.h"
 
+/* Also doubles as the hash function. */
 static uint32_t
 key_value(const void *key)
 {
@@ -52,23 +53,23 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i;
 
-	set = set_create(uint32_t_key_equals);
+	set = set_create(key_value, uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		set_add(set, i, &keys[i]);
+		set_add(set, &keys[i]);
 
 		if (i >= 100) {
 			uint32_t delete_value = i - 100;
-			set_remove(set, delete_value, &delete_value);
+			set_remove(set, &delete_value);
 		}
 	}
 
 	/* Make sure that all our entries were present at the end. */
 	for (i = size - 100; i < size; i++) {
-		assert(set_contains(set, i, &keys[i]));
-		entry = set_search(set, i, &keys[i]);
+		assert(set_contains(set, &keys[i]));
+		entry = set_search(set, &keys[i]);
 		assert(entry);
 		assert(key_value(entry->key) == i);
 	}
diff --git a/tests/set/destroy_callback.c b/tests/set/destroy_callback.c
index 6dff3e1..fd76bb9 100644
--- a/tests/set/destroy_callback.c
+++ b/tests/set/destroy_callback.c
@@ -52,12 +52,11 @@ main(int argc, char **argv)
 {
 	struct set *set;
 	uint32_t hash_str1 = fnv1_hash_string(str1);
-	uint32_t hash_str2 = fnv1_hash_string(str2);
 
-	set = set_create(string_key_equals);
+	set = set_create(fnv1_hash_string, string_key_equals);
 
-	set_add(set, hash_str1, str1);
-	set_add(set, hash_str2, str2);
+	set_add_pre_hashed(set, hash_str1, str1);
+	set_add(set, str2);
 
 	set_destroy(set, delete_callback);
 
diff --git a/tests/set/insert_and_lookup.c b/tests/set/insert_and_lookup.c
index 6b01bdd..d1c426e 100644
--- a/tests/set/insert_and_lookup.c
+++ b/tests/set/insert_and_lookup.c
@@ -38,20 +38,19 @@ main(int argc, char **argv)
 	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 set_entry *entry;
 
-	set = set_create(string_key_equals);
+	set = set_create(fnv1_hash_string, string_key_equals);
 
-	set_add(set, hash_str1, str1);
-	set_add(set, hash_str2, str2);
+	set_add_pre_hashed(set, hash_str1, str1);
+	set_add(set, str2);
 
-	assert(set_contains(set, hash_str1, str1));
-	entry = set_search(set, hash_str1, str1);
+	assert(set_contains(set, str1));
+	entry = set_search_pre_hashed(set, hash_str1, str1);
 	assert(strcmp(entry->key, str1) == 0);
 
-	assert(set_contains(set, hash_str2, str2));
-	entry = set_search(set, hash_str2, str2);
+	assert(set_contains(set, str2));
+	entry = set_search(set, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
 	set_destroy(set, NULL);
diff --git a/tests/set/insert_many.c b/tests/set/insert_many.c
index 2dc15da..195a971 100644
--- a/tests/set/insert_many.c
+++ b/tests/set/insert_many.c
@@ -29,8 +29,8 @@
 #include <string.h>
 #include <assert.h>
 #include "set.h"
-#include "fnv_hash.h"
 
+/* Also double as hash function. */
 static uint32_t
 key_value(const void *key)
 {
@@ -52,17 +52,17 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i;
 
-	set = set_create(uint32_t_key_equals);
+	set = set_create(key_value, uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		set_add(set, i, keys + i);
+		set_add_pre_hashed(set, i, keys + i);
 	}
 
 	for (i = 0; i < size; i++) {
-		assert(set_contains(set, i, keys + i));
-		entry = set_search(set, i, keys + i);
+		assert(set_contains(set, keys + i));
+		entry = set_search_pre_hashed(set, i, keys + i);
 		assert(entry);
 		assert(key_value(entry->key) == i);
 	}
diff --git a/tests/set/null_remove.c b/tests/set/null_remove.c
index 8b8ba89..853698d 100644
--- a/tests/set/null_remove.c
+++ b/tests/set/null_remove.c
@@ -36,7 +36,7 @@ main(int argc, char **argv)
 {
 	struct set *set;
 
-	set = set_create(string_key_equals);
+	set = set_create(fnv1_hash_string, string_key_equals);
 
 	set_remove_entry(set, NULL);
 
diff --git a/tests/set/random_entry.c b/tests/set/random_entry.c
index 371d02f..c700c7d 100644
--- a/tests/set/random_entry.c
+++ b/tests/set/random_entry.c
@@ -29,8 +29,8 @@
 #include <string.h>
 #include <assert.h>
 #include "set.h"
-#include "fnv_hash.h"
 
+/* Also doubles as hash function. */
 static uint32_t
 key_value(const void *key)
 {
@@ -58,12 +58,12 @@ main(int argc, char **argv)
 	uint32_t keys[size];
 	uint32_t i, random_value;
 
-	set = set_create(uint32_t_key_equals);
+	set = set_create(key_value, uint32_t_key_equals);
 
 	for (i = 0; i < size; i++) {
 		keys[i] = i;
 
-		set_add(set, i, keys + i);
+		set_add(set, keys + i);
 	}
 
 	/* Test the no-predicate case. */
diff --git a/tests/set/replacement.c b/tests/set/replacement.c
index 2c7555e..bdf304f 100644
--- a/tests/set/replacement.c
+++ b/tests/set/replacement.c
@@ -38,23 +38,22 @@ main(int argc, char **argv)
 	char *str1 = strdup("test1");
 	char *str2 = strdup("test1");
 	uint32_t hash_str1 = fnv1_hash_string(str1);
-	uint32_t hash_str2 = fnv1_hash_string(str2);
 	struct set_entry *entry;
 
-	set = set_create(string_key_equals);
+	set = set_create(fnv1_hash_string, string_key_equals);
 
-	set_add(set, hash_str1, str1);
-	set_add(set, hash_str2, str2);
+	set_add_pre_hashed(set, hash_str1, str1);
+	set_add(set, str2);
 
-	assert(set_contains(set, hash_str1, str1));
-	entry = set_search(set, hash_str1, str1);
+	assert(set_contains(set, str1));
+	entry = set_search_pre_hashed(set, hash_str1, str1);
 	assert(entry);
 	assert(entry->key == str2);
 
 	set_remove_entry(set, entry);
 
-	assert(!set_contains(set, hash_str1, str1));
-	entry = set_search(set, hash_str1, str1);
+	assert(!set_contains(set, str1));
+	entry = set_search(set, str1);
 	assert(!entry);
 
 	set_destroy(set, NULL);