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.
37 #include <urcu-rbtree.h>
38 #include <urcu-pointer.h>
43 #define dbg_printf(args...) printf(args)
45 #define dbg_printf(args...)
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.
56 /* Sentinel (bottom nodes).
57 * Don't care about p, left, right, pos and key values */
58 struct rcu_rbtree_node rcu_rbtree_nil
= {
63 * Iterative rbtree search.
65 struct rcu_rbtree_node
* rcu_rbtree_search(struct rcu_rbtree_node
*x
,
66 void *k
, rcu_rbtree_comp comp
)
68 x
= rcu_dereference(x
);
70 while (x
!= &rcu_rbtree_nil
&& k
!= x
->key
) {
72 x
= rcu_dereference(x
->left
);
74 x
= rcu_dereference(x
->right
);
79 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree_node
*x
,
82 struct rcu_rbtree_node
*xl
;
84 x
= rcu_dereference(x
);
86 while ((xl
= rcu_dereference(x
->left
)) != &rcu_rbtree_nil
)
91 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree_node
*x
,
94 struct rcu_rbtree_node
*xr
;
96 x
= rcu_dereference(x
);
98 while ((xr
= rcu_dereference(x
->right
)) != &rcu_rbtree_nil
)
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.
111 * next and prev need to have mutex held to ensure that parent pointer is
114 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree_node
*x
,
115 rcu_rbtree_comp comp
)
117 struct rcu_rbtree_node
*xr
, *y
, *yr
;
119 x
= rcu_dereference(x
);
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
) {
126 y
= rcu_dereference(y
->p
);
131 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree_node
*x
,
132 rcu_rbtree_comp comp
)
134 struct rcu_rbtree_node
*xl
, *y
, *yl
;
136 x
= rcu_dereference(x
);
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
) {
143 y
= rcu_dereference(y
->p
);
149 * We have to ensure these assumptions are correct for prev/next
152 * with x being a right child, the assumption that:
154 * or if x is a left child, the assumption that:
157 * This explains why we have to allocate a vc copy of the node for left_rotate,
158 * right_rotate and transplant operations.
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
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
)
174 struct rcu_rbtree_node
*xc
, *y
, *yc
, *b
, *bc
;
176 dbg_printf("left rotate %p\n", x
->key
);
180 if (x
!= &rcu_rbtree_nil
) {
186 if (y
!= &rcu_rbtree_nil
) {
195 if (b
!= &rcu_rbtree_nil
) {
196 /* Beta position changes from left to right. */
199 assert(b
->pos
== IS_LEFT
);
202 bc
= &rcu_rbtree_nil
;
204 /* Modify children and parents in the node copies */
205 if (x
!= &rcu_rbtree_nil
) {
209 xc
= &rcu_rbtree_nil
;
211 if (y
!= &rcu_rbtree_nil
) {
215 yc
= &rcu_rbtree_nil
;
218 * Order stores to node copies (children/parents) before stores that
219 * will make the copies visible to the rest of the tree.
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
);
229 _STORE_SHARED(x
->p
->right
, yc
);
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
);
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 */
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
);
250 static void left_rotate(struct rcu_rbtree_node
**root
,
251 struct rcu_rbtree_node
*x
,
252 rcu_rbtree_alloc rballoc
)
254 struct rcu_rbtree_node
*y
;
258 if (y
->left
!= &rcu_rbtree_nil
)
261 if (x
->p
== &rcu_rbtree_nil
)
263 else if (x
== x
->p
->left
)
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
)
281 struct rcu_rbtree_node
*x
, *xc
, *yc
, *b
, *bc
;;
283 dbg_printf("right rotate %p\n", y
->key
);
287 if (x
!= &rcu_rbtree_nil
) {
296 if (y
!= &rcu_rbtree_nil
) {
302 if (b
!= &rcu_rbtree_nil
) {
303 /* Beta position changes from right to left. */
306 assert(b
->pos
== IS_RIGHT
);
309 bc
= &rcu_rbtree_nil
;
311 /* Modify children and parents in the node copies */
312 if (x
!= &rcu_rbtree_nil
) {
316 xc
= &rcu_rbtree_nil
;
318 if (y
!= &rcu_rbtree_nil
) {
322 yc
= &rcu_rbtree_nil
;
325 * Order stores to node copies (children/parents) before stores that
326 * will make the copies visible to the rest of the tree.
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
);
336 _STORE_SHARED(y
->p
->left
, xc
);
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
);
344 if (y
!= &rcu_rbtree_nil
) {
345 _STORE_SHARED(yc
->right
->p
, yc
);/* gamma stays right */
346 defer_rcu(rbfree
, y
);
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
);
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
)
361 struct rcu_rbtree_node
*y
;
363 dbg_printf("insert fixup %p\n", z
->key
);
365 while (z
->p
->color
== COLOR_RED
) {
366 if (z
->p
== z
->p
->p
->left
) {
368 if (y
->color
== COLOR_RED
) {
369 z
->p
->color
= COLOR_BLACK
;
370 y
->color
= COLOR_BLACK
;
371 z
->p
->p
->color
= COLOR_RED
;
374 if (z
== z
->p
->right
) {
376 z
= left_rotate(root
, z
,
379 z
->p
->color
= COLOR_BLACK
;
380 z
->p
->p
->color
= COLOR_RED
;
381 right_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
385 if (y
->color
== COLOR_RED
) {
386 z
->p
->color
= COLOR_BLACK
;
387 y
->color
= COLOR_BLACK
;
388 z
->p
->p
->color
= COLOR_RED
;
391 if (z
== z
->p
->left
) {
393 z
= right_rotate(root
, z
,
396 z
->p
->color
= COLOR_BLACK
;
397 z
->p
->p
->color
= COLOR_RED
;
398 left_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
402 (*root
)->color
= COLOR_BLACK
;
406 * rcu_rbtree_insert - Insert a node in the RCU rbtree
408 * Returns 0 on success, or < 0 on error.
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
)
416 struct rcu_rbtree_node
*x
, *y
;
418 dbg_printf("insert %p\n", z
->key
);
423 while (x
!= &rcu_rbtree_nil
) {
425 if (comp(z
->key
, x
->key
) < 0)
432 z
->left
= &rcu_rbtree_nil
;
433 z
->right
= &rcu_rbtree_nil
;
434 z
->color
= COLOR_RED
;
436 if (y
== &rcu_rbtree_nil
)
437 z
->pos
= IS_RIGHT
; /* arbitrary for root node */
438 else if (comp(z
->key
, y
->key
) < 0)
444 * Order stores to z (children/parents) before stores that will make it
445 * visible to the rest of the tree.
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
);
454 _STORE_SHARED(y
->right
, z
);
455 rcu_rbtree_insert_fixup(root
, z
, rballoc
, rbfree
);
457 * Make sure to commit all _STORE_SHARED() for non-coherent caches.
465 * Transplant v into u position.
466 * Returns new copy of v.
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
)
475 struct rcu_rbtree_node
*vc
;
477 dbg_printf("transplant %p\n", v
->key
);
479 if (v
!= &rcu_rbtree_nil
) {
483 /* Change vc parent pointer */
488 * Order stores to node copies (children/parents) before stores
489 * that will make the copies visible to the rest of the tree.
493 vc
= &rcu_rbtree_nil
;
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
);
502 _STORE_SHARED(u
->p
->right
, vc
);
504 if (v
!= &rcu_rbtree_nil
) {
506 * The children pointers in vc are the same as v. We can
507 * therefore reparent v's children to vc safely.
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
);
514 defer_rcu(rbfree
, v
);
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
)
524 dbg_printf("remove fixup %p\n", x
->key
);
526 while (x
!= *root
&& x
->color
== COLOR_BLACK
) {
527 if (x
== x
->p
->left
) {
528 struct rcu_rbtree_node
*w
, *t
;
531 assert(w
!= &rcu_rbtree_nil
);
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 */
541 if (w
->left
->color
== COLOR_BLACK
542 && w
->right
->color
== COLOR_BLACK
) {
543 w
->color
= COLOR_RED
;
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
);
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
);
559 struct rcu_rbtree_node
*w
, *t
;
562 assert(w
!= &rcu_rbtree_nil
);
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 */
572 if (w
->right
->color
== COLOR_BLACK
573 && w
->left
->color
== COLOR_BLACK
) {
574 w
->color
= COLOR_RED
;
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
);
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
);
591 x
->color
= COLOR_BLACK
;
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
)
605 struct rcu_rbtree_node
*x
, *xc
, *yc
;
607 dbg_printf("remove nonil %p\n", z
->key
);
611 if (x
!= &rcu_rbtree_nil
) {
615 xc
= &rcu_rbtree_nil
;
620 /* Update parent and children pointers within copies */
624 /* Transplant y->right (xc) into y, within copy */
626 /* But also change the right pointer of yc */
627 yc
->right
= z
->right
;
629 /* Transplant y into z, within copy */
633 yc
->color
= z
->color
;
636 * Order stores to node copies (children/parents) before stores that
637 * will make the copies visible to the rest of the tree.
641 /* Update external pointers */
644 /* Transplant y->right into y, external parent links */
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
);
652 _STORE_SHARED(y
->p
->right
, xc
);
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
);
661 _STORE_SHARED(z
->p
->right
, yc
);
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
);
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
);
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
)
690 struct rcu_rbtree_node
*x
, *y
;
691 unsigned int y_original_color
;
693 dbg_printf("remove %p\n", z
->key
);
696 y_original_color
= y
->color
;
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
);
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
);
707 if (y_original_color
== COLOR_BLACK
)
708 rcu_rbtree_remove_fixup(root
, x
, rballoc
, rbfree
);
710 * Commit all _STORE_SHARED().