0

My freeNode() function goes through each child of my root node and free()'s each of them from the bottom back up to the root. Two of the allocs are not being free()'d.

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include "dictionary.h"
#include <string.h>
#include <ctype.h>

// node needs one node* for each letter in alpha and apostrophe
#define NODE_SIZE 27

// create trie struct
typedef struct node
{
    bool isWord;
    struct node* letter[NODE_SIZE];
}
node;

// create root node
node* root = NULL;

// counts number of words in dictionary
int wordCount = 0;

// iterates through node and frees its children
void freeNode(node* n)
{
    for (int i = 0; i < NODE_SIZE; i++)
    {
        if (n->letter[i] != NULL)
        {
            freeNode(n->letter[i]);
        }
    }
    free(n);
}

// inits a new node
void initNode(node* nodeToInit)
{
    nodeToInit->isWord = false;
    for (int i = 0; i < NODE_SIZE; i++)
    {
        nodeToInit->letter[i] = NULL;
    }
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // init checker node
    node* checker = root;

    // iterate through each char
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        // let l be the current letter of word
        char l = word[i];
        if (isalpha(l))
        {
            // lowercase if letter, otherwise it is apostrophe
            l = tolower(l);
        }

        if (checker->letter[l - 'a'] == NULL)
        {
            return false;
        }
        else
        {
            checker = checker->letter[l - 'a'];
        }
    }
    if (checker->isWord == true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

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

    // init root node and temp node
    root = malloc(sizeof(node));
    initNode(root);
    node* tempNode = root;

    // iterate through dict until EOF
    for (char c = fgetc(dictPtr); c != EOF; c = fgetc(dictPtr))
    {
        // if end of word, mark as word, start new word
        if (c == '\n')
        {
            tempNode->isWord = true;
            wordCount++;
            tempNode = root;
        }
        else
        {
            // next letter not in node yet
            if (tempNode->letter[c-'a'] == NULL)
            {
                tempNode->letter[c-'a'] = malloc(sizeof(node));
                initNode(tempNode->letter[c-'a']);
            }

            // go to next letter
            tempNode = tempNode->letter[c-'a'];
        }
    }
    fclose(dictPtr);
    return true;
}

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

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

Valgrind lets me know there are two allocs that aren't free()'d. And its line about "by 0x80491d5: load (dictionary.c:127)" seems to be saying that section of code is the problem?

==15977== HEAP SUMMARY:
==15977==     in use at exit: 224 bytes in 2 blocks
==15977==   total heap usage: 367,047 allocs, 367,045 frees, 41,109,744 bytes allocated
==15977== 
==15977== 224 (112 direct, 112 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==15977==    at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==15977==    by 0x80491D5: load (dictionary.c:127)
==15977==    by 0x8048725: main (speller.c:45)
==15977== 
==15977== LEAK SUMMARY:
==15977==    definitely lost: 112 bytes in 1 blocks
==15977==    indirectly lost: 112 bytes in 1 blocks
==15977==      possibly lost: 0 bytes in 0 blocks
==15977==    still reachable: 0 bytes in 0 blocks
==15977==         suppressed: 0 bytes in 0 blocks
==15977== 
==15977== For counts of detected and suppressed errors, rerun with: -v
==15977== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 0 from 0)

Why isn't my freeNode() function freeing all of the nodes?

2

You overlooked something. Here's a hint. What is the integer value of ' - 'a'? Or, subtract the ASCII value of 'a' from the value of an apostrophe?

I'm actually surprised that your code isn't generating an error. Oh, wait, it does, sort of. Try turning off the printing of misspelled words and run against a large text under valgrind --leak-checks=full. You'll find some read errors.

I know what the problem is, but not sure about exactly what's really happening, or why your code works. Anyways, here's what's happening. Exactly two nodes are being left behind, one direct node, and one child(indirect). You're failing to clear apostrophe nodes, the one for the apostrophe and it's only child node, S. (I have no idea why the node for the apostrophe is not throwing an error, since the index is -58. Maybe someone else can explain that one. I'm also not sure why it's only 2 nodes total since apostrophe nodes should be all over the trie. My theory is that all the apostrophe's are being put in one node, so the 's' that follows always goes into the same child.)

When you free all of the nodes, it sweeps through the trie from root node 0 through root 26, but fails to find the apostrophe nodes. I'm guessing that all of the apostrophes are going into the same node somewhere, and the S node is a child of that node. Or, it's just going into a bit bucket somewhere. OK, I really don't know where it's creating the phantom nodes.

Try inserting the following code to see what's happening:

// next letter not in node yet
if( (c-'a')<0 || (c-'a') > 26) printf("BINGBINGBING! c-a=%i\n",(c-'a') );

If you add some code to load() to handle the special case of the apostrophe, it should solve your issue.

If this answers your question, please accept this answer to remove it from the unanswered question pool. Let's keep up on forum housekeeping. ;-)

You must log in to answer this question.

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