[Mesa-dev] [PATCH] util/hash_table: Rework the API to know about hashing
Timothy Arceri
t_arceri at yahoo.com.au
Tue Nov 25 21:42:50 PST 2014
On Tue, 2014-11-25 at 01:56 -0500, Connor Abbott wrote:
> On Tue, Nov 25, 2014 at 1:19 AM, Jason Ekstrand <jason at jlekstrand.net> wrote:
> > 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 intrinsicly
> > 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.
>
> Yes, please! The only fear I have is that this may affect some
> microbenchmark somewhere, since every time you insert, lookup, or
> remove an element of the hash table you now have to go through a
> function pointer to get to the hashing function. This doesn't seem too
> likely to make a difference, but since the primary goal of the hash
> table and the reason it was written is performance you can never be
> too careful. Of course, if it does turn out to make a difference, the
> fix is easy.
On the subject of the hash table performance I spent way to much time
looking into this recently. In the end it was taking up to much time
benchmarking and profiling for what it was worth (at least in my test
cases) so I've moved on for now. However for those interested here is
what I found.
Unsurprisingly most time is spent doing the hash and resolving
collisions. For increased hash speed I implemented the _mm_crc32_u8()
intrinsic which seemed to give a nice bump in performance and with no
noticeable change in collisions over the FNV-1a hash.
For better collision resolution I was looking at robin hood hashing
which looks like a nice fit for the current table [1] but moved on
before trying it out.
As for other improvements I also split the insert function in two as
currently there is almost always a search done before the insert, but
then the insert does a second search to find an empty slot. So I created
a _mesa_hash_table_search_pre_insert function that checks if the hash
already exists but also returns the spare slot if it doesn't which can
then just be passed to an insert that doesn't do a second search.
Once this is done you can also reorder the if statement in the search as
you now can expect search calls to be lookups and return a result rather
than looking for a free slot.
Although this seemed to reduce time spent in this area I also noticed a
drop (very small but seemingly reproducible) in frame rates I couldn't
work out why this might be happening.
Anyway if anyone's interested in looking at this further I'm happy to
send the patches or push it to my github repo.
[1] http://codecapsule.com/2013/11/11/robin-hood-hashing/
>
> Connor
>
> >
> > Signed-off-by: Jason Ekstrand <jason.ekstrand at intel.com>
> > ---
> > src/gallium/drivers/vc4/vc4_opt_cse.c | 7 +--
> > src/glsl/ir_variable_refcount.cpp | 9 ++--
> > src/glsl/link_uniform_block_active_visitor.cpp | 6 +--
> > src/glsl/link_uniform_blocks.cpp | 3 +-
> > src/mesa/main/hash.c | 17 ++++--
> > src/util/hash_table.c | 75 +++++++++++++++++++-------
> > src/util/hash_table.h | 19 +++++--
> > src/util/tests/hash_table/collision.c | 22 ++++----
> > src/util/tests/hash_table/delete_and_lookup.c | 16 +++---
> > src/util/tests/hash_table/delete_management.c | 9 ++--
> > src/util/tests/hash_table/destroy_callback.c | 9 ++--
> > src/util/tests/hash_table/insert_and_lookup.c | 13 +++--
> > src/util/tests/hash_table/insert_many.c | 6 +--
> > src/util/tests/hash_table/random_entry.c | 4 +-
> > src/util/tests/hash_table/remove_null.c | 2 +-
> > src/util/tests/hash_table/replacement.c | 13 +++--
> > 16 files changed, 138 insertions(+), 92 deletions(-)
> >
> > diff --git a/src/gallium/drivers/vc4/vc4_opt_cse.c b/src/gallium/drivers/vc4/vc4_opt_cse.c
> > index bebfb652..0e9335e 100644
> > --- a/src/gallium/drivers/vc4/vc4_opt_cse.c
> > +++ b/src/gallium/drivers/vc4/vc4_opt_cse.c
> > @@ -84,7 +84,7 @@ vc4_find_cse(struct vc4_compile *c, struct hash_table *ht,
> >
> > uint32_t hash = _mesa_hash_data(&key, sizeof(key));
> > struct hash_entry *entry =
> > - _mesa_hash_table_search(ht, hash, &key);
> > + _mesa_hash_table_search_with_hash(ht, hash, &key);
> >
> > if (entry) {
> > if (debug) {
> > @@ -106,7 +106,7 @@ vc4_find_cse(struct vc4_compile *c, struct hash_table *ht,
> > if (!alloc_key)
> > return NULL;
> > memcpy(alloc_key, &key, sizeof(*alloc_key));
> > - _mesa_hash_table_insert(ht, hash, alloc_key, inst);
> > + _mesa_hash_table_insert_with_hash(ht, hash, alloc_key, inst);
> >
> > if (debug) {
> > fprintf(stderr, "Added to CSE HT: ");
> > @@ -125,7 +125,8 @@ qir_opt_cse(struct vc4_compile *c)
> > struct qinst *last_sf = NULL;
> > uint32_t sf_count = 0, r4_count = 0;
> >
> > - struct hash_table *ht = _mesa_hash_table_create(NULL, inst_key_equals);
> > + struct hash_table *ht = _mesa_hash_table_create(NULL, NULL,
> > + inst_key_equals);
> > if (!ht)
> > return false;
> >
> > diff --git a/src/glsl/ir_variable_refcount.cpp b/src/glsl/ir_variable_refcount.cpp
> > index f67fe67..e4d825c 100644
> > --- a/src/glsl/ir_variable_refcount.cpp
> > +++ b/src/glsl/ir_variable_refcount.cpp
> > @@ -38,7 +38,8 @@
> > ir_variable_refcount_visitor::ir_variable_refcount_visitor()
> > {
> > this->mem_ctx = ralloc_context(NULL);
> > - this->ht = _mesa_hash_table_create(NULL, _mesa_key_pointer_equal);
> > + this->ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
> > + _mesa_key_pointer_equal);
> > }
> >
> > static void
> > @@ -70,15 +71,13 @@ ir_variable_refcount_visitor::get_variable_entry(ir_variable *var)
> > {
> > assert(var);
> >
> > - struct hash_entry *e = _mesa_hash_table_search(this->ht,
> > - _mesa_hash_pointer(var),
> > - var);
> > + struct hash_entry *e = _mesa_hash_table_search(this->ht, var);
> > if (e)
> > return (ir_variable_refcount_entry *)e->data;
> >
> > ir_variable_refcount_entry *entry = new ir_variable_refcount_entry(var);
> > assert(entry->referenced_count == 0);
> > - _mesa_hash_table_insert(this->ht, _mesa_hash_pointer(var), var, entry);
> > + _mesa_hash_table_insert(this->ht, var, entry);
> >
> > return entry;
> > }
> > diff --git a/src/glsl/link_uniform_block_active_visitor.cpp b/src/glsl/link_uniform_block_active_visitor.cpp
> > index 9da6a4b..292cde3 100644
> > --- a/src/glsl/link_uniform_block_active_visitor.cpp
> > +++ b/src/glsl/link_uniform_block_active_visitor.cpp
> > @@ -27,9 +27,8 @@
> > link_uniform_block_active *
> > process_block(void *mem_ctx, struct hash_table *ht, ir_variable *var)
> > {
> > - const uint32_t h = _mesa_hash_string(var->get_interface_type()->name);
> > const hash_entry *const existing_block =
> > - _mesa_hash_table_search(ht, h, var->get_interface_type()->name);
> > + _mesa_hash_table_search(ht, var->get_interface_type()->name);
> >
> > const glsl_type *const block_type = var->is_interface_instance()
> > ? var->type : var->get_interface_type();
> > @@ -54,8 +53,7 @@ process_block(void *mem_ctx, struct hash_table *ht, ir_variable *var)
> > b->binding = 0;
> > }
> >
> > - _mesa_hash_table_insert(ht, h, var->get_interface_type()->name,
> > - (void *) b);
> > + _mesa_hash_table_insert(ht, var->get_interface_type()->name, (void *) b);
> > return b;
> > } else {
> > link_uniform_block_active *const b =
> > diff --git a/src/glsl/link_uniform_blocks.cpp b/src/glsl/link_uniform_blocks.cpp
> > index 536fcd4..f5fc502 100644
> > --- a/src/glsl/link_uniform_blocks.cpp
> > +++ b/src/glsl/link_uniform_blocks.cpp
> > @@ -182,7 +182,8 @@ link_uniform_blocks(void *mem_ctx,
> > * the hash is organized by block-name.
> > */
> > struct hash_table *block_hash =
> > - _mesa_hash_table_create(mem_ctx, _mesa_key_string_equal);
> > + _mesa_hash_table_create(mem_ctx, _mesa_key_hash_string,
> > + _mesa_key_string_equal);
> >
> > if (block_hash == NULL) {
> > _mesa_error_no_memory(__func__);
> > diff --git a/src/mesa/main/hash.c b/src/mesa/main/hash.c
> > index 52095f7..a73d4a3 100644
> > --- a/src/mesa/main/hash.c
> > +++ b/src/mesa/main/hash.c
> > @@ -96,6 +96,12 @@ uint_hash(GLuint id)
> > return id;
> > }
> >
> > +static uint32_t
> > +uint_key_hash(const void *key)
> > +{
> > + return uint_hash((uintptr_t)key);
> > +}
> > +
> > static void *
> > uint_key(GLuint id)
> > {
> > @@ -114,7 +120,8 @@ _mesa_NewHashTable(void)
> > struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
> >
> > if (table) {
> > - table->ht = _mesa_hash_table_create(NULL, uint_key_compare);
> > + table->ht = _mesa_hash_table_create(NULL, uint_key_hash,
> > + uint_key_compare);
> > if (table->ht == NULL) {
> > free(table);
> > _mesa_error_no_memory(__func__);
> > @@ -175,7 +182,7 @@ _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
> > if (key == DELETED_KEY_VALUE)
> > return table->deleted_key_data;
> >
> > - entry = _mesa_hash_table_search(table->ht, uint_hash(key), uint_key(key));
> > + entry = _mesa_hash_table_search(table->ht, uint_key(key));
> > if (!entry)
> > return NULL;
> >
> > @@ -266,11 +273,11 @@ _mesa_HashInsert_unlocked(struct _mesa_HashTable *table, GLuint key, void *data)
> > if (key == DELETED_KEY_VALUE) {
> > table->deleted_key_data = data;
> > } else {
> > - entry = _mesa_hash_table_search(table->ht, hash, uint_key(key));
> > + entry = _mesa_hash_table_search_with_hash(table->ht, hash, uint_key(key));
> > if (entry) {
> > entry->data = data;
> > } else {
> > - _mesa_hash_table_insert(table->ht, hash, uint_key(key), data);
> > + _mesa_hash_table_insert_with_hash(table->ht, hash, uint_key(key), data);
> > }
> > }
> > }
> > @@ -340,7 +347,7 @@ _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
> > if (key == DELETED_KEY_VALUE) {
> > table->deleted_key_data = NULL;
> > } else {
> > - entry = _mesa_hash_table_search(table->ht, uint_hash(key), uint_key(key));
> > + entry = _mesa_hash_table_search(table->ht, uint_key(key));
> > _mesa_hash_table_remove(table->ht, entry);
> > }
> > mtx_unlock(&table->Mutex);
> > diff --git a/src/util/hash_table.c b/src/util/hash_table.c
> > index 1b6726c..8eb96f9 100644
> > --- a/src/util/hash_table.c
> > +++ b/src/util/hash_table.c
> > @@ -42,6 +42,7 @@
> >
> > #include <stdlib.h>
> > #include <string.h>
> > +#include <assert.h>
> >
> > #include "hash_table.h"
> > #include "ralloc.h"
> > @@ -110,6 +111,7 @@ entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
> >
> > struct hash_table *
> > _mesa_hash_table_create(void *mem_ctx,
> > + uint32_t (*key_hash_function)(const void *key),
> > bool (*key_equals_function)(const void *a,
> > const void *b))
> > {
> > @@ -123,6 +125,7 @@ _mesa_hash_table_create(void *mem_ctx,
> > 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->key_hash_function = key_hash_function;
> > ht->key_equals_function = key_equals_function;
> > ht->table = rzalloc_array(ht, struct hash_entry, ht->size);
> > ht->entries = 0;
> > @@ -176,15 +179,8 @@ _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
> > ht->deleted_key = deleted_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 *
> > -_mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
> > - const void *key)
> > +static struct hash_entry *
> > +hash_table_search(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;
> > @@ -210,6 +206,31 @@ _mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
> > return NULL;
> > }
> >
> > +/**
> > + * 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 *
> > +_mesa_hash_table_search(struct hash_table *ht, const void *key)
> > +{
> > + assert(ht->key_hash_function);
> > + return hash_table_search(ht, ht->key_hash_function(key), key);
> > +}
> > +
> > +struct hash_entry *
> > +_mesa_hash_table_search_with_hash(struct hash_table *ht, uint32_t hash,
> > + const void *key)
> > +{
> > + assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
> > + return hash_table_search(ht, hash, key);
> > +}
> > +
> > +static struct hash_entry *
> > +hash_table_insert(struct hash_table *ht, uint32_t hash,
> > + const void *key, void *data);
> > +
> > static void
> > _mesa_hash_table_rehash(struct hash_table *ht, int new_size_index)
> > {
> > @@ -235,22 +256,15 @@ _mesa_hash_table_rehash(struct hash_table *ht, int new_size_index)
> > ht->deleted_entries = 0;
> >
> > hash_table_foreach(&old_ht, entry) {
> > - _mesa_hash_table_insert(ht, entry->hash,
> > - entry->key, entry->data);
> > + hash_table_insert(ht, entry->hash, entry->key, entry->data);
> > }
> >
> > ralloc_free(old_ht.table);
> > }
> >
> > -/**
> > - * 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 *
> > -_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
> > - const void *key, void *data)
> > +static struct hash_entry *
> > +hash_table_insert(struct hash_table *ht, uint32_t hash,
> > + const void *key, void *data)
> > {
> > uint32_t start_hash_address, hash_address;
> >
> > @@ -307,6 +321,27 @@ _mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
> > }
> >
> > /**
> > + * 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 *
> > +_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
> > +{
> > + assert(ht->key_hash_function);
> > + hash_table_insert(ht, ht->key_hash_function(key), key, data);
> > +}
> > +
> > +struct hash_entry *
> > +_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash,
> > + const void *key, void *data)
> > +{
> > + assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
> > + hash_table_insert(ht, hash, key, data);
> > +}
> > +
> > +/**
> > * This function deletes the given hash table entry.
> > *
> > * Note that deletion doesn't otherwise modify the table, so an iteration over
> > diff --git a/src/util/hash_table.h b/src/util/hash_table.h
> > index d6b6ebf..a65127f 100644
> > --- a/src/util/hash_table.h
> > +++ b/src/util/hash_table.h
> > @@ -46,6 +46,7 @@ struct hash_entry {
> >
> > struct hash_table {
> > struct hash_entry *table;
> > + uint32_t (*key_hash_function)(const void *key);
> > bool (*key_equals_function)(const void *a, const void *b);
> > const void *deleted_key;
> > uint32_t size;
> > @@ -58,6 +59,7 @@ struct hash_table {
> >
> > struct hash_table *
> > _mesa_hash_table_create(void *mem_ctx,
> > + uint32_t (*key_hash_function)(const void *key),
> > bool (*key_equals_function)(const void *a,
> > const void *b));
> > void _mesa_hash_table_destroy(struct hash_table *ht,
> > @@ -66,11 +68,15 @@ void _mesa_hash_table_set_deleted_key(struct hash_table *ht,
> > const void *deleted_key);
> >
> > struct hash_entry *
> > -_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
> > - const void *key, void *data);
> > +_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
> > struct hash_entry *
> > -_mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
> > - const void *key);
> > +_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash,
> > + const void *key, void *data);
> > +struct hash_entry *
> > +_mesa_hash_table_search(struct hash_table *ht, const void *key);
> > +struct hash_entry *
> > +_mesa_hash_table_search_with_hash(struct hash_table *ht, uint32_t hash,
> > + const void *key);
> > void _mesa_hash_table_remove(struct hash_table *ht,
> > struct hash_entry *entry);
> >
> > @@ -85,6 +91,11 @@ uint32_t _mesa_hash_string(const char *key);
> > bool _mesa_key_string_equal(const void *a, const void *b);
> > bool _mesa_key_pointer_equal(const void *a, const void *b);
> >
> > +static inline uint32_t _mesa_key_hash_string(const void *key)
> > +{
> > + return _mesa_hash_string((const char *)key);
> > +}
> > +
> > static inline uint32_t _mesa_hash_pointer(const void *pointer)
> > {
> > return _mesa_hash_data(&pointer, sizeof(pointer));
> > diff --git a/src/util/tests/hash_table/collision.c b/src/util/tests/hash_table/collision.c
> > index 9174c39..e73c233 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_with_hash(ht, bad_hash, str1);
> > assert(entry1->key == str1);
> >
> > - entry2 = _mesa_hash_table_search(ht, bad_hash, str2);
> > + entry2 = _mesa_hash_table_search_with_hash(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_with_hash(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_with_hash(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_with_hash(ht, bad_hash, str1);
> > assert(entry1->key == str1);
> > - entry2 = _mesa_hash_table_search(ht, bad_hash, str2);
> > + entry2 = _mesa_hash_table_search_with_hash(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);
> > --
> > 2.1.0
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list