0

sorry if I am asking the question in a wrong way or my code is too messy I am knew here. My problem is that it looks like load works and the dictionary is loaded into the trie but check and unload functions act like it was never loaded in. I would be very grateful for any pointers as to what is going wrong.

// Implements a dictionary's functionality

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

#include "dictionary.h"

//global dictionary counting variable and temporary node for traversal
int count = 0;
// Represents number of children for each node in a trie
//#define N 27

// Represents a node in a trie
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

// Represents a trie
node *root;

node *new_node;

bool checkunl = true;

node *getNode(void);

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //make a variables for letters
    int letter;



    // Initialize trie
    root = getNode();
    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];
    memset(word, '\0', LENGTH + 1);
    rewind(file);

    node *temp;

    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {
        temp = root;

        //iterate over letters
        for (int i = 0; word[i] != '\0'; i++)
        {
            letter = word[i];
            if (letter == '\'')
            {
                letter = 123;
            }

            //create new node if children[current letter] is NULL
            if (temp->children[letter - 'a'] == NULL)
            {
                temp->children[letter - 'a'] = getNode();
                temp = temp->children[letter - 'a'];

            }
            else
            {
                temp = temp->children[letter - 'a'];
            }
        }
        temp->is_word = true;
        count++;
        memset(word, '\0', LENGTH + 1);
    }

    // Close dictionary
    fclose(file);

    temp = NULL;
    // Indicate success
    return true;
}

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

    return count;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *temp = root;
    int letter;
    for (int i = 0; i < (sizeof(word) / sizeof(char)); i++)
    {
        letter = word[i];
        if (letter == '\'')
        {
            letter = 123;
        }
        letter = tolower(letter);

        if (temp->children[letter - 'a'] == NULL)
        {
            memset(temp, '\0', sizeof(node));
            return false;
        }
        temp = temp->children[letter - 'a'];
    }
    if (temp->is_word == true)
    {
        temp = NULL;
        return true;
        memset(temp, '\0', sizeof(node));
    }
    else
    {
        temp = NULL;
        return false;
        memset(temp, '\0', sizeof(node));
    }
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *temp;
    if (checkunl == true)
    {
        temp = root;
        checkunl = false;
    }
    for (int i = 0; i < 27; i++)
    {
        if (temp->children[i] != NULL)
        {
            temp = temp->children[i];
            unload();
            return 0;
        }
    }
    if (temp != root)
    {
        free(temp);
        checkunl = true;
    }
    if (temp == root)
    {
        free(temp);
        return true;
    }
    return false;
}

node *getNode(void)
{
    node *pNode = NULL;

    pNode = (node *)calloc(1, sizeof(node));

    if (pNode == NULL)
    {
        return false;
    }

    pNode->is_word = false;
    for (int i = 0; i < 27; i++)
    {
        pNode->children[i] = NULL;
    }
    return pNode;
}
7
  • Thank you Cliff B for correcting the code I wasn't sure how to do that.
    – Ben Kruse
    Mar 29 '19 at 17:46
  • Is root declared globally, outside of any function? (previously didn't scroll down, so missed the getNode definition, the use of calloc instead of malloc means the rest of the function is not needed as it already sets everything to NULL or false, as those are represented by all-zeroes, but it is inefficient, not wrong)
    – Blauelf
    Mar 29 '19 at 17:48
  • Root is declared globally and I tried declaring temp globally and inside the function. I switched to calloc in case malloc was causing the problem and left in the rest of the function because I wasn't sure if it was needed or not. @Blauelf
    – Ben Kruse
    Mar 29 '19 at 17:50
  • root declared only globally right? C has this feature of "shadowing", where a variable shadows another of the same name but declared at a more outside scope. If you have that right, no accidental second non-global node *root... no idea. What makes you assume the nodes are not there?
    – Blauelf
    Mar 29 '19 at 17:54
  • Yes I only declared it locally. When I run it the check function counts all words as misspelled and unload acts like the dictionary trie in memory is empty. @Blauelf
    – Ben Kruse
    Mar 29 '19 at 17:57
1

load looks about right. I don't understand the use of memset and rewind in that one, but I guess at least they do no harm.

In check however, the memset does cause serious harm. If it cannot find the next node, it zeroes the current one, erasing any trace of its children (and declaring it not a word). At least two of the three memset won't have adverse effects, as code after a return cannot be executed by regular means (return leaves the function).

So calling check slowly erases nodes until you have only an empty root node left.

To fix, remove the memsets. A check function should never change anything in the dict.

unload, when implemented in this very inefficient way, requires a global variable temp, and you'd hit a double free if you don't set the pointer to NULL after unloading, which could be some more work.

A more efficient way would require a helper function which takes the node to unload as its parameter, and would ensure that the given node and all of its children are unloaded, by first calling itself for all the non-NULL children, then freeing the node itself.

1
  • Thank you so much that seems to have been the problem. I thought 'memset' would reset the pointer not the node itself. I definitely will change unload but was having trouble since I couldn't check if it was working. @Blauelf
    – Ben Kruse
    Mar 31 '19 at 13:54

You must log in to answer this question.

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