Unfixable memory leak
<p>I apologize for the long code snippet ahead, but I spent a good while looking on here and I feel like nothing I've seen so far can help me solve this. I've asked questions on course forums, had TAs help, and have gotten suggestions from friends and nothing has been able to lock down the root of my problem here.</p>

<p>In this program, I am using a tree to create a spell-checker. There are many things that need to be fixed in my code, but the memory leak is the only one I really need help figuring out.</p>

<p>The issue is that I am fairly sure I am allocating the correct amount of space for my nodes, and I think Valgrind confirms this, because I only have 2 not-freed blocks (out of 365,371 allocs).</p>

<p>Anyway, I will post the entirety of the code (in case anyone needs the full context), but the relevant parts I presume are the load function and the clear function, where I allocate and free the memory, respectively.</p>

<pre><code>/**
c* Implements a dictionary's functionality.
*/
#include &lt;ctype.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

#include "dictionary.h"

// number of characters we are using (a-z and ')
#define LETTERS 27

// max guaranteed number of nonnegative char values that exist
#define CHARVALUES 128

// create node structure for trie
typedef struct node
{
    struct node *children[LETTERS];
    bool is_word;
}
node;

// create root node for trie
node *root;

// stores the size of our dictionary
unsigned int dict_size = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // keeps track of where we are; starts with root for each new word
    node *current_node = root;

    while (*word != '\0')
    {

        // indices: 'a' -&gt; 0, ..., 'z' -&gt; 25, '\' -&gt; 26
        int index = (tolower(*word) - 'a') % CHARVALUES;
        if (index &gt;= LETTERS - 1)
        {
            // by assumption, the char must be '\'' if not '\n' or a letter
            index = LETTERS - 1;
        }

        // if the node we need to go to is NULL, the word is not here
        if (current_node-&gt;children[index] == NULL)
        {
            return false;
        }

        // go to the next logical node, and look at the next letter of the word
        current_node = current_node-&gt;children[index];
        word++;
    }
    return current_node-&gt;is_word;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{

    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        return false;
    }

    // allocate memory for the root node
    root = malloc(sizeof(node));

    // store first letter (by assumption, it must be a lowercase letter)
    char letter = fgetc(inptr);

    // stores indices corresponding to letters
    int index = 0;

    /**
     * we can assume that there is at least one word; we will execute the loop
     * and assign letter a new value at the end. at the end of each loop, due
     * to the inside loop, letter will be a newline; we know the EOF in the
     * dictionary follows a newline, so the loop will terminate appropriately
     */
    do
    {
        // keeps track of where we are; starts with root for each new word
        node *current_node = root; 

        // this loop will only execute if our character is a letter or '\''
        while (letter != '\n')
        {
            // indices: 'a' -&gt; 0, ..., 'z' -&gt; 25, '\' -&gt; 26
            index = (letter - 'a') % CHARVALUES;
            if (index &gt;= LETTERS - 1)
            {
                // by assumption, the char must be '\'' if not '\n' or a letter
                index = LETTERS - 1;
            }

            // allocate memory for a node if we have not done so already
            if (current_node-&gt;children[index] == NULL)
            {
                current_node-&gt;children[index] = malloc(sizeof(node));

                // if we cannot allocate the memory, unload and return false
                if (current_node-&gt;children[index] == NULL)
                {
                    unload();
                    return false;
                }

            }

            // go to the appropriate node for the next letter in our word
            current_node = current_node-&gt;children[index];

            // get the next letter
            letter = fgetc(inptr);
        }

        // after each linefeed, our current node represents a dictionary word
        current_node-&gt;is_word = true;
        dict_size++;

        // get the next letter
        letter = fgetc(inptr);
    }
    while (letter != EOF);

    fclose(inptr);

    // if we haven't returned false yet, then loading the trie must have worked
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    return dict_size;
}

void clear(node *head)
{
    for (int i = 0; i &lt; LETTERS; i++)
    {
        if (head-&gt;children[i] != NULL)
        {
            clear(head-&gt;children[i]);
        }
    }
    free(head);
}

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

<p>The relevant valgrind output is the following:</p>

<pre><code>==18981== HEAP SUMMARY:
==18981==     in use at exit: 448 bytes in 2 blocks
==18981==   total heap usage: 365,371 allocs, 365,369 frees, 81,843,792 bytes allocated
==18981== 
==18981== 448 (224 direct, 224 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011B0: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:40)
==18981== 
==18981== LEAK SUMMARY:
==18981==    definitely lost: 224 bytes in 1 blocks
==18981==    indirectly lost: 224 bytes in 1 blocks
==18981==      possibly lost: 0 bytes in 0 blocks
==18981==    still reachable: 0 bytes in 0 blocks
==18981==         suppressed: 0 bytes in 0 blocks
==18981== 1 errors in context 3 of 11:
==18981== 
==18981== 
==18981== Invalid read of size 8
==18981==    at 0x40120C: load (dictionary.c:123)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981== 
==18981== 
==18981== 1 errors in context 4 of 11:
==18981== Invalid read of size 8
==18981==    at 0x4011E0: load (dictionary.c:114)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981== 
==18981== 
==18981== 1 errors in context 5 of 11:
==18981== Invalid write of size 8
==18981==    at 0x4011D4: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981== 
==18981== 
==18981== 1 errors in context 6 of 11:
==18981== Invalid read of size 8
==18981==    at 0x4011B2: load (dictionary.c:109)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
</code></pre>

<p>So, my interpretation of this output is that, in the following block of code:</p>

<pre><code>        if (current_node-&gt;children[index] == NULL)
        {
            current_node-&gt;children[index] = malloc(sizeof(node));

            // if we cannot allocate the memory, unload and return false
            if (current_node-&gt;children[index] == NULL)
            {
                unload();
                return false;
            }

        }
</code></pre>

<p>the <code>malloc</code> statement (which is indeed line dictionary.c:111) is executed twice such that the allocated memory is never freed. (Is this correct?) Now, that leads me to think that the real problem lies with my clear function, i.e. that it is written poorly and does not clear every node of my trie.</p>

<p>However, I've stared at the code for hours and I literally cannot see anything wrong with it. (I'm sure a lot is; I'm just not too good at this.)</p>

<p>Any help with this would be greatly appreciated.</p>

<p>As a sidenote: I've had multiple people (not course staff) tell me that I should initialize all of my pointers in the children array to NULL, but the course staff outright told me this was optional, and I have already tested it both ways with the same results. I know it's probably a portability thing even if it technically "works" like that, but just know that that is <em>not</em> the solution I am looking for, as I know there is some other root cause (i.e. one that causes it to not work on any device at all whatsoever...)</p>

<p>Again, if you can help in any way with what is wrong with my logic here, I would greatly appreciate it. I have been trying to figure this out for hours to no avail.</p>