urcu-rbtree.c

   1 /*
   2  * urcu-rbtree.c
   3  *
   4  * Userspace RCU library - Red-Black Tree
   5  *
   6  * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  *
  22  * Implementation of RCU-adapted data structures and operations based on the RB
  23  * tree algorithms found in chapter 12 of:
  24  *
  25  * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
  26  * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
  27  * Press, September 2009.
  28  */
  29
  30 #define _BSD_SOURCE
  31 #define _LGPL_SOURCE
  32
  33 #include <stdio.h>
  34 #include <pthread.h>
  35 #include <assert.h>
  36 #include <string.h>
  37
  38 #include <urcu/rcurbtree.h>
  39 #include <urcu-pointer.h>
  40 #include <urcu-call-rcu.h>
  41
  42 #define DEBUG
  43
  44 #ifdef DEBUG
  45 #define dbg_printf(args...)     printf(args)
  46 #else
  47 #define dbg_printf(args...)
  48 #endif
  49
  50 /*
  51  * Undefine this to enable the non-RCU rotate and transplant functions
  52  * (for debugging).
  53  */
  54 #define RBTREE_RCU_SUPPORT_ROTATE_LEFT
  55 #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
  56 #define RBTREE_RCU_SUPPORT_TRANSPLANT
  57
  58 static
  59 void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
  60 {
  61         x->decay_next = xc;
  62 }
  63
  64 static
  65 struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
  66 {
  67         if (!x)
  68                 return NULL;
  69         while (x->decay_next)
  70                 x = x->decay_next;
  71         return x;
  72 }
  73
  74 static
  75 struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
  76 {
  77         return x->decay_next;
  78 }
  79
  80 static
  81 struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
  82                                 struct rcu_rbtree_node *x)
  83 {
  84         struct rcu_rbtree_node *xc;
  85
  86         if (rcu_rbtree_is_nil(x))
  87                 return x;
  88
  89         xc = rbtree->rballoc();
  90         memcpy(xc, x, sizeof(struct rcu_rbtree_node));
  91         xc->decay_next = NULL;
  92         set_decay(x, xc);
  93         call_rcu(&x->head, rbtree->rbfree);
  94         return xc;
  95 }
  96
  97 /*
  98  * TODO
  99  * Deal with memory allocation errors.
 100  * Can be ensured by reserving a pool of memory entries before doing the
 101  * insertion, which will have to be function of number of
 102  * transplantations/rotations required for the operation.
 103  */
 104
 105 static
 106 void show_tree(struct rcu_rbtree *rbtree)
 107 {
 108         struct rcu_rbtree_node *node;
 109
 110         node = rcu_rbtree_min(rbtree, rbtree->root);
 111         while (!rcu_rbtree_is_nil(node)) {
 112                 assert(!is_decay(node));
 113                 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
 114                         (unsigned long)node->key,
 115                         (unsigned long) node->p->key,
 116                         (unsigned long) node->right->key,
 117                         (unsigned long) node->left->key,
 118                         node->color ? "red" : "black",
 119                         node->pos ? "right" : "left",
 120                         node->nil ? "nil" : "");
 121                 node = rcu_rbtree_next(rbtree, node);
 122         }
 123         printf("\n");
 124 }
 125
 126 static
 127 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
 128 {
 129         return &rbtree->nil_node;
 130 }
 131
 132 /*
 133  * Iterative rbtree search.
 134  */
 135 struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree,
 136                                           struct rcu_rbtree_node *x,
 137                                           void *k)
 138 {
 139         x = rcu_dereference(x);
 140
 141         while (!rcu_rbtree_is_nil(x) && k != x->key) {
 142                 if (rbtree->comp(k, x->key) < 0)
 143                         x = rcu_dereference(x->left);
 144                 else
 145                         x = rcu_dereference(x->right);
 146         }
 147         return x;
 148 }
 149
 150 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
 151                                        struct rcu_rbtree_node *x)
 152 {
 153         struct rcu_rbtree_node *xl;
 154
 155         x = rcu_dereference(x);
 156
 157         if (rcu_rbtree_is_nil(x))
 158                 return x;
 159
 160         while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 161                 x = xl;
 162         return x;
 163 }
 164
 165 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
 166                                        struct rcu_rbtree_node *x)
 167 {
 168         struct rcu_rbtree_node *xr;
 169
 170         x = rcu_dereference(x);
 171
 172         if (rcu_rbtree_is_nil(x))
 173                 return x;
 174
 175         while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 176                 x = xr;
 177         return x;
 178 }
 179
 180 /*
 181  * FIXME:
 182  * Updates should wait for a grace period between update of the
 183  * redirect pointer and update of the parent child pointer. This is to make sure
 184  * that no reference to the old entry exist.
 185  */
 186
 187 /*
 188  * next and prev need to have mutex held to ensure that parent pointer is
 189  * coherent.
 190  */
 191 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
 192                                         struct rcu_rbtree_node *x)
 193 {
 194         struct rcu_rbtree_node *xr, *y;
 195
 196         x = rcu_dereference(x);
 197
 198         if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
 199                 return rcu_rbtree_min(rbtree, xr);
 200         y = rcu_dereference(x->p);
 201         while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) {
 202                 x = y;
 203                 y = rcu_dereference(y->p);
 204         }
 205         return y;
 206 }
 207
 208 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
 209                                         struct rcu_rbtree_node *x)
 210 {
 211         struct rcu_rbtree_node *xl, *y;
 212
 213         x = rcu_dereference(x);
 214
 215         if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
 216                 return rcu_rbtree_min(rbtree, xl);
 217         y = rcu_dereference(x->p);
 218         while (!rcu_rbtree_is_nil(y) && x->pos == IS_LEFT) {
 219                 x = y;
 220                 y = rcu_dereference(y->p);
 221         }
 222         return y;
 223 }
 224
 225 /*
 226  * We have to ensure these assumptions are correct for prev/next
 227  * traversal:
 228  *
 229  * with x being a right child, the assumption that:
 230  *   x->p->right == x
 231  * or if x is a left child, the assumption that:
 232  *   x->p->left == x
 233  *
 234  * This explains why we have to allocate a vc copy of the node for left_rotate,
 235  * right_rotate and transplant operations.
 236  *
 237  * We always ensure that the right/left child and correct parent is set in the
 238  * node copies *before* we reparent the children and make the upper-level point
 239  * to the copy.
 240  */
 241
 242 /* RCU: copy x and y, atomically point to new versions. GC old. */
 243 /* Should be eventually followed by a cmm_smp_wmc() */
 244
 245 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
 246
 247 static
 248 void left_rotate(struct rcu_rbtree *rbtree,
 249                  struct rcu_rbtree_node *x)
 250 {
 251         struct rcu_rbtree_node *y, *y_left, *x_p;
 252         unsigned int x_pos;
 253
 254         y = x->right;
 255         y_left = y->left;
 256
 257         /* Now operate on new copy, decay old versions */
 258         x = dup_decay_node(rbtree, x);
 259         y = dup_decay_node(rbtree, y);
 260         y_left = dup_decay_node(rbtree, y_left);
 261
 262         x_pos = x->pos;
 263         x_p = x->p;
 264
 265         /* Internal node modifications */
 266         x->right = y_left;
 267         y->p = x->p;
 268         y->pos = x->pos;
 269         x->pos = IS_LEFT;
 270         y->left = x;
 271         x->p = y;
 272         if (!rcu_rbtree_is_nil(y_left)) {
 273                 y_left->p = x;
 274                 y_left->pos = IS_RIGHT;
 275         }
 276
 277         cmm_smp_wmb();  /* write into node before publish */
 278
 279         /* External references update (visible by readers) */
 280         if (rcu_rbtree_is_nil(x_p))
 281                 _CMM_STORE_SHARED(rbtree->root, y);
 282         else if (x_pos == IS_LEFT)
 283                 _CMM_STORE_SHARED(x_p->left, y);
 284         else
 285                 _CMM_STORE_SHARED(x_p->right, y);
 286
 287         /* Point children to new copy (parent only used by updates/next/prev) */
 288         x->left->p = get_decay(x->left->p);
 289         y->right->p = get_decay(y->right->p);
 290         if (!rcu_rbtree_is_nil(y_left)) {
 291                 y_left->right->p = get_decay(y_left->right->p);
 292                 y_left->left->p = get_decay(y_left->left->p);
 293         }
 294
 295         /* Sanity checks */
 296         assert(y == rbtree->root || y->p->left == y || y->p->right == y);
 297         assert(x == rbtree->root || x->p->left == x || x->p->right == x);
 298         assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
 299         assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
 300         assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
 301         assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
 302         assert(!is_decay(rbtree->root));
 303         assert(!is_decay(x));
 304         assert(!is_decay(y));
 305         assert(!is_decay(x->right));
 306         assert(!is_decay(x->left));
 307         assert(!is_decay(y->right));
 308         assert(!is_decay(y->left));
 309 }
 310
 311 #else
 312
 313 /* non-rcu version */
 314 static
 315 void left_rotate(struct rcu_rbtree *rbtree,
 316                  struct rcu_rbtree_node *x)
 317 {
 318         struct rcu_rbtree_node *y;
 319
 320         y = x->right;
 321         x->right = y->left;
 322         if (!rcu_rbtree_is_nil(y->left)) {
 323                 y->left->p = x;
 324                 y->left->pos = IS_RIGHT;
 325         }
 326         y->p = x->p;
 327         if (rcu_rbtree_is_nil(x->p))
 328                 rbtree->root = y;
 329         else if (x == x->p->left) {
 330                 x->p->left = y;
 331                 y->pos = IS_LEFT;
 332         } else {
 333                 x->p->right = y;
 334                 y->pos = IS_RIGHT;
 335         }
 336         y->left = x;
 337         x->pos = IS_LEFT;
 338         x->p = y;
 339 }
 340
 341 #endif
 342
 343 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
 344 static
 345 void right_rotate(struct rcu_rbtree *rbtree,
 346                   struct rcu_rbtree_node *x)
 347 {
 348         struct rcu_rbtree_node *y, *y_right, *x_p;
 349         unsigned int x_pos;
 350
 351         y = x->left;
 352         y_right = y->right;
 353
 354         /* Now operate on new copy, decay old versions */
 355         x = dup_decay_node(rbtree, x);
 356         y = dup_decay_node(rbtree, y);
 357         y_right = dup_decay_node(rbtree, y_right);
 358
 359         x_pos = x->pos;
 360         x_p = x->p;
 361
 362         /* Internal node modifications */
 363         x->left = y_right;
 364         y->p = x->p;
 365         y->pos = x->pos;
 366         x->pos = IS_RIGHT;
 367         y->right = x;
 368         x->p = y;
 369         if (!rcu_rbtree_is_nil(y_right)) {
 370                 y_right->p = x;
 371                 y_right->pos = IS_LEFT;
 372         }
 373
 374         cmm_smp_wmb();  /* write into node before publish */
 375
 376         /* External references update (visible by readers) */
 377         if (rcu_rbtree_is_nil(x_p))
 378                 _CMM_STORE_SHARED(rbtree->root, y);
 379         else if (x_pos == IS_RIGHT)
 380                 _CMM_STORE_SHARED(x_p->right, y);
 381         else
 382                 _CMM_STORE_SHARED(x_p->left, y);
 383
 384         /* Point children to new copy (parent only used by updates/next/prev) */
 385         x->right->p = get_decay(x->right->p);
 386         y->left->p = get_decay(y->left->p);
 387         if (!rcu_rbtree_is_nil(y_right)) {
 388                 y_right->left->p = get_decay(y_right->left->p);
 389                 y_right->right->p = get_decay(y_right->right->p);
 390         }
 391
 392         /* Sanity checks */
 393         assert(y == rbtree->root || y->p->right == y || y->p->left == y);
 394         assert(x == rbtree->root || x->p->right == x || x->p->left == x);
 395         assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
 396         assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
 397         assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
 398         assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
 399         assert(!is_decay(rbtree->root));
 400         assert(!is_decay(x));
 401         assert(!is_decay(y));
 402         assert(!is_decay(x->left));
 403         assert(!is_decay(x->right));
 404         assert(!is_decay(y->left));
 405         assert(!is_decay(y->right));
 406 }
 407
 408 #else
 409
 410 /* non-rcu version */
 411 static
 412 void right_rotate(struct rcu_rbtree *rbtree,
 413                   struct rcu_rbtree_node *x)
 414 {
 415         struct rcu_rbtree_node *y;
 416
 417         y = x->left;
 418         x->left = y->right;
 419         if (!rcu_rbtree_is_nil(y->right)) {
 420                 y->right->p = x;
 421                 y->right->pos = IS_LEFT;
 422         }
 423         y->p = x->p;
 424         if (rcu_rbtree_is_nil(x->p))
 425                 rbtree->root = y;
 426         else if (x == x->p->right) {
 427                 x->p->right = y;
 428                 y->pos = IS_RIGHT;
 429         } else {
 430                 x->p->left = y;
 431                 y->pos = IS_LEFT;
 432         }
 433         y->right = x;
 434         x->pos = IS_RIGHT;
 435         x->p = y;
 436 }
 437
 438 #endif
 439
 440 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
 441                                     struct rcu_rbtree_node *z)
 442 {
 443         struct rcu_rbtree_node *y;
 444
 445         dbg_printf("insert fixup %p\n", z->key);
 446         assert(!is_decay(rbtree->root));
 447
 448         while (z->p->color == COLOR_RED) {
 449                 if (z->p == z->p->p->left) {
 450                         y = z->p->p->right;
 451                         if (y->color == COLOR_RED) {
 452                                 z->p->color = COLOR_BLACK;
 453                                 y->color = COLOR_BLACK;
 454                                 z->p->p->color = COLOR_RED;
 455                                 z = z->p->p;
 456                         } else {
 457                                 if (z == z->p->right) {
 458                                         z = z->p;
 459                                         left_rotate(rbtree, z);
 460                                         z = get_decay(z);
 461                                         assert(!is_decay(rbtree->root));
 462                                 }
 463                                 z->p->color = COLOR_BLACK;
 464                                 z->p->p->color = COLOR_RED;
 465                                 assert(!is_decay(z));
 466                                 assert(!is_decay(z->p));
 467                                 assert(!is_decay(z->p->p));
 468                                 right_rotate(rbtree, z->p->p);
 469                                 assert(!is_decay(z));
 470                                 assert(!is_decay(rbtree->root));
 471                         }
 472                 } else {
 473                         y = z->p->p->left;
 474                         if (y->color == COLOR_RED) {
 475                                 z->p->color = COLOR_BLACK;
 476                                 y->color = COLOR_BLACK;
 477                                 z->p->p->color = COLOR_RED;
 478                                 z = z->p->p;
 479                         } else {
 480                                 if (z == z->p->left) {
 481                                         z = z->p;
 482                                         right_rotate(rbtree, z);
 483                                         z = get_decay(z);
 484                                         assert(!is_decay(rbtree->root));
 485                                 }
 486                                 z->p->color = COLOR_BLACK;
 487                                 z->p->p->color = COLOR_RED;
 488                                 left_rotate(rbtree, z->p->p);
 489                                 assert(!is_decay(z));
 490                                 assert(!is_decay(rbtree->root));
 491                         }
 492                 }
 493         }
 494         rbtree->root->color = COLOR_BLACK;
 495 }
 496
 497 /*
 498  * rcu_rbtree_insert - Insert a node in the RCU rbtree
 499  *
 500  * Returns 0 on success, or < 0 on error.
 501  */
 502 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
 503                       struct rcu_rbtree_node *z)
 504 {
 505         struct rcu_rbtree_node *x, *y;
 506
 507         dbg_printf("insert %p\n", z->key);
 508         assert(!is_decay(rbtree->root));
 509
 510         y = make_nil(rbtree);
 511         if (!rbtree->root)
 512                 rbtree->root = make_nil(rbtree);
 513         x = rbtree->root;
 514         while (!rcu_rbtree_is_nil(x)) {
 515                 y = x;
 516                 if (rbtree->comp(z->key, x->key) < 0)
 517                         x = x->left;
 518                 else
 519                         x = x->right;
 520         }
 521
 522         z->p = y;
 523
 524         z->left = make_nil(rbtree);
 525         z->right = make_nil(rbtree);
 526         z->color = COLOR_RED;
 527         z->nil = 0;
 528         z->decay_next = NULL;
 529
 530         if (rcu_rbtree_is_nil(y))
 531                 z->pos = IS_RIGHT;      /* arbitrary for root node */
 532         else if (rbtree->comp(z->key, y->key) < 0)
 533                 z->pos = IS_LEFT;
 534         else
 535                 z->pos = IS_RIGHT;
 536
 537         /*
 538          * Order stores to z (children/parents) before stores that will make it
 539          * visible to the rest of the tree.
 540          */
 541         cmm_smp_wmb();
 542
 543         if (rcu_rbtree_is_nil(y))
 544                 _CMM_STORE_SHARED(rbtree->root, z);
 545         else if (rbtree->comp(z->key, y->key) < 0)
 546                 _CMM_STORE_SHARED(y->left, z);
 547         else
 548                 _CMM_STORE_SHARED(y->right, z);
 549         rcu_rbtree_insert_fixup(rbtree, z);
 550         /*
 551          * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
 552          */
 553         cmm_smp_wmc();
 554         show_tree(rbtree);
 555
 556         return 0;
 557 }
 558
 559 /*
 560  * Transplant v into u position.
 561  */
 562
 563 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
 564
 565 static
 566 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 567                         struct rcu_rbtree_node *u,
 568                         struct rcu_rbtree_node *v)
 569 {
 570         dbg_printf("transplant %p\n", v->key);
 571
 572         if (!rcu_rbtree_is_nil(v))
 573                 v = dup_decay_node(rbtree, v);
 574
 575         if (rcu_rbtree_is_nil(u->p)) {
 576                 v->p = u->p;
 577                 cmm_smp_wmb();  /* write into node before publish */
 578                 _CMM_STORE_SHARED(rbtree->root, v);
 579         } else if (u == u->p->left) {
 580                 v->pos = IS_LEFT;
 581                 v->p = u->p;
 582                 cmm_smp_wmb();  /* write into node before publish */
 583                 _CMM_STORE_SHARED(u->p->left, v);
 584         } else {
 585                 v->pos = IS_RIGHT;
 586                 v->p = u->p;
 587                 cmm_smp_wmb();  /* write into node before publish */
 588                 _CMM_STORE_SHARED(u->p->right, v);
 589         }
 590         /* Point children to new copy (parent only used by updates/next/prev) */
 591         if (!rcu_rbtree_is_nil(v)) {
 592                 v->right->p = get_decay(v->right->p);
 593                 v->left->p = get_decay(v->left->p);
 594         }
 595         assert(!is_decay(rbtree->root));
 596 }
 597
 598 #else
 599
 600 /* Non-RCU version */
 601 static
 602 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
 603                            struct rcu_rbtree_node *u,
 604                            struct rcu_rbtree_node *v)
 605 {
 606         dbg_printf("transplant %p\n", v->key);
 607
 608         if (rcu_rbtree_is_nil(u->p))
 609                 rbtree->root = v;
 610         else if (u == u->p->left) {
 611                 u->p->left = v;
 612                 v->pos = IS_LEFT;
 613         } else {
 614                 u->p->right = v;
 615                 v->pos = IS_RIGHT;
 616         }
 617         v->p = u->p;
 618 }
 619
 620 #endif
 621
 622 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
 623                                     struct rcu_rbtree_node *x)
 624 {
 625         dbg_printf("remove fixup %p\n", x->key);
 626
 627         while (x != rbtree->root && x->color == COLOR_BLACK) {
 628                 assert(!is_decay(x->p));
 629                 assert(!is_decay(x->p->left));
 630                 if (x == x->p->left) {
 631                         struct rcu_rbtree_node *w;
 632
 633                         w = x->p->right;
 634
 635                         if (w->color == COLOR_RED) {
 636                                 w->color = COLOR_BLACK;
 637                                 x->p->color = COLOR_RED;
 638                                 left_rotate(rbtree, x->p);
 639                                 x = get_decay(x);
 640                                 assert(!is_decay(rbtree->root));
 641                                 w = x->p->right;
 642                         }
 643                         if (w->left->color == COLOR_BLACK
 644                             && w->right->color == COLOR_BLACK) {
 645                                 w->color = COLOR_RED;
 646                                 x = x->p;
 647                                 assert(!is_decay(rbtree->root));
 648                                 assert(!is_decay(x));
 649                         } else {
 650                                 if (w->right->color == COLOR_BLACK) {
 651                                         w->left->color = COLOR_BLACK;
 652                                         w->color = COLOR_RED;
 653                                         right_rotate(rbtree, w);
 654                                         assert(!is_decay(rbtree->root));
 655                                         x = get_decay(x);
 656                                         w = x->p->right;
 657                                 }
 658                                 w->color = x->p->color;
 659                                 x->p->color = COLOR_BLACK;
 660                                 w->right->color = COLOR_BLACK;
 661                                 left_rotate(rbtree, x->p);
 662                                 assert(!is_decay(rbtree->root));
 663                                 x = rbtree->root;
 664                         }
 665                 } else {
 666                         struct rcu_rbtree_node *w;
 667
 668                         w = x->p->left;
 669
 670                         if (w->color == COLOR_RED) {
 671                                 w->color = COLOR_BLACK;
 672                                 x->p->color = COLOR_RED;
 673                                 right_rotate(rbtree, x->p);
 674                                 assert(!is_decay(rbtree->root));
 675                                 x = get_decay(x);
 676                                 w = x->p->left;
 677                         }
 678                         if (w->right->color == COLOR_BLACK
 679                             && w->left->color == COLOR_BLACK) {
 680                                 w->color = COLOR_RED;
 681                                 x = x->p;
 682                                 assert(!is_decay(rbtree->root));
 683                                 assert(!is_decay(x));
 684                         } else {
 685                                 if (w->left->color == COLOR_BLACK) {
 686                                         w->right->color = COLOR_BLACK;
 687                                         w->color = COLOR_RED;
 688                                         left_rotate(rbtree, w);
 689                                         assert(!is_decay(rbtree->root));
 690                                         x = get_decay(x);
 691                                         w = x->p->left;
 692                                 }
 693                                 w->color = x->p->color;
 694                                 x->p->color = COLOR_BLACK;
 695                                 w->left->color = COLOR_BLACK;
 696                                 right_rotate(rbtree, x->p);
 697                                 assert(!is_decay(rbtree->root));
 698                                 x = rbtree->root;
 699                         }
 700                 }
 701         }
 702         x->color = COLOR_BLACK;
 703 }
 704
 705 /*
 706  * Delete z. All non-copied children left/right positions are unchanged.
 707  */
 708 static
 709 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
 710                              struct rcu_rbtree_node *z,
 711                              struct rcu_rbtree_node *y)
 712 {
 713         struct rcu_rbtree_node *x;
 714
 715         dbg_printf("remove nonil %p\n", z->key);
 716         show_tree(rbtree);
 717
 718         assert(!is_decay(z));
 719         assert(!is_decay(y));
 720         assert(!is_decay(y->right));
 721         assert(!is_decay(y->p));
 722         x = y->right;
 723         assert(!is_decay(x));
 724         if (y->p == z)
 725                 x->p = y;
 726         else {
 727                 rcu_rbtree_transplant(rbtree, y, y->right);
 728                 assert(!is_decay(y));
 729                 assert(!is_decay(z));
 730                 assert(!is_decay(z->right));
 731                 y->right = z->right;
 732                 y->right->p = y;
 733         }
 734         rcu_rbtree_transplant(rbtree, z, y);
 735         y = get_decay(y);
 736         assert(!is_decay(z));
 737         assert(!is_decay(z->left));
 738         y->left = z->left;
 739         y->left->p = y;
 740         y->color = z->color;
 741 }
 742
 743 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
 744                       struct rcu_rbtree_node *z)
 745 {
 746         struct rcu_rbtree_node *x, *y;
 747         unsigned int y_original_color;
 748
 749         assert(!is_decay(rbtree->root));
 750         dbg_printf("remove %p\n", z->key);
 751         show_tree(rbtree);
 752
 753         assert(!is_decay(z));
 754         y = z;
 755         y_original_color = y->color;
 756
 757         if (rcu_rbtree_is_nil(z->left)) {
 758                 rcu_rbtree_transplant(rbtree, z, z->right);
 759                 assert(!is_decay(z));
 760                 x = get_decay(z->right);
 761                 show_tree(rbtree);
 762         } else if (rcu_rbtree_is_nil(z->right)) {
 763                 rcu_rbtree_transplant(rbtree, z, z->left);
 764                 assert(!is_decay(z));
 765                 x = get_decay(z->left);
 766                 show_tree(rbtree);
 767         } else {
 768                 y = rcu_rbtree_min(rbtree, z->right);
 769                 assert(!is_decay(y));
 770                 y_original_color = y->color;
 771                 x = y->right;
 772                 rcu_rbtree_remove_nonil(rbtree, z, y);
 773                 x = get_decay(x);
 774                 show_tree(rbtree);
 775         }
 776         if (y_original_color == COLOR_BLACK)
 777                 rcu_rbtree_remove_fixup(rbtree, x);
 778         show_tree(rbtree);
 779         /*
 780          * Commit all _CMM_STORE_SHARED().
 781          */
 782         cmm_smp_wmc();
 783
 784         return 0;
 785 }