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>
41 #define dbg_printf(args...) printf(args)
43 #define dbg_printf(args...)
48 * Deal with memory allocation errors.
49 * Can be ensured by reserving a pool of memory entries before doing the
50 * insertion, which will have to be function of number of
51 * transplantations/rotations required for the operation.
54 /* Sentinel (bottom nodes).
55 * Don't care about p, left, right, pos and key values */
56 struct rcu_rbtree_node rcu_rbtree_nil
= {
61 * Iterative rbtree search.
63 struct rcu_rbtree_node
* rcu_rbtree_search(struct rcu_rbtree_node
*x
,
64 void *k
, rcu_rbtree_comp comp
)
66 x
= rcu_dereference(x
);
68 while (x
!= &rcu_rbtree_nil
&& k
!= x
->key
) {
70 x
= rcu_dereference(x
->left
);
72 x
= rcu_dereference(x
->right
);
77 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree_node
*x
,
80 struct rcu_rbtree_node
*xl
;
82 x
= rcu_dereference(x
);
84 while ((xl
= rcu_dereference(x
->left
)) != &rcu_rbtree_nil
)
89 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree_node
*x
,
92 struct rcu_rbtree_node
*xr
;
94 x
= rcu_dereference(x
);
96 while ((xr
= rcu_dereference(x
->right
)) != &rcu_rbtree_nil
)
103 * Updates should wait for a grace period between update of the
104 * redirect pointer and update of the parent child pointer. This is to make sure
105 * that no reference to the old entry exist.
109 * next and prev need to have mutex held to ensure that parent pointer is
112 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree_node
*x
,
113 rcu_rbtree_comp comp
)
115 struct rcu_rbtree_node
*xr
, *y
, *yr
;
117 x
= rcu_dereference(x
);
119 if ((xr
= rcu_dereference(x
->right
)) != &rcu_rbtree_nil
)
120 return rcu_rbtree_min(xr
, comp
);
121 y
= rcu_dereference(x
->p
);
122 while (y
!= &rcu_rbtree_nil
&& x
->pos
== IS_RIGHT
) {
124 y
= rcu_dereference(y
->p
);
129 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree_node
*x
,
130 rcu_rbtree_comp comp
)
132 struct rcu_rbtree_node
*xl
, *y
, *yl
;
134 x
= rcu_dereference(x
);
136 if ((xl
= rcu_dereference(x
->left
)) != &rcu_rbtree_nil
)
137 return rcu_rbtree_min(xl
, comp
);
138 y
= rcu_dereference(x
->p
);
139 while (y
!= &rcu_rbtree_nil
&& x
->pos
== IS_LEFT
) {
141 y
= rcu_dereference(y
->p
);
147 * We have to ensure these assumptions are correct for prev/next
150 * with x being a right child, the assumption that:
152 * or if x is a left child, the assumption that:
155 * This explains why we have to allocate a vc copy of the node for left_rotate,
156 * right_rotate and transplant operations.
158 * We always ensure that the right/left child and correct parent is set in the
159 * node copies *before* we reparent the children and make the upper-level point
163 /* RCU: copy x and y, atomically point to new versions. GC old. */
164 /* Should be eventually followed by a smp_wmc() */
165 /* Returns the new x. Previous x->right references are changed to yc.
166 * Previous y->left->right is changed to bc. */
167 static struct rcu_rbtree_node
*left_rotate(struct rcu_rbtree_node
**root
,
168 struct rcu_rbtree_node
*x
,
169 rcu_rbtree_alloc rballoc
,
170 rcu_rbtree_free rbfree
)
172 struct rcu_rbtree_node
*xc
, *y
, *yc
, *b
, *bc
;
174 dbg_printf("left rotate %p\n", x
->key
);
178 if (x
!= &rcu_rbtree_nil
) {
184 if (y
!= &rcu_rbtree_nil
) {
193 if (b
!= &rcu_rbtree_nil
) {
194 /* Beta position changes from left to right. */
197 assert(b
->pos
== IS_LEFT
);
200 bc
= &rcu_rbtree_nil
;
202 /* Modify children and parents in the node copies */
203 if (x
!= &rcu_rbtree_nil
) {
207 xc
= &rcu_rbtree_nil
;
209 if (y
!= &rcu_rbtree_nil
) {
213 yc
= &rcu_rbtree_nil
;
216 * Order stores to node copies (children/parents) before stores that
217 * will make the copies visible to the rest of the tree.
221 /* Make parents point to the copies */
222 if (x
->p
== &rcu_rbtree_nil
)
223 _STORE_SHARED(*root
, yc
);
224 else if (x
->pos
== IS_LEFT
)
225 _STORE_SHARED(x
->p
->left
, yc
);
227 _STORE_SHARED(x
->p
->right
, yc
);
229 /* Assign children parents to copies */
230 if (x
!= &rcu_rbtree_nil
) {
231 _STORE_SHARED(xc
->left
->p
, xc
); /* alpha stays left */
232 defer_rcu(rbfree
, x
);
234 if (y
!= &rcu_rbtree_nil
) {
235 _STORE_SHARED(yc
->right
->p
, yc
);/* gamma stays right */
236 defer_rcu(rbfree
, y
);
237 /* yc->left is xc, its parent is already set in node copy */
239 if (b
!= &rcu_rbtree_nil
) {
240 _STORE_SHARED(bc
->right
->p
, bc
);
241 _STORE_SHARED(bc
->left
->p
, bc
);
242 defer_rcu(rbfree
, b
);
248 static void left_rotate(struct rcu_rbtree_node
**root
,
249 struct rcu_rbtree_node
*x
,
250 rcu_rbtree_alloc rballoc
)
252 struct rcu_rbtree_node
*y
;
256 if (y
->left
!= &rcu_rbtree_nil
)
259 if (x
->p
== &rcu_rbtree_nil
)
261 else if (x
== x
->p
->left
)
270 /* RCU: copy x and y, atomically point to new versions. GC old. */
271 /* Should be eventually followed by a smp_wmc() */
272 /* Returns the new y. Previous y->left references are changed to xc.
273 * Previous y->left->right is changed to bc */
274 static struct rcu_rbtree_node
*right_rotate(struct rcu_rbtree_node
**root
,
275 struct rcu_rbtree_node
*y
,
276 rcu_rbtree_alloc rballoc
,
277 rcu_rbtree_free rbfree
)
279 struct rcu_rbtree_node
*x
, *xc
, *yc
, *b
, *bc
;;
281 dbg_printf("right rotate %p\n", y
->key
);
285 if (x
!= &rcu_rbtree_nil
) {
294 if (y
!= &rcu_rbtree_nil
) {
300 if (b
!= &rcu_rbtree_nil
) {
301 /* Beta position changes from right to left. */
304 assert(b
->pos
== IS_RIGHT
);
307 bc
= &rcu_rbtree_nil
;
309 /* Modify children and parents in the node copies */
310 if (x
!= &rcu_rbtree_nil
) {
314 xc
= &rcu_rbtree_nil
;
316 if (y
!= &rcu_rbtree_nil
) {
320 yc
= &rcu_rbtree_nil
;
323 * Order stores to node copies (children/parents) before stores that
324 * will make the copies visible to the rest of the tree.
328 /* Make parents point to the copies */
329 if (y
->p
== &rcu_rbtree_nil
)
330 _STORE_SHARED(*root
, xc
);
331 else if (y
->pos
== IS_RIGHT
)
332 _STORE_SHARED(y
->p
->right
, xc
);
334 _STORE_SHARED(y
->p
->left
, xc
);
336 /* Assign children parents to copies */
337 if (x
!= &rcu_rbtree_nil
) {
338 _STORE_SHARED(xc
->left
->p
, xc
); /* alpha stays left */
339 /* xc->right is yc, its parent is already set in node copy */
340 defer_rcu(rbfree
, x
);
342 if (y
!= &rcu_rbtree_nil
) {
343 _STORE_SHARED(yc
->right
->p
, yc
);/* gamma stays right */
344 defer_rcu(rbfree
, y
);
346 if (b
!= &rcu_rbtree_nil
) {
347 _STORE_SHARED(bc
->right
->p
, bc
);
348 _STORE_SHARED(bc
->left
->p
, bc
);
349 defer_rcu(rbfree
, b
);
354 static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node
**root
,
355 struct rcu_rbtree_node
*z
,
356 rcu_rbtree_alloc rballoc
,
357 rcu_rbtree_free rbfree
)
359 struct rcu_rbtree_node
*y
;
361 dbg_printf("insert fixup %p\n", z
->key
);
363 while (z
->p
->color
== COLOR_RED
) {
364 if (z
->p
== z
->p
->p
->left
) {
366 if (y
->color
== COLOR_RED
) {
367 z
->p
->color
= COLOR_BLACK
;
368 y
->color
= COLOR_BLACK
;
369 z
->p
->p
->color
= COLOR_RED
;
372 if (z
== z
->p
->right
) {
374 z
= left_rotate(root
, z
,
377 z
->p
->color
= COLOR_BLACK
;
378 z
->p
->p
->color
= COLOR_RED
;
379 right_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
383 if (y
->color
== COLOR_RED
) {
384 z
->p
->color
= COLOR_BLACK
;
385 y
->color
= COLOR_BLACK
;
386 z
->p
->p
->color
= COLOR_RED
;
389 if (z
== z
->p
->left
) {
391 z
= right_rotate(root
, z
,
394 z
->p
->color
= COLOR_BLACK
;
395 z
->p
->p
->color
= COLOR_RED
;
396 left_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
400 (*root
)->color
= COLOR_BLACK
;
404 * rcu_rbtree_insert - Insert a node in the RCU rbtree
406 * Returns 0 on success, or < 0 on error.
408 int rcu_rbtree_insert(struct rcu_rbtree_node
**root
,
409 struct rcu_rbtree_node
*z
,
410 rcu_rbtree_comp comp
,
411 rcu_rbtree_alloc rballoc
,
412 rcu_rbtree_free rbfree
)
414 struct rcu_rbtree_node
*x
, *y
;
416 dbg_printf("insert %p\n", z
->key
);
421 while (x
!= &rcu_rbtree_nil
) {
423 if (comp(z
->key
, x
->key
) < 0)
430 z
->left
= &rcu_rbtree_nil
;
431 z
->right
= &rcu_rbtree_nil
;
432 z
->color
= COLOR_RED
;
434 if (y
== &rcu_rbtree_nil
)
435 z
->pos
= IS_RIGHT
; /* arbitrary for root node */
436 else if (comp(z
->key
, y
->key
) < 0)
442 * Order stores to z (children/parents) before stores that will make it
443 * visible to the rest of the tree.
447 if (y
== &rcu_rbtree_nil
)
448 _STORE_SHARED(*root
, z
);
449 else if (comp(z
->key
, y
->key
) < 0)
450 _STORE_SHARED(y
->left
, z
);
452 _STORE_SHARED(y
->right
, z
);
453 rcu_rbtree_insert_fixup(root
, z
, rballoc
, rbfree
);
455 * Make sure to commit all _STORE_SHARED() for non-coherent caches.
463 * Transplant v into u position.
464 * Returns new copy of v.
466 static struct rcu_rbtree_node
*
467 rcu_rbtree_transplant(struct rcu_rbtree_node
**root
,
468 struct rcu_rbtree_node
*u
,
469 struct rcu_rbtree_node
*v
,
470 rcu_rbtree_alloc rballoc
,
471 rcu_rbtree_free rbfree
)
473 struct rcu_rbtree_node
*vc
;
475 dbg_printf("transplant %p\n", v
->key
);
477 if (v
!= &rcu_rbtree_nil
) {
481 /* Change vc parent pointer */
486 * Order stores to node copies (children/parents) before stores
487 * that will make the copies visible to the rest of the tree.
491 vc
= &rcu_rbtree_nil
;
494 /* Assign upper-level pointer to vc, replacing u. */
495 if (u
->p
== &rcu_rbtree_nil
)
496 _STORE_SHARED(*root
, vc
);
497 else if (u
== u
->p
->left
)
498 _STORE_SHARED(u
->p
->left
, vc
);
500 _STORE_SHARED(u
->p
->right
, vc
);
502 if (v
!= &rcu_rbtree_nil
) {
504 * The children pointers in vc are the same as v. We can
505 * therefore reparent v's children to vc safely.
507 if (vc
->right
!= &rcu_rbtree_nil
)
508 _STORE_SHARED(vc
->right
->p
, vc
);
509 if (vc
->left
!= &rcu_rbtree_nil
)
510 _STORE_SHARED(vc
->left
->p
, vc
);
512 defer_rcu(rbfree
, v
);
517 static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node
**root
,
518 struct rcu_rbtree_node
*x
,
519 rcu_rbtree_alloc rballoc
,
520 rcu_rbtree_free rbfree
)
522 dbg_printf("remove fixup %p\n", x
->key
);
524 while (x
!= *root
&& x
->color
== COLOR_BLACK
) {
525 if (x
== x
->p
->left
) {
526 struct rcu_rbtree_node
*w
, *t
;
529 if (w
->color
== COLOR_RED
) {
530 w
->color
== COLOR_BLACK
;
531 x
->p
->color
= COLOR_RED
;
532 t
= left_rotate(root
, x
->p
, rballoc
, rbfree
);
533 assert(x
->p
->left
== t
->left
);
534 /* x is a left node, not copied by rotation */
537 if (w
->left
->color
== COLOR_BLACK
538 && w
->right
->color
== COLOR_BLACK
) {
539 w
->color
= COLOR_RED
;
542 if (w
->right
->color
== COLOR_BLACK
) {
543 w
->left
->color
= COLOR_BLACK
;
544 w
->color
= COLOR_RED
;
545 right_rotate(root
, w
, rballoc
, rbfree
);
548 w
->color
= x
->p
->color
;
549 x
->p
->color
= COLOR_BLACK
;
550 w
->right
->color
= COLOR_BLACK
;
551 left_rotate(root
, x
->p
, rballoc
, rbfree
);
555 struct rcu_rbtree_node
*w
, *t
;
558 if (w
->color
== COLOR_RED
) {
559 w
->color
== COLOR_BLACK
;
560 x
->p
->color
= COLOR_RED
;
561 t
= right_rotate(root
, x
->p
, rballoc
, rbfree
);
562 assert(x
->p
->right
== t
->right
);
563 /* x is a right node, not copied by rotation */
566 if (w
->right
->color
== COLOR_BLACK
567 && w
->left
->color
== COLOR_BLACK
) {
568 w
->color
= COLOR_RED
;
571 if (w
->left
->color
== COLOR_BLACK
) {
572 w
->right
->color
= COLOR_BLACK
;
573 w
->color
= COLOR_RED
;
574 left_rotate(root
, w
, rballoc
, rbfree
);
577 w
->color
= x
->p
->color
;
578 x
->p
->color
= COLOR_BLACK
;
579 w
->left
->color
= COLOR_BLACK
;
580 right_rotate(root
, x
->p
, rballoc
, rbfree
);
585 x
->color
= COLOR_BLACK
;
589 * Returns the new copy of y->right.
590 * Delete z. All non-copied children left/right positions are unchanged. */
591 static struct rcu_rbtree_node
*
592 rcu_rbtree_remove_nonil(struct rcu_rbtree_node
**root
,
593 struct rcu_rbtree_node
*z
,
594 struct rcu_rbtree_node
*y
,
595 rcu_rbtree_comp comp
,
596 rcu_rbtree_alloc rballoc
,
597 rcu_rbtree_free rbfree
)
599 struct rcu_rbtree_node
*x
, *xc
, *yc
;
601 dbg_printf("remove nonil %p\n", z
->key
);
605 if (x
!= &rcu_rbtree_nil
) {
609 xc
= &rcu_rbtree_nil
;
614 /* Update parent and children pointers within copies */
618 /* Transplant y->right (xc) into y, within copy */
620 /* But also change the right pointer of yc */
621 yc
->right
= z
->right
;
623 /* Transplant y into z, within copy */
627 yc
->color
= z
->color
;
630 * Order stores to node copies (children/parents) before stores that
631 * will make the copies visible to the rest of the tree.
635 /* Update external pointers */
638 /* Transplant y->right into y, external parent links */
640 /* Assign upper-level pointer to xc, replacing y. */
641 if (y
->p
== &rcu_rbtree_nil
)
642 _STORE_SHARED(*root
, xc
);
643 else if (y
== y
->p
->left
)
644 _STORE_SHARED(y
->p
->left
, xc
);
646 _STORE_SHARED(y
->p
->right
, xc
);
649 /* Transplant y into z, update external parent links */
650 if (z
->p
== &rcu_rbtree_nil
)
651 _STORE_SHARED(*root
, yc
);
652 else if (z
== z
->p
->left
)
653 _STORE_SHARED(z
->p
->left
, yc
);
655 _STORE_SHARED(z
->p
->right
, yc
);
657 if (x
!= &rcu_rbtree_nil
) {
658 /* Reparent xc's children to xc. */
659 _STORE_SHARED(xc
->right
->p
, xc
);
660 assert(yc
->right
== &rcu_rbtree_nil
661 || xc
->right
->pos
== IS_RIGHT
);
662 _STORE_SHARED(xc
->left
->p
, xc
);
663 assert(yc
->right
== &rcu_rbtree_nil
664 || xc
->left
->pos
== IS_LEFT
);
665 defer_rcu(rbfree
, x
);
668 /* Reparent yc's children to yc */
669 _STORE_SHARED(yc
->right
->p
, yc
);
670 assert(yc
->right
== &rcu_rbtree_nil
|| yc
->right
->pos
== IS_RIGHT
);
671 _STORE_SHARED(yc
->left
->p
, yc
);
672 assert(yc
->right
== &rcu_rbtree_nil
|| yc
->left
->pos
== IS_LEFT
);
673 defer_rcu(rbfree
, y
);
678 int rcu_rbtree_remove(struct rcu_rbtree_node
**root
,
679 struct rcu_rbtree_node
*z
,
680 rcu_rbtree_comp comp
,
681 rcu_rbtree_alloc rballoc
,
682 rcu_rbtree_free rbfree
)
684 struct rcu_rbtree_node
*x
, *y
;
685 unsigned int y_original_color
;
687 dbg_printf("remove %p\n", z
->key
);
690 y_original_color
= y
->color
;
692 if (z
->left
== &rcu_rbtree_nil
) {
693 x
= rcu_rbtree_transplant(root
, z
, z
->right
, rballoc
, rbfree
);
694 } else if (z
->right
== &rcu_rbtree_nil
) {
695 x
= rcu_rbtree_transplant(root
, z
, z
->left
, rballoc
, rbfree
);
697 y
= rcu_rbtree_min(z
->right
, comp
);
698 y_original_color
= y
->color
;
699 x
= rcu_rbtree_remove_nonil(root
, z
, y
, comp
, rballoc
, rbfree
);
701 if (y_original_color
== COLOR_BLACK
)
702 rcu_rbtree_remove_fixup(root
, x
, rballoc
, rbfree
);
704 * Commit all _STORE_SHARED().