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.
40 #include <urcu/rcurbtree.h>
41 #include <urcu-pointer.h>
42 #include <urcu-call-rcu.h>
43 #include <urcu/compiler.h>
46 * Explanation of next/prev walk coherency and search coherency when
47 * performed concurrently with updates.
49 * next/prev walk coherency with respect to concurrent updates:
51 * There are 3 scenarios for which we need to model and validate this:
52 * rotation, transplant and "teleportation" (the latter being a remote
53 * transplant in a remove non-nil case).
55 * - rotation left (right is symmetric)
56 * xl and yr point to the same parent nodes before/after left
57 * rotation. yll and ylr also point to the same parent node
58 * before/after left rotation.
59 * As we are copying x, y and yl (the 3 nodes which parent/child
60 * relationship are changed) to "new" version of this node cluster,
61 * all external references to the cluster either point to the old
62 * cluster or the new one. If we take this cluster as a "black box"
63 * from the point of view of next/prev traversal, all we have to
64 * ensure is that the old and the new cluster behave in the exact same
65 * way with respect to traversal order.
68 * In this operation, we transplant a copy of "v" into its parent
69 * location (u), thus replacing it. The children of "v", vl and vr,
70 * still point to v (new version) after the transplant, so it does not
71 * change the behavior when considering the next/prev traversal. "v"
72 * being copied to a new version ensures that the parent pointers of v
73 * are pointing to its new parent (parent of u) before it is published
74 * to readers (by setting the child pointer of u's parent to the new
78 * This one is probably the most tricky and will require some ascii
81 * We want to remove z from this tree:
99 * What we are going to do is to "teleport" y into z's location,
100 * reparenting yr to b. We are taking care to create a new cluster
101 * copy that is isolated from any reader. We will represent the new
102 * members of the cluster with capital letters.
118 * In this transient state, we notice that the pointers within the
119 * cluster all point to the new cluster nodes, and they point to the
120 * correct external nodes. However, no external pointer point to the
121 * cluster (yet). The first pointer to point to this cluster will be
122 * "zp->right". It will therefore make the cluster visible for search.
124 * In this intermediate state, we can walk through the new cluster
125 * when coming from the top (in a next/prev traversal), but can come
126 * back to the old cluster when going back up from the children nodes.
127 * All we have to ensure is that the two clusters, taken as a black
128 * box from a next/prev traversal perspective, yield to the exact same
131 * Search coherency with concurrent updates:
133 * Simple "search" (only going down the tree) is also handled by this
134 * cluster scheme. The explanation is a subset of the prev/next
135 * explanation, where we don't have to care about the intermediate
136 * stages where the children point to the old cluster, because we only
137 * ever use the top level pointers to go down into the children nodes,
138 * we never go back up. So by simply making sure that all the cluster
139 * internal nodes pointers are setup correctly before making the
140 * cluster visible to the readers (by setting the parent pointer to
141 * the topmost new node in the cluster), we are sure that readers will
142 * see a coherent view of the cluster at all times.
146 #define dbg_printf(args...) printf(args)
147 #define dbg_usleep(usecs) usleep(usecs)
149 #define dbg_printf(args...)
150 #define dbg_usleep(usecs)
154 * Undefine this to enable the non-RCU rotate and transplant functions
155 * (for debugging). Note that these versions don't support the tree
156 * max_end updates, so lookups must be performed with
157 * rcu_rbtree_search_begin_key when using this debug facility.
159 #define RBTREE_RCU_SUPPORT_ROTATE_LEFT
160 #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
161 #define RBTREE_RCU_SUPPORT_TRANSPLANT
162 #define RBTREE_RCU_SUPPORT
164 #ifdef RBTREE_RCU_SUPPORT
165 #define c_rcu_dereference(x) rcu_dereference(x)
166 #define c_cmm_smp_wmb() cmm_smp_wmb()
167 #define c_cmm_smp_wmc() cmm_smp_wmc()
168 #define C_CMM_STORE_SHARED(x, v) CMM_STORE_SHARED(x, v)
169 #define C__CMM_STORE_SHARED(x, v) _CMM_STORE_SHARED(x, v)
171 #define c_rcu_dereference(x) (x)
172 #define c_cmm_smp_wmb()
173 #define c_cmm_smp_wmc()
174 #define C_CMM_STORE_SHARED(x, v) ((x) = (v))
175 #define C__CMM_STORE_SHARED(x, v) ((x) = (v))
179 * Add internal mutex locking within the RBTree, for debugging. Enable this
180 * define and add mutexes to RCU readers to debug races with with rotation or
183 /* #define RBTREE_INTERNAL_LOCKING */
185 #ifdef RBTREE_INTERNAL_LOCKING
186 static pthread_mutex_t test_mutex
= PTHREAD_MUTEX_INITIALIZER
;
187 static pthread_mutex_t outer_mutex
= PTHREAD_MUTEX_INITIALIZER
;
190 void lock_outer_mutex(void)
192 pthread_mutex_lock(&outer_mutex
);
196 void unlock_outer_mutex(void)
198 pthread_mutex_unlock(&outer_mutex
);
202 void lock_test_mutex(void)
204 pthread_mutex_lock(&test_mutex
);
208 void unlock_test_mutex(void)
210 pthread_mutex_unlock(&test_mutex
);
214 void lock_outer_mutex(void)
219 void unlock_outer_mutex(void)
224 void lock_test_mutex(void)
229 void unlock_test_mutex(void)
235 void set_parent(struct rcu_rbtree_node
*node
,
236 struct rcu_rbtree_node
*parent
,
239 C__CMM_STORE_SHARED(node
->parent
, ((unsigned long) parent
) | pos
);
243 struct rcu_rbtree_node
*get_parent(struct rcu_rbtree_node
*node
)
245 return (struct rcu_rbtree_node
*) (node
->parent
& ~1UL);
249 unsigned int get_pos(struct rcu_rbtree_node
*node
)
251 return (unsigned int) (node
->parent
& 1UL);
255 struct rcu_rbtree_node
*get_parent_and_pos(struct rcu_rbtree_node
*node
,
258 unsigned long parent_pos
= c_rcu_dereference(node
->parent
);
260 *pos
= (unsigned int) (parent_pos
& 1UL);
261 return (struct rcu_rbtree_node
*) (parent_pos
& ~1UL);
265 void set_decay(struct rcu_rbtree_node
*x
, struct rcu_rbtree_node
*xc
)
271 struct rcu_rbtree_node
*get_decay(struct rcu_rbtree_node
*x
)
275 while (x
->decay_next
)
281 struct rcu_rbtree_node
*is_decay(struct rcu_rbtree_node
*x
)
283 return x
->decay_next
;
287 struct rcu_rbtree_node
*_rcu_rbtree_alloc_node(struct rcu_rbtree
*rbtree
)
289 return rbtree
->rballoc(sizeof(struct rcu_rbtree_node
));
293 void _rcu_rbtree_free_node(struct rcu_head
*head
)
295 struct rcu_rbtree_node
*node
=
296 caa_container_of(head
, struct rcu_rbtree_node
, head
);
297 node
->rbtree
->rbfree(node
);
300 #ifdef RBTREE_RCU_SUPPORT
303 struct rcu_rbtree_node
*dup_decay_node(struct rcu_rbtree
*rbtree
,
304 struct rcu_rbtree_node
*x
)
306 struct rcu_rbtree_node
*xc
;
308 if (rcu_rbtree_is_nil(rbtree
, x
))
311 xc
= _rcu_rbtree_alloc_node(rbtree
);
312 memcpy(xc
, x
, sizeof(*xc
));
313 xc
->decay_next
= NULL
;
315 rbtree
->call_rcu(&x
->head
, _rcu_rbtree_free_node
);
319 #else /* RBTREE_RCU_SUPPORT */
322 struct rcu_rbtree_node
*dup_decay_node(struct rcu_rbtree
*rbtree
,
323 struct rcu_rbtree_node
*x
)
331 * Info for range lookups:
332 * Range lookup information is only valid when used when searching for
333 * ranges. It should never be used in next/prev traversal because the
334 * pointers to parents are not in sync with the parent vision of the
338 void set_left(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
,
339 struct rcu_rbtree_node
*left
)
345 void set_right(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
,
346 struct rcu_rbtree_node
*right
)
348 node
->_right
= right
;
352 void *calculate_node_max_end(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
)
357 if (!rcu_rbtree_is_nil(rbtree
, node
->_right
)) {
358 if (rbtree
->comp(max_end
, node
->_right
->max_end
) < 0)
359 max_end
= node
->_right
->max_end
;
361 if (!rcu_rbtree_is_nil(rbtree
, node
->_left
)) {
362 if (rbtree
->comp(max_end
, node
->_left
->max_end
) < 0)
363 max_end
= node
->_left
->max_end
;
370 * Deal with memory allocation errors.
371 * Can be ensured by reserving a pool of memory entries before doing the
372 * insertion, which will have to be function of number of
373 * transplantations/rotations required for the operation (which is a
374 * multiple of the tree height).
379 void show_tree(struct rcu_rbtree
*rbtree
)
381 struct rcu_rbtree_node
*node
;
383 node
= rcu_rbtree_min(rbtree
, rbtree
->root
);
384 while (!rcu_rbtree_is_nil(rbtree
, node
)) {
385 assert(!is_decay(node
));
386 printf("{ b:%lX e:%lX pb: %lX r:%lX l:%lX %s %s %s} ",
387 (unsigned long) node
->begin
,
388 (unsigned long) node
->end
,
389 (unsigned long) get_parent(node
)->begin
,
390 (unsigned long) node
->_right
->begin
,
391 (unsigned long) node
->_left
->begin
,
392 node
->color
? "red" : "black",
393 get_pos(node
) ? "right" : "left",
394 rcu_rbtree_is_nil(rbtree
, node
) ? "nil" : "");
395 node
= rcu_rbtree_next(rbtree
, node
);
400 #define check_max_end(rbtree, x) \
402 if (rcu_rbtree_is_nil(rbtree, x)) \
404 assert(rbtree->comp(x->max_end, \
405 calculate_node_max_end(rbtree, x)) == 0); \
410 void show_tree(struct rcu_rbtree
*rbtree
)
415 void check_max_end(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*x
)
421 struct rcu_rbtree_node
*make_nil(struct rcu_rbtree
*rbtree
)
423 return &rbtree
->nil_node
;
427 * Iterative rbtree search.
429 struct rcu_rbtree_node
*rcu_rbtree_search(struct rcu_rbtree
*rbtree
,
430 struct rcu_rbtree_node
*x
,
433 struct rcu_rbtree_node
*xl
;
435 dbg_printf("searching point 0x%lx\n", (unsigned long) point
);
436 x
= c_rcu_dereference(x
);
438 while (!rcu_rbtree_is_nil(rbtree
, x
)) {
440 xl
= c_rcu_dereference(x
->_left
);
441 dbg_printf("search x %lx x_end %lx x_max_end %lx\n", (unsigned long) x
->begin
,
442 (unsigned long) x
->end
, (unsigned long) x
->max_end
);
443 dbg_printf("search xl %lx xl_end %lx xl_max_end %lx\n", (unsigned long) xl
->begin
,
444 (unsigned long) xl
->end
, (unsigned long) xl
->max_end
);
445 if (!rcu_rbtree_is_nil(rbtree
, xl
)
446 && (rbtree
->comp(xl
->max_end
, point
) > 0)) {
447 dbg_printf("go left\n");
449 } else if (rbtree
->comp(x
->begin
, point
) <= 0
450 && rbtree
->comp(point
, x
->end
) < 0) {
451 dbg_printf("got it!\n");
453 } else if (rbtree
->comp(point
, x
->begin
) > 0) {
454 dbg_printf("go right\n");
455 x
= c_rcu_dereference(x
->_right
);
457 dbg_printf("not found!\n");
458 x
= make_nil(rbtree
);
461 if (rcu_rbtree_is_nil(rbtree
, x
))
462 dbg_printf("Reached bottom of tree.\n");
467 struct rcu_rbtree_node
*rcu_rbtree_search_range(struct rcu_rbtree
*rbtree
,
468 struct rcu_rbtree_node
*x
,
469 void *begin
, void *end
)
471 struct rcu_rbtree_node
*node
;
473 node
= rcu_rbtree_search(rbtree
, x
, begin
);
474 if (rcu_rbtree_is_nil(rbtree
, node
))
476 if (rbtree
->comp(node
->end
, end
) < 0)
477 return NULL
; /* High is outside lookup range */
482 * Search by exact range start value.
484 struct rcu_rbtree_node
*rcu_rbtree_search_begin_key(struct rcu_rbtree
*rbtree
,
485 struct rcu_rbtree_node
*x
,
488 x
= c_rcu_dereference(x
);
491 while (!rcu_rbtree_is_nil(rbtree
, x
) && (comp
= rbtree
->comp(k
, x
->begin
)) != 0) {
494 x
= c_rcu_dereference(x
->_left
);
496 x
= c_rcu_dereference(x
->_right
);
502 struct rcu_rbtree_node
*rcu_rbtree_min_dup_decay(struct rcu_rbtree
*rbtree
,
503 struct rcu_rbtree_node
*x
,
504 struct rcu_rbtree_node
**zr
)
506 struct rcu_rbtree_node
*xl
;
508 x
= c_rcu_dereference(x
);
510 if (rcu_rbtree_is_nil(rbtree
, x
)) {
514 *zr
= x
= dup_decay_node(rbtree
, x
);
516 while (!rcu_rbtree_is_nil(rbtree
, xl
= c_rcu_dereference(x
->_left
))) {
517 x
= dup_decay_node(rbtree
, xl
);
518 set_parent(x
, get_decay(get_parent(x
)), get_pos(x
));
519 get_parent(x
)->_left
= get_decay(get_parent(x
)->_left
);
525 struct rcu_rbtree_node
*rcu_rbtree_min_update_decay(struct rcu_rbtree
*rbtree
,
526 struct rcu_rbtree_node
*x
)
528 struct rcu_rbtree_node
*xl
;
530 x
= c_rcu_dereference(x
);
532 if (rcu_rbtree_is_nil(rbtree
, x
))
535 set_parent(x
->_right
, get_decay(get_parent(x
->_right
)),
537 set_parent(x
->_left
, get_decay(get_parent(x
->_left
)),
541 while (!rcu_rbtree_is_nil(rbtree
, xl
= c_rcu_dereference(x
->_left
))) {
543 set_parent(x
->_right
, get_decay(get_parent(x
->_right
)),
545 set_parent(x
->_left
, get_decay(get_parent(x
->_left
)),
551 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree
*rbtree
,
552 struct rcu_rbtree_node
*x
)
554 struct rcu_rbtree_node
*xl
;
556 x
= c_rcu_dereference(x
);
558 if (rcu_rbtree_is_nil(rbtree
, x
))
561 while (!rcu_rbtree_is_nil(rbtree
, xl
= c_rcu_dereference(x
->_left
)))
566 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree
*rbtree
,
567 struct rcu_rbtree_node
*x
)
569 struct rcu_rbtree_node
*xr
;
571 x
= c_rcu_dereference(x
);
573 if (rcu_rbtree_is_nil(rbtree
, x
))
576 while (!rcu_rbtree_is_nil(rbtree
, xr
= c_rcu_dereference(x
->_right
)))
582 * RCU read lock must be held across the next/prev calls to ensure validity of
585 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree
*rbtree
,
586 struct rcu_rbtree_node
*x
)
588 struct rcu_rbtree_node
*xr
, *y
;
591 x
= c_rcu_dereference(x
);
593 if (!rcu_rbtree_is_nil(rbtree
, xr
= c_rcu_dereference(x
->_right
)))
594 return rcu_rbtree_min(rbtree
, xr
);
595 y
= get_parent_and_pos(x
, &x_pos
);
596 while (!rcu_rbtree_is_nil(rbtree
, y
) && x_pos
== IS_RIGHT
) {
598 y
= get_parent_and_pos(y
, &x_pos
);
603 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree
*rbtree
,
604 struct rcu_rbtree_node
*x
)
606 struct rcu_rbtree_node
*xl
, *y
;
609 x
= c_rcu_dereference(x
);
611 if (!rcu_rbtree_is_nil(rbtree
, xl
= c_rcu_dereference(x
->_left
)))
612 return rcu_rbtree_max(rbtree
, xl
);
613 y
= get_parent_and_pos(x
, &x_pos
);
614 while (!rcu_rbtree_is_nil(rbtree
, y
) && x_pos
== IS_LEFT
) {
616 y
= get_parent_and_pos(y
, &x_pos
);
622 * "node" needs to be non-visible by readers.
625 void populate_node_end(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
,
626 unsigned int copy_parents
, struct rcu_rbtree_node
*stop
)
628 struct rcu_rbtree_node
*prev
= NULL
, *orig_node
= node
, *top
;
634 assert(!rcu_rbtree_is_nil(rbtree
, node
));
636 if (prev
&& copy_parents
) {
637 node
= dup_decay_node(rbtree
, node
);
638 if (get_pos(prev
) == IS_RIGHT
)
642 set_parent(prev
, node
, get_pos(prev
));
645 max_end
= calculate_node_max_end(rbtree
, node
);
647 * Compare the node max_end keys to make sure we replace
648 * references to a key belonging to a node we remove
649 * from the tree. Otherwise we would still be using this
650 * pointer as an invalid reference after garbage
651 * collection of the node and of its associated
652 * begin/end pointers.
654 if (max_end
!= node
->max_end
) {
655 node
->max_end
= max_end
;
657 top
= get_parent(node
);
658 c_cmm_smp_wmb(); /* write into node before publish */
659 /* make new branch visible to readers */
660 if (rcu_rbtree_is_nil(rbtree
, top
))
661 C__CMM_STORE_SHARED(rbtree
->root
, node
);
662 if (get_pos(node
) == IS_LEFT
)
663 C__CMM_STORE_SHARED(top
->_left
, node
);
665 C__CMM_STORE_SHARED(top
->_right
, node
);
669 /* Check for propagation stop */
674 node
= get_parent(node
);
675 } while (!rcu_rbtree_is_nil(rbtree
, node
));
677 top
= node
; /* nil */
678 c_cmm_smp_wmb(); /* write into node before publish */
679 /* make new branch visible to readers */
680 C__CMM_STORE_SHARED(rbtree
->root
, prev
);
685 /* update children */
688 assert(!rcu_rbtree_is_nil(rbtree
, node
));
689 set_parent(node
->_left
, get_decay(get_parent(node
->_left
)), IS_LEFT
);
690 set_parent(node
->_right
, get_decay(get_parent(node
->_right
)), IS_RIGHT
);
691 } while ((node
= get_parent(node
)) != top
);
695 * We have to ensure these assumptions are correct for prev/next
698 * with x being a right child, the assumption that:
699 * get_parent(x)->_right == x
700 * or if x is a left child, the assumption that:
701 * get_parent(x)->_left == x
703 * This explains why we have to allocate a vc copy of the node for left_rotate,
704 * right_rotate and transplant operations.
706 * We always ensure that the right/left child and correct parent is set in the
707 * node copies *before* we reparent the children and make the upper-level point
711 /* RCU: copy x and y, atomically point to new versions. GC old. */
712 /* Should be eventually followed by a cmm_smp_wmc() */
714 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
717 void left_rotate(struct rcu_rbtree
*rbtree
,
718 struct rcu_rbtree_node
*x
)
720 struct rcu_rbtree_node
*y
, *y_left
;
722 dbg_printf("left rotate %lx\n", (unsigned long) x
->begin
);
727 /* Now operate on new copy, decay old versions */
728 x
= dup_decay_node(rbtree
, x
);
729 y
= dup_decay_node(rbtree
, y
);
730 y_left
= dup_decay_node(rbtree
, y_left
);
732 check_max_end(rbtree
, get_parent(x
));
733 check_max_end(rbtree
, x
);
734 check_max_end(rbtree
, y
);
736 /* Internal node modifications */
737 set_parent(y
, get_parent(x
), get_pos(x
));
738 set_parent(x
, y
, IS_LEFT
);
739 set_left(rbtree
, y
, x
);
740 set_right(rbtree
, x
, y_left
);
742 if (!rcu_rbtree_is_nil(rbtree
, y_left
))
743 set_parent(y_left
, x
, IS_RIGHT
);
746 * We only changed the relative position of x and y wrt their
747 * children, and reparented y (but are keeping the same nodes in
748 * place, so its parent does not need to have end value
751 x
->max_end
= calculate_node_max_end(rbtree
, x
);
752 y
->max_end
= calculate_node_max_end(rbtree
, y
);
754 c_cmm_smp_wmb(); /* write into node before publish */
756 /* External references update (visible by readers) */
757 if (rcu_rbtree_is_nil(rbtree
, get_parent(y
)))
758 C__CMM_STORE_SHARED(rbtree
->root
, y
);
759 else if (get_pos(y
) == IS_LEFT
)
760 C__CMM_STORE_SHARED(get_parent(y
)->_left
, y
);
762 C__CMM_STORE_SHARED(get_parent(y
)->_right
, y
);
764 /* Point children to new copy (parent only used by updates/next/prev) */
765 set_parent(x
->_left
, get_decay(get_parent(x
->_left
)),
767 set_parent(y
->_right
, get_decay(get_parent(y
->_right
)),
769 if (!rcu_rbtree_is_nil(rbtree
, y_left
)) {
770 set_parent(y_left
->_right
,
771 get_decay(get_parent(y_left
->_right
)),
772 get_pos(y_left
->_right
));
773 set_parent(y_left
->_left
,
774 get_decay(get_parent(y_left
->_left
)),
775 get_pos(y_left
->_left
));
779 assert(y
== rbtree
->root
|| get_parent(y
)->_left
== y
780 || get_parent(y
)->_right
== y
);
781 assert(x
== rbtree
->root
|| get_parent(x
)->_left
== x
782 || get_parent(x
)->_right
== x
);
783 assert(rcu_rbtree_is_nil(rbtree
, x
->_right
) || get_parent(x
->_right
) == x
);
784 assert(rcu_rbtree_is_nil(rbtree
, x
->_left
) || get_parent(x
->_left
) == x
);
785 assert(rcu_rbtree_is_nil(rbtree
, y
->_right
) || get_parent(y
->_right
) == y
);
786 assert(rcu_rbtree_is_nil(rbtree
, y
->_left
) || get_parent(y
->_left
) == y
);
787 assert(!is_decay(rbtree
->root
));
788 assert(!is_decay(x
));
789 assert(!is_decay(y
));
790 assert(!is_decay(x
->_right
));
791 assert(!is_decay(x
->_left
));
792 assert(!is_decay(y
->_right
));
793 assert(!is_decay(y
->_left
));
794 check_max_end(rbtree
, get_parent(y
));
795 check_max_end(rbtree
, x
);
796 check_max_end(rbtree
, y
);
801 /* non-rcu version */
803 void left_rotate(struct rcu_rbtree
*rbtree
,
804 struct rcu_rbtree_node
*x
)
806 struct rcu_rbtree_node
*y
;
810 x
->_right
= y
->_left
;
811 if (!rcu_rbtree_is_nil(rbtree
, y
->_left
))
812 set_parent(y
->_left
, x
, IS_RIGHT
);
813 set_parent(y
, get_parent(x
), get_pos(x
));
814 if (rcu_rbtree_is_nil(rbtree
, get_parent(x
)))
816 else if (x
== get_parent(x
)->_left
) {
817 get_parent(x
)->_left
= y
;
819 get_parent(x
)->_right
= y
;
822 set_parent(x
, y
, IS_LEFT
);
825 * We only changed the relative position of x and y wrt their
826 * children, and reparented y (but are keeping the same nodes in
827 * place, so its parent does not need to have end value
830 x
->max_end
= calculate_node_max_end(rbtree
, x
);
831 y
->max_end
= calculate_node_max_end(rbtree
, y
);
838 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
840 void right_rotate(struct rcu_rbtree
*rbtree
,
841 struct rcu_rbtree_node
*x
)
843 struct rcu_rbtree_node
*y
, *y_right
;
845 dbg_printf("right rotate %lx\n", (unsigned long) x
->begin
);
850 /* Now operate on new copy, decay old versions */
851 x
= dup_decay_node(rbtree
, x
);
852 y
= dup_decay_node(rbtree
, y
);
853 y_right
= dup_decay_node(rbtree
, y_right
);
855 check_max_end(rbtree
, get_parent(x
));
856 check_max_end(rbtree
, x
);
857 check_max_end(rbtree
, y
);
859 /* Internal node modifications */
860 set_parent(y
, get_parent(x
), get_pos(x
));
861 set_parent(x
, y
, IS_RIGHT
);
862 set_right(rbtree
, y
, x
);
863 set_left(rbtree
, x
, y_right
);
865 if (!rcu_rbtree_is_nil(rbtree
, y_right
))
866 set_parent(y_right
, x
, IS_LEFT
);
869 * We only changed the relative position of x and y wrt their
870 * children, and reparented y (but are keeping the same nodes in
871 * place, so its parent does not need to have end value
874 x
->max_end
= calculate_node_max_end(rbtree
, x
);
875 y
->max_end
= calculate_node_max_end(rbtree
, y
);
877 c_cmm_smp_wmb(); /* write into node before publish */
879 /* External references update (visible by readers) */
880 if (rcu_rbtree_is_nil(rbtree
, get_parent(y
)))
881 C__CMM_STORE_SHARED(rbtree
->root
, y
);
882 else if (get_pos(y
) == IS_RIGHT
)
883 C__CMM_STORE_SHARED(get_parent(y
)->_right
, y
);
885 C__CMM_STORE_SHARED(get_parent(y
)->_left
, y
);
887 /* Point children to new copy (parent only used by updates/next/prev) */
888 set_parent(x
->_right
, get_decay(get_parent(x
->_right
)),
890 set_parent(y
->_left
, get_decay(get_parent(y
->_left
)),
892 if (!rcu_rbtree_is_nil(rbtree
, y_right
)) {
893 set_parent(y_right
->_left
,
894 get_decay(get_parent(y_right
->_left
)),
895 get_pos(y_right
->_left
));
896 set_parent(y_right
->_right
,
897 get_decay(get_parent(y_right
->_right
)),
898 get_pos(y_right
->_right
));
902 assert(y
== rbtree
->root
|| get_parent(y
)->_right
== y
903 || get_parent(y
)->_left
== y
);
904 assert(x
== rbtree
->root
|| get_parent(x
)->_right
== x
905 || get_parent(x
)->_left
== x
);
906 assert(rcu_rbtree_is_nil(rbtree
, x
->_left
) || get_parent(x
->_left
) == x
);
907 assert(rcu_rbtree_is_nil(rbtree
, x
->_right
) || get_parent(x
->_right
) == x
);
908 assert(rcu_rbtree_is_nil(rbtree
, y
->_left
) || get_parent(y
->_left
) == y
);
909 assert(rcu_rbtree_is_nil(rbtree
, y
->_right
) || get_parent(y
->_right
) == y
);
910 assert(!is_decay(rbtree
->root
));
911 assert(!is_decay(x
));
912 assert(!is_decay(y
));
913 assert(!is_decay(x
->_left
));
914 assert(!is_decay(x
->_right
));
915 assert(!is_decay(y
->_left
));
916 assert(!is_decay(y
->_right
));
917 check_max_end(rbtree
, x
);
918 check_max_end(rbtree
, y
);
919 check_max_end(rbtree
, get_parent(y
));
924 /* non-rcu version */
926 void right_rotate(struct rcu_rbtree
*rbtree
,
927 struct rcu_rbtree_node
*x
)
929 struct rcu_rbtree_node
*y
;
933 x
->_left
= y
->_right
;
934 if (!rcu_rbtree_is_nil(rbtree
, y
->_right
))
935 set_parent(y
->_right
, x
, IS_LEFT
);
936 set_parent(y
, get_parent(x
), get_pos(x
));
937 if (rcu_rbtree_is_nil(rbtree
, get_parent(x
)))
939 else if (x
== get_parent(x
)->_right
) {
940 get_parent(x
)->_right
= y
;
942 get_parent(x
)->_left
= y
;
945 set_parent(x
, y
, IS_RIGHT
);
948 * We only changed the relative position of x and y wrt their
949 * children, and reparented y (but are keeping the same nodes in
950 * place, so its parent does not need to have end value
953 x
->max_end
= calculate_node_max_end(rbtree
, x
);
954 y
->max_end
= calculate_node_max_end(rbtree
, y
);
961 static void rcu_rbtree_insert_fixup(struct rcu_rbtree
*rbtree
,
962 struct rcu_rbtree_node
*z
)
964 struct rcu_rbtree_node
*y
;
966 dbg_printf("insert fixup %p\n", z
->begin
);
967 assert(!is_decay(rbtree
->root
));
969 while (get_parent(z
)->color
== COLOR_RED
) {
970 if (get_parent(z
) == get_parent(get_parent(z
))->_left
) {
971 y
= get_parent(get_parent(z
))->_right
;
972 if (y
->color
== COLOR_RED
) {
973 get_parent(z
)->color
= COLOR_BLACK
;
974 y
->color
= COLOR_BLACK
;
975 get_parent(get_parent(z
))->color
= COLOR_RED
;
976 z
= get_parent(get_parent(z
));
978 if (z
== get_parent(z
)->_right
) {
980 left_rotate(rbtree
, z
);
982 assert(!is_decay(rbtree
->root
));
984 get_parent(z
)->color
= COLOR_BLACK
;
985 get_parent(get_parent(z
))->color
= COLOR_RED
;
986 assert(!is_decay(z
));
987 assert(!is_decay(get_parent(z
)));
988 assert(!is_decay(get_parent(get_parent(z
))));
989 right_rotate(rbtree
, get_parent(get_parent(z
)));
990 assert(!is_decay(z
));
991 assert(!is_decay(rbtree
->root
));
994 y
= get_parent(get_parent(z
))->_left
;
995 if (y
->color
== COLOR_RED
) {
996 get_parent(z
)->color
= COLOR_BLACK
;
997 y
->color
= COLOR_BLACK
;
998 get_parent(get_parent(z
))->color
= COLOR_RED
;
999 z
= get_parent(get_parent(z
));
1001 if (z
== get_parent(z
)->_left
) {
1003 right_rotate(rbtree
, z
);
1005 assert(!is_decay(rbtree
->root
));
1007 get_parent(z
)->color
= COLOR_BLACK
;
1008 get_parent(get_parent(z
))->color
= COLOR_RED
;
1009 left_rotate(rbtree
, get_parent(get_parent(z
)));
1010 assert(!is_decay(z
));
1011 assert(!is_decay(rbtree
->root
));
1015 rbtree
->root
->color
= COLOR_BLACK
;
1019 * rcu_rbtree_insert - Insert a node in the RCU rbtree
1021 * Returns 0 on success, or < 0 on error.
1023 int rcu_rbtree_insert(struct rcu_rbtree
*rbtree
,
1024 void *begin
, void *end
)
1026 struct rcu_rbtree_node
*x
, *y
, *z
;
1028 z
= _rcu_rbtree_alloc_node(rbtree
);
1034 dbg_printf("insert %p\n", z
->begin
);
1035 assert(!is_decay(rbtree
->root
));
1037 y
= make_nil(rbtree
);
1039 while (!rcu_rbtree_is_nil(rbtree
, x
)) {
1041 if (rbtree
->comp(z
->begin
, x
->begin
) < 0)
1047 z
->_left
= make_nil(rbtree
);
1048 z
->_right
= make_nil(rbtree
);
1049 z
->color
= COLOR_RED
;
1050 z
->decay_next
= NULL
;
1051 z
->max_end
= z
->end
;
1054 if (rcu_rbtree_is_nil(rbtree
, y
)) {
1055 set_parent(z
, y
, IS_RIGHT
); /* pos arbitrary for root node */
1057 * Order stores to z (children/parents) before stores
1058 * that will make it visible to the rest of the tree.
1061 C__CMM_STORE_SHARED(rbtree
->root
, z
);
1062 } else if (rbtree
->comp(z
->begin
, y
->begin
) < 0) {
1063 y
= dup_decay_node(rbtree
, y
);
1064 set_parent(z
, y
, IS_LEFT
);
1065 if (get_pos(z
) == IS_LEFT
)
1066 C__CMM_STORE_SHARED(y
->_left
, z
);
1068 C__CMM_STORE_SHARED(y
->_right
, z
);
1069 populate_node_end(rbtree
, y
, 1, NULL
);
1071 y
= dup_decay_node(rbtree
, y
);
1072 set_parent(z
, y
, IS_RIGHT
);
1073 if (get_pos(z
) == IS_LEFT
)
1074 C__CMM_STORE_SHARED(y
->_left
, z
);
1076 C__CMM_STORE_SHARED(y
->_right
, z
);
1077 populate_node_end(rbtree
, y
, 1, NULL
);
1079 rcu_rbtree_insert_fixup(rbtree
, z
);
1081 * Make sure to commit all C__CMM_STORE_SHARED() for non-coherent caches.
1085 check_max_end(rbtree
, z
);
1086 check_max_end(rbtree
, y
);
1092 * Transplant v into u position.
1095 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
1098 void rcu_rbtree_transplant(struct rcu_rbtree
*rbtree
,
1099 struct rcu_rbtree_node
*u
,
1100 struct rcu_rbtree_node
*v
,
1101 unsigned int copy_parents
,
1102 struct rcu_rbtree_node
*stop
)
1104 dbg_printf("transplant %p\n", v
->begin
);
1106 if (!rcu_rbtree_is_nil(rbtree
, v
))
1107 v
= dup_decay_node(rbtree
, v
);
1109 if (rcu_rbtree_is_nil(rbtree
, get_parent(u
))) {
1110 /* pos is arbitrary for root node */
1111 set_parent(v
, get_parent(u
), IS_RIGHT
);
1112 c_cmm_smp_wmb(); /* write into node before publish */
1113 C__CMM_STORE_SHARED(rbtree
->root
, v
);
1115 struct rcu_rbtree_node
*vp
;
1119 vp
= dup_decay_node(rbtree
, vp
);
1120 set_parent(v
, vp
, get_pos(u
));
1121 if (get_pos(v
) == IS_LEFT
)
1122 C__CMM_STORE_SHARED(vp
->_left
, v
);
1124 C__CMM_STORE_SHARED(vp
->_right
, v
);
1125 populate_node_end(rbtree
, vp
, copy_parents
, stop
);
1126 check_max_end(rbtree
, vp
);
1129 /* Point children to new copy (parent only used by updates/next/prev) */
1130 if (!rcu_rbtree_is_nil(rbtree
, v
)) {
1131 set_parent(v
->_right
, get_decay(get_parent(v
->_right
)),
1132 get_pos(v
->_right
));
1133 set_parent(v
->_left
, get_decay(get_parent(v
->_left
)),
1136 assert(!is_decay(rbtree
->root
));
1137 check_max_end(rbtree
, v
);
1142 /* Non-RCU version */
1144 void rcu_rbtree_transplant(struct rcu_rbtree
*rbtree
,
1145 struct rcu_rbtree_node
*u
,
1146 struct rcu_rbtree_node
*v
,
1147 unsigned int copy_parents
,
1148 struct rcu_rbtree_node
*stop
)
1150 dbg_printf("transplant %p\n", v
->begin
);
1153 if (rcu_rbtree_is_nil(rbtree
, get_parent(u
))) {
1156 if (u
== get_parent(u
)->_left
)
1157 get_parent(u
)->_left
= v
;
1159 get_parent(u
)->_right
= v
;
1160 populate_node_end(rbtree
, get_parent(u
), copy_parents
, stop
);
1162 set_parent(v
, get_parent(u
), get_pos(u
));
1163 unlock_test_mutex();
1168 static void rcu_rbtree_remove_fixup(struct rcu_rbtree
*rbtree
,
1169 struct rcu_rbtree_node
*x
)
1171 dbg_printf("remove fixup %p\n", x
->begin
);
1173 while (x
!= rbtree
->root
&& x
->color
== COLOR_BLACK
) {
1174 assert(!is_decay(get_parent(x
)));
1175 assert(!is_decay(get_parent(x
)->_left
));
1176 if (x
== get_parent(x
)->_left
) {
1177 struct rcu_rbtree_node
*w
;
1179 w
= get_parent(x
)->_right
;
1181 if (w
->color
== COLOR_RED
) {
1182 w
->color
= COLOR_BLACK
;
1183 get_parent(x
)->color
= COLOR_RED
;
1184 left_rotate(rbtree
, get_parent(x
));
1186 assert(!is_decay(rbtree
->root
));
1187 w
= get_parent(x
)->_right
;
1189 if (w
->_left
->color
== COLOR_BLACK
1190 && w
->_right
->color
== COLOR_BLACK
) {
1191 w
->color
= COLOR_RED
;
1193 assert(!is_decay(rbtree
->root
));
1194 assert(!is_decay(x
));
1196 if (w
->_right
->color
== COLOR_BLACK
) {
1197 w
->_left
->color
= COLOR_BLACK
;
1198 w
->color
= COLOR_RED
;
1199 right_rotate(rbtree
, w
);
1200 assert(!is_decay(rbtree
->root
));
1202 w
= get_parent(x
)->_right
;
1204 w
->color
= get_parent(x
)->color
;
1205 get_parent(x
)->color
= COLOR_BLACK
;
1206 w
->_right
->color
= COLOR_BLACK
;
1207 left_rotate(rbtree
, get_parent(x
));
1208 assert(!is_decay(rbtree
->root
));
1212 struct rcu_rbtree_node
*w
;
1214 w
= get_parent(x
)->_left
;
1216 if (w
->color
== COLOR_RED
) {
1217 w
->color
= COLOR_BLACK
;
1218 get_parent(x
)->color
= COLOR_RED
;
1219 right_rotate(rbtree
, get_parent(x
));
1220 assert(!is_decay(rbtree
->root
));
1222 w
= get_parent(x
)->_left
;
1224 if (w
->_right
->color
== COLOR_BLACK
1225 && w
->_left
->color
== COLOR_BLACK
) {
1226 w
->color
= COLOR_RED
;
1228 assert(!is_decay(rbtree
->root
));
1229 assert(!is_decay(x
));
1231 if (w
->_left
->color
== COLOR_BLACK
) {
1232 w
->_right
->color
= COLOR_BLACK
;
1233 w
->color
= COLOR_RED
;
1234 left_rotate(rbtree
, w
);
1235 assert(!is_decay(rbtree
->root
));
1237 w
= get_parent(x
)->_left
;
1239 w
->color
= get_parent(x
)->color
;
1240 get_parent(x
)->color
= COLOR_BLACK
;
1241 w
->_left
->color
= COLOR_BLACK
;
1242 right_rotate(rbtree
, get_parent(x
));
1243 assert(!is_decay(rbtree
->root
));
1248 x
->color
= COLOR_BLACK
;
1252 * Delete z. All non-copied children left/right positions are unchanged.
1255 void rcu_rbtree_remove_nonil(struct rcu_rbtree
*rbtree
,
1256 struct rcu_rbtree_node
*z
,
1257 struct rcu_rbtree_node
*y
)
1259 struct rcu_rbtree_node
*x
;
1261 dbg_printf("remove nonil %p\n", z
->begin
);
1264 assert(!is_decay(z
));
1265 assert(!is_decay(y
));
1266 assert(!is_decay(y
->_right
));
1267 assert(!is_decay(get_parent(y
)));
1269 assert(!is_decay(x
));
1270 if (get_parent(y
) == z
) {
1271 y
= dup_decay_node(rbtree
, y
);
1272 set_parent(x
, y
, get_pos(x
)); /* parent for nil */
1273 /* y is z's right node */
1274 set_left(rbtree
, y
, z
->_left
);
1275 y
->max_end
= calculate_node_max_end(rbtree
, y
);
1276 rcu_rbtree_transplant(rbtree
, z
, y
, 1, NULL
);
1278 struct rcu_rbtree_node
*oy_right
, *z_right
;
1281 * Need to make sure y is always visible by readers.
1283 y
= rcu_rbtree_min_dup_decay(rbtree
, z
->_right
, &z_right
);
1284 assert(!is_decay(y
));
1285 assert(!is_decay(z
));
1286 oy_right
= y
->_right
;
1289 * The max child begin of z_right does not change, because
1290 * we're only changing its left children.
1292 y
->_right
= z_right
;
1293 set_parent(y
->_right
, y
, IS_RIGHT
);
1294 assert(!is_decay(z
->_left
));
1295 y
->_left
= z
->_left
;
1296 assert(!is_decay(oy_right
));
1298 * Transplant of oy_right to old y's location will only
1299 * trigger a "end" value update of the already copied branch
1300 * (which is not visible yet). We are transplanting
1301 * oy_right as a left child of old y's parent, so the
1302 * min values update propagated upward necessarily stops
1305 rcu_rbtree_transplant(rbtree
, y
, oy_right
, 0, y
);
1306 y
->max_end
= calculate_node_max_end(rbtree
, y
);
1307 rcu_rbtree_transplant(rbtree
, z
, y
, 1, NULL
);
1308 /* Update children */
1309 (void) rcu_rbtree_min_update_decay(rbtree
, y
->_right
);
1312 assert(!is_decay(z
));
1313 assert(!is_decay(z
->_left
));
1314 y
->color
= z
->color
;
1315 set_parent(y
->_left
, y
, IS_LEFT
);
1316 set_parent(y
->_right
, get_decay(get_parent(y
->_right
)), IS_RIGHT
);
1317 assert(!is_decay(y
->_left
));
1318 assert(!is_decay(y
->_right
));
1321 int rcu_rbtree_remove(struct rcu_rbtree
*rbtree
,
1322 struct rcu_rbtree_node
*z
)
1324 struct rcu_rbtree_node
*x
, *y
;
1325 unsigned int y_original_color
;
1327 assert(!is_decay(rbtree
->root
));
1328 dbg_printf("remove %p\n", z
->begin
);
1331 assert(!is_decay(z
));
1333 y_original_color
= y
->color
;
1335 if (rcu_rbtree_is_nil(rbtree
, z
->_left
)) {
1336 rcu_rbtree_transplant(rbtree
, z
, z
->_right
, 1, NULL
);
1337 assert(!is_decay(z
));
1338 x
= get_decay(z
->_right
);
1340 } else if (rcu_rbtree_is_nil(rbtree
, z
->_right
)) {
1341 rcu_rbtree_transplant(rbtree
, z
, z
->_left
, 1, NULL
);
1342 assert(!is_decay(z
));
1343 x
= get_decay(z
->_left
);
1346 y
= rcu_rbtree_min(rbtree
, z
->_right
);
1347 assert(!is_decay(y
));
1348 y_original_color
= y
->color
;
1350 rcu_rbtree_remove_nonil(rbtree
, z
, y
);
1354 if (y_original_color
== COLOR_BLACK
)
1355 rcu_rbtree_remove_fixup(rbtree
, x
);
1357 check_max_end(rbtree
, x
);
1358 check_max_end(rbtree
, get_decay(y
));
1360 * Commit all C__CMM_STORE_SHARED().
1363 #ifdef RBTREE_RCU_SUPPORT
1364 rbtree
->call_rcu(&z
->head
, _rcu_rbtree_free_node
);
1366 _rcu_rbtree_free_node(&z
->head
);