HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Does this C binary search tree have memory leaks?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thissearchbinarydoesmemoryleakshavetree

Problem

I am new to C, so I have been trying to get practice doing some coding.

Usually I use languages like Java, python, ruby, etc: Garbage collected languages. So manually cleaning up is new to me and I would appreciate any advice on whether there are major flaws in my approach.

Also any other comments on the overall idomatic-ness of this code, and things that I need to watch out for as I try to learn more C. (If it matters, I am compiling this to the c99 standards)

```
#include
#include
#include

/ a reference counted BST node... /
typedef struct _node node;
struct _node {
char *word;
unsigned int refs;
node *left;
node *right;
};

/* allocate a node onto the heap.
* copy word into a new array so that it can free it when it wants to
* later without fear of clobbering another node's string.
*
* TODO: Maybe implement word counting so that if someone else adds a
* word that's already in the tree, I don't need to store two
* instances.
*/
node node_new(char word) {
node *n = malloc(sizeof(node));

char *nword = malloc(strlen(word) + 1);
memcpy(nword, word, sizeof(nword));
n->word = nword;

n->refs = 0;
n->left = NULL;
n->right = NULL;

return n;
}

/* Decrement the references and if it is determined that no one holds
* a ref to this object, then free it and check its children.
*
* Return the number of nodes freed in this manner. If this node has
* referents, then return 0 since no nodes were freed.
*/
int node_del(node *n) {
n->refs -= 1;

if (n->refs > 0) return 0;

int removed = 1;

if (n->left != NULL)
removed += node_del(n->left);

if (n->right != NULL)
removed += node_del(n->right);

free(n->word);
free(n);

return removed;
}

/* replace link with n.
* Cleans up link if needed.
*/
void node_setlink(node **link, node *n) {
if (*link != NULL) {
node_del(*link);
}

n->refs += 1;
*link = n;
}

/* Add a node to the BS

Solution

The code looks nice. Just a few comments:

In new_node, your word-copying is wrong as you use sizeof(nword) where
nword is a pointer. Using sizeof on a pointer gives only the size of the
pointer itself, not the size of what it points to. try it with some long
words. Your word copying could either use strdup or if you don't have that,
write your own.

In main, set n to NULL before using it.

There are no checks for malloc failure. It is good practice to check, but the
only thing one can do is often to exit.

It is best to avoid leading underscore on identifiers (they are reserved). And it is generally better to use explicit braces around statements even when strictly unnecessary.

Context

StackExchange Code Review Q#30486, answer score: 2

Revisions (0)

No revisions yet.