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 } 670