Setting pointer to NULL after free in quirky data structures (C)

Question

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.

Answer 1

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.