diff options
| author | Connor Abbott <[email protected]> | 2019-05-21 12:21:53 +0200 |
|---|---|---|
| committer | Connor Abbott <[email protected]> | 2019-05-31 19:14:09 +0200 |
| commit | 451211741c894e7aea33f92a75fe9870fc5f1478 (patch) | |
| tree | 3c05b61d1348e2224d51c95b91f34b43bc7d3c4e /src/util | |
| parent | f7ff6856492e8437ad78bb6a853a681afd3fc98c (diff) | |
util/hash_table: Pull out loop-invariant computations
To keep the set and hash table in sync. Note that some of this had
already been done for hash tables, in particular pulling out the
hash % ht->size computation.
Reviewed-by: Eric Anholt <[email protected]>
Acked-by: Jason Ekstrand <[email protected]>
Diffstat (limited to 'src/util')
| -rw-r--r-- | src/util/hash_table.c | 27 |
1 files changed, 13 insertions, 14 deletions
diff --git a/src/util/hash_table.c b/src/util/hash_table.c index 57a5f247edc..65b685a0828 100644 --- a/src/util/hash_table.c +++ b/src/util/hash_table.c @@ -242,12 +242,12 @@ _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_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 size = ht->size; + uint32_t start_hash_address = hash % size; uint32_t hash_address = start_hash_address; + uint32_t double_hash = 1 + hash % ht->rehash; do { - uint32_t double_hash; - struct hash_entry *entry = ht->table + hash_address; if (entry_is_free(entry)) { @@ -258,9 +258,9 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) } } - double_hash = 1 + hash % ht->rehash; - - hash_address = (hash_address + double_hash) % ht->size; + hash_address += double_hash; + if (hash_address >= size) + hash_address -= size; } while (hash_address != start_hash_address); return NULL; @@ -326,7 +326,6 @@ 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; struct hash_entry *available_entry = NULL; assert(key != NULL); @@ -337,11 +336,12 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, _mesa_hash_table_rehash(ht, ht->size_index); } - start_hash_address = hash % ht->size; - hash_address = start_hash_address; + uint32_t size = ht->size; + uint32_t start_hash_address = hash % size; + uint32_t hash_address = start_hash_address; + uint32_t double_hash = 1 + hash % ht->rehash; do { struct hash_entry *entry = ht->table + hash_address; - uint32_t double_hash; if (!entry_is_present(ht, entry)) { /* Stash the first available entry we find */ @@ -370,10 +370,9 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, return entry; } - - double_hash = 1 + hash % ht->rehash; - - hash_address = (hash_address + double_hash) % ht->size; + hash_address += double_hash; + if (hash_address >= size) + hash_address -= size; } while (hash_address != start_hash_address); if (available_entry) { |