0

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;
                    }

2 Answers 2

0

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.

3
  • It appears that he is creating a bidirectional linked list type of trie. When the new node is created at childIndex, it has an element called parent that needs to point back to current_node, so the statement appears to be correct. However, I don't see the reason for it. While its a good exercise to do this, there is no need for a bidirectional linked list. The pset can be implemented with a unidirectional trie. There's no reason to backtrack. Haven't looked at the underlying problem yet. It would be helpful if the exact line 104 could be identified.
    – Cliff B
    Dec 10, 2017 at 2:50
  • Yes its as @Cliff B said it was bidirectional tracing back...and thATS not where the problem lies...
    – shaistha
    Dec 10, 2017 at 6:15
  • @Cliff B you are rights...that's the line causing the issue....my thoughts were that...it would check for the empty node....n then create a new one...
    – shaistha
    Dec 10, 2017 at 6:17
0

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. ;-)

4
  • you are right..that's where the faults been occurring.... yes it is null...I thought...It will check if its null and then point to the new one....so I haven't initialised it ...I.e.,check if empty and theb create a node ..that was my thought
    – shaistha
    Dec 10, 2017 at 6:14
  • As you could see in my code...@Cliff B in the top...while creating current_node...I set it equal to the root...
    – shaistha
    Dec 10, 2017 at 6:20
  • If a pointer to a structure has not had memory allocated to it, none of the structure elements exist, so they cannot be referenced.Any attempt to reference a nonexistent element almost always results in a seg fault. For example, if mynode has been created but no malloc or calloc executed and the address stored in mynode, then two things are true. mynode can be rerferenced to check whether it is NULL or something else (including garbage data), but any attempt to reference mynode->is_end (or any other structure element) will almost certainly generate a seg fault.
    – Cliff B
    Dec 10, 2017 at 6:34
  • Those two lines of code don't execute at the same time.. The correct word is "before", not "while" creating current_node. The two lines of code do the following: 1. Copy the contents of root to current_node (currently either garbage data if not initialized, or NULL - note that when a pointer is created, there is no default initialization to NULL), and then 2. allocate memory to root (which has no effect on current_node). Now, if those two lines were reversed, there's be an entirely different story here.
    – Cliff B
    Dec 10, 2017 at 6:36

You must log in to answer this question.

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