util/hash_table: Rework the API to know about hashing

Previously, the hash_table API required the user to do all of the hashing
of keys as it passed them in.  Since the hashing function is intrinsically
tied to the comparison function, it makes sense for the hash table to know
about it.  Also, it makes for a somewhat clumsy API as the user is
constantly calling hashing functions many of which have long names.  This
is especially bad when the standard call looks something like

_mesa_hash_table_insert(ht, _mesa_pointer_hash(key), key, data);

In the above case, there is no reason why the hash table shouldn't do the
hashing for you.  We leave the option for you to do your own hashing if
it's more efficient, but it's no longer needed.  Also, if you do do your
own hashing, the hash table will assert that your hash matches what it
expects out of the hashing function.  This should make it harder to mess up
your hashing.

v2: change to call the old entrypoint "pre_hashed" rather than
    "with_hash", like cworth's equivalent change upstream (change by
    anholt, acked-in-general by Jason).

Signed-off-by: Jason Ekstrand <jason.ekstrand@intel.com>
Signed-off-by: Eric Anholt <eric@anholt.net>
Reviewed-by: Eric Anholt <eric@anholt.net>

9 files changed, 44 insertions, 50 deletions

diff --git a/src/util/tests/hash_table/collision.c b/src/util/tests/hash_table/collision.c
index 9174c39..2da316d 100644
--- a/src/util/tests/hash_table/collision.c
+++ b/src/util/tests/hash_table/collision.c
@@ -40,38 +40,38 @@ main(int argc, char **argv)
    uint32_t bad_hash = 5;
    int i;
 
-   ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal);
+   ht = _mesa_hash_table_create(NULL, NULL, _mesa_key_string_equal);
 
-   _mesa_hash_table_insert(ht, bad_hash, str1, NULL);
-   _mesa_hash_table_insert(ht, bad_hash, str2, NULL);
+   _mesa_hash_table_insert_with_hash(ht, bad_hash, str1, NULL);
+   _mesa_hash_table_insert_with_hash(ht, bad_hash, str2, NULL);
 
-   entry1 = _mesa_hash_table_search(ht, bad_hash, str1);
+   entry1 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str1);
    assert(entry1->key == str1);
 
-   entry2 = _mesa_hash_table_search(ht, bad_hash, str2);
+   entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2);
    assert(entry2->key == str2);
 
    /* Check that we can still find #1 after inserting #2 */
-   entry1 = _mesa_hash_table_search(ht, bad_hash, str1);
+   entry1 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str1);
    assert(entry1->key == str1);
 
    /* Remove the collided entry and look again. */
    _mesa_hash_table_remove(ht, entry1);
-   entry2 = _mesa_hash_table_search(ht, bad_hash, str2);
+   entry2 = _mesa_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.
     */
-   _mesa_hash_table_insert(ht, bad_hash, str1, NULL);
+   _mesa_hash_table_insert_with_hash(ht, bad_hash, str1, NULL);
    for (i = 0; i < 100; i++) {
       char *key = malloc(10);
       sprintf(key, "spam%d", i);
-      _mesa_hash_table_insert(ht, _mesa_hash_string(key), key, NULL);
+      _mesa_hash_table_insert_with_hash(ht, _mesa_hash_string(key), key, NULL);
    }
-   entry1 = _mesa_hash_table_search(ht, bad_hash, str1);
+   entry1 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str1);
    assert(entry1->key == str1);
-   entry2 = _mesa_hash_table_search(ht, bad_hash, str2);
+   entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2);
    assert(entry2->key == str2);
 
    _mesa_hash_table_destroy(ht, NULL);
diff --git a/src/util/tests/hash_table/delete_and_lookup.c b/src/util/tests/hash_table/delete_and_lookup.c
index fc886ff..be54631 100644
--- a/src/util/tests/hash_table/delete_and_lookup.c
+++ b/src/util/tests/hash_table/delete_and_lookup.c
@@ -45,27 +45,25 @@ 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 = _mesa_hash_table_create(NULL, _mesa_key_string_equal);
+	ht = _mesa_hash_table_create(NULL, badhash, _mesa_key_string_equal);
 
-	_mesa_hash_table_insert(ht, hash_str1, str1, NULL);
-	_mesa_hash_table_insert(ht, hash_str2, str2, NULL);
+	_mesa_hash_table_insert(ht, str1, NULL);
+	_mesa_hash_table_insert(ht, str2, NULL);
 
