summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorConnor Abbott <[email protected]>2019-05-21 12:21:53 +0200
committerConnor Abbott <[email protected]>2019-05-31 19:14:09 +0200
commit451211741c894e7aea33f92a75fe9870fc5f1478 (patch)
tree3c05b61d1348e2224d51c95b91f34b43bc7d3c4e
parentf7ff6856492e8437ad78bb6a853a681afd3fc98c (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]>
-rw-r--r--src/util/hash_table.c27
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) {