Do a full search when adding new items

Previously, the hash_table_insert or set_add functions 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.

v2: Fold in Connor Abbot's fix to not check keys in deleted entries.
v3: Propagate this change to int-set, too (change by anholt).

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

3 files changed, 47 insertions, 19 deletions

diff --git a/hash_table.c b/hash_table.c
index 1d0de75..8390472 100644
--- a/hash_table.c
+++ b/hash_table.c
@@ -258,6 +258,7 @@ hash_table_insert_pre_hashed(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) {
 		hash_table_rehash(ht, ht->size_index + 1);
@@ -272,13 +273,11 @@ hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
 		uint32_t double_hash;
 
 		if (!entry_is_present(entry)) {
-			if (entry_is_deleted(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
@@ -292,7 +291,8 @@ hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
 		 * required to avoid memory leaks, perform a search
 		 * before inserting.
 		 */
-		if (entry->hash == hash &&
+		if (!entry_is_deleted(entry) &&
+		    entry->hash == hash &&
 		    ht->key_equals_function(key, entry->key)) {
 			entry->key = key;
 			entry->data = data;
@@ -305,6 +305,16 @@ hash_table_insert_pre_hashed(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(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.
 	 */
diff --git a/int-set.c b/int-set.c
index 76f8c87..f9d5246 100644
--- a/int-set.c
+++ b/int-set.c
@@ -224,6 +224,7 @@ struct int_set_entry *
 int_set_add(struct int_set *set, uint32_t value)
 {
 	uint32_t hash_address;
+	struct int_set_entry *available_entry = NULL;
 
 	if (set->entries >= set->max_entries) {
 		int_set_rehash(set, set->size_index + 1);
@@ -237,14 +238,14 @@ int_set_add(struct int_set *set, uint32_t value)
 		uint32_t double_hash;
 
 		if (!entry_is_present(entry)) {
+			if (available_entry == NULL)
+				available_entry = entry;
+			if (entry_is_free(entry))
+				break;
 			if (entry_is_deleted(entry)) {
 				set->deleted_entries--;
 				entry->deleted = 0;
 			}
-			entry->value = value;
-			entry->occupied = 1;
-			set->entries++;
-			return entry;
 		}
 
 		if (entry->value == value) {
@@ -256,6 +257,13 @@ int_set_add(struct int_set *set, uint32_t value)
 		hash_address = (hash_address + double_hash) % set->size;
 	} while (hash_address != value % set->size);
 
+	if (available_entry) {
+		available_entry->value = value;
+		available_entry->occupied = 1;
+		set->entries++;
+		return available_entry;
+	}
+
 	/* We could hit here if a required resize failed. An unchecked-malloc
 	 * application could ignore this result.
 	 */
diff --git a/set.c b/set.c
index d81807f..5033892 100644
--- a/set.c
+++ b/set.c
@@ -272,6 +272,7 @@ struct set_entry *
 set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
 {
 	uint32_t hash_address;
+	struct set_entry *available_entry = NULL;
 
 	if (set->entries >= set->max_entries) {
 		set_rehash(set, set->size_index + 1);
@@ -285,12 +286,11 @@ set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
 		uint32_t double_hash;
 
 		if (!entry_is_present(entry)) {
-			if (entry_is_deleted(entry))
-				set->deleted_entries--;
-			entry->hash = hash;
-			entry->key = key;
-			set->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
@@ -303,7 +303,8 @@ set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
 		 * If freeing of old keys is required to avoid memory leaks,
 		 * perform a search before inserting.
 		 */
-		if (entry->hash == hash &&
+		if (!entry_is_deleted(entry) &&
+		    entry->hash == hash &&
 		    set->key_equals_function(key, entry->key)) {
 			entry->key = key;
 			return entry;
@@ -314,6 +315,15 @@ set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
 		hash_address = (hash_address + double_hash) % set->size;
 	} while (hash_address != hash % set->size);
 
+	if (available_entry) {
+		if (entry_is_deleted(available_entry))
+			set->deleted_entries--;
+		available_entry->hash = hash;
+		available_entry->key = key;
+		set->entries++;
+		return available_entry;
+	}
+
 	/* We could hit here if a required resize failed. An unchecked-malloc
 	 * application could ignore this result.
 	 */