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