| line |
true |
false |
branch |
|
59
|
1 |
149 |
if (IS_SENTINEL(node)) return NULL; |
|
60
|
380 |
149 |
while (NOT_SENTINEL(node->left)) |
|
66
|
1 |
108 |
if (IS_SENTINEL(node)) return NULL; |
|
67
|
416 |
108 |
while (NOT_SENTINEL(node->right)) |
|
73
|
77 |
0 |
while (node && node->parent) |
|
|
54 |
23 |
while (node && node->parent) |
|
77
|
23 |
0 |
return node && node->right && node->right->right == node->right? node : NULL; |
|
|
21 |
2 |
return node && node->right && node->right->right == node->right? node : NULL; |
|
|
21 |
0 |
return node && node->right && node->right->right == node->right? node : NULL; |
|
81
|
2 |
25395 |
if (IS_SENTINEL(node)) return NULL; |
|
84
|
158 |
25237 |
if (NOT_SENTINEL(node->left)) { |
|
86
|
26 |
158 |
while (NOT_SENTINEL(node->right)) |
|
93
|
4902 |
25183 |
while (parent->left == node) { |
|
97
|
54 |
4848 |
if (!parent) return NULL; |
|
104
|
1 |
845696 |
if (IS_SENTINEL(node)) return NULL; |
|
107
|
235242 |
610454 |
if (NOT_SENTINEL(node->right)) { |
|
109
|
234986 |
235242 |
while (NOT_SENTINEL(node->left)) |
|
116
|
0 |
610454 |
assert(parent); |
|
117
|
8409652 |
610454 |
while (parent->right == node) { |
|
118
|
0 |
8409652 |
assert(parent != parent->parent); |
|
123
|
300223 |
310231 |
if (!parent->parent) return NULL; |
|
140
|
70000 |
0 |
if (IS_ROOTSENTINEL(node)) |
|
143
|
1366585 |
70000 |
while (NOT_SENTINEL(node)) { |
|
146
|
173480 |
1193105 |
if (cmp<0) node= node->left; |
|
147
|
1193105 |
0 |
else if (cmp>0) node= node->right; |
|
150
|
69993 |
7 |
if (nearest && last_cmp_out) |
|
|
69993 |
0 |
if (nearest && last_cmp_out) |
|
167
|
400399 |
0 |
if (IS_ROOTSENTINEL(node)) |
|
170
|
10705025 |
400132 |
while (NOT_SENTINEL(node)) { |
|
173
|
577364 |
10127661 |
if (cmp<0) node= node->left; |
|
174
|
10127394 |
267 |
else if (cmp>0) node= node->right; |
|
177
|
400132 |
267 |
if (IS_SENTINEL(node)) { |
|
179
|
400132 |
0 |
if (result_first) |
|
180
|
400106 |
26 |
*result_first= nearest && cmp < 0? rbtree_node_prev(nearest) : nearest; |
|
|
24997 |
375109 |
*result_first= nearest && cmp < 0? rbtree_node_prev(nearest) : nearest; |
|
181
|
400132 |
0 |
if (result_last) |
|
182
|
400106 |
26 |
*result_last= nearest && cmp > 0? rbtree_node_next(nearest) : nearest; |
|
|
375109 |
24997 |
*result_last= nearest && cmp > 0? rbtree_node_next(nearest) : nearest; |
|
183
|
400121 |
11 |
if (result_count) *result_count= 0; |
|
188
|
0 |
267 |
if (result_first || result_count) { |
|
|
0 |
0 |
if (result_first || result_count) { |
|
192
|
209 |
267 |
while (NOT_SENTINEL(test)) { |
|
194
|
4 |
205 |
if (cmp == 0) { |
|
202
|
267 |
0 |
if (result_first) *result_first= first; |
|
204
|
1 |
266 |
if (result_last || result_count) { |
|
|
1 |
0 |
if (result_last || result_count) { |
|
208
|
218 |
267 |
while (NOT_SENTINEL(test)) { |
|
210
|
4 |
214 |
if (cmp == 0) { |
|
218
|
266 |
1 |
if (result_last) *result_last= last; |
|
219
|
24 |
243 |
if (result_count) *result_count= count; |
|
229
|
0 |
470212 |
if (NODE_IS_IN_TREE(node)) |
|
232
|
127 |
470085 |
if (IS_ROOTSENTINEL(hint)) { |
|
233
|
38 |
89 |
if (IS_SENTINEL(hint->left)) { |
|
251
|
39734 |
460322 |
if (cmp < 0) { |
|
258
|
470174 |
29882 |
if (IS_SENTINEL(next)) |
|
264
|
470055 |
119 |
if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) { |
|
|
34970 |
435085 |
if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) { |
|
|
445071 |
24984 |
if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) { |
|
269
|
24778 |
10153463 |
if ((cmp < 0? parent->right : parent->left) == hint) { |
|
|
44525 |
10133716 |
if ((cmp < 0? parent->right : parent->left) == hint) { |
|
270
|
0 |
44525 |
if ((cmp < 0) == (compare(ctx, PTR_OFS(node,cmp_ptr_ofs), PTR_OFS(parent,cmp_ptr_ofs)) < 0)) { |
|
272
|
0 |
0 |
while (NOT_ROOTSENTINEL(parent->parent)) |
|
278
|
400546 |
9733170 |
else if (IS_ROOTSENTINEL(parent->parent)) |
|
283
|
34987 |
435187 |
if (cmp < 0) |
|
293
|
12068514 |
470174 |
for (parent= pos; NOT_ROOTSENTINEL(parent); parent= parent->parent) |
|
306
|
44317 |
17915 |
if (parent->right == node) parent->right= new_head; |
|
323
|
374899 |
76415 |
if (parent->right == node) parent->right= new_head; |
|
343
|
897563 |
18462 |
while (IS_RED(current)) { |
|
349
|
833842 |
63721 |
if (parent->right == current) { |
|
351
|
443960 |
389882 |
if (IS_RED(parent->left)) { |
|
361
|
402 |
389480 |
if (IS_RED(current->left)) |
|
373
|
1891 |
61830 |
if (IS_RED(parent->right)) { |
|
383
|
61427 |
403 |
if (IS_RED(current->right)) |
|
403
|
1293819 |
70848 |
while (NOT_SENTINEL(node)) { |
|
404
|
1129788 |
164031 |
if (node->right == prev) |
|
416
|
143 |
623 |
if (index >= GET_COUNT(node)) |
|
418
|
1372 |
623 |
while (index != GET_COUNT(node->left)) { |
|
419
|
414 |
958 |
if (index < GET_COUNT(node->left)) |
|
437
|
0 |
26 |
if (GET_COUNT(current) == 0) |
|
441
|
7 |
19 |
if (IS_SENTINEL(current->left) || IS_SENTINEL(current->right)) |
|
|
1 |
6 |
if (IS_SENTINEL(current->left) || IS_SENTINEL(current->right)) |
|
450
|
2 |
4 |
: rbtree_node_next( current ); |
|
464
|
4 |
2 |
if (temp->left == current) temp->left= successor; else temp->right= successor; |
|
480
|
25 |
1 |
sentinel= IS_SENTINEL(node->left)? node->left : node->right; |
|
483
|
69 |
26 |
for (current= node; NOT_ROOTSENTINEL(current); current= current->parent) |
|
488
|
9 |
17 |
if (IS_RED(node)) { |
|
489
|
1 |
8 |
if (leftside) parent->left= sentinel; |
|
495
|
1 |
16 |
if (node->left != sentinel) { |
|
499
|
1 |
0 |
if (leftside) parent->left= node->left; |
|
503
|
4 |
12 |
if (node->right != sentinel) { |
|
507
|
3 |
1 |
if (leftside) parent->left= node->right; |
|
523
|
9 |
3 |
if (leftside) parent->left= sentinel; else parent->right= sentinel; |
|
525
|
9 |
3 |
sibling= (leftside)? parent->right : parent->left; |
|
530
|
17 |
6 |
while (IS_BLACK(current) && NOT_ROOTSENTINEL(parent)) { |
|
|
14 |
3 |
while (IS_BLACK(current) && NOT_ROOTSENTINEL(parent)) { |
|
536
|
2 |
12 |
if (IS_RED(sibling)) { |
|
539
|
2 |
0 |
if (leftside) { |
|
554
|
9 |
3 |
if (IS_BLACK(sibling->right) && IS_BLACK(sibling->left)) { |
|
|
9 |
0 |
if (IS_BLACK(sibling->right) && IS_BLACK(sibling->left)) { |
|
555
|
0 |
9 |
assert(NOT_SENTINEL(sibling)); |
|
562
|
6 |
3 |
sibling= (leftside)? parent->right : parent->left; |
|
579
|
3 |
0 |
if (leftside) { |
|
580
|
0 |
3 |
if (IS_BLACK(sibling->right)) { // Case 3 from the text |
|
586
|
0 |
3 |
assert(NOT_SENTINEL(sibling)); |
|
596
|
0 |
0 |
if (IS_BLACK(sibling->left)) { // Case 3 from the text |
|
602
|
0 |
0 |
assert(NOT_SENTINEL(sibling)); |
|
630
|
0 |
45 |
if (!IS_ROOTSENTINEL(root_sentinel)) |
|
632
|
8 |
37 |
if (IS_SENTINEL(root_sentinel->left)) |
|
637
|
235067 |
235119 |
if (NOT_SENTINEL(current->left)) { |
|
642
|
235082 |
235104 |
if (NOT_SENTINEL(current->right)) { |
|
651
|
470186 |
0 |
if (destructor) destructor(PTR_OFS(current,obj_ofs), ctx); |
|
653
|
37 |
470149 |
if (current == root_sentinel) |
|
655
|
235067 |
235082 |
else if (from_left) |
|
670
|
15 |
0 |
if (node && !node->parent) { |
|
|
15 |
0 |
if (node && !node->parent) { |
|
671
|
15 |
0 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
|
15 |
0 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
|
15 |
0 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
|
0 |
15 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
673
|
15 |
0 |
if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right |
|
|
15 |
0 |
if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right |
|
|
15 |
0 |
if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right |
|
674
|
0 |
15 |
|| node->right->right != node->right) |
|
676
|
0 |
15 |
if (node->left == node->right) return 0; /* empty tree, nothing more to check */ |
|
677
|
0 |
15 |
if (node->left->parent != node) |
|
687
|
470008 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
470008 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
470008 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
470008 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
0 |
470008 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
690
|
0 |
470008 |
if (GET_COUNT(node) != GET_COUNT(node->left) + GET_COUNT(node->right) + 1) |
|
694
|
234993 |
235015 |
if (NOT_SENTINEL(node->left)) { |
|
695
|
0 |
234993 |
if (node->left->parent != node) |
|
697
|
10217 |
224776 |
if (IS_RED(node) && IS_RED(node->left)) |
|
|
0 |
10217 |
if (IS_RED(node) && IS_RED(node->left)) |
|
699
|
0 |
234993 |
if (compare(ctx, PTR_OFS(node->left, cmp_pointer_ofs), PTR_OFS(node, cmp_pointer_ofs)) > 0) |
|
702
|
0 |
234993 |
if (err) return err; |
|
704
|
235000 |
235008 |
if (NOT_SENTINEL(node->right)) { |
|
705
|
0 |
235000 |
if (node->right->parent != node) |
|
707
|
10217 |
224783 |
if (IS_RED(node) && IS_RED(node->right)) |
|
|
0 |
10217 |
if (IS_RED(node) && IS_RED(node->right)) |
|
709
|
0 |
235000 |
if (compare(ctx, PTR_OFS(node->right, cmp_pointer_ofs), PTR_OFS(node, cmp_pointer_ofs)) < 0) |
|
712
|
0 |
235000 |
if (err) return err; |
|
714
|
0 |
470008 |
if (left_black_count != right_black_count) |