segfault while freeing memory in speller

Question

I'm having an enormous problem implementing the unload function for the speller in pset6. Although it's not a well-polished algorithm I first wanted to make a quick design that allows me to take a glance at the important factors of this pset, but I couldn't even finish that!

The problem I'm having is impossible to explain without posting the code so here it goes

// iterate to release dictionary
for (int i = 'a'; i <= 'z'; i++)
{
    words* current = &first[i-'a'];
    while (current != NULL)
    {
        words* temp = current;
        free (current);
        current = temp -> next;
    }
}

I've used a simply defined hash table with 26 entries (one for each letter). The table it's called first. For the dictionary I've used a struct called words which includes a char* with no size defined and a struct word* called next. As you may see here

typedef struct words
{
    char* word;
    struct words* next;
}
words;

words first[26];

The traversing is the same one I used in earlier stages to print the entire list and it worked. The only changes are introducing that temp pointer and assigning to it later to current and of course the free step, that's where the segmentation fault occurs.

Using GDB I was able to see the segfaults occurs in the first iteration for the first letter, so it's not a matter of size. I printed the values of temp and current at the moment of the crash and both are memory addresses leading to words.

I'm also having some bizarre problems deallocating iteration-life-only char* buffers, but I thought better to ask about unloading first because I want to see a working version of the speller in order to keep it going and improve it.

Answer 1

You have to keep in mind that a node is only accessible through a previous node when dealing with a singly-linked-list.

Also, since you've allocated memory separately for the string named word which is a member of struct words, you also have to free that separately "before" freeing the data associated with the pointer to the struct that contains this word or you'll lose access to it and never be able to free it.

Another problem is that when you free data that's pointed to by one or more pointers using one of these pointers, all the other pointers become pointing to nothing because the data itself was already freed from memory. And that's what causes the segmentation fault — you're creating another pointer namely temp to point to the same location in memory as current, you're "freeing the memory pointed to by current which is the same memory pointed to by temp", then you're trying to reach temp->next which of course leads to a segfault since the memory pointed to by temp was just freed using current.

To fix that you probably should traverse to the end of the list and start freeing it backwards (i.e., from the last node to the starting node) keeping in mind that, given current as a pointer to a struct words, you should free current->word (if it's not freed already) before you free current itself as I mentioned earlier.