0

The code works and I compared it with the staff's code it cought all the errors but it leaks memory. I don't know why isn't it freeing new_node. I also managed to make unload() work but I don't fully understand how it really works.

Here's the full code:

/**
 * Implements a dictionary's functionality.
 */

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

#include "dictionary.h"

// Create variable to keep track of sucessful unloading of dictionary (used for unload())
bool unloadSucess = false;

// Create variable to keep track of sucessful loading of dictionary (used for size())
bool loadSucess = false;

// Global variable to count number of words loaded (for size())
int wordCounter = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word2)
{
    // node * for traversing
    node *cursor = root;

    // iterate through letters in word
    for (int i = 0, x = strlen(word2); i < x; i++)
    {
        // calculate the place in child to place the chararcter
        int bar = placeChild(i, word2);
        if (bar == 50)
        {
            printf("Invalid char found.\n");
            return false;
        }

        // check for misspelled word first
        if (cursor->children[bar] == NULL)
        {
            return false;
        }
        // otherwise move to next letter
        else
        {
            cursor = cursor->children[bar];
        }
    }
    // check if that word exists once done iterating
    if (cursor->is_word == true)
    {
        return true;
    }

    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    // open dictionary
    FILE *openDictionary = fopen(dictionary, "r");
    if (openDictionary == NULL)
    {
        fprintf(stderr, "Could not open Dictionary.\n");
        return false;
    }

    // the longest word (45 chars) + 1 char for null terminator
    char word[LENGTH + 1];

    // allocate space for root node * (header)
    root = calloc(1, sizeof(node));
    if (root == NULL)
    {
        unload();
        return false;
    }

    // struct to keep track of head
    node *head = root;

    /*
    * scan dictionary word by word
    */
    while (fscanf(openDictionary, "%s", word) != EOF)
    {
        // return head to beginning of trie
        head = root;

        // iterate through the characters of the source word
        for (int i = 0, x = strlen(word); i < x; i++)
        {
            // calculate the place in child to put the chararcter
            int foo = placeChild(i, word);
            if (foo == 50)
            {
                printf("Invalid char found.\n");
                return false;
            }

            // if there's no character in the child
            if (head->children[foo] == NULL)
            {
                // malloc a node * for the new character
                new_node = calloc(1, sizeof(node));
                if (new_node == NULL)
                {
                    unload();
                    return false;
                }

                // make the latest linked child point to the new node *
                head->children[foo] = new_node;

                // traverse to that child
                head = head->children[foo];
            }
            // if there's already a character in child
            else
            {
                // move to next child
                head = head->children[foo];
            }
        }
        // mark character as word's final letter
        head->is_word = true;

        // update counter
        wordCounter++;
    }
    // mark sucessful completion (used in size())
    loadSucess = true;
    // close the opened dictionary file
    fclose(openDictionary);
    // dictionary sucessfuly loaded
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // load() has been called and completed
    if (loadSucess == true)
    {
        return wordCounter;
    }
    // load() has not yet been loaded
    else
    {
        return 0;
    }
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    node *traversal = root;

    // unload using recursion
    unloadHelper(traversal);

    // unload sucessful
    if (unloadSucess == true)
    {
        free(root);

        return true;
    }
    // unload unsuccessful
    return false;
}

/**
 * unload the dictionary from memory
 */
void unloadHelper(node *traversal)
{
    for (int i = 0; i < 27; i++)
    {
        if (traversal != NULL)
        {
            traversal = traversal->children[i];
            return unloadHelper(traversal);
        }
    }
    free(traversal);
    unloadSucess = true;
}

/**
 * calculate the placement of source letter in child
 */
int placeChild(int i, const char sourceWord[])
{
    int placement = 0;

    // if it is a letter
    if (isalpha(sourceWord[i]))
    {
        placement = tolower(sourceWord[i]) - 97;
        return placement;
    }
    // if it is an apostrophe
    else if (sourceWord[i] == '\'')
    {
        placement = 26;
        return placement;
    }
    // assign a number to indicate that the char isn't valid
    else
    {
        placement = 50;
        return placement;
    }
}

And here's the header:

/**
 * Declares a dictionary's functionality.
 */

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word);

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

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

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void);

/**
 * Declaration of function to check where to place the char of source word in load()
 */
int placeChild(int i, const char sourceWord[]);



// Declare structure for tries
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

// Create root for starting point (later allocated)
node *root;

// Create new node for following children
node *new_node;

/**
 * Declaration of function to help with unload()
 */
void unloadHelper(node *traversal);

#endif // DICTIONARY_H

When running valgrind --leak-check=full ./speller texts/ralph.txt it gives this error:

==3946== 
==3946== HEAP SUMMARY:
==3946==     in use at exit: 82,226,144 bytes in 367,081 blocks
==3946==   total heap usage: 367,084 allocs, 3 frees, 82,227,504 bytes allocated
==3946== 
==3946== 672 bytes in 3 blocks are possibly lost in loss record 2 of 4
==3946==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3946==    by 0x401446: load (dictionary.c:111)
==3946==    by 0x4009FD: main (speller.c:40)
==3946== 
==3946== 82,225,248 (5,824 direct, 82,219,424 indirect) bytes in 26 blocks are definitely lost in loss record 4 of 4
==3946==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3946==    by 0x401446: load (dictionary.c:111)
==3946==    by 0x4009FD: main (speller.c:40)
==3946== 
==3946== LEAK SUMMARY:
==3946==    definitely lost: 5,824 bytes in 26 blocks
==3946==    indirectly lost: 82,219,424 bytes in 367,051 blocks
==3946==      possibly lost: 672 bytes in 3 blocks
==3946==    still reachable: 224 bytes in 1 blocks
==3946==         suppressed: 0 bytes in 0 blocks
==3946== Reachable blocks (those to which a pointer was found) are not shown.
==3946== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==3946== 
==3946== For counts of detected and suppressed errors, rerun with: -v
==3946== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
0

Don't do

            traversal = traversal->children[i];
            return unloadHelper(traversal);

but

            unloadHelper(traversal->children[i]);

The assignment makes you lose the current value of traversal, while return immediately ends your function, returning to the calling code.

I don't think I understand the concept of unloadSuccess.

Don't free root after you've already freed it by calling unloadHelper(root); disguised as unloadHelper(traversal); in unload.

| improve this answer | |

You must log in to answer this question.

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