contrib/libarchive/libarchive/archive_rb.c

   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 \f
 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 \f
 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 \f
 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 \f
 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 \f
 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 childen 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 childen 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, sincef 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 evalate 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 simpliest 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 simpliest 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 }