C malloc stack vs heap issue

Question

I am implementing the insert function of a binary search tree in C and I am encountering a problem with malloc.

First of all, I have a Tree and Node struct

typedef struct Node {
    double value;

    struct Node *parent;
    struct Node *right_child;
    struct Node *left_child;
} Node;

typedef struct Tree {
    struct Node *root;
} Tree;

And here is my insert function to insert a value into the tree.

void insert(Tree *t, double v) {

    Node *n = malloc(sizeof(Node));
    n->left_child = malloc(sizeof(Node));
    n->right_child = malloc(sizeof(Node));
    n->parent = malloc(sizeof(Node));
    n->value=v;

    Node *x = t->root, *y = NULL;

    //follow tree down until we reach a leaf of the tree
    while (x) {

        //save last non-NULL value. We will insert node n as a child to this leaf.
        y = x;

        if (n->value < x->value) {
            x = x->left_child;
        } else {
            x = x->right_child;
        }
    }

    //The parent of the node to insert is the leaf we reached
    n->parent = y;

    //If n is greater than y then it is its right child and vice-versa.
    if (n->value > y->value) {
        y->right_child = n;
    } else {
        y->left_child = n;
    }

}

And my main method

int main(void) {

    Node n1;

    n1.value = 4;
    n1.parent = NULL;
    n1.left_child = NULL;
    n1.right_child = NULL;

    Tree t;

    t.root = &n1;

    insert(&t,2.0);

    printf("In order traversal\n");
    inOrderTraversalNode(t.root);

    return EXIT_SUCCESS;
}

When I print the in-order traveral code I get undefined behavior (eg: 26815615859885194199148049996411692254958731641184786755447122887443528060147093953603748596333806855380063716372972101707507765623893139892867298012168192.000000) instead of the correct traversal.

I am pretty sure the problem is the Node creation in the insert method. I assume the problem is that the new node exists on the stack which is then being destroyed when the insert function exits - which is what is causing the undefined behaviour during the traversal. However, I thought that malloc stores the variable on the heap and makes it available globally. Or perhaps the node is on the heap but the pointer is on the stack? Could someone show me where I am going wrong here?

I see that `main` creates a `Node` and initializes the pointers to `NULL`, but when `insert` creates a `Node`, it initializes the pointers by calling `malloc`. However, the `Node` returned by `malloc` is itself not initialized. — user3386109, Sep 22 '15 at 02:33

score 1 · Accepted Answer · answered Sep 22 '15 at 02:33

1

The initial contents in the memory allocated via malloc is undefined.

Firstly, remove n->parent = malloc(sizeof(Node));, which causes memory leak.

Secondly, change

  n->left_child = malloc(sizeof(Node));
  n->right_child = malloc(sizeof(Node));

to

  n->left_child = NULL;
  n->right_child = NULL;

so that the program can correctly recognize the leaf.

answered Sep 22 '15 at 02:33

MikeCAT

73,922
11
45
70

Thank you this seems to work. I had read on this post http://stackoverflow.com/questions/14768230/malloc-for-struct-and-pointer-in-c To allocate memory for the pointer in the struct separately – user1893354 Sep 22 '15 at 02:54

score 1 · Answer 2 · answered Sep 22 '15 at 02:33

Try using calloc instead of malloc. The problem is that malloc doesn't initialize values to zero, it only allocates the space. calloc zeros out the space you're requesting. So, you're getting jumped to a random part of memory occasionally when you get to a pointer that isn't valid, but isn't NULL either.

malloc and friends definitely allocate on the heap, you've got that thinking right; what they return is a pointer to a space in memory of at least the size you requested that is definitely safe to read from and write to. However, since the value isn't zeroed out to begin with when you use malloc, you aren't able to guarantee that the pointer stored in your struct is actually to a valid location.

EDIT: also, other poster is right: there is definitely a memory leak with what you're doing. Didn't catch that.

C malloc stack vs heap issue

2 Answers2