From 451211741c894e7aea33f92a75fe9870fc5f1478 Mon Sep 17 00:00:00 2001 From: Connor Abbott Date: Tue, 21 May 2019 12:21:53 +0200 Subject: [PATCH] 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 Acked-by: Jason Ekstrand --- src/util/hash_table.c | 27 +++++++++++++-------------- 1 file 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) { -- 2.30.2