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;
}