0

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;


}
1
  • But hey, congrats on fixing your error. I appreciate that you'd like to know why certain code works instead of moving on as soon as you get it working (like I do, sometimes!). – Edward Lee Dec 16 '17 at 22:02
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. :-)

1
  • 1
    Looping and recursion are two different things. Tim is using both techniques, loops and recursive calls of the clear function. To be explicitly clear, the vars in each recursive call are completely independent from one another. Changing the value of a var, like index for example, in one recursion will not change the value of the var of the same name in the parent, child, or any other recursive call. They're totally unrelated. Also, the scope of these vars within the loops had no issue here. In the while loop, index wasn't being "reset" to 0, it simply wasn't being incremented. See my answer. – Cliff B Dec 16 '17 at 22:50
1

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. ;-)

0

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .