0

I have the following following somewhat convoluted data structures: a binary tree made up of nodes, and a linked list of items, each item storing tree nodes. If a Node is created, then it will certainly be used in a Tree, in a List, or both. Here are the data structures:

typedef struct Node Node;
typedef struct Item Item;

struct Node {
    int key;
    Node *left;
    Node *right;
};

typedef struct {
    Node *root;
} Tree;

struct Item {
    Node *value;
    Item *next;
};

typedef struct {
    Item *head;
} List;

I am having trouble free'ing my tree and list. Logically, I would first free the Tree, and then the List. My idea was to set the Node pointers to NULL after freeing them in order for the List to decide whether the current Item has non-NULL nodes which must be free'd.

Here is how the Tree is free'd:

void tree_free_helper(Node *node)
{
    if (node) {
        tree_free_helper(node->left);
        tree_free_helper(node->right);
        free(node);
        node = NULL;
    }
}

void tree_free(Tree *tree)
{
    if (tree) {
        tree_free_helper(tree->root);
        free(tree);
    }    
}

This works fine if Nodes only belong to a Tree. However, when a Node is also stored in a List Item, I get one extra free call = number of mallocs + 1. Here is how I free a List:

void list_free(List *list)
{
    Item *p, *q;

    if (!list) return;

    p = list->head;
    while (p) {
        q = p;
        p = p->next;
        if (q->value) // trying to free only non-free'd nodes
            free(q->value);
        free(q);
    }

    free(list);
}

Valgrind dutifully informs me that Address 0x52040e0 is 0 bytes inside a block of size 24 free'd, and where in my code the block 0x52040e0 was alloc'd at. Here's a simple example for which I get this valgrind report, where I create 3 nodes for a Tree (n1 being the root and having n0 as left child and n2 as right child); the problem comes from appending one of the nodes (n0 in this example) to a List:

int main() {
    List *list = list_create();
    Tree *tree = tree_create();

    Node *n0 = node_create(0);
    Node *n1 = node_create(1);
    Node *n2 = node_create(2);

    tree->root = n1;
    n1->left = n0;
    n1->right = n2;

    list_append(list, n0);

    tree_free(tree);
    list_free(list);
}

Note: list_create, tree_create, and node_create respectively create a List, a Tree, and a Node. list_append creates an Item that is added to the list, and the item stores the Node passed as argument.

So my question is: seeing that setting the node pointer to NULL after I free it does not seem to have any effect, as if (q->value) always evaluates to true in list_free, what am I doing wrong? Thank you for any insight.

Improve this question
4
  • It doesn't make sense to check for NULL in your free() function if you ignore that allocation might actually produce a NULL. Commented Mar 7, 2018 at 15:59
  • Pardon if this detail was buried somewhere in there (I couldn't find it). Are the same nodes pointed to by both structures? By the looks of the code in main, it seems so. If so, you need to decide which "owns" them (the tree or the list). The one that doesn't shouldn't be freeing their node, but should still be removing their List (or Tree) matching the corresponding Node from their respective formal structures. Commented Mar 7, 2018 at 16:02
  • @IharobAlAsimi I do check for the return value of malloc in my ..._create functions. The check for NULL in list_free is meant to check whether the current item in the list still contains a valid reference to a node, and in this case free the node (i.e. the node was never in the tree). Commented Mar 7, 2018 at 16:04
  • @WhozCraig Yes, indeed, some nodes are pointed to by both structures. I decided on the Tree owning the Nodes, in which case the List only removes (frees) Nodes that do not belong to the Tree. It is a bit convoluted, I know. Commented Mar 7, 2018 at 16:27

1 Answer 1

Reset to default
3

You are not setting the pointer to NULL really,

void tree_free_helper(Node *node)
{
    if (node) {
        tree_free_helper(node->left);
        tree_free_helper(node->right);
        free(node);
        node = NULL;
    }
}

only sets the local node pointer to NULL, you would need something like the following

void tree_free_helper(Node **node)
{
    if (node && *node) {
        tree_free_helper(&(*node)->left);
        tree_free_helper(&(*node)->right);
        free(*node);
        *node = NULL;
    }
}

Pointer variables and parameters just like any other variables and parameters are allocated in the stack frame of the function so they have a life time equal to that of the function, so when you set node to NULL you are actually only setting the variable node to NULL and not the pointer itself.

If you want to set the pointer, you have to pass it's address — or a pointer to the pointer — instead to be able to modify it inside the function.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

if (node) should probably be if (node && *node ) in your code.
Oh! I understand! Thanks for pointing this out, now it makes sense come to think of it. I am now calling tree_free_helper from tree_free like this: tree_free_helper(&(tree->root));. Unfortunately, valgrind still shows me 7 allocs and 8 frees with the same culprit (the node being appended to the list).
If you call valgrind with the right switches it will tell you where the alloc was. And that way you can track the leak. Also compile with debug symbols.
@IharobAlAsimi It isn't a leak; it's a double-free (seven allocs, eight frees), likely because of the reason I commented on below the OP post.
I'm using it with --leak-check=full (not sure if this is what you had in mind). I'll get into it and come back here when (if?) I manage to solve the problem.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.