CS50 pset5 Memory Leak (trie structure)

Question

So I've written the functions for pset5 using a trie and it seems to work fine. It gives the same number of misspelled words etc. as the cs50 one, but it seems that there are some memory leak problems.

Here's the valgrind output for loading the whole library.

==8099==
==8099== HEAP SUMMARY:
==8099==     in use at exit: 3,865,120 bytes in 17,255 blocks
==8099==   total heap usage: 367,084 allocs, 349,829 frees, 82,227,504 bytes allocated
==8099== 
==8099== 3,865,120 (1,914,304 direct, 1,950,816 indirect) bytes in 8,546 blocks are definitely lost in loss record 2 of 2
==8099==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8099==    by 0x4012C2: load (dictionary.c:104)
==8099==    by 0x40090D: main (speller.c:45)
==8099== 
==8099== LEAK SUMMARY:
==8099==    definitely lost: 1,914,304 bytes in 8,546 blocks
==8099==    indirectly lost: 1,950,816 bytes in 8,709 blocks
==8099==      possibly lost: 0 bytes in 0 blocks
==8099==    still reachable: 0 bytes in 0 blocks
==8099==         suppressed: 0 bytes in 0 blocks
==8099== 
==8099== For counts of detected and suppressed errors, rerun with: -v
==8099== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

It seems like I haven't freed all the memory allocated and the problem looks like it's coming from my load function?

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // try to open file
    FILE* fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        return false;  // unable to open dictionary -> return false
    }

    // initialise root node, calloc sets the pointers to NULL
    root = calloc(1, sizeof(node));

    // prepare to load words into dictionary
    node* crawler = root;
    int index = 0, c_index;

    // go through each character in the dictionary
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            if (c == '\'')
            {
                c_index = 26;
            }
            else
            {
                c_index = c - 'a';// get the relative position of the letter
            }

            if (crawler->children[c_index] == NULL)       // if there is no trie, make space
            {
                crawler->children[c_index] = calloc(1, sizeof(node));
            }
            crawler = crawler->children[c_index];     // move to the next trie
            index++;
        }
        // we must have found a whole word
        else if (index > 0)
        {
            // finish word, make boolean true and go back to top
            crawler->is_word = true;
            crawler = root;
            words_loaded++;
            index = 0;      // reset to start looking for new words
        }
    }
    fclose(fp);
    return true;
}

The line in question (104 according to valgrind) is:

crawler->children[c_index] = calloc(1, sizeof(node));

So I assume there's something going wrong with the memory allocation, like perhaps my code not freeing the memory in the unload function or elsewhere.

// clearing function to use in unloading.
void clear(node* node)
{
    for (int i = 0; i < 26; i++)
    {
        if (node->children[i] != NULL)
        {
         clear(node->children[i]);
         node->children[i] = NULL;
        }
    }
    free(node);
    return;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    clear(root);
    return true;
}

There are parts of the code I was unsure of, like the setting of node->children[i] = NULL; in the recursive function, I'm not sure if it's necessary or if it even does anything?

I ran the code with the small dictionary and it ends up running without any leaks, but adding words to the dictionary causes more and more leaks to pop up it seems. Any help as to where I may be going wrong?

Thanks

Answer 1

for (int i = 0; i < 26; i++)

You have 27 elements (a-z and '), so <=26 or <27 would be appropriate.