1238104Sdes/* 2238104Sdes * rbtree.c -- generic red black tree 3238104Sdes * 4238104Sdes * Taken from Unbound, modified for ldns 5238104Sdes * 6238104Sdes * Copyright (c) 2001-2008, NLnet Labs. All rights reserved. 7238104Sdes * 8238104Sdes * This software is open source. 9238104Sdes * 10238104Sdes * Redistribution and use in source and binary forms, with or without 11238104Sdes * modification, are permitted provided that the following conditions 12238104Sdes * are met: 13238104Sdes * 14238104Sdes * Redistributions of source code must retain the above copyright notice, 15238104Sdes * this list of conditions and the following disclaimer. 16238104Sdes * 17238104Sdes * Redistributions in binary form must reproduce the above copyright notice, 18238104Sdes * this list of conditions and the following disclaimer in the documentation 19238104Sdes * and/or other materials provided with the distribution. 20238104Sdes * 21238104Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 22238104Sdes * be used to endorse or promote products derived from this software without 23238104Sdes * specific prior written permission. 24238104Sdes * 25238104Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26238104Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 27238104Sdes * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28238104Sdes * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 29238104Sdes * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 30238104Sdes * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 31238104Sdes * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 32238104Sdes * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 33238104Sdes * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 34238104Sdes * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 35238104Sdes * POSSIBILITY OF SUCH DAMAGE. 36238104Sdes * 37238104Sdes */ 38238104Sdes 39238104Sdes/** 40238104Sdes * \file 41238104Sdes * Implementation of a redblack tree. 42238104Sdes */ 43238104Sdes 44238104Sdes#include <ldns/config.h> 45238104Sdes#include <ldns/rbtree.h> 46238104Sdes#include <ldns/util.h> 47238104Sdes#include <stdlib.h> 48238104Sdes 49238104Sdes/** Node colour black */ 50238104Sdes#define BLACK 0 51238104Sdes/** Node colour red */ 52238104Sdes#define RED 1 53238104Sdes 54238104Sdes/** the NULL node, global alloc */ 55238104Sdesldns_rbnode_t ldns_rbtree_null_node = { 56238104Sdes LDNS_RBTREE_NULL, /* Parent. */ 57238104Sdes LDNS_RBTREE_NULL, /* Left. */ 58238104Sdes LDNS_RBTREE_NULL, /* Right. */ 59238104Sdes NULL, /* Key. */ 60238104Sdes NULL, /* Data. */ 61238104Sdes BLACK /* Color. */ 62238104Sdes}; 63238104Sdes 64238104Sdes/** rotate subtree left (to preserve redblack property) */ 65238104Sdesstatic void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node); 66238104Sdes/** rotate subtree right (to preserve redblack property) */ 67238104Sdesstatic void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node); 68238104Sdes/** Fixup node colours when insert happened */ 69238104Sdesstatic void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node); 70238104Sdes/** Fixup node colours when delete happened */ 71238104Sdesstatic void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent); 72238104Sdes 73238104Sdes/* 74238104Sdes * Creates a new red black tree, intializes and returns a pointer to it. 75238104Sdes * 76238104Sdes * Return NULL on failure. 77238104Sdes * 78238104Sdes */ 79238104Sdesldns_rbtree_t * 80238104Sdesldns_rbtree_create (int (*cmpf)(const void *, const void *)) 81238104Sdes{ 82238104Sdes ldns_rbtree_t *rbtree; 83238104Sdes 84238104Sdes /* Allocate memory for it */ 85238104Sdes rbtree = (ldns_rbtree_t *) LDNS_MALLOC(ldns_rbtree_t); 86238104Sdes if (!rbtree) { 87238104Sdes return NULL; 88238104Sdes } 89238104Sdes 90238104Sdes /* Initialize it */ 91238104Sdes ldns_rbtree_init(rbtree, cmpf); 92238104Sdes 93238104Sdes return rbtree; 94238104Sdes} 95238104Sdes 96238104Sdesvoid 97238104Sdesldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *)) 98238104Sdes{ 99238104Sdes /* Initialize it */ 100238104Sdes rbtree->root = LDNS_RBTREE_NULL; 101238104Sdes rbtree->count = 0; 102238104Sdes rbtree->cmp = cmpf; 103238104Sdes} 104238104Sdes 105238104Sdesvoid 106238104Sdesldns_rbtree_free(ldns_rbtree_t *rbtree) 107238104Sdes{ 108238104Sdes LDNS_FREE(rbtree); 109238104Sdes} 110238104Sdes 111238104Sdes/* 112238104Sdes * Rotates the node to the left. 113238104Sdes * 114238104Sdes */ 115238104Sdesstatic void 116238104Sdesldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node) 117238104Sdes{ 118238104Sdes ldns_rbnode_t *right = node->right; 119238104Sdes node->right = right->left; 120238104Sdes if (right->left != LDNS_RBTREE_NULL) 121238104Sdes right->left->parent = node; 122238104Sdes 123238104Sdes right->parent = node->parent; 124238104Sdes 125238104Sdes if (node->parent != LDNS_RBTREE_NULL) { 126238104Sdes if (node == node->parent->left) { 127238104Sdes node->parent->left = right; 128238104Sdes } else { 129238104Sdes node->parent->right = right; 130238104Sdes } 131238104Sdes } else { 132238104Sdes rbtree->root = right; 133238104Sdes } 134238104Sdes right->left = node; 135238104Sdes node->parent = right; 136238104Sdes} 137238104Sdes 138238104Sdes/* 139238104Sdes * Rotates the node to the right. 140238104Sdes * 141238104Sdes */ 142238104Sdesstatic void 143238104Sdesldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node) 144238104Sdes{ 145238104Sdes ldns_rbnode_t *left = node->left; 146238104Sdes node->left = left->right; 147238104Sdes if (left->right != LDNS_RBTREE_NULL) 148238104Sdes left->right->parent = node; 149238104Sdes 150238104Sdes left->parent = node->parent; 151238104Sdes 152238104Sdes if (node->parent != LDNS_RBTREE_NULL) { 153238104Sdes if (node == node->parent->right) { 154238104Sdes node->parent->right = left; 155238104Sdes } else { 156238104Sdes node->parent->left = left; 157238104Sdes } 158238104Sdes } else { 159238104Sdes rbtree->root = left; 160238104Sdes } 161238104Sdes left->right = node; 162238104Sdes node->parent = left; 163238104Sdes} 164238104Sdes 165238104Sdesstatic void 166238104Sdesldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node) 167238104Sdes{ 168238104Sdes ldns_rbnode_t *uncle; 169238104Sdes 170238104Sdes /* While not at the root and need fixing... */ 171238104Sdes while (node != rbtree->root && node->parent->color == RED) { 172238104Sdes /* If our parent is left child of our grandparent... */ 173238104Sdes if (node->parent == node->parent->parent->left) { 174238104Sdes uncle = node->parent->parent->right; 175238104Sdes 176238104Sdes /* If our uncle is red... */ 177238104Sdes if (uncle->color == RED) { 178238104Sdes /* Paint the parent and the uncle black... */ 179238104Sdes node->parent->color = BLACK; 180238104Sdes uncle->color = BLACK; 181238104Sdes 182238104Sdes /* And the grandparent red... */ 183238104Sdes node->parent->parent->color = RED; 184238104Sdes 185238104Sdes /* And continue fixing the grandparent */ 186238104Sdes node = node->parent->parent; 187238104Sdes } else { /* Our uncle is black... */ 188238104Sdes /* Are we the right child? */ 189238104Sdes if (node == node->parent->right) { 190238104Sdes node = node->parent; 191238104Sdes ldns_rbtree_rotate_left(rbtree, node); 192238104Sdes } 193238104Sdes /* Now we're the left child, repaint and rotate... */ 194238104Sdes node->parent->color = BLACK; 195238104Sdes node->parent->parent->color = RED; 196238104Sdes ldns_rbtree_rotate_right(rbtree, node->parent->parent); 197238104Sdes } 198238104Sdes } else { 199238104Sdes uncle = node->parent->parent->left; 200238104Sdes 201238104Sdes /* If our uncle is red... */ 202238104Sdes if (uncle->color == RED) { 203238104Sdes /* Paint the parent and the uncle black... */ 204238104Sdes node->parent->color = BLACK; 205238104Sdes uncle->color = BLACK; 206238104Sdes 207238104Sdes /* And the grandparent red... */ 208238104Sdes node->parent->parent->color = RED; 209238104Sdes 210238104Sdes /* And continue fixing the grandparent */ 211238104Sdes node = node->parent->parent; 212238104Sdes } else { /* Our uncle is black... */ 213238104Sdes /* Are we the right child? */ 214238104Sdes if (node == node->parent->left) { 215238104Sdes node = node->parent; 216238104Sdes ldns_rbtree_rotate_right(rbtree, node); 217238104Sdes } 218238104Sdes /* Now we're the right child, repaint and rotate... */ 219238104Sdes node->parent->color = BLACK; 220238104Sdes node->parent->parent->color = RED; 221238104Sdes ldns_rbtree_rotate_left(rbtree, node->parent->parent); 222238104Sdes } 223238104Sdes } 224238104Sdes } 225238104Sdes rbtree->root->color = BLACK; 226238104Sdes} 227238104Sdes 228238104Sdesvoid 229238104Sdesldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree) 230238104Sdes{ 231238104Sdes (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree, 232238104Sdes data); 233238104Sdes} 234238104Sdes 235238104Sdes/* 236238104Sdes * Inserts a node into a red black tree. 237238104Sdes * 238238104Sdes * Returns NULL on failure or the pointer to the newly added node 239238104Sdes * otherwise. 240238104Sdes */ 241238104Sdesldns_rbnode_t * 242238104Sdesldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data) 243238104Sdes{ 244238104Sdes /* XXX Not necessary, but keeps compiler quiet... */ 245238104Sdes int r = 0; 246238104Sdes 247238104Sdes /* We start at the root of the tree */ 248238104Sdes ldns_rbnode_t *node = rbtree->root; 249238104Sdes ldns_rbnode_t *parent = LDNS_RBTREE_NULL; 250238104Sdes 251238104Sdes /* Lets find the new parent... */ 252238104Sdes while (node != LDNS_RBTREE_NULL) { 253238104Sdes /* Compare two keys, do we have a duplicate? */ 254238104Sdes if ((r = rbtree->cmp(data->key, node->key)) == 0) { 255238104Sdes return NULL; 256238104Sdes } 257238104Sdes parent = node; 258238104Sdes 259238104Sdes if (r < 0) { 260238104Sdes node = node->left; 261238104Sdes } else { 262238104Sdes node = node->right; 263238104Sdes } 264238104Sdes } 265238104Sdes 266238104Sdes /* Initialize the new node */ 267238104Sdes data->parent = parent; 268238104Sdes data->left = data->right = LDNS_RBTREE_NULL; 269238104Sdes data->color = RED; 270238104Sdes rbtree->count++; 271238104Sdes 272238104Sdes /* Insert it into the tree... */ 273238104Sdes if (parent != LDNS_RBTREE_NULL) { 274238104Sdes if (r < 0) { 275238104Sdes parent->left = data; 276238104Sdes } else { 277238104Sdes parent->right = data; 278238104Sdes } 279238104Sdes } else { 280238104Sdes rbtree->root = data; 281238104Sdes } 282238104Sdes 283238104Sdes /* Fix up the red-black properties... */ 284238104Sdes ldns_rbtree_insert_fixup(rbtree, data); 285238104Sdes 286238104Sdes return data; 287238104Sdes} 288238104Sdes 289238104Sdes/* 290238104Sdes * Searches the red black tree, returns the data if key is found or NULL otherwise. 291238104Sdes * 292238104Sdes */ 293238104Sdesldns_rbnode_t * 294238104Sdesldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key) 295238104Sdes{ 296238104Sdes ldns_rbnode_t *node; 297238104Sdes 298238104Sdes if (ldns_rbtree_find_less_equal(rbtree, key, &node)) { 299238104Sdes return node; 300238104Sdes } else { 301238104Sdes return NULL; 302238104Sdes } 303238104Sdes} 304238104Sdes 305238104Sdes/** helpers for delete: swap node colours */ 306238104Sdesstatic void swap_int8(uint8_t* x, uint8_t* y) 307238104Sdes{ 308238104Sdes uint8_t t = *x; *x = *y; *y = t; 309238104Sdes} 310238104Sdes 311238104Sdes/** helpers for delete: swap node pointers */ 312238104Sdesstatic void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y) 313238104Sdes{ 314238104Sdes ldns_rbnode_t* t = *x; *x = *y; *y = t; 315238104Sdes} 316238104Sdes 317238104Sdes/** Update parent pointers of child trees of 'parent' */ 318238104Sdesstatic void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new) 319238104Sdes{ 320238104Sdes if(parent == LDNS_RBTREE_NULL) 321238104Sdes { 322238104Sdes if(rbtree->root == old) rbtree->root = new; 323238104Sdes return; 324238104Sdes } 325238104Sdes if(parent->left == old) parent->left = new; 326238104Sdes if(parent->right == old) parent->right = new; 327238104Sdes} 328238104Sdes/** Update parent pointer of a node 'child' */ 329238104Sdesstatic void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new) 330238104Sdes{ 331238104Sdes if(child == LDNS_RBTREE_NULL) return; 332238104Sdes if(child->parent == old) child->parent = new; 333238104Sdes} 334238104Sdes 335238104Sdesldns_rbnode_t* 336238104Sdesldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key) 337238104Sdes{ 338238104Sdes ldns_rbnode_t *to_delete; 339238104Sdes ldns_rbnode_t *child; 340238104Sdes if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0; 341238104Sdes rbtree->count--; 342238104Sdes 343238104Sdes /* make sure we have at most one non-leaf child */ 344238104Sdes if(to_delete->left != LDNS_RBTREE_NULL && 345238104Sdes to_delete->right != LDNS_RBTREE_NULL) 346238104Sdes { 347238104Sdes /* swap with smallest from right subtree (or largest from left) */ 348238104Sdes ldns_rbnode_t *smright = to_delete->right; 349238104Sdes while(smright->left != LDNS_RBTREE_NULL) 350238104Sdes smright = smright->left; 351238104Sdes /* swap the smright and to_delete elements in the tree, 352238104Sdes * but the ldns_rbnode_t is first part of user data struct 353238104Sdes * so cannot just swap the keys and data pointers. Instead 354238104Sdes * readjust the pointers left,right,parent */ 355238104Sdes 356238104Sdes /* swap colors - colors are tied to the position in the tree */ 357238104Sdes swap_int8(&to_delete->color, &smright->color); 358238104Sdes 359238104Sdes /* swap child pointers in parents of smright/to_delete */ 360238104Sdes change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); 361238104Sdes if(to_delete->right != smright) 362238104Sdes change_parent_ptr(rbtree, smright->parent, smright, to_delete); 363238104Sdes 364238104Sdes /* swap parent pointers in children of smright/to_delete */ 365238104Sdes change_child_ptr(smright->left, smright, to_delete); 366238104Sdes change_child_ptr(smright->left, smright, to_delete); 367238104Sdes change_child_ptr(smright->right, smright, to_delete); 368238104Sdes change_child_ptr(smright->right, smright, to_delete); 369238104Sdes change_child_ptr(to_delete->left, to_delete, smright); 370238104Sdes if(to_delete->right != smright) 371238104Sdes change_child_ptr(to_delete->right, to_delete, smright); 372238104Sdes if(to_delete->right == smright) 373238104Sdes { 374238104Sdes /* set up so after swap they work */ 375238104Sdes to_delete->right = to_delete; 376238104Sdes smright->parent = smright; 377238104Sdes } 378238104Sdes 379238104Sdes /* swap pointers in to_delete/smright nodes */ 380238104Sdes swap_np(&to_delete->parent, &smright->parent); 381238104Sdes swap_np(&to_delete->left, &smright->left); 382238104Sdes swap_np(&to_delete->right, &smright->right); 383238104Sdes 384238104Sdes /* now delete to_delete (which is at the location where the smright previously was) */ 385238104Sdes } 386238104Sdes 387238104Sdes if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left; 388238104Sdes else child = to_delete->right; 389238104Sdes 390238104Sdes /* unlink to_delete from the tree, replace to_delete with child */ 391238104Sdes change_parent_ptr(rbtree, to_delete->parent, to_delete, child); 392238104Sdes change_child_ptr(child, to_delete, to_delete->parent); 393238104Sdes 394238104Sdes if(to_delete->color == RED) 395238104Sdes { 396238104Sdes /* if node is red then the child (black) can be swapped in */ 397238104Sdes } 398238104Sdes else if(child->color == RED) 399238104Sdes { 400238104Sdes /* change child to BLACK, removing a RED node is no problem */ 401238104Sdes if(child!=LDNS_RBTREE_NULL) child->color = BLACK; 402238104Sdes } 403238104Sdes else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent); 404238104Sdes 405238104Sdes /* unlink completely */ 406238104Sdes to_delete->parent = LDNS_RBTREE_NULL; 407238104Sdes to_delete->left = LDNS_RBTREE_NULL; 408238104Sdes to_delete->right = LDNS_RBTREE_NULL; 409238104Sdes to_delete->color = BLACK; 410238104Sdes return to_delete; 411238104Sdes} 412238104Sdes 413238104Sdesstatic void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent) 414238104Sdes{ 415238104Sdes ldns_rbnode_t* sibling; 416238104Sdes int go_up = 1; 417238104Sdes 418238104Sdes /* determine sibling to the node that is one-black short */ 419238104Sdes if(child_parent->right == child) sibling = child_parent->left; 420238104Sdes else sibling = child_parent->right; 421238104Sdes 422238104Sdes while(go_up) 423238104Sdes { 424238104Sdes if(child_parent == LDNS_RBTREE_NULL) 425238104Sdes { 426238104Sdes /* removed parent==black from root, every path, so ok */ 427238104Sdes return; 428238104Sdes } 429238104Sdes 430238104Sdes if(sibling->color == RED) 431238104Sdes { /* rotate to get a black sibling */ 432238104Sdes child_parent->color = RED; 433238104Sdes sibling->color = BLACK; 434238104Sdes if(child_parent->right == child) 435238104Sdes ldns_rbtree_rotate_right(rbtree, child_parent); 436238104Sdes else ldns_rbtree_rotate_left(rbtree, child_parent); 437238104Sdes /* new sibling after rotation */ 438238104Sdes if(child_parent->right == child) sibling = child_parent->left; 439238104Sdes else sibling = child_parent->right; 440238104Sdes } 441238104Sdes 442238104Sdes if(child_parent->color == BLACK 443238104Sdes && sibling->color == BLACK 444238104Sdes && sibling->left->color == BLACK 445238104Sdes && sibling->right->color == BLACK) 446238104Sdes { /* fixup local with recolor of sibling */ 447238104Sdes if(sibling != LDNS_RBTREE_NULL) 448238104Sdes sibling->color = RED; 449238104Sdes 450238104Sdes child = child_parent; 451238104Sdes child_parent = child_parent->parent; 452238104Sdes /* prepare to go up, new sibling */ 453238104Sdes if(child_parent->right == child) sibling = child_parent->left; 454238104Sdes else sibling = child_parent->right; 455238104Sdes } 456238104Sdes else go_up = 0; 457238104Sdes } 458238104Sdes 459238104Sdes if(child_parent->color == RED 460238104Sdes && sibling->color == BLACK 461238104Sdes && sibling->left->color == BLACK 462238104Sdes && sibling->right->color == BLACK) 463238104Sdes { 464238104Sdes /* move red to sibling to rebalance */ 465238104Sdes if(sibling != LDNS_RBTREE_NULL) 466238104Sdes sibling->color = RED; 467238104Sdes child_parent->color = BLACK; 468238104Sdes return; 469238104Sdes } 470238104Sdes 471238104Sdes /* get a new sibling, by rotating at sibling. See which child 472238104Sdes of sibling is red */ 473238104Sdes if(child_parent->right == child 474238104Sdes && sibling->color == BLACK 475238104Sdes && sibling->right->color == RED 476238104Sdes && sibling->left->color == BLACK) 477238104Sdes { 478238104Sdes sibling->color = RED; 479238104Sdes sibling->right->color = BLACK; 480238104Sdes ldns_rbtree_rotate_left(rbtree, sibling); 481238104Sdes /* new sibling after rotation */ 482238104Sdes if(child_parent->right == child) sibling = child_parent->left; 483238104Sdes else sibling = child_parent->right; 484238104Sdes } 485238104Sdes else if(child_parent->left == child 486238104Sdes && sibling->color == BLACK 487238104Sdes && sibling->left->color == RED 488238104Sdes && sibling->right->color == BLACK) 489238104Sdes { 490238104Sdes sibling->color = RED; 491238104Sdes sibling->left->color = BLACK; 492238104Sdes ldns_rbtree_rotate_right(rbtree, sibling); 493238104Sdes /* new sibling after rotation */ 494238104Sdes if(child_parent->right == child) sibling = child_parent->left; 495238104Sdes else sibling = child_parent->right; 496238104Sdes } 497238104Sdes 498238104Sdes /* now we have a black sibling with a red child. rotate and exchange colors. */ 499238104Sdes sibling->color = child_parent->color; 500238104Sdes child_parent->color = BLACK; 501238104Sdes if(child_parent->right == child) 502238104Sdes { 503238104Sdes sibling->left->color = BLACK; 504238104Sdes ldns_rbtree_rotate_right(rbtree, child_parent); 505238104Sdes } 506238104Sdes else 507238104Sdes { 508238104Sdes sibling->right->color = BLACK; 509238104Sdes ldns_rbtree_rotate_left(rbtree, child_parent); 510238104Sdes } 511238104Sdes} 512238104Sdes 513238104Sdesint 514238104Sdesldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result) 515238104Sdes{ 516238104Sdes int r; 517238104Sdes ldns_rbnode_t *node; 518238104Sdes 519238104Sdes /* We start at root... */ 520238104Sdes node = rbtree->root; 521238104Sdes 522238104Sdes *result = NULL; 523238104Sdes 524238104Sdes /* While there are children... */ 525238104Sdes while (node != LDNS_RBTREE_NULL) { 526238104Sdes r = rbtree->cmp(key, node->key); 527238104Sdes if (r == 0) { 528238104Sdes /* Exact match */ 529238104Sdes *result = node; 530238104Sdes return 1; 531238104Sdes } 532238104Sdes if (r < 0) { 533238104Sdes node = node->left; 534238104Sdes } else { 535238104Sdes /* Temporary match */ 536238104Sdes *result = node; 537238104Sdes node = node->right; 538238104Sdes } 539238104Sdes } 540238104Sdes return 0; 541238104Sdes} 542238104Sdes 543238104Sdes/* 544238104Sdes * Finds the first element in the red black tree 545238104Sdes * 546238104Sdes */ 547238104Sdesldns_rbnode_t * 548238104Sdesldns_rbtree_first (ldns_rbtree_t *rbtree) 549238104Sdes{ 550238104Sdes ldns_rbnode_t *node = rbtree->root; 551238104Sdes 552238104Sdes if (rbtree->root != LDNS_RBTREE_NULL) { 553238104Sdes for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left); 554238104Sdes } 555238104Sdes return node; 556238104Sdes} 557238104Sdes 558238104Sdesldns_rbnode_t * 559238104Sdesldns_rbtree_last (ldns_rbtree_t *rbtree) 560238104Sdes{ 561238104Sdes ldns_rbnode_t *node = rbtree->root; 562238104Sdes 563238104Sdes if (rbtree->root != LDNS_RBTREE_NULL) { 564238104Sdes for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right); 565238104Sdes } 566238104Sdes return node; 567238104Sdes} 568238104Sdes 569238104Sdes/* 570238104Sdes * Returns the next node... 571238104Sdes * 572238104Sdes */ 573238104Sdesldns_rbnode_t * 574238104Sdesldns_rbtree_next (ldns_rbnode_t *node) 575238104Sdes{ 576238104Sdes ldns_rbnode_t *parent; 577238104Sdes 578238104Sdes if (node->right != LDNS_RBTREE_NULL) { 579238104Sdes /* One right, then keep on going left... */ 580238104Sdes for (node = node->right; 581238104Sdes node->left != LDNS_RBTREE_NULL; 582238104Sdes node = node->left); 583238104Sdes } else { 584238104Sdes parent = node->parent; 585238104Sdes while (parent != LDNS_RBTREE_NULL && node == parent->right) { 586238104Sdes node = parent; 587238104Sdes parent = parent->parent; 588238104Sdes } 589238104Sdes node = parent; 590238104Sdes } 591238104Sdes return node; 592238104Sdes} 593238104Sdes 594238104Sdesldns_rbnode_t * 595238104Sdesldns_rbtree_previous(ldns_rbnode_t *node) 596238104Sdes{ 597238104Sdes ldns_rbnode_t *parent; 598238104Sdes 599238104Sdes if (node->left != LDNS_RBTREE_NULL) { 600238104Sdes /* One left, then keep on going right... */ 601238104Sdes for (node = node->left; 602238104Sdes node->right != LDNS_RBTREE_NULL; 603238104Sdes node = node->right); 604238104Sdes } else { 605238104Sdes parent = node->parent; 606238104Sdes while (parent != LDNS_RBTREE_NULL && node == parent->left) { 607238104Sdes node = parent; 608238104Sdes parent = parent->parent; 609238104Sdes } 610238104Sdes node = parent; 611238104Sdes } 612238104Sdes return node; 613238104Sdes} 614238104Sdes 615238104Sdes/** 616238104Sdes * split off elements number of elements from the start 617238104Sdes * of the name tree and return a new tree 618238104Sdes */ 619238104Sdesldns_rbtree_t * 620238104Sdesldns_rbtree_split(ldns_rbtree_t *tree, 621238104Sdes size_t elements) 622238104Sdes{ 623238104Sdes ldns_rbtree_t *new_tree; 624238104Sdes ldns_rbnode_t *cur_node; 625238104Sdes ldns_rbnode_t *move_node; 626238104Sdes size_t count = 0; 627238104Sdes 628238104Sdes new_tree = ldns_rbtree_create(tree->cmp); 629238104Sdes 630238104Sdes cur_node = ldns_rbtree_first(tree); 631238104Sdes while (count < elements && cur_node != LDNS_RBTREE_NULL) { 632238104Sdes move_node = ldns_rbtree_delete(tree, cur_node->key); 633238104Sdes (void)ldns_rbtree_insert(new_tree, move_node); 634238104Sdes cur_node = ldns_rbtree_first(tree); 635238104Sdes count++; 636238104Sdes } 637238104Sdes 638238104Sdes return new_tree; 639238104Sdes} 640238104Sdes 641238104Sdes/* 642238104Sdes * add all node from the second tree to the first (removing them from the 643238104Sdes * second), and fix up nsec(3)s if present 644238104Sdes */ 645238104Sdesvoid 646238104Sdesldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2) 647238104Sdes{ 648238104Sdes ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1); 649238104Sdes} 650238104Sdes 651238104Sdes/** recursive descent traverse */ 652238104Sdesstatic void 653238104Sdestraverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg, 654238104Sdes ldns_rbnode_t* node) 655238104Sdes{ 656238104Sdes if(!node || node == LDNS_RBTREE_NULL) 657238104Sdes return; 658238104Sdes /* recurse */ 659238104Sdes traverse_post(func, arg, node->left); 660238104Sdes traverse_post(func, arg, node->right); 661238104Sdes /* call user func */ 662238104Sdes (*func)(node, arg); 663238104Sdes} 664238104Sdes 665238104Sdesvoid 666238104Sdesldns_traverse_postorder(ldns_rbtree_t* tree, 667238104Sdes void (*func)(ldns_rbnode_t*, void*), void* arg) 668238104Sdes{ 669238104Sdes traverse_post(func, arg, tree->root); 670238104Sdes} 671