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