-	entry = _mesa_hash_table_search(ht, hash_str2, str2);
+	entry = _mesa_hash_table_search(ht, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
-	entry = _mesa_hash_table_search(ht, hash_str1, str1);
+	entry = _mesa_hash_table_search(ht, str1);
 	assert(strcmp(entry->key, str1) == 0);
 
 	_mesa_hash_table_remove(ht, entry);
 
-	entry = _mesa_hash_table_search(ht, hash_str1, str1);
+	entry = _mesa_hash_table_search(ht, str1);
 	assert(entry == NULL);
 
-	entry = _mesa_hash_table_search(ht, hash_str2, str2);
+	entry = _mesa_hash_table_search(ht, str2);
 	assert(strcmp(entry->key, str2) == 0);
 
 	_mesa_hash_table_destroy(ht, NULL);
diff --git a/src/util/tests/hash_table/delete_management.c b/src/util/tests/hash_table/delete_management.c
index b8d7640..0a6bec3 100644
--- a/src/util/tests/hash_table/delete_management.c
+++ b/src/util/tests/hash_table/delete_management.c
@@ -51,24 +51,23 @@ main(int argc, char **argv)
    uint32_t keys[size];
    uint32_t i;
 
-   ht = _mesa_hash_table_create(NULL, uint32_t_key_equals);
+   ht = _mesa_hash_table_create(NULL, key_value, uint32_t_key_equals);
 
    for (i = 0; i < size; i++) {
       keys[i] = i;
 
-      _mesa_hash_table_insert(ht, i, keys + i, NULL);
+      _mesa_hash_table_insert(ht, keys + i, NULL);
 
       if (i >= 100) {
          uint32_t delete_value = i - 100;
-         entry = _mesa_hash_table_search(ht, delete_value,
-                                              &delete_value);
+         entry = _mesa_hash_table_search(ht, &delete_value);
          _mesa_hash_table_remove(ht, entry);
       }
    }
 
    /* Make sure that all our entries were present at the end. */
    for (i = size - 100; i < size; i++) {
-      entry = _mesa_hash_table_search(ht, i, keys + i);
+      entry = _mesa_hash_table_search(ht, keys + i);
       assert(entry);
       assert(key_value(entry->key) == i);
    }
diff --git a/src/util/tests/hash_table/destroy_callback.c b/src/util/tests/hash_table/destroy_callback.c
index dce2b33..79b4fda 100644
--- a/src/util/tests/hash_table/destroy_callback.c
+++ b/src/util/tests/hash_table/destroy_callback.c
@@ -50,13 +50,12 @@ int
 main(int argc, char **argv)
 {
    struct hash_table *ht;
-   uint32_t hash_str1 = _mesa_hash_string(str1);
-   uint32_t hash_str2 = _mesa_hash_string(str2);
 
-   ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal);
+   ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
+                                _mesa_key_string_equal);
 
-   _mesa_hash_table_insert(ht, hash_str1, str1, NULL);
-   _mesa_hash_table_insert(ht, hash_str2, str2, NULL);
+   _mesa_hash_table_insert(ht, str1, NULL);
+   _mesa_hash_table_insert(ht, str2, NULL);
 
    _mesa_hash_table_destroy(ht, delete_callback);
 
diff --git a/src/util/tests/hash_table/insert_and_lookup.c b/src/util/tests/hash_table/insert_and_lookup.c
index 402f3fd..0705b07 100644
--- a/src/util/tests/hash_table/insert_and_lookup.c
+++ b/src/util/tests/hash_table/insert_and_lookup.c
@@ -36,19 +36,18 @@ main(int argc, char **argv)
    struct hash_table *ht;
    const char *str1 = "test1";
    const char *str2 = "test2";
-   uint32_t hash_str1 = _mesa_hash_string(str1);
-   uint32_t hash_str2 = _mesa_hash_string(str2);
    struct hash_entry *entry;
 
-   ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal);
+   ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
+                                _mesa_key_string_equal);
 
-   _mesa_hash_table_insert(ht, hash_str1, str1, NULL);
-   _mesa_hash_table_insert(ht, hash_str2, str2, NULL);
+   _mesa_hash_table_insert(ht, str1, NULL);
+   _mesa_hash_table_insert(ht, str2, NULL);
 
