Calling delete on an item that is not in the hash set will create an incorrect count

[stephengrice]

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.

[akashchgupta]

You are correct. That remains an issue to be solved.