pset5 2017 unload() trie segmentation fault and undefined behavior

Question

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

Answer 1

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