contrib/ldns/rbtree.c

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