0

I'm trying to implement a hash table in C. I'm using open addressing/linear probing to resolve collisions, so that if the program tries to create a new entry and the key hashes to a slot which is already in use, the entry will occupy the next available slot. I finally got my search and insert functions to stop segfaulting, but my delete function doesn't correctly delete hash table entries and I'm not sure why.

My hash table is implemented as an array of pointers to Item structures. The Item structure contains a key string and a data value (just an int for now.) My delete function calls free() on the pointer to the item it needs to delete and sets that value in the array to NULL. However, the function seems to only delete the key string from the Item structure. Subsequent calls to ht_search() with the same key yield NULL as expected, but a pointer to the item pre-deletion still allows the program to access the item's value. I'm not sure why this is and can't figure it out.

Relevant parts of my code: (Let me know if I should include additional functions like ht_insert() and ht_search() in my example.)

#define HASHTABLE_SIZE 1000
#define KEY_SIZE       64

typedef struct {
    char key[KEY_SIZE];
    int value;
} Item;

Item *hashtable[HASHTABLE_SIZE];

unsigned int
ht_hash(const char *key)
{
    unsigned int sum = 0;

    for (; *key; ++key) {
        sum = sum * 101 + *key;
    }

    sum %= HASHTABLE_SIZE;

    return sum;
}

Item
*ht_delete(const char *key)
{
    unsigned int hash = ht_hash(key);
    unsigned int i = hash;

    for (;; ++i) {
        i %= HASHTABLE_SIZE;

        if (hashtable[i] && !strcmp(key, hashtable[i]->key))
            break;
        if (i == hash)
            return -1;
    }

    free(hashtable[i]);
    hashtable[i] = NULL;

    return hashtable[i];
}

int
main(void)
{
    Item *sel;
    char *s = "foobar";
    int data = 12345;

    /* everything is fine so far */
    sel = ht_insert(s, data);

    /* this sets the 'key' field in sel to an empty string,
     * but the value field is still accessible? */
    ht_delete(s);

    /* sel becomes null */
    sel = ht_search(s);

    return 0;
}

Does anyone know why ht_delete doesn't fully delete the Item structure? What's going on?

  • What do you mean exactly by "the value field is still accessible" ? Can you put some code that do not work in the expected way ? – Joël Hecht Jan 07 '22 at 06:25
  • @JoëlHecht In the main function, I declare sel as a pointer to an item structure and point it to a hash table entry using ht_insert (ht_insert returns a pointer to the item it inserts into the hash table.) After calling ht_delete on sel, it doesn't fully delete the structure that sel points to. The 'key' field of the Item struct becomes an empty string, but the 'value' field remains available. Sorry if this explanation doesn't make any sense –  Jan 07 '22 at 06:59
  • Do I understand correctly that you expect `int* p=malloc(sizeof(int)); *p=5; free(p); int a=*p;` to somehow fail in a reliable, reproducable way? I.e. that somehow `a` does not end up being 5? – Yunnosch Jan 07 '22 at 07:03
  • @Yunnosch I thought `free`ing the struct would delete its contents - trying to access the value field after the struct was `free`d would be like dereferencing a null pointer or something. I guess I'll have to do more research on these functions. –  Jan 07 '22 at 09:36
  • "I thought freeing the struct would delete its contents" Keep that thought. It makes you program correctly, i.e. not access it. But actually it is wrong, nothing is deleted. What really happens in much worse: At some point the memory is used by other mallocs. Which is why it is so horribly dangerous to access after free. I think there should be duplicates on StackOverflow for "Why can I still read after free()?". Maybe somebody finds one. If you want to determine whether malloced memory has been freed then I am afraid your approach is wrong. You need to know yourself. – Yunnosch Jan 07 '22 at 11:19
  • Does this answer your question? [Using pointer after free()](https://stackoverflow.com/questions/15432123/using-pointer-after-free) – Yunnosch Jan 07 '22 at 11:23
  • In the duplicate I propose, read more than one answer to get the info/understanding you want. – Yunnosch Jan 07 '22 at 11:24
  • @Yunnosch the duplicate cleared some stuff up. I also read that free() doesn't actually clear the memory, it just releases it back to the operating system. While I don't get why the OS lets us access relinquished memory, it makes sense why the memory location would still have usable data. I also don't get why free'ing the struct sets the value of the key field to NULL. I will have to do more testing. Also, if I call free on one of the pointers in the array and set that array element to NULL, is it safe to store a malloc'd pointer in that same place later? –  Jan 07 '22 at 21:51

0 Answers0