pset5, have a seg fault but valgrind reports no error

Question

I think I have load, check and size function running successfully. However, my code meets seg fault again. Valgrind reports:

==5654== Stack overflow in thread 1: can't grow stack to 0xffe801ff8

==5654== Process terminating with default action of signal 11 (SIGSEGV)

==5654== Access not within mapped region at address 0xFFE801FF8

---other things---

==5654== at 0x4014A6: unload (dictionary.c:204)

==5654== HEAP SUMMARY:

==5654== in use at exit: 1,792 bytes in 8 blocks

==5654== total heap usage: 10 allocs, 2 frees, 2,928 bytes allocated

---other things----

==5654== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) Segmentation fault

It seems there is something wrong in unload, I sue a recursion in the function. Here is the part of my code

// define a tries to load dictionary
typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;


// creat a pointer to track the beginning of trie
node* root;
node* destroyer;

// dictionary size counter
int dictionary_size = 0;



/**
* Initialize new nodes.
*/
void initialize(node* pointer)
{
    pointer->is_word = false;
    for(int i = 0; i < 27; i++)
    {
        pointer->children[i] = NULL;
    }
}


/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    root = NULL;
    destroyer = NULL;
    // open the dictionary file.
    FILE* dt = fopen(dictionary, "r");
    if (dt == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return 1;
    }

    // creat a pointer at the start of tries to track loading.
    node* new_node = malloc(sizeof(node));
    initialize(new_node);
    root = new_node;
    node* builder = root;
    destroyer = root;

    if (builder != NULL)
    {
        for (int ch = fgetc(dt); ch != EOF; ch = fgetc(dt))
        {
            if (isalpha(ch))
            {
                if (builder->children[ch - 'a'] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    initialize(new_node);
                    builder->children[ch - 'a'] = new_node;
                }

                builder = builder->children[ch - 'a'];
            }

            else if ( ch == '\'' )
            {
                if(builder->children[26] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    initialize(new_node);
                    builder->children[26] = new_node;
                }

                builder = builder->children[26];
            }

            // when hit \0
            else
            {
                builder->is_word = true;
                dictionary_size = dictionary_size + 1;

                // reset the pointer to the root, preparing for a new word
                builder = root;
            }
        }

        // hit EOF, close dictionary
        fclose(dt);
        return true;
    }

    return false;
}


/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{

    // set the lowest node as base case, then recursion.
    if (destroyer != NULL)
    {
        if (lowest(destroyer))
        {
            if (destroyer == root)
            {
                free(destroyer);
                return true;
            }
            else
            {
                free (destroyer);
            }
        }

        else
        {
            for(int j = 0; j < 27; j++)
            {
                if (destroyer->children[j] != NULL)
                {
                    destroyer = destroyer->children[j];
                    unload();
                }
            }
        }
    }
    return true;
}



/**
* Checks if the node is the lowest layer of trie.
*/ 
bool lowest(node* layer)
{
    if (layer != NULL)
    {
        for (int i = 0; i < 27; i++)
        {
            if (layer->children[i] != NULL)
            {
                return false;
            }
        }
        return true;
    }
    return false;
}

My questions are:

1. in my small dictionary, I put 3 words : a, and, once. I tried to draw the trie with pen and paper, it only took 8 node allocs. Why valgrind reports 10 allocs?

2. Why my code has seg fault? and why valgrind reports no error?

3. Does the seg fault have something to do with the valgrind warning "Stack overflow in thread 1: can't grow stack to 0xffe801ff8" ? what does it mean?

David was right about saying pset5 is the hill top (for cs50)...

Thank you!

Answer 1

You are running out of stack memory in your recursive calls to unload. I suspect, based on this post, that you need a return after free (destroyer);