[Mesa-dev] [PATCH 08/14] util: Implement the insertion functionality

[Thomas Helland]

---
 src/util/non_replacing_hash_table.c | 41 +++++++++++++++++++++++++++++++------
 1 file changed, 35 insertions(+), 6 deletions(-)

diff --git a/src/util/non_replacing_hash_table.c b/src/util/non_replacing_hash_table.c
index 1730b1ee0d..a4c57e9349 100644
--- a/src/util/non_replacing_hash_table.c
+++ b/src/util/non_replacing_hash_table.c
@@ -317,12 +317,14 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
             break;
       }
 
-      /* Implement replacement when another insert happens
-       * with a matching key.  This is a relatively common
-       * feature of hash tables, with the alternative
-       * generally being "insert the new value as well, and
-       * return it first when the key is searched for".
-       *
+      /* When another insert happens with a matching key,
+       * we check if there is a chain of matchin keys.
+       * If there is, we follow this chain until the end.
+       * We then do a linear probe until we find an empty spot.
+       * We insert the entry, and update the entry at our past
+       * matching key's position to point to the positon of
+       * the newly added data.
+       * 
        * Note that the hash table doesn't have a delete
        * callback.  If freeing of old data pointers is
        * required to avoid memory leaks, perform a search
@@ -331,8 +333,35 @@ 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;
+
+         /* Follow the chain of matching key's to the end */
+         while (old_entry->next_data != 0) {
+            entry = ht->table + old_entry->next_data;
+            /* We might have deleted the last entry, and have a
+             * dangling reference, so check that the keys match
+             * before we continue on traversing through the chain.
+             * If the key's don't match we undo our change of entry.
+             */
+            if (!ht->key_equals_function(key, entry->key)) {
+               entry = old_entry;
+               continue;
+            }
+            old_entry = entry;
+         }
+
+         /* Do a linear search for an empty spot in the table */
+         while (!entry_is_free(entry)) {
+            entry = ht->table + ((entry - ht->table + 1) % ht->size);
+         }
+
+         /* Now that we have an empty spot we add our data */
          entry->key = key;
          entry->data = data;
+         ht->entries++;
+
+         /* And update the matching key chain */
+         old_entry->next_data = entry - ht->table;
          return entry;
       }
 
-- 
2.11.0