0

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);
}
4
  • Please do not free any children directly (they should be freed by the recursively called function), and please do not assign to any parameters. You might remember my opinion from cs50.stackexchange.com/a/30728/12099 ;-) – Blauelf Dec 10 '18 at 13:31
  • Yeah, i remember it, I was thinking about the problem whole day yesterday without success. I totally forgot about the assigning to parameters part (i don't know why it is bad, i will google it now :)) – 11223342124 Dec 10 '18 at 13:43
  • Can you tell me why children pointers shouldn't be freed directly (if they are NULL)? – 11223342124 Dec 10 '18 at 13:51
  • Assigning to parameters is bad in case you need them later. Which you do at least in some case. Also, it's bad style, reducing readability. And you can't free NULL. What do you think should happen then? You never allocated a memory block at NULL, so what should be freed? (free(NULL) will just do nothing) – Blauelf Dec 10 '18 at 15:31
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. ;-)

2
  • Would be free_node(nodeArg->children[i], 0) :P (otherwise agree, as I pointed out potentially working pseudocode in my earlier answer) – Blauelf Dec 10 '18 at 17:16
  • I used for loop and solved the issue. Unload was really tough for me, don't know why :) Rest of the requirements for this PSET were much easier. Thank you guys for your help! – 11223342124 Dec 11 '18 at 20:37

You must log in to answer this question.

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