Unload() recursion C Segfault (TRIE like data base) CS50 pset5

Question

edit 1
As suggested by Jonathan Leffler I am now not using names starting with underscores and also deleted spaces around ->.
________________________________________________________________________________

I am getting a segfault when trying to free struct with recursive function.

Here is my struct:

//creating new trie data ctructure
typedef struct dict
{
    bool is_word;
    struct dict *children[ALPHABET+1];
}
node;

It is used to store dictionary, which is used in spellchecker. In the end of the program I need to free all memory that was allocated.

And here is the function that I've written. It should call itself and free trie piece by piece. However it gives me segfault after calling itself several times.

 bool unload(void)
 {
     // Check if root
     if (temp == root)
     {
         for (int i = 0; i < ALPHABET+1; i++)
         {
             if (!temp->children[i] && i != ALPHABET)
             {

             }
             else if (!temp->children[i] && i == ALPHABET)
             {
                 free(temp);
                 return true;
             }
             else if(temp->children[i])
             {
                 temp = temp->children[i];
                 unload();
             }
         }
     }
     else
     {
         for (int i = 0; i < ALPHABET+1; i++)
         {
             if (!temp->children[i] && i != ALPHABET)
             {

             }
             else if (!temp->children[i] && i == ALPHABET)
             {
                 temp1 = temp;
                 temp->children[i] = temp;
                 free(temp1);
                 return true;
             }
             else if (temp->children[i])
             {
                 temp = temp->children[i];
                unload();
             }
         }
     }
     return false;
 }

Assume that root , temp , temp1 are global. All of them are of struct _dict. And that when the function is called for the first time temp == root.

Welcome to Stack Overflow. Please read the [About] and [Ask] pages soon, but even more importantly, please read about how to create an MCVE ([MCVE]). One of the key requirements for an MCVE here is a compact set of input values that trigger the problem. That seems to be missing. — Jonathan Leffler, Mar 13 '17 at 21:26
Your code is demonstrating why global variables are a bad idea, and counter-productive. You should pass the node to be freed to the function; the initial call passes the root node. The function should not need to access any global variables. — Jonathan Leffler, Mar 13 '17 at 22:23

score 0 · Accepted Answer · answered Mar 13 '17 at 22:34

Your code is demonstrating why global variables are a bad idea, and counter-productive. You should pass the node to be freed to the function; the initial call passes the root node. The function should not need to access any global variables.

Note too that the dot . and arrow -> operators bind very tightly and should not be written with any spaces around them. Also, names starting with an underscore are basically reserved for use by the implementation. The full details are more nuanced than that, but not by much. It is simplest to avoid leading underscores in names you invent. Use them only to access system-provided facilities.

This code does what's necessary, assuming that the code that allocates a node ensures that all the pointers are null.

#include <stdlib.h>
#include <stdbool.h>
enum { ALPHABET = 26 };
typedef struct dict
{
    bool is_word;
    struct dict *children[ALPHABET+1];
} node;

void unload(node *item);

void unload(node *item)
{
    for (int i = 0; i < ALPHABET+1; i++)
    {
        if (item->children[i] != 0)
            unload(item->children[i]);
    }
    free(item);
}

The code could be revised to test whether item is NULL before using it at all. The condition in the loop is then not strictly necessary, but the overall function is more resilient if it is called before any nodes have been allocated.

As shown, it compiles cleanly with these rather stringent warning options (GCC 6.3.0 on a Mac running macOS Sierra 10.12.3):

$ gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes \
>     -Wstrict-prototypes -Wold-style-definition -c tr47.c
$

This code has not been run. I've written similar functions for other people's variants on this CS50 problem. It doesn't need to be any more complex than that.

Actually as per the assignment I am not supposed to alter declaration of unload (which is `bool unload(void) `) that's why global variables were used. Here is the node allocation part looks like: node* getnode(void) { node *newnode = malloc(sizeof(node)); if (newnode != NULL) { newnode -> is_word = false; for (int i = 0; i < (ALPHABET+1); i++) newnode -> children[i] = NULL; } return newnode; } — Roman Abdurahmanov, Mar 14 '17 at 01:03
OK: write: `bool unload(void) { real_unload(root); return true; }` and rename the function I wrote as `real_unload()`. Or maybe use: `bool unload(void) { if (root == NULL) return false; real_unload(root); return true; }`. Don't create global variables called `temp`. Don't use globals longer than you have to. Do the job cleanly — as shown. Don't tell me — you're not allowed to write other functions than the ones specified? In that case, you've got a sadistic tutor. This is CS50; are you sure about the rules you're citing? No-one's complained about similar freeing code before, but … — Jonathan Leffler, Mar 14 '17 at 01:06
No, it's just i cannot change implementations of specific functions (like unload). We are free to write any functions we think will help. So I will remember this trick of yours! — Roman Abdurahmanov, Mar 14 '17 at 01:21

Unload() recursion C Segfault (TRIE like data base) CS50 pset5

1 Answers1