Memory leaks in Speller

Question

My program passes all tests except the valgrind check. I tried to find the cause of errors, but valgrind is too 'obscure' for me yet, I don't know what to do.

I guess some memory isn't freed, but I think my algorithm is correct? Bellow is pseudo code attached.

Here is the output of valgrind (line numbers can be seen in code):

Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 62) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 42) 
Conditional jump or move depends on uninitialised value(s): (file: speller.c, line: 100) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 29) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 129) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 139) 
224 bytes in 1 blocks are still reachable in loss record 1 of 12: (file: dictionary.c, line: 96) 
224 bytes in 1 blocks are still reachable in loss record 2 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 3 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 4 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 5 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 6 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 7 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 8 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 9 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 10 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 11 of 12: (file: dictionary.c, line: 65) 
224 bytes in 1 blocks are still reachable in loss record 12 of 12: (file: dictionary.c, line: 65) 

LEAK SUMMARY:
definitely lost: 0 bytes in 0 blocks
indirectly lost: 0 bytes in 0 blocks
possibly lost: 0 bytes in 0 blocks
still reachable: 82,223,232 bytes in 367,068 blocks
suppressed: 0 bytes in 0 blocks

Here is pseudo-code for unload functionallity:

- call free_node function with node_pointer (node) and incrementer variable (i)
    - if node->children[i] is not NULL, go vertically to lower branch
        - node_pointer = node.children[i] 
        - set increment variable to 0 (because we want to start at the 0th node of horizontal level)
        - call free_node function with node_pointer and i
    - else go horizontally
        - free node->children[i]
        - increment i by one
        - if i is less than number of letters in the alphabet (26)
            - call function with node_pointer and i

Here is the whole program:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <ctype.h>
#include <cs50.h>
#include "dictionary.h"

// returns character index in the alphabet
int getPosition(char c)
{
    if (c >= 'a' && c <= 'z')
        return c - 'a';
    else if (c >= 'A' && c <= 'Z')
        return c - 'A';
    else if (c == '\'')
        return 26;
    else
        return -1;
}

// ###
// CHECK

bool traverse(struct node *nodeArg, const char *word, int i)
{
    int charAlphaIndex = getPosition(word[i]);
    // if current character doesn't exist in the trie, return false
    if (nodeArg->children[charAlphaIndex] == NULL) // line 29 ###
        return false;

    node *subNode = nodeArg->children[charAlphaIndex];

    // calls function recurivelly until the last character in word
    i++;
    if (isalpha(word[i]) || word[i] == '\'')
    {
        return traverse(subNode, word, i);
    };

    // returns true or false depending if the word has been found
    return subNode->is_word; // line 42
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int i = 0;
    return traverse(ROOT, word, i);
}

// ###
// LOAD

bool insert(int i, char *word, struct node *nodeArg)
{
    int charAlphaIndex = getPosition(word[i]);

    if (isalpha(word[i]) || word[i] == '\'') //refactor to ASCII range
    {
        node *subNode = nodeArg->children[charAlphaIndex];
        if (subNode == NULL) // line 62
        {
            // malloc error handling
            subNode = malloc(NODE_SIZE); // line 65
            if (subNode == NULL)
                return false;

            nodeArg->children[charAlphaIndex] = subNode;
        }
        i++;
        if (word[i] == '\n' || word[i] == '\0')
        {
            subNode->is_word = true;
        }
        return insert(i, word, subNode);
    }
    return true;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // opens file for reading
    FILE *file = fopen(dictionary, "r");
    char word[LENGTH];

    if (file == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    int i = 0;
    // malloc root node
    ROOT = malloc(NODE_SIZE); // line 96
    // word count in the dictionary
    WORD_COUNT = 0;
    // read word by word from file until the end of the file
    while (fgets(word, LENGTH + 1, file) != NULL) // line 100
    {
        // skip blank lines
        if (word[0] == '\n')
            continue;

        WORD_COUNT++;
        // true if whole dictionary (all words) is loaded into memory, else false
        IS_LOADED = insert(i, word, ROOT);
        if (!IS_LOADED)
            break;
    };
    fclose(file);
    return IS_LOADED;
}

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

// UNLOAD

bool free_node(node *nodeArg, int i)
{
    if (nodeArg->children[i] != NULL) // line 129
    {
        // traverse vertically
        nodeArg = nodeArg->children[i];
        i = 0;
        free_node(nodeArg, i);
    }
    else
    {
        // traverse horizontally
        free(nodeArg->children[i]); // line 139

        i++;
        // stop calling function when we get to the apostrophe (last element, node.children[26])
        if (i < 26)
        {
            free_node(nodeArg, i);
        }
    }
    return true;
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    int i = 0;
    return free_node(ROOT, i);
}

Trie:

// trie data structure
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

Answer 1

The Conditional jump or move depends on uninitialised value(s) should not be ignored. malloced memory can contain any values, it just provides the memory, it does not initialise it in any way. Initialise your nodes properly. Here, where the default values for members are NULL and false, both represented by all 0s, you might want to use calloc instead of malloc, which overwrites memory with zeroes.

I get what you are doing with free_node, but the logic would have to be different, like

• call free_node function with node pointer (nodeArg) and incrementer variable (i)
  • if nodeArg->children[i] is not NULL, go vertically to lower branch
    • call free_node function with nodeArg->children[i] and 0
  • (without "else") go horizontally:
  • if i+1 is less than length of nodeArg->children (should be 27)
    • call function with nodeArg and i+1
  • else
    • free nodeArg, which now has no remaining children

but even easier would be a for loop, removing the i parameter:

• for all children of current node
  • if child is non-NULL, call function recursively for the child node
• free current node

You should especially not change the values stored in the parameters.