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