pset5 Speller -load - Valgrind error - "invalid read of size 8"(segmentation fault)

Question

i have been trying to figure this out but need some help! even a hint will do...

//trie node
typedef struct trie_node
{
    struct trie_node* parent;
    struct trie_node *child[27];
    //check is end of word
    bool is_end;
}trie_node ;

//pointer to the root
trie_node* root;

thats my tries structure...on running the help50 valgrind i get this error

Helping with...                                                                                                                                                                                       

==4567== Invalid read of size 8
==4567==    at 0x4011BA: load (dictionary.c:104)
==4567==    by 0x4008C4: main (speller.c:40)

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 104 of dictionary.c.

here is my load function

bool load(const char *dictionary)
{


    //open dictionary
    FILE* fp= fopen (dictionary , "r");

    if (fp==NULL)
    {
        return false;  // not successful to load
    }


        //start from the root
        trie_node* current_node = root;
         root = calloc(1, sizeof(trie_node));


        //load dictionary words into memory 
        for (int word = fgetc(fp); word != EOF; word = fgetc(fp))
        {
            //load in word letter by letter
            while(word != '\0')
            {
                   //if apostrophe
                   if(word=='\'')
                   {
                       word = 'z'+ 1; // add to  child[27]
                    }

                    int childIndex = tolower(word) - 'a';
                    //input values in empty node
                    if (current_node -> child[childIndex] == '\0' ) 
                    {
                        current_node -> child[childIndex] = calloc(1, sizeof(trie_node));
                        current_node -> child[childIndex]->parent = current_node;
                    }
                //if letter already present
                current_node = current_node -> child[childIndex];
                ++ word;
            }    

            if(word == '\0')
            {
               //mark the end of word
               current_node ->is_end = true;
               count ++;
            }
        }

        // end of dictionary
        if(fgetc(fp) == EOF)
        {
            fclose(fp);
            return true;
        }
    return true;
}

the error is on this line or part..

int childIndex = tolower(word) - 'a';
                    //input values in empty node
                    if (current_node -> child[childIndex] == '\0' ) 
                    {
                        current_node -> child[childIndex] = calloc(1, sizeof(trie_node));
                        current_node -> child[childIndex]->parent = current_node;
                    }

Answer 1

Your problem arises from current_node -> child[childIndex]->parent = current_node;.

First off, unlike in math, A=B does not mean the same as B=A. If you want to change your current_node node, place it on the left side of the equal sign. Secondly, I'm unsure where you're going with those parent nodes—you don't seem to use it anywhere else in your function. Think about or revisit Zamyla's explanation of tries, and how a parent may or may not fit into the flow of the problem.

If you do go through with your parent approach, calloc it as well to avoid any errors.

Answer 2

Not 100% sure, but confident. I had to fill in missing code with educated guesses. It appears that the following is generating a seg fault:

                if (current_node -> child[childIndex] == '\0' )

When running the code (with assumptiions), it appears that current_node has not been initialized or is NULL. Because of that, none of the elements of the structure exist, causing a seg fault. Is current_node getting memory assigned before it is being used?

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