4 * Userspace RCU library - Red-Black Tree
6 * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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.
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.
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
22 * Implementation of RCU-adapted data structures and operations based on the RB
23 * tree algorithms found in chapter 12 of:
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.
39 #include <urcu/rcurbtree.h>
40 #include <urcu-pointer.h>
41 #include <urcu-call-rcu.h>
46 #define dbg_printf(args...) printf(args)
48 #define dbg_printf(args...)
52 * Undefine this to enable the non-RCU rotate and transplant functions
55 #define RBTREE_RCU_SUPPORT_ROTATE_LEFT
56 #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
57 #define RBTREE_RCU_SUPPORT_TRANSPLANT
60 static pthread_mutex_t test_mutex
= PTHREAD_MUTEX_INITIALIZER
;
61 static pthread_mutex_t outer_mutex
= PTHREAD_MUTEX_INITIALIZER
;
64 void lock_outer_mutex(void)
66 pthread_mutex_lock(&outer_mutex
);
70 void unlock_outer_mutex(void)
72 pthread_mutex_unlock(&outer_mutex
);
76 void lock_test_mutex(void)
78 pthread_mutex_lock(&test_mutex
);
82 void unlock_test_mutex(void)
84 pthread_mutex_unlock(&test_mutex
);
89 void set_parent(struct rcu_rbtree_node
*node
,
90 struct rcu_rbtree_node
*parent
,
93 node
->parent
= ((unsigned long) parent
) | pos
;
97 struct rcu_rbtree_node
*get_parent(struct rcu_rbtree_node
*node
)
99 return (struct rcu_rbtree_node
*) (node
->parent
& ~1UL);
103 unsigned int get_pos(struct rcu_rbtree_node
*node
)
105 return (unsigned int) (node
->parent
& 1UL);
109 struct rcu_rbtree_node
*get_parent_and_pos(struct rcu_rbtree_node
*node
,
112 unsigned long parent_pos
= rcu_dereference(node
->parent
);
114 *pos
= (unsigned int) (parent_pos
& 1UL);
115 return (struct rcu_rbtree_node
*) (parent_pos
& ~1UL);
119 void set_decay(struct rcu_rbtree_node
*x
, struct rcu_rbtree_node
*xc
)
125 struct rcu_rbtree_node
*get_decay(struct rcu_rbtree_node
*x
)
129 while (x
->decay_next
)
135 struct rcu_rbtree_node
*is_decay(struct rcu_rbtree_node
*x
)
137 return x
->decay_next
;
141 struct rcu_rbtree_node
*dup_decay_node(struct rcu_rbtree
*rbtree
,
142 struct rcu_rbtree_node
*x
)
144 struct rcu_rbtree_node
*xc
;
146 if (rcu_rbtree_is_nil(x
))
149 xc
= rbtree
->rballoc();
150 memcpy(xc
, x
, sizeof(struct rcu_rbtree_node
));
151 xc
->decay_next
= NULL
;
153 call_rcu(&x
->head
, rbtree
->rbfree
);
159 * Deal with memory allocation errors.
160 * Can be ensured by reserving a pool of memory entries before doing the
161 * insertion, which will have to be function of number of
162 * transplantations/rotations required for the operation.
166 void show_tree(struct rcu_rbtree
*rbtree
)
168 struct rcu_rbtree_node
*node
;
170 node
= rcu_rbtree_min(rbtree
, rbtree
->root
);
171 while (!rcu_rbtree_is_nil(node
)) {
172 assert(!is_decay(node
));
173 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
174 (unsigned long)node
->key
,
175 (unsigned long) get_parent(node
)->key
,
176 (unsigned long) node
->right
->key
,
177 (unsigned long) node
->left
->key
,
178 node
->color
? "red" : "black",
179 get_pos(node
) ? "right" : "left",
180 node
->nil
? "nil" : "");
181 node
= rcu_rbtree_next(rbtree
, node
);
187 struct rcu_rbtree_node
*make_nil(struct rcu_rbtree
*rbtree
)
189 return &rbtree
->nil_node
;
193 * Iterative rbtree search.
195 struct rcu_rbtree_node
* rcu_rbtree_search(struct rcu_rbtree
*rbtree
,
196 struct rcu_rbtree_node
*x
,
199 x
= rcu_dereference(x
);
201 while (!rcu_rbtree_is_nil(x
) && k
!= x
->key
) {
203 if (rbtree
->comp(k
, x
->key
) < 0)
204 x
= rcu_dereference(x
->left
);
206 x
= rcu_dereference(x
->right
);
212 struct rcu_rbtree_node
*rcu_rbtree_min_dup_decay(struct rcu_rbtree
*rbtree
,
213 struct rcu_rbtree_node
*x
,
214 struct rcu_rbtree_node
**zr
)
216 struct rcu_rbtree_node
*xl
;
218 x
= rcu_dereference(x
);
220 if (rcu_rbtree_is_nil(x
)) {
224 *zr
= x
= dup_decay_node(rbtree
, x
);
226 while (!rcu_rbtree_is_nil(xl
= rcu_dereference(x
->left
))) {
227 x
= dup_decay_node(rbtree
, xl
);
228 set_parent(x
, get_decay(get_parent(x
)), get_pos(x
));
229 get_parent(x
)->left
= get_decay(get_parent(x
)->left
);
235 struct rcu_rbtree_node
*rcu_rbtree_min_update_decay(struct rcu_rbtree
*rbtree
,
236 struct rcu_rbtree_node
*x
)
238 struct rcu_rbtree_node
*xl
;
240 x
= rcu_dereference(x
);
242 if (rcu_rbtree_is_nil(x
))
245 set_parent(x
->right
, get_decay(get_parent(x
->right
)),
247 set_parent(x
->left
, get_decay(get_parent(x
->left
)),
251 while (!rcu_rbtree_is_nil(xl
= rcu_dereference(x
->left
))) {
253 set_parent(x
->right
, get_decay(get_parent(x
->right
)),
255 set_parent(x
->left
, get_decay(get_parent(x
->left
)),
261 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree
*rbtree
,
262 struct rcu_rbtree_node
*x
)
264 struct rcu_rbtree_node
*xl
;
266 x
= rcu_dereference(x
);
268 if (rcu_rbtree_is_nil(x
))
271 while (!rcu_rbtree_is_nil(xl
= rcu_dereference(x
->left
)))
276 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree
*rbtree
,
277 struct rcu_rbtree_node
*x
)
279 struct rcu_rbtree_node
*xr
;
281 x
= rcu_dereference(x
);
283 if (rcu_rbtree_is_nil(x
))
286 while (!rcu_rbtree_is_nil(xr
= rcu_dereference(x
->right
)))
293 * Updates should wait for a grace period between update of the
294 * redirect pointer and update of the parent child pointer. This is to make sure
295 * that no reference to the old entry exist.
299 * RCU read lock must be held across the next/prev calls to ensure validity of
302 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree
*rbtree
,
303 struct rcu_rbtree_node
*x
)
305 struct rcu_rbtree_node
*xr
, *y
;
308 x
= rcu_dereference(x
);
310 if (!rcu_rbtree_is_nil(xr
= rcu_dereference(x
->right
)))
311 return rcu_rbtree_min(rbtree
, xr
);
312 y
= get_parent_and_pos(x
, &x_pos
);
313 while (!rcu_rbtree_is_nil(y
) && x_pos
== IS_RIGHT
) {
315 y
= get_parent_and_pos(y
, &x_pos
);
320 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree
*rbtree
,
321 struct rcu_rbtree_node
*x
)
323 struct rcu_rbtree_node
*xl
, *y
;
326 x
= rcu_dereference(x
);
328 if (!rcu_rbtree_is_nil(xl
= rcu_dereference(x
->left
)))
329 return rcu_rbtree_max(rbtree
, xl
);
330 y
= get_parent_and_pos(x
, &x_pos
);
331 while (!rcu_rbtree_is_nil(y
) && x_pos
== IS_LEFT
) {
333 y
= get_parent_and_pos(y
, &x_pos
);
339 * We have to ensure these assumptions are correct for prev/next
342 * with x being a right child, the assumption that:
343 * get_parent(x)->right == x
344 * or if x is a left child, the assumption that:
345 * get_parent(x)->left == x
347 * This explains why we have to allocate a vc copy of the node for left_rotate,
348 * right_rotate and transplant operations.
350 * We always ensure that the right/left child and correct parent is set in the
351 * node copies *before* we reparent the children and make the upper-level point
355 /* RCU: copy x and y, atomically point to new versions. GC old. */
356 /* Should be eventually followed by a cmm_smp_wmc() */
358 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
361 void left_rotate(struct rcu_rbtree
*rbtree
,
362 struct rcu_rbtree_node
*x
)
364 struct rcu_rbtree_node
*y
, *y_left
, *x_p
;
370 /* Now operate on new copy, decay old versions */
371 x
= dup_decay_node(rbtree
, x
);
372 y
= dup_decay_node(rbtree
, y
);
373 y_left
= dup_decay_node(rbtree
, y_left
);
378 /* Internal node modifications */
380 set_parent(y
, get_parent(x
), get_pos(x
));
381 set_parent(x
, y
, IS_LEFT
);
383 if (!rcu_rbtree_is_nil(y_left
))
384 set_parent(y_left
, x
, IS_RIGHT
);
386 cmm_smp_wmb(); /* write into node before publish */
388 /* External references update (visible by readers) */
389 if (rcu_rbtree_is_nil(x_p
))
390 _CMM_STORE_SHARED(rbtree
->root
, y
);
391 else if (x_pos
== IS_LEFT
)
392 _CMM_STORE_SHARED(x_p
->left
, y
);
394 _CMM_STORE_SHARED(x_p
->right
, y
);
396 /* Point children to new copy (parent only used by updates/next/prev) */
397 set_parent(x
->left
, get_decay(get_parent(x
->left
)),
399 set_parent(y
->right
, get_decay(get_parent(y
->right
)),
401 if (!rcu_rbtree_is_nil(y_left
)) {
402 set_parent(y_left
->right
, get_decay(get_parent(y_left
->right
)),
403 get_pos(y_left
->right
));
404 set_parent(y_left
->left
, get_decay(get_parent(y_left
->left
)),
405 get_pos(y_left
->left
));
409 assert(y
== rbtree
->root
|| get_parent(y
)->left
== y
|| get_parent(y
)->right
== y
);
410 assert(x
== rbtree
->root
|| get_parent(x
)->left
== x
|| get_parent(x
)->right
== x
);
411 assert(rcu_rbtree_is_nil(x
->right
) || get_parent(x
->right
) == x
);
412 assert(rcu_rbtree_is_nil(x
->left
) || get_parent(x
->left
) == x
);
413 assert(rcu_rbtree_is_nil(y
->right
) || get_parent(y
->right
) == y
);
414 assert(rcu_rbtree_is_nil(y
->left
) || get_parent(y
->left
) == y
);
415 assert(!is_decay(rbtree
->root
));
416 assert(!is_decay(x
));
417 assert(!is_decay(y
));
418 assert(!is_decay(x
->right
));
419 assert(!is_decay(x
->left
));
420 assert(!is_decay(y
->right
));
421 assert(!is_decay(y
->left
));
426 /* non-rcu version */
428 void left_rotate(struct rcu_rbtree
*rbtree
,
429 struct rcu_rbtree_node
*x
)
431 struct rcu_rbtree_node
*y
;
436 if (!rcu_rbtree_is_nil(y
->left
))
437 set_parent(y
->left
, x
, IS_RIGHT
);
438 set_parent(y
, get_parent(x
), get_pos(x
));
439 if (rcu_rbtree_is_nil(get_parent(x
)))
441 else if (x
== get_parent(x
)->left
) {
442 get_parent(x
)->left
= y
;
444 get_parent(x
)->right
= y
;
447 set_parent(x
, y
, IS_LEFT
);
453 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
455 void right_rotate(struct rcu_rbtree
*rbtree
,
456 struct rcu_rbtree_node
*x
)
458 struct rcu_rbtree_node
*y
, *y_right
, *x_p
;
464 /* Now operate on new copy, decay old versions */
465 x
= dup_decay_node(rbtree
, x
);
466 y
= dup_decay_node(rbtree
, y
);
467 y_right
= dup_decay_node(rbtree
, y_right
);
472 /* Internal node modifications */
474 set_parent(y
, get_parent(x
), get_pos(x
));
475 set_parent(x
, y
, IS_RIGHT
);
477 if (!rcu_rbtree_is_nil(y_right
))
478 set_parent(y_right
, x
, IS_LEFT
);
480 cmm_smp_wmb(); /* write into node before publish */
482 /* External references update (visible by readers) */
483 if (rcu_rbtree_is_nil(x_p
))
484 _CMM_STORE_SHARED(rbtree
->root
, y
);
485 else if (x_pos
== IS_RIGHT
)
486 _CMM_STORE_SHARED(x_p
->right
, y
);
488 _CMM_STORE_SHARED(x_p
->left
, y
);
490 /* Point children to new copy (parent only used by updates/next/prev) */
491 set_parent(x
->right
, get_decay(get_parent(x
->right
)),
493 set_parent(y
->left
, get_decay(get_parent(y
->left
)),
495 if (!rcu_rbtree_is_nil(y_right
)) {
496 set_parent(y_right
->left
, get_decay(get_parent(y_right
->left
)),
497 get_pos(y_right
->left
));
498 set_parent(y_right
->right
, get_decay(get_parent(y_right
->right
)),
499 get_pos(y_right
->right
));
503 assert(y
== rbtree
->root
|| get_parent(y
)->right
== y
|| get_parent(y
)->left
== y
);
504 assert(x
== rbtree
->root
|| get_parent(x
)->right
== x
|| get_parent(x
)->left
== x
);
505 assert(rcu_rbtree_is_nil(x
->left
) || get_parent(x
->left
) == x
);
506 assert(rcu_rbtree_is_nil(x
->right
) || get_parent(x
->right
) == x
);
507 assert(rcu_rbtree_is_nil(y
->left
) || get_parent(y
->left
) == y
);
508 assert(rcu_rbtree_is_nil(y
->right
) || get_parent(y
->right
) == y
);
509 assert(!is_decay(rbtree
->root
));
510 assert(!is_decay(x
));
511 assert(!is_decay(y
));
512 assert(!is_decay(x
->left
));
513 assert(!is_decay(x
->right
));
514 assert(!is_decay(y
->left
));
515 assert(!is_decay(y
->right
));
520 /* non-rcu version */
522 void right_rotate(struct rcu_rbtree
*rbtree
,
523 struct rcu_rbtree_node
*x
)
525 struct rcu_rbtree_node
*y
;
530 if (!rcu_rbtree_is_nil(y
->right
))
531 set_parent(y
->right
, x
, IS_LEFT
);
532 set_parent(y
, get_parent(x
), get_pos(x
));
533 if (rcu_rbtree_is_nil(get_parent(x
)))
535 else if (x
== get_parent(x
)->right
) {
536 get_parent(x
)->right
= y
;
538 get_parent(x
)->left
= y
;
541 set_parent(x
, y
, IS_RIGHT
);
547 static void rcu_rbtree_insert_fixup(struct rcu_rbtree
*rbtree
,
548 struct rcu_rbtree_node
*z
)
550 struct rcu_rbtree_node
*y
;
552 dbg_printf("insert fixup %p\n", z
->key
);
553 assert(!is_decay(rbtree
->root
));
555 while (get_parent(z
)->color
== COLOR_RED
) {
556 if (get_parent(z
) == get_parent(get_parent(z
))->left
) {
557 y
= get_parent(get_parent(z
))->right
;
558 if (y
->color
== COLOR_RED
) {
559 get_parent(z
)->color
= COLOR_BLACK
;
560 y
->color
= COLOR_BLACK
;
561 get_parent(get_parent(z
))->color
= COLOR_RED
;
562 z
= get_parent(get_parent(z
));
564 if (z
== get_parent(z
)->right
) {
566 left_rotate(rbtree
, z
);
568 assert(!is_decay(rbtree
->root
));
570 get_parent(z
)->color
= COLOR_BLACK
;
571 get_parent(get_parent(z
))->color
= COLOR_RED
;
572 assert(!is_decay(z
));
573 assert(!is_decay(get_parent(z
)));
574 assert(!is_decay(get_parent(get_parent(z
))));
575 right_rotate(rbtree
, get_parent(get_parent(z
)));
576 assert(!is_decay(z
));
577 assert(!is_decay(rbtree
->root
));
580 y
= get_parent(get_parent(z
))->left
;
581 if (y
->color
== COLOR_RED
) {
582 get_parent(z
)->color
= COLOR_BLACK
;
583 y
->color
= COLOR_BLACK
;
584 get_parent(get_parent(z
))->color
= COLOR_RED
;
585 z
= get_parent(get_parent(z
));
587 if (z
== get_parent(z
)->left
) {
589 right_rotate(rbtree
, z
);
591 assert(!is_decay(rbtree
->root
));
593 get_parent(z
)->color
= COLOR_BLACK
;
594 get_parent(get_parent(z
))->color
= COLOR_RED
;
595 left_rotate(rbtree
, get_parent(get_parent(z
)));
596 assert(!is_decay(z
));
597 assert(!is_decay(rbtree
->root
));
601 rbtree
->root
->color
= COLOR_BLACK
;
605 * rcu_rbtree_insert - Insert a node in the RCU rbtree
607 * Returns 0 on success, or < 0 on error.
609 int rcu_rbtree_insert(struct rcu_rbtree
*rbtree
,
610 struct rcu_rbtree_node
*z
)
612 struct rcu_rbtree_node
*x
, *y
;
614 dbg_printf("insert %p\n", z
->key
);
615 assert(!is_decay(rbtree
->root
));
617 y
= make_nil(rbtree
);
619 rbtree
->root
= make_nil(rbtree
);
621 while (!rcu_rbtree_is_nil(x
)) {
623 if (rbtree
->comp(z
->key
, x
->key
) < 0)
629 z
->left
= make_nil(rbtree
);
630 z
->right
= make_nil(rbtree
);
631 z
->color
= COLOR_RED
;
633 z
->decay_next
= NULL
;
635 if (rcu_rbtree_is_nil(y
))
636 set_parent(z
, y
, IS_RIGHT
); /* pos arbitrary for root node */
637 else if (rbtree
->comp(z
->key
, y
->key
) < 0)
638 set_parent(z
, y
, IS_LEFT
);
640 set_parent(z
, y
, IS_RIGHT
);
643 * Order stores to z (children/parents) before stores that will make it
644 * visible to the rest of the tree.
648 if (rcu_rbtree_is_nil(y
))
649 _CMM_STORE_SHARED(rbtree
->root
, z
);
650 else if (rbtree
->comp(z
->key
, y
->key
) < 0)
651 _CMM_STORE_SHARED(y
->left
, z
);
653 _CMM_STORE_SHARED(y
->right
, z
);
654 rcu_rbtree_insert_fixup(rbtree
, z
);
656 * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
665 * Transplant v into u position.
668 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
671 void rcu_rbtree_transplant(struct rcu_rbtree
*rbtree
,
672 struct rcu_rbtree_node
*u
,
673 struct rcu_rbtree_node
*v
)
675 dbg_printf("transplant %p\n", v
->key
);
677 if (!rcu_rbtree_is_nil(v
))
678 v
= dup_decay_node(rbtree
, v
);
680 if (rcu_rbtree_is_nil(get_parent(u
))) {
681 /* pos is arbitrary for root node */
682 set_parent(v
, get_parent(u
), IS_RIGHT
);
683 cmm_smp_wmb(); /* write into node before publish */
684 _CMM_STORE_SHARED(rbtree
->root
, v
);
686 set_parent(v
, get_parent(u
), get_pos(u
));
687 cmm_smp_wmb(); /* write into node before publish */
688 if (get_pos(u
) == IS_LEFT
)
689 _CMM_STORE_SHARED(get_parent(u
)->left
, v
);
691 _CMM_STORE_SHARED(get_parent(u
)->right
, v
);
694 /* Point children to new copy (parent only used by updates/next/prev) */
695 if (!rcu_rbtree_is_nil(v
)) {
696 set_parent(v
->right
, get_decay(get_parent(v
->right
)),
698 set_parent(v
->left
, get_decay(get_parent(v
->left
)),
701 assert(!is_decay(rbtree
->root
));
706 /* Non-RCU version */
708 void rcu_rbtree_transplant(struct rcu_rbtree
*rbtree
,
709 struct rcu_rbtree_node
*u
,
710 struct rcu_rbtree_node
*v
)
712 dbg_printf("transplant %p\n", v
->key
);
715 if (rcu_rbtree_is_nil(get_parent(u
)))
717 else if (u
== get_parent(u
)->left
)
718 get_parent(u
)->left
= v
;
720 get_parent(u
)->right
= v
;
721 set_parent(v
, get_parent(u
), get_pos(u
));
727 static void rcu_rbtree_remove_fixup(struct rcu_rbtree
*rbtree
,
728 struct rcu_rbtree_node
*x
)
730 dbg_printf("remove fixup %p\n", x
->key
);
732 while (x
!= rbtree
->root
&& x
->color
== COLOR_BLACK
) {
733 assert(!is_decay(get_parent(x
)));
734 assert(!is_decay(get_parent(x
)->left
));
735 if (x
== get_parent(x
)->left
) {
736 struct rcu_rbtree_node
*w
;
738 w
= get_parent(x
)->right
;
740 if (w
->color
== COLOR_RED
) {
741 w
->color
= COLOR_BLACK
;
742 get_parent(x
)->color
= COLOR_RED
;
743 left_rotate(rbtree
, get_parent(x
));
745 assert(!is_decay(rbtree
->root
));
746 w
= get_parent(x
)->right
;
748 if (w
->left
->color
== COLOR_BLACK
749 && w
->right
->color
== COLOR_BLACK
) {
750 w
->color
= COLOR_RED
;
752 assert(!is_decay(rbtree
->root
));
753 assert(!is_decay(x
));
755 if (w
->right
->color
== COLOR_BLACK
) {
756 w
->left
->color
= COLOR_BLACK
;
757 w
->color
= COLOR_RED
;
758 right_rotate(rbtree
, w
);
759 assert(!is_decay(rbtree
->root
));
761 w
= get_parent(x
)->right
;
763 w
->color
= get_parent(x
)->color
;
764 get_parent(x
)->color
= COLOR_BLACK
;
765 w
->right
->color
= COLOR_BLACK
;
766 left_rotate(rbtree
, get_parent(x
));
767 assert(!is_decay(rbtree
->root
));
771 struct rcu_rbtree_node
*w
;
773 w
= get_parent(x
)->left
;
775 if (w
->color
== COLOR_RED
) {
776 w
->color
= COLOR_BLACK
;
777 get_parent(x
)->color
= COLOR_RED
;
778 right_rotate(rbtree
, get_parent(x
));
779 assert(!is_decay(rbtree
->root
));
781 w
= get_parent(x
)->left
;
783 if (w
->right
->color
== COLOR_BLACK
784 && w
->left
->color
== COLOR_BLACK
) {
785 w
->color
= COLOR_RED
;
787 assert(!is_decay(rbtree
->root
));
788 assert(!is_decay(x
));
790 if (w
->left
->color
== COLOR_BLACK
) {
791 w
->right
->color
= COLOR_BLACK
;
792 w
->color
= COLOR_RED
;
793 left_rotate(rbtree
, w
);
794 assert(!is_decay(rbtree
->root
));
796 w
= get_parent(x
)->left
;
798 w
->color
= get_parent(x
)->color
;
799 get_parent(x
)->color
= COLOR_BLACK
;
800 w
->left
->color
= COLOR_BLACK
;
801 right_rotate(rbtree
, get_parent(x
));
802 assert(!is_decay(rbtree
->root
));
807 x
->color
= COLOR_BLACK
;
811 * Delete z. All non-copied children left/right positions are unchanged.
814 void rcu_rbtree_remove_nonil(struct rcu_rbtree
*rbtree
,
815 struct rcu_rbtree_node
*z
,
816 struct rcu_rbtree_node
*y
)
818 struct rcu_rbtree_node
*x
;
820 dbg_printf("remove nonil %p\n", z
->key
);
823 assert(!is_decay(z
));
824 assert(!is_decay(y
));
825 assert(!is_decay(y
->right
));
826 assert(!is_decay(get_parent(y
)));
828 assert(!is_decay(x
));
829 if (get_parent(y
) == z
) {
830 y
= dup_decay_node(rbtree
, y
);
831 set_parent(x
, y
, get_pos(x
)); /* parent for nil */
833 rcu_rbtree_transplant(rbtree
, z
, y
);
835 struct rcu_rbtree_node
*oy_right
, *z_right
;
838 * Need to make sure y is always visible by readers.
840 y
= rcu_rbtree_min_dup_decay(rbtree
, z
->right
, &z_right
);
841 assert(!is_decay(y
));
842 assert(!is_decay(z
));
845 set_parent(y
->right
, y
, IS_RIGHT
);
846 assert(!is_decay(z
->left
));
848 assert(!is_decay(oy_right
));
849 rcu_rbtree_transplant(rbtree
, y
, oy_right
);
850 rcu_rbtree_transplant(rbtree
, z
, y
);
851 /* Update children */
852 (void) rcu_rbtree_min_update_decay(rbtree
, y
->right
);
855 assert(!is_decay(z
));
856 assert(!is_decay(z
->left
));
858 set_parent(y
->left
, y
, IS_LEFT
);
859 set_parent(y
->right
, get_decay(get_parent(y
->right
)), IS_RIGHT
);
860 assert(!is_decay(y
->left
));
861 assert(!is_decay(y
->right
));
864 int rcu_rbtree_remove(struct rcu_rbtree
*rbtree
,
865 struct rcu_rbtree_node
*z
)
867 struct rcu_rbtree_node
*x
, *y
;
868 unsigned int y_original_color
;
870 assert(!is_decay(rbtree
->root
));
871 dbg_printf("remove %p\n", z
->key
);
874 assert(!is_decay(z
));
876 y_original_color
= y
->color
;
878 if (rcu_rbtree_is_nil(z
->left
)) {
879 rcu_rbtree_transplant(rbtree
, z
, z
->right
);
880 assert(!is_decay(z
));
881 x
= get_decay(z
->right
);
883 } else if (rcu_rbtree_is_nil(z
->right
)) {
884 rcu_rbtree_transplant(rbtree
, z
, z
->left
);
885 assert(!is_decay(z
));
886 x
= get_decay(z
->left
);
889 y
= rcu_rbtree_min(rbtree
, z
->right
);
890 assert(!is_decay(y
));
891 y_original_color
= y
->color
;
893 rcu_rbtree_remove_nonil(rbtree
, z
, y
);
897 if (y_original_color
== COLOR_BLACK
)
898 rcu_rbtree_remove_fixup(rbtree
, x
);
901 * Commit all _CMM_STORE_SHARED().