Mesa (master): util/hash_table: Do a full search when adding new items

[Jason Ekstrand]

Module: Mesa
Branch: master
Commit: c9287e797b3e58bd4403f79d484e7235dc59262d
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=c9287e797b3e58bd4403f79d484e7235dc59262d

Author: Jason Ekstrand <jason.ekstrand at intel.com>
Date:   Wed Feb  4 18:29:32 2015 -0800

util/hash_table: Do a full search when adding new items

Previously, the hash_table_insert function would bail early if it found a
deleted slot that it could re-use.  However, this is a problem if the key
being inserted is already in the hash table but further down the list.  If
this happens, the element ends up getting inserted in the hash table twice.
This commit makes it so that we walk over all of the possible entries for
the given key and then, if we don't find the key, place it in the available
free entry we found.

Reviewed-by: Eric Anholt <eric at anholt.net>

---

 src/util/hash_table.c |   23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index fd8e2ea..3247593 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -267,6 +267,7 @@ 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;
 
    if (ht->entries >= ht->max_entries) {
       _mesa_hash_table_rehash(ht, ht->size_index + 1);
@@ -281,13 +282,11 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
       uint32_t double_hash;
 
       if (!entry_is_present(ht, entry)) {
-         if (entry_is_deleted(ht, entry))
-            ht->deleted_entries--;
-         entry->hash = hash;
-         entry->key = key;
-         entry->data = data;
-         ht->entries++;
-         return entry;
+         /* Stash the first available entry we find */
+         if (available_entry == NULL)
+            available_entry = entry;
+         if (entry_is_free(entry))
+            break;
       }
 
       /* Implement replacement when another insert happens
@@ -314,6 +313,16 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
       hash_address = (hash_address + double_hash) % ht->size;
    } while (hash_address != start_hash_address);
 
+   if (available_entry) {
+      if (entry_is_deleted(ht, available_entry))
+         ht->deleted_entries--;
+      available_entry->hash = hash;
+      available_entry->key = key;
+      available_entry->data = data;
+      ht->entries++;
+      return available_entry;
+   }
+
    /* We could hit here if a required resize failed. An unchecked-malloc
     * application could ignore this result.
     */