patterncMinor
Does this C binary search tree have memory leaks?
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
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
pointer itself, not the size of what it points to. try it with some long
words. Your word copying could either use
write your own.
In
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.
In
new_node, your word-copying is wrong as you use sizeof(nword) wherenword is a pointer. Using sizeof on a pointer gives only the size of thepointer 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.