0

I've managed to implement a trie data structure for speller, and it seems like there are no memory leaks, but when I run valgrind -v ./speller texts/lalaland.txt I get quite a lot of errors from context.

==5897== 
==5897== HEAP SUMMARY:
==5897==     in use at exit: 0 bytes in 0 blocks
==5897==   total heap usage: 367,084 allocs, 367,084 frees, 82,227,504 bytes allocated
==5897== 
==5897== All heap blocks were freed -- no leaks are possible
==5897== 
==5897== ERROR SUMMARY: 9913647 errors from 9 contexts (suppressed: 0 from 0)
==5897== 
==5897== 1 errors in context 1 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x422E91: load (dictionary2.c:104)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 216 errors in context 2 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422B80: check (dictionary2.c:73)
==5897==    by 0x421363: main (speller.c:112)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 221 errors in context 3 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 739 errors in context 4 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x4213E7: main (speller.c:119)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 739 errors in context 5 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x4213C0: main (speller.c:119)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 739 errors in context 6 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422DD5: check (dictionary2.c:83)
==5897==    by 0x421363: main (speller.c:112)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 9185 errors in context 7 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 367081 errors in context 8 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x423205: load (dictionary2.c:127)
==5897==    by 0x420992: main (speller.c:40)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x422E91: load (dictionary2.c:104)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 9534726 errors in context 9 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== ERROR SUMMARY: 9913647 errors from 9 contexts (suppressed: 0 from 0)

dictionary2.c :

// Implements a dictionary's functionality

#include "dictionary.h"

// Define node to be used in hashtable
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

// Define root
node *root;

// Global variable to track word count
unsigned int word_count = 0;

// Global boolean to track whether dictionary was loaded or not
bool loaded = false;

// Helper function to unload trie nodes
void unload_node(node *firstnode)
{

    for (int i = 0; i < 27; i++)
    {
        if (firstnode->children[i] != NULL)         // line 28
        {
            unload_node(firstnode->children[i]);    // line 30
        }
    }
    free(firstnode);
    return;
}


// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    // Copy the word as word only has read access
    int length = strlen(word);
    char word_copy[length + 1];

    // Lowercase the word
    for (int i = 0; i < length; i++)
    {
        word_copy[i] = tolower(word[i]);
    }

    // Nul terminate the string
    word_copy[length] = '\0';

    // Direct traversal pointer to root
    node *trav = root;

    for (int i = 0, n = strlen(word_copy); i < n; i++)
    {
        // Find numerical value of letter
        int alphanum;

        if (word_copy[i] == 39)
        {
            // If it is apostrophe, allocate last slot in array
            alphanum = 26;
        }
        else
        {
            alphanum = word_copy[i] - 97;
        }

        if (trav->children[alphanum] != NULL)       // line 73
        {
            trav = trav->children[alphanum];
        }
        else
        {
            return false;
        }
    }

    return trav->is_word;       // line 83
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO

    // Open dictionary file
    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        fclose(inptr);
        fprintf(stderr, "Could not open %s.\n", dictionary);
        return 2;
    }

    // Scan through every word in dictionary and store into new node
    char wordBuffer[LENGTH + 1];

    // Malloc root node
    root = (node*) malloc(sizeof(node));        // line 104

    while (fscanf(inptr, "%s", wordBuffer) != EOF)
    {
        // Create traversal pointer to the root
        node *trav = root;

        for (int i = 0, n = strlen(wordBuffer); i < n; i++)
        {
            // Find numeric value of letter
            int alphanum;

            if (wordBuffer[i] == 39)
            {
                // If it is apostrophe, allocate last space in children's array
                alphanum = 26;
            }
            else
            {
                alphanum = wordBuffer[i] - 97;
            }


            if (trav->children[alphanum] == NULL)       // line 127
            {

                // If node does not exist in array slot, allocate memory for new node
                trav->children[alphanum] = malloc(sizeof(node));        // line 131

            }

            // Redirect trav to child
            trav = trav->children[alphanum];

        }

        trav->is_word = true;

        word_count++;
    }

    fclose(inptr);
    loaded = true;

    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    node *trav = root;
    unload_node(trav);      // line 170
    return true;
}
1

Memory allocated using malloc can initially contain anything, you would have to give the individual fields of your newly allocated struct values yourself. It still works because fresh memory usually starts at all zeroes, but there's no guarantee that's the case for all systems.

You could use calloc instead of malloc, that one initialises the allocated memory to all zeroes, which means NULL for pointers and false for booleans.

You must log in to answer this question.

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