pset5 load() seg fault and malloc problems

Question

I've been having great difficulty with implementing the load() function.

bool load(const char* dictionary)
{
    // Define node structure
    typedef struct node
    {
        bool is_word;
        struct node* children[27];
    }
    node;

    // Open dictionary
    FILE* dict = fopen(dictionary, "r");
    if (dictionary == NULL)
    {
        printf("Could not open dictionary.\n");
        return -100;
    }

    // Create root and set all pointers to NULL
    node* root = malloc(sizeof(node));
    root->is_word = false;
    for (int i = 0; i < 28; i++)
    {
        root->children[i] = NULL;
    }

    // Creat a traversal node
    node* trav = malloc(sizeof(node));
    trav = root;

    // Create a buffer that holds words from dictionary
    char word[46];

    while (fscanf(dict, "%s", word) != EOF)
    {
        for (int i = 0, l = strlen(word); i < l; i++)
        {
            int index = word[i] - 'a';
            if (i == 0)
            {
                if (root->children[index] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    trav->children[index] = new_node;
                }
                else
                {
                    trav = trav->children[index];
                }
            }
            else
            {
                trav = trav->children[index];
            }
            if (trav->children[index] == NULL)
            {
                    node* new_node = malloc(sizeof(node));
                    trav->children[index] = new_node;
            }    
            else
            {
                trav = trav->children[index];
            }
        }

        trav->is_word = true;
        trav = root;
    }

    fclose(dict);

    return true;
}

The first problem I encounter is the root node not being set to NULL; valgrind says that, when I try to NULL all children in root, "address is 0 bytes after a block of size 224 alloc'd". How can the program be looking for an address after the malloc'd block?

Secondly, I'm very shaky on the concept of recursive pointers. I've watched the lectures, walkthrough, and shorts, and I'm still fairly uncertain how to properly direct the pointers. Any tips on where to look for clearer direction would be greatly appreciated!

Answer 1

I see a couple of issues. The first is your for loop to initialize root:

for (int i = 0; i < 28; i++)

There are 27 children in the structure, numbered 0 to 26. Your loop is trying to initialize 28, numbered from 0 to 27. One too many.

Next, you have a memory leak here:

// Creat a traversal node
node* trav = malloc(sizeof(node));
trav = root;

This allocates memory with the creation and initialization of trav, but in the next line, immediately abandons the memory that was just allocated ( a very common mistake by new programmers.) Instead of malloc, do this:

node* trav=NULL;

It creates the pointer and sets it to null so no memory is allocated and/or lost. Or you could immediately assign it to root.

As for where to look for more info on recursive pointers, not sure where to point you. ;-)

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