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 *((const 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 /* 241 * Exchange descendant linkages. 242 */ 243 grandpa->rb_nodes[RB_POSITION(old_father)] = new_father; 244 new_child->rb_nodes[which] = old_child->rb_nodes[other]; 245 new_father->rb_nodes[other] = new_child; 246 247 /* 248 * Update ancestor linkages 249 */ 250 RB_SET_FATHER(new_father, grandpa); 251 RB_SET_FATHER(new_child, new_father); 252 253 /* 254 * Exchange properties between new_father and new_child. The only 255 * change is that new_child's position is now on the other side. 256 */ 257 RB_SWAP_PROPERTIES(new_father, new_child); 258 RB_SET_POSITION(new_child, other); 259 260 /* 261 * Make sure to reparent the new child to ourself. 262 */ 263 if (!RB_SENTINEL_P(new_child->rb_nodes[which])) { 264 RB_SET_FATHER(new_child->rb_nodes[which], new_child); 265 RB_SET_POSITION(new_child->rb_nodes[which], which); 266 } 267 268 } 269 270 static void 271 __archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt, 272 struct archive_rb_node *self) 273 { 274 struct archive_rb_node * father = RB_FATHER(self); 275 struct archive_rb_node * grandpa; 276 struct archive_rb_node * uncle; 277 unsigned int which; 278 unsigned int other; 279 280 for (;;) { 281 /* 282 * We are red and our parent is red, therefore we must have a 283 * grandfather and he must be black. 284 */ 285 grandpa = RB_FATHER(father); 286 which = (father == grandpa->rb_right); 287 other = which ^ RB_DIR_OTHER; 288 uncle = grandpa->rb_nodes[other]; 289 290 if (RB_BLACK_P(uncle)) 291 break; 292 293 /* 294 * Case 1: our uncle is red 295 * Simply invert the colors of our parent and 296 * uncle and make our grandparent red. And 297 * then solve the problem up at his level. 298 */ 299 RB_MARK_BLACK(uncle); 300 RB_MARK_BLACK(father); 301 if (RB_ROOT_P(rbt, grandpa)) { 302 /* 303 * If our grandpa is root, don't bother 304 * setting him to red, just return. 305 */ 306 return; 307 } 308 RB_MARK_RED(grandpa); 309 self = grandpa; 310 father = RB_FATHER(self); 311 if (RB_BLACK_P(father)) { 312 /* 313 * If our greatgrandpa is black, we're done. 314 */ 315 return; 316 } 317 } 318 319 /* 320 * Case 2&3: our uncle is black. 321 */ 322 if (self == father->rb_nodes[other]) { 323 /* 324 * Case 2: we are on the same side as our uncle 325 * Swap ourselves with our parent so this case 326 * becomes case 3. Basically our parent becomes our 327 * child. 328 */ 329 __archive_rb_tree_reparent_nodes(father, other); 330 } 331 /* 332 * Case 3: we are opposite a child of a black uncle. 333 * Swap our parent and grandparent. Since our grandfather 334 * is black, our father will become black and our new sibling 335 * (former grandparent) will become red. 336 */ 337 __archive_rb_tree_reparent_nodes(grandpa, which); 338 339 /* 340 * Final step: Set the root to black. 341 */ 342 RB_MARK_BLACK(rbt->rbt_root); 343 } 344 345 static void 346 __archive_rb_tree_prune_node(struct archive_rb_tree *rbt, 347 struct archive_rb_node *self, int rebalance) 348 { 349 const unsigned int which = RB_POSITION(self); 350 struct archive_rb_node *father = RB_FATHER(self); 351 352 /* 353 * Since we are childless, we know that self->rb_left is pointing 354 * to the sentinel node. 355 */ 356 father->rb_nodes[which] = self->rb_left; 357 358 /* 359 * Rebalance if requested. 360 */ 361 if (rebalance) 362 __archive_rb_tree_removal_rebalance(rbt, father, which); 363 } 364 365 /* 366 * When deleting an interior node 367 */ 368 static void 369 __archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree *rbt, 370 struct archive_rb_node *self, struct archive_rb_node *standin) 371 { 372 const unsigned int standin_which = RB_POSITION(standin); 373 unsigned int standin_other = standin_which ^ RB_DIR_OTHER; 374 struct archive_rb_node *standin_son; 375 struct archive_rb_node *standin_father = RB_FATHER(standin); 376 int rebalance = RB_BLACK_P(standin); 377 378 if (standin_father == self) { 379 /* 380 * As a child of self, any children would be opposite of 381 * our parent. 382 */ 383 standin_son = standin->rb_nodes[standin_which]; 384 } else { 385 /* 386 * Since we aren't a child of self, any children would be 387 * on the same side as our parent. 388 */ 389 standin_son = standin->rb_nodes[standin_other]; 390 } 391 392 if (RB_RED_P(standin_son)) { 393 /* 394 * We know we have a red child so if we flip it to black 395 * we don't have to rebalance. 396 */ 397 RB_MARK_BLACK(standin_son); 398 rebalance = F; 399 400 if (standin_father != self) { 401 /* 402 * Change the son's parentage to point to his grandpa. 403 */ 404 RB_SET_FATHER(standin_son, standin_father); 405 RB_SET_POSITION(standin_son, standin_which); 406 } 407 } 408 409 if (standin_father == self) { 410 /* 411 * If we are about to delete the standin's father, then when 412 * we call rebalance, we need to use ourselves as our father. 413 * Otherwise remember our original father. Also, since we are 414 * our standin's father we only need to reparent the standin's 415 * brother. 416 * 417 * | R --> S | 418 * | Q S --> Q T | 419 * | t --> | 420 * 421 * Have our son/standin adopt his brother as his new son. 422 */ 423 standin_father = standin; 424 } else { 425 /* 426 * | R --> S . | 427 * | / \ | T --> / \ | / | 428 * | ..... | S --> ..... | T | 429 * 430 * Sever standin's connection to his father. 431 */ 432 standin_father->rb_nodes[standin_which] = standin_son; 433 /* 434 * Adopt the far son. 435 */ 436 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; 437 RB_SET_FATHER(standin->rb_nodes[standin_other], standin); 438 /* 439 * Use standin_other because we need to preserve standin_which 440 * for the removal_rebalance. 441 */ 442 standin_other = standin_which; 443 } 444 445 /* 446 * Move the only remaining son to our standin. If our standin is our 447 * son, this will be the only son needed to be moved. 448 */ 449 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; 450 RB_SET_FATHER(standin->rb_nodes[standin_other], standin); 451 452 /* 453 * Now copy the result of self to standin and then replace 454 * self with standin in the tree. 455 */ 456 RB_COPY_PROPERTIES(standin, self); 457 RB_SET_FATHER(standin, RB_FATHER(self)); 458 RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin; 459 460 if (rebalance) 461 __archive_rb_tree_removal_rebalance(rbt, standin_father, standin_which); 462 } 463 464 /* 465 * We could do this by doing 466 * __archive_rb_tree_node_swap(rbt, self, which); 467 * __archive_rb_tree_prune_node(rbt, self, F); 468 * 469 * But it's more efficient to just evaluate and recolor the child. 470 */ 471 static void 472 __archive_rb_tree_prune_blackred_branch( 473 struct archive_rb_node *self, unsigned int which) 474 { 475 struct archive_rb_node *father = RB_FATHER(self); 476 struct archive_rb_node *son = self->rb_nodes[which]; 477 478 /* 479 * Remove ourselves from the tree and give our former child our 480 * properties (position, color, root). 481 */ 482 RB_COPY_PROPERTIES(son, self); 483 father->rb_nodes[RB_POSITION(son)] = son; 484 RB_SET_FATHER(son, father); 485 } 486 /* 487 * 488 */ 489 void 490 __archive_rb_tree_remove_node(struct archive_rb_tree *rbt, 491 struct archive_rb_node *self) 492 { 493 struct archive_rb_node *standin; 494 unsigned int which; 495 496 /* 497 * In the following diagrams, we (the node to be removed) are S. Red 498 * nodes are lowercase. T could be either red or black. 499 * 500 * Remember the major axiom of the red-black tree: the number of 501 * black nodes from the root to each leaf is constant across all 502 * leaves, only the number of red nodes varies. 503 * 504 * Thus removing a red leaf doesn't require any other changes to a 505 * red-black tree. So if we must remove a node, attempt to rearrange 506 * the tree so we can remove a red node. 507 * 508 * The simplest case is a childless red node or a childless root node: 509 * 510 * | T --> T | or | R --> * | 511 * | s --> * | 512 */ 513 if (RB_CHILDLESS_P(self)) { 514 const int rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self); 515 __archive_rb_tree_prune_node(rbt, self, rebalance); 516 return; 517 } 518 if (!RB_TWOCHILDREN_P(self)) { 519 /* 520 * The next simplest case is the node we are deleting is 521 * black and has one red child. 522 * 523 * | T --> T --> T | 524 * | S --> R --> R | 525 * | r --> s --> * | 526 */ 527 which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT; 528 __archive_rb_tree_prune_blackred_branch(self, which); 529 return; 530 } 531 532 /* 533 * We invert these because we prefer to remove from the inside of 534 * the tree. 535 */ 536 which = RB_POSITION(self) ^ RB_DIR_OTHER; 537 538 /* 539 * Let's find the node closes to us opposite of our parent 540 * Now swap it with ourself, "prune" it, and rebalance, if needed. 541 */ 542 standin = __archive_rb_tree_iterate(rbt, self, which); 543 __archive_rb_tree_swap_prune_and_rebalance(rbt, self, standin); 544 } 545 546 static void 547 __archive_rb_tree_removal_rebalance(struct archive_rb_tree *rbt, 548 struct archive_rb_node *parent, unsigned int which) 549 { 550 551 while (RB_BLACK_P(parent->rb_nodes[which])) { 552 unsigned int other = which ^ RB_DIR_OTHER; 553 struct archive_rb_node *brother = parent->rb_nodes[other]; 554 555 /* 556 * For cases 1, 2a, and 2b, our brother's children must 557 * be black and our father must be black 558 */ 559 if (RB_BLACK_P(parent) 560 && RB_BLACK_P(brother->rb_left) 561 && RB_BLACK_P(brother->rb_right)) { 562 if (RB_RED_P(brother)) { 563 /* 564 * Case 1: Our brother is red, swap its 565 * position (and colors) with our parent. 566 * This should now be case 2b (unless C or E 567 * has a red child which is case 3; thus no 568 * explicit branch to case 2b). 569 * 570 * B -> D 571 * A d -> b E 572 * C E -> A C 573 */ 574 __archive_rb_tree_reparent_nodes(parent, other); 575 brother = parent->rb_nodes[other]; 576 } else { 577 /* 578 * Both our parent and brother are black. 579 * Change our brother to red, advance up rank 580 * and go through the loop again. 581 * 582 * B -> *B 583 * *A D -> A d 584 * C E -> C E 585 */ 586 RB_MARK_RED(brother); 587 if (RB_ROOT_P(rbt, parent)) 588 return; /* root == parent == black */ 589 which = RB_POSITION(parent); 590 parent = RB_FATHER(parent); 591 continue; 592 } 593 } 594 /* 595 * Avoid an else here so that case 2a above can hit either 596 * case 2b, 3, or 4. 597 */ 598 if (RB_RED_P(parent) 599 && RB_BLACK_P(brother) 600 && RB_BLACK_P(brother->rb_left) 601 && RB_BLACK_P(brother->rb_right)) { 602 /* 603 * We are black, our father is red, our brother and 604 * both nephews are black. Simply invert/exchange the 605 * colors of our father and brother (to black and red 606 * respectively). 607 * 608 * | f --> F | 609 * | * B --> * b | 610 * | N N --> N N | 611 */ 612 RB_MARK_BLACK(parent); 613 RB_MARK_RED(brother); 614 break; /* We're done! */ 615 } else { 616 /* 617 * Our brother must be black and have at least one 618 * red child (it may have two). 619 */ 620 if (RB_BLACK_P(brother->rb_nodes[other])) { 621 /* 622 * Case 3: our brother is black, our near 623 * nephew is red, and our far nephew is black. 624 * Swap our brother with our near nephew. 625 * This result in a tree that matches case 4. 626 * (Our father could be red or black). 627 * 628 * | F --> F | 629 * | x B --> x B | 630 * | n --> n | 631 */ 632 __archive_rb_tree_reparent_nodes(brother, which); 633 brother = parent->rb_nodes[other]; 634 } 635 /* 636 * Case 4: our brother is black and our far nephew 637 * is red. Swap our father and brother locations and 638 * change our far nephew to black. (these can be 639 * done in either order so we change the color first). 640 * The result is a valid red-black tree and is a 641 * terminal case. (again we don't care about the 642 * father's color) 643 * 644 * If the father is red, we will get a red-black-black 645 * tree: 646 * | f -> f --> b | 647 * | B -> B --> F N | 648 * | n -> N --> | 649 * 650 * If the father is black, we will get an all black 651 * tree: 652 * | F -> F --> B | 653 * | B -> B --> F N | 654 * | n -> N --> | 655 * 656 * If we had two red nephews, then after the swap, 657 * our former father would have a red grandson. 658 */ 659 RB_MARK_BLACK(brother->rb_nodes[other]); 660 __archive_rb_tree_reparent_nodes(parent, other); 661 break; /* We're done! */ 662 } 663 } 664 } 665 666 struct archive_rb_node * 667 __archive_rb_tree_iterate(struct archive_rb_tree *rbt, 668 struct archive_rb_node *self, const unsigned int direction) 669 { 670 const unsigned int other = direction ^ RB_DIR_OTHER; 671 672 if (self == NULL) { 673 self = rbt->rbt_root; 674 if (RB_SENTINEL_P(self)) 675 return NULL; 676 while (!RB_SENTINEL_P(self->rb_nodes[direction])) 677 self = self->rb_nodes[direction]; 678 return self; 679 } 680 /* 681 * We can't go any further in this direction. We proceed up in the 682 * opposite direction until our parent is in direction we want to go. 683 */ 684 if (RB_SENTINEL_P(self->rb_nodes[direction])) { 685 while (!RB_ROOT_P(rbt, self)) { 686 if (other == RB_POSITION(self)) 687 return RB_FATHER(self); 688 self = RB_FATHER(self); 689 } 690 return NULL; 691 } 692 693 /* 694 * Advance down one in current direction and go down as far as possible 695 * in the opposite direction. 696 */ 697 self = self->rb_nodes[direction]; 698 while (!RB_SENTINEL_P(self->rb_nodes[other])) 699 self = self->rb_nodes[other]; 700 return self; 701 } 702