nicer formatting
[tridge/junkcode.git] / 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)