pset5. Can't trace memory leak

Question

Load function (with a trie data structure)

//DEBUG
unsigned int allocs = 0;

// define node and create root
typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

node* root;

// create crawler
node* crawler;

// initialize words counter
unsigned int words = 0;


/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // open dictionary for reading
    FILE* fptr = fopen(dictionary, "r");
    if (fptr == NULL)
    {
        printf("Couldn't open dictionary %s\n.", dictionary);
        return false;
    }

// initialize root
root = calloc(1, sizeof(node));

//DEBUG
allocs++;

// initialize crawler
crawler = root;

char buffer; 
int index;
while(fread(&buffer, 1, 1, fptr) == 1)
{
    if (isalpha(buffer))
    {
        index = ((int) buffer) - 97;
    }
    else if (((int) buffer) == NEWLINE)
    {
        index = -1;
    }
    else
    {
        index = 26;
    }

    if (index >= 0)
    {
        // if node doesn't exist create one
        if (crawler->children[index] == NULL)
        {
            crawler->children[index] = calloc(1, sizeof(node));

            //DEBUG
            allocs++;

            crawler = crawler->children[index];
        }

        // in node exists move to it
        else
        {
            crawler = crawler->children[index];
        }
    }
    else
    {
        words++;
        crawler->is_word = true;
        crawler = root;
    }


}
crawler = root;

// close dictionary file
fclose(fptr);

//DEBUG
printf("DEBUG: MEMORY WAS ALLOCATED  %i  TIMES\n", allocs);

return true;
}

Unload function

// prototype
void loop(void);

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */

bool unload(void)
{
    crawler = root;

    // frees all nodes except root
    loop();

    // frees root
    free(crawler);

    // return true and quit
    return true;
}

void loop(void)
{
    // initialize backtrack variable and index variable
    node* track = crawler;

    for (int i = 0; i < 26; i++)
    {
        if (crawler->children[i] != NULL)
        {
            // move to the next node
            crawler = crawler->children[i];

            loop();

            free(crawler);
            crawler = track;
        }
    }
}

With this dictionary

aardvark's
aardvarks
exegetics
trumps
truncate
kappa
ross

and this text

truncate exegetics aardvarks keepo ross 

I get this output

==9053== Memcheck, a memory error detector
==9053== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==9053== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==9053== Command: ./speller DEBUG/dictionary DEBUG/text.txt
==9053== 
DEBUG: MEMORY WAS ALLOCATED  41  TIMES

[program output without any invalid read or write errors]

==9053== HEAP SUMMARY:
==9053==     in use at exit: 448 bytes in 2 blocks
==9053==   total heap usage: 43 allocs, 41 frees, 10,320 bytes allocated
==9053== 
==9053== 448 (224 direct, 224 indirect) bytes in 1 blocks are definitely     lost in loss record 2 of 2
==9053==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9053==    by 0x40120E: load (dictionary.c:84)
==9053==    by 0x40095D: main (speller.c:45)
==9053== 
==9053== LEAK SUMMARY:
==9053==    definitely lost: 224 bytes in 1 blocks
==9053==    indirectly lost: 224 bytes in 1 blocks
==9053==      possibly lost: 0 bytes in 0 blocks
==9053==    still reachable: 0 bytes in 0 blocks
==9053==         suppressed: 0 bytes in 0 blocks
==9053== 
==9053== For counts of detected and suppressed errors, rerun with: -v
==9053== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

My allocs variable says that memory was allocated 41 times, but valgrind says that there were 43 allocs. I can't figure out why.

Full code is here: https://gist.github.com/FraySnap/de9a25414ad43388e6f37dceae23d3d2

Answer 1

Prepare to slap head with hand!

If you were to run valgrind with the full dictionary and a large file, you'd probably see thousands of blocks lost. So, given this declaration,

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

... what's wrong with this code?

void loop(void)
{
    ...

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

Hopefully, you didn't leave a bruise. ;-)

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

Answer 2

Function fopen() allocate memory for itself. Try without fclose(). You'll get leak of memory. You opened dictionary file and speller opened text file. So amount of memory will be = amount of nodes + amount of fopen() functions.