--- src/util/non_replacing_hash_table.c | 112 +++++++++++++++++++----------------- src/util/non_replacing_hash_table.h | 102 ++++++++++++++++---------------- 2 files changed, 111 insertions(+), 103 deletions(-)
diff --git a/src/util/non_replacing_hash_table.c b/src/util/non_replacing_hash_table.c index 48f42aa7c9..ecec94e2d6 100644 --- a/src/util/non_replacing_hash_table.c +++ b/src/util/non_replacing_hash_table.c @@ -93,32 +93,32 @@ static const struct { }; static int -entry_is_free(const struct hash_entry *entry) +entry_is_free(const struct non_replacing_hash_entry *entry) { return entry->key == NULL; } static int -entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) +entry_is_deleted(const struct non_replacing_hash_table *ht, struct non_replacing_hash_entry *entry) { return entry->key == ht->deleted_key; } static int -entry_is_present(const struct hash_table *ht, struct hash_entry *entry) +entry_is_present(const struct non_replacing_hash_table *ht, struct non_replacing_hash_entry *entry) { return entry->key != NULL && entry->key != ht->deleted_key; } -struct hash_table * -_mesa_hash_table_create(void *mem_ctx, +struct non_replacing_hash_table * +_mesa_non_replacing_hash_table_create(void *mem_ctx, uint32_t (*key_hash_function)(const void *key), bool (*key_equals_function)(const void *a, const void *b)) { - struct hash_table *ht; + struct non_replacing_hash_table *ht; - ht = ralloc(mem_ctx, struct hash_table); + ht = ralloc(mem_ctx, struct non_replacing_hash_table); if (ht == NULL) return NULL; @@ -128,7 +128,7 @@ _mesa_hash_table_create(void *mem_ctx, 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->table = rzalloc_array(ht, struct non_replacing_hash_entry, ht->size); ht->entries = 0; ht->deleted_entries = 0; ht->deleted_key = &deleted_key_value; @@ -148,16 +148,16 @@ _mesa_hash_table_create(void *mem_ctx, * freeing. */ void -_mesa_hash_table_destroy(struct hash_table *ht, - void (*delete_function)(struct hash_entry *entry)) +_mesa_non_replacing_hash_table_destroy(struct non_replacing_hash_table *ht, + void (*delete_function)(struct non_replacing_hash_entry *entry)) { if (!ht) return; if (delete_function) { - struct hash_entry *entry; + struct non_replacing_hash_entry *entry; - hash_table_foreach(ht, entry) { + non_replacing_hash_table_foreach(ht, entry) { delete_function(entry); } } @@ -171,10 +171,10 @@ _mesa_hash_table_destroy(struct hash_table *ht, * If delete_function is passed, it gets called on each entry present. */ void -_mesa_hash_table_clear(struct hash_table *ht, - void (*delete_function)(struct hash_entry *entry)) +_mesa_non_replacing_hash_table_clear(struct non_replacing_hash_table *ht, + void (*delete_function)(struct non_replacing_hash_entry *entry)) { - struct hash_entry *entry; + struct non_replacing_hash_entry *entry; for (entry = ht->table; entry != ht->table + ht->size; entry++) { if (entry->key == NULL) @@ -202,13 +202,14 @@ _mesa_hash_table_clear(struct hash_table *ht, * This must be called before any keys are actually deleted from the table. */ void -_mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key) +_mesa_non_replacing_hash_table_set_deleted_key(struct non_replacing_hash_table *ht, + const void *deleted_key) { ht->deleted_key = deleted_key; } -static struct hash_entry * -hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) +static struct non_replacing_hash_entry * +hash_table_search(struct non_replacing_hash_table *ht, uint32_t hash, const void *key) { uint32_t start_hash_address = hash % ht->size; uint32_t hash_address = start_hash_address; @@ -216,13 +217,13 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) do { uint32_t double_hash; - struct hash_entry *entry = ht->table + hash_address; + struct non_replacing_hash_entry *entry = ht->table + hash_address; if (entry_is_free(entry)) { return NULL; } else if (entry_is_present(ht, entry) && entry->hash == hash) { if (ht->key_equals_function(key, entry->key)) { - struct hash_entry *previous_entry = entry; + struct non_replacing_hash_entry *previous_entry = entry; /* Follow the chain of matching key's to the end */ while (previous_entry->next_data != 0 ) { @@ -256,35 +257,36 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *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) +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_search(struct non_replacing_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) +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_search_pre_hashed(struct non_replacing_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, +static struct non_replacing_hash_entry * +hash_table_insert(struct non_replacing_hash_table *ht, uint32_t hash, const void *key, void *data); static void -_mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) +_mesa_non_replacing_hash_table_rehash(struct non_replacing_hash_table *ht, + unsigned new_size_index) { - struct hash_table old_ht; - struct hash_entry *table, *entry; + struct non_replacing_hash_table old_ht; + struct non_replacing_hash_entry *table, *entry; if (new_size_index >= ARRAY_SIZE(hash_sizes)) return; - table = rzalloc_array(ht, struct hash_entry, + table = rzalloc_array(ht, struct non_replacing_hash_entry, hash_sizes[new_size_index].size); if (table == NULL) return; @@ -299,32 +301,32 @@ _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index) ht->entries = 0; ht->deleted_entries = 0; - hash_table_foreach(&old_ht, entry) { + non_replacing_hash_table_foreach(&old_ht, entry) { hash_table_insert(ht, entry->hash, entry->key, entry->data); } ralloc_free(old_ht.table); } -static struct hash_entry * -hash_table_insert(struct hash_table *ht, uint32_t hash, +static struct non_replacing_hash_entry * +hash_table_insert(struct non_replacing_hash_table *ht, uint32_t hash, const void *key, void *data) { uint32_t start_hash_address, hash_address; - struct hash_entry *available_entry = NULL; + struct non_replacing_hash_entry *available_entry = NULL; assert(key != NULL); if (ht->entries >= ht->max_entries) { - _mesa_hash_table_rehash(ht, ht->size_index + 1); + _mesa_non_replacing_hash_table_rehash(ht, ht->size_index + 1); } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { - _mesa_hash_table_rehash(ht, ht->size_index); + _mesa_non_replacing_hash_table_rehash(ht, ht->size_index); } start_hash_address = hash % ht->size; hash_address = start_hash_address; do { - struct hash_entry *entry = ht->table + hash_address; + struct non_replacing_hash_entry *entry = ht->table + hash_address; uint32_t double_hash; if (!entry_is_present(ht, entry)) { @@ -351,7 +353,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, if (!entry_is_deleted(ht, entry) && entry->hash == hash && ht->key_equals_function(key, entry->key)) { - struct hash_entry *old_entry = entry; + struct non_replacing_hash_entry *old_entry = entry; /* Follow the chain of matching key's to the end */ while (old_entry->next_data != 0) { @@ -411,16 +413,18 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, * 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) +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_insert(struct non_replacing_hash_table *ht, + const void *key, void *data) { assert(ht->key_hash_function); return hash_table_insert(ht, ht->key_hash_function(key), key, data); } -struct hash_entry * -_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, - const void *key, void *data) +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_insert_pre_hashed(struct non_replacing_hash_table *ht, + uint32_t hash, const void *key, + void *data) { assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key)); return hash_table_insert(ht, hash, key, data); @@ -437,8 +441,8 @@ _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, * the chain will be broken, and the table will have unpredictable results. */ void -_mesa_hash_table_remove(struct hash_table *ht, - struct hash_entry *entry) +_mesa_non_replacing_hash_table_remove(struct non_replacing_hash_table *ht, + struct non_replacing_hash_entry *entry) { if (!entry) return; @@ -455,9 +459,9 @@ _mesa_hash_table_remove(struct hash_table *ht, * Pass in NULL for the first entry, as in the start of a for loop. Note that * an iteration over the table is O(table_size) not O(entries). */ -struct hash_entry * -_mesa_hash_table_next_entry(struct hash_table *ht, - struct hash_entry *entry) +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_next_entry(struct non_replacing_hash_table *ht, + struct non_replacing_hash_entry *entry) { if (entry == NULL) entry = ht->table; @@ -481,11 +485,11 @@ _mesa_hash_table_next_entry(struct hash_table *ht, * implementation. @predicate may be used to filter entries, or may * be set to NULL for no filtering. */ -struct hash_entry * -_mesa_hash_table_random_entry(struct hash_table *ht, - bool (*predicate)(struct hash_entry *entry)) +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_random_entry(struct non_replacing_hash_table *ht, + bool (*predicate)(struct non_replacing_hash_entry *entry)) { - struct hash_entry *entry; + struct non_replacing_hash_entry *entry; uint32_t i = rand() % ht->size; if (ht->entries == 0) @@ -541,7 +545,7 @@ _mesa_hash_string(const char *key) /** * String compare function for use as the comparison callback in - * _mesa_hash_table_create(). + * _mesa_non_replacing_hash_table_create(). */ bool _mesa_key_string_equal(const void *a, const void *b) diff --git a/src/util/non_replacing_hash_table.h b/src/util/non_replacing_hash_table.h index 7550400539..f047ad5c11 100644 --- a/src/util/non_replacing_hash_table.h +++ b/src/util/non_replacing_hash_table.h @@ -25,8 +25,8 @@ * */ -#ifndef _HASH_TABLE_H -#define _HASH_TABLE_H +#ifndef _NON_REPLACING_HASH_TABLE_H +#define _NON_REPLACING_HASH_TABLE_H #include <stdlib.h> #include <inttypes.h> @@ -38,7 +38,7 @@ extern "C" { #endif -struct hash_entry { +struct non_replacing_hash_entry { uint32_t hash; const void *key; void *data; @@ -49,8 +49,8 @@ struct hash_entry { uint32_t next_data; }; -struct hash_table { - struct hash_entry *table; +struct non_replacing_hash_table { + struct non_replacing_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; @@ -62,41 +62,44 @@ struct hash_table { uint32_t deleted_entries; }; -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, - void (*delete_function)(struct hash_entry *entry)); -void _mesa_hash_table_clear(struct hash_table *ht, - void (*delete_function)(struct hash_entry *entry)); -void _mesa_hash_table_set_deleted_key(struct hash_table *ht, - const void *deleted_key); - -static inline uint32_t _mesa_hash_table_num_entries(struct hash_table *ht) +struct non_replacing_hash_table * +_mesa_non_replacing_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_non_replacing_hash_table_destroy(struct non_replacing_hash_table *ht, + void (*delete_function)(struct non_replacing_hash_entry *entry)); +void _mesa_non_replacing_hash_table_clear(struct non_replacing_hash_table *ht, + void (*delete_function)(struct non_replacing_hash_entry *entry)); +void _mesa_non_replacing_hash_table_set_deleted_key(struct non_replacing_hash_table *ht, + const void *deleted_key); + +static inline uint32_t +_mesa_non_replacing_hash_table_num_entries(struct non_replacing_hash_table *ht) { return ht->entries; } -struct hash_entry * -_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data); -struct hash_entry * -_mesa_hash_table_insert_pre_hashed(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); - -struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht, - struct hash_entry *entry); -struct hash_entry * -_mesa_hash_table_random_entry(struct hash_table *ht, - bool (*predicate)(struct hash_entry *entry)); +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_insert(struct non_replacing_hash_table *ht, const void *key, + void *data); +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_insert_pre_hashed(struct non_replacing_hash_table *ht, uint32_t hash, + const void *key, void *data); +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_search(struct non_replacing_hash_table *ht, const void *key); +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_search_pre_hashed(struct non_replacing_hash_table *ht, uint32_t hash, + const void *key); +void _mesa_non_replacing_hash_table_remove(struct non_replacing_hash_table *ht, + struct non_replacing_hash_entry *entry); + +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_next_entry(struct non_replacing_hash_table *ht, + struct non_replacing_hash_entry *entry); +struct non_replacing_hash_entry * +_mesa_non_replacing_hash_table_random_entry(struct non_replacing_hash_table *ht, + bool (*predicate)(struct non_replacing_hash_entry *entry)); uint32_t _mesa_hash_data(const void *data, size_t size); uint32_t _mesa_hash_string(const char *key); @@ -118,7 +121,8 @@ enum { }; static inline uint32_t -_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size) +_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, + size_t size) { const uint8_t *bytes = (const uint8_t *)data; @@ -139,21 +143,21 @@ _mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size) * an entry's data with the deleted marker), but not against insertion * (which may rehash the table, making entry a dangling pointer). */ -#define hash_table_foreach(ht, entry) \ - for (entry = _mesa_hash_table_next_entry(ht, NULL); \ - entry != NULL; \ - entry = _mesa_hash_table_next_entry(ht, entry)) +#define non_replacing_hash_table_foreach(ht, entry) \ + for (entry = _mesa_non_replacing_hash_table_next_entry(ht, NULL); \ + entry != NULL; \ + entry = _mesa_non_replacing_hash_table_next_entry(ht, entry)) static inline void -hash_table_call_foreach(struct hash_table *ht, - void (*callback)(const void *key, - void *data, - void *closure), - void *closure) +non_replacing_hash_table_call_foreach(struct non_replacing_hash_table *ht, + void (*callback)(const void *key, + void *data, + void *closure), + void *closure) { - struct hash_entry *entry; + struct non_replacing_hash_entry *entry; - hash_table_foreach(ht, entry) + non_replacing_hash_table_foreach(ht, entry) callback(entry->key, entry->data, closure); } @@ -161,4 +165,4 @@ hash_table_call_foreach(struct hash_table *ht, } /* extern C */ #endif -#endif /* _HASH_TABLE_H */ +#endif /* _NON_REPLACING_HASH_TABLE_H */ -- 2.11.0 _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev