1

* Error in `/home/jharvard/Dropbox/pset5/speller': double free or corruption (top): 0x0804c698 *

If I set unload to always return true, load/check work perfectly. Valgrind gives me a lot of invalid read and free errors stemming from my helper function, but I don't understand why it's broken.

Valgrind: http://pastebin.com/GdY1XHSY

4

It's a subtle error. The problem lies in your helper code. Look at the following:

for (int i = 0; i < 27; i++)
{
    if (curs->children[i] != NULL)
    {
        curs = curs->children[i];
        helper(curs);           
    }
}

The reassignment curs = curs->children[i]; is disrupting what you were trying to accomplish. For simplicity, let's assume that there are no nulls in the first 3 levels. On the first pass, when i=0, curs = root, but gets reassigned to root->children[0]. When teh recursion comes back to the top level, instead of processing root[1], it will process root[0]->children[1]. The third pass (i=2) will process root[0]->children[1]->children[2], and so on, until it has nothing left to process.

The point is that when you return from the recursive call, you will not continue to process the same level in the trie, but will be one level further down the trie because of the reassignment. The remainder of the previous level will never get processed. Also, after each call to helper completes the for loop, it will process the final free(curs) and will lose any nodes that were skipped or orphaned.

This is easily fixed by not doing the reassignment. Instead, just call helpers on the actual child. You can also deal with your return issue here. You'll have to add/restore the code to determine a fail, but the return will handle passing the bool true/false back to the top.

`return helpers(curs->children[i]);`

You might also find my answer on recursion at the following link helpful:

Pset3 Binary Search problems

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

1
  • Errors like this are so hard to understand what is actually going on in the code. How can you know which 'level' of code will be processed first? I understand the solution, it's just hard to understand how to avoid this problem in the first place.
    – borker
    Oct 24 '16 at 18:25

You must log in to answer this question.

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