bstree.c

   1 /*
   2 Simple binary search tree implementation.
   3
   4 Andrew Tridgell
   5 May 1994
   6 */
   7
   8
   9
  10 /* these are the functions that are defines in this file */
  11 void *bst_insert(void *tree,void *data,int size,int (*compare)());
  12 void *bst_find(void *tree,void *data,int (*compare)());
  13
  14 struct bst_struct
  15 {
  16   struct bst_struct *ltree;
  17   struct bst_struct *rtree;
  18   void *data;
  19   int data_len;
  20 }
  21
  22
  23 /* find an element in a tree */
  24 void *bst_find(void *tree,void *data,int (*compare)())
  25 {
  26   int ret;
  27   struct bst_struct *bstree = tree;
  28   if (!bstree || !data || !compare) return(NULL);
  29
  30   ret = compare(data,bstree->data);
  31   if (ret < 0)
  32     return(bst_find(bstree->ltree,data,compare));
  33   if (ret > 0)
  34     return(bst_find(bstree->rtree,data,compare));
  35
  36   return(bstree->data);
  37 }
  38
  39 /* create a bst bode */
  40 void *bst_create_node(coid *data,int size)
  41 {
  42   struct bst_struct *bstree = (struct bst_struct *)malloc(sizeof(*bstree));
  43   bstree->ltree = NULL;
  44   bstree->rtree = NULL;
  45   bstree->data = malloc(size);
  46   if (!bstree->data)
  47     {
  48       free(bstree); return(NULL);
  49     }
  50   memcpy(bstree->data,data,size);
  51   bstree->data_len = size;
  52 }
  53
  54 /* insert an element into a tree, returning the new tree */
  55 void *bst_insert(void *tree,void *data,int size,int (*compare)())
  56 {
  57   int ret;
  58   struct bst_struct *bstree = tree;
  59   if (!data || !compare) return(NULL);
  60
  61   if (!bstree)
  62     return(bst_create_node(data,size));
  63
  64   ret = compare(data,bstree->data);
  65   if (ret < 0)
  66     bstree->ltree = bst_insert(bstree->ltree,data,size,compare);
  67   if (ret > 0)
  68     bstree->rtree = bst_insert(bstree->rtree,data,size,compare);
  69
  70   if (ret == 0)
  71     {
  72       /* replace the existing element */
  73       if (bstree->data) free(bstree(data));
  74       bstree->data = (void *)malloc(size);
  75       if (!bstree->data) return(NULL);
  76       memcpy(bstree->data,data,size);
  77       bstree->data_len = size;
  78     }
  79
  80   return(bstree);
  81 }
  82
  83
  84 /* find an element in a tree */
  85 void bst_inorder(void *tree,int (*fn)())
  86 {
  87   struct bst_struct *bstree = tree;
  88   if (!bstree || !fn) return;
  89
  90   bst_inorder(bstree->ltree,fn);
  91   fn(bstree->data,bstree->data_len);
  92   bst_inorder(bstree->rtree,fn);
  93 }
  94
  95
  96 #if 1
  97 /* test a bstree */
  98 bst_test(int size)