0

While trying to implement the size function in pest5, I noticed I was seg faulting and traced it back to an error in the load function. It appears that after the first letter is read into the trie, the subsequent nodes appear to have pointers to the value 0x11. It is not every node in the trie and I can't find a pattern to it. I'll place the relevant code below. It appears to happen around the new malloc() call.

    for (int c = fgetc(dict); c != EOF; c = fgetc(dict))
    {
        int index = 0;
        if (c == '\n')
        {
            if (node != root)
            {
                //set word to true
                node->is_word = true;
                node = root;
            }
        }

        else
        {
            index = alpha_index(c);

            if (node->children[index] != NULL)
            {
                //break loop if pointer already exists
                node = node->children[index];
            }

            else
            {
                //point to new node
                tmp = node;
                node->children[index] = malloc(sizeof(node));
                node = node->children[index];
                node->parent = tmp;
            }
        }
  • can you please add the declarations for the node structure and tmp? – Cliff B Jul 7 '15 at 2:05
  • @Cliff B, The node declaration is: typedef struct node { bool is_word; struct node* children[27]; struct node* parent; } node; tmp is simply a node* node.parent seems to work correctly as does node.is_true, it is just the children that seem to be adding in odd values. – reddisht Jul 7 '15 at 11:08
  • why do you need a parent member? – Kareem Jul 7 '15 at 16:31
  • @Kareem, while I hadn't gotten that far, my thinking was that it would make freeing the malloc/calloced memory easier by traversing in reverse. Then again, maybe I'm making this whole thing harder than it is. – reddisht Jul 7 '15 at 21:48
4

In a struct like this:

typedef struct Node
{
    bool is_word;
    struct Node* children[27];
    struct Node* parent;
} Node

you have a bool, an array of 27 pointers to Node (children) and another pointer to node (parent).

When you are creating a new node,

node->children[index] = malloc(sizeof(Node));

you are allocating a chunk of memory the size of Node and assigning its address to the index element of node->children. All of the elements of the new Node are currently uninitialized. is_word can be either true or false, parent is pointing at a "random" address and each pointer in the children array is also pointing at a "random", or garbage, address.

After that line you're doing the following:

node = node->children[index];
node->parent = tmp;

which makes you traverse the trie into your newly malloced node and you assign a valid address (the address of old node) into node->parent. That's perfect. So the problem you can find here, your node->children is uninitialized and in the next iteration, when your if condition is checked:

if (node->children[index] != NULL)

you will in fact end up in this branch of the if-else fork since node->children[index] is not initialized to NULL, it is a "random" value. Unfortunately it is also more than likely an illegal address (which is what garbage value is by definition).

| improve this answer | |
  • I'm sorry, @andrej, I'm following you up do the malloc() statement, but then you lost me. Maybe I've got pointer use in my head wrong. I was thinking that when I use node = node->children[index] I was then making the node I was working with the one that the children was pointing to. Any further help appreciated. (Also, I had been using calloc() but was worried that it was causing one of the problems so I changed it to something more familiar while I debugged.) – reddisht Jul 7 '15 at 15:40
  • let me edit a bit, hopefully I'll make it clearer :) – Andrej Jul 7 '15 at 15:46
  • Hopefully it's clearer now. – Andrej Jul 7 '15 at 16:38
  • So if the issue is just a junk value, that should be taken care of by using calloc(), correct? – reddisht Jul 7 '15 at 16:42
  • presumably so, unless there's other issues elsewhere in your code. – Andrej Jul 7 '15 at 17:03
-1

I went through this evening and reordered things. It didn't help the problem, but I think the code is cleaner.

I was thinking about @andrej's struct definition and noticed that he had capitalized Node when referring to the struct. I wondered if the struct (at large) and the specific node called node were confusing things. Once I changed the name, it solved the problem.

Now on to the rest of the problem at hand!

| improve this answer | |
  • By convention, you should capitalize structs - as in types - and classes, whereas variables should start with lower case characters (including variables of type Node). If your problem is solved you should probably mark it as such. – Andrej Jul 9 '15 at 2:00

You must log in to answer this question.

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