"SfR Fresh" - the SfR Freeware/Shareware Archive 
Member "pvfs-2.7.1/src/io/trove/trove-handle-mgmt/avltree.h" of archive pvfs-2.7.1.tar.gz:
As a special service "SfR Fresh" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting with prefixed line numbers.
Alternatively you can here view or download the uninterpreted source code file.
That can be also achieved for any archive member file by clicking within an archive contents listing on the first character of the file(path) respectively on the according byte size field.
1 /*
2 * avltree.h : from http://purists.org/avltree/
3 */
4
5 #ifndef AVLTREE_H
6 #define AVLTREE_H
7
8 #ifndef AVLDATUM
9 #error AVLDATUM undefined!
10 #endif
11
12 #ifndef AVLKEY_TYPE
13 #error AVLKEY_TYPE undefined
14 #endif
15
16 #ifndef AVLKEY
17 #error AVLKEY undefined!
18 #endif
19
20 /*
21 * Which of a given node's subtrees is higher?
22 */
23 enum AVLSKEW
24 {
25 NONE,
26 LEFT,
27 RIGHT
28 };
29
30 /*
31 * Did a given insertion/deletion succeed, and what do we do next?
32 */
33 enum AVLRES
34 {
35 ERROR = 0,
36 OK,
37 BALANCE,
38 };
39
40 /*
41 * AVL tree node structure
42 */
43 struct avlnode
44 {
45 struct avlnode *left, *right;
46 AVLDATUM d;
47 enum AVLSKEW skew;
48 };
49
50 /*
51 * avlinsert: insert a node into the AVL tree.
52 *
53 * Parameters:
54 *
55 * n Address of a pointer to a node.
56 *
57 * d Item to be inserted.
58 *
59 * Return values:
60 *
61 * nonzero The item has been inserted. The excact value of
62 * nonzero yields is of no concern to user code; when
63 * avlinsert recursively calls itself, the number
64 * returned tells the parent activation if the AVL tree
65 * may have become unbalanced; specifically:
66 *
67 * OK None of the subtrees of the node that n points to
68 * has grown, the AVL tree is valid.
69 *
70 * BALANCE One of the subtrees of the node that n points to
71 * has grown, the node's "skew" flag needs adjustment,
72 * and the AVL tree may have become unbalanced.
73 *
74 * zero The datum provided could not be inserted, either due
75 * to AVLKEY collision (the tree already contains another
76 * item with which the same AVLKEY is associated), or
77 * due to insufficient memory.
78 */
79 enum AVLRES
80 avlinsert(struct avlnode **n, AVLDATUM d);
81
82 /*
83 * avlremove: remove an item from the tree.
84 *
85 * Parameters:
86 *
87 * n Address of a pointer to a node.
88 *
89 * key AVLKEY of item to be removed.
90 *
91 * Return values:
92 *
93 * nonzero The item has been removed. The exact value of
94 * nonzero yields if of no concern to user code; when
95 * avlremove recursively calls itself, the number
96 * returned tells the parent activation if the AVL tree
97 * may have become unbalanced; specifically:
98 *
99 * OK None of the subtrees of the node that n points to
100 * has shrunk, the AVL tree is valid.
101 *
102 * BALANCE One of the subtrees of the node that n points to
103 * has shrunk, the node's "skew" flag needs adjustment,
104 * and the AVL tree may have become unbalanced.
105 *
106 * zero The tree does not contain an item yielding the
107 * AVLKEY value provided by the caller.
108 */
109 enum AVLRES
110 avlremove(struct avlnode **n, AVLKEY_TYPE key);
111
112 /*
113 * avlaccess: retrieve the datum corresponding to a given AVLKEY.
114 *
115 * Parameters:
116 *
117 * n Pointer to the root node.
118 *
119 * key TKEY of item to be accessed.
120 *
121 * Return values:
122 *
123 * non-NULL An item yielding the AVLKEY provided has been found,
124 * the return value points to the AVLKEY attached to it.
125 *
126 * NULL The item could not be found.
127 */
128 AVLDATUM *
129 avlaccess(struct avlnode *n, AVLKEY_TYPE key);
130
131 #ifdef AVLALTKEY
132 /*
133 * avlaltaccess: retrieve the datum corresponding to a given AVLALTKEY.
134 *
135 * Parameters:
136 *
137 * n Pointer to the root node.
138 *
139 * key TKEY of item to be accessed.
140 *
141 * Return values:
142 *
143 * non-NULL An item yielding the AVLALTKEY provided has been found,
144 * the return value points to the AVLALTKEY attached to it.
145 *
146 * NULL The item could not be found.
147 */
148 AVLDATUM *
149 avlaltaccess(struct avlnode *n, AVLKEY_TYPE key);
150 #endif
151
152 /*
153 * avlgethighest: retrieve the datum from the highest weighted node
154 *
155 * Parameters:
156 *
157 * n pointer to the root node
158 *
159 * Return values:
160 *
161 * non-NULL the return value points to the AVLKEY attached to the node
162 *
163 * NULL tree has no nodes
164 */
165 AVLDATUM *
166 avlgethighest(struct avlnode *n);
167
168 /*
169 * Function to be called by the tree traversal functions.
170 *
171 * Parameters:
172 *
173 * n Pointer to a node.
174 *
175 * param Value provided by the traversal function's caller.
176 *
177 * depth Recursion depth indicator. Allows the function to
178 * determine how many levels the node bein processed is
179 * below the root node. Can be used, for example,
180 * for selecting the proper indentation width when
181 * avldepthfirst is used to print a tree dump to
182 * the screen.
183 */
184 typedef void AVLWORKER(struct avlnode *n, int param, int depth);
185
186 /*
187 * avldepthfirst: depth-first tree traversal.
188 *
189 * Parameters:
190 *
191 * n Pointer to the root node.
192 *
193 * f Worker function to be called for every node.
194 *
195 * param Additional parameter to be passed to the
196 * worker function
197 *
198 * depth Recursion depth indicator. Allows the worker function
199 * to determine how many levels the node being processed
200 * is below the root node. Can be used, for example,
201 * for selecting the proper indentation width when
202 * avldepthfirst ist used to print a tree dump to
203 * the screen.
204 *
205 * Most of the time, you will want to call avldepthfirst
206 * with a "depth" value of zero.
207 */
208 void
209 avldepthfirst(struct avlnode *n, AVLWORKER *f, int param, int depth);
210
211 /*
212 * avlpreorder: depth-first tree traversal.
213 *
214 * Parameters:
215 *
216 * n Pointer to the root node.
217 *
218 * f Worker function to be called for every node.
219 *
220 * param Additional parameter to be passed to the
221 * worker function
222 *
223 * depth Recursion depth indicator. Allows the worker function
224 * to determine how many levels the node being processed
225 * is below the root node. Can be used, for example,
226 * for selecting the proper indentation width when
227 * avldepthfirst ist used to print a tree dump to
228 * the screen.
229 *
230 * Most of the time, you will want to call avlpostorder
231 * with a "depth" value of zero.
232 */
233 void
234 avlpostorder(struct avlnode *n, AVLWORKER *f, int param, int depth);
235 #endif
236