pset5 (trie) valgrind memory leak

Question

I'm having trouble with the last step of pset5, valgrind. When I run it with the test text I get: Looks like you're trying to access 8 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 124 of dictionary.c.

Line 124...

   (if (start->child[i] != NULL))

is within my bool function that aids with unloading the memory. I've tried quite a bit of changes, but to no avail. Below is my current code:

// Implements a dictionary's functionality

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

#include "dictionary.h"


typedef struct node

{
    bool is_word;
    struct node *child[27];
}
node;
node *root;

int get_i(const char c)
{
if (c == '\'')
{
    return 26;
}
else
{
    return tolower(c) % 'a';
}
}

// intialize counter variable to count words in the load/size function
int counter = 0;

//function for unload
bool freedom(node *start);

// function for checking char of words
int get_i(const char c);

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{

// create memory for root pointer
root = calloc(1, sizeof(node));

// Open dictionary file
FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
{
    fprintf(stderr, "Could not open. \n"); // Print error if file cannot be 
opened
    return 2;
}


// set new node to root to start process
node *start = root;

for (int x = fgetc(dict); x != EOF; x = fgetc(dict))
{

    if (x == '\n') // if NULL
    {
        start->is_word = true;
        counter++;
        start = root; // traverse over the trie again from the beginning
    }

    else // if not NULL
    {
        int i = get_i(x);

        if (start->child[i] == NULL)
        {
            start->child[i] = calloc(1, sizeof(node));
        }

        // move to nxt node
        start = start->child[i];

    }
}
free(start);
fclose(dict);
return true;

}

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

// iterate over each letter to build a word; then check if it is a word
for (int i = 0; word[i] != '\0'; i++)
{
    int ind = get_i(word[i]);

    if (start->child[ind] == NULL) // go to the next letter in word
    {
        return false; // if the sequence of letters isnt in the dict it is "misspelled"
    }

    start = start->child[ind]; // if it is !NULL go to next letter
}
return start->is_word;
}


// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
// return the number of words found in dictionary by returning the counter 
variable
return counter;

}

// free the children
bool freedom(node *start)
{
// go through all th children of the corn
for (int i = 0; i < 27; i++)
{
    if (start->child[i] != NULL)
    {
        freedom(start->child[i]);
    }
}

free(start);
return true;
}

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

Answer 1

Without even looking at anything but this:

(if (start->child[i] != NULL))

I would ask if start actually exists at this point in the execution. I'll look at the code and edit my answer if/when I find something, while you keep looking.

[EDIT: ok, I looked at the code.]

So, my initial thought was right. Something is not there any longer.

One question. Looking at line 85 at the end of load():

free(start);

What do you think is being freed? What is start set to point at?

Answer this and you'll find the root of your problem! (snicker!)

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