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