CS50 pset5 unload trie segmentation fault

Question

I am having problems with implementing unload. load works perfectly and I can use the check function. I have tried many ways of changing my code but it only creates an infinite loop and I have no idea why. Does anyone know where there are the problems?

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

// prototypes
bool check(const char* word);
bool load(const char* dictionary);
unsigned int size(void);

// define node type for load
typedef struct node{
bool is_word;
struct node* children[27];
} node;

// additional prototypes
int ret_index(int letter);

// set starting pointer root as global variable
node* root;

/*declare node pointers to point to the leaves of the trie
(each indicating a level in the trie for the unload function) */
node* leaf[46];

// set integer pointer for level in unload function
int number = 0;
int* level = &number;

/* set integer pointer for counting number of words 
(counted in load but returned in size function) */
unsigned int* dic_size;

bool load(const char* dictionary)
{
     // open dictionary file
    FILE* fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        printf("Cannot open dictionary file!\n");
        return false;
    }

    // create head root for trie
    root = malloc(sizeof(node));

    // initialize count for size of words in dictionary (for size function)
    dic_size = malloc(sizeof(unsigned int));
    *dic_size = 0;

    // create node pointer traverse to move around trie
    node* traverse = root;

    // get char from dictionary
    int c;

    // iterate through dictionary
    for (c = fgetc(fp);c != EOF; c = fgetc(fp))
    {
        // load the letter to trie
        if (c != '\n')
        {
            // index used inside children[#]: ' = 0 and a ~ z = 1 ~ 27
            int index = ret_index(c);

            // if there is no node, create a new node and connect it
            if (traverse -> children[index] == NULL)
            {
                node* new_node = malloc(sizeof(node));
                for (int i = 0; i < 27; i++)
                {
                    new_node -> children[i] = NULL;
                }
                traverse -> children[index] = new_node;
            }
            // move to new node to traverse
            traverse = traverse -> children[index];
        }
        // if new line (end of word), signal true and point traverse to root to start new word
        else
        {
            // put signal is_word to indicate end of word
            traverse -> is_word = true;

            // increment count of size (to use in size function)
            *dic_size += 1;

            // prepare for new word
            traverse = root;
        }
    }

    // eof: put end of the word
    traverse -> is_word = true;

    // increment count of size
    *dic_size += 1;

    // close dictionary file
    fclose(fp);

    // signal function is completed; else return false
    if (c == EOF)
    {
        return true;
    }
    return false;
}

bool unload(void)
{
    /* set a temporal node pointer to traverse 
    and to wire leaf[*level] with the loaded nodes */
    node* traverse = root;

    // declare bool variable to check whether child of current node is unloaded
    bool checkUnload;

    // iterate through all the children node pointer
    for (int i = 0, n = 27; i < n; i++)
    {
        // wire the leaf[*level] pointers to the loaded nodes
        leaf[*level] = traverse;

        // if there is no path
        if (leaf[*level] -> children[i] == NULL)
        {
            // base case: if last node is null
            if (i == 26)
            {
                // free the node itself
                free(leaf[*level]);

                // update value of level and traverse pointer
                *level = *level - 1;
                traverse = leaf[*level];

                // return value
                if (leaf[*level] == NULL)
                {
                    return true;
                }
                return false;
            }
        }
        // else, when there is a path, go down (use recursion)
        else
        {
            // update level and traverse pointer
            *level = *level + 1;
            traverse = traverse -> children[i];

            // recursion
            checkUnload = unload();
        }
    }

    // check if successfull and return value
    if (root == NULL)
    {
        return true;
    }
    return false;
}

// change value of letter into index value for use in trie
int ret_index(int letter)
{
     // check whether valid input was given
    if (!isalpha(letter) && letter != '\'')
    {
        printf("invalid letter given to re_index!\n");
    }

    // index used inside children[#]: ' = 0, a ~ z = 1 ~ 27
    int index;
    if (isalpha(letter))
    {
        index = letter - 96;
    }
    else
    {
         index = letter - 39;
    }
    return index;
}

Answer 1

Creating dic_size as a pointer is an unnecessary level of indirection. A regular unsigned int or even int would work as well.

Even your load function could easily segfault.

You allocate space for root, but you never initialize it. You could use calloc instead of malloc, that one nulls the space, creating NULL pointers in the array, and false in the boolean. You zero the pointer array for additional nodes (but forget the boolean), using calloc is the easier, though less explicit way.

Your final traverse -> is_word = true; and so on should trigger only if traverse != root, as the file might end with a newline.

I find that unload really difficult to understand, and I don't get how that recursion is meant to work.

I used an extra function, to which I passed a node pointer, and that function would call itself for any child that was not NULL pointer, passing the child, and then delete the node itself, like (pseudo-code)

void unloadNode (node* killIt) {
    for all non-NULL children of killIt, call
        unloadNode(killIt->children[i]);
    free(killIt);
}

and then in unload

unloadNode(root);
reset dict size and whatever else

You might want to change ret_index to return correct values for upper- and lowercase letters (like tolower(letter) - 96 or letter & 31), and maybe return 0, not letter - 39 in the else path (so it does not blow up if you pass something else). Just to make it more robust.