freeing memory causing segmentation fault 11

Question

I'm trying to create a binary search tree. This is my node initialization function:

node_t* node_init(int val){
        node_t* n1 = malloc(sizeof(node_t));
        n1->value = val;
        n1->leftNode = NULL;
        n1->rightNode = NULL;

        return n1;
}

Since I'm malloc'ing memory, I know I should be freeing it somewhere else. I do so in my main method:

int main(){
        tree_t t1;
        tree_init(&t1);
        
        node_t* n1 = node_init(5);

        node_t* n2 = node_init(7);
        

        t1.count += add(n1, &(t1.root));
        t1.count += add(n2, &(t1.root));

        //free(n1);
        //free(n2);
        
        print_tree(t1.root);
}

Yet, when I uncomment the freeing lines, I get a segmentation fault error. I'm not sure why that Is the case since I must free the memory once it's been allocated. I don't do any freeing in my add function, and the code prints out a valid binary search tree without the free statements.

If it helps, here is my add function:

int add(node_t* n, node_t** tn){
        if(*tn == NULL){*tn = n; return 1;}
        if(n->value < (*tn)->value){add(n, &((*tn)->leftNode));}
        else if (n->value > (*tn)->value){add(n, &((*tn)->rightNode));}
        else{return 0;}
}

Once you free the nodes, you may not access them again. It seems reasonable to think that `print_tree` would attempt to access the nodes in the tree, so you must not free them before calling that function. — John Bollinger, Jun 06 '21 at 17:02
Typically, one would free all the nodes in the tree by traversing the tree to find them, not by retaining and using separate pointers to them. Either way can work, but the latter requires maintaining extra data structures. — John Bollinger, Jun 06 '21 at 17:03

score 3 · Accepted Answer · answered Jun 06 '21 at 17:07

3

For starters the function add has undefined behavior because in some paths of execution it returns nothing.

You need to write

int add(node_t* n, node_t** tn){
        if(*tn == NULL){*tn = n; return 1;}
        if(n->value < (*tn)->value){ return add(n, &((*tn)->leftNode));}
        else if (n->value > (*tn)->value){ return add(n, &((*tn)->rightNode));}
        else{return 0;}
}

These statements with calls of free

    free(n1);
    free(n2);

do not set n1 and n2 to NULL in the tree. So this call

    print_tree(t1.root);

invokes undefined behavior.

answered Jun 06 '21 at 17:07

Vlad from Moscow

301,070
26
186
335

Understood! Sorry, you said the free calls "do not set n1 and n2 to NULL in the tree?" So what are they set to, and why does printing the tree invoke undefined behavior? – rjc810 Jun 06 '21 at 17:12
1

@rjc810 The function free just frees the memory pointed to by the pointer used as an argument.. The original pointer itself used as an argument is not changed. So in the function print_tree you are using the pointers n1 and n2 to access memory that was already freed. – Vlad from Moscow Jun 06 '21 at 17:15
In your answer, you wrote: `"the function add has undefined behavior because in some paths of execution it returns nothing."` -- This statement is not quite correct. In contrast to C++, this does not cause undefined behavior in C. See [this question](https://stackoverflow.com/q/1610030/12149471) for further information. – Andreas Wenzel Jun 06 '21 at 17:18
@AndreasWenzel There is used the return value of the function like t1.count += add(n1, &(t1.root)); – Vlad from Moscow Jun 06 '21 at 17:19
@VladfromMoscow: Yes, accessing the non-existant return value is what causes the undefined behavior in C. Therefore, the undefined behavior is not caused by the function `add`, but rather by the function `main`. – Andreas Wenzel Jun 06 '21 at 17:21
@AndreasWenzel It seems you do not understand the answer in the provided by you reference. There is written that in such a case except main there is undefined behavior. "This code has formally undefined behaviour" – Vlad from Moscow Jun 06 '21 at 17:27
@VladfromMoscow: What do you mean by "the answer"? The question I linked to has 9 answers. Do you mean the accepted answer? That answer talks mainly about C++, and only mentions that the situation is different in C, without stating in what way it is different. – Andreas Wenzel Jun 06 '21 at 18:11
@VladfromMoscow: [§6.9.1 ¶12 of the ISO C11 standard](http://port70.net/~nsz/c/c11/n1570.html#6.9.1p12) clearly states that what I said is correct, namely that the undefined behavior is not invoked by the function `add` not returning a value, but rather by the function `main` accessing the non-existant return value. Note that this question is tagged C, not C++. – Andreas Wenzel Jun 06 '21 at 18:12
@AndreasWenzel This quote does not mean that if a function has a non-void return type and returns nothing then the behavior of the function is defined. If a function has a non-void return type then its return statements shall return an expression. – Vlad from Moscow Jun 06 '21 at 18:28
@VladfromMoscow: Yes, you are right that according to [§6.8.6.4 ¶1](http://port70.net/~nsz/c/c11/n1570.html#6.8.6.4p1), if there is an explicit `return` statement, then it must contain a return value. However, this does not apply if there is no explicit return statement, but instead the `}` which terminates the function is reached. In that case, [§6.9.1 ¶12](http://port70.net/~nsz/c/c11/n1570.html#6.9.1p12) applies. – Andreas Wenzel Jun 06 '21 at 18:39
@AndreasWenzel I have not found in the Standard how the behavior of a function is defined that does not return explicitly something though having a non-void return type. – Vlad from Moscow Jun 06 '21 at 18:51

freeing memory causing segmentation fault 11

1 Answers1