Trie filling with garbage value

Question

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

Answer 1

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

Answer 2

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!