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).

21 files changed, 218 insertions, 135 deletions

diff --git a/hash_table.c b/hash_table.c
index d8be630..1d0de75 100644
--- a/hash_table.c
+++ b/hash_table.c
@@ -102,8 +102,9 @@ entry_is_present(const struct hash_entry *entry)
 }
 
 struct hash_table *
-hash_table_create(int key_equals_function(const void *a,
-					  const void *b))
+hash_table_create(uint32_t (*hash_function)(const void *key),
+		  int (*key_equals_function)(const void *a,
+					     const void *b))
 {
 	struct hash_table *ht;
 
@@ -115,6 +116,7 @@ hash_table_create(int key_equals_function(const void *a,
 	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;
@@ -153,13 +155,28 @@ hash_table_destroy(struct hash_table *ht,
 }
 
 /**
+ * Finds a hash table entry with the given key.
+ *
+ * Returns NULL if no entry is found.  Note that the data pointer may be
+ * modified by the user.
+ */
+struct hash_entry *
+hash_table_search(struct hash_table *ht, const void *key)
+{
+	uint32_t hash = ht->hash_function(key);
+
+	return hash_table_search_pre_hashed(ht, hash, key);
+}
+
+/**
  * Finds a hash table entry with the given key and hash of that key.
  *
  * Returns NULL if no entry is found.  Note that the data pointer may be
  * modified by the user.
  */
 struct hash_entry *
-hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
+hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
+			     const void *key)
 {
 	uint32_t start_hash_address = hash % ht->size;
 	uint32_t hash_address = start_hash_address;
@@ -209,21 +226,36 @@ hash_table_rehash(struct hash_table *ht, int new_size_index)
 	ht->deleted_entries = 0;
 
 	hash_table_foreach(&old_ht, entry) {
-		hash_table_insert(ht, entry->hash, entry->key, entry->data);
+		hash_table_insert_pre_hashed(ht, entry->hash,
+					     entry->key, entry->data);
 	}
 
 	free(old_ht.table);
 }
 
 /**
+ * Inserts the key into the table.
+ *
+ * Note that insertion may rearrange the table on a resize or rehash,
+ * so previously found hash_entries are no longer valid after this function.
+ */
+struct hash_entry *
+hash_table_insert(struct hash_table *ht, const void *key, void *data)
+{
+	uint32_t hash = ht->hash_function(key);
+
+	return hash_table_insert_pre_hashed(ht, hash, key, data);
+}
+
+/**
  * Inserts the key with the given hash into the table.
  *
  * Note that insertion may rearrange the table on a resize or rehash,
  * so previously found hash_entries are no longer valid after this function.
  */
 struct hash_entry *
-hash_table_insert(struct hash_table *ht, uint32_t hash,
-		  const void *key, void *data)
+hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
+			     const void *key, void *data)
 {
 	uint32_t start_hash_address, hash_address;
 
@@ -288,11 +320,11 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
  * instead to avoid an extra search.
  */
 void
-hash_table_remove(struct hash_table *ht, uint32_t hash, const void *key)
+hash_table_remove(struct hash_table *ht, const void *key)
 {
 	struct hash_entry *entry;
 
-	entry = hash_table_search(ht, hash, key);
+	entry = hash_table_search(ht, key);
 
 	hash_table_remove_entry(ht, entry);
 }
diff --git a/hash_table.h b/hash_table.h
index 21a821d..7bdb805 100644
--- a/hash_table.h
+++ b/hash_table.h
@@ -42,6 +42,7 @@ struct hash_entry {
 
 struct hash_table {
 	struct hash_entry *table;
+	uint32_t (*hash_function)(const void *key);
 	int (*key_equals_function)(const void *a, const void *b);
 	uint32_t size;
 	uint32_t rehash;
@@ -52,23 +53,21 @@ struct hash_table {
 };
 
 struct hash_table *
-hash_table_create(int (*key_equals_function)(const void *a,
+hash_table_create(uint32_t (*hash_function)(const void *key),
+		  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, uint32_t hash,
-		  const void *key, void *data);
+hash_table_insert(struct hash_table *ht, const void *key, void *data);
 
 struct hash_entry *
-hash_table_search(struct hash_table *ht, uint32_t hash,
-		  const void *key);
+hash_table_search(struct hash_table *ht, const void *key);
 
 void
-hash_table_remove(struct hash_table *ht, uint32_t hash,
-		  const void *key);
+hash_table_remove(struct hash_table *ht, const void *key);
 
 void
 hash_table_remove_entry(struct hash_table *ht, struct hash_entry *entry);
@@ -91,6 +90,18 @@ hash_table_random_entry(struct hash_table *ht,
 	     entry != NULL;					\
 	     entry = hash_table_next_entry(ht, entry))
 
+/* Alternate interfaces to reduce repeated calls to hash function. */
+struct hash_entry *
+hash_table_search_pre_hashed(struct hash_table *ht,
+			     uint32_t hash,
+			     const void *key);
+
+struct hash_entry *
+hash_table_insert_pre_hashed(struct hash_table *ht,
+			     uint32_t hash,
+			     const void *key, void *data);
+
+
 #ifdef __cplusplus
 } /* extern C */
 #endif
diff --git a/set.c b/set.c
index fe8ab41..4846e49 100644
--- a/set.c
+++ b/set.c
@@ -102,8 +102,9 @@ entry_is_present(const struct set_entry *entry)
 }
 
 struct set *
-set_create(int key_equals_function(const void *a,
-					  const void *b))
+set_create(uint32_t (*hash_function)(const void *key),
+	   int key_equals_function(const void *a,
+				   const void *b))
 {
 	struct set *ht;
 
@@ -115,6 +116,7 @@ set_create(int key_equals_function(const void *a,
 	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;
@@ -156,22 +158,35 @@ set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
 /* Does the set contain an entry with the given key and hash.
  */
 bool
-set_contains(struct set *ht, uint32_t hash, const void *key)
+set_contains(struct set *ht, const void *key)
 {
 	struct set_entry *entry;
 
-	entry = set_search(ht, hash, key);
+	entry = set_search(ht, key);
 
 	return entry != NULL;
 }
 
 /**
+ * Finds a set entry with the given key.
+ *
+ * Returns NULL if no entry is found.
+ */
+struct set_entry *
+set_search(struct set *ht, const void *key)
+{
+	uint32_t hash = ht->hash_function(key);
+
+	return set_search_pre_hashed (ht, hash, key);
+}
+
+/**
  * Finds a set entry with the given key and hash of that key.
  *
  * Returns NULL if no entry is found.
  */
 struct set_entry *
-set_search(struct set *ht, uint32_t hash, const void *key)
+set_search_pre_hashed(struct set *ht, uint32_t hash, const void *key)
 {
 	uint32_t hash_address;
 
@@ -224,7 +239,7 @@ set_rehash(struct set *ht, int new_size_index)
 	     entry != old_ht.table + old_ht.size;
 	     entry++) {
 		if (entry_is_present(entry)) {
-			set_add(ht, entry->hash, entry->key);
+			set_add_pre_hashed(ht, entry->hash, entry->key);
 		}
 	}
 
@@ -232,13 +247,27 @@ set_rehash(struct set *ht, int new_size_index)
 }
 
 /**
+ * Inserts the key into the table.
+ *
+ * Note that insertion may rearrange the table on a resize or rehash,
+ * so previously found hash_entries are no longer valid after this function.
+ */
+struct set_entry *
+set_add(struct set *ht, const void *key)
+{
+	uint32_t hash = ht->hash_function(key);
+
+	return set_add_pre_hashed(ht, hash, key);
+}
+
+/**
  * Inserts the key with the given hash into the table.
  *
  * Note that insertion may rearrange the table on a resize or rehash,
  * so previously found hash_entries are no longer valid after this function.
  */
 struct set_entry *
-set_add(struct set *ht, uint32_t hash, const void *key)
+set_add_pre_hashed(struct set *ht, uint32_t hash, const void *key)
 {
 	uint32_t hash_address;
 
@@ -298,11 +327,11 @@ set_add(struct set *ht, uint32_t hash, const void *key)
  * set_remove_entry can be called instead to avoid an extra search.
  */
 void
-set_remove(struct set *set, uint32_t hash, const void *key)
+set_remove(struct set *set, const void *key)
 {
 	struct set_entry *entry;
 
-	entry = set_search(set, hash, key);
+	entry = set_search(set, key);
 
 	set_remove_entry(set, entry);
 }
diff --git a/set.h b/set.h
index 1a041ba..53748bf 100644
--- a/set.h
+++ b/set.h
@@ -38,6 +38,7 @@ struct set_entry {
 
 struct set {
 	struct set_entry *table;
+	uint32_t (*hash_function)(const void *key);
 	int (*key_equals_function)(const void *a, const void *b);
 	uint32_t size;
 	uint32_t rehash;
@@ -48,23 +49,24 @@ struct set {
 };
 
 struct set *
-set_create(int (*key_equals_function)(const void *a,
-				       const void *b));
+set_create(uint32_t (*hash_function)(const void *key),
+	   int (*key_equals_function)(const void *a,
+				      const void *b));
 void
 set_destroy(struct set *set,
 	    void (*delete_function)(struct set_entry *entry));
 
 struct set_entry *
-set_add(struct set *set, uint32_t hash, const void *key);
+set_add(struct set *set, const void *key);
 
 bool
-set_contains(struct set *set, uint32_t hash, const void *key);
+set_contains(struct set *set, const void *key);
 
 void
-set_remove(struct set *set, uint32_t hash, const void *key);
+set_remove(struct set *set, const void *key);
 
 struct set_entry *
-set_search(struct set *set, uint32_t hash, const void *key);
+set_search(struct set *set, const void *key);
 
 void
 set_remove_entry(struct set *set, struct set_entry *entry);
@@ -76,4 +78,11 @@ struct set_entry *
 set_random_entry(struct set *set,
 		 int (*predicate)(struct set_entry *entry));
 
+/* Alternate interfaces to reduce repeated calls to hash function. */
+struct set_entry *
+set_search_pre_hashed(struct set *set, uint32_t hash, const void *key);
+
+struct set_entry *
+set_add_pre_hashed(struct set *set, uint32_t hash, const void *key);
+
 #endif
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);