1231200Smm/*- 2231200Smm * Copyright (c) 2001 The NetBSD Foundation, Inc. 3231200Smm * All rights reserved. 4231200Smm * 5231200Smm * This code is derived from software contributed to The NetBSD Foundation 6231200Smm * by Matt Thomas <matt@3am-software.com>. 7231200Smm * 8231200Smm * Redistribution and use in source and binary forms, with or without 9231200Smm * modification, are permitted provided that the following conditions 10231200Smm * are met: 11231200Smm * 1. Redistributions of source code must retain the above copyright 12231200Smm * notice, this list of conditions and the following disclaimer. 13231200Smm * 2. Redistributions in binary form must reproduce the above copyright 14231200Smm * notice, this list of conditions and the following disclaimer in the 15231200Smm * documentation and/or other materials provided with the distribution. 16231200Smm * 17231200Smm * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 18231200Smm * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 19231200Smm * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 20231200Smm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 21231200Smm * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22231200Smm * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23231200Smm * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24231200Smm * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25231200Smm * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26231200Smm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27231200Smm * POSSIBILITY OF SUCH DAMAGE. 28231200Smm * 29231200Smm * Based on: NetBSD: rb.c,v 1.6 2010/04/30 13:58:09 joerg Exp 30231200Smm */ 31231200Smm 32231200Smm#include "archive_platform.h" 33231200Smm 34231200Smm#include <stddef.h> 35231200Smm 36231200Smm#include "archive_rb.h" 37231200Smm 38231200Smm/* Keep in sync with archive_rb.h */ 39231200Smm#define RB_DIR_LEFT 0 40231200Smm#define RB_DIR_RIGHT 1 41231200Smm#define RB_DIR_OTHER 1 42231200Smm#define rb_left rb_nodes[RB_DIR_LEFT] 43231200Smm#define rb_right rb_nodes[RB_DIR_RIGHT] 44231200Smm 45231200Smm#define RB_FLAG_POSITION 0x2 46231200Smm#define RB_FLAG_RED 0x1 47231200Smm#define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED) 48231200Smm#define RB_FATHER(rb) \ 49231200Smm ((struct archive_rb_node *)((rb)->rb_info & ~RB_FLAG_MASK)) 50231200Smm#define RB_SET_FATHER(rb, father) \ 51231200Smm ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK))) 52231200Smm 53231200Smm#define RB_SENTINEL_P(rb) ((rb) == NULL) 54231200Smm#define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left) 55231200Smm#define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right) 56231200Smm#define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb))) 57231200Smm#define RB_CHILDLESS_P(rb) \ 58231200Smm (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb))) 59231200Smm#define RB_TWOCHILDREN_P(rb) \ 60231200Smm (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb)) 61231200Smm 62231200Smm#define RB_POSITION(rb) \ 63231200Smm (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT) 64231200Smm#define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT) 65231200Smm#define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT) 66231200Smm#define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0) 67231200Smm#define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0) 68231200Smm#define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED)) 69231200Smm#define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED)) 70231200Smm#define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED)) 71231200Smm#define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb)) 72231200Smm#define RB_SET_POSITION(rb, position) \ 73231200Smm ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \ 74231200Smm ((rb)->rb_info &= ~RB_FLAG_POSITION))) 75231200Smm#define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK)) 76231200Smm#define RB_COPY_PROPERTIES(dst, src) \ 77231200Smm ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK)) 78231200Smm#define RB_SWAP_PROPERTIES(a, b) do { \ 79231200Smm uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \ 80231200Smm (a)->rb_info ^= xorinfo; \ 81231200Smm (b)->rb_info ^= xorinfo; \ 82231200Smm } while (/*CONSTCOND*/ 0) 83231200Smm 84231200Smmstatic void __archive_rb_tree_insert_rebalance(struct archive_rb_tree *, 85231200Smm struct archive_rb_node *); 86231200Smmstatic void __archive_rb_tree_removal_rebalance(struct archive_rb_tree *, 87231200Smm struct archive_rb_node *, unsigned int); 88231200Smm 89231200Smm#define RB_SENTINEL_NODE NULL 90231200Smm 91231200Smm#define T 1 92231200Smm#define F 0 93231200Smm 94231200Smmvoid 95231200Smm__archive_rb_tree_init(struct archive_rb_tree *rbt, 96231200Smm const struct archive_rb_tree_ops *ops) 97231200Smm{ 98231200Smm rbt->rbt_ops = ops; 99232153Smm *((struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE; 100231200Smm} 101231200Smm 102231200Smmstruct archive_rb_node * 103231200Smm__archive_rb_tree_find_node(struct archive_rb_tree *rbt, const void *key) 104231200Smm{ 105231200Smm archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; 106231200Smm struct archive_rb_node *parent = rbt->rbt_root; 107231200Smm 108231200Smm while (!RB_SENTINEL_P(parent)) { 109231200Smm const signed int diff = (*compare_key)(parent, key); 110231200Smm if (diff == 0) 111231200Smm return parent; 112231200Smm parent = parent->rb_nodes[diff > 0]; 113231200Smm } 114231200Smm 115231200Smm return NULL; 116231200Smm} 117231200Smm 118231200Smmstruct archive_rb_node * 119231200Smm__archive_rb_tree_find_node_geq(struct archive_rb_tree *rbt, const void *key) 120231200Smm{ 121231200Smm archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; 122231200Smm struct archive_rb_node *parent = rbt->rbt_root; 123231200Smm struct archive_rb_node *last = NULL; 124231200Smm 125231200Smm while (!RB_SENTINEL_P(parent)) { 126231200Smm const signed int diff = (*compare_key)(parent, key); 127231200Smm if (diff == 0) 128231200Smm return parent; 129231200Smm if (diff < 0) 130231200Smm last = parent; 131231200Smm parent = parent->rb_nodes[diff > 0]; 132231200Smm } 133231200Smm 134231200Smm return last; 135231200Smm} 136231200Smm 137231200Smmstruct archive_rb_node * 138231200Smm__archive_rb_tree_find_node_leq(struct archive_rb_tree *rbt, const void *key) 139231200Smm{ 140231200Smm archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; 141231200Smm struct archive_rb_node *parent = rbt->rbt_root; 142231200Smm struct archive_rb_node *last = NULL; 143231200Smm 144231200Smm while (!RB_SENTINEL_P(parent)) { 145231200Smm const signed int diff = (*compare_key)(parent, key); 146231200Smm if (diff == 0) 147231200Smm return parent; 148231200Smm if (diff > 0) 149231200Smm last = parent; 150231200Smm parent = parent->rb_nodes[diff > 0]; 151231200Smm } 152231200Smm 153231200Smm return last; 154231200Smm} 155231200Smm 156231200Smmint 157231200Smm__archive_rb_tree_insert_node(struct archive_rb_tree *rbt, 158231200Smm struct archive_rb_node *self) 159231200Smm{ 160231200Smm archive_rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes; 161231200Smm struct archive_rb_node *parent, *tmp; 162231200Smm unsigned int position; 163231200Smm int rebalance; 164231200Smm 165231200Smm tmp = rbt->rbt_root; 166231200Smm /* 167231200Smm * This is a hack. Because rbt->rbt_root is just a 168231200Smm * struct archive_rb_node *, just like rb_node->rb_nodes[RB_DIR_LEFT], 169231200Smm * we can use this fact to avoid a lot of tests for root and know 170231200Smm * that even at root, updating 171231200Smm * RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will 172231200Smm * update rbt->rbt_root. 173231200Smm */ 174231200Smm parent = (struct archive_rb_node *)(void *)&rbt->rbt_root; 175231200Smm position = RB_DIR_LEFT; 176231200Smm 177231200Smm /* 178231200Smm * Find out where to place this new leaf. 179231200Smm */ 180231200Smm while (!RB_SENTINEL_P(tmp)) { 181231200Smm const signed int diff = (*compare_nodes)(tmp, self); 182231200Smm if (diff == 0) { 183231200Smm /* 184231200Smm * Node already exists; don't insert. 185231200Smm */ 186231200Smm return F; 187231200Smm } 188231200Smm parent = tmp; 189231200Smm position = (diff > 0); 190231200Smm tmp = parent->rb_nodes[position]; 191231200Smm } 192231200Smm 193231200Smm /* 194231200Smm * Initialize the node and insert as a leaf into the tree. 195231200Smm */ 196231200Smm RB_SET_FATHER(self, parent); 197231200Smm RB_SET_POSITION(self, position); 198231200Smm if (parent == (struct archive_rb_node *)(void *)&rbt->rbt_root) { 199231200Smm RB_MARK_BLACK(self); /* root is always black */ 200231200Smm rebalance = F; 201231200Smm } else { 202231200Smm /* 203231200Smm * All new nodes are colored red. We only need to rebalance 204231200Smm * if our parent is also red. 205231200Smm */ 206231200Smm RB_MARK_RED(self); 207231200Smm rebalance = RB_RED_P(parent); 208231200Smm } 209231200Smm self->rb_left = parent->rb_nodes[position]; 210231200Smm self->rb_right = parent->rb_nodes[position]; 211231200Smm parent->rb_nodes[position] = self; 212231200Smm 213231200Smm /* 214231200Smm * Rebalance tree after insertion 215231200Smm */ 216231200Smm if (rebalance) 217231200Smm __archive_rb_tree_insert_rebalance(rbt, self); 218231200Smm 219231200Smm return T; 220231200Smm} 221231200Smm 222231200Smm/* 223231200Smm * Swap the location and colors of 'self' and its child @ which. The child 224231200Smm * can not be a sentinel node. This is our rotation function. However, 225231200Smm * since it preserves coloring, it great simplifies both insertion and 226231200Smm * removal since rotation almost always involves the exchanging of colors 227231200Smm * as a separate step. 228231200Smm */ 229231200Smm/*ARGSUSED*/ 230231200Smmstatic void 231231200Smm__archive_rb_tree_reparent_nodes( 232231200Smm struct archive_rb_node *old_father, const unsigned int which) 233231200Smm{ 234231200Smm const unsigned int other = which ^ RB_DIR_OTHER; 235231200Smm struct archive_rb_node * const grandpa = RB_FATHER(old_father); 236231200Smm struct archive_rb_node * const old_child = old_father->rb_nodes[which]; 237231200Smm struct archive_rb_node * const new_father = old_child; 238231200Smm struct archive_rb_node * const new_child = old_father; 239231200Smm 240248616Smm if (new_father == NULL) 241248616Smm return; 242231200Smm /* 243231200Smm * Exchange descendant linkages. 244231200Smm */ 245231200Smm grandpa->rb_nodes[RB_POSITION(old_father)] = new_father; 246231200Smm new_child->rb_nodes[which] = old_child->rb_nodes[other]; 247231200Smm new_father->rb_nodes[other] = new_child; 248231200Smm 249231200Smm /* 250231200Smm * Update ancestor linkages 251231200Smm */ 252231200Smm RB_SET_FATHER(new_father, grandpa); 253231200Smm RB_SET_FATHER(new_child, new_father); 254231200Smm 255231200Smm /* 256231200Smm * Exchange properties between new_father and new_child. The only 257231200Smm * change is that new_child's position is now on the other side. 258231200Smm */ 259231200Smm RB_SWAP_PROPERTIES(new_father, new_child); 260231200Smm RB_SET_POSITION(new_child, other); 261231200Smm 262231200Smm /* 263231200Smm * Make sure to reparent the new child to ourself. 264231200Smm */ 265231200Smm if (!RB_SENTINEL_P(new_child->rb_nodes[which])) { 266231200Smm RB_SET_FATHER(new_child->rb_nodes[which], new_child); 267231200Smm RB_SET_POSITION(new_child->rb_nodes[which], which); 268231200Smm } 269231200Smm 270231200Smm} 271231200Smm 272231200Smmstatic void 273231200Smm__archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt, 274231200Smm struct archive_rb_node *self) 275231200Smm{ 276231200Smm struct archive_rb_node * father = RB_FATHER(self); 277231200Smm struct archive_rb_node * grandpa; 278231200Smm struct archive_rb_node * uncle; 279231200Smm unsigned int which; 280231200Smm unsigned int other; 281231200Smm 282231200Smm for (;;) { 283231200Smm /* 284231200Smm * We are red and our parent is red, therefore we must have a 285231200Smm * grandfather and he must be black. 286231200Smm */ 287231200Smm grandpa = RB_FATHER(father); 288231200Smm which = (father == grandpa->rb_right); 289231200Smm other = which ^ RB_DIR_OTHER; 290231200Smm uncle = grandpa->rb_nodes[other]; 291231200Smm 292231200Smm if (RB_BLACK_P(uncle)) 293231200Smm break; 294231200Smm 295231200Smm /* 296231200Smm * Case 1: our uncle is red 297231200Smm * Simply invert the colors of our parent and 298231200Smm * uncle and make our grandparent red. And 299231200Smm * then solve the problem up at his level. 300231200Smm */ 301231200Smm RB_MARK_BLACK(uncle); 302231200Smm RB_MARK_BLACK(father); 303231200Smm if (RB_ROOT_P(rbt, grandpa)) { 304231200Smm /* 305231200Smm * If our grandpa is root, don't bother 306231200Smm * setting him to red, just return. 307231200Smm */ 308231200Smm return; 309231200Smm } 310231200Smm RB_MARK_RED(grandpa); 311231200Smm self = grandpa; 312231200Smm father = RB_FATHER(self); 313231200Smm if (RB_BLACK_P(father)) { 314231200Smm /* 315313571Smm * If our great-grandpa is black, we're done. 316231200Smm */ 317231200Smm return; 318231200Smm } 319231200Smm } 320231200Smm 321231200Smm /* 322231200Smm * Case 2&3: our uncle is black. 323231200Smm */ 324231200Smm if (self == father->rb_nodes[other]) { 325231200Smm /* 326231200Smm * Case 2: we are on the same side as our uncle 327231200Smm * Swap ourselves with our parent so this case 328231200Smm * becomes case 3. Basically our parent becomes our 329231200Smm * child. 330231200Smm */ 331231200Smm __archive_rb_tree_reparent_nodes(father, other); 332231200Smm } 333231200Smm /* 334231200Smm * Case 3: we are opposite a child of a black uncle. 335231200Smm * Swap our parent and grandparent. Since our grandfather 336231200Smm * is black, our father will become black and our new sibling 337231200Smm * (former grandparent) will become red. 338231200Smm */ 339231200Smm __archive_rb_tree_reparent_nodes(grandpa, which); 340231200Smm 341231200Smm /* 342231200Smm * Final step: Set the root to black. 343231200Smm */ 344231200Smm RB_MARK_BLACK(rbt->rbt_root); 345231200Smm} 346231200Smm 347231200Smmstatic void 348231200Smm__archive_rb_tree_prune_node(struct archive_rb_tree *rbt, 349231200Smm struct archive_rb_node *self, int rebalance) 350231200Smm{ 351231200Smm const unsigned int which = RB_POSITION(self); 352231200Smm struct archive_rb_node *father = RB_FATHER(self); 353231200Smm 354231200Smm /* 355231200Smm * Since we are childless, we know that self->rb_left is pointing 356231200Smm * to the sentinel node. 357231200Smm */ 358231200Smm father->rb_nodes[which] = self->rb_left; 359231200Smm 360231200Smm /* 361231200Smm * Rebalance if requested. 362231200Smm */ 363231200Smm if (rebalance) 364231200Smm __archive_rb_tree_removal_rebalance(rbt, father, which); 365231200Smm} 366231200Smm 367231200Smm/* 368231200Smm * When deleting an interior node 369231200Smm */ 370231200Smmstatic void 371231200Smm__archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree *rbt, 372231200Smm struct archive_rb_node *self, struct archive_rb_node *standin) 373231200Smm{ 374231200Smm const unsigned int standin_which = RB_POSITION(standin); 375231200Smm unsigned int standin_other = standin_which ^ RB_DIR_OTHER; 376231200Smm struct archive_rb_node *standin_son; 377231200Smm struct archive_rb_node *standin_father = RB_FATHER(standin); 378231200Smm int rebalance = RB_BLACK_P(standin); 379231200Smm 380231200Smm if (standin_father == self) { 381231200Smm /* 382231200Smm * As a child of self, any children would be opposite of 383231200Smm * our parent. 384231200Smm */ 385231200Smm standin_son = standin->rb_nodes[standin_which]; 386231200Smm } else { 387231200Smm /* 388231200Smm * Since we aren't a child of self, any children would be 389231200Smm * on the same side as our parent. 390231200Smm */ 391231200Smm standin_son = standin->rb_nodes[standin_other]; 392231200Smm } 393231200Smm 394231200Smm if (RB_RED_P(standin_son)) { 395231200Smm /* 396231200Smm * We know we have a red child so if we flip it to black 397231200Smm * we don't have to rebalance. 398231200Smm */ 399231200Smm RB_MARK_BLACK(standin_son); 400231200Smm rebalance = F; 401231200Smm 402231200Smm if (standin_father != self) { 403231200Smm /* 404231200Smm * Change the son's parentage to point to his grandpa. 405231200Smm */ 406231200Smm RB_SET_FATHER(standin_son, standin_father); 407231200Smm RB_SET_POSITION(standin_son, standin_which); 408231200Smm } 409231200Smm } 410231200Smm 411231200Smm if (standin_father == self) { 412231200Smm /* 413231200Smm * If we are about to delete the standin's father, then when 414231200Smm * we call rebalance, we need to use ourselves as our father. 415231200Smm * Otherwise remember our original father. Also, since we are 416231200Smm * our standin's father we only need to reparent the standin's 417231200Smm * brother. 418231200Smm * 419231200Smm * | R --> S | 420231200Smm * | Q S --> Q T | 421231200Smm * | t --> | 422231200Smm * 423231200Smm * Have our son/standin adopt his brother as his new son. 424231200Smm */ 425231200Smm standin_father = standin; 426231200Smm } else { 427231200Smm /* 428231200Smm * | R --> S . | 429231200Smm * | / \ | T --> / \ | / | 430231200Smm * | ..... | S --> ..... | T | 431231200Smm * 432231200Smm * Sever standin's connection to his father. 433231200Smm */ 434231200Smm standin_father->rb_nodes[standin_which] = standin_son; 435231200Smm /* 436231200Smm * Adopt the far son. 437231200Smm */ 438231200Smm standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; 439231200Smm RB_SET_FATHER(standin->rb_nodes[standin_other], standin); 440231200Smm /* 441231200Smm * Use standin_other because we need to preserve standin_which 442231200Smm * for the removal_rebalance. 443231200Smm */ 444231200Smm standin_other = standin_which; 445231200Smm } 446231200Smm 447231200Smm /* 448231200Smm * Move the only remaining son to our standin. If our standin is our 449231200Smm * son, this will be the only son needed to be moved. 450231200Smm */ 451231200Smm standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; 452231200Smm RB_SET_FATHER(standin->rb_nodes[standin_other], standin); 453231200Smm 454231200Smm /* 455231200Smm * Now copy the result of self to standin and then replace 456231200Smm * self with standin in the tree. 457231200Smm */ 458231200Smm RB_COPY_PROPERTIES(standin, self); 459231200Smm RB_SET_FATHER(standin, RB_FATHER(self)); 460231200Smm RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin; 461231200Smm 462231200Smm if (rebalance) 463231200Smm __archive_rb_tree_removal_rebalance(rbt, standin_father, standin_which); 464231200Smm} 465231200Smm 466231200Smm/* 467231200Smm * We could do this by doing 468231200Smm * __archive_rb_tree_node_swap(rbt, self, which); 469231200Smm * __archive_rb_tree_prune_node(rbt, self, F); 470231200Smm * 471231200Smm * But it's more efficient to just evaluate and recolor the child. 472231200Smm */ 473231200Smmstatic void 474231200Smm__archive_rb_tree_prune_blackred_branch( 475231200Smm struct archive_rb_node *self, unsigned int which) 476231200Smm{ 477231200Smm struct archive_rb_node *father = RB_FATHER(self); 478231200Smm struct archive_rb_node *son = self->rb_nodes[which]; 479231200Smm 480231200Smm /* 481231200Smm * Remove ourselves from the tree and give our former child our 482231200Smm * properties (position, color, root). 483231200Smm */ 484231200Smm RB_COPY_PROPERTIES(son, self); 485231200Smm father->rb_nodes[RB_POSITION(son)] = son; 486231200Smm RB_SET_FATHER(son, father); 487231200Smm} 488231200Smm/* 489231200Smm * 490231200Smm */ 491231200Smmvoid 492231200Smm__archive_rb_tree_remove_node(struct archive_rb_tree *rbt, 493231200Smm struct archive_rb_node *self) 494231200Smm{ 495231200Smm struct archive_rb_node *standin; 496231200Smm unsigned int which; 497231200Smm 498231200Smm /* 499231200Smm * In the following diagrams, we (the node to be removed) are S. Red 500231200Smm * nodes are lowercase. T could be either red or black. 501231200Smm * 502231200Smm * Remember the major axiom of the red-black tree: the number of 503231200Smm * black nodes from the root to each leaf is constant across all 504231200Smm * leaves, only the number of red nodes varies. 505231200Smm * 506231200Smm * Thus removing a red leaf doesn't require any other changes to a 507231200Smm * red-black tree. So if we must remove a node, attempt to rearrange 508231200Smm * the tree so we can remove a red node. 509231200Smm * 510231200Smm * The simplest case is a childless red node or a childless root node: 511231200Smm * 512231200Smm * | T --> T | or | R --> * | 513231200Smm * | s --> * | 514231200Smm */ 515231200Smm if (RB_CHILDLESS_P(self)) { 516231200Smm const int rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self); 517231200Smm __archive_rb_tree_prune_node(rbt, self, rebalance); 518231200Smm return; 519231200Smm } 520231200Smm if (!RB_TWOCHILDREN_P(self)) { 521231200Smm /* 522231200Smm * The next simplest case is the node we are deleting is 523231200Smm * black and has one red child. 524231200Smm * 525231200Smm * | T --> T --> T | 526231200Smm * | S --> R --> R | 527231200Smm * | r --> s --> * | 528231200Smm */ 529231200Smm which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT; 530231200Smm __archive_rb_tree_prune_blackred_branch(self, which); 531231200Smm return; 532231200Smm } 533231200Smm 534231200Smm /* 535231200Smm * We invert these because we prefer to remove from the inside of 536231200Smm * the tree. 537231200Smm */ 538231200Smm which = RB_POSITION(self) ^ RB_DIR_OTHER; 539231200Smm 540231200Smm /* 541231200Smm * Let's find the node closes to us opposite of our parent 542231200Smm * Now swap it with ourself, "prune" it, and rebalance, if needed. 543231200Smm */ 544231200Smm standin = __archive_rb_tree_iterate(rbt, self, which); 545231200Smm __archive_rb_tree_swap_prune_and_rebalance(rbt, self, standin); 546231200Smm} 547231200Smm 548231200Smmstatic void 549231200Smm__archive_rb_tree_removal_rebalance(struct archive_rb_tree *rbt, 550231200Smm struct archive_rb_node *parent, unsigned int which) 551231200Smm{ 552231200Smm 553231200Smm while (RB_BLACK_P(parent->rb_nodes[which])) { 554231200Smm unsigned int other = which ^ RB_DIR_OTHER; 555231200Smm struct archive_rb_node *brother = parent->rb_nodes[other]; 556231200Smm 557248616Smm if (brother == NULL) 558248616Smm return;/* The tree may be broken. */ 559231200Smm /* 560231200Smm * For cases 1, 2a, and 2b, our brother's children must 561231200Smm * be black and our father must be black 562231200Smm */ 563231200Smm if (RB_BLACK_P(parent) 564231200Smm && RB_BLACK_P(brother->rb_left) 565231200Smm && RB_BLACK_P(brother->rb_right)) { 566231200Smm if (RB_RED_P(brother)) { 567231200Smm /* 568231200Smm * Case 1: Our brother is red, swap its 569231200Smm * position (and colors) with our parent. 570231200Smm * This should now be case 2b (unless C or E 571231200Smm * has a red child which is case 3; thus no 572231200Smm * explicit branch to case 2b). 573231200Smm * 574231200Smm * B -> D 575231200Smm * A d -> b E 576231200Smm * C E -> A C 577231200Smm */ 578231200Smm __archive_rb_tree_reparent_nodes(parent, other); 579231200Smm brother = parent->rb_nodes[other]; 580248616Smm if (brother == NULL) 581248616Smm return;/* The tree may be broken. */ 582231200Smm } else { 583231200Smm /* 584231200Smm * Both our parent and brother are black. 585231200Smm * Change our brother to red, advance up rank 586231200Smm * and go through the loop again. 587231200Smm * 588231200Smm * B -> *B 589231200Smm * *A D -> A d 590231200Smm * C E -> C E 591231200Smm */ 592231200Smm RB_MARK_RED(brother); 593231200Smm if (RB_ROOT_P(rbt, parent)) 594231200Smm return; /* root == parent == black */ 595231200Smm which = RB_POSITION(parent); 596231200Smm parent = RB_FATHER(parent); 597231200Smm continue; 598231200Smm } 599231200Smm } 600231200Smm /* 601231200Smm * Avoid an else here so that case 2a above can hit either 602231200Smm * case 2b, 3, or 4. 603231200Smm */ 604231200Smm if (RB_RED_P(parent) 605231200Smm && RB_BLACK_P(brother) 606231200Smm && RB_BLACK_P(brother->rb_left) 607231200Smm && RB_BLACK_P(brother->rb_right)) { 608231200Smm /* 609231200Smm * We are black, our father is red, our brother and 610231200Smm * both nephews are black. Simply invert/exchange the 611231200Smm * colors of our father and brother (to black and red 612231200Smm * respectively). 613231200Smm * 614231200Smm * | f --> F | 615231200Smm * | * B --> * b | 616231200Smm * | N N --> N N | 617231200Smm */ 618231200Smm RB_MARK_BLACK(parent); 619231200Smm RB_MARK_RED(brother); 620231200Smm break; /* We're done! */ 621231200Smm } else { 622231200Smm /* 623231200Smm * Our brother must be black and have at least one 624231200Smm * red child (it may have two). 625231200Smm */ 626231200Smm if (RB_BLACK_P(brother->rb_nodes[other])) { 627231200Smm /* 628231200Smm * Case 3: our brother is black, our near 629231200Smm * nephew is red, and our far nephew is black. 630231200Smm * Swap our brother with our near nephew. 631231200Smm * This result in a tree that matches case 4. 632231200Smm * (Our father could be red or black). 633231200Smm * 634231200Smm * | F --> F | 635231200Smm * | x B --> x B | 636231200Smm * | n --> n | 637231200Smm */ 638231200Smm __archive_rb_tree_reparent_nodes(brother, which); 639231200Smm brother = parent->rb_nodes[other]; 640231200Smm } 641231200Smm /* 642231200Smm * Case 4: our brother is black and our far nephew 643231200Smm * is red. Swap our father and brother locations and 644231200Smm * change our far nephew to black. (these can be 645231200Smm * done in either order so we change the color first). 646231200Smm * The result is a valid red-black tree and is a 647231200Smm * terminal case. (again we don't care about the 648231200Smm * father's color) 649231200Smm * 650231200Smm * If the father is red, we will get a red-black-black 651231200Smm * tree: 652231200Smm * | f -> f --> b | 653231200Smm * | B -> B --> F N | 654231200Smm * | n -> N --> | 655231200Smm * 656231200Smm * If the father is black, we will get an all black 657231200Smm * tree: 658231200Smm * | F -> F --> B | 659231200Smm * | B -> B --> F N | 660231200Smm * | n -> N --> | 661231200Smm * 662231200Smm * If we had two red nephews, then after the swap, 663231200Smm * our former father would have a red grandson. 664231200Smm */ 665248616Smm if (brother->rb_nodes[other] == NULL) 666248616Smm return;/* The tree may be broken. */ 667231200Smm RB_MARK_BLACK(brother->rb_nodes[other]); 668231200Smm __archive_rb_tree_reparent_nodes(parent, other); 669231200Smm break; /* We're done! */ 670231200Smm } 671231200Smm } 672231200Smm} 673231200Smm 674231200Smmstruct archive_rb_node * 675231200Smm__archive_rb_tree_iterate(struct archive_rb_tree *rbt, 676231200Smm struct archive_rb_node *self, const unsigned int direction) 677231200Smm{ 678231200Smm const unsigned int other = direction ^ RB_DIR_OTHER; 679231200Smm 680231200Smm if (self == NULL) { 681231200Smm self = rbt->rbt_root; 682231200Smm if (RB_SENTINEL_P(self)) 683231200Smm return NULL; 684231200Smm while (!RB_SENTINEL_P(self->rb_nodes[direction])) 685231200Smm self = self->rb_nodes[direction]; 686231200Smm return self; 687231200Smm } 688231200Smm /* 689231200Smm * We can't go any further in this direction. We proceed up in the 690231200Smm * opposite direction until our parent is in direction we want to go. 691231200Smm */ 692231200Smm if (RB_SENTINEL_P(self->rb_nodes[direction])) { 693231200Smm while (!RB_ROOT_P(rbt, self)) { 694232153Smm if (other == (unsigned int)RB_POSITION(self)) 695231200Smm return RB_FATHER(self); 696231200Smm self = RB_FATHER(self); 697231200Smm } 698231200Smm return NULL; 699231200Smm } 700231200Smm 701231200Smm /* 702231200Smm * Advance down one in current direction and go down as far as possible 703231200Smm * in the opposite direction. 704231200Smm */ 705231200Smm self = self->rb_nodes[direction]; 706231200Smm while (!RB_SENTINEL_P(self->rb_nodes[other])) 707231200Smm self = self->rb_nodes[other]; 708231200Smm return self; 709231200Smm} 710