pset5 memory leak while using a Trie

Question

I have implemented the different functions of this pset and I use a trie datastructure. However I run into several problems when I run the program. The output seems to be correct, but check50 says for nearly all tests that it 'can't check until a frown turns upside down'. More seriously, when I use a bigger text like the austin powers file, the program leaks a lot of memory. When I use a small dictionary and a text file which has the same words as that dictionary, valgrind states that all memory has been freed. This difference in performance has confused me quite a bit. I think it might have to do with the way I have implemented storing the apostrophe character, but I am not sure what I have done wrong.

Anyway I would like some advice on how to solve these issues. When I run a bigger text I get this output from valgrind:

==1498== HEAP SUMMARY:
==1498==     in use at exit: 1,916,768 bytes in 8,557 blocks
==1498==   total heap usage: 367,084 allocs, 358,527 frees, 82,227,504 bytes allocated
==1498== 
==1498== LEAK SUMMARY:
==1498==    definitely lost: 1,870,848 bytes in 8,352 blocks
==1498==    indirectly lost: 45,920 bytes in 205 blocks
==1498==      possibly lost: 0 bytes in 0 blocks
==1498==    still reachable: 0 bytes in 0 blocks
==1498==         suppressed: 0 bytes in 0 blocks
==1498== Rerun with --leak-check=full to see details of leaked memory
==1498== 
==1498== For counts of detected and suppressed errors, rerun with: -v
==1498== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

I have implemented the load function in the following way:

FILE* dic = fopen(dictionary, "r");

    // give error message if the dictionary file is incorrect
    if (dic == NULL)
    {
        printf("could not open dictionary\n");
        return false;
    }

    // The calloc function assigns a block of memory
    // where all the individual parts are given the value NULL.
    root = calloc(1, sizeof(node));

    // checks the position of the letter in a word
    int letter_counter = 0;

    // check each char of the dictionary until the eof
    for (int c = fgetc(dic); c != EOF; c = fgetc(dic))
    {
        // check if its the first letter of a word
        if (letter_counter == 0)
        {
            // convert the letter to an alphabetic index value
            index = tolower(c) - 'a';

            // check if the index in the root node is NULL
            if (root -> children[index] == NULL)
            {
                // allocate memory for a new node and let root point at it
                root -> children[index] = calloc(1, sizeof(node));
            }

            // let tracker also point to the next node
            tracker = root -> children[index];

            // update letter_counter
            letter_counter++;
        }

        // check if the character is alphabetic or an apostrophe
        else if (isalpha(c) != 0 || c == 39)
        {
            // convert the letter to an (alphabetic) index value
            if (isalpha(c) != 0)
            {
                index = tolower(c) - 'a';
            }

            else
            {
                index = 26;
            }

            // check the index of the node at which tracker points
            if (tracker -> children[index] == NULL)
            {
                // allocate a new chunk of memory and let tracker point at it.
                tracker -> children[index] = calloc(1, sizeof(node));

                // update position of tracker
                tracker = tracker -> children[index];
            }

            else
            {
                // move tracker to the next node
                tracker = tracker -> children[index];
            }

            // update letter_counter
            letter_counter++;
        }

        else
        {
            // end of the word
            tracker -> is_word = true;

            // a new word will start after this, so letter counter goes to 0.
            letter_counter = 0;

            // word counter will be updated
            word_counter++;
        }
    }

    // close the dictionary and return true
    fclose(dic);
    return true;

The root and tracker pointers are globally defined as is the index integer. The unload function that I use is the following:

bool unload(void)
{
    // TODO
    // paste the root pointer in the helper function
    node_clearer(root);

    if (root == NULL);
    {
        return true;
    }

    return false;
}

// recursive helper function for unload
void node_clearer(node* curr_node)
{
    // this function iterates throught the nodes children
    for (int t = 0; t < 27; t++)
    {
        if (curr_node -> children[t] != NULL)
        {
            // if a node has a child, go to the child
            node_clearer(curr_node -> children[t]);
        }
    }

    // if a node has no children, we wil free it
    free(curr_node);
}

This pset has both really challenged and frustrated me, so I would dearly love to solve this. Anyway thanks in advance for the help.

Answer 1

I figured out what caused the memory leak. In the helper function of unload, I would free a node if it had no children, but I forgot to set the pointer that points to that node equal to NULL. I have corrected this and now the code works fine.