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
165 static pthread_mutex_t test_mutex
= PTHREAD_MUTEX_INITIALIZER
;
166 static pthread_mutex_t outer_mutex
= PTHREAD_MUTEX_INITIALIZER
;
169 void lock_outer_mutex(void)
171 pthread_mutex_lock(&outer_mutex
);
175 void unlock_outer_mutex(void)
177 pthread_mutex_unlock(&outer_mutex
);
181 void lock_test_mutex(void)
183 pthread_mutex_lock(&test_mutex
);
187 void unlock_test_mutex(void)
189 pthread_mutex_unlock(&test_mutex
);
194 void set_parent(struct rcu_rbtree_node
*node
,
195 struct rcu_rbtree_node
*parent
,
198 _CMM_STORE_SHARED(node
->parent
, ((unsigned long) parent
) | pos
);
202 struct rcu_rbtree_node
*get_parent(struct rcu_rbtree_node
*node
)
204 return (struct rcu_rbtree_node
*) (node
->parent
& ~1UL);
208 unsigned int get_pos(struct rcu_rbtree_node
*node
)
210 return (unsigned int) (node
->parent
& 1UL);
214 struct rcu_rbtree_node
*get_parent_and_pos(struct rcu_rbtree_node
*node
,
217 unsigned long parent_pos
= rcu_dereference(node
->parent
);
219 *pos
= (unsigned int) (parent_pos
& 1UL);
220 return (struct rcu_rbtree_node
*) (parent_pos
& ~1UL);
224 void set_decay(struct rcu_rbtree_node
*x
, struct rcu_rbtree_node
*xc
)
230 struct rcu_rbtree_node
*get_decay(struct rcu_rbtree_node
*x
)
234 while (x
->decay_next
)
240 struct rcu_rbtree_node
*is_decay(struct rcu_rbtree_node
*x
)
242 return x
->decay_next
;
246 struct rcu_rbtree_node
*_rcu_rbtree_alloc_node(struct rcu_rbtree
*rbtree
)
248 return rbtree
->rballoc(sizeof(struct rcu_rbtree_node
));
252 void _rcu_rbtree_free_node(struct rcu_head
*head
)
254 struct rcu_rbtree_node
*node
=
255 caa_container_of(head
, struct rcu_rbtree_node
, head
);
256 node
->rbtree
->rbfree(node
);
259 #ifdef RBTREE_RCU_SUPPORT
262 struct rcu_rbtree_node
*dup_decay_node(struct rcu_rbtree
*rbtree
,
263 struct rcu_rbtree_node
*x
)
265 struct rcu_rbtree_node
*xc
;
267 if (rcu_rbtree_is_nil(rbtree
, x
))
270 xc
= _rcu_rbtree_alloc_node(rbtree
);
271 memcpy(xc
, x
, sizeof(*xc
));
272 xc
->decay_next
= NULL
;
274 rbtree
->call_rcu(&x
->head
, _rcu_rbtree_free_node
);
278 #else /* RBTREE_RCU_SUPPORT */
281 struct rcu_rbtree_node
*dup_decay_node(struct rcu_rbtree
*rbtree
,
282 struct rcu_rbtree_node
*x
)
290 * Info for range lookups:
291 * Range lookup information is only valid when used when searching for
292 * ranges. It should never be used in next/prev traversal because the
293 * pointers to parents are not in sync with the parent vision of the
297 void set_left(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
,
298 struct rcu_rbtree_node
*left
)
304 void set_right(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
,
305 struct rcu_rbtree_node
*right
)
307 node
->_right
= right
;
311 void *calculate_node_max_end(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
)
316 if (!rcu_rbtree_is_nil(rbtree
, node
->_right
)) {
317 if (rbtree
->comp(max_end
, node
->_right
->max_end
) < 0)
318 max_end
= node
->_right
->max_end
;
320 if (!rcu_rbtree_is_nil(rbtree
, node
->_left
)) {
321 if (rbtree
->comp(max_end
, node
->_left
->max_end
) < 0)
322 max_end
= node
->_left
->max_end
;
329 * Deal with memory allocation errors.
330 * Can be ensured by reserving a pool of memory entries before doing the
331 * insertion, which will have to be function of number of
332 * transplantations/rotations required for the operation (which is a
333 * multiple of the tree height).
338 void show_tree(struct rcu_rbtree
*rbtree
)
340 struct rcu_rbtree_node
*node
;
342 node
= rcu_rbtree_min(rbtree
, rbtree
->root
);
343 while (!rcu_rbtree_is_nil(rbtree
, node
)) {
344 assert(!is_decay(node
));
345 printf("{ b:%lX e:%lX pb: %lX r:%lX l:%lX %s %s %s} ",
346 (unsigned long) node
->begin
,
347 (unsigned long) node
->end
,
348 (unsigned long) get_parent(node
)->begin
,
349 (unsigned long) node
->_right
->begin
,
350 (unsigned long) node
->_left
->begin
,
351 node
->color
? "red" : "black",
352 get_pos(node
) ? "right" : "left",
353 rcu_rbtree_is_nil(rbtree
, node
) ? "nil" : "");
354 node
= rcu_rbtree_next(rbtree
, node
);
359 #define check_max_end(rbtree, x) \
361 if (rcu_rbtree_is_nil(rbtree, x)) \
363 assert(rbtree->comp(x->max_end, \
364 calculate_node_max_end(rbtree, x)) == 0); \
369 void show_tree(struct rcu_rbtree
*rbtree
)
374 void check_max_end(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*x
)
380 struct rcu_rbtree_node
*make_nil(struct rcu_rbtree
*rbtree
)
382 return &rbtree
->nil_node
;
386 * Iterative rbtree search.
388 struct rcu_rbtree_node
*rcu_rbtree_search(struct rcu_rbtree
*rbtree
,
389 struct rcu_rbtree_node
*x
,
392 struct rcu_rbtree_node
*xl
;
394 dbg_printf("searching point 0x%lx\n", (unsigned long) point
);
395 x
= rcu_dereference(x
);
397 while (!rcu_rbtree_is_nil(rbtree
, x
)) {
399 xl
= rcu_dereference(x
->_left
);
400 dbg_printf("search x %lx x_end %lx x_max_end %lx\n", (unsigned long) x
->begin
,
401 (unsigned long) x
->end
, (unsigned long) x
->max_end
);
402 dbg_printf("search xl %lx xl_end %lx xl_max_end %lx\n", (unsigned long) xl
->begin
,
403 (unsigned long) xl
->end
, (unsigned long) xl
->max_end
);
404 if (!rcu_rbtree_is_nil(rbtree
, xl
)
405 && (rbtree
->comp(xl
->max_end
, point
) > 0)) {
406 dbg_printf("go left\n");
408 } else if (rbtree
->comp(x
->begin
, point
) <= 0
409 && rbtree
->comp(point
, x
->end
) < 0) {
410 dbg_printf("got it!\n");
412 } else if (rbtree
->comp(point
, x
->begin
) > 0) {
413 dbg_printf("go right\n");
414 x
= rcu_dereference(x
->_right
);
416 dbg_printf("not found!\n");
417 x
= make_nil(rbtree
);
420 if (rcu_rbtree_is_nil(rbtree
, x
))
421 dbg_printf("Reached bottom of tree.\n");
426 struct rcu_rbtree_node
*rcu_rbtree_search_range(struct rcu_rbtree
*rbtree
,
427 struct rcu_rbtree_node
*x
,
428 void *begin
, void *end
)
430 struct rcu_rbtree_node
*node
;
432 node
= rcu_rbtree_search(rbtree
, x
, begin
);
433 if (rcu_rbtree_is_nil(rbtree
, node
))
435 if (rbtree
->comp(node
->end
, end
) < 0)
436 return NULL
; /* High is outside lookup range */
441 * Search by exact range start value.
443 struct rcu_rbtree_node
*rcu_rbtree_search_begin_key(struct rcu_rbtree
*rbtree
,
444 struct rcu_rbtree_node
*x
,
447 x
= rcu_dereference(x
);
450 while (!rcu_rbtree_is_nil(rbtree
, x
) && (comp
= rbtree
->comp(k
, x
->begin
)) != 0) {
453 x
= rcu_dereference(x
->_left
);
455 x
= rcu_dereference(x
->_right
);
461 struct rcu_rbtree_node
*rcu_rbtree_min_dup_decay(struct rcu_rbtree
*rbtree
,
462 struct rcu_rbtree_node
*x
,
463 struct rcu_rbtree_node
**zr
)
465 struct rcu_rbtree_node
*xl
;
467 x
= rcu_dereference(x
);
469 if (rcu_rbtree_is_nil(rbtree
, x
)) {
473 *zr
= x
= dup_decay_node(rbtree
, x
);
475 while (!rcu_rbtree_is_nil(rbtree
, xl
= rcu_dereference(x
->_left
))) {
476 x
= dup_decay_node(rbtree
, xl
);
477 set_parent(x
, get_decay(get_parent(x
)), get_pos(x
));
478 get_parent(x
)->_left
= get_decay(get_parent(x
)->_left
);
484 struct rcu_rbtree_node
*rcu_rbtree_min_update_decay(struct rcu_rbtree
*rbtree
,
485 struct rcu_rbtree_node
*x
)
487 struct rcu_rbtree_node
*xl
;
489 x
= rcu_dereference(x
);
491 if (rcu_rbtree_is_nil(rbtree
, x
))
494 set_parent(x
->_right
, get_decay(get_parent(x
->_right
)),
496 set_parent(x
->_left
, get_decay(get_parent(x
->_left
)),
500 while (!rcu_rbtree_is_nil(rbtree
, xl
= rcu_dereference(x
->_left
))) {
502 set_parent(x
->_right
, get_decay(get_parent(x
->_right
)),
504 set_parent(x
->_left
, get_decay(get_parent(x
->_left
)),
510 struct rcu_rbtree_node
*rcu_rbtree_min(struct rcu_rbtree
*rbtree
,
511 struct rcu_rbtree_node
*x
)
513 struct rcu_rbtree_node
*xl
;
515 x
= rcu_dereference(x
);
517 if (rcu_rbtree_is_nil(rbtree
, x
))
520 while (!rcu_rbtree_is_nil(rbtree
, xl
= rcu_dereference(x
->_left
)))
525 struct rcu_rbtree_node
*rcu_rbtree_max(struct rcu_rbtree
*rbtree
,
526 struct rcu_rbtree_node
*x
)
528 struct rcu_rbtree_node
*xr
;
530 x
= rcu_dereference(x
);
532 if (rcu_rbtree_is_nil(rbtree
, x
))
535 while (!rcu_rbtree_is_nil(rbtree
, xr
= rcu_dereference(x
->_right
)))
541 * RCU read lock must be held across the next/prev calls to ensure validity of
544 struct rcu_rbtree_node
*rcu_rbtree_next(struct rcu_rbtree
*rbtree
,
545 struct rcu_rbtree_node
*x
)
547 struct rcu_rbtree_node
*xr
, *y
;
550 x
= rcu_dereference(x
);
552 if (!rcu_rbtree_is_nil(rbtree
, xr
= rcu_dereference(x
->_right
)))
553 return rcu_rbtree_min(rbtree
, xr
);
554 y
= get_parent_and_pos(x
, &x_pos
);
555 while (!rcu_rbtree_is_nil(rbtree
, y
) && x_pos
== IS_RIGHT
) {
557 y
= get_parent_and_pos(y
, &x_pos
);
562 struct rcu_rbtree_node
*rcu_rbtree_prev(struct rcu_rbtree
*rbtree
,
563 struct rcu_rbtree_node
*x
)
565 struct rcu_rbtree_node
*xl
, *y
;
568 x
= rcu_dereference(x
);
570 if (!rcu_rbtree_is_nil(rbtree
, xl
= rcu_dereference(x
->_left
)))
571 return rcu_rbtree_max(rbtree
, xl
);
572 y
= get_parent_and_pos(x
, &x_pos
);
573 while (!rcu_rbtree_is_nil(rbtree
, y
) && x_pos
== IS_LEFT
) {
575 y
= get_parent_and_pos(y
, &x_pos
);
581 * "node" needs to be non-visible by readers.
584 void populate_node_end(struct rcu_rbtree
*rbtree
, struct rcu_rbtree_node
*node
,
585 unsigned int copy_parents
, struct rcu_rbtree_node
*stop
)
587 struct rcu_rbtree_node
*prev
= NULL
, *orig_node
= node
, *top
;
593 assert(!rcu_rbtree_is_nil(rbtree
, node
));
595 if (prev
&& copy_parents
) {
596 node
= dup_decay_node(rbtree
, node
);
597 if (get_pos(prev
) == IS_RIGHT
)
601 set_parent(prev
, node
, get_pos(prev
));
604 max_end
= calculate_node_max_end(rbtree
, node
);
606 * Compare the node max_end keys to make sure we replace
607 * references to a key belonging to a node we remove
608 * from the tree. Otherwise we would still be using this
609 * pointer as an invalid reference after garbage
610 * collection of the node and of its associated
611 * begin/end pointers.
613 if (max_end
!= node
->max_end
) {
614 node
->max_end
= max_end
;
616 top
= get_parent(node
);
617 cmm_smp_wmb(); /* write into node before publish */
618 /* make new branch visible to readers */
619 if (rcu_rbtree_is_nil(rbtree
, top
))
620 _CMM_STORE_SHARED(rbtree
->root
, node
);
621 if (get_pos(node
) == IS_LEFT
)
622 _CMM_STORE_SHARED(top
->_left
, node
);
624 _CMM_STORE_SHARED(top
->_right
, node
);
628 /* Check for propagation stop */
633 node
= get_parent(node
);
634 } while (!rcu_rbtree_is_nil(rbtree
, node
));
636 top
= node
; /* nil */
637 cmm_smp_wmb(); /* write into node before publish */
638 /* make new branch visible to readers */
639 _CMM_STORE_SHARED(rbtree
->root
, prev
);
644 /* update children */
647 assert(!rcu_rbtree_is_nil(rbtree
, node
));
648 set_parent(node
->_left
, get_decay(get_parent(node
->_left
)), IS_LEFT
);
649 set_parent(node
->_right
, get_decay(get_parent(node
->_right
)), IS_RIGHT
);
650 } while ((node
= get_parent(node
)) != top
);
654 * We have to ensure these assumptions are correct for prev/next
657 * with x being a right child, the assumption that:
658 * get_parent(x)->_right == x
659 * or if x is a left child, the assumption that:
660 * get_parent(x)->_left == x
662 * This explains why we have to allocate a vc copy of the node for left_rotate,
663 * right_rotate and transplant operations.
665 * We always ensure that the right/left child and correct parent is set in the
666 * node copies *before* we reparent the children and make the upper-level point
670 /* RCU: copy x and y, atomically point to new versions. GC old. */
671 /* Should be eventually followed by a cmm_smp_wmc() */
673 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
676 void left_rotate(struct rcu_rbtree
*rbtree
,
677 struct rcu_rbtree_node
*x
)
679 struct rcu_rbtree_node
*y
, *y_left
;
681 dbg_printf("left rotate %lx\n", (unsigned long) x
->begin
);
686 /* Now operate on new copy, decay old versions */
687 x
= dup_decay_node(rbtree
, x
);
688 y
= dup_decay_node(rbtree
, y
);
689 y_left
= dup_decay_node(rbtree
, y_left
);
691 check_max_end(rbtree
, get_parent(x
));
692 check_max_end(rbtree
, x
);
693 check_max_end(rbtree
, y
);
695 /* Internal node modifications */
696 set_parent(y
, get_parent(x
), get_pos(x
));
697 set_parent(x
, y
, IS_LEFT
);
698 set_left(rbtree
, y
, x
);
699 set_right(rbtree
, x
, y_left
);
701 if (!rcu_rbtree_is_nil(rbtree
, y_left
))
702 set_parent(y_left
, x
, IS_RIGHT
);
705 * We only changed the relative position of x and y wrt their
706 * children, and reparented y (but are keeping the same nodes in
707 * place, so its parent does not need to have end value
710 x
->max_end
= calculate_node_max_end(rbtree
, x
);
711 y
->max_end
= calculate_node_max_end(rbtree
, y
);
713 cmm_smp_wmb(); /* write into node before publish */
715 /* External references update (visible by readers) */
716 if (rcu_rbtree_is_nil(rbtree
, get_parent(y
)))
717 _CMM_STORE_SHARED(rbtree
->root
, y
);
718 else if (get_pos(y
) == IS_LEFT
)
719 _CMM_STORE_SHARED(get_parent(y
)->_left
, y
);
721 _CMM_STORE_SHARED(get_parent(y
)->_right
, y
);
723 /* Point children to new copy (parent only used by updates/next/prev) */
724 set_parent(x
->_left
, get_decay(get_parent(x
->_left
)),
726 set_parent(y
->_right
, get_decay(get_parent(y
->_right
)),
728 if (!rcu_rbtree_is_nil(rbtree
, y_left
)) {
729 set_parent(y_left
->_right
,
730 get_decay(get_parent(y_left
->_right
)),
731 get_pos(y_left
->_right
));
732 set_parent(y_left
->_left
,
733 get_decay(get_parent(y_left
->_left
)),
734 get_pos(y_left
->_left
));
738 assert(y
== rbtree
->root
|| get_parent(y
)->_left
== y
739 || get_parent(y
)->_right
== y
);
740 assert(x
== rbtree
->root
|| get_parent(x
)->_left
== x
741 || get_parent(x
)->_right
== x
);
742 assert(rcu_rbtree_is_nil(rbtree
, x
->_right
) || get_parent(x
->_right
) == x
);
743 assert(rcu_rbtree_is_nil(rbtree
, x
->_left
) || get_parent(x
->_left
) == x
);
744 assert(rcu_rbtree_is_nil(rbtree
, y
->_right
) || get_parent(y
->_right
) == y
);
745 assert(rcu_rbtree_is_nil(rbtree
, y
->_left
) || get_parent(y
->_left
) == y
);
746 assert(!is_decay(rbtree
->root
));
747 assert(!is_decay(x
));
748 assert(!is_decay(y
));
749 assert(!is_decay(x
->_right
));
750 assert(!is_decay(x
->_left
));
751 assert(!is_decay(y
->_right
));
752 assert(!is_decay(y
->_left
));
753 check_max_end(rbtree
, get_parent(y
));
754 check_max_end(rbtree
, x
);
755 check_max_end(rbtree
, y
);
760 /* non-rcu version */
762 void left_rotate(struct rcu_rbtree
*rbtree
,
763 struct rcu_rbtree_node
*x
)
765 struct rcu_rbtree_node
*y
;
769 x
->_right
= y
->_left
;
770 if (!rcu_rbtree_is_nil(rbtree
, y
->_left
))
771 set_parent(y
->_left
, x
, IS_RIGHT
);
772 set_parent(y
, get_parent(x
), get_pos(x
));
773 if (rcu_rbtree_is_nil(rbtree
, get_parent(x
)))
775 else if (x
== get_parent(x
)->_left
) {
776 get_parent(x
)->_left
= y
;
778 get_parent(x
)->_right
= y
;
781 set_parent(x
, y
, IS_LEFT
);
787 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
789 void right_rotate(struct rcu_rbtree
*rbtree
,
790 struct rcu_rbtree_node
*x
)
792 struct rcu_rbtree_node
*y
, *y_right
;
794 dbg_printf("right rotate %lx\n", (unsigned long) x
->begin
);
799 /* Now operate on new copy, decay old versions */
800 x
= dup_decay_node(rbtree
, x
);
801 y
= dup_decay_node(rbtree
, y
);
802 y_right
= dup_decay_node(rbtree
, y_right
);
804 check_max_end(rbtree
, get_parent(x
));
805 check_max_end(rbtree
, x
);
806 check_max_end(rbtree
, y
);
808 /* Internal node modifications */
809 set_parent(y
, get_parent(x
), get_pos(x
));
810 set_parent(x
, y
, IS_RIGHT
);
811 set_right(rbtree
, y
, x
);
812 set_left(rbtree
, x
, y_right
);
814 if (!rcu_rbtree_is_nil(rbtree
, y_right
))
815 set_parent(y_right
, x
, IS_LEFT
);
818 * We only changed the relative position of x and y wrt their
819 * children, and reparented y (but are keeping the same nodes in
820 * place, so its parent does not need to have end value
823 x
->max_end
= calculate_node_max_end(rbtree
, x
);
824 y
->max_end
= calculate_node_max_end(rbtree
, y
);
826 cmm_smp_wmb(); /* write into node before publish */
828 /* External references update (visible by readers) */
829 if (rcu_rbtree_is_nil(rbtree
, get_parent(y
)))
830 _CMM_STORE_SHARED(rbtree
->root
, y
);
831 else if (get_pos(y
) == IS_RIGHT
)
832 _CMM_STORE_SHARED(get_parent(y
)->_right
, y
);
834 _CMM_STORE_SHARED(get_parent(y
)->_left
, y
);
836 /* Point children to new copy (parent only used by updates/next/prev) */
837 set_parent(x
->_right
, get_decay(get_parent(x
->_right
)),
839 set_parent(y
->_left
, get_decay(get_parent(y
->_left
)),
841 if (!rcu_rbtree_is_nil(rbtree
, y_right
)) {
842 set_parent(y_right
->_left
,
843 get_decay(get_parent(y_right
->_left
)),
844 get_pos(y_right
->_left
));
845 set_parent(y_right
->_right
,
846 get_decay(get_parent(y_right
->_right
)),
847 get_pos(y_right
->_right
));
851 assert(y
== rbtree
->root
|| get_parent(y
)->_right
== y
852 || get_parent(y
)->_left
== y
);
853 assert(x
== rbtree
->root
|| get_parent(x
)->_right
== x
854 || get_parent(x
)->_left
== x
);
855 assert(rcu_rbtree_is_nil(rbtree
, x
->_left
) || get_parent(x
->_left
) == x
);
856 assert(rcu_rbtree_is_nil(rbtree
, x
->_right
) || get_parent(x
->_right
) == x
);
857 assert(rcu_rbtree_is_nil(rbtree
, y
->_left
) || get_parent(y
->_left
) == y
);
858 assert(rcu_rbtree_is_nil(rbtree
, y
->_right
) || get_parent(y
->_right
) == y
);
859 assert(!is_decay(rbtree
->root
));
860 assert(!is_decay(x
));
861 assert(!is_decay(y
));
862 assert(!is_decay(x
->_left
));
863 assert(!is_decay(x
->_right
));
864 assert(!is_decay(y
->_left
));
865 assert(!is_decay(y
->_right
));
866 check_max_end(rbtree
, x
);
867 check_max_end(rbtree
, y
);
868 check_max_end(rbtree
, get_parent(y
));
873 /* non-rcu version */
875 void right_rotate(struct rcu_rbtree
*rbtree
,
876 struct rcu_rbtree_node
*x
)
878 struct rcu_rbtree_node
*y
;
882 x
->_left
= y
->_right
;
883 if (!rcu_rbtree_is_nil(rbtree
, y
->_right
))
884 set_parent(y
->_right
, x
, IS_LEFT
);
885 set_parent(y
, get_parent(x
), get_pos(x
));
886 if (rcu_rbtree_is_nil(rbtree
, get_parent(x
)))
888 else if (x
== get_parent(x
)->_right
) {
889 get_parent(x
)->_right
= y
;
891 get_parent(x
)->_left
= y
;
894 set_parent(x
, y
, IS_RIGHT
);
900 static void rcu_rbtree_insert_fixup(struct rcu_rbtree
*rbtree
,
901 struct rcu_rbtree_node
*z
)
903 struct rcu_rbtree_node
*y
;
905 dbg_printf("insert fixup %p\n", z
->begin
);
906 assert(!is_decay(rbtree
->root
));
908 while (get_parent(z
)->color
== COLOR_RED
) {
909 if (get_parent(z
) == get_parent(get_parent(z
))->_left
) {
910 y
= get_parent(get_parent(z
))->_right
;
911 if (y
->color
== COLOR_RED
) {
912 get_parent(z
)->color
= COLOR_BLACK
;
913 y
->color
= COLOR_BLACK
;
914 get_parent(get_parent(z
))->color
= COLOR_RED
;
915 z
= get_parent(get_parent(z
));
917 if (z
== get_parent(z
)->_right
) {
919 left_rotate(rbtree
, z
);
921 assert(!is_decay(rbtree
->root
));
923 get_parent(z
)->color
= COLOR_BLACK
;
924 get_parent(get_parent(z
))->color
= COLOR_RED
;
925 assert(!is_decay(z
));
926 assert(!is_decay(get_parent(z
)));
927 assert(!is_decay(get_parent(get_parent(z
))));
928 right_rotate(rbtree
, get_parent(get_parent(z
)));
929 assert(!is_decay(z
));
930 assert(!is_decay(rbtree
->root
));
933 y
= get_parent(get_parent(z
))->_left
;
934 if (y
->color
== COLOR_RED
) {
935 get_parent(z
)->color
= COLOR_BLACK
;
936 y
->color
= COLOR_BLACK
;
937 get_parent(get_parent(z
))->color
= COLOR_RED
;
938 z
= get_parent(get_parent(z
));
940 if (z
== get_parent(z
)->_left
) {
942 right_rotate(rbtree
, z
);
944 assert(!is_decay(rbtree
->root
));
946 get_parent(z
)->color
= COLOR_BLACK
;
947 get_parent(get_parent(z
))->color
= COLOR_RED
;
948 left_rotate(rbtree
, get_parent(get_parent(z
)));
949 assert(!is_decay(z
));
950 assert(!is_decay(rbtree
->root
));
954 rbtree
->root
->color
= COLOR_BLACK
;
958 * rcu_rbtree_insert - Insert a node in the RCU rbtree
960 * Returns 0 on success, or < 0 on error.
962 int rcu_rbtree_insert(struct rcu_rbtree
*rbtree
,
963 void *begin
, void *end
)
965 struct rcu_rbtree_node
*x
, *y
, *z
;
967 z
= _rcu_rbtree_alloc_node(rbtree
);
973 dbg_printf("insert %p\n", z
->begin
);
974 assert(!is_decay(rbtree
->root
));
976 y
= make_nil(rbtree
);
978 while (!rcu_rbtree_is_nil(rbtree
, x
)) {
980 if (rbtree
->comp(z
->begin
, x
->begin
) < 0)
986 z
->_left
= make_nil(rbtree
);
987 z
->_right
= make_nil(rbtree
);
988 z
->color
= COLOR_RED
;
989 z
->decay_next
= NULL
;
993 if (rcu_rbtree_is_nil(rbtree
, y
)) {
994 set_parent(z
, y
, IS_RIGHT
); /* pos arbitrary for root node */
996 * Order stores to z (children/parents) before stores
997 * that will make it visible to the rest of the tree.
1000 _CMM_STORE_SHARED(rbtree
->root
, z
);
1001 } else if (rbtree
->comp(z
->begin
, y
->begin
) < 0) {
1002 y
= dup_decay_node(rbtree
, y
);
1003 set_parent(z
, y
, IS_LEFT
);
1004 if (get_pos(z
) == IS_LEFT
)
1005 _CMM_STORE_SHARED(y
->_left
, z
);
1007 _CMM_STORE_SHARED(y
->_right
, z
);
1008 populate_node_end(rbtree
, y
, 1, NULL
);
1010 y
= dup_decay_node(rbtree
, y
);
1011 set_parent(z
, y
, IS_RIGHT
);
1012 if (get_pos(z
) == IS_LEFT
)
1013 _CMM_STORE_SHARED(y
->_left
, z
);
1015 _CMM_STORE_SHARED(y
->_right
, z
);
1016 populate_node_end(rbtree
, y
, 1, NULL
);
1018 rcu_rbtree_insert_fixup(rbtree
, z
);
1020 * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
1024 check_max_end(rbtree
, z
);
1025 check_max_end(rbtree
, y
);
1031 * Transplant v into u position.
1034 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
1037 void rcu_rbtree_transplant(struct rcu_rbtree
*rbtree
,
1038 struct rcu_rbtree_node
*u
,
1039 struct rcu_rbtree_node
*v
,
1040 unsigned int copy_parents
,
1041 struct rcu_rbtree_node
*stop
)
1043 dbg_printf("transplant %p\n", v
->begin
);
1045 if (!rcu_rbtree_is_nil(rbtree
, v
))
1046 v
= dup_decay_node(rbtree
, v
);
1048 if (rcu_rbtree_is_nil(rbtree
, get_parent(u
))) {
1049 /* pos is arbitrary for root node */
1050 set_parent(v
, get_parent(u
), IS_RIGHT
);
1051 cmm_smp_wmb(); /* write into node before publish */
1052 _CMM_STORE_SHARED(rbtree
->root
, v
);
1054 struct rcu_rbtree_node
*vp
;
1058 vp
= dup_decay_node(rbtree
, vp
);
1059 set_parent(v
, vp
, get_pos(u
));
1060 if (get_pos(v
) == IS_LEFT
)
1061 _CMM_STORE_SHARED(vp
->_left
, v
);
1063 _CMM_STORE_SHARED(vp
->_right
, v
);
1064 populate_node_end(rbtree
, vp
, copy_parents
, stop
);
1065 check_max_end(rbtree
, vp
);
1068 /* Point children to new copy (parent only used by updates/next/prev) */
1069 if (!rcu_rbtree_is_nil(rbtree
, v
)) {
1070 set_parent(v
->_right
, get_decay(get_parent(v
->_right
)),
1071 get_pos(v
->_right
));
1072 set_parent(v
->_left
, get_decay(get_parent(v
->_left
)),
1075 assert(!is_decay(rbtree
->root
));
1076 check_max_end(rbtree
, v
);
1081 /* Non-RCU version */
1083 void rcu_rbtree_transplant(struct rcu_rbtree
*rbtree
,
1084 struct rcu_rbtree_node
*u
,
1085 struct rcu_rbtree_node
*v
,
1086 unsigned int copy_parents
,
1087 struct rcu_rbtree_node
*stop
)
1089 dbg_printf("transplant %p\n", v
->begin
);
1092 if (rcu_rbtree_is_nil(rbtree
, get_parent(u
)))
1094 else if (u
== get_parent(u
)->_left
)
1095 get_parent(u
)->_left
= v
;
1097 get_parent(u
)->_right
= v
;
1098 set_parent(v
, get_parent(u
), get_pos(u
));
1099 unlock_test_mutex();
1104 static void rcu_rbtree_remove_fixup(struct rcu_rbtree
*rbtree
,
1105 struct rcu_rbtree_node
*x
)
1107 dbg_printf("remove fixup %p\n", x
->begin
);
1109 while (x
!= rbtree
->root
&& x
->color
== COLOR_BLACK
) {
1110 assert(!is_decay(get_parent(x
)));
1111 assert(!is_decay(get_parent(x
)->_left
));
1112 if (x
== get_parent(x
)->_left
) {
1113 struct rcu_rbtree_node
*w
;
1115 w
= get_parent(x
)->_right
;
1117 if (w
->color
== COLOR_RED
) {
1118 w
->color
= COLOR_BLACK
;
1119 get_parent(x
)->color
= COLOR_RED
;
1120 left_rotate(rbtree
, get_parent(x
));
1122 assert(!is_decay(rbtree
->root
));
1123 w
= get_parent(x
)->_right
;
1125 if (w
->_left
->color
== COLOR_BLACK
1126 && w
->_right
->color
== COLOR_BLACK
) {
1127 w
->color
= COLOR_RED
;
1129 assert(!is_decay(rbtree
->root
));
1130 assert(!is_decay(x
));
1132 if (w
->_right
->color
== COLOR_BLACK
) {
1133 w
->_left
->color
= COLOR_BLACK
;
1134 w
->color
= COLOR_RED
;
1135 right_rotate(rbtree
, w
);
1136 assert(!is_decay(rbtree
->root
));
1138 w
= get_parent(x
)->_right
;
1140 w
->color
= get_parent(x
)->color
;
1141 get_parent(x
)->color
= COLOR_BLACK
;
1142 w
->_right
->color
= COLOR_BLACK
;
1143 left_rotate(rbtree
, get_parent(x
));
1144 assert(!is_decay(rbtree
->root
));
1148 struct rcu_rbtree_node
*w
;
1150 w
= get_parent(x
)->_left
;
1152 if (w
->color
== COLOR_RED
) {
1153 w
->color
= COLOR_BLACK
;
1154 get_parent(x
)->color
= COLOR_RED
;
1155 right_rotate(rbtree
, get_parent(x
));
1156 assert(!is_decay(rbtree
->root
));
1158 w
= get_parent(x
)->_left
;
1160 if (w
->_right
->color
== COLOR_BLACK
1161 && w
->_left
->color
== COLOR_BLACK
) {
1162 w
->color
= COLOR_RED
;
1164 assert(!is_decay(rbtree
->root
));
1165 assert(!is_decay(x
));
1167 if (w
->_left
->color
== COLOR_BLACK
) {
1168 w
->_right
->color
= COLOR_BLACK
;
1169 w
->color
= COLOR_RED
;
1170 left_rotate(rbtree
, w
);
1171 assert(!is_decay(rbtree
->root
));
1173 w
= get_parent(x
)->_left
;
1175 w
->color
= get_parent(x
)->color
;
1176 get_parent(x
)->color
= COLOR_BLACK
;
1177 w
->_left
->color
= COLOR_BLACK
;
1178 right_rotate(rbtree
, get_parent(x
));
1179 assert(!is_decay(rbtree
->root
));
1184 x
->color
= COLOR_BLACK
;
1188 * Delete z. All non-copied children left/right positions are unchanged.
1191 void rcu_rbtree_remove_nonil(struct rcu_rbtree
*rbtree
,
1192 struct rcu_rbtree_node
*z
,
1193 struct rcu_rbtree_node
*y
)
1195 struct rcu_rbtree_node
*x
;
1197 dbg_printf("remove nonil %p\n", z
->begin
);
1200 assert(!is_decay(z
));
1201 assert(!is_decay(y
));
1202 assert(!is_decay(y
->_right
));
1203 assert(!is_decay(get_parent(y
)));
1205 assert(!is_decay(x
));
1206 if (get_parent(y
) == z
) {
1207 y
= dup_decay_node(rbtree
, y
);
1208 set_parent(x
, y
, get_pos(x
)); /* parent for nil */
1209 /* y is z's right node */
1210 set_left(rbtree
, y
, z
->_left
);
1211 y
->max_end
= calculate_node_max_end(rbtree
, y
);
1212 rcu_rbtree_transplant(rbtree
, z
, y
, 1, NULL
);
1214 struct rcu_rbtree_node
*oy_right
, *z_right
;
1217 * Need to make sure y is always visible by readers.
1219 y
= rcu_rbtree_min_dup_decay(rbtree
, z
->_right
, &z_right
);
1220 assert(!is_decay(y
));
1221 assert(!is_decay(z
));
1222 oy_right
= y
->_right
;
1225 * The max child begin of z_right does not change, because
1226 * we're only changing its left children.
1228 y
->_right
= z_right
;
1229 set_parent(y
->_right
, y
, IS_RIGHT
);
1230 assert(!is_decay(z
->_left
));
1231 y
->_left
= z
->_left
;
1232 assert(!is_decay(oy_right
));
1234 * Transplant of oy_right to old y's location will only
1235 * trigger a "end" value update of the already copied branch
1236 * (which is not visible yet). We are transplanting
1237 * oy_right as a left child of old y's parent, so the
1238 * min values update propagated upward necessarily stops
1241 rcu_rbtree_transplant(rbtree
, y
, oy_right
, 0, y
);
1242 y
->max_end
= calculate_node_max_end(rbtree
, y
);
1243 rcu_rbtree_transplant(rbtree
, z
, y
, 1, NULL
);
1244 /* Update children */
1245 (void) rcu_rbtree_min_update_decay(rbtree
, y
->_right
);
1248 assert(!is_decay(z
));
1249 assert(!is_decay(z
->_left
));
1250 y
->color
= z
->color
;
1251 set_parent(y
->_left
, y
, IS_LEFT
);
1252 set_parent(y
->_right
, get_decay(get_parent(y
->_right
)), IS_RIGHT
);
1253 assert(!is_decay(y
->_left
));
1254 assert(!is_decay(y
->_right
));
1257 int rcu_rbtree_remove(struct rcu_rbtree
*rbtree
,
1258 struct rcu_rbtree_node
*z
)
1260 struct rcu_rbtree_node
*x
, *y
;
1261 unsigned int y_original_color
;
1263 assert(!is_decay(rbtree
->root
));
1264 dbg_printf("remove %p\n", z
->begin
);
1267 assert(!is_decay(z
));
1269 y_original_color
= y
->color
;
1271 if (rcu_rbtree_is_nil(rbtree
, z
->_left
)) {
1272 rcu_rbtree_transplant(rbtree
, z
, z
->_right
, 1, NULL
);
1273 assert(!is_decay(z
));
1274 x
= get_decay(z
->_right
);
1276 } else if (rcu_rbtree_is_nil(rbtree
, z
->_right
)) {
1277 rcu_rbtree_transplant(rbtree
, z
, z
->_left
, 1, NULL
);
1278 assert(!is_decay(z
));
1279 x
= get_decay(z
->_left
);
1282 y
= rcu_rbtree_min(rbtree
, z
->_right
);
1283 assert(!is_decay(y
));
1284 y_original_color
= y
->color
;
1286 rcu_rbtree_remove_nonil(rbtree
, z
, y
);
1290 if (y_original_color
== COLOR_BLACK
)
1291 rcu_rbtree_remove_fixup(rbtree
, x
);
1293 check_max_end(rbtree
, x
);
1294 check_max_end(rbtree
, get_decay(y
));
1296 * Commit all _CMM_STORE_SHARED().
1299 #ifdef RBTREE_RCU_SUPPORT
1300 rbtree
->call_rcu(&z
->head
, _rcu_rbtree_free_node
);
1302 _rcu_rbtree_free_node(&z
->head
);