How to free recursive struct (trie)

Question

FINAL EDIT

My function that frees the memory works properly, and as milevyo has suggested, the problem lies in node creation, which I had fixed. I now have a separate problem where the program segfaults when run normally, but it cannot be reproduced in gdb or valgrind. However, that is a separate question altogether.

I have since found out that this segfault happened because I did not check for the EOF character properly. As per Cliff B's answer in this question, the check for EOF happens only after the last character in the file. As a result, in my function that loads the dictionary file, I had assigned the last character of the file to some i (which in this case was -1 according to a printf call), and tried to create and access a child node if index -1. This caused a segmentation fault, and also caused problems with my unload function, which would not unload the very last node I created.

As to why the segmentation fault does not appear when I run the program in gdb or valgrind, I have no idea.

EDIT 3

While stepping through my load function where the node creation happens, I notice an unexpected behaviour. I believe the problem lies somewhere in these lines of code, which are embedded within a for loop. The casting to (node*) is just to be safe, though it does not affect the running of the code to my knowledge.

// if node doesnt exist, calloc one, go to node
if (current_node->children[i] == NULL)
{
    current_node->children[i] = (node*) calloc(1, sizeof(node));
    nodes++;
}
current_node = current_node->children[i];

While stepping through the load function, I see that my current_node->children[i] seem to be calloc'ed properly (all children set to NULL), but the moment I step into current_node->children[i] and examine its children (see image below), I see that the addresses get screwed up. Specifically, the i'th child in the children node gets set to 0x0 for some reason. While 0x0 is supposed to be equal to NULL (correct me if I'm wrong), my free_all function seems to want to go into the 0x0 pointer, which of course results in a segfault. Can anyone shed light on how this might happen?

Values of children[i]

EDIT 2: I'm using calloc to create my nodes

root = calloc(1, sizeof(node));

For my child nodes, they are created within a for loop where I iterate over characters of the dictionary file I'm reading in.

if (current_node->children[i] == NULL)
{
    current_node->children[i] = calloc(1, sizeof(node));
    nodes++;
}

c in this case represents the character of the word being read in. I get i using the following:

if (c == '\'')
    i = 26;
else if (isalpha(c))
    i = c - 97;

EDIT: I'm thinking that something in my node creation is faulty, as milevyo suggested. This is because if I print out the addresses, it goes from 0x603250 to 0x603340 to 0x603430 to 0x603520, then finally to (nil), before it segfaults. I have verified that the root node gets passed in correctly by printing out its value in gdb. I'll try to figure it out.

ORIGINAL QUESTION

I'm running into a segfault when trying to free a recursive struct, but cannot figure out why, and would like some help.

My struct is defined as follows:

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

This is meant to implement a trie structure in which to load a dictionary into, for purposes of a spellcheck. After the spellcheck is done, I need to free the memory that I've allocated to the trie.

This is my current function which should free the trie when passed the root node, but it segfaults when doing so, though not immediately:

void free_all(node* curs)
{
    int i;

    // recursive case (go to end of trie)
    for (i = 0; i < 27; i++)
    {
        if (curs->children[i] != NULL)
        {
            free_all(curs->children[i]);
        }
    }

    // base case
    free(curs);
}

Where could I have gone wrong? If more information is needed, please let me know.

Doing

@bolov Yes ,read that . Therefore , removed comment :) – Trill

The posted code looks OK. The problem lies in other parts of your code. – Emilie

Show us how you are creating a trie. – Vav

Are you initializing the entries in children to NULL when you first allocate a node? If not, then that's your problem. – Cleopatracleopatre

i can not see the purpose of using NODES here, thus i think the problem is in the logic you are using. (NODES do not store any useful value) – Brickey

@milevyo: the nodes here are only useful for their bool value is_word. I will load a dictionary into the trie, with each node's is_word value signifying that the word exists. This is then used in a word checker program which passes words into the trie, and checks if the word exists in the trie. If it does not, the word is misspelled. – Doing

still i can not get the picture – Brickey

Answer 1

i think, root node is faulty ( maybe it is null). if not, look elsewhere. in node creation for example.

void free_all(node* curs)
{
    int i;
    if(!curs) return;   // safe guard including root node. 

    // recursive case (go to end of trie)
    for (i = 0; i < 27; i++)
       free_all(curs->children[i]);


    // base case
    free(curs);
}

Brickey

Answer 2

The free_all function is ok. You have to check you set to NULL all children not allocated. This includes nodes that are not leaves, but don't have all the 27 children.

If that is ok, or fixing it doesn't fix the segfault, you have to debug.

Bobsleigh

I allocated memory to my nodes using calloc and not malloc, and to my knowledge that already sets all children to NULL, so that should not be the problem – Doing

@panzer. Yes, calloc should set them to NULL. If you are paranoid, you cold just double check (I would). As I've said, the best option now is to debug. Good luck :) – Bobsleigh