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>
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.
48 /* Sentinel (bottom nodes). Don't care about p, left, right and key values */
49 struct rcu_rbtree_node rcu_rbtree_nil
= {
54 * Iterative rbtree search.
56 struct rcu_rbtree_node
* rcu_rbtree_search(struct rcu_rbtree_node
*x
,
57 void *k
, rcu_rbtree_comp comp
)
59 x
= rcu_dereference(x
);
61 while (x
!= &rcu_rbtree_nil
&& k
!= x
->key
) {
63 x
= rcu_dereference(x
->left
);
65 x
= rcu_dereference(x
->right
);
70 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree_node
*x
,
73 struct rcu_rbtree_node
*xl
;
75 x
= rcu_dereference(x
);
77 while ((xl
= rcu_dereference(x
->left
)) != &rcu_rbtree_nil
)
82 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree_node
*x
,
85 struct rcu_rbtree_node
*xr
;
87 x
= rcu_dereference(x
);
89 while ((xr
= rcu_dereference(x
->right
)) != &rcu_rbtree_nil
)
95 * next and prev need to have mutex held to ensure that parent pointer is
98 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree_node
*x
,
101 struct rcu_rbtree_node
*xr
, *y
, *yredir
;
103 x
= rcu_dereference(x
);
105 if ((xr
= rcu_dereference(x
->right
)) != &rcu_rbtree_nil
)
106 return rcu_rbtree_min(xr
, comp
);
107 y
= rcu_dereference(x
->p
);
108 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
110 while (y
!= &rcu_rbtree_nil
&& x
== rcu_dereference(y
->right
)) {
112 y
= rcu_dereference(y
->p
);
113 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
119 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree_node
*x
,
120 rcu_rbtree_comp comp
)
122 struct rcu_rbtree_node
*xl
, *y
, *yredir
;
124 x
= rcu_dereference(x
);
126 if ((xl
= rcu_dereference(x
->left
)) != &rcu_rbtree_nil
)
127 return rcu_rbtree_max(xl
, comp
);
128 y
= rcu_dereference(x
->p
);
129 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
131 while (y
!= &rcu_rbtree_nil
&& x
== rcu_dereference(y
->left
)) {
133 y
= rcu_dereference(y
->p
);
134 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
141 * We have to ensure these assumptions are correct for prev/next
144 * with x being a right child, the assumption that:
146 * or if x is a left child, the assumption that:
149 * This explains why we have to allocate a vc copy of the node for left_rotate,
150 * right_rotate and transplant operations.
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
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 static struct rcu_rbtree_node
*left_rotate(struct rcu_rbtree_node
**root
,
161 struct rcu_rbtree_node
*x
,
162 rcu_rbtree_alloc rballoc
,
163 rcu_rbtree_free rbfree
)
165 struct rcu_rbtree_node
*xc
, *y
, *yc
;
169 if (x
!= &rcu_rbtree_nil
) {
174 if (y
!= &rcu_rbtree_nil
) {
179 /* Modify children and parents in the node copies */
180 if (x
!= &rcu_rbtree_nil
) {
184 xc
= &rcu_rbtree_nil
;
186 if (y
!= &rcu_rbtree_nil
) {
190 yc
= &rcu_rbtree_nil
;
193 * Order stores to node copies (children/parents) before stores that
194 * will make the copies visible to the rest of the tree.
199 * redirect old nodes to new.
205 * Ensure that redirections are visible before updating external
210 /* Make parents point to the copies */
211 if (x
->p
== &rcu_rbtree_nil
)
212 _STORE_SHARED(*root
, yc
);
213 else if (x
== x
->p
->left
)
214 _STORE_SHARED(x
->p
->left
, yc
);
216 _STORE_SHARED(x
->p
->right
, yc
);
218 /* Assign children parents to copies */
219 if (x
!= &rcu_rbtree_nil
) {
220 _STORE_SHARED(xc
->right
->p
, xc
);
221 _STORE_SHARED(xc
->left
->p
, xc
);
222 defer_rcu(rbfree
, x
);
224 if (y
!= &rcu_rbtree_nil
) {
225 _STORE_SHARED(yc
->right
->p
, yc
);
226 defer_rcu(rbfree
, y
);
227 /* yc->left is xc, its parent is already set in node copy */
233 static void left_rotate(struct rcu_rbtree_node
**root
,
234 struct rcu_rbtree_node
*x
,
235 rcu_rbtree_alloc rballoc
)
237 struct rcu_rbtree_node
*y
;
241 if (y
->left
!= &rcu_rbtree_nil
)
244 if (x
->p
== &rcu_rbtree_nil
)
246 else if (x
== x
->p
->left
)
255 /* RCU: copy x and y, atomically point to new versions. GC old. */
256 /* Should be eventually followed by a smp_wmc() */
257 /* Returns the new x. Previous x->left references are changed to yc. */
258 static struct rcu_rbtree_node
*right_rotate(struct rcu_rbtree_node
**root
,
259 struct rcu_rbtree_node
*x
,
260 rcu_rbtree_alloc rballoc
,
261 rcu_rbtree_free rbfree
)
263 struct rcu_rbtree_node
*xc
, *y
, *yc
;
267 if (x
!= &rcu_rbtree_nil
) {
272 if (y
!= &rcu_rbtree_nil
) {
277 /* Modify children and parents in the node copies */
278 if (x
!= &rcu_rbtree_nil
) {
282 xc
= &rcu_rbtree_nil
;
284 if (y
!= &rcu_rbtree_nil
) {
288 yc
= &rcu_rbtree_nil
;
291 * Order stores to node copies (children/parents) before stores that
292 * will make the copies visible to the rest of the tree.
297 * redirect old nodes to new.
303 * Ensure that redirections are visible before updating external
308 /* Make parents point to the copies */
309 if (x
->p
== &rcu_rbtree_nil
)
310 _STORE_SHARED(*root
, yc
);
311 else if (x
== x
->p
->right
)
312 _STORE_SHARED(x
->p
->right
, yc
);
314 _STORE_SHARED(x
->p
->left
, yc
);
316 /* Assign children parents to copies */
317 if (x
!= &rcu_rbtree_nil
) {
318 _STORE_SHARED(xc
->left
->p
, xc
);
319 _STORE_SHARED(xc
->right
->p
, xc
);
320 defer_rcu(rbfree
, x
);
322 if (y
!= &rcu_rbtree_nil
) {
323 _STORE_SHARED(yc
->left
->p
, yc
);
324 defer_rcu(rbfree
, y
);
325 /* yc->right is xc, its parent is already set in node copy */
331 static void right_rotate(struct rcu_rbtree_node
**root
,
332 struct rcu_rbtree_node
*x
,
333 rcu_rbtree_alloc rballoc
)
335 struct rcu_rbtree_node
*y
;
339 if (y
->right
!= &rcu_rbtree_nil
)
342 if (x
->p
== &rcu_rbtree_nil
)
344 else if (x
== x
->p
->right
)
353 static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node
**root
,
354 struct rcu_rbtree_node
*z
,
355 rcu_rbtree_alloc rballoc
,
356 rcu_rbtree_free rbfree
)
358 struct rcu_rbtree_node
*y
;
360 while (z
->p
->color
== COLOR_RED
) {
361 if (z
->p
== z
->p
->p
->left
) {
363 if (y
->color
== COLOR_RED
) {
364 z
->p
->color
= COLOR_BLACK
;
365 y
->color
= COLOR_BLACK
;
366 z
->p
->p
->color
= COLOR_RED
;
369 if (z
== z
->p
->right
) {
371 z
= left_rotate(root
, z
,
374 z
->p
->color
= COLOR_BLACK
;
375 z
->p
->p
->color
= COLOR_RED
;
376 right_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
380 if (y
->color
== COLOR_RED
) {
381 z
->p
->color
= COLOR_BLACK
;
382 y
->color
= COLOR_BLACK
;
383 z
->p
->p
->color
= COLOR_RED
;
386 if (z
== z
->p
->left
) {
388 z
= right_rotate(root
, z
,
391 z
->p
->color
= COLOR_BLACK
;
392 z
->p
->p
->color
= COLOR_RED
;
393 left_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
397 (*root
)->color
= COLOR_BLACK
;
401 * rcu_rbtree_insert - Insert a node in the RCU rbtree
403 * Returns 0 on success, or < 0 on error.
405 int rcu_rbtree_insert(struct rcu_rbtree_node
**root
,
406 struct rcu_rbtree_node
*z
,
407 rcu_rbtree_comp comp
,
408 rcu_rbtree_alloc rballoc
,
409 rcu_rbtree_free rbfree
)
411 struct rcu_rbtree_node
*x
, *y
;
416 while (x
!= &rcu_rbtree_nil
) {
418 if (comp(z
->key
, x
->key
) < 0)
425 z
->left
= &rcu_rbtree_nil
;
426 z
->right
= &rcu_rbtree_nil
;
427 z
->color
= COLOR_RED
;
431 * Order stores to z (children/parents) before stores that will make it
432 * visible to the rest of the tree.
436 if (y
== &rcu_rbtree_nil
)
437 _STORE_SHARED(*root
, z
);
438 else if (comp(z
->key
, y
->key
) < 0)
439 _STORE_SHARED(y
->left
, z
);
441 _STORE_SHARED(y
->right
, z
);
442 rcu_rbtree_insert_fixup(root
, z
, rballoc
, rbfree
);
444 * Make sure to commit all _STORE_SHARED() for non-coherent caches.
452 * Transplant v into u position.
453 * Returns new copy of v.
455 static struct rcu_rbtree_node
*
456 rcu_rbtree_transplant(struct rcu_rbtree_node
**root
,
457 struct rcu_rbtree_node
*u
,
458 struct rcu_rbtree_node
*v
,
459 rcu_rbtree_alloc rballoc
,
460 rcu_rbtree_free rbfree
)
462 struct rcu_rbtree_node
*vc
;
464 if (v
!= &rcu_rbtree_nil
) {
468 /* Change vc parent pointer */
472 * Order stores to node copies (children/parents) before stores
473 * that will make the copies visible to the rest of the tree.
478 * redirect old node to new.
483 * Ensure that redirections are visible before updating external
488 vc
= &rcu_rbtree_nil
;
491 /* Assign upper-level pointer to vc, replacing u. */
492 if (u
->p
== &rcu_rbtree_nil
)
493 _STORE_SHARED(*root
, vc
);
494 else if (u
== u
->p
->left
)
495 _STORE_SHARED(u
->p
->left
, vc
);
497 _STORE_SHARED(u
->p
->right
, vc
);
499 if (v
!= &rcu_rbtree_nil
) {
501 * The children pointers in vc are the same as v. We can
502 * therefore reparent v's children to vc safely.
504 _STORE_SHARED(vc
->right
->p
, vc
);
505 _STORE_SHARED(vc
->left
->p
, vc
);
507 defer_rcu(rbfree
, v
);
512 static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node
**root
,
513 struct rcu_rbtree_node
*x
,
514 rcu_rbtree_alloc rballoc
,
515 rcu_rbtree_free rbfree
)
517 while (x
!= *root
&& x
->color
== COLOR_BLACK
) {
518 if (x
== x
->p
->left
) {
519 struct rcu_rbtree_node
*w
, *t
;
522 if (w
->color
== COLOR_RED
) {
523 w
->color
== COLOR_BLACK
;
524 x
->p
->color
= COLOR_RED
;
525 t
= left_rotate(root
, x
->p
, rballoc
, rbfree
);
526 assert(x
->p
->left
== t
->left
);
527 /* x is a left node, not copied by rotation */
530 if (w
->left
->color
== COLOR_BLACK
531 && w
->right
->color
== COLOR_BLACK
) {
532 w
->color
= COLOR_RED
;
535 if (w
->right
->color
== COLOR_BLACK
) {
536 w
->left
->color
= COLOR_BLACK
;
537 w
->color
= COLOR_RED
;
538 right_rotate(root
, w
, rballoc
, rbfree
);
541 w
->color
= x
->p
->color
;
542 x
->p
->color
= COLOR_BLACK
;
543 w
->right
->color
= COLOR_BLACK
;
544 left_rotate(root
, x
->p
, rballoc
, rbfree
);
548 struct rcu_rbtree_node
*w
;
551 if (w
->color
== COLOR_RED
) {
552 w
->color
== COLOR_BLACK
;
553 x
->p
->color
= COLOR_RED
;
554 right_rotate(root
, x
->p
, rballoc
, rbfree
);
555 /* x is a right node, not copied by rotation */
558 if (w
->right
->color
== COLOR_BLACK
559 && w
->left
->color
== COLOR_BLACK
) {
560 w
->color
= COLOR_RED
;
563 if (w
->left
->color
== COLOR_BLACK
) {
564 w
->right
->color
= COLOR_BLACK
;
565 w
->color
= COLOR_RED
;
566 left_rotate(root
, w
, rballoc
, rbfree
);
569 w
->color
= x
->p
->color
;
570 x
->p
->color
= COLOR_BLACK
;
571 w
->left
->color
= COLOR_BLACK
;
572 right_rotate(root
, x
->p
, rballoc
, rbfree
);
577 x
->color
= COLOR_BLACK
;
580 /* Returns the new copy of y->right */
581 static struct rcu_rbtree_node
*
582 rcu_rbtree_remove_nonil(struct rcu_rbtree_node
**root
,
583 struct rcu_rbtree_node
*z
,
584 struct rcu_rbtree_node
*y
,
585 rcu_rbtree_comp comp
,
586 rcu_rbtree_alloc rballoc
,
587 rcu_rbtree_free rbfree
)
589 struct rcu_rbtree_node
*x
, *xc
, *yc
;
593 if (x
!= &rcu_rbtree_nil
) {
597 xc
= &rcu_rbtree_nil
;
602 /* Update parent and children pointers within copies */
606 /* Transplant y->right (xc) into y, within copy */
608 /* But also change the right pointer of yc */
609 yc
->right
= z
->right
;
611 /* Transplant y into z, within copy */
615 yc
->color
= z
->color
;
618 * Order stores to node copies (children/parents) before stores that
619 * will make the copies visible to the rest of the tree.
624 * redirect old nodes to new.
626 if (x
!= &rcu_rbtree_nil
)
631 * Ensure that redirections are visible before updating external
636 /* Update external pointers */
639 /* Transplant y->right into y, external parent links */
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
);
647 _STORE_SHARED(y
->p
->right
, xc
);
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
);
656 _STORE_SHARED(z
->p
->right
, yc
);
658 if (x
!= &rcu_rbtree_nil
) {
659 /* Reparent xc's children to xc. */
660 _STORE_SHARED(xc
->right
->p
, xc
);
661 _STORE_SHARED(xc
->left
->p
, xc
);
662 defer_rcu(rbfree
, x
);
665 /* Reparent yc's children to yc */
666 _STORE_SHARED(yc
->right
->p
, yc
);
667 _STORE_SHARED(yc
->left
->p
, yc
);
668 defer_rcu(rbfree
, y
);
673 int rcu_rbtree_remove(struct rcu_rbtree_node
**root
,
674 struct rcu_rbtree_node
*z
,
675 rcu_rbtree_comp comp
,
676 rcu_rbtree_alloc rballoc
,
677 rcu_rbtree_free rbfree
)
679 struct rcu_rbtree_node
*x
, *y
;
680 unsigned int y_original_color
;
683 y_original_color
= y
->color
;
685 if (z
->left
== &rcu_rbtree_nil
) {
686 x
= rcu_rbtree_transplant(root
, z
, z
->right
, rballoc
, rbfree
);
687 } else if (z
->right
== &rcu_rbtree_nil
) {
688 x
= rcu_rbtree_transplant(root
, z
, z
->left
, rballoc
, rbfree
);
690 y
= rcu_rbtree_min(z
->right
, comp
);
691 y_original_color
= y
->color
;
692 x
= rcu_rbtree_remove_nonil(root
, z
, y
, comp
, rballoc
, rbfree
);
694 if (y_original_color
== COLOR_BLACK
)
695 rcu_rbtree_remove_fixup(root
, x
, rballoc
, rbfree
);
697 * Commit all _STORE_SHARED().