0

Having a lot of trouble with unload(). I've scrapped nearly working functions several times just in the hopes that starting over will fix things. I cannot figure out why my code keeps leading to the undefined behavior exhibited. The function I wrote below sits within unload() and runs before unload checks to see if the root node has been set to NULL as a result of NULL_search_and_free(). My structure is a trie.

This handles very small word sets as dictionaries just fine (100 words). As I near 200 or so, I run into some strange behavior that I can't seem to find a cause for. It happens during the deletion process titled so in my notes to the last part of the code. It always suffers a segmentation fault on a specific memory address, 108b600. It runs through the code and finds only NULL children. As per the function's code, it sets the traversal pointer up to the parent node (108b510) so that it can delete 108b600. It then starts in on the for loop of the deletion process and detects a non-NULL node pointer at 108b600, as expected. However, instead of deleting 108b600 when arriving at free(x->children[i]); where x in this case should still be pointing to the parent, it suddenly switches to 108b600 and tries to free memory from an unallocated child pointer. The function will successfully run through twenty or so node deletions before behaving this way, and I can't seem to find a clue as to why while working with the debugger.

Help greatly appreciated!

 void NULL_search_and_free(node *x)
 {

//checks that this isn't about to be performed for final deletion of root node.
if(x == root && ALL_NULL(root) == true)
{
    if(root != NULL)
    {
        free(root);
        root = NULL;
        NULL_search_and_free(x);
    }

}

if(root != NULL)
{
    //locates an allocated node if one exists and recursively dives down the trie until none are below
    for(int i = 0; i < 27; i++)
    {
        if(x->children[i] != NULL)
        {
            x = x->children[i];
            NULL_search_and_free(x);
        }
    }

    //sets traversal pointer back up one node in preparation for deleting what's below
    x = x->parent;

    //**deletion process** locates the first occupied node below and deletes it. continues by recursively calling NULL_search.
    for(int i = 0; i < 27; i++)
    {
        if(x->children[i] != NULL)
        {
            free(x->children[i]);
            x->children[i] = NULL;
            NULL_search_and_free(x);
        }
    }
}

1 Answer 1

2

Couldn't do a full, in-depth analysis because I would need to see the node struct declaration and all of the involved functions. However, here's a somewhat common issue. Look at the following code:

for(int i = 0; i < 27; i++)
{
    if(x->children[i] != NULL)
    {
        x = x->children[i];
        NULL_search_and_free(x);
    }
}

Now, say that the trie is completely populated for several levels (no NULL nodes). On the first pass, x points at a level 1 node at the start. When the code steps into the if statement, x is reassigned to a child, or level 2 node by the x = x->children[i]; statement and a recursive call is executed to NULL_search_and_free(x).

Here's the problem. When the recursion returns, x is still at a level 2 node and the remaining level 1 nodes are bypassed.

To correctly call the recursion, the call should have been directly to x->children[i]. X should not have been reassigned to a child node.

There may well be other issues, but this is certainly a major problem. Also, if you have almost identical blocks of code in two places, it should be a red flag that the code could possibly be simplified somehow. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

4
  • Thanks, Cliff. I take your point about not reassigning x. I had originally thought of using parent pointers to traverse back up the structure thereby ending back at root->children[0] before moving on to 'b'. Since tinkering around with the method of recursion call you suggested, most of my thinking about how to navigate around to free nodes seems over complicated as making the recursive call actually navigates up the trie for you.
    – Scott J.
    Jan 4, 2018 at 18:00
  • I am having a similar issue with my code.
    – A Stepe
    Apr 22, 2018 at 21:33
  • @Cliff B I am having a similar issue with my code. However, without reassigning x to point to the next node, how will the following stack access it? I tried to store the address of each preceding node in a variable before calling the next node.
    – A Stepe
    Apr 22, 2018 at 21:43
  • When a function calls itself recursively, each iteration saves its own values, separate and independent of previous calls. Also, remember that parameters are passed by copy. In other words, if the code calls NULL_search_and_free(x->children[i]); the parameter 'x->children[i]' from the parent call will be copied and stored as 'x' in the new child function. Any changes made to the child version of x will have no effect on the parent function's x value. When the process returns to the parent version of the function, all of the variables are still there, unchanged (except for globals).
    – Cliff B
    Apr 22, 2018 at 22:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .