1 /*                  /Net/dxcern/userd/timbl/hypertext/WWW/Library/Implementation/HTBTree.html
2                          BALANCED BINARY TREE FOR SORTING THINGS
3 
4    Tree creation, traversal and freeing.  User-supplied comparison routine.
5 
6    Author: Arthur Secret, CERN. Public domain.  Please mail bugs and changes to
7    www-request@info.cern.ch
8 
9    part of libWWW
10 
11  */
12 #ifndef HTBTREE_H
13 #define HTBTREE_H 1
14 
15 #ifndef HTUTILS_H
16 #include <HTUtils.h>
17 #endif
18 
19 #ifdef __cplusplus
20 extern "C" {
21 #endif
22 /*
23 
24 Data structures
25 
26  */ typedef struct _HTBTree_element {
27 	void *object;		/* User object */
28 	struct _HTBTree_element *up;
29 	struct _HTBTree_element *left;
30 	int left_depth;
31 	struct _HTBTree_element *right;
32 	int right_depth;
33     } HTBTElement;
34 
35     typedef int (*HTComparer) (void *a, void *b);
36 
37     typedef struct _HTBTree_top {
38 	HTComparer compare;
39 	struct _HTBTree_element *top;
40     } HTBTree;
41 
42 /*
43 
44 Create a binary tree given its discrimination routine
45 
46  */
47     extern HTBTree *HTBTree_new(HTComparer comp);
48 
49 /*
50 
51 Free storage of the tree but not of the objects
52 
53  */
54     extern void HTBTree_free(HTBTree *tree);
55 
56 /*
57 
58 Free storage of the tree and of the objects
59 
60  */
61     extern void HTBTreeAndObject_free(HTBTree *tree);
62 
63 /*
64 
65 Add an object to a binary tree
66 
67  */
68 
69     extern void HTBTree_add(HTBTree *tree, void *object);
70 
71 /*
72 
73 Search an object in a binary tree
74 
75   returns          Pointer to equivalent object in a tree or NULL if none.
76  */
77 
78     extern void *HTBTree_search(HTBTree *tree, void *object);
79 
80 /*
81 
82 Find user object for element
83 
84  */
85 #define HTBTree_object(element)  ((element)->object)
86 
87 /*
88 
89 Find next element in depth-first order
90 
91   ON ENTRY,
92 
93   ele                    if NULL, start with leftmost element. if != 0 give next object to
94                          the right.
95 
96   returns                Pointer to element or NULL if none left.
97 
98  */
99     extern HTBTElement *HTBTree_next(HTBTree *tree, HTBTElement *ele);
100 
101 #ifdef __cplusplus
102 }
103 #endif
104 #endif				/* HTBTREE_H */
105