How to free recursive struct (trie)

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.

---

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);
}

---

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.

链接地址: http://www.djcxy.com/p/89710.html

上一篇: 登录]初始化= xyz“意思是在一个SQL异常？

下一篇: 如何释放递归结构（trie）