| line |
true |
false |
branch |
|
78
|
17856 |
4464 |
8 + lg_table[(n >> 8) & 0xff] : |
|
111
|
0 |
0 |
if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; } |
|
114
|
0 |
0 |
24 + lg_table[(x >> 24) & 0xff] : |
|
115
|
0 |
0 |
16 + lg_table[(x >> 16) & 0xff]) : |
|
117
|
0 |
0 |
8 + lg_table[(x >> 8) & 0xff] : |
|
120
|
0 |
0 |
if(e >= 16) { |
|
122
|
0 |
0 |
if(e >= 24) { y = (y + 1 + x / y) >> 1; } |
|
124
|
0 |
0 |
} else if(e >= 8) { |
|
130
|
0 |
0 |
return (x < (y * y)) ? y - 1 : y; |
|
150
|
22080 |
4464 |
(U1 < U1n) && (U2 < U2n) && (*U1 == *U2); |
|
|
22080 |
0 |
(U1 < U1n) && (U2 < U2n) && (*U1 == *U2); |
|
|
22080 |
0 |
(U1 < U1n) && (U2 < U2n) && (*U1 == *U2); |
|
155
|
0 |
4464 |
(U2 < U2n ? *U1 - *U2 : 1) : |
|
|
0 |
0 |
(U2 < U2n ? *U1 - *U2 : 1) : |
|
|
48 |
4416 |
(U2 < U2n ? *U1 - *U2 : 1) : |
|
173
|
0 |
0 |
for(i = last - 2; first <= i; --i) { |
|
174
|
0 |
0 |
for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) { |
|
175
|
0 |
0 |
do { *(j - 1) = *j; } while((++j < last) && (*j < 0)); |
|
|
0 |
0 |
do { *(j - 1) = *j; } while((++j < last) && (*j < 0)); |
|
176
|
0 |
0 |
if(last <= j) { break; } |
|
178
|
0 |
0 |
if(r == 0) { *j = ~*j; } |
|
198
|
0 |
0 |
for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { |
|
200
|
0 |
0 |
if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; } |
|
201
|
0 |
0 |
if(d <= c) { break; } |
|
214
|
0 |
0 |
if((size % 2) == 0) { |
|
216
|
0 |
0 |
if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); } |
|
219
|
0 |
0 |
for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); } |
|
220
|
0 |
0 |
if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); } |
|
221
|
0 |
0 |
for(i = m - 1; 0 < i; --i) { |
|
237
|
0 |
89280 |
if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); } |
|
238
|
0 |
89280 |
if(Td[PA[*v2]] > Td[PA[*v3]]) { |
|
239
|
0 |
0 |
if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; } |
|
251
|
0 |
0 |
if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); } |
|
252
|
0 |
0 |
if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); } |
|
253
|
0 |
0 |
if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); } |
|
254
|
0 |
0 |
if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); } |
|
255
|
0 |
0 |
if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); } |
|
256
|
0 |
0 |
if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; } |
|
270
|
0 |
22320 |
if(t <= 512) { |
|
271
|
0 |
0 |
if(t <= 32) { |
|
296
|
4573344 |
4464 |
for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; } |
|
|
4559952 |
13392 |
for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; } |
|
297
|
13666464 |
17856 |
for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { } |
|
|
13666464 |
0 |
for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { } |
|
298
|
17856 |
0 |
if(b <= a) { break; } |
|
303
|
4464 |
13392 |
if(first < a) { *first = ~*first; } |
|
324
|
4464 |
22320 |
if((last - first) <= SS_INSERTIONSORT_THRESHOLD) { |
|
326
|
0 |
4464 |
if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); } |
|
328
|
4464 |
0 |
STACK_POP(first, last, depth, limit); |
|
333
|
0 |
22320 |
if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); } |
|
334
|
0 |
22320 |
if(limit < 0) { |
|
335
|
0 |
0 |
for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) { |
|
336
|
0 |
0 |
if((x = Td[PA[*a]]) != v) { |
|
337
|
0 |
0 |
if(1 < (a - first)) { break; } |
|
342
|
0 |
0 |
if(Td[PA[*first] - 1] < v) { |
|
345
|
0 |
0 |
if((a - first) <= (last - a)) { |
|
346
|
0 |
0 |
if(1 < (a - first)) { |
|
353
|
0 |
0 |
if(1 < (last - a)) { |
|
369
|
22777440 |
22320 |
for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } |
|
|
22777440 |
0 |
for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } |
|
370
|
0 |
22320 |
if(((a = b) < last) && (x < v)) { |
|
|
0 |
0 |
if(((a = b) < last) && (x < v)) { |
|
371
|
0 |
0 |
for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) { |
|
|
0 |
0 |
for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) { |
|
372
|
0 |
0 |
if(x == v) { SWAP(*b, *a); ++a; } |
|
375
|
0 |
22320 |
for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { } |
|
|
0 |
0 |
for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { } |
|
376
|
0 |
22320 |
if((b < (d = c)) && (x > v)) { |
|
|
0 |
0 |
if((b < (d = c)) && (x > v)) { |
|
377
|
0 |
0 |
for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { |
|
|
0 |
0 |
for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { |
|
378
|
0 |
0 |
if(x == v) { SWAP(*c, *d); --d; } |
|
381
|
0 |
22320 |
for(; b < c;) { |
|
383
|
0 |
0 |
for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) { |
|
|
0 |
0 |
for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) { |
|
384
|
0 |
0 |
if(x == v) { SWAP(*b, *a); ++a; } |
|
386
|
0 |
0 |
for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { |
|
|
0 |
0 |
for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { |
|
387
|
0 |
0 |
if(x == v) { SWAP(*c, *d); --d; } |
|
391
|
0 |
22320 |
if(a <= d) { |
|
394
|
0 |
0 |
if((s = a - first) > (t = b - a)) { s = t; } |
|
395
|
0 |
0 |
for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
|
396
|
0 |
0 |
if((s = d - c) > (t = last - d - 1)) { s = t; } |
|
397
|
0 |
0 |
for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
|
400
|
0 |
0 |
b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth); |
|
402
|
0 |
0 |
if((a - first) <= (last - c)) { |
|
403
|
0 |
0 |
if((last - c) <= (c - b)) { |
|
407
|
0 |
0 |
} else if((a - first) <= (c - b)) { |
|
417
|
0 |
0 |
if((a - first) <= (c - b)) { |
|
421
|
0 |
0 |
} else if((last - c) <= (c - b)) { |
|
433
|
17856 |
4464 |
if(Td[PA[*first] - 1] < v) { |
|
454
|
14141376 |
4416 |
for(; 0 < n; --n, ++a, ++b) { |
|
465
|
0 |
0 |
for(; (0 < l) && (0 < r);) { |
|
|
0 |
0 |
for(; (0 < l) && (0 < r);) { |
|
466
|
0 |
0 |
if(l == r) { ss_blockswap(first, middle, l); break; } |
|
467
|
0 |
0 |
if(l < r) { |
|
472
|
0 |
0 |
if(b < first) { |
|
475
|
0 |
0 |
if((r -= l + 1) <= l) { break; } |
|
485
|
0 |
0 |
if(last <= b) { |
|
488
|
0 |
0 |
if((l -= r + 1) <= r) { break; } |
|
512
|
0 |
0 |
if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); } |
|
515
|
0 |
0 |
0 < len; |
|
518
|
0 |
0 |
q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth); |
|
519
|
0 |
0 |
if(q < 0) { |
|
526
|
0 |
0 |
if(a < middle) { |
|
527
|
0 |
0 |
if(r == 0) { *a = ~*a; } |
|
531
|
0 |
0 |
if(first == middle) { break; } |
|
534
|
0 |
0 |
if(x != 0) { while(*--last < 0) { } } |
|
|
0 |
0 |
if(x != 0) { while(*--last < 0) { } } |
|
535
|
0 |
0 |
if(middle == last) { break; } |
|
557
|
0 |
0 |
if(r < 0) { |
|
560
|
0 |
0 |
if(bufend <= b) { *bufend = t; return; } |
|
562
|
0 |
0 |
} while(*b < 0); |
|
563
|
0 |
0 |
} else if(r > 0) { |
|
566
|
0 |
0 |
if(last <= c) { |
|
567
|
0 |
0 |
while(b < bufend) { *a++ = *b, *b++ = *a; } |
|
571
|
0 |
0 |
} while(*c < 0); |
|
576
|
0 |
0 |
if(bufend <= b) { *bufend = t; return; } |
|
578
|
0 |
0 |
} while(*b < 0); |
|
582
|
0 |
0 |
if(last <= c) { |
|
583
|
0 |
0 |
while(b < bufend) { *a++ = *b, *b++ = *a; } |
|
587
|
0 |
0 |
} while(*c < 0); |
|
608
|
4416 |
0 |
if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; } |
|
610
|
4416 |
0 |
if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; } |
|
614
|
0 |
4416 |
if(0 < r) { |
|
615
|
0 |
0 |
if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } |
|
|
0 |
0 |
if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } |
|
617
|
0 |
0 |
if(b <= buf) { *buf = t; break; } |
|
619
|
0 |
0 |
if(*b < 0) { p1 = PA + ~*b; x |= 1; } |
|
621
|
0 |
4416 |
} else if(r < 0) { |
|
622
|
0 |
0 |
if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } |
|
|
0 |
0 |
if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } |
|
624
|
0 |
0 |
if(c < first) { |
|
625
|
0 |
0 |
while(buf < b) { *a-- = *b, *b-- = *a; } |
|
629
|
0 |
0 |
if(*c < 0) { p2 = PA + ~*c; x |= 2; } |
|
632
|
4416 |
0 |
if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } |
|
|
14132544 |
4416 |
if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } |
|
634
|
4416 |
0 |
if(b <= buf) { *buf = t; break; } |
|
636
|
0 |
0 |
if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } |
|
|
0 |
0 |
if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } |
|
638
|
0 |
0 |
if(c < first) { |
|
639
|
0 |
0 |
while(buf < b) { *a-- = *b, *b-- = *a; } |
|
643
|
0 |
0 |
if(*b < 0) { p1 = PA + ~*b; x |= 1; } |
|
645
|
0 |
0 |
if(*c < 0) { p2 = PA + ~*c; x |= 2; } |
|
676
|
4416 |
0 |
if((last - middle) <= bufsize) { |
|
677
|
4416 |
0 |
if((first < middle) && (middle < last)) { |
|
|
4416 |
0 |
if((first < middle) && (middle < last)) { |
|
680
|
4416 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
4416 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
4416 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
681
|
4416 |
0 |
STACK_POP(first, middle, last, check); |
|
685
|
0 |
0 |
if((middle - first) <= bufsize) { |
|
686
|
0 |
0 |
if(first < middle) { |
|
689
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
690
|
0 |
0 |
STACK_POP(first, middle, last, check); |
|
694
|
0 |
0 |
for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1; |
|
695
|
0 |
0 |
0 < len; |
|
697
|
0 |
0 |
if(ss_compare(T, PA + GETIDX(*(middle + m + half)), |
|
|
0 |
0 |
if(ss_compare(T, PA + GETIDX(*(middle + m + half)), |
|
698
|
0 |
0 |
PA + GETIDX(*(middle - m - half - 1)), depth) < 0) { |
|
704
|
0 |
0 |
if(0 < m) { |
|
708
|
0 |
0 |
if(rm < last) { |
|
709
|
0 |
0 |
if(*rm < 0) { |
|
711
|
0 |
0 |
if(first < lm) { for(; *--l < 0;) { } next |= 4; } |
|
|
0 |
0 |
if(first < lm) { for(; *--l < 0;) { } next |= 4; } |
|
713
|
0 |
0 |
} else if(first < lm) { |
|
714
|
0 |
0 |
for(; *r < 0; ++r) { } |
|
719
|
0 |
0 |
if((l - first) <= (last - r)) { |
|
723
|
0 |
0 |
if((next & 2) && (r == middle)) { next ^= 6; } |
|
|
0 |
0 |
if((next & 2) && (r == middle)) { next ^= 6; } |
|
728
|
0 |
0 |
if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) { |
|
|
0 |
0 |
if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) { |
|
731
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
|
0 |
0 |
MERGE_CHECK(first, last, check); |
|
732
|
0 |
0 |
STACK_POP(first, middle, last, check); |
|
758
|
48 |
0 |
if(lastsuffix != 0) { ++first; } |
|
763
|
0 |
48 |
if((bufsize < SS_BLOCKSIZE) && |
|
766
|
0 |
0 |
if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; } |
|
771
|
4416 |
48 |
for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) { |
|
779
|
4416 |
0 |
if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; } |
|
780
|
4224 |
4416 |
for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) { |
|
789
|
336 |
48 |
for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) { |
|
790
|
192 |
144 |
if(i & 1) { |
|
795
|
0 |
48 |
if(limit != 0) { |
|
805
|
48 |
0 |
if(lastsuffix != 0) { |
|
809
|
48 |
0 |
(a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); |
|
|
0 |
48 |
(a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); |
|
|
0 |
48 |
(a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); |