File Coverage

src/ldns/rbtree.c
Criterion Covered Total %
statement 108 279 38.7
branch 42 168 25.0
condition n/a
subroutine n/a
pod n/a
total 150 447 33.5


line stmt bran cond sub pod time code
1             /*
2             * rbtree.c -- generic red black tree
3             *
4             * Taken from Unbound, modified for ldns
5             *
6             * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
7             *
8             * This software is open source.
9             *
10             * Redistribution and use in source and binary forms, with or without
11             * modification, are permitted provided that the following conditions
12             * are met:
13             *
14             * Redistributions of source code must retain the above copyright notice,
15             * this list of conditions and the following disclaimer.
16             *
17             * Redistributions in binary form must reproduce the above copyright notice,
18             * this list of conditions and the following disclaimer in the documentation
19             * and/or other materials provided with the distribution.
20             *
21             * Neither the name of the NLNET LABS nor the names of its contributors may
22             * be used to endorse or promote products derived from this software without
23             * specific prior written permission.
24             *
25             * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26             * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27             * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28             * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29             * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30             * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
31             * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32             * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33             * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34             * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35             * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36             *
37             */
38              
39             /**
40             * \file
41             * Implementation of a redblack tree.
42             */
43              
44             #include
45             #include
46             #include
47             #include
48              
49             /** Node colour black */
50             #define BLACK 0
51             /** Node colour red */
52             #define RED 1
53              
54             /** the NULL node, global alloc */
55             ldns_rbnode_t ldns_rbtree_null_node = {
56             LDNS_RBTREE_NULL, /* Parent. */
57             LDNS_RBTREE_NULL, /* Left. */
58             LDNS_RBTREE_NULL, /* Right. */
59             NULL, /* Key. */
60             NULL, /* Data. */
61             BLACK /* Color. */
62             };
63              
64             /** rotate subtree left (to preserve redblack property) */
65             static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
66             /** rotate subtree right (to preserve redblack property) */
67             static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
68             /** Fixup node colours when insert happened */
69             static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
70             /** Fixup node colours when delete happened */
71             static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
72              
73             /*
74             * Creates a new red black tree, intializes and returns a pointer to it.
75             *
76             * Return NULL on failure.
77             *
78             */
79             ldns_rbtree_t *
80 31           ldns_rbtree_create (int (*cmpf)(const void *, const void *))
81             {
82             ldns_rbtree_t *rbtree;
83              
84             /* Allocate memory for it */
85 31           rbtree = (ldns_rbtree_t *) LDNS_MALLOC(ldns_rbtree_t);
86 31 50         if (!rbtree) {
87 0           return NULL;
88             }
89              
90             /* Initialize it */
91 31           ldns_rbtree_init(rbtree, cmpf);
92              
93 31           return rbtree;
94             }
95              
96             void
97 31           ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
98             {
99             /* Initialize it */
100 31           rbtree->root = LDNS_RBTREE_NULL;
101 31           rbtree->count = 0;
102 31           rbtree->cmp = cmpf;
103 31           }
104              
105             void
106 31           ldns_rbtree_free(ldns_rbtree_t *rbtree)
107             {
108 31           LDNS_FREE(rbtree);
109 31           }
110              
111             /*
112             * Rotates the node to the left.
113             *
114             */
115             static void
116 12           ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
117             {
118 12           ldns_rbnode_t *right = node->right;
119 12           node->right = right->left;
120 12 50         if (right->left != LDNS_RBTREE_NULL)
121 0           right->left->parent = node;
122              
123 12           right->parent = node->parent;
124              
125 12 100         if (node->parent != LDNS_RBTREE_NULL) {
126 4 100         if (node == node->parent->left) {
127 1           node->parent->left = right;
128             } else {
129 4           node->parent->right = right;
130             }
131             } else {
132 8           rbtree->root = right;
133             }
134 12           right->left = node;
135 12           node->parent = right;
136 12           }
137              
138             /*
139             * Rotates the node to the right.
140             *
141             */
142             static void
143 8           ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
144             {
145 8           ldns_rbnode_t *left = node->left;
146 8           node->left = left->right;
147 8 50         if (left->right != LDNS_RBTREE_NULL)
148 0           left->right->parent = node;
149              
150 8           left->parent = node->parent;
151              
152 8 100         if (node->parent != LDNS_RBTREE_NULL) {
153 1 50         if (node == node->parent->right) {
154 0           node->parent->right = left;
155             } else {
156 1           node->parent->left = left;
157             }
158             } else {
159 7           rbtree->root = left;
160             }
161 8           left->right = node;
162 8           node->parent = left;
163 8           }
164              
165             static void
166 80           ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
167             {
168             ldns_rbnode_t *uncle;
169              
170             /* While not at the root and need fixing... */
171 104 100         while (node != rbtree->root && node->parent->color == RED) {
    100          
172             /* If our parent is left child of our grandparent... */
173 24 100         if (node->parent == node->parent->parent->left) {
174 8           uncle = node->parent->parent->right;
175              
176             /* If our uncle is red... */
177 8 50         if (uncle->color == RED) {
178             /* Paint the parent and the uncle black... */
179 0           node->parent->color = BLACK;
180 0           uncle->color = BLACK;
181              
182             /* And the grandparent red... */
183 0           node->parent->parent->color = RED;
184              
185             /* And continue fixing the grandparent */
186 0           node = node->parent->parent;
187             } else { /* Our uncle is black... */
188             /* Are we the right child? */
189 8 100         if (node == node->parent->right) {
190 1           node = node->parent;
191 1           ldns_rbtree_rotate_left(rbtree, node);
192             }
193             /* Now we're the left child, repaint and rotate... */
194 8           node->parent->color = BLACK;
195 8           node->parent->parent->color = RED;
196 8           ldns_rbtree_rotate_right(rbtree, node->parent->parent);
197             }
198             } else {
199 16           uncle = node->parent->parent->left;
200              
201             /* If our uncle is red... */
202 16 100         if (uncle->color == RED) {
203             /* Paint the parent and the uncle black... */
204 5           node->parent->color = BLACK;
205 5           uncle->color = BLACK;
206              
207             /* And the grandparent red... */
208 5           node->parent->parent->color = RED;
209              
210             /* And continue fixing the grandparent */
211 5           node = node->parent->parent;
212             } else { /* Our uncle is black... */
213             /* Are we the right child? */
214 11 50         if (node == node->parent->left) {
215 0           node = node->parent;
216 0           ldns_rbtree_rotate_right(rbtree, node);
217             }
218             /* Now we're the right child, repaint and rotate... */
219 11           node->parent->color = BLACK;
220 11           node->parent->parent->color = RED;
221 11           ldns_rbtree_rotate_left(rbtree, node->parent->parent);
222             }
223             }
224             }
225 80           rbtree->root->color = BLACK;
226 80           }
227              
228             void
229 0           ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
230             {
231 0           (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
232             data);
233 0           }
234              
235             /*
236             * Inserts a node into a red black tree.
237             *
238             * Returns NULL on failure or the pointer to the newly added node
239             * otherwise.
240             */
241             ldns_rbnode_t *
242 80           ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
243             {
244             /* XXX Not necessary, but keeps compiler quiet... */
245 80           int r = 0;
246              
247             /* We start at the root of the tree */
248 80           ldns_rbnode_t *node = rbtree->root;
249 80           ldns_rbnode_t *parent = LDNS_RBTREE_NULL;
250              
251             /* Lets find the new parent... */
252 160 100         while (node != LDNS_RBTREE_NULL) {
253             /* Compare two keys, do we have a duplicate? */
254 80 50         if ((r = rbtree->cmp(data->key, node->key)) == 0) {
255 0           return NULL;
256             }
257 80           parent = node;
258              
259 80 100         if (r < 0) {
260 36           node = node->left;
261             } else {
262 44           node = node->right;
263             }
264             }
265              
266             /* Initialize the new node */
267 80           data->parent = parent;
268 80           data->left = data->right = LDNS_RBTREE_NULL;
269 80           data->color = RED;
270 80           rbtree->count++;
271              
272             /* Insert it into the tree... */
273 80 100         if (parent != LDNS_RBTREE_NULL) {
274 49 100         if (r < 0) {
275 26           parent->left = data;
276             } else {
277 49           parent->right = data;
278             }
279             } else {
280 31           rbtree->root = data;
281             }
282              
283             /* Fix up the red-black properties... */
284 80           ldns_rbtree_insert_fixup(rbtree, data);
285              
286 80           return data;
287             }
288              
289             /*
290             * Searches the red black tree, returns the data if key is found or NULL otherwise.
291             *
292             */
293             ldns_rbnode_t *
294 86           ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
295             {
296             ldns_rbnode_t *node;
297              
298 86 100         if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
299 6           return node;
300             } else {
301 86           return NULL;
302             }
303             }
304              
305             /** helpers for delete: swap node colours */
306 0           static void swap_int8(uint8_t* x, uint8_t* y)
307             {
308 0           uint8_t t = *x; *x = *y; *y = t;
309 0           }
310              
311             /** helpers for delete: swap node pointers */
312 0           static void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y)
313             {
314 0           ldns_rbnode_t* t = *x; *x = *y; *y = t;
315 0           }
316              
317             /** Update parent pointers of child trees of 'parent' */
318 0           static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
319             {
320 0 0         if(parent == LDNS_RBTREE_NULL)
321             {
322 0 0         if(rbtree->root == old) rbtree->root = new;
323 0           return;
324             }
325 0 0         if(parent->left == old) parent->left = new;
326 0 0         if(parent->right == old) parent->right = new;
327             }
328             /** Update parent pointer of a node 'child' */
329 0           static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new)
330             {
331 0 0         if(child == LDNS_RBTREE_NULL) return;
332 0 0         if(child->parent == old) child->parent = new;
333             }
334              
335             ldns_rbnode_t*
336 0           ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
337             {
338             ldns_rbnode_t *to_delete;
339             ldns_rbnode_t *child;
340 0 0         if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
341 0           rbtree->count--;
342              
343             /* make sure we have at most one non-leaf child */
344 0 0         if(to_delete->left != LDNS_RBTREE_NULL &&
    0          
345 0           to_delete->right != LDNS_RBTREE_NULL)
346             {
347             /* swap with smallest from right subtree (or largest from left) */
348 0           ldns_rbnode_t *smright = to_delete->right;
349 0 0         while(smright->left != LDNS_RBTREE_NULL)
350 0           smright = smright->left;
351             /* swap the smright and to_delete elements in the tree,
352             * but the ldns_rbnode_t is first part of user data struct
353             * so cannot just swap the keys and data pointers. Instead
354             * readjust the pointers left,right,parent */
355              
356             /* swap colors - colors are tied to the position in the tree */
357 0           swap_int8(&to_delete->color, &smright->color);
358              
359             /* swap child pointers in parents of smright/to_delete */
360 0           change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
361 0 0         if(to_delete->right != smright)
362 0           change_parent_ptr(rbtree, smright->parent, smright, to_delete);
363              
364             /* swap parent pointers in children of smright/to_delete */
365 0           change_child_ptr(smright->left, smright, to_delete);
366 0           change_child_ptr(smright->left, smright, to_delete);
367 0           change_child_ptr(smright->right, smright, to_delete);
368 0           change_child_ptr(smright->right, smright, to_delete);
369 0           change_child_ptr(to_delete->left, to_delete, smright);
370 0 0         if(to_delete->right != smright)
371 0           change_child_ptr(to_delete->right, to_delete, smright);
372 0 0         if(to_delete->right == smright)
373             {
374             /* set up so after swap they work */
375 0           to_delete->right = to_delete;
376 0           smright->parent = smright;
377             }
378              
379             /* swap pointers in to_delete/smright nodes */
380 0           swap_np(&to_delete->parent, &smright->parent);
381 0           swap_np(&to_delete->left, &smright->left);
382 0           swap_np(&to_delete->right, &smright->right);
383              
384             /* now delete to_delete (which is at the location where the smright previously was) */
385             }
386              
387 0 0         if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left;
388 0           else child = to_delete->right;
389              
390             /* unlink to_delete from the tree, replace to_delete with child */
391 0           change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
392 0           change_child_ptr(child, to_delete, to_delete->parent);
393              
394 0 0         if(to_delete->color == RED)
395             {
396             /* if node is red then the child (black) can be swapped in */
397             }
398 0 0         else if(child->color == RED)
399             {
400             /* change child to BLACK, removing a RED node is no problem */
401 0 0         if(child!=LDNS_RBTREE_NULL) child->color = BLACK;
402             }
403 0           else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
404              
405             /* unlink completely */
406 0           to_delete->parent = LDNS_RBTREE_NULL;
407 0           to_delete->left = LDNS_RBTREE_NULL;
408 0           to_delete->right = LDNS_RBTREE_NULL;
409 0           to_delete->color = BLACK;
410 0           return to_delete;
411             }
412              
413 0           static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
414             {
415             ldns_rbnode_t* sibling;
416 0           int go_up = 1;
417              
418             /* determine sibling to the node that is one-black short */
419 0 0         if(child_parent->right == child) sibling = child_parent->left;
420 0           else sibling = child_parent->right;
421              
422 0 0         while(go_up)
423             {
424 0 0         if(child_parent == LDNS_RBTREE_NULL)
425             {
426             /* removed parent==black from root, every path, so ok */
427 0           return;
428             }
429              
430 0 0         if(sibling->color == RED)
431             { /* rotate to get a black sibling */
432 0           child_parent->color = RED;
433 0           sibling->color = BLACK;
434 0 0         if(child_parent->right == child)
435 0           ldns_rbtree_rotate_right(rbtree, child_parent);
436 0           else ldns_rbtree_rotate_left(rbtree, child_parent);
437             /* new sibling after rotation */
438 0 0         if(child_parent->right == child) sibling = child_parent->left;
439 0           else sibling = child_parent->right;
440             }
441              
442 0 0         if(child_parent->color == BLACK
443 0 0         && sibling->color == BLACK
444 0 0         && sibling->left->color == BLACK
445 0 0         && sibling->right->color == BLACK)
446             { /* fixup local with recolor of sibling */
447 0 0         if(sibling != LDNS_RBTREE_NULL)
448 0           sibling->color = RED;
449              
450 0           child = child_parent;
451 0           child_parent = child_parent->parent;
452             /* prepare to go up, new sibling */
453 0 0         if(child_parent->right == child) sibling = child_parent->left;
454 0           else sibling = child_parent->right;
455             }
456 0           else go_up = 0;
457             }
458              
459 0 0         if(child_parent->color == RED
460 0 0         && sibling->color == BLACK
461 0 0         && sibling->left->color == BLACK
462 0 0         && sibling->right->color == BLACK)
463             {
464             /* move red to sibling to rebalance */
465 0 0         if(sibling != LDNS_RBTREE_NULL)
466 0           sibling->color = RED;
467 0           child_parent->color = BLACK;
468 0           return;
469             }
470              
471             /* get a new sibling, by rotating at sibling. See which child
472             of sibling is red */
473 0 0         if(child_parent->right == child
474 0 0         && sibling->color == BLACK
475 0 0         && sibling->right->color == RED
476 0 0         && sibling->left->color == BLACK)
477             {
478 0           sibling->color = RED;
479 0           sibling->right->color = BLACK;
480 0           ldns_rbtree_rotate_left(rbtree, sibling);
481             /* new sibling after rotation */
482 0 0         if(child_parent->right == child) sibling = child_parent->left;
483 0           else sibling = child_parent->right;
484             }
485 0 0         else if(child_parent->left == child
486 0 0         && sibling->color == BLACK
487 0 0         && sibling->left->color == RED
488 0 0         && sibling->right->color == BLACK)
489             {
490 0           sibling->color = RED;
491 0           sibling->left->color = BLACK;
492 0           ldns_rbtree_rotate_right(rbtree, sibling);
493             /* new sibling after rotation */
494 0 0         if(child_parent->right == child) sibling = child_parent->left;
495 0           else sibling = child_parent->right;
496             }
497              
498             /* now we have a black sibling with a red child. rotate and exchange colors. */
499 0           sibling->color = child_parent->color;
500 0           child_parent->color = BLACK;
501 0 0         if(child_parent->right == child)
502             {
503 0           sibling->left->color = BLACK;
504 0           ldns_rbtree_rotate_right(rbtree, child_parent);
505             }
506             else
507             {
508 0           sibling->right->color = BLACK;
509 0           ldns_rbtree_rotate_left(rbtree, child_parent);
510             }
511             }
512              
513             int
514 86           ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
515             {
516             int r;
517             ldns_rbnode_t *node;
518              
519             /* We start at root... */
520 86           node = rbtree->root;
521              
522 86           *result = NULL;
523              
524             /* While there are children... */
525 170 100         while (node != LDNS_RBTREE_NULL) {
526 90           r = rbtree->cmp(key, node->key);
527 90 100         if (r == 0) {
528             /* Exact match */
529 6           *result = node;
530 6           return 1;
531             }
532 84 100         if (r < 0) {
533 37           node = node->left;
534             } else {
535             /* Temporary match */
536 47           *result = node;
537 47           node = node->right;
538             }
539             }
540 80           return 0;
541             }
542              
543             /*
544             * Finds the first element in the red black tree
545             *
546             */
547             ldns_rbnode_t *
548 0           ldns_rbtree_first (ldns_rbtree_t *rbtree)
549             {
550 0           ldns_rbnode_t *node = rbtree->root;
551              
552 0 0         if (rbtree->root != LDNS_RBTREE_NULL) {
553 0 0         for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
554             }
555 0           return node;
556             }
557              
558             ldns_rbnode_t *
559 0           ldns_rbtree_last (ldns_rbtree_t *rbtree)
560             {
561 0           ldns_rbnode_t *node = rbtree->root;
562              
563 0 0         if (rbtree->root != LDNS_RBTREE_NULL) {
564 0 0         for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);
565             }
566 0           return node;
567             }
568              
569             /*
570             * Returns the next node...
571             *
572             */
573             ldns_rbnode_t *
574 0           ldns_rbtree_next (ldns_rbnode_t *node)
575             {
576             ldns_rbnode_t *parent;
577              
578 0 0         if (node->right != LDNS_RBTREE_NULL) {
579             /* One right, then keep on going left... */
580 0 0         for (node = node->right;
581 0           node->left != LDNS_RBTREE_NULL;
582 0           node = node->left);
583             } else {
584 0           parent = node->parent;
585 0 0         while (parent != LDNS_RBTREE_NULL && node == parent->right) {
    0          
586 0           node = parent;
587 0           parent = parent->parent;
588             }
589 0           node = parent;
590             }
591 0           return node;
592             }
593              
594             ldns_rbnode_t *
595 0           ldns_rbtree_previous(ldns_rbnode_t *node)
596             {
597             ldns_rbnode_t *parent;
598              
599 0 0         if (node->left != LDNS_RBTREE_NULL) {
600             /* One left, then keep on going right... */
601 0 0         for (node = node->left;
602 0           node->right != LDNS_RBTREE_NULL;
603 0           node = node->right);
604             } else {
605 0           parent = node->parent;
606 0 0         while (parent != LDNS_RBTREE_NULL && node == parent->left) {
    0          
607 0           node = parent;
608 0           parent = parent->parent;
609             }
610 0           node = parent;
611             }
612 0           return node;
613             }
614              
615             /**
616             * split off elements number of elements from the start
617             * of the name tree and return a new tree
618             */
619             ldns_rbtree_t *
620 0           ldns_rbtree_split(ldns_rbtree_t *tree,
621             size_t elements)
622             {
623             ldns_rbtree_t *new_tree;
624             ldns_rbnode_t *cur_node;
625             ldns_rbnode_t *move_node;
626 0           size_t count = 0;
627              
628 0           new_tree = ldns_rbtree_create(tree->cmp);
629              
630 0           cur_node = ldns_rbtree_first(tree);
631 0 0         while (count < elements && cur_node != LDNS_RBTREE_NULL) {
    0          
632 0           move_node = ldns_rbtree_delete(tree, cur_node->key);
633 0           (void)ldns_rbtree_insert(new_tree, move_node);
634 0           cur_node = ldns_rbtree_first(tree);
635 0           count++;
636             }
637              
638 0           return new_tree;
639             }
640              
641             /*
642             * add all node from the second tree to the first (removing them from the
643             * second), and fix up nsec(3)s if present
644             */
645             void
646 0           ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
647             {
648 0           ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1);
649 0           }
650              
651             /** recursive descent traverse */
652             static void
653 191           traverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg,
654             ldns_rbnode_t* node)
655             {
656 191 50         if(!node || node == LDNS_RBTREE_NULL)
    100          
657 111           return;
658             /* recurse */
659 80           traverse_post(func, arg, node->left);
660 80           traverse_post(func, arg, node->right);
661             /* call user func */
662 80           (*func)(node, arg);
663             }
664              
665             void
666 31           ldns_traverse_postorder(ldns_rbtree_t* tree,
667             void (*func)(ldns_rbnode_t*, void*), void* arg)
668             {
669 31           traverse_post(func, arg, tree->root);
670 31           }