From 38934921c4d6801ebdc13d32b4238c4a2ffa9c98 Mon Sep 17 00:00:00 2001 From: rofl0r Date: Sun, 14 Mar 2021 01:06:35 +0000 Subject: 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. --- src/hsearch.c | 26 ++++++++++++++------------ 1 file 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; -- cgit v1.2.3