PSet5: Segfault in unload

Question

My code compiles, but when I run it it returns the following message and segfault.

dictionary.c:183:9: runtime error: index 27 out of bounds for type 'struct node *[27]'
dictionary.c:185:15: runtime error: index 27 out of bounds for type 'struct node *[27]'

I am posting my load and unload code below as I have read responses on this topic mention incorrect loading as a reason for the segfault.

I have taken care to ensure that every node I create is set to NULL, and that each of the children within the node is also set to NULL. I have also manually followed the loading of the pset's small dictionary into a trie, and it seems to create the correct number of nodes, with each children pointing to the correct next node.

In short I am lost, and any help would be appreciated. Please also let me know if further clarification to this question is needed:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cs50.h>
#include <strings.h>
#include <ctype.h>

#include "dictionary.h"

// Number of node pointers in children
#define SIZE 27

// declare trie node
typedef struct node
{
    bool is_word;
    struct node *children[SIZE];
}
node;

// declare root and trav pointers
node *root;
node *trav;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // declare word char
    char word1[LENGTH + 1];

    // assign root node
    root = (node*)calloc (1, sizeof(node));
    nodes++;

    // make sure each children pointer points to NULL
    for (int p = 0; p < SIZE; p++)
    {
        root->children[p] = NULL;
    }

    // check if there is space for new node
    if(!root)
    {
        unload();
        return false;
    }

    // receive word from dictionary
    FILE *file = fopen(dictionary, "r");

    if (!file)
    {
        printf("File does not exist!\n");
        return false;
    }

    // loop through each word in the dictionary
    while (fscanf(file, "%s", word1) != EOF)
    {
        // set trav node to root node
        trav = root;
        int j;
        // loop through word1
        for (int i = 0; i < strlen(word1); i++)
        {
            // convert word character to integer
            if (word1[i] == '\'')
            {
                j = (word1[i] - 13);
            }
            else
            {
                j = (word1[i] - 'a');
            }

            // check if trav->children is null
            if (!trav->children[j])
            {
                // if it is create a new node and point trav at it
                node*new_node = (node*)calloc (1, sizeof(node));
                nodes++;

                // make sure each children pointer points to NULL
                for (int p = 0; p < SIZE; p++)
                {
                    new_node->children[p] = NULL;
                }

                // check if there is space for new node
                if(!new_node)
                {
                    unload();
                    return false;
                }
                trav->children[j] = new_node;
                trav = trav->children[j];
            }

            // else move trav to next node
            else
                trav = trav->children[j];
        }

        // at end of loop set is_word to true at last node
        trav->is_word = true;
    }

    fclose(file);
    return true;
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{

    while(root)
    {
        trav = root;
        found(trav, 0, SIZE);
    }
    return true;
}

// finds node in trie to free and points trav at it
void found(node *ptr, int r, int upper)
{

    if (r == upper)
    {
        free(ptr);
    }

    if (ptr->children[r])
    {
        ptr = ptr->children[r];
        return found(ptr, 0, upper);
    }

    else if (!ptr->children[r])
    {
        r++;
        return found(ptr, r, upper);
    }

}

Answer 1

First, the while loop in unload makes no sense, since root is never changed, you would enter an infinite loop trying to free the same trie over and over (probably running into another segfault on first re-try).

Then, your found function is basically emulating a for loop (which I would prefer, as it saves several recursion levels). But would work with a few small changes.

One problem is, that it should stop after freeing the current node, so put a return; behind the free. That's the thing causing the segfault with index out of bounds, when you test ptr->children[SIZE] in the if below.

Another problem is that the call to found(ptr, r + 1, upper) at the end should happen even if the call to found(ptr->children[r], 0, upper) happened before, otherwise you skip nodes to unload. So there should be no other return, and no else if, and you should not change the content of the ptr parameter.