-   entry = _mesa_hash_table_search(ht, hash_str1, str1);
+   entry = _mesa_hash_table_search(ht, str1);
    assert(strcmp(entry->key, str1) == 0);
 
-   entry = _mesa_hash_table_search(ht, hash_str2, str2);
+   entry = _mesa_hash_table_search(ht, str2);
    assert(strcmp(entry->key, str2) == 0);
 
    _mesa_hash_table_destroy(ht, NULL);
diff --git a/src/util/tests/hash_table/insert_many.c b/src/util/tests/hash_table/insert_many.c
index b2122dc..c6c0591 100644
--- a/src/util/tests/hash_table/insert_many.c
+++ b/src/util/tests/hash_table/insert_many.c
@@ -51,16 +51,16 @@ main(int argc, char **argv)
    uint32_t keys[size];
    uint32_t i;
 
-   ht = _mesa_hash_table_create(NULL, uint32_t_key_equals);
+   ht = _mesa_hash_table_create(NULL, key_value, uint32_t_key_equals);
 
    for (i = 0; i < size; i++) {
       keys[i] = i;
 
-      _mesa_hash_table_insert(ht, i, keys + i, NULL);
+      _mesa_hash_table_insert(ht, keys + i, NULL);
    }
 
    for (i = 0; i < size; i++) {
-      entry = _mesa_hash_table_search(ht, i, keys + i);
+      entry = _mesa_hash_table_search(ht, keys + i);
       assert(entry);
       assert(key_value(entry->key) == i);
    }
diff --git a/src/util/tests/hash_table/random_entry.c b/src/util/tests/hash_table/random_entry.c
index 22cafa7..4a79181 100644
--- a/src/util/tests/hash_table/random_entry.c
+++ b/src/util/tests/hash_table/random_entry.c
@@ -57,12 +57,12 @@ main(int argc, char **argv)
    uint32_t keys[size];
    uint32_t i, random_value;
 
-   ht = _mesa_hash_table_create(NULL, uint32_t_key_equals);
+   ht = _mesa_hash_table_create(NULL, key_value, uint32_t_key_equals);
 
    for (i = 0; i < size; i++) {
       keys[i] = i;
 
-      _mesa_hash_table_insert(ht, i, keys + i, NULL);
+      _mesa_hash_table_insert(ht, keys + i, NULL);
    }
 
    /* Test the no-predicate case. */
diff --git a/src/util/tests/hash_table/remove_null.c b/src/util/tests/hash_table/remove_null.c
index 90fb784..7042f5e 100644
--- a/src/util/tests/hash_table/remove_null.c
+++ b/src/util/tests/hash_table/remove_null.c
@@ -35,7 +35,7 @@ main(int argc, char **argv)
 {
    struct hash_table *ht;
 
-   ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal);
+   ht = _mesa_hash_table_create(NULL, NULL, _mesa_key_string_equal);
 
    _mesa_hash_table_remove(ht, NULL);
 
diff --git a/src/util/tests/hash_table/replacement.c b/src/util/tests/hash_table/replacement.c
index 387cfc0..01ede68 100644
--- a/src/util/tests/hash_table/replacement.c
+++ b/src/util/tests/hash_table/replacement.c
@@ -36,24 +36,23 @@ main(int argc, char **argv)
    struct hash_table *ht;
    char *str1 = strdup("test1");
    char *str2 = strdup("test1");
-   uint32_t hash_str1 = _mesa_hash_string(str1);
-   uint32_t hash_str2 = _mesa_hash_string(str2);
    struct hash_entry *entry;
 
    assert(str1 != str2);
 
-   ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal);
+   ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
+                                _mesa_key_string_equal);
 
-   _mesa_hash_table_insert(ht, hash_str1, str1, str1);
-   _mesa_hash_table_insert(ht, hash_str2, str2, str2);
+   _mesa_hash_table_insert(ht, str1, str1);
+   _mesa_hash_table_insert(ht, str2, str2);
 
-   entry = _mesa_hash_table_search(ht, hash_str1, str1);
+   entry = _mesa_hash_table_search(ht, str1);
    assert(entry);
    assert(entry->data == str2);
 
    _mesa_hash_table_remove(ht, entry);
 
-   entry = _mesa_hash_table_search(ht, hash_str1, str1);
+   entry = _mesa_hash_table_search(ht, str1);
    assert(!entry);
 
    _mesa_hash_table_destroy(ht, NULL);