Memory leaks on unload

Question

All tests pass except the valgrind check at the end. I am sure that my unload algorithm isn't correct, but I checked like 5 times, and I can't find logic flaw.

I don't need solution, just a hint what I am doing wrong.

Here is the output of the valgrind (line 65 is line where memory is allocated using calloc):

224 bytes in 1 blocks are still reachable in loss record 1 of 11: (file: dictionary.c, line: 96) 
224 bytes in 1 blocks are still reachable in loss record 2 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 3 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 4 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 5 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 6 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 7 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 8 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 9 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 10 of 11: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 11 of 11: (file: dictionary.c, line: 65) 

Here is the pseudo code:

- call free_node function with node_pointer (node) and incrementer variable (i)
    - if node->children[i] is not NULL, go vertically to lower branch
        - node_pointer = node.children[i] 
        - set increment variable to 0 (because we want to start at the 0th node of horizontal level)
        - call free_node function with newly set node_pointer and i
    - else go horizontally
        - free node->children[i]
        - increment i by one
        - if i is less than number of elements in node.child array (27)
            - call function with node_pointer and i
        - else
            - free node

My intention is to go to the lowest possible node until I hit node with NULL pointers in children array. Then I start going horizontally while node pointers are NULL and I free them. If I encounter not NULL pointer, I go to lower branch and repeat the process.

Here is actual code:

bool free_node(node *nodeArg, int i)
{
    if (nodeArg->children[i] != NULL)
    {
        // traverse vertically
        nodeArg = nodeArg->children[i];
        i = 0;
        free_node(nodeArg, i);
    }
    else
    {
        // traverse horizontally
        free(nodeArg->children[i]);
        i++;

        if (i < 27)
            free_node(nodeArg, i);
        else
           free(nodeArg);
    }
    return true;
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    int i = 0;
    return free_node(ROOT, i);
}

Answer 1

There are several issues, some have been mentioned in comments.

As mentioned, when recursively calling, don't reassign the child to the current node. Call the child directly instead. free_node(nodeArg->children[i], i); When nodeArg is reassigned as it is in the original code, it causes a big problem. Say that it's working on "parent[3]". The reassignment changes the current pointer in the current recursion to "parent[3]->child[0]". When the recursion returns, and the code needs to move to "parent[4]", it will instead still be at the child's level and will instead move to "parent[3]->child[1]". It will be 1 level lower in the tree than it should be and all of the siblings of parent[3] that follow would be skipped.

But that problem is somewhat moot. Because the code uses an if/else construct instead of a for loop to cycle through all of the siblings, only one node at each level will be processed. After the first pass through the if/else construct, it hits a return statement and stops. There's no mechanism to process any further.

You might also find this useful: http://cs50.stackexchange.com/questions/9691/pset3-binary-search-problems/9694#9694

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