| 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 | } |