Ticket #7191: container.c.gcov.txt

File container.c.gcov.txt, 7.5 KB (added by andrea, 7 years ago)

Gcov output for test suite with proposed 7191 fix

Line 
1        -:  561:/** Assuming the members of <b>sl</b> are in order, return the index of the
2        -:  562: * member that matches <b>key</b>.  If no member matches, return the index of
3        -:  563: * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
4        -:  564: * is greater than <b>key</b>.  Set <b>found_out</b> to true on a match, to
5        -:  565: * false otherwise.  Ordering and matching are defined by a <b>compare</b>
6        -:  566: * function that returns 0 on a match; less than 0 if key is less than member,
7        -:  567: * and greater than 0 if key is greater then member.
8        -:  568: */
9        -:  569:int
10function smartlist_bsearch_idx called 101 returned 100% blocks executed 39%
11      101:  570:smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
12        -:  571:                      int (*compare)(const void *key, const void **member),
13        -:  572:                      int *found_out)
14        -:  573:{
15        -:  574:  int hi, lo, cmp, mid, len;
16        -:  575:
17      101:  576:  tor_assert(sl);
18branch  0 taken 0% (fallthrough)
19branch  1 taken 100%
20call    2 never executed
21call    3 never executed
22call    4 never executed
23      101:  577:  tor_assert(compare);
24branch  0 taken 0% (fallthrough)
25branch  1 taken 100%
26call    2 never executed
27call    3 never executed
28call    4 never executed
29      101:  578:  tor_assert(found_out);
30branch  0 taken 0% (fallthrough)
31branch  1 taken 100%
32call    2 never executed
33call    3 never executed
34call    4 never executed
35        -:  579:
36      101:  580:  len = smartlist_len(sl);
37        -:  581:
38        -:  582:  /* Check for the trivial case of a zero-length list */
39      101:  583:  if (len == 0) {
40branch  0 taken 1% (fallthrough)
41branch  1 taken 99%
42        1:  584:    *found_out = 0;
43        -:  585:    /* We already know smartlist_len(sl) is 0 in this case */
44        1:  586:    return 0;
45        -:  587:  }
46        -:  588:
47        -:  589:  /* Okay, we have a real search to do */
48      100:  590:  tor_assert(len > 0);
49branch  0 taken 0% (fallthrough)
50branch  1 taken 100%
51call    2 never executed
52call    3 never executed
53call    4 never executed
54      100:  591:  lo = 0;
55      100:  592:  hi = len - 1;
56        -:  593:
57        -:  594:  /*
58        -:  595:   * These invariants are always true:
59        -:  596:   *
60        -:  597:   * For all i such that 0 <= i < lo, sl[i] < key
61        -:  598:   * For all i such that hi < i <= len, sl[i] > key
62        -:  599:   */
63        -:  600:
64      370:  601:  while (lo <= hi) {
65branch  0 taken 97%
66branch  1 taken 3% (fallthrough)
67      262:  602:    mid = (lo + hi) / 2;
68      262:  603:    cmp = compare(key, (const void**) &(sl->list[mid]));
69call    0 returned 100%
70      262:  604:    if (cmp == 0) {
71branch  0 taken 32% (fallthrough)
72branch  1 taken 68%
73        -:  605:      /* sl[mid] == key; we found it */
74       83:  606:      *found_out = 1;
75       83:  607:      return mid;
76      179:  608:    } else if (cmp > 0) {
77branch  0 taken 43% (fallthrough)
78branch  1 taken 57%
79        -:  609:      /*
80        -:  610:       * key > sl[mid] and an index i such that sl[i] == key must
81        -:  611:       * have i > mid if it exists.
82        -:  612:       */
83        -:  613:
84        -:  614:      /* Check for end-of-list case */
85       77:  615:      if (mid < len) {
86branch  0 taken 100% (fallthrough)
87branch  1 taken 0%
88        -:  616:        /* Normal case, move lo to the element immediately after sl[mid] */
89       77:  617:        lo = mid + 1;
90        -:  618:      } else {
91        -:  619:        /* These should always be true in this case */
92    #####:  620:        tor_assert(mid == hi);
93branch  0 never executed
94branch  1 never executed
95call    2 never executed
96call    3 never executed
97call    4 never executed
98    #####:  621:        tor_assert(mid == len);
99branch  0 never executed
100branch  1 never executed
101call    2 never executed
102call    3 never executed
103call    4 never executed
104        -:  622:        /*
105        -:  623:         * We were at the end of the list and concluded that every element e
106        -:  624:         * compares e < key.
107        -:  625:         */
108    #####:  626:        *found_out = 0;
109    #####:  627:        return len;
110        -:  628:      }
111        -:  629:    } else {
112        -:  630:      /* This should always be true in this case */
113      102:  631:      tor_assert(cmp < 0);
114branch  0 taken 0% (fallthrough)
115branch  1 taken 100%
116call    2 never executed
117call    3 never executed
118call    4 never executed
119        -:  632:
120        -:  633:      /*
121        -:  634:       * key < sl[mid] and an index i such that sl[i] == key must
122        -:  635:       * have i < mid if it exists.
123        -:  636:       */
124        -:  637:
125      102:  638:      if (mid > 0) {
126branch  0 taken 91% (fallthrough)
127branch  1 taken 9%
128        -:  639:        /* Normal case, move hi to the element immediately before sl[mid] */
129       93:  640:        hi = mid - 1;
130        -:  641:      } else {
131        -:  642:        /* These should always be true in this case */
132        9:  643:        tor_assert(mid == lo);
133branch  0 taken 0% (fallthrough)
134branch  1 taken 100%
135call    2 never executed
136call    3 never executed
137call    4 never executed
138        9:  644:        tor_assert(mid == 0);
139branch  0 taken 0% (fallthrough)
140branch  1 taken 100%
141call    2 never executed
142call    3 never executed
143call    4 never executed
144        -:  645:        /*
145        -:  646:         * We were at the beginning of the list and concluded that every
146        -:  647:         * element e compares e > key.
147        -:  648:         */
148        9:  649:        *found_out = 0;
149        9:  650:        return 0;
150        -:  651:      }
151        -:  652:    }
152        -:  653:  }
153        -:  654:
154        -:  655:  /*
155        -:  656:   * lo > hi; we have no element matching key but we have elements falling
156        -:  657:   * on both sides of it.  The lo index points to the first element > key.
157        -:  658:   */
158        8:  659:  tor_assert(lo == hi + 1); /* All other cases should have been handled */
159branch  0 taken 0% (fallthrough)
160branch  1 taken 100%
161call    2 never executed
162call    3 never executed
163call    4 never executed
164        8:  660:  tor_assert(lo >= 0);
165branch  0 taken 0% (fallthrough)
166branch  1 taken 100%
167call    2 never executed
168call    3 never executed
169call    4 never executed
170        8:  661:  tor_assert(lo <= len);
171branch  0 taken 0% (fallthrough)
172branch  1 taken 100%
173call    2 never executed
174call    3 never executed
175call    4 never executed
176        8:  662:  tor_assert(hi >= 0);
177branch  0 taken 0% (fallthrough)
178branch  1 taken 100%
179call    2 never executed
180call    3 never executed
181call    4 never executed
182        8:  663:  tor_assert(hi <= len);
183branch  0 taken 0% (fallthrough)
184branch  1 taken 100%
185call    2 never executed
186call    3 never executed
187call    4 never executed
188        -:  664:
189        8:  665:  if (lo < len) {
190branch  0 taken 63% (fallthrough)
191branch  1 taken 38%
192        5:  666:    cmp = compare(key, (const void **) &(sl->list[lo]));
193call    0 returned 100%
194        5:  667:    tor_assert(cmp < 0);
195branch  0 taken 0% (fallthrough)
196branch  1 taken 100%
197call    2 never executed
198call    3 never executed
199call    4 never executed
200        -:  668:  } else {
201        3:  669:    cmp = compare(key, (const void **) &(sl->list[len-1]));
202call    0 returned 100%
203        3:  670:    tor_assert(cmp > 0);
204branch  0 taken 0% (fallthrough)
205branch  1 taken 100%
206call    2 never executed
207call    3 never executed
208call    4 never executed
209        -:  671:  }
210        -:  672:
211        8:  673:  *found_out = 0;
212        8:  674:  return lo;
213        -:  675:}