]>
Commit | Line | Data |
---|---|---|
cec40916 | 1 | /* Copyright (C) 1995, 1996, 1997, 2000, 2006 Free Software Foundation, Inc. |
6d52618b | 2 | This file is part of the GNU C Library. |
993b3242 | 3 | Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997. |
60478656 | 4 | |
6d52618b | 5 | The GNU C Library is free software; you can redistribute it and/or |
41bdb6e2 AJ |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
60478656 | 9 | |
6d52618b UD |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
41bdb6e2 | 13 | Lesser General Public License for more details. |
60478656 | 14 | |
41bdb6e2 AJ |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, write to the Free | |
17 | Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA | |
18 | 02111-1307 USA. */ | |
60478656 | 19 | |
993b3242 UD |
20 | /* Tree search for red/black trees. |
21 | The algorithm for adding nodes is taken from one of the many "Algorithms" | |
22 | books by Robert Sedgewick, although the implementation differs. | |
23 | The algorithm for deleting nodes can probably be found in a book named | |
24 | "Introduction to Algorithms" by Cormen/Leiserson/Rivest. At least that's | |
25 | the book that my professor took most algorithms from during the "Data | |
26 | Structures" course... | |
1be6ec30 | 27 | |
60478656 | 28 | Totally public domain. */ |
993b3242 UD |
29 | |
30 | /* Red/black trees are binary trees in which the edges are colored either red | |
31 | or black. They have the following properties: | |
32 | 1. The number of black edges on every path from the root to a leaf is | |
33 | constant. | |
34 | 2. No two red edges are adjacent. | |
35 | Therefore there is an upper bound on the length of every path, it's | |
36 | O(log n) where n is the number of nodes in the tree. No path can be longer | |
37 | than 1+2*P where P is the length of the shortest path in the tree. | |
38 | Useful for the implementation: | |
39 | 3. If one of the children of a node is NULL, then the other one is red | |
40 | (if it exists). | |
41 | ||
42 | In the implementation, not the edges are colored, but the nodes. The color | |
43 | interpreted as the color of the edge leading to this node. The color is | |
44 | meaningless for the root node, but we color the root node black for | |
45 | convenience. All added nodes are red initially. | |
46 | ||
47 | Adding to a red/black tree is rather easy. The right place is searched | |
48 | with a usual binary tree search. Additionally, whenever a node N is | |
49 | reached that has two red successors, the successors are colored black and | |
50 | the node itself colored red. This moves red edges up the tree where they | |
51 | pose less of a problem once we get to really insert the new node. Changing | |
52 | N's color to red may violate rule 2, however, so rotations may become | |
53 | necessary to restore the invariants. Adding a new red leaf may violate | |
54 | the same rule, so afterwards an additional check is run and the tree | |
55 | possibly rotated. | |
56 | ||
57 | Deleting is hairy. There are mainly two nodes involved: the node to be | |
58 | deleted (n1), and another node that is to be unchained from the tree (n2). | |
59 | If n1 has a successor (the node with a smallest key that is larger than | |
60 | n1), then the successor becomes n2 and its contents are copied into n1, | |
61 | otherwise n1 becomes n2. | |
62 | Unchaining a node may violate rule 1: if n2 is black, one subtree is | |
63 | missing one black edge afterwards. The algorithm must try to move this | |
64 | error upwards towards the root, so that the subtree that does not have | |
65 | enough black edges becomes the whole tree. Once that happens, the error | |
66 | has disappeared. It may not be necessary to go all the way up, since it | |
67 | is possible that rotations and recoloring can fix the error before that. | |
68 | ||
69 | Although the deletion algorithm must walk upwards through the tree, we | |
70 | do not store parent pointers in the nodes. Instead, delete allocates a | |
71 | small array of parent pointers and fills it while descending the tree. | |
72 | Since we know that the length of a path is O(log n), where n is the number | |
73 | of nodes, this is likely to use less memory. */ | |
74 | ||
75 | /* Tree rotations look like this: | |
76 | A C | |
77 | / \ / \ | |
78 | B C A G | |
79 | / \ / \ --> / \ | |
80 | D E F G B F | |
81 | / \ | |
82 | D E | |
83 | ||
84 | In this case, A has been rotated left. This preserves the ordering of the | |
85 | binary tree. */ | |
60478656 RM |
86 | |
87 | #include <stdlib.h> | |
f671aeab | 88 | #include <string.h> |
60478656 RM |
89 | #include <search.h> |
90 | ||
60478656 RM |
91 | typedef struct node_t |
92 | { | |
993b3242 UD |
93 | /* Callers expect this to be the first element in the structure - do not |
94 | move! */ | |
60478656 RM |
95 | const void *key; |
96 | struct node_t *left; | |
97 | struct node_t *right; | |
993b3242 UD |
98 | unsigned int red:1; |
99 | } *node; | |
2a068d20 | 100 | typedef const struct node_t *const_node; |
993b3242 UD |
101 | |
102 | #undef DEBUGGING | |
103 | ||
104 | #ifdef DEBUGGING | |
105 | ||
106 | /* Routines to check tree invariants. */ | |
107 | ||
108 | #include <assert.h> | |
109 | ||
110 | #define CHECK_TREE(a) check_tree(a) | |
111 | ||
112 | static void | |
113 | check_tree_recurse (node p, int d_sofar, int d_total) | |
114 | { | |
115 | if (p == NULL) | |
116 | { | |
117 | assert (d_sofar == d_total); | |
118 | return; | |
119 | } | |
120 | ||
121 | check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total); | |
122 | check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total); | |
123 | if (p->left) | |
124 | assert (!(p->left->red && p->red)); | |
125 | if (p->right) | |
126 | assert (!(p->right->red && p->red)); | |
127 | } | |
128 | ||
129 | static void | |
130 | check_tree (node root) | |
131 | { | |
132 | int cnt = 0; | |
133 | node p; | |
134 | if (root == NULL) | |
135 | return; | |
136 | root->red = 0; | |
137 | for(p = root->left; p; p = p->left) | |
138 | cnt += !p->red; | |
139 | check_tree_recurse (root, 0, cnt); | |
60478656 | 140 | } |
60478656 | 141 | |
60478656 | 142 | |
993b3242 | 143 | #else |
60478656 | 144 | |
993b3242 UD |
145 | #define CHECK_TREE(a) |
146 | ||
147 | #endif | |
148 | ||
149 | /* Possibly "split" a node with two red successors, and/or fix up two red | |
150 | edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP | |
151 | and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the | |
152 | comparison values that determined which way was taken in the tree to reach | |
153 | ROOTP. MODE is 1 if we need not do the split, but must check for two red | |
154 | edges between GPARENTP and ROOTP. */ | |
155 | static void | |
156 | maybe_split_for_insert (node *rootp, node *parentp, node *gparentp, | |
157 | int p_r, int gp_r, int mode) | |
158 | { | |
159 | node root = *rootp; | |
160 | node *rp, *lp; | |
161 | rp = &(*rootp)->right; | |
162 | lp = &(*rootp)->left; | |
163 | ||
164 | /* See if we have to split this node (both successors red). */ | |
165 | if (mode == 1 | |
166 | || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red)) | |
167 | { | |
168 | /* This node becomes red, its successors black. */ | |
169 | root->red = 1; | |
170 | if (*rp) | |
171 | (*rp)->red = 0; | |
172 | if (*lp) | |
173 | (*lp)->red = 0; | |
174 | ||
175 | /* If the parent of this node is also red, we have to do | |
176 | rotations. */ | |
177 | if (parentp != NULL && (*parentp)->red) | |
178 | { | |
179 | node gp = *gparentp; | |
180 | node p = *parentp; | |
181 | /* There are two main cases: | |
182 | 1. The edge types (left or right) of the two red edges differ. | |
183 | 2. Both red edges are of the same type. | |
184 | There exist two symmetries of each case, so there is a total of | |
185 | 4 cases. */ | |
186 | if ((p_r > 0) != (gp_r > 0)) | |
187 | { | |
188 | /* Put the child at the top of the tree, with its parent | |
189 | and grandparent as successors. */ | |
190 | p->red = 1; | |
191 | gp->red = 1; | |
192 | root->red = 0; | |
193 | if (p_r < 0) | |
194 | { | |
195 | /* Child is left of parent. */ | |
196 | p->left = *rp; | |
197 | *rp = p; | |
198 | gp->right = *lp; | |
199 | *lp = gp; | |
200 | } | |
201 | else | |
202 | { | |
203 | /* Child is right of parent. */ | |
204 | p->right = *lp; | |
205 | *lp = p; | |
206 | gp->left = *rp; | |
207 | *rp = gp; | |
208 | } | |
209 | *gparentp = root; | |
210 | } | |
211 | else | |
212 | { | |
213 | *gparentp = *parentp; | |
214 | /* Parent becomes the top of the tree, grandparent and | |
215 | child are its successors. */ | |
216 | p->red = 0; | |
217 | gp->red = 1; | |
218 | if (p_r < 0) | |
219 | { | |
220 | /* Left edges. */ | |
221 | gp->left = p->right; | |
222 | p->right = gp; | |
223 | } | |
224 | else | |
225 | { | |
226 | /* Right edges. */ | |
227 | gp->right = p->left; | |
228 | p->left = gp; | |
229 | } | |
230 | } | |
231 | } | |
232 | } | |
233 | } | |
234 | ||
235 | /* Find or insert datum into search tree. | |
236 | KEY is the key to be located, ROOTP is the address of tree root, | |
237 | COMPAR the ordering function. */ | |
60478656 | 238 | void * |
993b3242 | 239 | __tsearch (const void *key, void **vrootp, __compar_fn_t compar) |
60478656 | 240 | { |
993b3242 UD |
241 | node q; |
242 | node *parentp = NULL, *gparentp = NULL; | |
243 | node *rootp = (node *) vrootp; | |
244 | node *nextp; | |
245 | int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */ | |
60478656 RM |
246 | |
247 | if (rootp == NULL) | |
248 | return NULL; | |
249 | ||
993b3242 UD |
250 | /* This saves some additional tests below. */ |
251 | if (*rootp != NULL) | |
252 | (*rootp)->red = 0; | |
253 | ||
254 | CHECK_TREE (*rootp); | |
60478656 | 255 | |
993b3242 UD |
256 | nextp = rootp; |
257 | while (*nextp != NULL) | |
258 | { | |
259 | node root = *rootp; | |
260 | r = (*compar) (key, root->key); | |
261 | if (r == 0) | |
262 | return root; | |
263 | ||
264 | maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0); | |
265 | /* If that did any rotations, parentp and gparentp are now garbage. | |
266 | That doesn't matter, because the values they contain are never | |
267 | used again in that case. */ | |
268 | ||
269 | nextp = r < 0 ? &root->left : &root->right; | |
270 | if (*nextp == NULL) | |
271 | break; | |
272 | ||
273 | gparentp = parentp; | |
274 | parentp = rootp; | |
275 | rootp = nextp; | |
276 | ||
277 | gp_r = p_r; | |
278 | p_r = r; | |
60478656 RM |
279 | } |
280 | ||
993b3242 UD |
281 | q = (struct node_t *) malloc (sizeof (struct node_t)); |
282 | if (q != NULL) | |
60478656 | 283 | { |
993b3242 | 284 | *nextp = q; /* link new node to old */ |
60478656 | 285 | q->key = key; /* initialize new node */ |
993b3242 | 286 | q->red = 1; |
60478656 | 287 | q->left = q->right = NULL; |
cec40916 UD |
288 | |
289 | if (nextp != rootp) | |
290 | /* There may be two red edges in a row now, which we must avoid by | |
291 | rotating the tree. */ | |
292 | maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); | |
60478656 RM |
293 | } |
294 | ||
295 | return q; | |
296 | } | |
1be6ec30 | 297 | weak_alias (__tsearch, tsearch) |
60478656 RM |
298 | |
299 | ||
993b3242 UD |
300 | /* Find datum in search tree. |
301 | KEY is the key to be located, ROOTP is the address of tree root, | |
302 | COMPAR the ordering function. */ | |
60478656 | 303 | void * |
1be6ec30 | 304 | __tfind (key, vrootp, compar) |
60478656 | 305 | const void *key; |
d951286f | 306 | void *const *vrootp; |
60478656 RM |
307 | __compar_fn_t compar; |
308 | { | |
993b3242 | 309 | node *rootp = (node *) vrootp; |
60478656 RM |
310 | |
311 | if (rootp == NULL) | |
312 | return NULL; | |
313 | ||
993b3242 UD |
314 | CHECK_TREE (*rootp); |
315 | ||
316 | while (*rootp != NULL) | |
60478656 | 317 | { |
993b3242 | 318 | node root = *rootp; |
60478656 RM |
319 | int r; |
320 | ||
993b3242 UD |
321 | r = (*compar) (key, root->key); |
322 | if (r == 0) | |
323 | return root; | |
60478656 | 324 | |
993b3242 | 325 | rootp = r < 0 ? &root->left : &root->right; |
60478656 | 326 | } |
993b3242 | 327 | return NULL; |
60478656 | 328 | } |
1be6ec30 | 329 | weak_alias (__tfind, tfind) |
60478656 RM |
330 | |
331 | ||
993b3242 UD |
332 | /* Delete node with given key. |
333 | KEY is the key to be deleted, ROOTP is the address of the root of tree, | |
334 | COMPAR the comparison function. */ | |
60478656 | 335 | void * |
993b3242 | 336 | __tdelete (const void *key, void **vrootp, __compar_fn_t compar) |
60478656 | 337 | { |
993b3242 | 338 | node p, q, r, retval; |
60478656 | 339 | int cmp; |
993b3242 UD |
340 | node *rootp = (node *) vrootp; |
341 | node root, unchained; | |
342 | /* Stack of nodes so we remember the parents without recursion. It's | |
343 | _very_ unlikely that there are paths longer than 40 nodes. The tree | |
344 | would need to have around 250.000 nodes. */ | |
345 | int stacksize = 40; | |
346 | int sp = 0; | |
347 | node **nodestack = alloca (sizeof (node *) * stacksize); | |
60478656 | 348 | |
993b3242 | 349 | if (rootp == NULL) |
60478656 | 350 | return NULL; |
993b3242 UD |
351 | p = *rootp; |
352 | if (p == NULL) | |
353 | return NULL; | |
354 | ||
355 | CHECK_TREE (p); | |
60478656 RM |
356 | |
357 | while ((cmp = (*compar) (key, (*rootp)->key)) != 0) | |
358 | { | |
993b3242 UD |
359 | if (sp == stacksize) |
360 | { | |
361 | node **newstack; | |
362 | stacksize += 20; | |
363 | newstack = alloca (sizeof (node *) * stacksize); | |
86187531 | 364 | nodestack = memcpy (newstack, nodestack, sp * sizeof (node *)); |
993b3242 UD |
365 | } |
366 | ||
367 | nodestack[sp++] = rootp; | |
60478656 | 368 | p = *rootp; |
993b3242 UD |
369 | rootp = ((cmp < 0) |
370 | ? &(*rootp)->left | |
371 | : &(*rootp)->right); | |
60478656 | 372 | if (*rootp == NULL) |
993b3242 | 373 | return NULL; |
60478656 RM |
374 | } |
375 | ||
993b3242 UD |
376 | /* This is bogus if the node to be deleted is the root... this routine |
377 | really should return an integer with 0 for success, -1 for failure | |
378 | and errno = ESRCH or something. */ | |
379 | retval = p; | |
380 | ||
381 | /* We don't unchain the node we want to delete. Instead, we overwrite | |
382 | it with its successor and unchain the successor. If there is no | |
383 | successor, we really unchain the node to be deleted. */ | |
384 | ||
385 | root = *rootp; | |
386 | ||
387 | r = root->right; | |
388 | q = root->left; | |
389 | ||
390 | if (q == NULL || r == NULL) | |
391 | unchained = root; | |
392 | else | |
60478656 | 393 | { |
993b3242 UD |
394 | node *parent = rootp, *up = &root->right; |
395 | for (;;) | |
60478656 | 396 | { |
993b3242 UD |
397 | if (sp == stacksize) |
398 | { | |
399 | node **newstack; | |
400 | stacksize += 20; | |
401 | newstack = alloca (sizeof (node *) * stacksize); | |
86187531 | 402 | nodestack = memcpy (newstack, nodestack, sp * sizeof (node *)); |
993b3242 UD |
403 | } |
404 | nodestack[sp++] = parent; | |
405 | parent = up; | |
406 | if ((*up)->left == NULL) | |
407 | break; | |
408 | up = &(*up)->left; | |
60478656 | 409 | } |
993b3242 UD |
410 | unchained = *up; |
411 | } | |
412 | ||
413 | /* We know that either the left or right successor of UNCHAINED is NULL. | |
414 | R becomes the other one, it is chained into the parent of UNCHAINED. */ | |
415 | r = unchained->left; | |
416 | if (r == NULL) | |
417 | r = unchained->right; | |
418 | if (sp == 0) | |
419 | *rootp = r; | |
420 | else | |
421 | { | |
422 | q = *nodestack[sp-1]; | |
423 | if (unchained == q->right) | |
424 | q->right = r; | |
60478656 | 425 | else |
993b3242 UD |
426 | q->left = r; |
427 | } | |
428 | ||
429 | if (unchained != root) | |
430 | root->key = unchained->key; | |
431 | if (!unchained->red) | |
432 | { | |
433 | /* Now we lost a black edge, which means that the number of black | |
434 | edges on every path is no longer constant. We must balance the | |
435 | tree. */ | |
436 | /* NODESTACK now contains all parents of R. R is likely to be NULL | |
437 | in the first iteration. */ | |
438 | /* NULL nodes are considered black throughout - this is necessary for | |
439 | correctness. */ | |
440 | while (sp > 0 && (r == NULL || !r->red)) | |
441 | { | |
442 | node *pp = nodestack[sp - 1]; | |
443 | p = *pp; | |
444 | /* Two symmetric cases. */ | |
445 | if (r == p->left) | |
446 | { | |
447 | /* Q is R's brother, P is R's parent. The subtree with root | |
448 | R has one black edge less than the subtree with root Q. */ | |
449 | q = p->right; | |
afbf86d2 | 450 | if (q->red) |
993b3242 UD |
451 | { |
452 | /* If Q is red, we know that P is black. We rotate P left | |
453 | so that Q becomes the top node in the tree, with P below | |
454 | it. P is colored red, Q is colored black. | |
455 | This action does not change the black edge count for any | |
456 | leaf in the tree, but we will be able to recognize one | |
457 | of the following situations, which all require that Q | |
458 | is black. */ | |
459 | q->red = 0; | |
460 | p->red = 1; | |
461 | /* Left rotate p. */ | |
462 | p->right = q->left; | |
463 | q->left = p; | |
464 | *pp = q; | |
465 | /* Make sure pp is right if the case below tries to use | |
466 | it. */ | |
467 | nodestack[sp++] = pp = &q->left; | |
468 | q = p->right; | |
469 | } | |
470 | /* We know that Q can't be NULL here. We also know that Q is | |
471 | black. */ | |
472 | if ((q->left == NULL || !q->left->red) | |
473 | && (q->right == NULL || !q->right->red)) | |
474 | { | |
475 | /* Q has two black successors. We can simply color Q red. | |
476 | The whole subtree with root P is now missing one black | |
477 | edge. Note that this action can temporarily make the | |
478 | tree invalid (if P is red). But we will exit the loop | |
479 | in that case and set P black, which both makes the tree | |
480 | valid and also makes the black edge count come out | |
481 | right. If P is black, we are at least one step closer | |
482 | to the root and we'll try again the next iteration. */ | |
483 | q->red = 1; | |
484 | r = p; | |
485 | } | |
486 | else | |
487 | { | |
488 | /* Q is black, one of Q's successors is red. We can | |
489 | repair the tree with one operation and will exit the | |
490 | loop afterwards. */ | |
491 | if (q->right == NULL || !q->right->red) | |
492 | { | |
493 | /* The left one is red. We perform the same action as | |
494 | in maybe_split_for_insert where two red edges are | |
495 | adjacent but point in different directions: | |
496 | Q's left successor (let's call it Q2) becomes the | |
497 | top of the subtree we are looking at, its parent (Q) | |
498 | and grandparent (P) become its successors. The former | |
499 | successors of Q2 are placed below P and Q. | |
500 | P becomes black, and Q2 gets the color that P had. | |
501 | This changes the black edge count only for node R and | |
502 | its successors. */ | |
503 | node q2 = q->left; | |
504 | q2->red = p->red; | |
505 | p->right = q2->left; | |
506 | q->left = q2->right; | |
507 | q2->right = q; | |
508 | q2->left = p; | |
509 | *pp = q2; | |
510 | p->red = 0; | |
511 | } | |
512 | else | |
513 | { | |
514 | /* It's the right one. Rotate P left. P becomes black, | |
515 | and Q gets the color that P had. Q's right successor | |
516 | also becomes black. This changes the black edge | |
517 | count only for node R and its successors. */ | |
518 | q->red = p->red; | |
519 | p->red = 0; | |
520 | ||
521 | q->right->red = 0; | |
522 | ||
523 | /* left rotate p */ | |
524 | p->right = q->left; | |
525 | q->left = p; | |
526 | *pp = q; | |
527 | } | |
528 | ||
529 | /* We're done. */ | |
530 | sp = 1; | |
531 | r = NULL; | |
532 | } | |
533 | } | |
534 | else | |
535 | { | |
536 | /* Comments: see above. */ | |
537 | q = p->left; | |
afbf86d2 | 538 | if (q->red) |
993b3242 UD |
539 | { |
540 | q->red = 0; | |
541 | p->red = 1; | |
542 | p->left = q->right; | |
543 | q->right = p; | |
544 | *pp = q; | |
545 | nodestack[sp++] = pp = &q->right; | |
546 | q = p->left; | |
547 | } | |
548 | if ((q->right == NULL || !q->right->red) | |
549 | && (q->left == NULL || !q->left->red)) | |
550 | { | |
551 | q->red = 1; | |
552 | r = p; | |
553 | } | |
554 | else | |
555 | { | |
556 | if (q->left == NULL || !q->left->red) | |
557 | { | |
558 | node q2 = q->right; | |
559 | q2->red = p->red; | |
560 | p->left = q2->right; | |
561 | q->right = q2->left; | |
562 | q2->left = q; | |
563 | q2->right = p; | |
564 | *pp = q2; | |
565 | p->red = 0; | |
566 | } | |
567 | else | |
568 | { | |
569 | q->red = p->red; | |
570 | p->red = 0; | |
571 | q->left->red = 0; | |
572 | p->left = q->right; | |
573 | q->right = p; | |
574 | *pp = q; | |
575 | } | |
576 | sp = 1; | |
577 | r = NULL; | |
578 | } | |
579 | } | |
580 | --sp; | |
60478656 | 581 | } |
993b3242 UD |
582 | if (r != NULL) |
583 | r->red = 0; | |
60478656 | 584 | } |
993b3242 UD |
585 | |
586 | free (unchained); | |
587 | return retval; | |
60478656 | 588 | } |
4f54cdb1 | 589 | weak_alias (__tdelete, tdelete) |
60478656 RM |
590 | |
591 | ||
993b3242 UD |
592 | /* Walk the nodes of a tree. |
593 | ROOT is the root of the tree to be walked, ACTION the function to be | |
594 | called at each node. LEVEL is the level of ROOT in the whole tree. */ | |
60478656 | 595 | static void |
dfd2257a | 596 | internal_function |
993b3242 | 597 | trecurse (const void *vroot, __action_fn_t action, int level) |
60478656 | 598 | { |
2a068d20 | 599 | const_node root = (const_node) vroot; |
60478656 RM |
600 | |
601 | if (root->left == NULL && root->right == NULL) | |
602 | (*action) (root, leaf, level); | |
603 | else | |
604 | { | |
605 | (*action) (root, preorder, level); | |
606 | if (root->left != NULL) | |
607 | trecurse (root->left, action, level + 1); | |
608 | (*action) (root, postorder, level); | |
609 | if (root->right != NULL) | |
610 | trecurse (root->right, action, level + 1); | |
611 | (*action) (root, endorder, level); | |
612 | } | |
613 | } | |
614 | ||
615 | ||
993b3242 UD |
616 | /* Walk the nodes of a tree. |
617 | ROOT is the root of the tree to be walked, ACTION the function to be | |
618 | called at each node. */ | |
60478656 | 619 | void |
993b3242 | 620 | __twalk (const void *vroot, __action_fn_t action) |
60478656 | 621 | { |
2a068d20 | 622 | const_node root = (const_node) vroot; |
993b3242 UD |
623 | |
624 | CHECK_TREE (root); | |
60478656 RM |
625 | |
626 | if (root != NULL && action != NULL) | |
627 | trecurse (root, action, 0); | |
628 | } | |
1be6ec30 | 629 | weak_alias (__twalk, twalk) |
d951286f UD |
630 | |
631 | ||
632 | ||
633 | /* The standardized functions miss an important functionality: the | |
634 | tree cannot be removed easily. We provide a function to do this. */ | |
635 | static void | |
dfd2257a | 636 | internal_function |
d951286f UD |
637 | tdestroy_recurse (node root, __free_fn_t freefct) |
638 | { | |
f671aeab UD |
639 | if (root->left != NULL) |
640 | tdestroy_recurse (root->left, freefct); | |
641 | if (root->right != NULL) | |
642 | tdestroy_recurse (root->right, freefct); | |
643 | (*freefct) ((void *) root->key); | |
d951286f UD |
644 | /* Free the node itself. */ |
645 | free (root); | |
646 | } | |
647 | ||
648 | void | |
649 | __tdestroy (void *vroot, __free_fn_t freefct) | |
650 | { | |
651 | node root = (node) vroot; | |
652 | ||
653 | CHECK_TREE (root); | |
654 | ||
655 | if (root != NULL) | |
656 | tdestroy_recurse (root, freefct); | |
657 | } | |
658 | weak_alias (__tdestroy, tdestroy) |