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         *((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         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 \f
 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 \f
 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 \f
 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 }