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