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