htab_delete(): fix failure to set tombstone

we can't just set an item's key to zero and be done with a deletion,
because this will break the item search chain.
a deleted item requires a special marker, also known as tombstone.
when searching for an item, all slots with a tombstone need to treated
as if they were in use, but when inserting an item such a slot needs
to be filled with the new item.

a common procedure is to rehash the table when the number of deleted
items crosses a certain threshold, though for simplicity we leave this
task to the resize() function which does the same thing anyway when
the hashtable grows.

this allows to fix the issue quite elegantly and with almost no
additional overhead, so we don't penalize applications that do very
few deletions.

1 files changed, 14 insertions, 12 deletions

diff --git a/src/hsearch.c b/src/hsearch.c
index 0cc4aca..d8d395a 100644
--- a/src/hsearch.c
+++ b/src/hsearch.c
@@ -107,14 +107,14 @@ static int resize(struct htab *htab, size_t nel)
 	return 1;
 }
 
-static struct elem *lookup(struct htab *htab, const char *key, size_t hash)
+static struct elem *lookup(struct htab *htab, const char *key, size_t hash, size_t dead)
 {
 	size_t i, j;
 	struct elem *e;
 
 	for (i=hash,j=1; ; i+=j++) {
 		e = htab->elems + (i & htab->mask);
-		if (!e->item.key ||
+		if ((!e->item.key && (!e->hash || e->hash == dead)) ||
 		    (e->hash==hash && STRCMP(e->item.key, key)==0))
 			break;
 	}
@@ -138,36 +138,38 @@ void htab_destroy(struct htab *htab)
 	free(htab);
 }
 
-static htab_entry *htab_find_item(struct htab *htab, const char* key)
+static struct elem *htab_find_elem(struct htab *htab, const char* key)
 {
 	size_t hash = keyhash(key, htab->seed);
-	struct elem *e = lookup(htab, key, hash);
+	struct elem *e = lookup(htab, key, hash, 0);
 
 	if (e->item.key) {
-		return &e->item;
+		return e;
 	}
 	return 0;
 }
 
 htab_value* htab_find(struct htab *htab, const char* key)
 {
-	htab_entry *i = htab_find_item(htab, key);
-	if(i) return &i->data;
-	return 0;
+	struct elem *e = htab_find_elem(htab, key);
+	if(!e) return 0;
+	return &e->item.data;
 }
 
 int htab_delete(struct htab *htab, const char* key)
 {
-	htab_entry *i = htab_find_item(htab, key);
-	if(!i) return 0;
-	i->key = 0;
+	struct elem *e = htab_find_elem(htab, key);
+	if(!e) return 0;
+	e->item.key = 0;
+	e->hash = 0xdeadc0de;
+	--htab->used;
 	return 1;
 }
 
 int htab_insert(struct htab *htab, char* key, htab_value value)
 {
 	size_t hash = keyhash(key, htab->seed);
-	struct elem *e = lookup(htab, key, hash);
+	struct elem *e = lookup(htab, key, hash, 0xdeadc0de);
 	if(e->item.key) {
 		/* it's not allowed to overwrite existing data */
 		return 0;