diff options
Diffstat (limited to 'src/util')
| -rw-r--r-- | src/util/hash_table.c | 75 | ||||
| -rw-r--r-- | src/util/hash_table.h | 19 | ||||
| -rw-r--r-- | src/util/tests/hash_table/collision.c | 22 | ||||
| -rw-r--r-- | src/util/tests/hash_table/delete_and_lookup.c | 16 | ||||
| -rw-r--r-- | src/util/tests/hash_table/delete_management.c | 9 | ||||
| -rw-r--r-- | src/util/tests/hash_table/destroy_callback.c | 9 | ||||
| -rw-r--r-- | src/util/tests/hash_table/insert_and_lookup.c | 13 | ||||
| -rw-r--r-- | src/util/tests/hash_table/insert_many.c | 6 | ||||
| -rw-r--r-- | src/util/tests/hash_table/random_entry.c | 4 | ||||
| -rw-r--r-- | src/util/tests/hash_table/remove_null.c | 2 | ||||
| -rw-r--r-- | src/util/tests/hash_table/replacement.c | 13 |
11 files changed, 114 insertions, 74 deletions
diff --git a/src/util/hash_table.c b/src/util/hash_table.c index 920bdfd3317..e85ebe345f8 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_pre_hashed(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 d6b6ebf4069..5561e158454 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_pre_hashed(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 9174c396151..2da316dd727 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 fc886ff4f4e..be54631e3b2 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 b8d764019f4..0a6bec378c4 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 dce2b333234..79b4fda0ee3 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 402f3fd4002..0705b07c2ee 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 b2122dcf96c..c6c0591f751 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 22cafa7e857..4a79181afba 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 90fb784ac40..7042f5e9349 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 387cfc0fd94..01ede685826 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); |