[Mesa-dev] [PATCH 1/3] util/tests: Expand collision test for hash table

[Thomas Helland]

Add a test to exercise a worst case collision scenario
that may cause us to not be able to find an empty
slot in the table even though it is not full.
This hits the bug in my last revision of the series
converting the hash table to quadratic probing.

Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
---
 src/util/tests/hash_table/collision.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/src/util/tests/hash_table/collision.c b/src/util/tests/hash_table/collision.c
index 69a4c29..ba284d8 100644
--- a/src/util/tests/hash_table/collision.c
+++ b/src/util/tests/hash_table/collision.c
@@ -89,6 +89,20 @@ main(int argc, char **argv)
    entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2);
    assert(entry2->key == str2);
 
+
+   _mesa_hash_table_destroy(ht, NULL);
+
+   /* Try inserting multiple items with the same hash
+    * This exercises a worst case scenario where we might fail to find
+    * an empty slot in the table, even though there is free space
+    */
+   ht = _mesa_hash_table_create(NULL, NULL, _mesa_key_string_equal);
+   for (i = 0; i < 100; i++) {
+      char *key = malloc(10);
+      sprintf(key, "spam%d", i);
+      assert(_mesa_hash_table_insert_pre_hashed(ht, bad_hash, key, NULL) != NULL);
+   }
+
    _mesa_hash_table_destroy(ht, NULL);
 
    return 0;
-- 
2.3.4