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
, *yr
, *yrredir
;
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
)
111 if (y
== &rcu_rbtree_nil
)
113 yr
= rcu_dereference(y
->right
);
114 while ((yrredir
= rcu_dereference(yr
->redir
)) != NULL
)
119 y
= rcu_dereference(y
->p
);
120 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
126 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree_node
*x
,
127 rcu_rbtree_comp comp
)
129 struct rcu_rbtree_node
*xl
, *y
, *yredir
, *yl
, *ylredir
;;
131 x
= rcu_dereference(x
);
133 if ((xl
= rcu_dereference(x
->left
)) != &rcu_rbtree_nil
)
134 return rcu_rbtree_max(xl
, comp
);
135 y
= rcu_dereference(x
->p
);
136 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
139 if (y
== &rcu_rbtree_nil
)
141 yl
= rcu_dereference(y
->left
);
142 while ((ylredir
= rcu_dereference(yl
->redir
)) != NULL
)
147 y
= rcu_dereference(y
->p
);
148 while ((yredir
= rcu_dereference(y
->redir
)) != NULL
)
155 * We have to ensure these assumptions are correct for prev/next
158 * with x being a right child, the assumption that:
160 * or if x is a left child, the assumption that:
163 * This explains why we have to allocate a vc copy of the node for left_rotate,
164 * right_rotate and transplant operations.
166 * We always ensure that the right/left child and correct parent is set in the
167 * node copies *before* we reparent the children and make the upper-level point
171 /* RCU: copy x and y, atomically point to new versions. GC old. */
172 /* Should be eventually followed by a smp_wmc() */
173 /* Returns the new x. Previous x->right references are changed to yc. */
174 static struct rcu_rbtree_node
*left_rotate(struct rcu_rbtree_node
**root
,
175 struct rcu_rbtree_node
*x
,
176 rcu_rbtree_alloc rballoc
,
177 rcu_rbtree_free rbfree
)
179 struct rcu_rbtree_node
*xc
, *y
, *yc
;
183 if (x
!= &rcu_rbtree_nil
) {
188 if (y
!= &rcu_rbtree_nil
) {
193 /* Modify children and parents in the node copies */
194 if (x
!= &rcu_rbtree_nil
) {
198 xc
= &rcu_rbtree_nil
;
200 if (y
!= &rcu_rbtree_nil
) {
204 yc
= &rcu_rbtree_nil
;
207 * Order stores to node copies (children/parents) before stores that
208 * will make the copies visible to the rest of the tree.
213 * redirect old nodes to new.
215 _STORE_SHARED(x
->redir
, xc
);
216 _STORE_SHARED(y
->redir
, yc
);
219 * Ensure that redirections are visible before updating external
224 /* Make parents point to the copies */
225 if (x
->p
== &rcu_rbtree_nil
)
226 _STORE_SHARED(*root
, yc
);
227 else if (x
== x
->p
->left
)
228 _STORE_SHARED(x
->p
->left
, yc
);
230 _STORE_SHARED(x
->p
->right
, yc
);
232 /* Assign children parents to copies */
233 if (x
!= &rcu_rbtree_nil
) {
234 _STORE_SHARED(xc
->right
->p
, xc
);
235 _STORE_SHARED(xc
->left
->p
, xc
);
236 defer_rcu(rbfree
, x
);
238 if (y
!= &rcu_rbtree_nil
) {
239 _STORE_SHARED(yc
->right
->p
, yc
);
240 defer_rcu(rbfree
, y
);
241 /* yc->left is xc, its parent is already set in node copy */
247 static void left_rotate(struct rcu_rbtree_node
**root
,
248 struct rcu_rbtree_node
*x
,
249 rcu_rbtree_alloc rballoc
)
251 struct rcu_rbtree_node
*y
;
255 if (y
->left
!= &rcu_rbtree_nil
)
258 if (x
->p
== &rcu_rbtree_nil
)
260 else if (x
== x
->p
->left
)
269 /* RCU: copy x and y, atomically point to new versions. GC old. */
270 /* Should be eventually followed by a smp_wmc() */
271 /* Returns the new x. Previous x->left references are changed to yc. */
272 static struct rcu_rbtree_node
*right_rotate(struct rcu_rbtree_node
**root
,
273 struct rcu_rbtree_node
*x
,
274 rcu_rbtree_alloc rballoc
,
275 rcu_rbtree_free rbfree
)
277 struct rcu_rbtree_node
*xc
, *y
, *yc
;
281 if (x
!= &rcu_rbtree_nil
) {
286 if (y
!= &rcu_rbtree_nil
) {
291 /* Modify children and parents in the node copies */
292 if (x
!= &rcu_rbtree_nil
) {
296 xc
= &rcu_rbtree_nil
;
298 if (y
!= &rcu_rbtree_nil
) {
302 yc
= &rcu_rbtree_nil
;
305 * Order stores to node copies (children/parents) before stores that
306 * will make the copies visible to the rest of the tree.
311 * redirect old nodes to new.
313 _STORE_SHARED(x
->redir
, xc
);
314 _STORE_SHARED(y
->redir
, yc
);
317 * Ensure that redirections are visible before updating external
322 /* Make parents point to the copies */
323 if (x
->p
== &rcu_rbtree_nil
)
324 _STORE_SHARED(*root
, yc
);
325 else if (x
== x
->p
->right
)
326 _STORE_SHARED(x
->p
->right
, yc
);
328 _STORE_SHARED(x
->p
->left
, yc
);
330 /* Assign children parents to copies */
331 if (x
!= &rcu_rbtree_nil
) {
332 _STORE_SHARED(xc
->left
->p
, xc
);
333 _STORE_SHARED(xc
->right
->p
, xc
);
334 defer_rcu(rbfree
, x
);
336 if (y
!= &rcu_rbtree_nil
) {
337 _STORE_SHARED(yc
->left
->p
, yc
);
338 defer_rcu(rbfree
, y
);
339 /* yc->right is xc, its parent is already set in node copy */
345 static void right_rotate(struct rcu_rbtree_node
**root
,
346 struct rcu_rbtree_node
*x
,
347 rcu_rbtree_alloc rballoc
)
349 struct rcu_rbtree_node
*y
;
353 if (y
->right
!= &rcu_rbtree_nil
)
356 if (x
->p
== &rcu_rbtree_nil
)
358 else if (x
== x
->p
->right
)
367 static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node
**root
,
368 struct rcu_rbtree_node
*z
,
369 rcu_rbtree_alloc rballoc
,
370 rcu_rbtree_free rbfree
)
372 struct rcu_rbtree_node
*y
;
374 while (z
->p
->color
== COLOR_RED
) {
375 if (z
->p
== z
->p
->p
->left
) {
377 if (y
->color
== COLOR_RED
) {
378 z
->p
->color
= COLOR_BLACK
;
379 y
->color
= COLOR_BLACK
;
380 z
->p
->p
->color
= COLOR_RED
;
383 if (z
== z
->p
->right
) {
385 z
= left_rotate(root
, z
,
388 z
->p
->color
= COLOR_BLACK
;
389 z
->p
->p
->color
= COLOR_RED
;
390 right_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
394 if (y
->color
== COLOR_RED
) {
395 z
->p
->color
= COLOR_BLACK
;
396 y
->color
= COLOR_BLACK
;
397 z
->p
->p
->color
= COLOR_RED
;
400 if (z
== z
->p
->left
) {
402 z
= right_rotate(root
, z
,
405 z
->p
->color
= COLOR_BLACK
;
406 z
->p
->p
->color
= COLOR_RED
;
407 left_rotate(root
, z
->p
->p
, rballoc
, rbfree
);
411 (*root
)->color
= COLOR_BLACK
;
415 * rcu_rbtree_insert - Insert a node in the RCU rbtree
417 * Returns 0 on success, or < 0 on error.
419 int rcu_rbtree_insert(struct rcu_rbtree_node
**root
,
420 struct rcu_rbtree_node
*z
,
421 rcu_rbtree_comp comp
,
422 rcu_rbtree_alloc rballoc
,
423 rcu_rbtree_free rbfree
)
425 struct rcu_rbtree_node
*x
, *y
;
430 while (x
!= &rcu_rbtree_nil
) {
432 if (comp(z
->key
, x
->key
) < 0)
439 z
->left
= &rcu_rbtree_nil
;
440 z
->right
= &rcu_rbtree_nil
;
441 z
->color
= COLOR_RED
;
445 * Order stores to z (children/parents) before stores that will make it
446 * visible to the rest of the tree.
450 if (y
== &rcu_rbtree_nil
)
451 _STORE_SHARED(*root
, z
);
452 else if (comp(z
->key
, y
->key
) < 0)
453 _STORE_SHARED(y
->left
, z
);
455 _STORE_SHARED(y
->right
, z
);
456 rcu_rbtree_insert_fixup(root
, z
, rballoc
, rbfree
);
458 * Make sure to commit all _STORE_SHARED() for non-coherent caches.
466 * Transplant v into u position.
467 * Returns new copy of v.
469 static struct rcu_rbtree_node
*
470 rcu_rbtree_transplant(struct rcu_rbtree_node
**root
,
471 struct rcu_rbtree_node
*u
,
472 struct rcu_rbtree_node
*v
,
473 rcu_rbtree_alloc rballoc
,
474 rcu_rbtree_free rbfree
)
476 struct rcu_rbtree_node
*vc
;
478 if (v
!= &rcu_rbtree_nil
) {
482 /* 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.
492 * redirect old node to new.
494 _STORE_SHARED(v
->redir
, vc
);
497 * Ensure that redirections are visible before updating external
502 vc
= &rcu_rbtree_nil
;
505 /* Assign upper-level pointer to vc, replacing u. */
506 if (u
->p
== &rcu_rbtree_nil
)
507 _STORE_SHARED(*root
, vc
);
508 else if (u
== u
->p
->left
)
509 _STORE_SHARED(u
->p
->left
, vc
);
511 _STORE_SHARED(u
->p
->right
, vc
);
513 if (v
!= &rcu_rbtree_nil
) {
515 * The children pointers in vc are the same as v. We can
516 * therefore reparent v's children to vc safely.
518 _STORE_SHARED(vc
->right
->p
, vc
);
519 _STORE_SHARED(vc
->left
->p
, vc
);
521 defer_rcu(rbfree
, v
);
526 static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node
**root
,
527 struct rcu_rbtree_node
*x
,
528 rcu_rbtree_alloc rballoc
,
529 rcu_rbtree_free rbfree
)
531 while (x
!= *root
&& x
->color
== COLOR_BLACK
) {
532 if (x
== x
->p
->left
) {
533 struct rcu_rbtree_node
*w
, *t
;
536 if (w
->color
== COLOR_RED
) {
537 w
->color
== COLOR_BLACK
;
538 x
->p
->color
= COLOR_RED
;
539 t
= left_rotate(root
, x
->p
, rballoc
, rbfree
);
540 assert(x
->p
->left
== t
->left
);
541 /* x is a left node, not copied by rotation */
544 if (w
->left
->color
== COLOR_BLACK
545 && w
->right
->color
== COLOR_BLACK
) {
546 w
->color
= COLOR_RED
;
549 if (w
->right
->color
== COLOR_BLACK
) {
550 w
->left
->color
= COLOR_BLACK
;
551 w
->color
= COLOR_RED
;
552 right_rotate(root
, w
, rballoc
, rbfree
);
555 w
->color
= x
->p
->color
;
556 x
->p
->color
= COLOR_BLACK
;
557 w
->right
->color
= COLOR_BLACK
;
558 left_rotate(root
, x
->p
, rballoc
, rbfree
);
562 struct rcu_rbtree_node
*w
;
565 if (w
->color
== COLOR_RED
) {
566 w
->color
== COLOR_BLACK
;
567 x
->p
->color
= COLOR_RED
;
568 right_rotate(root
, x
->p
, rballoc
, rbfree
);
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
;
594 /* Returns the new copy of y->right */
595 static struct rcu_rbtree_node
*
596 rcu_rbtree_remove_nonil(struct rcu_rbtree_node
**root
,
597 struct rcu_rbtree_node
*z
,
598 struct rcu_rbtree_node
*y
,
599 rcu_rbtree_comp comp
,
600 rcu_rbtree_alloc rballoc
,
601 rcu_rbtree_free rbfree
)
603 struct rcu_rbtree_node
*x
, *xc
, *yc
;
607 if (x
!= &rcu_rbtree_nil
) {
611 xc
= &rcu_rbtree_nil
;
616 /* Update parent and children pointers within copies */
620 /* Transplant y->right (xc) into y, within copy */
622 /* But also change the right pointer of yc */
623 yc
->right
= z
->right
;
625 /* Transplant y into z, within copy */
629 yc
->color
= z
->color
;
632 * Order stores to node copies (children/parents) before stores that
633 * will make the copies visible to the rest of the tree.
638 * redirect old nodes to new.
640 if (x
!= &rcu_rbtree_nil
)
641 _STORE_SHARED(x
->redir
, xc
);
642 _STORE_SHARED(y
->redir
, yc
);
645 * Ensure that redirections are visible before updating external
650 /* Update external pointers */
653 /* Transplant y->right into y, external parent links */
655 /* Assign upper-level pointer to xc, replacing y. */
656 if (y
->p
== &rcu_rbtree_nil
)
657 _STORE_SHARED(*root
, xc
);
658 else if (y
== y
->p
->left
)
659 _STORE_SHARED(y
->p
->left
, xc
);
661 _STORE_SHARED(y
->p
->right
, xc
);
664 /* Transplant y into z, update external parent links */
665 if (z
->p
== &rcu_rbtree_nil
)
666 _STORE_SHARED(*root
, yc
);
667 else if (z
== z
->p
->left
)
668 _STORE_SHARED(z
->p
->left
, yc
);
670 _STORE_SHARED(z
->p
->right
, yc
);
672 if (x
!= &rcu_rbtree_nil
) {
673 /* Reparent xc's children to xc. */
674 _STORE_SHARED(xc
->right
->p
, xc
);
675 _STORE_SHARED(xc
->left
->p
, xc
);
676 defer_rcu(rbfree
, x
);
679 /* Reparent yc's children to yc */
680 _STORE_SHARED(yc
->right
->p
, yc
);
681 _STORE_SHARED(yc
->left
->p
, yc
);
682 defer_rcu(rbfree
, y
);
687 int rcu_rbtree_remove(struct rcu_rbtree_node
**root
,
688 struct rcu_rbtree_node
*z
,
689 rcu_rbtree_comp comp
,
690 rcu_rbtree_alloc rballoc
,
691 rcu_rbtree_free rbfree
)
693 struct rcu_rbtree_node
*x
, *y
;
694 unsigned int y_original_color
;
697 y_original_color
= y
->color
;
699 if (z
->left
== &rcu_rbtree_nil
) {
700 x
= rcu_rbtree_transplant(root
, z
, z
->right
, rballoc
, rbfree
);
701 } else if (z
->right
== &rcu_rbtree_nil
) {
702 x
= rcu_rbtree_transplant(root
, z
, z
->left
, rballoc
, rbfree
);
704 y
= rcu_rbtree_min(z
->right
, comp
);
705 y_original_color
= y
->color
;
706 x
= rcu_rbtree_remove_nonil(root
, z
, y
, comp
, rballoc
, rbfree
);
708 if (y_original_color
== COLOR_BLACK
)
709 rcu_rbtree_remove_fixup(root
, x
, rballoc
, rbfree
);
711 * Commit all _STORE_SHARED().