1.1 --- a/CMakeLists.txt	Fri Sep 21 18:42:49 2012 -0500
     1.2 +++ b/CMakeLists.txt	Wed Sep 26 13:11:09 2012 -0500
     1.3 @@ -72,3 +72,7 @@
     1.4    ${list_SRCS}
     1.5    )
     1.6  
     1.7 +set (bst_SRCS src/bst.h src/bst.c src/bst_test.c)
     1.8 +add_executable (bst_test
     1.9 +  ${bst_SRCS}
    1.10 +  )

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/bst.c	Wed Sep 26 13:11:09 2012 -0500
     2.3 @@ -0,0 +1,190 @@
     2.4 +#include <stdio.h>
     2.5 +#include <stdlib.h>
     2.6 +
     2.7 +#include "bst.h"
     2.8 +
     2.9 +// Private functions.
    2.10 +void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data));
    2.11 +void * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
    2.12 +void * bst_node_minimum(struct bst_node * node);
    2.13 +void * bst_node_maximum(struct bst_node * node);
    2.14 +
    2.15 +////////////////////////////////////////////////////////////////////////////////
    2.16 +struct bst *
    2.17 +bst_new(bool (*le)(void * a, void * b),
    2.18 +	bool (*eq)(void * a, void * b))
    2.19 +   {
    2.20 +   if ( (NULL == le) || (NULL == eq) )
    2.21 +      return NULL;
    2.22 +
    2.23 +   struct bst * bst = malloc(sizeof(struct bst));
    2.24 +   if (NULL == bst)
    2.25 +      return NULL;
    2.26 +
    2.27 +   bst->root = NULL;
    2.28 +   bst->size = 0;
    2.29 +   bst->le = le;
    2.30 +   bst->eq = eq;
    2.31 +   return bst;
    2.32 +   }
    2.33 +
    2.34 +
    2.35 +////////////////////////////////////////////////////////////////////////////////
    2.36 +void
    2.37 +bst_delete(struct bst * bst)
    2.38 +   {
    2.39 +   if (NULL == bst) return;
    2.40 +   if (0 < bst->size)
    2.41 +      {
    2.42 +      // Walk the tree and delete the nodes.
    2.43 +      // This will cause memory leaks, so hopefully the user has already
    2.44 +      // emptied the tree.
    2.45 +      }
    2.46 +   free(bst);
    2.47 +   }
    2.48 +
    2.49 +////////////////////////////////////////////////////////////////////////////////
    2.50 +void *
    2.51 +bst_insert(struct bst * bst, void * data)
    2.52 +   {
    2.53 +   if ( (NULL == bst) || (NULL == data) )
    2.54 +      return NULL;
    2.55 +
    2.56 +   struct bst_node * new = malloc(sizeof(struct bst_node));
    2.57 +   if (NULL == new)
    2.58 +      return NULL;
    2.59 +   new->left = new->right = new->parent = NULL;
    2.60 +   new->data = data;
    2.61 +
    2.62 +   if (NULL == bst->root)
    2.63 +      {
    2.64 +      bst->root = new;
    2.65 +      return new->data;
    2.66 +      }
    2.67 +
    2.68 +   struct bst_node * p = NULL;
    2.69 +   struct bst_node * c = bst->root;
    2.70 +
    2.71 +   while (NULL != c)
    2.72 +      {
    2.73 +      p = c;
    2.74 +      if (bst->le(new->data, c->data))
    2.75 +	 c = c->left;
    2.76 +      else
    2.77 +	 c = c->right;
    2.78 +      }
    2.79 +   new->parent = p;
    2.80 +   if (bst->le(new->data, p->data))
    2.81 +      p->left = new;
    2.82 +   else
    2.83 +      p->right = new;
    2.84 +
    2.85 +   return new->data;
    2.86 +   }
    2.87 +
    2.88 +
    2.89 +////////////////////////////////////////////////////////////////////////////////
    2.90 +void bst_walk_inorder(struct bst * bst, void (*op)(void * data))
    2.91 +   {
    2.92 +   if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
    2.93 +      return;
    2.94 +
    2.95 +   bst_node_walk_inorder(bst->root, op);
    2.96 +   }
    2.97 +
    2.98 +////////////////////////////////////////////////////////////////////////////////
    2.99 +void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data))
   2.100 +   {
   2.101 +   if (NULL != node)
   2.102 +      {
   2.103 +      bst_node_walk_inorder(node->left, op);
   2.104 +      op(node->data);
   2.105 +      bst_node_walk_inorder(node->right, op);
   2.106 +      }
   2.107 +   }
   2.108 +
   2.109 +////////////////////////////////////////////////////////////////////////////////
   2.110 +void * bst_search(struct bst * bst, void * data)
   2.111 +   {
   2.112 +   if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
   2.113 +      return NULL;
   2.114 +
   2.115 +   return bst_node_search(bst, bst->root, data);
   2.116 +   }
   2.117 +
   2.118 +////////////////////////////////////////////////////////////////////////////////
   2.119 +// Recursive
   2.120 +void * bst_node_search(struct bst * bst, struct bst_node * node, void * data)
   2.121 +   {
   2.122 +   if (NULL == node)
   2.123 +      return NULL;
   2.124 +
   2.125 +   if (bst->eq(data, node->data))
   2.126 +      return node->data;
   2.127 +
   2.128 +   if (bst->le(data, node->data))
   2.129 +      return bst_node_search(bst, node->left, data);
   2.130 +   else
   2.131 +      return bst_node_search(bst, node->right, data);
   2.132 +   }
   2.133 +
   2.134 +////////////////////////////////////////////////////////////////////////////////
   2.135 +// Iterative
   2.136 +void * bst_search_iterative(struct bst * bst, void * data)
   2.137 +   {
   2.138 +   if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
   2.139 +      return NULL;
   2.140 +
   2.141 +   struct bst_node * node = bst->root;
   2.142 +   while (1)
   2.143 +      {
   2.144 +      if (NULL == node)
   2.145 +	 return NULL;
   2.146 +      
   2.147 +      if (bst->eq(data, node->data))
   2.148 +	 return node->data;
   2.149 +      
   2.150 +      if (bst->le(data, node->data))
   2.151 +	 node = node->left;
   2.152 +      else
   2.153 +	 node = node->right;
   2.154 +      }
   2.155 +   }
   2.156 +
   2.157 +////////////////////////////////////////////////////////////////////////////////
   2.158 +void * bst_minimum(struct bst * bst)
   2.159 +   {
   2.160 +   if (NULL == bst)
   2.161 +      return NULL;
   2.162 +
   2.163 +   return bst_node_minimum(bst->root);
   2.164 +   }
   2.165 +
   2.166 +////////////////////////////////////////////////////////////////////////////////
   2.167 +void * bst_node_minimum(struct bst_node * node)
   2.168 +   {
   2.169 +   while ( (NULL != node) && (NULL != node->left) )
   2.170 +      node = node->left;
   2.171 +   if (NULL == node)
   2.172 +      return NULL;
   2.173 +   return node->data;
   2.174 +   }
   2.175 +
   2.176 +////////////////////////////////////////////////////////////////////////////////
   2.177 +void * bst_maximum(struct bst * bst)
   2.178 +   {
   2.179 +   if (NULL == bst)
   2.180 +      return NULL;
   2.181 +
   2.182 +   return bst_node_maximum(bst->root);
   2.183 +   }
   2.184 +
   2.185 +////////////////////////////////////////////////////////////////////////////////
   2.186 +void * bst_node_maximum(struct bst_node * node)
   2.187 +   {
   2.188 +   while ( (NULL != node) && (NULL != node->right) )
   2.189 +      node = node->right;
   2.190 +   if (NULL == node)
   2.191 +      return NULL;
   2.192 +   return node->data;
   2.193 +   }

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/bst.h	Wed Sep 26 13:11:09 2012 -0500
     3.3 @@ -0,0 +1,36 @@
     3.4 +#ifndef BST_H_
     3.5 +#define BST_H_
     3.6 +
     3.7 +#include <stddef.h>
     3.8 +#include <stdbool.h>
     3.9 +
    3.10 +struct bst_node
    3.11 +   {
    3.12 +   struct bst_node * parent;
    3.13 +   struct bst_node * left;
    3.14 +   struct bst_node * right;
    3.15 +   void * data;
    3.16 +   };
    3.17 +
    3.18 +struct bst
    3.19 +   {
    3.20 +   struct bst_node * root;
    3.21 +   size_t size;
    3.22 +   bool (*le)(void * a, void * b);
    3.23 +   bool (*eq)(void * a, void * b);
    3.24 +   };
    3.25 +
    3.26 +struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
    3.27 +void bst_delete(struct bst * bst);
    3.28 +
    3.29 +void * bst_insert(struct bst * bst, void * data);
    3.30 +
    3.31 +void * bst_search(struct bst * bst, void * data);
    3.32 +void * bst_search_iterative(struct bst * bst, void * data);
    3.33 +
    3.34 +void * bst_minimum(struct bst * bst);
    3.35 +void * bst_maximum(struct bst * bst);
    3.36 +
    3.37 +void bst_walk_inorder(struct bst * bst, void (*op)(void * data));
    3.38 +
    3.39 +#endif

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/bst_test.c	Wed Sep 26 13:11:09 2012 -0500
     4.3 @@ -0,0 +1,91 @@
     4.4 +#include <stdio.h>
     4.5 +#include <stdlib.h>
     4.6 +#include <stdbool.h>
     4.7 +#include <time.h>
     4.8 +
     4.9 +#include "bst.h"
    4.10 +
    4.11 +#define MAX_NUMS 10
    4.12 +
    4.13 +bool le(void *a, void * b)
    4.14 +   {
    4.15 +   return *((int *) a) <= *((int *) b);
    4.16 +   }
    4.17 +
    4.18 +bool eq(void *a, void * b)
    4.19 +   {
    4.20 +   return *((int *) a) == *((int *) b);
    4.21 +   }
    4.22 +
    4.23 +void print(void * d)
    4.24 +   {
    4.25 +   printf("%d\n", *((int *) d) );
    4.26 +   }
    4.27 +
    4.28 +int main(int argc, char ** argv)
    4.29 +   {
    4.30 +   struct bst * bst = bst_new(le, eq);
    4.31 +   if (NULL == bst)
    4.32 +      {
    4.33 +      perror("bst_new");
    4.34 +      exit(EXIT_FAILURE);
    4.35 +      }
    4.36 +
    4.37 +   //srand(time());
    4.38 +   int * ip;
    4.39 +   for (int i = 0 ; i < MAX_NUMS ; ++i)
    4.40 +      {
    4.41 +      ip = malloc(sizeof(int));
    4.42 +      if (NULL == ip)
    4.43 +	 {
    4.44 +	 perror("malloc");
    4.45 +	 exit(EXIT_FAILURE);
    4.46 +	 }
    4.47 +
    4.48 +      *ip = rand();
    4.49 +
    4.50 +      if (NULL == bst_insert(bst, ip))
    4.51 +	 {
    4.52 +	 perror("bst_insert");
    4.53 +	 exit(EXIT_FAILURE);
    4.54 +	 }
    4.55 +      }
    4.56 +
    4.57 +   bst_walk_inorder(bst, print);
    4.58 +
    4.59 +   int i = 1;
    4.60 +   int * p = (int *) bst_search(bst, &i);
    4.61 +   if (NULL == p)
    4.62 +      printf("%d NOT FOUND\n", i);
    4.63 +   else
    4.64 +      printf("%d FOUND\n", i);
    4.65 +
    4.66 +   i = *ip;
    4.67 +   p = (int *) bst_search(bst, &i);
    4.68 +   if (NULL == p)
    4.69 +      printf("%d NOT FOUND\n", i);
    4.70 +   else
    4.71 +      printf("%d FOUND\n", i);
    4.72 +
    4.73 +   i = *ip;
    4.74 +   p = (int *) bst_search_iterative(bst, &i);
    4.75 +   if (NULL == p)
    4.76 +      printf("%d NOT FOUND\n", i);
    4.77 +   else
    4.78 +      printf("%d FOUND\n", i);
    4.79 +
    4.80 +
    4.81 +   int * min = bst_minimum(bst);
    4.82 +   if (NULL == min)
    4.83 +      printf("tree has no minimum.  empty?\n");
    4.84 +   else
    4.85 +      printf("%d MINIMUM\n", *min);
    4.86 +
    4.87 +   int * max = bst_maximum(bst);
    4.88 +   if (NULL == max)
    4.89 +      printf("tree has no maximum.  empty?\n");
    4.90 +   else
    4.91 +      printf("%d MAXIMUM\n", *max);
    4.92 +
    4.93 +   exit(EXIT_SUCCESS);
    4.94 +   }