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