0

I'm sort of at my wit's end with this pset and I can't pinpoint where my errors are. Running valgrind says I'm trying to access 8 bytes of memory in my load() function around where I check if the pointer at an index is null (current -> children[index] == NULL). If you guys could take a look at this, that'd be great. Any unrelated improvements welcome as well. Thanks!

// creating the root node
node* root;

// if word is in dictionary, it will return true, else false
bool check(const char *word1)
{
    char word[strlen(word1)];
    strcpy(word, word1);

    // pointer for traversal
    node* current = root;

    unsigned int index;

    for (int i = 0; i < strlen(word); i++)
    {
        // standardize the letters so they're easier to index to

        word[i] = toupper(word[i]);

        // calculate which index the character of the word goes into

        if (isalpha(word[i]))
        {
            index = word[i] - 65;
        }

        // if it's an apostrophe, index to the end of the array

        else if (word[i] == '\'')
        {
            index = 26;
        }

        // if word is misspelled it will return NULL

        if (current -> children[index] == NULL)
        {
            return false;
        }

        else
        {
            current = current -> children[index];
        }
    }

    return current -> is_word;

}

unsigned int wordcounter;

// Loads dictionary into memory, returning true if successful else false
//for each word in dictionary file, store in a data structure
bool load(const char *dictionary)
{

    // open the dictionary

    FILE* dictionary1 = fopen(dictionary, "r");

    if (!dictionary1)
    {
        fprintf(stderr, "Couldn't open dictionary.\n");
        return false;
    }

    unsigned int index = 0;

    // space for new node

    node* new_node;

    // pointer for traversing

    node* current = root;

    // creating root node

    root = malloc(sizeof(node));

    // take each character from the dictionary and
    // place in trie as follows

    for (char c = fgetc(dictionary1); c != EOF; c = fgetc(dictionary1))
    {
        // if it's a letter, capitalize it

        c = toupper(c);

        // if it is an alphabetic character or a comma
        // go to the correct index, check if there's
        // already a node & if not, create a new one
        // if there's already a node, move to that node

        if (isalpha(c) || c == '\'')
        {
            if (isalpha(c))
            {
                // index to a value between 0 & 25 for trie

                index = c - 65;    
            }

            else if (c == '\'')
            {
                // the last element in index is for comma's

                index = 26;
            }


            // if there is a NULL pointer at that index

            if (current -> children[index] == NULL)
            {

                // create a new node

                new_node = malloc(sizeof(node));
                if (!new_node)
                {
                    fprintf(stderr, "Couldn't create new node.\n");
                    return false;
                }

                // connect node to the trie

                current -> children[index] = new_node;

                // move to the new node

                current = current -> children[index];
            }

            else
            {
                // simply move to the node

                current = current -> children[index];
            }
        }

        // if you've reached the end of a word

        else if (c == '\n')
        {
            // indicate that you've reached a valid word

            current -> is_word = true;

            // keep track of how many words you've
            // counted for the 'size' function

            wordcounter++;

            // go back to the beginning of the trie

            current = root;
        }

    }

    fclose(dictionary1);

    return true;
}

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

bool freeTrie(node* ptr)
{

    node* trav = ptr;

    for (int index = 0; index < 27; index++)
    {
        // if there is a valid node at that index

        if (trav -> children[index] != NULL)
        {
            // call freeTrie
            freeTrie(trav -> children[index]);
        }

    }
    // the freeTrie function will be recursively called
    // until you've reached the bottom of the trie
    // where the pointer has a NULL value
    // from that point can you actually free the node
    free(ptr);

    return true;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    return freeTrie(root);
}
1

Let's think about what the relevant code is doing. First, root is declared, but not initialized, so it contains garbage data, not a valid address. The code then sets current equal to root. In other words, current now contains the same garbage data as root. THEN, the code changes root with a malloc call to assign memory to root. The code goes on to try and use the current pointer, which still contains garbage data and not a valid memory address.

Setting current equal to root only copies the address from root to current. When root is later changed, current will not change. Do you see the problem here?

There may be other problems, but this is certainly fatal. Fortunately, it's a very easy fix! ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance.e ;-)

1
  • That got it to work! Thank you so much! – Nicole Nguyeb Jan 1 '19 at 4:23

You must log in to answer this question.

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