Branch Coverage

rbtree.c
Criterion Covered Total %
branch 227 288 78.8


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)