| line |
true |
false |
branch |
|
59
|
3 |
272 |
if (IS_SENTINEL(node)) return NULL; |
|
60
|
554 |
272 |
while (NOT_SENTINEL(node->left)) |
|
66
|
1 |
139 |
if (IS_SENTINEL(node)) return NULL; |
|
67
|
448 |
139 |
while (NOT_SENTINEL(node->right)) |
|
74
|
0 |
0 |
while (NOT_SENTINEL(node->right)) |
|
76
|
0 |
0 |
return IS_SENTINEL(node)? NULL : node; |
|
81
|
0 |
0 |
while (NOT_SENTINEL(node->left)) |
|
83
|
0 |
0 |
return IS_SENTINEL(node)? NULL : node; |
|
87
|
596 |
0 |
while (node && node->parent) |
|
|
419 |
177 |
while (node && node->parent) |
|
91
|
177 |
0 |
return node && node->right && node->right->right == node->right? node : NULL; |
|
|
151 |
26 |
return node && node->right && node->right->right == node->right? node : NULL; |
|
|
151 |
0 |
return node && node->right && node->right->right == node->right? node : NULL; |
|
95
|
5 |
513 |
if (IS_SENTINEL(node)) return NULL; |
|
98
|
187 |
326 |
if (NOT_SENTINEL(node->left)) { |
|
100
|
32 |
187 |
while (NOT_SENTINEL(node->right)) |
|
107
|
266 |
269 |
while (parent->left == node) { |
|
111
|
57 |
209 |
if (!parent) return NULL; |
|
118
|
4 |
1001875 |
if (IS_SENTINEL(node)) return NULL; |
|
121
|
287989 |
713886 |
if (NOT_SENTINEL(node->right)) { |
|
123
|
250108 |
287989 |
while (NOT_SENTINEL(node->left)) |
|
130
|
0 |
713886 |
assert(parent); |
|
131
|
9520193 |
713886 |
while (parent->right == node) { |
|
132
|
0 |
9520193 |
assert(parent != parent->parent); |
|
137
|
350986 |
362900 |
if (!parent->parent) return NULL; |
|
154
|
15751 |
0 |
if (IS_ROOTSENTINEL(node)) |
|
157
|
320269 |
15368 |
while (NOT_SENTINEL(node)) { |
|
160
|
80991 |
239278 |
if (cmp<0) node= node->left; |
|
161
|
238895 |
383 |
else if (cmp>0) node= node->right; |
|
164
|
15648 |
103 |
if (nearest && last_cmp_out) |
|
|
15648 |
0 |
if (nearest && last_cmp_out) |
|
181
|
77 |
3 |
if (IS_ROOTSENTINEL(node)) |
|
184
|
186 |
13 |
while (NOT_SENTINEL(node)) { |
|
187
|
56 |
130 |
if (cmp<0) node= node->left; |
|
188
|
63 |
67 |
else if (cmp>0) node= node->right; |
|
191
|
13 |
67 |
if (IS_SENTINEL(node)) { |
|
193
|
13 |
0 |
if (result_first) |
|
194
|
13 |
0 |
*result_first= nearest && cmp < 0? rbtree_node_prev(nearest) : nearest; |
|
|
4 |
9 |
*result_first= nearest && cmp < 0? rbtree_node_prev(nearest) : nearest; |
|
195
|
13 |
0 |
if (result_last) |
|
196
|
13 |
0 |
*result_last= nearest && cmp > 0? rbtree_node_next(nearest) : nearest; |
|
|
9 |
4 |
*result_last= nearest && cmp > 0? rbtree_node_next(nearest) : nearest; |
|
197
|
3 |
10 |
if (result_count) *result_count= 0; |
|
202
|
1 |
66 |
if (result_first || result_count) { |
|
|
1 |
0 |
if (result_first || result_count) { |
|
206
|
45 |
67 |
while (NOT_SENTINEL(test)) { |
|
208
|
4 |
41 |
if (cmp == 0) { |
|
216
|
66 |
1 |
if (result_first) *result_first= first; |
|
218
|
2 |
65 |
if (result_last || result_count) { |
|
|
2 |
0 |
if (result_last || result_count) { |
|
222
|
52 |
67 |
while (NOT_SENTINEL(test)) { |
|
224
|
6 |
46 |
if (cmp == 0) { |
|
232
|
65 |
2 |
if (result_last) *result_last= last; |
|
233
|
24 |
43 |
if (result_count) *result_count= count; |
|
241
|
2 |
2 |
while (NOT_SENTINEL(test)) { |
|
242
|
2 |
0 |
if (0 == compare(ctx, PTR_OFS(test,cmp_ptr_ofs), PTR_OFS(node,cmp_ptr_ofs) )) { |
|
255
|
16 |
22 |
while (NOT_SENTINEL(test)) { |
|
256
|
7 |
9 |
if (0 == compare(ctx, PTR_OFS(test,cmp_ptr_ofs), PTR_OFS(node,cmp_ptr_ofs) )) { |
|
271
|
0 |
0 |
if (NODE_IS_IN_TREE(node)) |
|
274
|
0 |
0 |
if (IS_ROOTSENTINEL(hint)) { |
|
275
|
0 |
0 |
if (IS_SENTINEL(hint->left)) { |
|
293
|
0 |
0 |
if (cmp < 0) { |
|
300
|
0 |
0 |
if (IS_SENTINEL(next)) |
|
306
|
0 |
0 |
if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) { |
|
|
0 |
0 |
if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) { |
|
|
0 |
0 |
if (NOT_ROOTSENTINEL(hint->parent) && (cmp < 0? leftmost : rightmost)) { |
|
311
|
0 |
0 |
if ((cmp < 0? parent->right : parent->left) == hint) { |
|
|
0 |
0 |
if ((cmp < 0? parent->right : parent->left) == hint) { |
|
312
|
0 |
0 |
if ((cmp < 0) == (compare(ctx, PTR_OFS(node,cmp_ptr_ofs), PTR_OFS(parent,cmp_ptr_ofs)) < 0)) { |
|
314
|
0 |
0 |
while (NOT_ROOTSENTINEL(parent->parent)) |
|
320
|
0 |
0 |
else if (IS_ROOTSENTINEL(parent->parent)) |
|
325
|
0 |
0 |
if (cmp < 0) |
|
335
|
0 |
0 |
for (parent= pos; NOT_ROOTSENTINEL(parent); parent= parent->parent) |
|
349
|
7669 |
3 |
if (IS_SENTINEL(parent->left)) { |
|
355
|
0 |
3 |
while (!IS_SENTINEL(parent->right)) |
|
365
|
151635 |
7672 |
for (tmp= parent; NOT_ROOTSENTINEL(tmp); tmp= tmp->parent) |
|
378
|
463382 |
29980 |
if (IS_SENTINEL(parent->right)) { |
|
384
|
2 |
29980 |
while (!IS_SENTINEL(parent->left)) |
|
394
|
12529858 |
493362 |
for (tmp= parent; NOT_ROOTSENTINEL(tmp); tmp= tmp->parent) |
|
406
|
47488 |
19198 |
if (parent->right == node) parent->right= new_head; |
|
423
|
398600 |
81955 |
if (parent->right == node) parent->right= new_head; |
|
443
|
955600 |
20076 |
while (IS_RED(current)) { |
|
449
|
887327 |
68273 |
if (parent->right == current) { |
|
451
|
472613 |
414714 |
if (IS_RED(parent->left)) { |
|
461
|
439 |
414275 |
if (IS_RED(current->left)) |
|
473
|
2029 |
66244 |
if (IS_RED(parent->right)) { |
|
483
|
65815 |
429 |
if (IS_RED(current->right)) |
|
503
|
1868786 |
100923 |
while (NOT_SENTINEL(node)) { |
|
504
|
1663789 |
204997 |
if (node->right == prev) |
|
516
|
164 |
646 |
if (index >= GET_COUNT(node)) |
|
518
|
1442 |
646 |
while (index != GET_COUNT(node->left)) { |
|
519
|
435 |
1007 |
if (index < GET_COUNT(node->left)) |
|
537
|
0 |
142 |
if (GET_COUNT(current) == 0) |
|
541
|
47 |
95 |
if (IS_SENTINEL(current->left) || IS_SENTINEL(current->right)) |
|
|
22 |
25 |
if (IS_SENTINEL(current->left) || IS_SENTINEL(current->right)) |
|
550
|
3 |
22 |
: rbtree_node_next( current ); |
|
564
|
22 |
3 |
if (temp->left == current) temp->left= successor; else temp->right= successor; |
|
580
|
120 |
22 |
sentinel= IS_SENTINEL(node->left)? node->left : node->right; |
|
583
|
383 |
142 |
for (current= node; NOT_ROOTSENTINEL(current); current= current->parent) |
|
588
|
48 |
94 |
if (IS_RED(node)) { |
|
589
|
20 |
28 |
if (leftside) parent->left= sentinel; |
|
595
|
22 |
72 |
if (node->left != sentinel) { |
|
599
|
22 |
0 |
if (leftside) parent->left= node->left; |
|
603
|
25 |
47 |
if (node->right != sentinel) { |
|
607
|
17 |
8 |
if (leftside) parent->left= node->right; |
|
623
|
40 |
7 |
if (leftside) parent->left= sentinel; else parent->right= sentinel; |
|
625
|
40 |
7 |
sibling= (leftside)? parent->right : parent->left; |
|
630
|
82 |
23 |
while (IS_BLACK(current) && NOT_ROOTSENTINEL(parent)) { |
|
|
68 |
14 |
while (IS_BLACK(current) && NOT_ROOTSENTINEL(parent)) { |
|
636
|
16 |
52 |
if (IS_RED(sibling)) { |
|
639
|
16 |
0 |
if (leftside) { |
|
654
|
45 |
7 |
if (IS_BLACK(sibling->right) && IS_BLACK(sibling->left)) { |
|
|
42 |
3 |
if (IS_BLACK(sibling->right) && IS_BLACK(sibling->left)) { |
|
655
|
0 |
42 |
assert(NOT_SENTINEL(sibling)); |
|
662
|
35 |
7 |
sibling= (leftside)? parent->right : parent->left; |
|
679
|
10 |
0 |
if (leftside) { |
|
680
|
3 |
7 |
if (IS_BLACK(sibling->right)) { // Case 3 from the text |
|
686
|
0 |
10 |
assert(NOT_SENTINEL(sibling)); |
|
696
|
0 |
0 |
if (IS_BLACK(sibling->left)) { // Case 3 from the text |
|
702
|
0 |
0 |
assert(NOT_SENTINEL(sibling)); |
|
730
|
0 |
116 |
if (!IS_ROOTSENTINEL(root_sentinel)) |
|
732
|
19 |
97 |
if (IS_SENTINEL(root_sentinel->left)) |
|
737
|
250503 |
250389 |
if (NOT_SENTINEL(current->left)) { |
|
742
|
250486 |
250406 |
if (NOT_SENTINEL(current->right)) { |
|
751
|
500892 |
0 |
if (destructor) destructor(PTR_OFS(current,obj_ofs), ctx); |
|
753
|
97 |
500795 |
if (current == root_sentinel) |
|
755
|
250389 |
250406 |
else if (from_left) |
|
770
|
19 |
0 |
if (node && !node->parent) { |
|
|
19 |
0 |
if (node && !node->parent) { |
|
771
|
19 |
0 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
|
19 |
0 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
|
19 |
0 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
|
0 |
19 |
if (IS_RED(node) || IS_RED(node->left) || GET_COUNT(node) || GET_COUNT(node->right)) |
|
773
|
19 |
0 |
if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right |
|
|
19 |
0 |
if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right |
|
|
19 |
0 |
if (GET_COUNT(node->right) || IS_RED(node->right) || node->right->left != node->right |
|
774
|
0 |
19 |
|| node->right->right != node->right) |
|
776
|
0 |
19 |
if (node->left == node->right) return 0; /* empty tree, nothing more to check */ |
|
777
|
0 |
19 |
if (node->left->parent != node) |
|
787
|
500010 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
500010 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
500010 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
500010 |
0 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
|
0 |
500010 |
if (!node || !node->parent || !node->left || !node->right || !GET_COUNT(node)) |
|
790
|
0 |
500010 |
if (GET_COUNT(node) != GET_COUNT(node->left) + GET_COUNT(node->right) + 1) |
|
794
|
249992 |
250018 |
if (NOT_SENTINEL(node->left)) { |
|
795
|
0 |
249992 |
if (node->left->parent != node) |
|
797
|
10967 |
239025 |
if (IS_RED(node) && IS_RED(node->left)) |
|
|
0 |
10967 |
if (IS_RED(node) && IS_RED(node->left)) |
|
799
|
0 |
249992 |
if (compare(ctx, PTR_OFS(node->left, cmp_pointer_ofs), PTR_OFS(node, cmp_pointer_ofs)) > 0) |
|
802
|
0 |
249992 |
if (err) return err; |
|
804
|
249999 |
250011 |
if (NOT_SENTINEL(node->right)) { |
|
805
|
0 |
249999 |
if (node->right->parent != node) |
|
807
|
10967 |
239032 |
if (IS_RED(node) && IS_RED(node->right)) |
|
|
0 |
10967 |
if (IS_RED(node) && IS_RED(node->right)) |
|
809
|
0 |
249999 |
if (compare(ctx, PTR_OFS(node->right, cmp_pointer_ofs), PTR_OFS(node, cmp_pointer_ofs)) < 0) |
|
812
|
0 |
249999 |
if (err) return err; |
|
814
|
0 |
500010 |
if (left_black_count != right_black_count) |