Does this C binary search tree have memory leaks?

Question

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 <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 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 BST.
 */
void node_additem(node *root, node *n) {
    int comp = strcmp(root->word, n->word);

    node **target = (comp > 0) ? &(root->left) : &(root->right);

    if (*target == NULL) 
        node_setlink(target, n);
    else
        node_additem(*target, n);
}

/* Traverse the BST in order, dumping the words to standard out.
 * No side effects.
 */
void node_traverse(node *root) {
    if (root->left != NULL)
        node_traverse(root->left);

    printf("%s\n", root->word);

    if (root->right != NULL)
        node_traverse(root->right);
}

/* Go through each argument, adding it to the tree. Then traverse the tree. Then
 * free the tree.
 */
int main(int argc, char **argv) {
    if (argc < 3) {
        printf("Please give me two arguments, or there won't be anything to sort!");
        return 1;
    }

    node *n;

    node_setlink(&n, node_new(argv[1]));

    for (int i = 2; i < argc; i++) {
        node_additem(n, node_new(argv[i]));
    }

    node_traverse(n);
    printf("n is %s %d\n", n->word, n->refs);
    printf("%d removed when n freed.\n", node_del(n));

    return 0;
}

Answer 1

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.