CODEWITHSUNDEEP
cmemory-managementmemory-leaks
brvh
brvh

Reputation: 296

memory leak despite freeing struct

I'm having trouble with a memory leak, I am constructing a BST in C and need to free a BST. My BST_element:

typedef struct _BST_Node {
char* name;
char* public_key_file;
struct _BST_Node *left, *right;
} BST_Node;

My allocation function: 

BST_Node* new_BSTNode(char* name, char* public_key_file) {

BST_Node* node =  malloc(sizeof(BST_Node));
node->name = malloc((strlen(name) + 1) * sizeof(char));
node->public_key_file = malloc((strlen(public_key_file) + 1) * sizeof(char));
node->left = calloc(1,sizeof(BST_Node));
node->right = calloc(1,sizeof(BST_Node));

//check if allocation was correct
if (!node || !node->name || !node->public_key_file || !node->left || !node->right) {
    printf(ALLOCATION_ERROR_MSG);
    exit(ALLOCATION_ERROR);
}

//copy strings into struct
strcpy(node->name,name);
strcpy(node->public_key_file,public_key_file);

return node;

}

And the function responsible for freeing the allocated memory:

void free_BST(BST_Node** node) {

//free the children:
if(!((*node)->right->name==NULL))
    free_BST(&((*node)->right));
else free((*node)->right);

if(!((*node)->left->name==NULL))
    free_BST(&((*node)->left));
else free((*node)->left);

//free strings
free((*node)->public_key_file);
free((*node)->name);

free(*node);
}

I think the node** is not necessary, however this is an exam question so I'm not allowed to change the declaration.

My test case:

{
BST_Node* foo1 = new_BSTNode("hi","my");
BST_Node* foo2 = new_BSTNode("name","is");
foo1->left = foo2;
free_BST(&foo1);
}

The memory leak is foo1 according to VS. However in my destructor function, I explicitly free this struct? How can I solve this?

Upvotes: 2

Views: 212

Answers (2)

user3629249
user3629249

Reputation: 16540

there are several problems with the free operation.

For an example, lets say the 'current' node is at the very end of the chain of nodes, on the right end.

Then the conditions would be:

currentNode->name != NULL
currentNode->public_key_file != NULL
currentNode->right = NULL
currentNode->left != NULL

The first line in the free_BST() function asks:

is the currentNode->right->name != NULL

however, because currentNode->right is NULL, this will be accessing some very low address in memory. An address that has nothing to do with the chain of nodes!

Due to the address being in very low memory, there is a good chance the reading of that address will trigger a seg fault event.

For this particular problem with the code, suggest only looking at 

if( NULL != currentNode->right )
then 
    free name, 
    free public_key_file,         
    free currentNode

There is a similar problem when traversing left through the nodes

In other words, do not access data fields in anything other than the current node, as that 'other' node might not exist

Upvotes: 0

unwind
unwind

Reputation: 399881

You shouldn't set left and right pointers to anything but NULL when creating a new node.

You don't know which nodes are going to be needed, so it's rather bad form to always allocate, and it makes things confusing.

Allocate the needed child node(s) when doing insert on the tree, instead.

Upvotes: 6

Related Questions