Standard C - Crashing at malloc (despite working ~10 minutes ago)

Question

Not sure what is going on with my code. Was implementing a simple binary search tree and got everything to work - had no problem inserting a bunch of elements. Then, while trying to add some file IO functionalities, all of the sudden my program was crashing. I thought perhaps I had messed something up with the file pointers and writing (though that doesn't really make sense either, since it leaves the rest of the code untouched), so I pulled up an archived version of the code, and BAM - crashing after 2 inputs even though it was fully working the last time I tried it!

Adding a bunch of debug print statements (sorry still need to learn to use the debugger), it seems the crash most often occurs at my malloc - but sometimes it randomly crashes at different points if I keep rerunning the program too.

I'm really confused by this. How is it that I was able to insert ~10 elements and now I somehow cant even insert 3? Task manager says I have ~4Gb of RAM free, and it's not like I'm doing some massive amount of inputs - this should cost memory absolutely nothing. Also how is it crashing in different places even though I'm running the exact same code?

I'd be very grateful for any insights. Running Windows 10, Codeblocks as the IDE. Code for the main and the function in question below. In most of my runs, the program crashes before the third insert reaches "Space Allocated", but sometimes it manages to insert it - and then the program crashes anyways, for no apparent reason.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct node *BSTREE;


struct node
{
    int data;
    BSTREE left;
    BSTREE right;
};


BSTREE insert(BSTREE root, int number);
BSTREE find(BSTREE root, int number);
void inOrderTraversal(BSTREE subtree);

int main(){
    BSTREE root = NULL;

    root = (insert(root, 2));
    insert(root, 4);
    insert(root, 1);
}

BSTREE insert(BSTREE root, int number)
{
    printf("\n\nInside insert");

    BSTREE temp = NULL;

    if(!(root)){
    printf("\nInside empty root");


    temp = (BSTREE*)malloc(sizeof(BSTREE));
    printf("\nSpace allocated");


    temp->left = NULL;
    temp->right = NULL;
    printf("\nleft and right set to null");


    temp->data = number;
    printf("\n data set to number");


    root = temp;

    printf("\nroot is now temp; Before returning root");
    printf("\n node data: %d %d %d", root->data, root->left, root->right);

    return root;
    }


    if(number < root->data){
        root->left = (insert(root->left, number));
    }
    else if(number > root->data){
        root->right = (insert(root->right, number));
    }
    else if(number == root->data){
        return root;
    }
}

Answer 1

The line:

 temp = (BSTREE*)malloc(sizeof(BSTREE));

is an excellent example of why Is it a good idea to typedef pointers? recommends 'No'.

You have two problems:

1. You're allocating a pointer to a pointer to a struct node to a pointer to a struct node — you don't need the * in the cast (and there are those who'd argue you don't need to cast the result of malloc()).

2. You're only allocating enough space for a pointer but you're using it as if it was big enough to hold a struct node; it isn't.

The basic fix is one of these lines:

temp = (BSTREE)malloc(sizeof(struct node));
temp = malloc(sizeof(*temp));

There isn't a way to use BSTREE in the first sizeof operator that I can think of. The second is actually a sound technique; it remains valid even if the type of temp changes. You can create various hybrids too.

I'd recommend using:

typedef struct BSTree BSTree;
struct BSTree
{
    int     data;
    BSTree *left;
    BSTree *right;
};

and then you'd write:

BSTree *temp;

temp = (BSTree *)malloc(sizeof(BSTree));
temp = malloc(sizeof(*temp));

You might note that the second alternative hasn't changed.

Answer 2

It seems as you are not returning the memory that you reserve with malloc. When using dynamic memory, it's important to release it again, otherwise you'll have a so called memory leak and the size will just increase until program crashes.

Function for releasing (freeing) memory is free();

A call should look something like free(temp);

I can not try it to make sure because I don't have your library used so I can't guarantee it works, but I hope it solves it.