projects / urcu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Cleanup API
[urcu.git] / urcu-rbtree.c
1 /*
2 * urcu-rbtree.c
3 *
4 * Userspace RCU library - Red-Black Tree
5 *
6 * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
7 *
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.
12 *
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.
17 *
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
21 *
22 * Implementation of RCU-adapted data structures and operations based on the RB
23 * tree algorithms found in chapter 12 of:
24 *
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.
28 */
29
30 #define _BSD_SOURCE
31 #define _LGPL_SOURCE
32
33 #include <stdio.h>
34 #include <pthread.h>
35 #include <assert.h>
36 #include <string.h>
37 #include <unistd.h>
38
39 #include <urcu/rcurbtree.h>
40 #include <urcu-pointer.h>
41 #include <urcu-call-rcu.h>
42 #include <urcu/compiler.h>
43
44 #ifdef DEBUG
45 #define dbg_printf(args...) printf(args)
46 #define dbg_usleep(usecs) usleep(usecs)
47 #else
48 #define dbg_printf(args...)
49 #define dbg_usleep(usecs)
50 #endif
51
52 /*
53 * Undefine this to enable the non-RCU rotate and transplant functions
54 * (for debugging).
55 */
56 #define RBTREE_RCU_SUPPORT_ROTATE_LEFT
57 #define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
58 #define RBTREE_RCU_SUPPORT_TRANSPLANT
59
60 #ifdef EXTRA_DEBUG
61 static pthread_mutex_t test_mutex = PTHREAD_MUTEX_INITIALIZER;
62 static pthread_mutex_t outer_mutex = PTHREAD_MUTEX_INITIALIZER;
63
64 static
65 void lock_outer_mutex(void)
66 {
67 pthread_mutex_lock(&outer_mutex);
68 }
69
70 static
71 void unlock_outer_mutex(void)
72 {
73 pthread_mutex_unlock(&outer_mutex);
74 }
75
76 static
77 void lock_test_mutex(void)
78 {
79 pthread_mutex_lock(&test_mutex);
80 }
81
82 static
83 void unlock_test_mutex(void)
84 {
85 pthread_mutex_unlock(&test_mutex);
86 }
87 #endif
88
89 static
90 void set_parent(struct rcu_rbtree_node *node,
91 struct rcu_rbtree_node *parent,
92 unsigned int pos)
93 {
94 _CMM_STORE_SHARED(node->parent, ((unsigned long) parent) | pos);
95 }
96
97 static
98 struct rcu_rbtree_node *get_parent(struct rcu_rbtree_node *node)
99 {
100 return (struct rcu_rbtree_node *) (node->parent & ~1UL);
101 }
102
103 static
104 unsigned int get_pos(struct rcu_rbtree_node *node)
105 {
106 return (unsigned int) (node->parent & 1UL);
107 }
108
109 static
110 struct rcu_rbtree_node *get_parent_and_pos(struct rcu_rbtree_node *node,
111 unsigned int *pos)
112 {
113 unsigned long parent_pos = rcu_dereference(node->parent);
114
115 *pos = (unsigned int) (parent_pos & 1UL);
116 return (struct rcu_rbtree_node *) (parent_pos & ~1UL);
117 }
118
119 static
120 void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
121 {
122 x->decay_next = xc;
123 }
124
125 static
126 struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
127 {
128 if (!x)
129 return NULL;
130 while (x->decay_next)
131 x = x->decay_next;
132 return x;
133 }
134
135 static
136 struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
137 {
138 return x->decay_next;
139 }
140
141 static
142 struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
143 struct rcu_rbtree_node *x)
144 {
145 struct rcu_rbtree_node *xc;
146
147 if (rcu_rbtree_is_nil(rbtree, x))
148 return x;
149
150 xc = rbtree->rballoc();
151 memcpy(xc, x, sizeof(struct rcu_rbtree_node));
152 xc->decay_next = NULL;
153 set_decay(x, xc);
154 call_rcu(&x->head, rbtree->rbfree);
155 return xc;
156 }
157
158 /*
159 * Info for range lookups:
160 * Range lookup information is only valid when used when searching for
161 * ranges. It should never be used in next/prev traversal because the
162 * pointers to parents are not in sync with the parent vision of the
163 * children range.
164 */
165 static
166 void _set_left_dup_decay(struct rcu_rbtree *rbtree,
167 struct rcu_rbtree_node *node,
168 struct rcu_rbtree_node *left,
169 struct rcu_rbtree_node **top,
170 struct rcu_rbtree_node **top_child,
171 unsigned int *top_child_pos, int copy)
172 {
173 struct rcu_rbtree_node *first_node = node; /* already a copy */
174
175 node->_left = left;
176 do {
177 void *min_child_key;
178
179 if (rcu_rbtree_is_nil(rbtree, left)) {
180 min_child_key = node->key;
181 } else {
182 min_child_key = left->min_child_key;
183 assert(rbtree->comp(left->key, left->min_child_key) >= 0);
184 assert(rbtree->comp(node->key, left->min_child_key) >= 0);
185 }
186 if (min_child_key != node->min_child_key) {
187 if (node != first_node) {
188 if (copy) {
189 node = dup_decay_node(rbtree, node);
190 node->_left = left;
191 set_parent(left, node, IS_LEFT);
192 }
193 }
194 node->min_child_key = min_child_key;
195 } else {
196 if (node != first_node) {
197 if (top)
198 *top = node;
199 if (top_child)
200 *top_child = left;
201 if (top_child_pos)
202 *top_child_pos = get_pos(left);
203 } else {
204 if (top)
205 *top = get_parent(node);
206 if (top_child)
207 *top_child = node;
208 if (top_child_pos)
209 *top_child_pos = get_pos(node);
210 }
211 return;
212 }
213 left = node;
214 } while (get_pos(node) == IS_LEFT
215 && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
216
217 if (rcu_rbtree_is_nil(rbtree, node)) {
218 if (top)
219 *top = node;
220 if (top_child)
221 *top_child = left;
222 if (top_child_pos)
223 *top_child_pos = IS_LEFT; /* arbitrary */
224 } else {
225 assert(get_pos(node) == IS_RIGHT);
226 if (top)
227 *top = get_parent(node);
228 if (top_child)
229 *top_child = node;
230 if (top_child_pos)
231 *top_child_pos = IS_RIGHT;
232 }
233 }
234
235 static
236 void set_left_dup_decay(struct rcu_rbtree *rbtree,
237 struct rcu_rbtree_node *node,
238 struct rcu_rbtree_node *left,
239 struct rcu_rbtree_node **top,
240 struct rcu_rbtree_node **top_child,
241 unsigned int *top_child_pos)
242 {
243 _set_left_dup_decay(rbtree, node, left, top, top_child,
244 top_child_pos, 1);
245 }
246
247 static
248 void set_left_update_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
249 struct rcu_rbtree_node *left)
250 {
251 struct rcu_rbtree_node *first_node = node; /* already a copy */
252
253 do {
254 if (node != first_node) {
255 set_parent(node->_right,
256 get_decay(get_parent(node->_right)), IS_RIGHT);
257 }
258 } while (get_pos(node) == IS_LEFT
259 && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
260 }
261
262 static
263 void set_right_dup_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
264 struct rcu_rbtree_node *right,
265 struct rcu_rbtree_node **top,
266 struct rcu_rbtree_node **top_child,
267 unsigned int *top_child_pos)
268 {
269 struct rcu_rbtree_node *first_node = node; /* already a copy */
270
271 node->_right = right;
272 do {
273 void *max_child_key;
274
275 if (rcu_rbtree_is_nil(rbtree, right)) {
276 max_child_key = node->key;
277 } else {
278 max_child_key = right->max_child_key;
279 assert(rbtree->comp(right->key, right->max_child_key) <= 0);
280 assert(rbtree->comp(node->key, right->max_child_key) <= 0);
281 }
282 if (max_child_key != node->max_child_key) {
283 if (node != first_node) {
284 node = dup_decay_node(rbtree, node);
285 node->_right = right;
286 set_parent(right, node, IS_RIGHT);
287 }
288 node->max_child_key = max_child_key;
289 } else {
290 if (node != first_node) {
291 if (top)
292 *top = node;
293 if (top_child)
294 *top_child = right;
295 if (top_child_pos)
296 *top_child_pos = get_pos(right);
297 } else {
298 if (top)
299 *top = get_parent(node);
300 if (top_child)
301 *top_child = node;
302 if (top_child_pos)
303 *top_child_pos = get_pos(node);
304 }
305 return;
306 }
307 right = node;
308 } while (get_pos(node) == IS_RIGHT
309 && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
310
311 if (rcu_rbtree_is_nil(rbtree, node)) {
312 if (top)
313 *top = node;
314 if (top_child)
315 *top_child = right;
316 if (top_child_pos)
317 *top_child_pos = IS_RIGHT; /* arbitrary */
318 } else {
319 assert(get_pos(node) == IS_LEFT);
320 if (top)
321 *top = get_parent(node);
322 if (top_child)
323 *top_child = node;
324 if (top_child_pos)
325 *top_child_pos = IS_LEFT;
326 }
327 }
328
329 static
330 void set_right_update_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
331 struct rcu_rbtree_node *right)
332 {
333 struct rcu_rbtree_node *first_node = node; /* already a copy */
334
335 do {
336 if (node != first_node) {
337 set_parent(node->_left,
338 get_decay(get_parent(node->_left)), IS_LEFT);
339 }
340 } while (get_pos(node) == IS_RIGHT
341 && !rcu_rbtree_is_nil(rbtree, node = get_parent(node)));
342 }
343
344 /*
345 * TODO
346 * Deal with memory allocation errors.
347 * Can be ensured by reserving a pool of memory entries before doing the
348 * insertion, which will have to be function of number of
349 * transplantations/rotations required for the operation.
350 */
351
352 #ifdef DEBUG
353 static
354 void show_tree(struct rcu_rbtree *rbtree)
355 {
356 struct rcu_rbtree_node *node;
357
358 node = rcu_rbtree_min(rbtree, rbtree->root);
359 while (!rcu_rbtree_is_nil(rbtree, node)) {
360 assert(!is_decay(node));
361 printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
362 (unsigned long)node->key,
363 (unsigned long) get_parent(node)->key,
364 (unsigned long) node->_right->key,
365 (unsigned long) node->_left->key,
366 node->color ? "red" : "black",
367 get_pos(node) ? "right" : "left",
368 node->nil ? "nil" : "");
369 node = rcu_rbtree_next(rbtree, node);
370 }
371 printf("\n");
372 }
373 #else /* DEBUG */
374 static
375 void show_tree(struct rcu_rbtree *rbtree)
376 {
377 }
378 #endif /* DEBUG */
379
380 static
381 struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
382 {
383 return &rbtree->nil_node;
384 }
385
386 /*
387 * Iterative rbtree search.
388 */
389 struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree,
390 struct rcu_rbtree_node *x,
391 void *k)
392 {
393 x = rcu_dereference(x);
394 int comp;
395
396 while (!rcu_rbtree_is_nil(rbtree, x) && (comp = rbtree->comp(k, x->key)) != 0) {
397 dbg_usleep(10);
398 if (comp < 0)
399 x = rcu_dereference(x->_left);
400 else
401 x = rcu_dereference(x->_right);
402 }
403 return x;
404 }
405
406 struct rcu_rbtree_node *rcu_rbtree_search_min(struct rcu_rbtree *rbtree,
407 struct rcu_rbtree_node *x,
408 void *range_low, void *range_high)
409 {
410 struct rcu_rbtree_node *xl;
411 x = rcu_dereference(x);
412
413 dbg_printf("start search min x %lx low %lx high %lx\n",
414 (unsigned long) x->key,
415 (unsigned long) range_low, (unsigned long) range_high);
416 while (!rcu_rbtree_is_nil(rbtree, x)) {
417 dbg_usleep(10);
418 xl = rcu_dereference(x->_left);
419 dbg_printf("search min x %lx\n", (unsigned long) x->key);
420 dbg_printf("search min xl %lx\n", (unsigned long) xl->key);
421 if (!rcu_rbtree_is_nil(rbtree, xl)
422 && (rbtree->comp(xl->max_child_key, range_low) >= 0
423 || rbtree->comp(xl->key, range_low) == 0)) {
424 dbg_printf("go left\n");
425 x = xl;
426 } else if (rbtree->comp(x->key, range_low) >= 0
427 && rbtree->comp(x->key, range_high) <= 0) {
428 dbg_printf("got it!\n");
429 break;
430 } else if (rbtree->comp(range_low, x->min_child_key) >= 0) {
431 dbg_printf("go right\n");
432 x = rcu_dereference(x->_right);
433 } else {
434 dbg_printf("not found!\n");
435 x = make_nil(rbtree);
436 }
437 }
438 return x;
439 }
440
441 struct rcu_rbtree_node *rcu_rbtree_search_max(struct rcu_rbtree *rbtree,
442 struct rcu_rbtree_node *x,
443 void *range_low, void *range_high)
444 {
445 struct rcu_rbtree_node *xr;
446 x = rcu_dereference(x);
447
448 dbg_printf("start search max x %lx low %lx high %lx\n",
449 (unsigned long) x->key,
450 (unsigned long) range_low, (unsigned long) range_high);
451 while (!rcu_rbtree_is_nil(rbtree, x)) {
452 dbg_usleep(10);
453 xr = rcu_dereference(x->_right);
454 dbg_printf("search max x %lx\n", (unsigned long) x->key);
455 dbg_printf("search max xl %lx\n", (unsigned long) xr->key);
456 if (!rcu_rbtree_is_nil(rbtree, xr)
457 && (rbtree->comp(xr->min_child_key, range_high) <= 0
458 || rbtree->comp(xr->key, range_high) == 0)) {
459 dbg_printf("go right\n");
460 x = xr;
461 } else if (rbtree->comp(x->key, range_low) >= 0
462 && rbtree->comp(x->key, range_high) <= 0) {
463 dbg_printf("got it!\n");
464 break;
465 } else if (rbtree->comp(range_high, x->max_child_key) <= 0) {
466 dbg_printf("go left\n");
467 x = rcu_dereference(x->_left);
468 } else {
469 dbg_printf("not found!\n");
470 x = make_nil(rbtree);
471 }
472 }
473 return x;
474 }
475
476 static
477 struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree,
478 struct rcu_rbtree_node *x,
479 struct rcu_rbtree_node **zr)
480 {
481 struct rcu_rbtree_node *xl;
482
483 x = rcu_dereference(x);
484
485 if (rcu_rbtree_is_nil(rbtree, x)) {
486 *zr = x;
487 return x;
488 } else
489 *zr = x = dup_decay_node(rbtree, x);
490
491 while (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left))) {
492 x = dup_decay_node(rbtree, xl);
493 set_parent(x, get_decay(get_parent(x)), get_pos(x));
494 get_parent(x)->_left = get_decay(get_parent(x)->_left);
495 }
496 return x;
497 }
498
499 static
500 struct rcu_rbtree_node *rcu_rbtree_min_update_decay(struct rcu_rbtree *rbtree,
501 struct rcu_rbtree_node *x)
502 {
503 struct rcu_rbtree_node *xl;
504
505 x = rcu_dereference(x);
506
507 if (rcu_rbtree_is_nil(rbtree, x))
508 return x;
509 else {
510 set_parent(x->_right, get_decay(get_parent(x->_right)),
511 get_pos(x->_right));
512 set_parent(x->_left, get_decay(get_parent(x->_left)),
513 get_pos(x->_left));
514 }
515
516 while (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left))) {
517 x = xl;
518 set_parent(x->_right, get_decay(get_parent(x->_right)),
519 get_pos(x->_right));
520 set_parent(x->_left, get_decay(get_parent(x->_left)),
521 get_pos(x->_left));
522 }
523 return x;
524 }
525
526 struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
527 struct rcu_rbtree_node *x)
528 {
529 struct rcu_rbtree_node *xl;
530
531 x = rcu_dereference(x);
532
533 if (rcu_rbtree_is_nil(rbtree, x))
534 return x;
535
536 while (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left)))
537 x = xl;
538 return x;
539 }
540
541 struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
542 struct rcu_rbtree_node *x)
543 {
544 struct rcu_rbtree_node *xr;
545
546 x = rcu_dereference(x);
547
548 if (rcu_rbtree_is_nil(rbtree, x))
549 return x;
550
551 while (!rcu_rbtree_is_nil(rbtree, xr = rcu_dereference(x->_right)))
552 x = xr;
553 return x;
554 }
555
556 /*
557 * FIXME:
558 * Updates should wait for a grace period between update of the
559 * redirect pointer and update of the parent child pointer. This is to make sure
560 * that no reference to the old entry exist.
561 */
562
563 /*
564 * RCU read lock must be held across the next/prev calls to ensure validity of
565 * the returned node.
566 */
567 struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree,
568 struct rcu_rbtree_node *x)
569 {
570 struct rcu_rbtree_node *xr, *y;
571 unsigned int x_pos;
572
573 x = rcu_dereference(x);
574
575 if (!rcu_rbtree_is_nil(rbtree, xr = rcu_dereference(x->_right)))
576 return rcu_rbtree_min(rbtree, xr);
577 y = get_parent_and_pos(x, &x_pos);
578 while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_RIGHT) {
579 x = y;
580 y = get_parent_and_pos(y, &x_pos);
581 }
582 return y;
583 }
584
585 struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
586 struct rcu_rbtree_node *x)
587 {
588 struct rcu_rbtree_node *xl, *y;
589 unsigned int x_pos;
590
591 x = rcu_dereference(x);
592
593 if (!rcu_rbtree_is_nil(rbtree, xl = rcu_dereference(x->_left)))
594 return rcu_rbtree_max(rbtree, xl);
595 y = get_parent_and_pos(x, &x_pos);
596 while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_LEFT) {
597 x = y;
598 y = get_parent_and_pos(y, &x_pos);
599 }
600 return y;
601 }
602
603 /*
604 * We have to ensure these assumptions are correct for prev/next
605 * traversal:
606 *
607 * with x being a right child, the assumption that:
608 * get_parent(x)->_right == x
609 * or if x is a left child, the assumption that:
610 * get_parent(x)->_left == x
611 *
612 * This explains why we have to allocate a vc copy of the node for left_rotate,
613 * right_rotate and transplant operations.
614 *
615 * We always ensure that the right/left child and correct parent is set in the
616 * node copies *before* we reparent the children and make the upper-level point
617 * to the copy.
618 */
619
620 /* RCU: copy x and y, atomically point to new versions. GC old. */
621 /* Should be eventually followed by a cmm_smp_wmc() */
622
623 #ifdef RBTREE_RCU_SUPPORT_ROTATE_LEFT
624
625 static
626 void left_rotate(struct rcu_rbtree *rbtree,
627 struct rcu_rbtree_node *x)
628 {
629 struct rcu_rbtree_node *y, *y_left, *top, *top_child;
630 unsigned int top_child_pos;
631
632 y = x->_right;
633 y_left = y->_left;
634
635 /* Now operate on new copy, decay old versions */
636 x = dup_decay_node(rbtree, x);
637 y = dup_decay_node(rbtree, y);
638 y_left = dup_decay_node(rbtree, y_left);
639
640 /* Internal node modifications */
641 set_parent(y, get_parent(x), get_pos(x));
642 set_parent(x, y, IS_LEFT);
643 set_left_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
644 set_right_dup_decay(rbtree, x, y_left, NULL, NULL, NULL);
645 assert(!is_decay(top));
646 assert(!is_decay(top_child));
647
648 if (!rcu_rbtree_is_nil(rbtree, y_left))
649 set_parent(y_left, x, IS_RIGHT);
650
651 cmm_smp_wmb(); /* write into node before publish */
652
653 /* External references update (visible by readers) */
654 if (rcu_rbtree_is_nil(rbtree, top))
655 _CMM_STORE_SHARED(rbtree->root, top_child);
656 else if (top_child_pos == IS_LEFT)
657 _CMM_STORE_SHARED(top->_left, top_child);
658 else
659 _CMM_STORE_SHARED(top->_right, top_child);
660
661 /* Point children to new copy (parent only used by updates/next/prev) */
662 set_parent(x->_left, get_decay(get_parent(x->_left)),
663 get_pos(x->_left));
664 set_parent(y->_right, get_decay(get_parent(y->_right)),
665 get_pos(y->_right));
666 if (!rcu_rbtree_is_nil(rbtree, y_left)) {
667 set_parent(y_left->_right,
668 get_decay(get_parent(y_left->_right)),
669 get_pos(y_left->_right));
670 set_parent(y_left->_left,
671 get_decay(get_parent(y_left->_left)),
672 get_pos(y_left->_left));
673 }
674 set_left_update_decay(rbtree, y, x);
675
676 /* Sanity checks */
677 assert(y == rbtree->root || get_parent(y)->_left == y
678 || get_parent(y)->_right == y);
679 assert(x == rbtree->root || get_parent(x)->_left == x
680 || get_parent(x)->_right == x);
681 assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x);
682 assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x);
683 assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y);
684 assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y);
685 assert(!is_decay(rbtree->root));
686 assert(!is_decay(x));
687 assert(!is_decay(y));
688 assert(!is_decay(x->_right));
689 assert(!is_decay(x->_left));
690 assert(!is_decay(y->_right));
691 assert(!is_decay(y->_left));
692 }
693
694 #else
695
696 /* non-rcu version */
697 static
698 void left_rotate(struct rcu_rbtree *rbtree,
699 struct rcu_rbtree_node *x)
700 {
701 struct rcu_rbtree_node *y;
702
703 lock_test_mutex();
704 y = x->_right;
705 x->_right = y->_left;
706 if (!rcu_rbtree_is_nil(rbtree, y->_left))
707 set_parent(y->_left, x, IS_RIGHT);
708 set_parent(y, get_parent(x), get_pos(x));
709 if (rcu_rbtree_is_nil(rbtree, get_parent(x)))
710 rbtree->root = y;
711 else if (x == get_parent(x)->_left) {
712 get_parent(x)->_left = y;
713 } else {
714 get_parent(x)->_right = y;
715 }
716 y->_left = x;
717 set_parent(x, y, IS_LEFT);
718 unlock_test_mutex();
719 }
720
721 #endif
722
723 #ifdef RBTREE_RCU_SUPPORT_ROTATE_RIGHT
724 static
725 void right_rotate(struct rcu_rbtree *rbtree,
726 struct rcu_rbtree_node *x)
727 {
728 struct rcu_rbtree_node *y, *y_right, *top, *top_child;
729 unsigned int top_child_pos;
730
731 y = x->_left;
732 y_right = y->_right;
733
734 /* Now operate on new copy, decay old versions */
735 x = dup_decay_node(rbtree, x);
736 y = dup_decay_node(rbtree, y);
737 y_right = dup_decay_node(rbtree, y_right);
738
739 /* Internal node modifications */
740 set_parent(y, get_parent(x), get_pos(x));
741 set_parent(x, y, IS_RIGHT);
742 set_right_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
743 set_left_dup_decay(rbtree, x, y_right, NULL, NULL, NULL);
744 assert(!is_decay(top));
745 assert(!is_decay(top_child));
746
747 if (!rcu_rbtree_is_nil(rbtree, y_right))
748 set_parent(y_right, x, IS_LEFT);
749
750 cmm_smp_wmb(); /* write into node before publish */
751
752 /* External references update (visible by readers) */
753 if (rcu_rbtree_is_nil(rbtree, top))
754 _CMM_STORE_SHARED(rbtree->root, top_child);
755 else if (top_child_pos == IS_RIGHT)
756 _CMM_STORE_SHARED(top->_right, top_child);
757 else
758 _CMM_STORE_SHARED(top->_left, top_child);
759
760 /* Point children to new copy (parent only used by updates/next/prev) */
761 set_parent(x->_right, get_decay(get_parent(x->_right)),
762 get_pos(x->_right));
763 set_parent(y->_left, get_decay(get_parent(y->_left)),
764 get_pos(y->_left));
765 if (!rcu_rbtree_is_nil(rbtree, y_right)) {
766 set_parent(y_right->_left,
767 get_decay(get_parent(y_right->_left)),
768 get_pos(y_right->_left));
769 set_parent(y_right->_right,
770 get_decay(get_parent(y_right->_right)),
771 get_pos(y_right->_right));
772 }
773 set_right_update_decay(rbtree, y, x);
774
775
776 /* Sanity checks */
777 assert(y == rbtree->root || get_parent(y)->_right == y
778 || get_parent(y)->_left == y);
779 assert(x == rbtree->root || get_parent(x)->_right == x
780 || get_parent(x)->_left == x);
781 assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x);
782 assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x);
783 assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y);
784 assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y);
785 assert(!is_decay(rbtree->root));
786 assert(!is_decay(x));
787 assert(!is_decay(y));
788 assert(!is_decay(x->_left));
789 assert(!is_decay(x->_right));
790 assert(!is_decay(y->_left));
791 assert(!is_decay(y->_right));
792 }
793
794 #else
795
796 /* non-rcu version */
797 static
798 void right_rotate(struct rcu_rbtree *rbtree,
799 struct rcu_rbtree_node *x)
800 {
801 struct rcu_rbtree_node *y;
802
803 lock_test_mutex();
804 y = x->_left;
805 x->_left = y->_right;
806 if (!rcu_rbtree_is_nil(rbtree, y->_right))
807 set_parent(y->_right, x, IS_LEFT);
808 set_parent(y, get_parent(x), get_pos(x));
809 if (rcu_rbtree_is_nil(rbtree, get_parent(x)))
810 rbtree->root = y;
811 else if (x == get_parent(x)->_right) {
812 get_parent(x)->_right = y;
813 } else {
814 get_parent(x)->_left = y;
815 }
816 y->_right = x;
817 set_parent(x, y, IS_RIGHT);
818 unlock_test_mutex();
819 }
820
821 #endif
822
823 static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
824 struct rcu_rbtree_node *z)
825 {
826 struct rcu_rbtree_node *y;
827
828 dbg_printf("insert fixup %p\n", z->key);
829 assert(!is_decay(rbtree->root));
830
831 while (get_parent(z)->color == COLOR_RED) {
832 if (get_parent(z) == get_parent(get_parent(z))->_left) {
833 y = get_parent(get_parent(z))->_right;
834 if (y->color == COLOR_RED) {
835 get_parent(z)->color = COLOR_BLACK;
836 y->color = COLOR_BLACK;
837 get_parent(get_parent(z))->color = COLOR_RED;
838 z = get_parent(get_parent(z));
839 } else {
840 if (z == get_parent(z)->_right) {
841 z = get_parent(z);
842 left_rotate(rbtree, z);
843 z = get_decay(z);
844 assert(!is_decay(rbtree->root));
845 }
846 get_parent(z)->color = COLOR_BLACK;
847 get_parent(get_parent(z))->color = COLOR_RED;
848 assert(!is_decay(z));
849 assert(!is_decay(get_parent(z)));
850 assert(!is_decay(get_parent(get_parent(z))));
851 right_rotate(rbtree, get_parent(get_parent(z)));
852 assert(!is_decay(z));
853 assert(!is_decay(rbtree->root));
854 }
855 } else {
856 y = get_parent(get_parent(z))->_left;
857 if (y->color == COLOR_RED) {
858 get_parent(z)->color = COLOR_BLACK;
859 y->color = COLOR_BLACK;
860 get_parent(get_parent(z))->color = COLOR_RED;
861 z = get_parent(get_parent(z));
862 } else {
863 if (z == get_parent(z)->_left) {
864 z = get_parent(z);
865 right_rotate(rbtree, z);
866 z = get_decay(z);
867 assert(!is_decay(rbtree->root));
868 }
869 get_parent(z)->color = COLOR_BLACK;
870 get_parent(get_parent(z))->color = COLOR_RED;
871 left_rotate(rbtree, get_parent(get_parent(z)));
872 assert(!is_decay(z));
873 assert(!is_decay(rbtree->root));
874 }
875 }
876 }
877 rbtree->root->color = COLOR_BLACK;
878 }
879
880 /*
881 * rcu_rbtree_insert - Insert a node in the RCU rbtree
882 *
883 * Returns 0 on success, or < 0 on error.
884 */
885 int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
886 struct rcu_rbtree_node *z)
887 {
888 struct rcu_rbtree_node *x, *y, *top, *top_child;
889 unsigned int top_child_pos;
890
891 dbg_printf("insert %p\n", z->key);
892 assert(!is_decay(rbtree->root));
893
894 y = make_nil(rbtree);
895 x = rbtree->root;
896 while (!rcu_rbtree_is_nil(rbtree, x)) {
897 y = x;
898 if (rbtree->comp(z->key, x->key) < 0)
899 x = x->_left;
900 else
901 x = x->_right;
902 }
903
904 z->_left = make_nil(rbtree);
905 z->_right = make_nil(rbtree);
906 z->min_child_key = z->key;
907 z->max_child_key = z->key;
908 z->color = COLOR_RED;
909 z->decay_next = NULL;
910
911 if (rcu_rbtree_is_nil(rbtree, y))
912 set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */
913 else if (rbtree->comp(z->key, y->key) < 0)
914 set_parent(z, y, IS_LEFT);
915 else
916 set_parent(z, y, IS_RIGHT);
917
918 /*
919 * Order stores to z (children/parents) before stores that will make it
920 * visible to the rest of the tree.
921 */
922 cmm_smp_wmb();
923
924 if (rcu_rbtree_is_nil(rbtree, y)) {
925 _CMM_STORE_SHARED(rbtree->root, z);
926 } else if (rbtree->comp(z->key, y->key) < 0) {
927 set_left_dup_decay(rbtree, y, z, &top, &top_child,
928 &top_child_pos);
929 if (rcu_rbtree_is_nil(rbtree, top))
930 _CMM_STORE_SHARED(rbtree->root, top_child);
931 else if (top_child_pos == IS_LEFT)
932 _CMM_STORE_SHARED(top->_left, top_child);
933 else
934 _CMM_STORE_SHARED(top->_right, top_child);
935 set_left_update_decay(rbtree, y, z);
936 } else {
937 set_right_dup_decay(rbtree, y, z, &top, &top_child,
938 &top_child_pos);
939 if (rcu_rbtree_is_nil(rbtree, top))
940 _CMM_STORE_SHARED(rbtree->root, top_child);
941 else if (top_child_pos == IS_LEFT)
942 _CMM_STORE_SHARED(top->_left, top_child);
943 else
944 _CMM_STORE_SHARED(top->_right, top_child);
945 set_right_update_decay(rbtree, y, z);
946 }
947 rcu_rbtree_insert_fixup(rbtree, z);
948 /*
949 * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
950 */
951 cmm_smp_wmc();
952 show_tree(rbtree);
953
954 return 0;
955 }
956
957 /*
958 * Transplant v into u position.
959 */
960
961 #ifdef RBTREE_RCU_SUPPORT_TRANSPLANT
962
963 static
964 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
965 struct rcu_rbtree_node *u,
966 struct rcu_rbtree_node *v,
967 unsigned int copy_parents)
968 {
969 struct rcu_rbtree_node *top, *top_child;
970 unsigned int top_child_pos;
971
972 dbg_printf("transplant %p\n", v->key);
973
974 if (!rcu_rbtree_is_nil(rbtree, v))
975 v = dup_decay_node(rbtree, v);
976
977 if (rcu_rbtree_is_nil(rbtree, get_parent(u))) {
978 /* pos is arbitrary for root node */
979 set_parent(v, get_parent(u), IS_RIGHT);
980 cmm_smp_wmb(); /* write into node before publish */
981 _CMM_STORE_SHARED(rbtree->root, v);
982 } else {
983 set_parent(v, get_parent(u), get_pos(u));
984 cmm_smp_wmb(); /* write into node before publish */
985
986 if (get_pos(u) == IS_LEFT) {
987 _set_left_dup_decay(rbtree, get_parent(u), v,
988 &top, &top_child, &top_child_pos,
989 copy_parents);
990 } else {
991 assert(copy_parents);
992 set_right_dup_decay(rbtree, get_parent(u), v,
993 &top, &top_child, &top_child_pos);
994 }
995
996 if (rcu_rbtree_is_nil(rbtree, top))
997 _CMM_STORE_SHARED(rbtree->root, top_child);
998 else if (top_child_pos == IS_LEFT)
999 _CMM_STORE_SHARED(top->_left, top_child);
1000 else
1001 _CMM_STORE_SHARED(top->_right, top_child);
1002
1003 /* Point children to new copy (parent only used by updates/next/prev) */
1004 if (get_pos(u) == IS_LEFT) {
1005 if (copy_parents)
1006 set_left_update_decay(rbtree, get_parent(u), v);
1007 } else {
1008 assert(copy_parents);
1009 set_right_update_decay(rbtree, get_parent(u), v);
1010 }
1011 }
1012
1013 /* Point children to new copy (parent only used by updates/next/prev) */
1014 if (!rcu_rbtree_is_nil(rbtree, v)) {
1015 set_parent(v->_right, get_decay(get_parent(v->_right)),
1016 get_pos(v->_right));
1017 set_parent(v->_left, get_decay(get_parent(v->_left)),
1018 get_pos(v->_left));
1019 }
1020 assert(!is_decay(rbtree->root));
1021 }
1022
1023 #else
1024
1025 /* Non-RCU version */
1026 static
1027 void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
1028 struct rcu_rbtree_node *u,
1029 struct rcu_rbtree_node *v,
1030 unsigned int copy_parents)
1031 {
1032 dbg_printf("transplant %p\n", v->key);
1033
1034 lock_test_mutex();
1035 if (rcu_rbtree_is_nil(rbtree, get_parent(u)))
1036 rbtree->root = v;
1037 else if (u == get_parent(u)->_left)
1038 get_parent(u)->_left = v;
1039 else
1040 get_parent(u)->_right = v;
1041 set_parent(v, get_parent(u), get_pos(u));
1042 unlock_test_mutex();
1043 }
1044
1045 #endif
1046
1047 static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
1048 struct rcu_rbtree_node *x)
1049 {
1050 dbg_printf("remove fixup %p\n", x->key);
1051
1052 while (x != rbtree->root && x->color == COLOR_BLACK) {
1053 assert(!is_decay(get_parent(x)));
1054 assert(!is_decay(get_parent(x)->_left));
1055 if (x == get_parent(x)->_left) {
1056 struct rcu_rbtree_node *w;
1057
1058 w = get_parent(x)->_right;
1059
1060 if (w->color == COLOR_RED) {
1061 w->color = COLOR_BLACK;
1062 get_parent(x)->color = COLOR_RED;
1063 left_rotate(rbtree, get_parent(x));
1064 x = get_decay(x);
1065 assert(!is_decay(rbtree->root));
1066 w = get_parent(x)->_right;
1067 }
1068 if (w->_left->color == COLOR_BLACK
1069 && w->_right->color == COLOR_BLACK) {
1070 w->color = COLOR_RED;
1071 x = get_parent(x);
1072 assert(!is_decay(rbtree->root));
1073 assert(!is_decay(x));
1074 } else {
1075 if (w->_right->color == COLOR_BLACK) {
1076 w->_left->color = COLOR_BLACK;
1077 w->color = COLOR_RED;
1078 right_rotate(rbtree, w);
1079 assert(!is_decay(rbtree->root));
1080 x = get_decay(x);
1081 w = get_parent(x)->_right;
1082 }
1083 w->color = get_parent(x)->color;
1084 get_parent(x)->color = COLOR_BLACK;
1085 w->_right->color = COLOR_BLACK;
1086 left_rotate(rbtree, get_parent(x));
1087 assert(!is_decay(rbtree->root));
1088 x = rbtree->root;
1089 }
1090 } else {
1091 struct rcu_rbtree_node *w;
1092
1093 w = get_parent(x)->_left;
1094
1095 if (w->color == COLOR_RED) {
1096 w->color = COLOR_BLACK;
1097 get_parent(x)->color = COLOR_RED;
1098 right_rotate(rbtree, get_parent(x));
1099 assert(!is_decay(rbtree->root));
1100 x = get_decay(x);
1101 w = get_parent(x)->_left;
1102 }
1103 if (w->_right->color == COLOR_BLACK
1104 && w->_left->color == COLOR_BLACK) {
1105 w->color = COLOR_RED;
1106 x = get_parent(x);
1107 assert(!is_decay(rbtree->root));
1108 assert(!is_decay(x));
1109 } else {
1110 if (w->_left->color == COLOR_BLACK) {
1111 w->_right->color = COLOR_BLACK;
1112 w->color = COLOR_RED;
1113 left_rotate(rbtree, w);
1114 assert(!is_decay(rbtree->root));
1115 x = get_decay(x);
1116 w = get_parent(x)->_left;
1117 }
1118 w->color = get_parent(x)->color;
1119 get_parent(x)->color = COLOR_BLACK;
1120 w->_left->color = COLOR_BLACK;
1121 right_rotate(rbtree, get_parent(x));
1122 assert(!is_decay(rbtree->root));
1123 x = rbtree->root;
1124 }
1125 }
1126 }
1127 x->color = COLOR_BLACK;
1128 }
1129
1130 /*
1131 * Delete z. All non-copied children left/right positions are unchanged.
1132 */
1133 static
1134 void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
1135 struct rcu_rbtree_node *z,
1136 struct rcu_rbtree_node *y)
1137 {
1138 struct rcu_rbtree_node *x, *top, *top_child;
1139 unsigned int top_child_pos;
1140
1141 dbg_printf("remove nonil %p\n", z->key);
1142 show_tree(rbtree);
1143
1144 assert(!is_decay(z));
1145 assert(!is_decay(y));
1146 assert(!is_decay(y->_right));
1147 assert(!is_decay(get_parent(y)));
1148 x = y->_right;
1149 assert(!is_decay(x));
1150 if (get_parent(y) == z) {
1151 y = dup_decay_node(rbtree, y);
1152 set_parent(x, y, get_pos(x)); /* parent for nil */
1153 /* y is z's right node: set left will just update y */
1154 set_left_dup_decay(rbtree, y, z->_left,
1155 &top, &top_child, &top_child_pos);
1156 assert(top_child == y);
1157 rcu_rbtree_transplant(rbtree, z, y, 1);
1158 } else {
1159 struct rcu_rbtree_node *oy_right, *z_right;
1160
1161 /*
1162 * Need to make sure y is always visible by readers.
1163 */
1164 y = rcu_rbtree_min_dup_decay(rbtree, z->_right, &z_right);
1165 assert(!is_decay(y));
1166 assert(!is_decay(z));
1167 oy_right = y->_right;
1168
1169 /*
1170 * The max child key of z_right does not change, because
1171 * we're only changing its left children.
1172 */
1173 y->_right = z_right;
1174 set_parent(y->_right, y, IS_RIGHT);
1175 if (rcu_rbtree_is_nil(rbtree, y->_right))
1176 y->max_child_key = y->key;
1177 else
1178 y->max_child_key = y->_right->max_child_key;
1179
1180 assert(!is_decay(z->_left));
1181 y->_left = z->_left;
1182 if (rcu_rbtree_is_nil(rbtree, y->_left))
1183 y->min_child_key = y->key;
1184 else
1185 y->min_child_key = y->_left->min_child_key;
1186
1187 assert(!is_decay(oy_right));
1188 /*
1189 * Transplant of oy_right to old y's location will only
1190 * trigger a min/max update of the already copied branch
1191 * (which is not visible yet). We are transplanting
1192 * oy_right as a left child of old y's parent, so the
1193 * min values update propagated upward necessarily stops
1194 * at z_right.
1195 */
1196 rcu_rbtree_transplant(rbtree, y, oy_right, 0);
1197 rcu_rbtree_transplant(rbtree, z, y, 1);
1198 /* Update children */
1199 (void) rcu_rbtree_min_update_decay(rbtree, y->_right);
1200 }
1201 y = get_decay(y);
1202 assert(!is_decay(z));
1203 assert(!is_decay(z->_left));
1204 y->color = z->color;
1205 set_parent(y->_left, y, IS_LEFT);
1206 set_parent(y->_right, get_decay(get_parent(y->_right)), IS_RIGHT);
1207 assert(!is_decay(y->_left));
1208 assert(!is_decay(y->_right));
1209 }
1210
1211 int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
1212 struct rcu_rbtree_node *z)
1213 {
1214 struct rcu_rbtree_node *x, *y;
1215 unsigned int y_original_color;
1216
1217 assert(!is_decay(rbtree->root));
1218 dbg_printf("remove %p\n", z->key);
1219 show_tree(rbtree);
1220
1221 assert(!is_decay(z));
1222 y = z;
1223 y_original_color = y->color;
1224
1225 if (rcu_rbtree_is_nil(rbtree, z->_left)) {
1226 rcu_rbtree_transplant(rbtree, z, z->_right, 1);
1227 assert(!is_decay(z));
1228 x = get_decay(z->_right);
1229 show_tree(rbtree);
1230 } else if (rcu_rbtree_is_nil(rbtree, z->_right)) {
1231 rcu_rbtree_transplant(rbtree, z, z->_left, 1);
1232 assert(!is_decay(z));
1233 x = get_decay(z->_left);
1234 show_tree(rbtree);
1235 } else {
1236 y = rcu_rbtree_min(rbtree, z->_right);
1237 assert(!is_decay(y));
1238 y_original_color = y->color;
1239 x = y->_right;
1240 rcu_rbtree_remove_nonil(rbtree, z, y);
1241 x = get_decay(x);
1242 show_tree(rbtree);
1243 }
1244 if (y_original_color == COLOR_BLACK)
1245 rcu_rbtree_remove_fixup(rbtree, x);
1246 show_tree(rbtree);
1247 /*
1248 * Commit all _CMM_STORE_SHARED().
1249 */
1250 cmm_smp_wmc();
1251
1252 return 0;
1253 }
Userspace RCU (urcu) for Linux
This page took 0.058216 seconds and 5 git commands to generate.