summaryrefslogtreecommitdiffstats
path: root/WWW/Library/Implementation/HTBTree.h
blob: a4f78f94e1a0cb069f4c2eb2c9825062276e65be (plain)
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
100
101
102
103
104
/*                  /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

#ifdef __cplusplus
extern "C" {
#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);

#ifdef __cplusplus
}
#endif
#endif				/* HTBTREE_H */