1 /******************************************************************************* 2 * Copyright (C) 2018 Cadence Design Systems, Inc. 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to use this Software with Cadence processor cores only and 7 * not with any other processors and platforms, subject to 8 * the following conditions: 9 * 10 * The above copyright notice and this permission notice shall be included 11 * in all copies or substantial portions of the Software. 12 * 13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 14 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 15 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 16 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 17 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 18 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 19 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 20 21 ******************************************************************************/ 22 23 /******************************************************************************* 24 * rbtree.c 25 * 26 * Red-black tree library 27 ******************************************************************************/ 28 29 #include "xf.h" 30 31 /******************************************************************************* 32 * Macros definitions 33 ******************************************************************************/ 34 35 /* ...node color */ 36 #define RB_RED (1) 37 #define RB_BLK (0) 38 39 /* ...pointer to parent node */ 40 #define RB_PARENT(tree, node) ((node)->parent) 41 42 /* ...pointer to left child node */ 43 #define RB_LEFT(tree, node) ((node)->left) 44 45 /* ...pointer to right child node */ 46 #define RB_RIGHT(tree, node) ((node)->right) 47 48 /* ...pointer to right child node */ 49 #define RB_COLOR(tree, node) ((node)->color & 1) 50 51 /* ...check if node is black */ 52 #define RB_IS_BLACK(tree, node) (!((node)->color & RB_RED)) 53 54 /* ...root node index of the tree - can be simplified? */ 55 #define RB_ROOT(tree) RB_LEFT((tree), &(tree)->root) 56 57 /* ...empty node */ 58 #define RB_NULL(tree) (&(tree)->root) 59 60 /******************************************************************************* 61 * Helpers 62 ******************************************************************************/ 63 64 #define RB_SET_P(t, n, p) \ 65 ({ (n)->parent = (p); }) 66 67 #define RB_SET_L(t, n, l) \ 68 ({ (n)->left = (l); }) 69 70 #define RB_SET_R(t, n, r) \ 71 ({ (n)->right = (r); }) 72 73 #define RB_SET_C(t, n, c) \ 74 RB_SET_C_##c((t), (n)) 75 76 #define RB_SET_C_RB_BLK(t, n) \ 77 ({ (n)->color &= ~1; }) 78 79 #define RB_SET_C_RB_RED(t, n) \ 80 ({ (n)->color |= 1; }) 81 82 #define RB_SET_P_C(t, n, p, c) \ 83 ({ (n)->parent = (p); RB_SET_C_##c(t, n); }) 84 85 #define RB_SET_P_L(t, n, p, l) \ 86 ({ (n)->parent = (p); (n)->left = (l); }) 87 88 #define RB_SET_P_L_C(t, n, p, l, c) \ 89 ({ (n)->parent = (p); (n)->left = (l); RB_SET_C_##c(t, n); }) 90 91 #define RB_SET_P_R(t, n, p, r) \ 92 ({ (n)->parent = (p); (n)->right = (r); }) 93 94 #define RB_SET_P_R_C(t, n, p, r, c) \ 95 ({ (n)->parent = (p); (n)->right = (r); RB_SET_C_##c(t, n); }) 96 97 #define RB_SET_P_L_R(t, n, p, l, r) \ 98 ({ (n)->parent = (p); (n)->left = (l); (n)->right = (r); }) 99 100 #define RB_SET_P_L_R_C(t, n, p, l, r, c)\ 101 ({ (n)->parent = (p); (n)->left = (l); (n)->right = (r); RB_SET_C_##c(t, n); }) 102 103 #define RB_SET_ROOT(t, n) \ 104 RB_SET_L((t), &(t)->root, (n)) 105 106 /******************************************************************************* 107 * RB-tree functions 108 ******************************************************************************/ 109 110 /******************************************************************************* 111 * rb_first, rb_last 112 * 113 * Return pointer to first/last item in the tree 114 ******************************************************************************/ 115 116 rb_idx_t rb_first(rb_tree_t *tree) 117 { 118 rb_idx_t p_idx, t_idx; 119 120 if ((p_idx = RB_ROOT(tree)) != RB_NULL(tree)) 121 { 122 /* ...find left-most item in non-empty tree */ 123 while ((t_idx = RB_LEFT(tree, p_idx)) != RB_NULL(tree)) 124 p_idx = t_idx; 125 } 126 127 return p_idx; 128 } 129 130 rb_idx_t rb_last(rb_tree_t *tree) 131 { 132 rb_idx_t p_idx, t_idx; 133 134 if ((p_idx = RB_ROOT(tree)) != RB_NULL(tree)) 135 { 136 /* ...find right-most item in non-empty tree */ 137 while ((t_idx = RB_RIGHT(tree, p_idx)) != RB_NULL(tree)) 138 p_idx = t_idx; 139 } 140 141 return p_idx; 142 } 143 144 /******************************************************************************* 145 * rb_next, rb_prev 146 * 147 * Return next / previous in-order item in the tree 148 ******************************************************************************/ 149 150 rb_idx_t rb_next(rb_tree_t *tree, rb_idx_t n_idx) 151 { 152 rb_idx_t p_idx, c_idx, t_idx; 153 154 /* ...if we have any right children, process them */ 155 if ((c_idx = RB_RIGHT(tree, n_idx)) != RB_NULL(tree)) 156 { 157 /* ...descent to the left-most node starting from right child */ 158 while ((t_idx = RB_LEFT(tree, c_idx)) != RB_NULL(tree)) 159 c_idx = t_idx; 160 return c_idx; 161 } 162 163 /* ...no right children; ascend to our parent while we are right child */ 164 while ((p_idx = RB_PARENT(tree, n_idx)) != RB_NULL(tree)) 165 { 166 /* ...as soon as "n" is a left child, return "p" */ 167 if (n_idx == RB_RIGHT(tree, p_idx)) 168 n_idx = p_idx; 169 else 170 return p_idx; 171 } 172 173 /* ...we were right-most child */ 174 return p_idx; 175 } 176 177 rb_idx_t rb_prev(rb_tree_t *tree, rb_idx_t n_idx) 178 { 179 rb_idx_t p_idx, c_idx, t_idx; 180 181 /* ...if we have any left children, process them */ 182 if ((c_idx = RB_LEFT(tree, n_idx)) != RB_NULL(tree)) 183 { 184 /* ...descent to the right-most node starting from left child */ 185 while ((t_idx = RB_RIGHT(tree, c_idx)) != RB_NULL(tree)) 186 c_idx = t_idx; 187 return c_idx; 188 } 189 190 /* ...no left children; ascend to our parent while we are left child */ 191 while ((p_idx = RB_PARENT(tree, n_idx)) != RB_NULL(tree)) 192 { 193 /* ...as soon as "n" is a right child, return "p" */ 194 if (n_idx == RB_LEFT(tree, p_idx)) 195 n_idx = p_idx; 196 else 197 return p_idx; 198 } 199 200 /* ...we were left-most child */ 201 return p_idx; 202 } 203 204 /******************************************************************************* 205 * rb_init 206 * 207 * Initialize rb-tree structure 208 ******************************************************************************/ 209 210 void rb_init(rb_tree_t *tree) 211 { 212 /* ...initialize sentinel node of the empty tree */ 213 RB_SET_P_L_R_C(tree, &tree->root, RB_NULL(tree), RB_NULL(tree), RB_NULL(tree), RB_BLK); 214 } 215 216 /******************************************************************************* 217 * rb_insert 218 * 219 * Insert new item into RB-tree. Returns non-zero node index on success 220 ******************************************************************************/ 221 222 /* ...internal tree balancing function */ 223 static void __rb_insert_balance(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx) 224 { 225 rb_idx_t u_idx, g_idx, t_idx, cl_idx, cr_idx; 226 227 rebalance: 228 229 /*************************************************************************** 230 * Trivial case #1 - N (red) is a root 231 **************************************************************************/ 232 233 if (p_idx == RB_NULL(tree)) 234 { 235 RB_SET_C(tree, n_idx, RB_BLK); 236 goto root; 237 } 238 239 /*************************************************************************** 240 * Trivial case #2 - P is black 241 **************************************************************************/ 242 243 if (RB_IS_BLACK(tree, p_idx)) 244 goto done; 245 246 /*************************************************************************** 247 * Complex cases - P is red, N is red 248 **************************************************************************/ 249 250 /* ...grandparent must exist and be black */ 251 g_idx = RB_PARENT(tree, p_idx); 252 if (p_idx == RB_LEFT(tree, g_idx)) 253 { 254 /* ...we are left grandchild; get uncle (if it exists) */ 255 u_idx = RB_RIGHT(tree, g_idx); 256 257 /* ...if U is read, we have conditions of case #3 */ 258 if (!RB_IS_BLACK(tree, u_idx)) 259 goto case3; 260 261 /* ...we will need grand-grand-parent later */ 262 t_idx = RB_PARENT(tree, g_idx); 263 264 /* ...U is black/null; if we are LL grandchild, we have case #5 */ 265 if (n_idx == RB_LEFT(tree, p_idx)) 266 goto case5_ll; 267 268 /* ...N is RL grandchild of G; case #4 */ 269 goto case4_rl; 270 } 271 else 272 { 273 /* ...we are right grandchild; get uncle (if it exists) */ 274 u_idx = RB_LEFT(tree, g_idx); 275 276 /* ...if U is read, we have conditions of case #3 */ 277 if (!RB_IS_BLACK(tree, u_idx)) 278 goto case3; 279 280 /* ...we will need grand-grand-parent later */ 281 t_idx = RB_PARENT(tree, g_idx); 282 283 /* ...U is black/null; if we are RR grandchild, we have case #5 */ 284 if (n_idx == RB_RIGHT(tree, p_idx)) 285 goto case5_rr; 286 287 /* ...N is LR grandchild of G; case #4 */ 288 goto case4_lr; 289 } 290 291 case4_rl: 292 293 /*************************************************************************** 294 * Case #4 - P is red, U is black, N is red RL grandchild of G. We will do 295 * two tree rotations - first the one described in case #4, second is the 296 * one described in case #5 (as have conditions for case #5(LL) with P and 297 * N changing roles 298 **************************************************************************/ 299 300 cl_idx = RB_LEFT(tree, n_idx), cr_idx = RB_RIGHT(tree, n_idx); 301 RB_SET_P_L_R_C(tree, n_idx, t_idx, p_idx, g_idx, RB_BLK); 302 RB_SET_P_R(tree, p_idx, n_idx, cl_idx); 303 RB_SET_P(tree, cl_idx, p_idx); 304 RB_SET_P_L_C(tree, g_idx, n_idx, cr_idx, RB_RED); 305 RB_SET_P(tree, cr_idx, g_idx); 306 307 /* ...new root of subtree is N; adjust T pointer */ 308 goto case5_xx; 309 310 case4_lr: 311 312 /*************************************************************************** 313 * Case #4 - P is red, U is black, N is red LR grandchild of G. We will do 314 * two tree rotations - first the one described in case #4, second is the 315 * one described in case #5 (as have conditions for case #5(RR) with P and 316 * N changing roles 317 **************************************************************************/ 318 319 cl_idx = RB_LEFT(tree, n_idx), cr_idx = RB_RIGHT(tree, n_idx); 320 RB_SET_P_L_R_C(tree, n_idx, t_idx, g_idx, p_idx, RB_BLK); 321 RB_SET_P_L(tree, p_idx, n_idx, cr_idx); 322 RB_SET_P(tree, cr_idx, p_idx); 323 RB_SET_P_R_C(tree, g_idx, n_idx, cl_idx, RB_RED); 324 RB_SET_P(tree, cl_idx, g_idx); 325 326 /* ...new root of the subtree is N; adjust T pointer */ 327 goto case5_xx; 328 329 case5_ll: 330 331 /*************************************************************************** 332 * Case #5: N is LL grandchild of P; N and P red, G and U black 333 **************************************************************************/ 334 335 cr_idx = RB_RIGHT(tree, p_idx); 336 RB_SET_P_L_C(tree, g_idx, p_idx, cr_idx, RB_RED); 337 RB_SET_P(tree, cr_idx, g_idx); 338 RB_SET_P_R_C(tree, p_idx, t_idx, g_idx, RB_BLK); 339 340 /* ...new root of the subtree is P; relabel and adjust T pointer */ 341 n_idx = p_idx; 342 goto case5_xx; 343 344 case5_rr: 345 346 /*************************************************************************** 347 * Case #5: N is RR grandchild of P; N and P red, G and U black 348 **************************************************************************/ 349 350 cl_idx = RB_LEFT(tree, p_idx); 351 RB_SET_P_R_C(tree, g_idx, p_idx, cl_idx, RB_RED); 352 RB_SET_P(tree, cl_idx, g_idx); 353 RB_SET_P_L_C(tree, p_idx, t_idx, g_idx, RB_BLK); 354 355 /* ...new root of the subtree is P; relabel and adjust T pointer */ 356 n_idx = p_idx; 357 goto case5_xx; 358 359 case5_xx: 360 361 /* ...N is a (black) root of subtree; check if it is a root of tree as well */ 362 if (t_idx == RB_NULL(tree)) 363 goto root; 364 else if (g_idx == RB_LEFT(tree, t_idx)) 365 RB_SET_L(tree, t_idx, n_idx); 366 else 367 RB_SET_R(tree, t_idx, n_idx); 368 369 goto done; 370 371 case3: 372 373 /*************************************************************************** 374 * Case #3 - P and U are red, G is black 375 **************************************************************************/ 376 377 RB_SET_C(tree, p_idx, RB_BLK); 378 RB_SET_C(tree, u_idx, RB_BLK); 379 RB_SET_C(tree, g_idx, RB_RED); 380 381 /* ...rebalance the tree for a G */ 382 n_idx = g_idx, p_idx = RB_PARENT(tree, g_idx); 383 goto rebalance; 384 385 root: 386 /* ...adjust root pointer of the tree */ 387 RB_SET_ROOT(tree, n_idx); 388 389 done: 390 /* ...tree is balanced */ 391 return; 392 } 393 394 /* ...high-level API function */ 395 void rb_insert(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx) 396 { 397 if (p_idx == RB_NULL(tree)) 398 { 399 /* ...set black root node */ 400 RB_SET_P_L_R_C(tree, n_idx, p_idx, p_idx, p_idx, RB_BLK); 401 402 /* ...tree consists of the only root node; is balanced */ 403 RB_SET_ROOT(tree, n_idx); 404 } 405 else 406 { 407 /* ...create new node - set parent pointer and paint red */ 408 RB_SET_P_L_R_C(tree, n_idx, p_idx, RB_NULL(tree), RB_NULL(tree), RB_RED); 409 410 /* ...and rebalance the tree */ 411 __rb_insert_balance(tree, n_idx, p_idx); 412 } 413 } 414 415 /******************************************************************************* 416 * rb_delete 417 * 418 * Remove item from RB-key (by key). Returns zero on success 419 ******************************************************************************/ 420 421 /* ...internal tree balancing function */ 422 static void __rb_delete_rebalance(rb_tree_t *tree, rb_idx_t p_idx) 423 { 424 rb_idx_t n_idx, s_idx, sl_idx, sr_idx, g_idx, c_idx, cl_idx, cr_idx; 425 426 /* ...initialize rebalancing procedure with null-child of P */ 427 n_idx = RB_NULL(tree); 428 429 rebalance: 430 431 /* ...save grand-parent pointer (may be null) */ 432 g_idx = RB_PARENT(tree, p_idx); 433 434 /*************************************************************************** 435 * Check for complex cases 436 **************************************************************************/ 437 438 if (n_idx == RB_LEFT(tree, p_idx)) 439 { 440 /* ...N is left child; get sibling (must exist) and its children */ 441 s_idx = RB_RIGHT(tree, p_idx); 442 sl_idx = RB_LEFT(tree, s_idx); 443 sr_idx = RB_RIGHT(tree, s_idx); 444 445 /* ...if S is black, test for conditions 3,4,5,6; otherwise - case 2 */ 446 if (RB_IS_BLACK(tree, s_idx)) 447 goto test3_l; 448 else 449 goto case2_l; 450 } 451 else 452 { 453 /* ...N is right child; get sibling (must exist) and its children */ 454 s_idx = RB_LEFT(tree, p_idx); 455 sl_idx = RB_LEFT(tree, s_idx); 456 sr_idx = RB_RIGHT(tree, s_idx); 457 458 /* ...if S is black, test for conditions 3,4,5,6; otherwise - case 2 */ 459 if (RB_IS_BLACK(tree, s_idx)) 460 goto test3_r; 461 else 462 goto case2_r; 463 } 464 465 case2_l: 466 467 /*************************************************************************** 468 * Case #2: N is a left child of P; S is red 469 **************************************************************************/ 470 471 c_idx = sl_idx; 472 RB_SET_P_L_C(tree, s_idx, g_idx, p_idx, RB_BLK); 473 RB_SET_P_R_C(tree, p_idx, s_idx, c_idx, RB_RED); 474 RB_SET_P(tree, c_idx, p_idx); 475 476 /* ...S is new root of subtree, Sl(C) is new sibling of N; update G */ 477 goto case2_x; 478 479 case2_r: 480 481 /*************************************************************************** 482 * Case #2: N is a right child of P; S is red 483 **************************************************************************/ 484 485 c_idx = sr_idx; 486 RB_SET_P_R_C(tree, s_idx, g_idx, p_idx, RB_BLK); 487 RB_SET_P_L_C(tree, p_idx, s_idx, c_idx, RB_RED); 488 RB_SET_P(tree, c_idx, p_idx); 489 490 /* ...S is new root of subtree, Sr(C) is new sibling of N; update G */ 491 goto case2_x; 492 493 case2_x: 494 495 /* ...check if S is becoming new (black) root of the tree */ 496 if (g_idx == RB_NULL(tree)) 497 RB_SET_ROOT(tree, s_idx); 498 else if (p_idx == RB_LEFT(tree, g_idx)) 499 RB_SET_L(tree, g_idx, s_idx); 500 else 501 RB_SET_R(tree, g_idx, s_idx); 502 503 /* ...relabel new N's grandparent (now S) as G and new sibling (now C) as S */ 504 g_idx = s_idx, s_idx = c_idx; 505 sl_idx = RB_LEFT(tree, s_idx); 506 sr_idx = RB_RIGHT(tree, s_idx); 507 508 /* ...N is still one of P's children; select proper side */ 509 if (n_idx == RB_LEFT(tree, p_idx)) 510 goto test3_l; 511 else 512 goto test3_r; 513 514 test3_l: 515 516 /*************************************************************************** 517 * Test for cases 3,4,5,6; P is any, S is black. N is left child of P 518 **************************************************************************/ 519 520 if (!RB_IS_BLACK(tree, sr_idx)) 521 /* ...Sr is red, Sl of any color; conditions for case #6 are met */ 522 goto case6_l; 523 else if (!RB_IS_BLACK(tree, sl_idx)) 524 /* ...Sr is black and Sl is red; conditions for case #5 are met */ 525 goto case5_l; 526 else if (RB_IS_BLACK(tree, p_idx)) 527 /* ...Sl and Sr are of the same (black) color and P is black */ 528 goto case3; 529 else 530 /* ...Sl and Sr are of the same (black) color and P is red */ 531 goto case4; 532 533 test3_r: 534 535 /*************************************************************************** 536 * Test for cases 3,4,5,6; P is any, S is black. N is right child of P 537 **************************************************************************/ 538 539 if (!RB_IS_BLACK(tree, sl_idx)) 540 /* ...Sl is red, Sr of any color; conditions for case #6 are met */ 541 goto case6_r; 542 else if (!RB_IS_BLACK(tree, sr_idx)) 543 /* ...Sl is black and Sr is red; conditions for case #5 are met */ 544 goto case5_r; 545 else if (RB_IS_BLACK(tree, p_idx)) 546 /* ...Sl and Sr are of the same (black) color and P is black */ 547 goto case3; 548 else 549 /* ...Sl and Sr are of the same (black) color and P is red */ 550 goto case4; 551 552 case3: 553 554 /*************************************************************************** 555 * Case #3: N, P, S, Sl and Sr are black 556 **************************************************************************/ 557 558 RB_SET_C(tree, s_idx, RB_RED); 559 560 /* ...and rebalance the tree for parent */ 561 n_idx = p_idx, p_idx = RB_PARENT(tree, p_idx); 562 563 if (p_idx == RB_NULL(tree)) 564 goto done; 565 else 566 goto rebalance; 567 568 case4: 569 570 /*************************************************************************** 571 * Case #4: N and S are black, P is red, Sl and Sr are all black 572 **************************************************************************/ 573 574 RB_SET_C(tree, s_idx, RB_RED); 575 RB_SET_C(tree, p_idx, RB_BLK); 576 577 goto done; 578 579 case5_l: 580 /*************************************************************************** 581 * Case #5: S is black, Sl is red, Sr is black; N is left child of P. We 582 * have two subsequent transformations (case #5 and case #6) combined 583 **************************************************************************/ 584 585 cl_idx = RB_LEFT(tree, sl_idx); 586 cr_idx = RB_RIGHT(tree, sl_idx); 587 588 if (RB_IS_BLACK(tree, p_idx)) 589 RB_SET_P_L_R_C(tree, sl_idx, g_idx, p_idx, s_idx, RB_BLK); 590 else 591 RB_SET_P_L_R_C(tree, sl_idx, g_idx, p_idx, s_idx, RB_RED); 592 593 RB_SET_P_R_C(tree, p_idx, sl_idx, cl_idx, RB_BLK); 594 RB_SET_P(tree, cl_idx, p_idx); 595 RB_SET_P_L(tree, s_idx, sl_idx, cr_idx); 596 RB_SET_P(tree, cr_idx, s_idx); 597 598 /* ...relabel new root as S (for common processing in case #6) */ 599 s_idx = sl_idx; 600 goto case6_x; 601 602 case5_r: 603 /*************************************************************************** 604 * Case #5: S is black, Sr is red, Sl is black; N is right child of P. We 605 * have two subsequent transformations (case #5 and case #6) combined 606 **************************************************************************/ 607 608 cl_idx = RB_LEFT(tree, sr_idx); 609 cr_idx = RB_RIGHT(tree, sr_idx); 610 611 if (RB_IS_BLACK(tree, p_idx)) 612 RB_SET_P_L_R_C(tree, sr_idx, g_idx, s_idx, p_idx, RB_BLK); 613 else 614 RB_SET_P_L_R_C(tree, sr_idx, g_idx, s_idx, p_idx, RB_RED); 615 616 RB_SET_P_L_C(tree, p_idx, sr_idx, cr_idx, RB_BLK); 617 RB_SET_P(tree, cr_idx, p_idx); 618 RB_SET_P_R(tree, s_idx, sr_idx, cl_idx); 619 RB_SET_P(tree, cl_idx, s_idx); 620 621 /* ...relabel new root as S (for common processing in case #6) */ 622 s_idx = sr_idx; 623 goto case6_x; 624 625 case6_l: 626 627 /*************************************************************************** 628 * Case #6: S is black, N is the left child of P, Sr is red 629 **************************************************************************/ 630 631 if (RB_IS_BLACK(tree, p_idx)) 632 RB_SET_P_L(tree, s_idx, g_idx, p_idx); 633 else 634 RB_SET_P_L_C(tree, s_idx, g_idx, p_idx, RB_RED); 635 636 RB_SET_P_R_C(tree, p_idx, s_idx, sl_idx, RB_BLK); 637 RB_SET_P(tree, sl_idx, p_idx); 638 RB_SET_C(tree, sr_idx, RB_BLK); 639 640 /* ...S is a new root of subtree; update G */ 641 goto case6_x; 642 643 case6_r: 644 645 /*************************************************************************** 646 * Case #6: S is black, N is the right child of P, Sl is red 647 **************************************************************************/ 648 649 if (RB_IS_BLACK(tree, p_idx)) 650 RB_SET_P_R(tree, s_idx, g_idx, p_idx); 651 else 652 RB_SET_P_R_C(tree, s_idx, g_idx, p_idx, RB_RED); 653 654 RB_SET_P_L_C(tree, p_idx, s_idx, sr_idx, RB_BLK); 655 RB_SET_P(tree, sr_idx, p_idx); 656 RB_SET_C(tree, sl_idx, RB_BLK); 657 658 /* ...S is a new root of subtree; update G */ 659 goto case6_x; 660 661 case6_x: 662 663 /* ...S is a new root of subtree; update G's pointer */ 664 if (g_idx == RB_NULL(tree)) 665 RB_SET_ROOT(tree, s_idx); 666 else if (p_idx == RB_LEFT(tree, g_idx)) 667 RB_SET_L(tree, g_idx, s_idx); 668 else 669 RB_SET_R(tree, g_idx, s_idx); 670 671 /* ...tree is balanced; pass through */ 672 673 done: 674 675 return; 676 } 677 678 /* ...high-level API function */ 679 rb_idx_t rb_delete(rb_tree_t *tree, rb_idx_t n_idx) 680 { 681 rb_idx_t p_idx, t_idx, m_idx, c_idx, l_idx, r_idx, k_idx; 682 u32 color; 683 684 /* ...save parent of element N that we are going to remove */ 685 p_idx = RB_PARENT(tree, n_idx); 686 687 /* ...get in-order predecessor/successor of n_idx, if possible */ 688 if ((m_idx = RB_LEFT(tree, n_idx)) != RB_NULL(tree)) 689 { 690 while ((t_idx = RB_RIGHT(tree, m_idx)) != RB_NULL(tree)) 691 m_idx = t_idx; 692 693 /* ...set the child of in-order predecessor (may be null) */ 694 c_idx = RB_LEFT(tree, m_idx); 695 } 696 else if ((m_idx = RB_RIGHT(tree, n_idx)) != RB_NULL(tree)) 697 { 698 while ((t_idx = RB_LEFT(tree, m_idx)) != RB_NULL(tree)) 699 m_idx = t_idx; 700 701 /* ...set the child of in-order successor (may be null) */ 702 c_idx = RB_RIGHT(tree, m_idx); 703 } 704 else if (p_idx == RB_NULL(tree)) 705 { 706 /* ...tree consists of the only root node N that we are removing */ 707 RB_SET_ROOT(tree, m_idx); 708 709 /* ..return tree null pointer */ 710 return m_idx; 711 } 712 else 713 { 714 /* ...N is a (non-root) leaf node; M and C are null */ 715 c_idx = m_idx; 716 717 /* ...save the color of the node we are going to delete */ 718 color = RB_COLOR(tree, n_idx); 719 720 /* ...set new parent of C */ 721 t_idx = p_idx; 722 723 /* ...pointer that we return as in-order predecessor/successor */ 724 k_idx = p_idx; 725 726 /* ...adjust only parent of the N */ 727 goto adjust_parent; 728 } 729 730 /* ...node that replaces our component is M */ 731 k_idx = m_idx; 732 733 /*************************************************************************** 734 * Replace node N with M 735 **************************************************************************/ 736 737 /* ...save original color of M (the node that we are deleting) */ 738 color = RB_COLOR(tree, m_idx); 739 740 /* ...put M in place of N; get N's children */ 741 l_idx = RB_LEFT(tree, n_idx); 742 r_idx = RB_RIGHT(tree, n_idx); 743 744 /* ...see if M is a child of N */ 745 if ((t_idx = RB_PARENT(tree, m_idx)) != n_idx) 746 { 747 /* ...C becomes left or right child of M's original parent T */ 748 if (c_idx == RB_LEFT(tree, m_idx)) 749 RB_SET_R(tree, t_idx, c_idx); 750 else 751 RB_SET_L(tree, t_idx, c_idx); 752 753 /* ...adjust C parent pointer (okay if it's null) */ 754 RB_SET_P(tree, c_idx, t_idx); 755 756 /* ...set all pointers of node M (it replaces N) */ 757 RB_SET_P_L_R(tree, m_idx, p_idx, l_idx, r_idx); 758 RB_SET_P(tree, l_idx, m_idx); 759 RB_SET_P(tree, r_idx, m_idx); 760 } 761 else 762 { 763 /* ...M is a left or right child of N; it gets to N's place, and C remains intact */ 764 if (m_idx == l_idx) 765 { 766 RB_SET_P_R(tree, m_idx, p_idx, r_idx); 767 RB_SET_P(tree, r_idx, m_idx); 768 } 769 else 770 { 771 RB_SET_P_L(tree, m_idx, p_idx, l_idx); 772 RB_SET_P(tree, l_idx, m_idx); 773 } 774 775 /* ...parent of C is still M (we label it as T) */ 776 t_idx = m_idx; 777 } 778 779 /* ...paint M in the same color as N which it replaced */ 780 if (RB_IS_BLACK(tree, n_idx)) 781 RB_SET_C(tree, m_idx, RB_BLK); 782 else 783 RB_SET_C(tree, m_idx, RB_RED); 784 785 adjust_parent: 786 787 /* ...adjust N's parent node to point to M */ 788 if (p_idx == RB_NULL(tree)) 789 RB_SET_ROOT(tree, m_idx); 790 else if (n_idx == RB_LEFT(tree, p_idx)) 791 RB_SET_L(tree, p_idx, m_idx); 792 else 793 RB_SET_R(tree, p_idx, m_idx); 794 795 /* ...check for a color of deleted item (M or N in case it is a leaf) */ 796 if (color == RB_BLK) 797 { 798 if (c_idx == RB_NULL(tree)) 799 /* ...rebalance the tree for a T node (it is never a null)*/ 800 __rb_delete_rebalance(tree, t_idx); 801 else 802 /* ...C node exists and is necessarily red; repaint it black */ 803 RB_SET_C(tree, c_idx, RB_BLK); 804 } 805 806 /* ....return the node K which replaced deleted node N */ 807 return k_idx; 808 } 809 810 /******************************************************************************* 811 * rb_replace 812 * 813 * Replace the node with the same-key node - adjust tree pointers 814 ******************************************************************************/ 815 816 void rb_replace(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t t_idx) 817 { 818 rb_idx_t p_idx, l_idx, r_idx; 819 820 /* ...get node pointers */ 821 p_idx = RB_PARENT(tree, n_idx), l_idx = RB_LEFT(tree, n_idx), r_idx = RB_RIGHT(tree, n_idx); 822 823 /* ...set new node pointers */ 824 RB_SET_P_L_R(tree, t_idx, p_idx, l_idx, r_idx); 825 826 /* ...set node color */ 827 if (RB_IS_BLACK(tree, n_idx)) 828 RB_SET_C(tree, t_idx, RB_BLK); 829 else 830 RB_SET_C(tree, t_idx, RB_RED); 831 832 /* ...update parent node */ 833 if (p_idx == RB_NULL(tree)) 834 RB_SET_ROOT(tree, t_idx); 835 else if (n_idx == RB_LEFT(tree, p_idx)) 836 RB_SET_L(tree, p_idx, t_idx); 837 else 838 RB_SET_R(tree, p_idx, t_idx); 839 840 /* ...update children's parent node (okay if null) */ 841 RB_SET_P(tree, l_idx, t_idx), RB_SET_P(tree, r_idx, t_idx); 842 } 843
