Segmentation error on PSET5 unload function

Question

I'm working on the unload function for pset5 - speller and ran into segmentation errors with the first clear function below (dictionary.c unload function calls the recursive function clear). I changed the code to the second clear function below, converting the while loop to a for loop and the error went away, but I don't understand why. Can anyone take a look and tell me why the errors occurred with the first block?

I pasted my full dictionary.c code below the two clear functions if you need it.

First clear function

bool clear(node* cursor)
{
    int index = 0;
    while (index < 27)
    {
        if(cursor->children[index])
        {
            clear(cursor->children[index]);

        }
        else
        {
            index++;
        }
    }
    free(cursor);

    return true;


}

Second clear function

bool clear(node* cursor)
{
    for (int index = 0; index < 27; index++)
    {
        if(cursor->children[index])
        {
            clear(cursor->children[index]);

        }

     }
    free(cursor);

    return true;


}

Answer 1

I believe what went wrong in your first clear function was an issue of scope. In your first function, you declared index outside of your while loop, so when the recursion kicks in, the loop increments that same index variable, instead of setting it back at 0.

for loops work differently in that it will take care of that "resetting to 0" when it's used recursively. That way, when you're clearing your trie, no child gets left behind. :-)

Answer 2

The problem was the else statement. Using a while loop was fine, but the implementation was faulty.

Think about what happens because the index++ was put in an else clause. When the code executes, if the IF test is true, that code block will execute, not the else clause. So, on the next execution of the while loop, index has not been incremented. The code will try to execute the IF test, but since cursor->children[index] no longer exists, it will cause a seg fault.

To avoid this, index must be incremented on each pass no matter what. Drop the else clause and it should work.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

Answer 3

The problem is that your function frees the nodes but this doesn't set them to NULL. This means if the nodes has childrens it frees the children returns and tries to free the children again. But in your for loop you don't have the conditional increment, so it increments every iteration and doesn't access a freed node.