This source file includes following definitions.
- opal_interval_tree_construct
- opal_interval_tree_destruct
- opal_interval_tree_reader_get_token
- opal_interval_tree_reader_return_token
- opal_interval_tree_init
- opal_interval_tree_write_trylock
- opal_interval_tree_write_lock
- opal_interval_tree_write_unlock
- opal_interval_tree_insert_fixup_helper
- opal_interval_tree_insert_fixup
- opal_interval_tree_delete_fixup_helper
- opal_interval_tree_delete_fixup
- opal_interval_tree_gc_clean
- opal_interval_tree_insert
- opal_interval_tree_find_interval
- opal_interval_tree_find_node
- opal_interval_tree_find_overlapping
- opal_interval_tree_depth_node
- opal_interval_tree_depth
- rp_publish
- rp_wait_for_readers
- rp_free_wait
- rp_free
- opal_interval_tree_node_copy
- opal_interval_tree_delete_leaf
- opal_interval_tree_delete_interior
- opal_interval_tree_delete
- opal_interval_tree_destroy
- opal_interval_tree_next
- opal_interval_tree_insert_node
- inorder_traversal
- inorder_destroy
- opal_interval_tree_traverse
- left_rotate
- right_rotate
- opal_interval_tree_size
- opal_interval_tree_verify_node
- opal_interval_tree_black_depth
- opal_interval_tree_verify
- opal_interval_tree_dump_node
- opal_interval_tree_dump
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 #include "opal_config.h"
26
27 #include "opal/class/opal_interval_tree.h"
28 #include <limits.h>
29
30
31 static void opal_interval_tree_insert_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node);
32
33
34 static void opal_interval_tree_delete_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
35 opal_interval_tree_node_t *parent);
36 static void opal_interval_tree_insert_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *x);
37
38 static opal_interval_tree_node_t *opal_interval_tree_next (opal_interval_tree_t *tree,
39 opal_interval_tree_node_t *node);
40 static opal_interval_tree_node_t * opal_interval_tree_find_node(opal_interval_tree_t *tree,
41 uint64_t low, uint64_t high,
42 bool exact, void *data);
43
44 static opal_interval_tree_node_t *left_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x);
45 static opal_interval_tree_node_t *right_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x);
46
47 static void inorder_destroy(opal_interval_tree_t *tree, opal_interval_tree_node_t * node);
48
49 #define max(x,y) (((x) > (y)) ? (x) : (y))
50
51
52
53
54
55
56
57
58 static void opal_interval_tree_construct (opal_interval_tree_t *tree)
59 {
60 OBJ_CONSTRUCT(&tree->root, opal_interval_tree_node_t);
61 OBJ_CONSTRUCT(&tree->nill, opal_interval_tree_node_t);
62 OBJ_CONSTRUCT(&tree->free_list, opal_free_list_t);
63 OBJ_CONSTRUCT(&tree->gc_list, opal_list_t);
64
65
66 tree->nill.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
67 tree->nill.left = tree->nill.right = tree->nill.parent = &tree->nill;
68 tree->nill.max = 0;
69 tree->nill.data = NULL;
70
71
72 tree->root.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
73 tree->root.left = tree->root.right = tree->root.parent = &tree->nill;
74
75
76 tree->root.low = (uint64_t) -1;
77 tree->root.data = NULL;
78
79
80 tree->tree_size = 0;
81 tree->lock = 0;
82 tree->reader_count = 0;
83 tree->epoch = 0;
84
85
86
87 for (int i = 0 ; i < OPAL_INTERVAL_TREE_MAX_READERS ; ++i) {
88 tree->reader_epochs[i] = UINT_MAX;
89 }
90 }
91
92
93
94
95
96
97 static void opal_interval_tree_destruct (opal_interval_tree_t *tree)
98 {
99 opal_interval_tree_destroy (tree);
100
101 OBJ_DESTRUCT(&tree->free_list);
102 OBJ_DESTRUCT(&tree->root);
103 OBJ_DESTRUCT(&tree->nill);
104 }
105
106
107 OBJ_CLASS_INSTANCE(opal_interval_tree_node_t, opal_free_list_item_t, NULL, NULL);
108 OBJ_CLASS_INSTANCE(opal_interval_tree_t, opal_object_t, opal_interval_tree_construct,
109 opal_interval_tree_destruct);
110
111 typedef int32_t opal_interval_tree_token_t;
112
113
114
115
116 static opal_interval_tree_token_t opal_interval_tree_reader_get_token (opal_interval_tree_t *tree)
117 {
118 opal_interval_tree_token_t token = -1;
119
120 if (token < 0) {
121 int32_t reader_count = tree->reader_count;
122
123
124
125 token = tree->reader_id++ % OPAL_INTERVAL_TREE_MAX_READERS;
126 while (OPAL_UNLIKELY(reader_count <= token)) {
127 if (opal_atomic_compare_exchange_strong_32 (&tree->reader_count, &reader_count, token + 1)) {
128 break;
129 }
130 }
131 }
132
133 while (!OPAL_ATOMIC_COMPARE_EXCHANGE_STRONG_32((opal_atomic_int32_t *) &tree->reader_epochs[token],
134 &(int32_t) {UINT_MAX}, tree->epoch));
135
136 return token;
137 }
138
139 static void opal_interval_tree_reader_return_token (opal_interval_tree_t *tree, opal_interval_tree_token_t token)
140 {
141 tree->reader_epochs[token] = UINT_MAX;
142 }
143
144
145 int opal_interval_tree_init (opal_interval_tree_t *tree)
146 {
147 return opal_free_list_init (&tree->free_list, sizeof(opal_interval_tree_node_t),
148 opal_cache_line_size, OBJ_CLASS(opal_interval_tree_node_t),
149 0, opal_cache_line_size, 0, -1 , 128, NULL, 0, NULL, NULL, NULL);
150 }
151
152 static bool opal_interval_tree_write_trylock (opal_interval_tree_t *tree)
153 {
154 opal_atomic_rmb ();
155 return !(tree->lock || opal_atomic_swap_32 (&tree->lock, 1));
156 }
157
158 static void opal_interval_tree_write_lock (opal_interval_tree_t *tree)
159 {
160 while (!opal_interval_tree_write_trylock (tree));
161 }
162
163 static void opal_interval_tree_write_unlock (opal_interval_tree_t *tree)
164 {
165 opal_atomic_wmb ();
166 tree->lock = 0;
167 }
168
169 static void opal_interval_tree_insert_fixup_helper (opal_interval_tree_t *tree, opal_interval_tree_node_t *node) {
170 opal_interval_tree_node_t *y, *parent = node->parent;
171 bool rotate_right = false;
172
173 if (parent->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
174 return;
175 }
176
177 if (parent == parent->parent->left) {
178 y = parent->parent->right;
179 rotate_right = true;
180 } else {
181 y = parent->parent->left;
182 }
183
184 if (y->color == OPAL_INTERVAL_TREE_COLOR_RED) {
185 parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
186 y->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
187 parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
188 opal_interval_tree_insert_fixup_helper (tree, parent->parent);
189 return;
190 }
191
192 if (rotate_right) {
193 if (node == parent->right) {
194 node = left_rotate (tree, parent);
195 parent = node->parent;
196 }
197
198 parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
199 parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
200 (void) right_rotate(tree, parent->parent);
201 } else {
202 if (node == parent->left) {
203 node = right_rotate(tree, parent);
204 parent = node->parent;
205 }
206 parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
207 parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
208 (void) left_rotate(tree, parent->parent);
209 }
210
211 opal_interval_tree_insert_fixup_helper (tree, node);
212 }
213
214 static void opal_interval_tree_insert_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *node) {
215
216
217
218 opal_interval_tree_insert_fixup_helper (tree, node);
219
220
221 tree->root.left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
222 }
223
224
225
226
227
228
229
230
231
232
233 static inline opal_interval_tree_node_t *
234 opal_interval_tree_delete_fixup_helper (opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
235 opal_interval_tree_node_t *parent, const bool left)
236 {
237 opal_interval_tree_node_t *w;
238
239
240 w = left ? parent->right : parent->left;
241 if (w->color == OPAL_INTERVAL_TREE_COLOR_RED) {
242 w->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
243 parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
244 if (left) {
245 (void) left_rotate(tree, parent);
246 w = parent->right;
247 } else {
248 (void) right_rotate(tree, parent);
249 w = parent->left;
250 }
251 }
252
253 if ((w->left->color == OPAL_INTERVAL_TREE_COLOR_BLACK) && (w->right->color == OPAL_INTERVAL_TREE_COLOR_BLACK)) {
254 w->color = OPAL_INTERVAL_TREE_COLOR_RED;
255 return parent;
256 }
257
258 if (left) {
259 if (w->right->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
260 w->left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
261 w->color = OPAL_INTERVAL_TREE_COLOR_RED;
262 (void) right_rotate(tree, w);
263 w = parent->right;
264 }
265 w->color = parent->color;
266 parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
267 w->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
268 (void) left_rotate(tree, parent);
269 } else {
270 if (w->left->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
271 w->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
272 w->color = OPAL_INTERVAL_TREE_COLOR_RED;
273 (void) left_rotate(tree, w);
274 w = parent->left;
275 }
276 w->color = parent->color;
277 parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
278 w->left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
279 (void) right_rotate(tree, parent);
280 }
281
282
283 return tree->root.left;
284 }
285
286
287 static void opal_interval_tree_delete_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
288 opal_interval_tree_node_t *parent)
289 {
290 while ((node != tree->root.left) && (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK)) {
291 node = opal_interval_tree_delete_fixup_helper (tree, node, parent, node == parent->left);
292 parent = node->parent;
293 }
294
295 node->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
296 tree->nill.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
297 }
298
299
300
301 static void opal_interval_tree_gc_clean (opal_interval_tree_t *tree)
302 {
303 opal_interval_tree_node_t *node, *next;
304 uint32_t oldest_epoch = UINT_MAX;
305
306 if (0 == opal_list_get_size (&tree->gc_list)) {
307 return;
308 }
309
310 for (int i = 0 ; i < tree->reader_count ; ++i) {
311 oldest_epoch = (oldest_epoch < tree->reader_epochs[i]) ? oldest_epoch : tree->reader_epochs[i];
312 }
313
314 OPAL_LIST_FOREACH_SAFE(node, next, &tree->gc_list, opal_interval_tree_node_t) {
315 if (node->epoch < oldest_epoch) {
316 opal_list_remove_item (&tree->gc_list, &node->super.super);
317 opal_free_list_return_st (&tree->free_list, &node->super);
318 }
319 }
320 }
321
322
323 int opal_interval_tree_insert (opal_interval_tree_t *tree, void *value, uint64_t low, uint64_t high)
324 {
325 opal_interval_tree_node_t * node;
326
327 if (low > high) {
328 return OPAL_ERR_BAD_PARAM;
329 }
330
331 opal_interval_tree_write_lock (tree);
332
333 opal_interval_tree_gc_clean (tree);
334
335
336 node = (opal_interval_tree_node_t *) opal_free_list_get (&tree->free_list);
337 if (OPAL_UNLIKELY(NULL == node)) {
338 opal_interval_tree_write_unlock (tree);
339 return OPAL_ERR_OUT_OF_RESOURCE;
340 }
341
342
343 node->data = value;
344 node->low = low;
345 node->high = high;
346 node->max = high;
347 node->epoch = tree->epoch;
348
349
350 opal_interval_tree_insert_node (tree, node);
351
352 opal_interval_tree_insert_fixup (tree, node);
353 opal_interval_tree_write_unlock (tree);
354
355 return OPAL_SUCCESS;
356 }
357
358 static opal_interval_tree_node_t *opal_interval_tree_find_interval(opal_interval_tree_t *tree, opal_interval_tree_node_t *node, uint64_t low,
359 uint64_t high, bool exact, void *data)
360 {
361 if (node == &tree->nill) {
362 return NULL;
363 }
364
365 if (((exact && node->low == low && node->high == high) || (!exact && node->low <= low && node->high >= high)) &&
366 (!data || node->data == data)) {
367 return node;
368 }
369
370 if (low <= node->low) {
371 return opal_interval_tree_find_interval (tree, node->left, low, high, exact, data);
372 }
373
374 return opal_interval_tree_find_interval (tree, node->right, low, high, exact, data);
375 }
376
377
378
379
380 static opal_interval_tree_node_t *opal_interval_tree_find_node(opal_interval_tree_t *tree, uint64_t low, uint64_t high, bool exact, void *data)
381 {
382 return opal_interval_tree_find_interval (tree, tree->root.left, low, high, exact, data);
383 }
384
385 void *opal_interval_tree_find_overlapping (opal_interval_tree_t *tree, uint64_t low, uint64_t high)
386 {
387 opal_interval_tree_token_t token;
388 opal_interval_tree_node_t *node;
389
390 token = opal_interval_tree_reader_get_token (tree);
391 node = opal_interval_tree_find_node (tree, low, high, true, NULL);
392 opal_interval_tree_reader_return_token (tree, token);
393
394 return node ? node->data : NULL;
395 }
396
397 static size_t opal_interval_tree_depth_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
398 {
399 if (&tree->nill == node) {
400 return 0;
401 }
402
403 return 1 + max (opal_interval_tree_depth_node (tree, node->right), opal_interval_tree_depth_node (tree, node->left));
404 }
405
406 size_t opal_interval_tree_depth (opal_interval_tree_t *tree)
407 {
408 opal_interval_tree_token_t token;
409 size_t depth;
410
411 token = opal_interval_tree_reader_get_token (tree);
412 depth = opal_interval_tree_depth_node (tree, &tree->root);
413 opal_interval_tree_reader_return_token (tree, token);
414
415 return depth;
416 }
417
418
419 static inline void rp_publish (opal_interval_tree_node_t **ptr, opal_interval_tree_node_t *node)
420 {
421
422 opal_atomic_wmb ();
423
424 *ptr = node;
425 }
426
427
428 static inline void rp_wait_for_readers (opal_interval_tree_t *tree)
429 {
430 uint32_t epoch_id = ++tree->epoch;
431
432
433 for (int i = 0 ; i < tree->reader_count ; ++i) {
434 while (tree->reader_epochs[i] < epoch_id);
435 }
436 }
437
438
439 static inline void rp_free_wait (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
440 {
441 rp_wait_for_readers (tree);
442
443 opal_free_list_return_st (&tree->free_list, &node->super);
444 }
445
446
447 static inline void rp_free (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
448 {
449 opal_list_append (&tree->gc_list, &node->super.super);
450 }
451
452 static opal_interval_tree_node_t *opal_interval_tree_node_copy (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
453 {
454 opal_interval_tree_node_t *copy = (opal_interval_tree_node_t *) opal_free_list_wait_st (&tree->free_list);
455 size_t color_offset = offsetof(opal_interval_tree_node_t, color);
456 assert (NULL != copy);
457 memcpy ((unsigned char *) copy + color_offset, (unsigned char *) node + color_offset,
458 sizeof (*node) - color_offset);
459 return copy;
460 }
461
462
463 static void opal_interval_tree_delete_leaf (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
464 {
465 const opal_interval_tree_node_t *nill = &tree->nill;
466 opal_interval_tree_node_t **parent_ptr, *next, *parent = node->parent;
467 opal_interval_tree_nodecolor_t color = node->color;
468
469 assert (node->left == nill || node->right == nill);
470
471 parent_ptr = (parent->right == node) ? &parent->right : &parent->left;
472
473 next = (node->right == nill) ? node->left : node->right;
474
475 next->parent = node->parent;
476 rp_publish (parent_ptr, next);
477
478 rp_free (tree, node);
479
480 if (OPAL_INTERVAL_TREE_COLOR_BLACK == color) {
481 if (OPAL_INTERVAL_TREE_COLOR_RED == next->color) {
482 next->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
483 } else {
484 opal_interval_tree_delete_fixup (tree, next, parent);
485 }
486 }
487 }
488
489 static void opal_interval_tree_delete_interior (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
490 {
491 opal_interval_tree_node_t **parent_ptr, *next, *next_copy, *parent = node->parent;
492 opal_interval_tree_nodecolor_t color = node->color, next_color;
493
494 parent_ptr = (parent->right == node) ? &parent->right : &parent->left;
495 next = opal_interval_tree_next (tree, node);
496 next_color = next->color;
497
498 if (next != node->right) {
499
500 next_copy = opal_interval_tree_node_copy (tree, next);
501 next_copy->color = node->color;
502 next_copy->left = node->left;
503 next_copy->left->parent = next_copy;
504 next_copy->right = node->right;
505 next_copy->right->parent = next_copy;
506 next_copy->parent = node->parent;
507
508 rp_publish (parent_ptr, next_copy);
509 rp_free_wait (tree, node);
510
511 opal_interval_tree_delete_leaf (tree, next);
512 } else {
513
514 next->color = color;
515 next->left = node->left;
516 next->left->parent = next;
517 next->parent = node->parent;
518 rp_publish (parent_ptr, next);
519 rp_free (tree, node);
520
521
522
523 if (OPAL_INTERVAL_TREE_COLOR_BLACK == next_color) {
524 if (OPAL_INTERVAL_TREE_COLOR_RED == next->right->color) {
525 next->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
526 } else {
527 opal_interval_tree_delete_fixup (tree, next->right, next);
528 }
529 }
530 }
531 }
532
533
534 int opal_interval_tree_delete (opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data)
535 {
536 opal_interval_tree_node_t *node;
537
538 opal_interval_tree_write_lock (tree);
539 node = opal_interval_tree_find_node (tree, low, high, true, data);
540 if (NULL == node) {
541 opal_interval_tree_write_unlock (tree);
542 return OPAL_ERR_NOT_FOUND;
543 }
544
545
546
547
548
549
550
551
552
553
554
555 if ((node->left == &tree->nill) || (node->right == &tree->nill)) {
556
557 opal_interval_tree_delete_leaf (tree, node);
558 } else {
559
560 opal_interval_tree_delete_interior (tree, node);
561 }
562
563 --tree->tree_size;
564
565 opal_interval_tree_write_unlock (tree);
566
567 return OPAL_SUCCESS;
568 }
569
570 int opal_interval_tree_destroy (opal_interval_tree_t *tree)
571 {
572
573 inorder_destroy(tree, &tree->root);
574 tree->tree_size = 0;
575 return OPAL_SUCCESS;
576 }
577
578
579
580 static opal_interval_tree_node_t *opal_interval_tree_next (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
581 {
582 opal_interval_tree_node_t *p = node->right;
583
584 if (p == &tree->nill) {
585 p = node->parent;
586 while (node == p->right) {
587 node = p;
588 p = p->parent;
589 }
590
591 if (p == &tree->root) {
592 return &tree->nill;
593 }
594
595 return p;
596 }
597
598 while (p->left != &tree->nill) {
599 p = p->left;
600 }
601
602 return p;
603 }
604
605
606
607
608 static void opal_interval_tree_insert_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
609 {
610 opal_interval_tree_node_t *parent = &tree->root;
611 opal_interval_tree_node_t *n = parent->left;
612 opal_interval_tree_node_t *nill = &tree->nill;
613
614
615 node->color = OPAL_INTERVAL_TREE_COLOR_RED;
616 node->parent = NULL;
617 node->left = nill;
618 node->right = nill;
619
620
621 while (n != nill) {
622 if (n->max < node->high) {
623 n->max = node->high;
624 }
625
626 parent = n;
627 n = ((node->low < n->low) ? n->left : n->right);
628 assert (nill == n || n->parent == parent);
629 }
630
631
632 if ((node->low < parent->low)) {
633 parent->left = node;
634 } else {
635 parent->right = node;
636 }
637
638
639 node->parent = parent;
640
641 ++tree->tree_size;
642 }
643
644 static int inorder_traversal (opal_interval_tree_t *tree, uint64_t low, uint64_t high,
645 bool partial_ok, opal_interval_tree_action_fn_t action,
646 opal_interval_tree_node_t * node, void *ctx)
647 {
648 int rc;
649
650 if (node == &tree->nill) {
651 return OPAL_SUCCESS;
652 }
653
654 rc = inorder_traversal(tree, low, high, partial_ok, action, node->left, ctx);
655 if (OPAL_SUCCESS != rc) {
656 return rc;
657 }
658
659 if ((!partial_ok && (node->low <= low && node->high >= high)) ||
660 (partial_ok && ((low >= node->low && low <= node->high) ||
661 (high >= node->low && high <= node->high) ||
662 (node->low >= low && node->low <= high) ||
663 (node->high >= high && node->high <= high)))) {
664 rc = action (node->low, node->high, node->data, ctx);
665 if (OPAL_SUCCESS != rc) {
666 return rc;
667 }
668 }
669
670 return inorder_traversal(tree, low, high, partial_ok, action, node->right, ctx);
671 }
672
673
674
675 static void inorder_destroy (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
676 {
677 if (node == &tree->nill) {
678 return;
679 }
680
681 inorder_destroy(tree, node->left);
682 inorder_destroy(tree, node->right);
683
684 if (node->left != &tree->nill) {
685 opal_free_list_return_st (&tree->free_list, &node->left->super);
686 }
687
688 if (node->right != &tree->nill) {
689 opal_free_list_return_st (&tree->free_list, &node->right->super);
690 }
691 }
692
693
694
695 int opal_interval_tree_traverse (opal_interval_tree_t *tree, uint64_t low, uint64_t high,
696 bool partial_ok, opal_interval_tree_action_fn_t action, void *ctx)
697 {
698 opal_interval_tree_token_t token;
699 int rc;
700
701 if (action == NULL) {
702 return OPAL_ERR_BAD_PARAM;
703 }
704
705 token = opal_interval_tree_reader_get_token (tree);
706 rc = inorder_traversal (tree, low, high, partial_ok, action, tree->root.left, ctx);
707 opal_interval_tree_reader_return_token (tree, token);
708 return rc;
709 }
710
711
712
713
714 static opal_interval_tree_node_t *left_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x)
715 {
716 opal_interval_tree_node_t *x_copy = x;
717 opal_interval_tree_node_t *y = x->right;
718 opal_interval_tree_node_t *parent = x->parent;
719
720
721 if (y->left != &tree->nill) {
722 y->left->parent = x_copy;
723 }
724
725
726 x_copy->parent = y;
727 x_copy->right = y->left;
728 x_copy->max = max (x_copy->high, max (x_copy->left->max, x_copy->left->max));
729
730 rp_publish (&y->left, x_copy);
731
732
733
734 if (x == parent->left) {
735 rp_publish (&parent->left, y);
736 } else {
737 rp_publish (&parent->right, y);
738 }
739
740
741 y->parent = parent;
742
743 return x_copy;
744 }
745
746
747
748
749
750 static opal_interval_tree_node_t *right_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x)
751 {
752 opal_interval_tree_node_t *x_copy = x;
753 opal_interval_tree_node_t *y = x->left;
754 opal_interval_tree_node_t *parent = x->parent;
755
756
757 if (y->right != &tree->nill) {
758 y->right->parent = x_copy;
759 }
760
761 x_copy->left = y->right;
762 x_copy->parent = y;
763
764 rp_publish (&y->right, x_copy);
765
766
767
768 y->max = x->max;
769 y->parent = parent;
770
771 if (parent->left == x) {
772 rp_publish (&parent->left, y);
773 } else {
774 rp_publish (&parent->right, y);
775 }
776
777 return x_copy;
778 }
779
780
781 size_t opal_interval_tree_size(opal_interval_tree_t *tree)
782 {
783 return tree->tree_size;
784 }
785
786 static bool opal_interval_tree_verify_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node, int black_depth,
787 int current_black_depth)
788 {
789 if (node == &tree->nill) {
790 return true;
791 }
792
793 if (OPAL_INTERVAL_TREE_COLOR_RED == node->color &&
794 (OPAL_INTERVAL_TREE_COLOR_BLACK != node->left->color ||
795 OPAL_INTERVAL_TREE_COLOR_BLACK != node->right->color)) {
796 fprintf (stderr, "Red node has a red child!\n");
797 return false;
798 }
799
800 if (OPAL_INTERVAL_TREE_COLOR_BLACK == node->color) {
801 current_black_depth++;
802 }
803
804 if (node->left == &tree->nill && node->right == &tree->nill) {
805 if (black_depth != current_black_depth) {
806 fprintf (stderr, "Found leaf with unexpected black depth: %d, expected: %d\n", current_black_depth, black_depth);
807 return false;
808 }
809
810 return true;
811 }
812
813 return opal_interval_tree_verify_node (tree, node->left, black_depth, current_black_depth) ||
814 opal_interval_tree_verify_node (tree, node->right, black_depth, current_black_depth);
815 }
816
817 static int opal_interval_tree_black_depth (opal_interval_tree_t *tree, opal_interval_tree_node_t *node, int depth)
818 {
819 if (node == &tree->nill) {
820 return depth;
821 }
822
823
824 if (OPAL_INTERVAL_TREE_COLOR_BLACK == node->color) {
825 depth++;
826 }
827
828 return opal_interval_tree_black_depth (tree, node->left, depth);
829 }
830
831 bool opal_interval_tree_verify (opal_interval_tree_t *tree)
832 {
833 int black_depth;
834
835 if (OPAL_INTERVAL_TREE_COLOR_BLACK != tree->root.left->color) {
836 fprintf (stderr, "Root node of tree is NOT black!\n");
837 return false;
838 }
839
840 if (OPAL_INTERVAL_TREE_COLOR_BLACK != tree->nill.color) {
841 fprintf (stderr, "Leaf node color is NOT black!\n");
842 return false;
843 }
844
845 black_depth = opal_interval_tree_black_depth (tree, tree->root.left, 0);
846
847 return opal_interval_tree_verify_node (tree, tree->root.left, black_depth, 0);
848 }
849
850 static void opal_interval_tree_dump_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node, int black_rank, FILE *fh)
851 {
852 const char *color = (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK) ? "black" : "red";
853 uintptr_t left = (uintptr_t) node->left, right = (uintptr_t) node->right;
854 opal_interval_tree_node_t *nill = &tree->nill;
855
856 if (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
857 ++black_rank;
858 }
859
860 if (nill == node) {
861 return;
862 }
863
864
865 if ((uintptr_t) nill == left) {
866 left = (uintptr_t) node | 0x1;
867 fprintf (fh, " Node%lx [color=black,label=nill];\n\n", left);
868 } else {
869 left = (uintptr_t) node->left;
870 }
871
872 if ((uintptr_t) nill == right) {
873 right = (uintptr_t) node | 0x2;
874 fprintf (fh, " Node%lx [color=black,label=nill];\n\n", right);
875 } else {
876 right = (uintptr_t) node->right;
877 }
878
879
880 fprintf (fh, " Node%lx [color=%s,shape=box,label=\"[0x%" PRIx64 ",0x%" PRIx64 "]\\nmax=0x%" PRIx64
881 "\\ndata=0x%lx\\nblack rank=%d\"];\n", (uintptr_t) node, color, node->low, node->high, node->max,
882 (uintptr_t) node->data, black_rank);
883 fprintf (fh, " Node%lx -> Node%lx;\n", (uintptr_t) node, left);
884 fprintf (fh, " Node%lx -> Node%lx;\n\n", (uintptr_t) node, right);
885 if (node != tree->root.left) {
886 fprintf (fh, " Node%lx -> Node%lx;\n\n", (uintptr_t) node, (uintptr_t) node->parent);
887 }
888 opal_interval_tree_dump_node (tree, node->left, black_rank, fh);
889 opal_interval_tree_dump_node (tree, node->right, black_rank, fh);
890 }
891
892 int opal_interval_tree_dump (opal_interval_tree_t *tree, const char *path)
893 {
894 FILE *fh;
895
896 fh = fopen (path, "w");
897 if (NULL == fh) {
898 return OPAL_ERR_BAD_PARAM;
899 }
900
901 fprintf (fh, "digraph {\n");
902 fprintf (fh, " graph [ordering=\"out\"];");
903 opal_interval_tree_dump_node (tree, tree->root.left, 0, fh);
904 fprintf (fh, "}\n");
905
906 fclose (fh);
907
908 return OPAL_SUCCESS;
909 }