1 /*- 2 * Copyright (c) 2001 The NetBSD Foundation, Inc. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to The NetBSD Foundation 6 * by Matt Thomas <matt@3am-software.com>. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 18 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 19 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 21 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 * 29 * Based on: NetBSD: rb.c,v 1.6 2010/04/30 13:58:09 joerg Exp 30 */ 31 32 #include "archive_platform.h" 33 34 #include <stddef.h> 35 36 #include "archive_rb.h" 37 38 /* Keep in sync with archive_rb.h */ 39 #define RB_DIR_LEFT 0 40 #define RB_DIR_RIGHT 1 41 #define RB_DIR_OTHER 1 42 #define rb_left rb_nodes[RB_DIR_LEFT] 43 #define rb_right rb_nodes[RB_DIR_RIGHT] 44 45 #define RB_FLAG_POSITION 0x2 46 #define RB_FLAG_RED 0x1 47 #define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED) 48 #define RB_FATHER(rb) \ 49 ((struct archive_rb_node *)((rb)->rb_info & ~RB_FLAG_MASK)) 50 #define RB_SET_FATHER(rb, father) \ 51 ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK))) 52 53 #define RB_SENTINEL_P(rb) ((rb) == NULL) 54 #define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left) 55 #define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right) 56 #define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb))) 57 #define RB_CHILDLESS_P(rb) \ 58 (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb))) 59 #define RB_TWOCHILDREN_P(rb) \ 60 (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb)) 61 62 #define RB_POSITION(rb) \ 63 (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT) 64 #define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT) 65 #define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT) 66 #define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0) 67 #define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0) 68 #define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED)) 69 #define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED)) 70 #define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED)) 71 #define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb)) 72 #define RB_SET_POSITION(rb, position) \ 73 ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \ 74 ((rb)->rb_info &= ~RB_FLAG_POSITION))) 75 #define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK)) 76 #define RB_COPY_PROPERTIES(dst, src) \ 77 ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK)) 78 #define RB_SWAP_PROPERTIES(a, b) do { \ 79 uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \ 80 (a)->rb_info ^= xorinfo; \ 81 (b)->rb_info ^= xorinfo; \ 82 } while (/*CONSTCOND*/ 0) 83 84 static void __archive_rb_tree_insert_rebalance(struct archive_rb_tree *, 85 struct archive_rb_node *); 86 static void __archive_rb_tree_removal_rebalance(struct archive_rb_tree *, 87 struct archive_rb_node *, unsigned int); 88 89 #define RB_SENTINEL_NODE NULL 90 91 #define T 1 92 #define F 0 93 94 void 95 __archive_rb_tree_init(struct archive_rb_tree *rbt, 96 const struct archive_rb_tree_ops *ops) 97 { 98 rbt->rbt_ops = ops; 99 *((struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE; 100 } 101 102 struct archive_rb_node * 103 __archive_rb_tree_find_node(struct archive_rb_tree *rbt, const void *key) 104 { 105 archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; 106 struct archive_rb_node *parent = rbt->rbt_root; 107 108 while (!RB_SENTINEL_P(parent)) { 109 const signed int diff = (*compare_key)(parent, key); 110 if (diff == 0) 111 return parent; 112 parent = parent->rb_nodes[diff > 0]; 113 } 114 115 return NULL; 116 } 117 118 struct archive_rb_node * 119 __archive_rb_tree_find_node_geq(struct archive_rb_tree *rbt, const void *key) 120 { 121 archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; 122 struct archive_rb_node *parent = rbt->rbt_root; 123 struct archive_rb_node *last = NULL; 124 125 while (!RB_SENTINEL_P(parent)) { 126 const signed int diff = (*compare_key)(parent, key); 127 if (diff == 0) 128 return parent; 129 if (diff < 0) 130 last = parent; 131 parent = parent->rb_nodes[diff > 0]; 132 } 133 134 return last; 135 } 136 137 struct archive_rb_node * 138 __archive_rb_tree_find_node_leq(struct archive_rb_tree *rbt, const void *key) 139 { 140 archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; 141 struct archive_rb_node *parent = rbt->rbt_root; 142 struct archive_rb_node *last = NULL; 143 144 while (!RB_SENTINEL_P(parent)) { 145 const signed int diff = (*compare_key)(parent, key); 146 if (diff == 0) 147 return parent; 148 if (diff > 0) 149 last = parent; 150 parent = parent->rb_nodes[diff > 0]; 151 } 152 153 return last; 154 } 155 156 int 157 __archive_rb_tree_insert_node(struct archive_rb_tree *rbt, 158 struct archive_rb_node *self) 159 { 160 archive_rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes; 161 struct archive_rb_node *parent, *tmp; 162 unsigned int position; 163 int rebalance; 164 165 tmp = rbt->rbt_root; 166 /* 167 * This is a hack. Because rbt->rbt_root is just a 168 * struct archive_rb_node *, just like rb_node->rb_nodes[RB_DIR_LEFT], 169 * we can use this fact to avoid a lot of tests for root and know 170 * that even at root, updating 171 * RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will 172 * update rbt->rbt_root. 173 */ 174 parent = (struct archive_rb_node *)(void *)&rbt->rbt_root; 175 position = RB_DIR_LEFT; 176 177 /* 178 * Find out where to place this new leaf. 179 */ 180 while (!RB_SENTINEL_P(tmp)) { 181 const signed int diff = (*compare_nodes)(tmp, self); 182 if (diff == 0) { 183 /* 184 * Node already exists; don't insert. 185 */ 186 return F; 187 } 188 parent = tmp; 189 position = (diff > 0); 190 tmp = parent->rb_nodes[position]; 191 } 192 193 /* 194 * Initialize the node and insert as a leaf into the tree. 195 */ 196 RB_SET_FATHER(self, parent); 197 RB_SET_POSITION(self, position); 198 if (parent == (struct archive_rb_node *)(void *)&rbt->rbt_root) { 199 RB_MARK_BLACK(self); /* root is always black */ 200 rebalance = F; 201 } else { 202 /* 203 * All new nodes are colored red. We only need to rebalance 204 * if our parent is also red. 205 */ 206 RB_MARK_RED(self); 207 rebalance = RB_RED_P(parent); 208 } 209 self->rb_left = parent->rb_nodes[position]; 210 self->rb_right = parent->rb_nodes[position]; 211 parent->rb_nodes[position] = self; 212 213 /* 214 * Rebalance tree after insertion 215 */ 216 if (rebalance) 217 __archive_rb_tree_insert_rebalance(rbt, self); 218 219 return T; 220 } 221 222 /* 223 * Swap the location and colors of 'self' and its child @ which. The child 224 * can not be a sentinel node. This is our rotation function. However, 225 * since it preserves coloring, it great simplifies both insertion and 226 * removal since rotation almost always involves the exchanging of colors 227 * as a separate step. 228 */ 229 /*ARGSUSED*/ 230 static void 231 __archive_rb_tree_reparent_nodes( 232 struct archive_rb_node *old_father, const unsigned int which) 233 { 234 const unsigned int other = which ^ RB_DIR_OTHER; 235 struct archive_rb_node * const grandpa = RB_FATHER(old_father); 236 struct archive_rb_node * const old_child = old_father->rb_nodes[which]; 237 struct archive_rb_node * const new_father = old_child; 238 struct archive_rb_node * const new_child = old_father; 239 240 if (new_father == NULL) 241 return; 242 /* 243 * Exchange descendant linkages. 244 */ 245 grandpa->rb_nodes[RB_POSITION(old_father)] = new_father; 246 new_child->rb_nodes[which] = old_child->rb_nodes[other]; 247 new_father->rb_nodes[other] = new_child; 248 249 /* 250 * Update ancestor linkages 251 */ 252 RB_SET_FATHER(new_father, grandpa); 253 RB_SET_FATHER(new_child, new_father); 254 255 /* 256 * Exchange properties between new_father and new_child. The only 257 * change is that new_child's position is now on the other side. 258 */ 259 RB_SWAP_PROPERTIES(new_father, new_child); 260 RB_SET_POSITION(new_child, other); 261 262 /* 263 * Make sure to reparent the new child to ourself. 264 */ 265 if (!RB_SENTINEL_P(new_child->rb_nodes[which])) { 266 RB_SET_FATHER(new_child->rb_nodes[which], new_child); 267 RB_SET_POSITION(new_child->rb_nodes[which], which); 268 } 269 270 } 271 272 static void 273 __archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt, 274 struct archive_rb_node *self) 275 { 276 struct archive_rb_node * father = RB_FATHER(self); 277 struct archive_rb_node * grandpa; 278 struct archive_rb_node * uncle; 279 unsigned int which; 280 unsigned int other; 281 282 for (;;) { 283 /* 284 * We are red and our parent is red, therefore we must have a 285 * grandfather and he must be black. 286 */ 287 grandpa = RB_FATHER(father); 288 which = (father == grandpa->rb_right); 289 other = which ^ RB_DIR_OTHER; 290 uncle = grandpa->rb_nodes[other]; 291 292 if (RB_BLACK_P(uncle)) 293 break; 294 295 /* 296 * Case 1: our uncle is red 297 * Simply invert the colors of our parent and 298 * uncle and make our grandparent red. And 299 * then solve the problem up at his level. 300 */ 301 RB_MARK_BLACK(uncle); 302 RB_MARK_BLACK(father); 303 if (RB_ROOT_P(rbt, grandpa)) { 304 /* 305 * If our grandpa is root, don't bother 306 * setting him to red, just return. 307 */ 308 return; 309 } 310 RB_MARK_RED(grandpa); 311 self = grandpa; 312 father = RB_FATHER(self); 313 if (RB_BLACK_P(father)) { 314 /* 315 * If our great-grandpa is black, we're done. 316 */ 317 return; 318 } 319 } 320 321 /* 322 * Case 2&3: our uncle is black. 323 */ 324 if (self == father->rb_nodes[other]) { 325 /* 326 * Case 2: we are on the same side as our uncle 327 * Swap ourselves with our parent so this case 328 * becomes case 3. Basically our parent becomes our 329 * child. 330 */ 331 __archive_rb_tree_reparent_nodes(father, other); 332 } 333 /* 334 * Case 3: we are opposite a child of a black uncle. 335 * Swap our parent and grandparent. Since our grandfather 336 * is black, our father will become black and our new sibling 337 * (former grandparent) will become red. 338 */ 339 __archive_rb_tree_reparent_nodes(grandpa, which); 340 341 /* 342 * Final step: Set the root to black. 343 */ 344 RB_MARK_BLACK(rbt->rbt_root); 345 } 346 347 static void 348 __archive_rb_tree_prune_node(struct archive_rb_tree *rbt, 349 struct archive_rb_node *self, int rebalance) 350 { 351 const unsigned int which = RB_POSITION(self); 352 struct archive_rb_node *father = RB_FATHER(self); 353 354 /* 355 * Since we are childless, we know that self->rb_left is pointing 356 * to the sentinel node. 357 */ 358 father->rb_nodes[which] = self->rb_left; 359 360 /* 361 * Rebalance if requested. 362 */ 363 if (rebalance) 364 __archive_rb_tree_removal_rebalance(rbt, father, which); 365 } 366 367 /* 368 * When deleting an interior node 369 */ 370 static void 371 __archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree *rbt, 372 struct archive_rb_node *self, struct archive_rb_node *standin) 373 { 374 const unsigned int standin_which = RB_POSITION(standin); 375 unsigned int standin_other = standin_which ^ RB_DIR_OTHER; 376 struct archive_rb_node *standin_son; 377 struct archive_rb_node *standin_father = RB_FATHER(standin); 378 int rebalance = RB_BLACK_P(standin); 379 380 if (standin_father == self) { 381 /* 382 * As a child of self, any children would be opposite of 383 * our parent. 384 */ 385 standin_son = standin->rb_nodes[standin_which]; 386 } else { 387 /* 388 * Since we aren't a child of self, any children would be 389 * on the same side as our parent. 390 */ 391 standin_son = standin->rb_nodes[standin_other]; 392 } 393 394 if (RB_RED_P(standin_son)) { 395 /* 396 * We know we have a red child so if we flip it to black 397 * we don't have to rebalance. 398 */ 399 RB_MARK_BLACK(standin_son); 400 rebalance = F; 401 402 if (standin_father != self) { 403 /* 404 * Change the son's parentage to point to his grandpa. 405 */ 406 RB_SET_FATHER(standin_son, standin_father); 407 RB_SET_POSITION(standin_son, standin_which); 408 } 409 } 410 411 if (standin_father == self) { 412 /* 413 * If we are about to delete the standin's father, then when 414 * we call rebalance, we need to use ourselves as our father. 415 * Otherwise remember our original father. Also, since we are 416 * our standin's father we only need to reparent the standin's 417 * brother. 418 * 419 * | R --> S | 420 * | Q S --> Q T | 421 * | t --> | 422 * 423 * Have our son/standin adopt his brother as his new son. 424 */ 425 standin_father = standin; 426 } else { 427 /* 428 * | R --> S . | 429 * | / \ | T --> / \ | / | 430 * | ..... | S --> ..... | T | 431 * 432 * Sever standin's connection to his father. 433 */ 434 standin_father->rb_nodes[standin_which] = standin_son; 435 /* 436 * Adopt the far son. 437 */ 438 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; 439 RB_SET_FATHER(standin->rb_nodes[standin_other], standin); 440 /* 441 * Use standin_other because we need to preserve standin_which 442 * for the removal_rebalance. 443 */ 444 standin_other = standin_which; 445 } 446 447 /* 448 * Move the only remaining son to our standin. If our standin is our 449 * son, this will be the only son needed to be moved. 450 */ 451 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; 452 RB_SET_FATHER(standin->rb_nodes[standin_other], standin); 453 454 /* 455 * Now copy the result of self to standin and then replace 456 * self with standin in the tree. 457 */ 458 RB_COPY_PROPERTIES(standin, self); 459 RB_SET_FATHER(standin, RB_FATHER(self)); 460 RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin; 461 462 if (rebalance) 463 __archive_rb_tree_removal_rebalance(rbt, standin_father, standin_which); 464 } 465 466 /* 467 * We could do this by doing 468 * __archive_rb_tree_node_swap(rbt, self, which); 469 * __archive_rb_tree_prune_node(rbt, self, F); 470 * 471 * But it's more efficient to just evaluate and recolor the child. 472 */ 473 static void 474 __archive_rb_tree_prune_blackred_branch( 475 struct archive_rb_node *self, unsigned int which) 476 { 477 struct archive_rb_node *father = RB_FATHER(self); 478 struct archive_rb_node *son = self->rb_nodes[which]; 479 480 /* 481 * Remove ourselves from the tree and give our former child our 482 * properties (position, color, root). 483 */ 484 RB_COPY_PROPERTIES(son, self); 485 father->rb_nodes[RB_POSITION(son)] = son; 486 RB_SET_FATHER(son, father); 487 } 488 /* 489 * 490 */ 491 void 492 __archive_rb_tree_remove_node(struct archive_rb_tree *rbt, 493 struct archive_rb_node *self) 494 { 495 struct archive_rb_node *standin; 496 unsigned int which; 497 498 /* 499 * In the following diagrams, we (the node to be removed) are S. Red 500 * nodes are lowercase. T could be either red or black. 501 * 502 * Remember the major axiom of the red-black tree: the number of 503 * black nodes from the root to each leaf is constant across all 504 * leaves, only the number of red nodes varies. 505 * 506 * Thus removing a red leaf doesn't require any other changes to a 507 * red-black tree. So if we must remove a node, attempt to rearrange 508 * the tree so we can remove a red node. 509 * 510 * The simplest case is a childless red node or a childless root node: 511 * 512 * | T --> T | or | R --> * | 513 * | s --> * | 514 */ 515 if (RB_CHILDLESS_P(self)) { 516 const int rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self); 517 __archive_rb_tree_prune_node(rbt, self, rebalance); 518 return; 519 } 520 if (!RB_TWOCHILDREN_P(self)) { 521 /* 522 * The next simplest case is the node we are deleting is 523 * black and has one red child. 524 * 525 * | T --> T --> T | 526 * | S --> R --> R | 527 * | r --> s --> * | 528 */ 529 which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT; 530 __archive_rb_tree_prune_blackred_branch(self, which); 531 return; 532 } 533 534 /* 535 * We invert these because we prefer to remove from the inside of 536 * the tree. 537 */ 538 which = RB_POSITION(self) ^ RB_DIR_OTHER; 539 540 /* 541 * Let's find the node closes to us opposite of our parent 542 * Now swap it with ourself, "prune" it, and rebalance, if needed. 543 */ 544 standin = __archive_rb_tree_iterate(rbt, self, which); 545 __archive_rb_tree_swap_prune_and_rebalance(rbt, self, standin); 546 } 547 548 static void 549 __archive_rb_tree_removal_rebalance(struct archive_rb_tree *rbt, 550 struct archive_rb_node *parent, unsigned int which) 551 { 552 553 while (RB_BLACK_P(parent->rb_nodes[which])) { 554 unsigned int other = which ^ RB_DIR_OTHER; 555 struct archive_rb_node *brother = parent->rb_nodes[other]; 556 557 if (brother == NULL) 558 return;/* The tree may be broken. */ 559 /* 560 * For cases 1, 2a, and 2b, our brother's children must 561 * be black and our father must be black 562 */ 563 if (RB_BLACK_P(parent) 564 && RB_BLACK_P(brother->rb_left) 565 && RB_BLACK_P(brother->rb_right)) { 566 if (RB_RED_P(brother)) { 567 /* 568 * Case 1: Our brother is red, swap its 569 * position (and colors) with our parent. 570 * This should now be case 2b (unless C or E 571 * has a red child which is case 3; thus no 572 * explicit branch to case 2b). 573 * 574 * B -> D 575 * A d -> b E 576 * C E -> A C 577 */ 578 __archive_rb_tree_reparent_nodes(parent, other); 579 brother = parent->rb_nodes[other]; 580 if (brother == NULL) 581 return;/* The tree may be broken. */ 582 } else { 583 /* 584 * Both our parent and brother are black. 585 * Change our brother to red, advance up rank 586 * and go through the loop again. 587 * 588 * B -> *B 589 * *A D -> A d 590 * C E -> C E 591 */ 592 RB_MARK_RED(brother); 593 if (RB_ROOT_P(rbt, parent)) 594 return; /* root == parent == black */ 595 which = RB_POSITION(parent); 596 parent = RB_FATHER(parent); 597 continue; 598 } 599 } 600 /* 601 * Avoid an else here so that case 2a above can hit either 602 * case 2b, 3, or 4. 603 */ 604 if (RB_RED_P(parent) 605 && RB_BLACK_P(brother) 606 && RB_BLACK_P(brother->rb_left) 607 && RB_BLACK_P(brother->rb_right)) { 608 /* 609 * We are black, our father is red, our brother and 610 * both nephews are black. Simply invert/exchange the 611 * colors of our father and brother (to black and red 612 * respectively). 613 * 614 * | f --> F | 615 * | * B --> * b | 616 * | N N --> N N | 617 */ 618 RB_MARK_BLACK(parent); 619 RB_MARK_RED(brother); 620 break; /* We're done! */ 621 } else { 622 /* 623 * Our brother must be black and have at least one 624 * red child (it may have two). 625 */ 626 if (RB_BLACK_P(brother->rb_nodes[other])) { 627 /* 628 * Case 3: our brother is black, our near 629 * nephew is red, and our far nephew is black. 630 * Swap our brother with our near nephew. 631 * This result in a tree that matches case 4. 632 * (Our father could be red or black). 633 * 634 * | F --> F | 635 * | x B --> x B | 636 * | n --> n | 637 */ 638 __archive_rb_tree_reparent_nodes(brother, which); 639 brother = parent->rb_nodes[other]; 640 } 641 /* 642 * Case 4: our brother is black and our far nephew 643 * is red. Swap our father and brother locations and 644 * change our far nephew to black. (these can be 645 * done in either order so we change the color first). 646 * The result is a valid red-black tree and is a 647 * terminal case. (again we don't care about the 648 * father's color) 649 * 650 * If the father is red, we will get a red-black-black 651 * tree: 652 * | f -> f --> b | 653 * | B -> B --> F N | 654 * | n -> N --> | 655 * 656 * If the father is black, we will get an all black 657 * tree: 658 * | F -> F --> B | 659 * | B -> B --> F N | 660 * | n -> N --> | 661 * 662 * If we had two red nephews, then after the swap, 663 * our former father would have a red grandson. 664 */ 665 if (brother->rb_nodes[other] == NULL) 666 return;/* The tree may be broken. */ 667 RB_MARK_BLACK(brother->rb_nodes[other]); 668 __archive_rb_tree_reparent_nodes(parent, other); 669 break; /* We're done! */ 670 } 671 } 672 } 673 674 struct archive_rb_node * 675 __archive_rb_tree_iterate(struct archive_rb_tree *rbt, 676 struct archive_rb_node *self, const unsigned int direction) 677 { 678 const unsigned int other = direction ^ RB_DIR_OTHER; 679 680 if (self == NULL) { 681 self = rbt->rbt_root; 682 if (RB_SENTINEL_P(self)) 683 return NULL; 684 while (!RB_SENTINEL_P(self->rb_nodes[direction])) 685 self = self->rb_nodes[direction]; 686 return self; 687 } 688 /* 689 * We can't go any further in this direction. We proceed up in the 690 * opposite direction until our parent is in direction we want to go. 691 */ 692 if (RB_SENTINEL_P(self->rb_nodes[direction])) { 693 while (!RB_ROOT_P(rbt, self)) { 694 if (other == (unsigned int)RB_POSITION(self)) 695 return RB_FATHER(self); 696 self = RB_FATHER(self); 697 } 698 return NULL; 699 } 700 701 /* 702 * Advance down one in current direction and go down as far as possible 703 * in the opposite direction. 704 */ 705 self = self->rb_nodes[direction]; 706 while (!RB_SENTINEL_P(self->rb_nodes[other])) 707 self = self->rb_nodes[other]; 708 return self; 709 } 710