Description
Hi, this is a great tutorial. Thank you so much for writing it. I went from knowing almost nothing about implementing a hash table to feeling like I could do it myself.
I did notice one issue, though I could be wrong. Here is your delete method:
// hash_table.c
static ht_item HT_DELETED_ITEM = {NULL, NULL};
void ht_delete(ht_hash_table* ht, const char* key) {
int index = ht_get_hash(key, ht->size, 0);
ht_item* item = ht->items[index];
int i = 1;
while (item != NULL) {
if (item != &HT_DELETED_ITEM) {
if (strcmp(item->key, key) == 0) {
ht_del_item(item);
ht->items[index] = &HT_DELETED_ITEM;
}
}
index = ht_get_hash(key, ht->size, i);
item = ht->items[index];
i++;
}
ht->count--;
}
Notice that ht->count--; is at the bottom, whereas the item detection/deletion occurs under the condition with strcmp. So, if you call ht_delete on a hash table that does not contain the key you are calling on, ht->count will be decremented whether the item is found or not. As a result, the count will be wrong in this case.
I think simply moving the ht->count--; line up into the delete condition would fix the issue. Like this:
void ht_delete(ht_hash_table* ht, const char* key) {
int index = ht_get_hash(key, ht->size, 0);
ht_item* item = ht->items[index];
int i = 1;
while (item != NULL) {
if (item != &HT_DELETED_ITEM) {
if (strcmp(item->key, key) == 0) {
ht_del_item(item);
ht->items[index] = &HT_DELETED_ITEM;
ht->count--; // <-------------------------------- moved to here
return; // edit: found this from mbrlabs's code
}
}
index = ht_get_hash(key, ht->size, i);
item = ht->items[index];
i++;
}
}
I could be wrong. I just wanted to put this in there for someone to look at. Let me know what you think! :)
Edit: It seems the pull request #20 by @mbrlabs already addresses this.