M
Mark
Hello
I've implemented a very simple and small binary-search tree library as a
training exercise. I'm posting it here together with a testing program and
expect to receive critics and useful recommendations
It compiles fine with the following GCC options:
-std=c99 -pedantic -W -Wall -Wcast-align -Wcast-qual -Wmissing-prototypes -Wshadow
-Wnested-externs -Wstrict-prototypes -Waggregate-return -O0 -ggdb
I put in various checkpoints tracing messages which help me to better
understand BST and to debug, it can be disabled with -DWITH_TRACE compiler
flag. I'm yet to decide where to carefully put 'asserts'.
/* tree.h */
#ifndef TREE_H
#define TREE_H
#include <stddef.h> /* for size_t */
/* error codes */
enum {
T_ESUCCESS,
T_EINVALID,
T_EBADPTR,
T_EDUP,
T_ENOMEM,
T_EMPTYTREE
};
struct tree_node {
void *data;
size_t size; /* for future to indicate the data size */
struct tree_node *left;
struct tree_node *right;
};
struct tree_node *tree_allocnode(void *data);
int tree_addnode(struct tree_node **root, struct tree_node *node,
int(*cmp_fn)(const void *d1, const void *d2));
void tree_freenode(struct tree_node *node);
struct tree_node *tree_lookup(struct tree_node *root, const void *data,
int(*cmp_fn)(const void *d1, const void *d2));
void tree_freetree(struct tree_node *node, void (*fn)(void *data));
int tree_traverse(struct tree_node *root,
int(*fn)(struct tree_node *node, void *arg), void *arg);
#endif
/* tree.c */
#ifdef WITH_TRACE
#include <stdarg.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#ifdef WITH_TRACE
#define TRACE(...) (printf("TRACE: "), printf(__VA_ARGS__), printf("\n"))
#else
#define TRACE(...)
#endif
struct tree_node *tree_allocnode(void *data)
{
struct tree_node *node = NULL;
node = malloc(sizeof *node);
if (node != NULL)
{
if (data != NULL)
{
node->data = data;
node->left = node->right = NULL;
TRACE("node @ %p, data=%s", (void *)node, (char *)data);
}
else
{
free(node);
node = NULL;
}
}
return node;
}
int tree_addnode(struct tree_node **root, struct tree_node *node,
int(*cmp_fn)(const void *d1, const void *d2))
{
int res = T_ESUCCESS;
int d;
if (node != NULL)
{
/* empty tree case */
if (NULL == *root)
{
*root = node;
node->left = node->right = NULL;
TRACE("root @ %p", (void *)*root);
}
else
{
d = cmp_fn(node->data, (*root)->data);
if (d < 0)
{
tree_addnode(&(*root)->left, node, cmp_fn);
TRACE("node(%p)->left=%p", (void *)(*root), (void
*)(*root)->left);
}
else if (d > 0)
{
tree_addnode(&(*root)->right, node, cmp_fn);
TRACE("node(%p)->right=%p", (void *)(*root), (void
*)(*root)->right);
}
else /* d == 0, i.e. duplicate entry */
{
res = T_EDUP;
}
}
}
else
{
res = T_EBADPTR;
}
return res;
}
void tree_freenode(struct tree_node *node)
{
if (node != NULL)
{
if (node->data != NULL)
{
free(node->data);
}
free(node);
}
}
struct tree_node *tree_lookup(struct tree_node *root, const void *data,
int(*cmp_fn)(const void *d1, const void *d2))
{
struct tree_node *node = NULL;
int d;
if (root != NULL)
{
d = cmp_fn(data, root->data);
if (d > 0)
{
return tree_lookup(root->right, data, cmp_fn);
}
else if (d < 0)
{
return tree_lookup(root->left, data, cmp_fn);
}
else
{
node = root;
TRACE("node found %p", (void *)node);
}
}
return node;
}
void tree_freetree(struct tree_node *node, void (*fn)(void *data))
{
if (node != NULL)
{
if (fn != NULL)
{
fn(node->data);
}
TRACE("deleting node(%p)->left=%p", (void *)node, (void
*)node->left);
tree_freetree(node->left, fn);
TRACE("deleting node(%p)->right=%p", (void *)node, (void
*)node->right);
tree_freetree(node->right, fn);
free(node);
}
}
int tree_traverse(struct tree_node *root,
int(*fn)(struct tree_node *root, void *arg), void *arg)
{
int res = T_ESUCCESS;
if (root != NULL)
{
tree_traverse(root->left, fn, arg);
fn(root, arg);
tree_traverse(root->right, fn, arg);
}
else
{
res = T_EMPTYTREE;
}
return res;
}
/* tree-test.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"
static int tdata1[] = { 10, 6, 900, 7, 1, 57, 928, 1, 987 };
static char *tdata[] = { "yellow", "apple", "chess", "penguin", "car",
"mixer", "Zoo", "loop", "zebra" };
#define DNUM (sizeof(tdata) / sizeof(tdata[0]))
static int comp(const void *d1, const void *d2)
{
int res;
res = strcmp((const char *)d1, (const char *)d2);
if (res > 0) {
printf("%s > %s\n", (const char *)d1, (const char *)d2);
return 1;
} else if (res < 0) {
printf("%s < %s\n", (const char *)d1, (const char *)d2);
return -1;
} else {
printf("%s = %s\n", (const char *)d1, (const char *)d2);
return 0;
}
}
static int comp1(const void *d1, const void *d2)
{
if (*(const int *)d1 < *(const int *)d2) {
printf("%d < %d\n", *(const int *)d1, *(const int *)d2);
return -1;
}
else if (*(const int *)d1 > *(const int *)d2) {
printf("%d > %d\n", *(const int *)d1, *(const int *)d2);
return 1;
}
else { /* if (*(const int *)d1 == *(const int * )d2) */
printf("%d = %d\n", *(const int *)d1, *(const int *)d2);
return 0;
}
}
static int walk(struct tree_node *node, void *arg)
{
printf(arg, (char *)node->data);
return 0;
}
int main(void)
{
struct tree_node *tptr, *root = NULL;
unsigned int i;
puts("Populating the tree...\n");
for (i = 0; i < DNUM; i++) {
puts("-------------------------------------");
tptr = tree_allocnode(tdata);
if (NULL == tptr)
{
puts("Failed to allocate memory!");
exit(EXIT_FAILURE);
}
tree_addnode(&root, tptr, comp);
}
puts("Traversing the tree...\n");
tree_traverse(root, walk, "data=%s\n");
printf("found node %p\n", (void *)tree_lookup(root, tdata[3], comp));
puts("Destroying the tree...\n");
tree_freetree(root, NULL);
puts("Traversing the tree...\n");
tree_traverse(root, walk, "data=%s\n");
return 0;
}
I've implemented a very simple and small binary-search tree library as a
training exercise. I'm posting it here together with a testing program and
expect to receive critics and useful recommendations
It compiles fine with the following GCC options:
-std=c99 -pedantic -W -Wall -Wcast-align -Wcast-qual -Wmissing-prototypes -Wshadow
-Wnested-externs -Wstrict-prototypes -Waggregate-return -O0 -ggdb
I put in various checkpoints tracing messages which help me to better
understand BST and to debug, it can be disabled with -DWITH_TRACE compiler
flag. I'm yet to decide where to carefully put 'asserts'.
/* tree.h */
#ifndef TREE_H
#define TREE_H
#include <stddef.h> /* for size_t */
/* error codes */
enum {
T_ESUCCESS,
T_EINVALID,
T_EBADPTR,
T_EDUP,
T_ENOMEM,
T_EMPTYTREE
};
struct tree_node {
void *data;
size_t size; /* for future to indicate the data size */
struct tree_node *left;
struct tree_node *right;
};
struct tree_node *tree_allocnode(void *data);
int tree_addnode(struct tree_node **root, struct tree_node *node,
int(*cmp_fn)(const void *d1, const void *d2));
void tree_freenode(struct tree_node *node);
struct tree_node *tree_lookup(struct tree_node *root, const void *data,
int(*cmp_fn)(const void *d1, const void *d2));
void tree_freetree(struct tree_node *node, void (*fn)(void *data));
int tree_traverse(struct tree_node *root,
int(*fn)(struct tree_node *node, void *arg), void *arg);
#endif
/* tree.c */
#ifdef WITH_TRACE
#include <stdarg.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#ifdef WITH_TRACE
#define TRACE(...) (printf("TRACE: "), printf(__VA_ARGS__), printf("\n"))
#else
#define TRACE(...)
#endif
struct tree_node *tree_allocnode(void *data)
{
struct tree_node *node = NULL;
node = malloc(sizeof *node);
if (node != NULL)
{
if (data != NULL)
{
node->data = data;
node->left = node->right = NULL;
TRACE("node @ %p, data=%s", (void *)node, (char *)data);
}
else
{
free(node);
node = NULL;
}
}
return node;
}
int tree_addnode(struct tree_node **root, struct tree_node *node,
int(*cmp_fn)(const void *d1, const void *d2))
{
int res = T_ESUCCESS;
int d;
if (node != NULL)
{
/* empty tree case */
if (NULL == *root)
{
*root = node;
node->left = node->right = NULL;
TRACE("root @ %p", (void *)*root);
}
else
{
d = cmp_fn(node->data, (*root)->data);
if (d < 0)
{
tree_addnode(&(*root)->left, node, cmp_fn);
TRACE("node(%p)->left=%p", (void *)(*root), (void
*)(*root)->left);
}
else if (d > 0)
{
tree_addnode(&(*root)->right, node, cmp_fn);
TRACE("node(%p)->right=%p", (void *)(*root), (void
*)(*root)->right);
}
else /* d == 0, i.e. duplicate entry */
{
res = T_EDUP;
}
}
}
else
{
res = T_EBADPTR;
}
return res;
}
void tree_freenode(struct tree_node *node)
{
if (node != NULL)
{
if (node->data != NULL)
{
free(node->data);
}
free(node);
}
}
struct tree_node *tree_lookup(struct tree_node *root, const void *data,
int(*cmp_fn)(const void *d1, const void *d2))
{
struct tree_node *node = NULL;
int d;
if (root != NULL)
{
d = cmp_fn(data, root->data);
if (d > 0)
{
return tree_lookup(root->right, data, cmp_fn);
}
else if (d < 0)
{
return tree_lookup(root->left, data, cmp_fn);
}
else
{
node = root;
TRACE("node found %p", (void *)node);
}
}
return node;
}
void tree_freetree(struct tree_node *node, void (*fn)(void *data))
{
if (node != NULL)
{
if (fn != NULL)
{
fn(node->data);
}
TRACE("deleting node(%p)->left=%p", (void *)node, (void
*)node->left);
tree_freetree(node->left, fn);
TRACE("deleting node(%p)->right=%p", (void *)node, (void
*)node->right);
tree_freetree(node->right, fn);
free(node);
}
}
int tree_traverse(struct tree_node *root,
int(*fn)(struct tree_node *root, void *arg), void *arg)
{
int res = T_ESUCCESS;
if (root != NULL)
{
tree_traverse(root->left, fn, arg);
fn(root, arg);
tree_traverse(root->right, fn, arg);
}
else
{
res = T_EMPTYTREE;
}
return res;
}
/* tree-test.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"
static int tdata1[] = { 10, 6, 900, 7, 1, 57, 928, 1, 987 };
static char *tdata[] = { "yellow", "apple", "chess", "penguin", "car",
"mixer", "Zoo", "loop", "zebra" };
#define DNUM (sizeof(tdata) / sizeof(tdata[0]))
static int comp(const void *d1, const void *d2)
{
int res;
res = strcmp((const char *)d1, (const char *)d2);
if (res > 0) {
printf("%s > %s\n", (const char *)d1, (const char *)d2);
return 1;
} else if (res < 0) {
printf("%s < %s\n", (const char *)d1, (const char *)d2);
return -1;
} else {
printf("%s = %s\n", (const char *)d1, (const char *)d2);
return 0;
}
}
static int comp1(const void *d1, const void *d2)
{
if (*(const int *)d1 < *(const int *)d2) {
printf("%d < %d\n", *(const int *)d1, *(const int *)d2);
return -1;
}
else if (*(const int *)d1 > *(const int *)d2) {
printf("%d > %d\n", *(const int *)d1, *(const int *)d2);
return 1;
}
else { /* if (*(const int *)d1 == *(const int * )d2) */
printf("%d = %d\n", *(const int *)d1, *(const int *)d2);
return 0;
}
}
static int walk(struct tree_node *node, void *arg)
{
printf(arg, (char *)node->data);
return 0;
}
int main(void)
{
struct tree_node *tptr, *root = NULL;
unsigned int i;
puts("Populating the tree...\n");
for (i = 0; i < DNUM; i++) {
puts("-------------------------------------");
tptr = tree_allocnode(tdata);
if (NULL == tptr)
{
puts("Failed to allocate memory!");
exit(EXIT_FAILURE);
}
tree_addnode(&root, tptr, comp);
}
puts("Traversing the tree...\n");
tree_traverse(root, walk, "data=%s\n");
printf("found node %p\n", (void *)tree_lookup(root, tdata[3], comp));
puts("Destroying the tree...\n");
tree_freetree(root, NULL);
puts("Traversing the tree...\n");
tree_traverse(root, walk, "data=%s\n");
return 0;
}