| line |
true |
false |
branch |
|
65
|
0 |
96 |
24 + lg_table[(n >> 24) & 0xff] : |
|
66
|
96 |
0 |
16 + lg_table[(n >> 16) & 0xff]) : |
|
68
|
0 |
0 |
8 + lg_table[(n >> 8) & 0xff] : |
|
83
|
0 |
0 |
for(a = first + 1; a < last; ++a) { |
|
84
|
0 |
0 |
for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) { |
|
85
|
0 |
0 |
do { *(b + 1) = *b; } while((first <= --b) && (*b < 0)); |
|
|
0 |
0 |
do { *(b + 1) = *b; } while((first <= --b) && (*b < 0)); |
|
86
|
0 |
0 |
if(b < first) { break; } |
|
88
|
0 |
0 |
if(r == 0) { *b = ~*b; } |
|
103
|
0 |
0 |
for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { |
|
105
|
0 |
0 |
if(d < (e = ISAd[SA[j]])) { k = j; d = e; } |
|
106
|
0 |
0 |
if(d <= c) { break; } |
|
119
|
0 |
0 |
if((size % 2) == 0) { |
|
121
|
0 |
0 |
if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); } |
|
124
|
0 |
0 |
for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); } |
|
125
|
0 |
0 |
if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); } |
|
126
|
0 |
0 |
for(i = m - 1; 0 < i; --i) { |
|
141
|
0 |
192 |
if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); } |
|
142
|
48 |
144 |
if(ISAd[*v2] > ISAd[*v3]) { |
|
143
|
48 |
0 |
if(ISAd[*v1] > ISAd[*v3]) { return v1; } |
|
155
|
0 |
0 |
if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); } |
|
156
|
0 |
0 |
if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); } |
|
157
|
0 |
0 |
if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); } |
|
158
|
0 |
0 |
if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); } |
|
159
|
0 |
0 |
if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); } |
|
160
|
0 |
0 |
if(ISAd[*v3] > ISAd[*v4]) { return v4; } |
|
174
|
0 |
48 |
if(t <= 512) { |
|
175
|
0 |
0 |
if(t <= 32) { |
|
210
|
48 |
0 |
if(size <= budget->remain) { budget->remain -= size; return 1; } |
|
211
|
0 |
0 |
if(budget->chance == 0) { budget->count += size; return 0; } |
|
229
|
9119760 |
0 |
for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { } |
|
|
9119664 |
96 |
for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { } |
|
230
|
96 |
0 |
if(((a = b) < last) && (x < v)) { |
|
|
96 |
0 |
if(((a = b) < last) && (x < v)) { |
|
231
|
48 |
96 |
for(; (++b < last) && ((x = ISAd[*b]) <= v);) { |
|
|
48 |
0 |
for(; (++b < last) && ((x = ISAd[*b]) <= v);) { |
|
232
|
48 |
0 |
if(x == v) { SWAP(*b, *a); ++a; } |
|
235
|
0 |
96 |
for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { } |
|
|
0 |
0 |
for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { } |
|
236
|
0 |
96 |
if((b < (d = c)) && (x > v)) { |
|
|
0 |
0 |
if((b < (d = c)) && (x > v)) { |
|
237
|
0 |
0 |
for(; (b < --c) && ((x = ISAd[*c]) >= v);) { |
|
|
0 |
0 |
for(; (b < --c) && ((x = ISAd[*c]) >= v);) { |
|
238
|
0 |
0 |
if(x == v) { SWAP(*c, *d); --d; } |
|
241
|
0 |
96 |
for(; b < c;) { |
|
243
|
0 |
0 |
for(; (++b < c) && ((x = ISAd[*b]) <= v);) { |
|
|
0 |
0 |
for(; (++b < c) && ((x = ISAd[*b]) <= v);) { |
|
244
|
0 |
0 |
if(x == v) { SWAP(*b, *a); ++a; } |
|
246
|
0 |
0 |
for(; (b < --c) && ((x = ISAd[*c]) >= v);) { |
|
|
0 |
0 |
for(; (b < --c) && ((x = ISAd[*c]) >= v);) { |
|
247
|
0 |
0 |
if(x == v) { SWAP(*c, *d); --d; } |
|
251
|
96 |
0 |
if(a <= d) { |
|
253
|
96 |
0 |
if((s = a - first) > (t = b - a)) { s = t; } |
|
254
|
96 |
96 |
for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
|
255
|
0 |
96 |
if((s = d - c) > (t = last - d - 1)) { s = t; } |
|
256
|
0 |
96 |
for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } |
|
273
|
4559904 |
48 |
for(c = first, d = a - 1; c <= d; ++c) { |
|
274
|
4559856 |
48 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
|
4559856 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
279
|
0 |
48 |
for(c = last - 1, e = d + 1, d = b; e < d; --c) { |
|
280
|
0 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
|
0 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
298
|
0 |
0 |
for(c = first, d = a - 1; c <= d; ++c) { |
|
299
|
0 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
|
0 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
302
|
0 |
0 |
if(lastrank != rank) { lastrank = rank; newrank = d - SA; } |
|
308
|
0 |
0 |
for(e = d; first <= e; --e) { |
|
310
|
0 |
0 |
if(lastrank != rank) { lastrank = rank; newrank = e - SA; } |
|
311
|
0 |
0 |
if(newrank != rank) { ISA[*e] = newrank; } |
|
315
|
0 |
0 |
for(c = last - 1, e = d + 1, d = b; e < d; --c) { |
|
316
|
0 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
|
0 |
0 |
if((0 <= (s = *c - depth)) && (ISA[s] == v)) { |
|
319
|
0 |
0 |
if(lastrank != rank) { lastrank = rank; newrank = d - SA; } |
|
341
|
96 |
48 |
if(limit < 0) { |
|
342
|
48 |
48 |
if(limit == -1) { |
|
347
|
48 |
0 |
if(a < last) { |
|
348
|
48 |
48 |
for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } |
|
350
|
0 |
48 |
if(b < last) { |
|
351
|
0 |
0 |
for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } |
|
355
|
48 |
0 |
if(1 < (b - a)) { |
|
360
|
0 |
48 |
if((a - first) <= (last - b)) { |
|
361
|
0 |
0 |
if(1 < (a - first)) { |
|
364
|
0 |
0 |
} else if(1 < (last - b)) { |
|
367
|
0 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
370
|
0 |
48 |
if(1 < (last - b)) { |
|
373
|
0 |
48 |
} else if(1 < (a - first)) { |
|
376
|
0 |
48 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
379
|
48 |
0 |
} else if(limit == -2) { |
|
382
|
48 |
0 |
if(stack[ssize].d == 0) { |
|
385
|
0 |
0 |
if(0 <= trlink) { stack[trlink].d = -1; } |
|
388
|
48 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
391
|
0 |
0 |
if(0 <= *first) { |
|
393
|
0 |
0 |
do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a)); |
|
|
0 |
0 |
do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a)); |
|
396
|
0 |
0 |
if(first < last) { |
|
397
|
0 |
0 |
a = first; do { *a = ~*a; } while(*++a < 0); |
|
398
|
0 |
0 |
next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1; |
|
399
|
0 |
0 |
if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } |
|
|
0 |
0 |
if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } |
|
402
|
0 |
0 |
if(trbudget_check(budget, a - first)) { |
|
403
|
0 |
0 |
if((a - first) <= (last - a)) { |
|
407
|
0 |
0 |
if(1 < (last - a)) { |
|
415
|
0 |
0 |
if(0 <= trlink) { stack[trlink].d = -1; } |
|
416
|
0 |
0 |
if(1 < (last - a)) { |
|
419
|
0 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
423
|
0 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
429
|
0 |
48 |
if((last - first) <= TR_INSERTIONSORT_THRESHOLD) { |
|
435
|
0 |
48 |
if(limit-- == 0) { |
|
437
|
0 |
0 |
for(a = last - 1; first < a; a = b) { |
|
438
|
0 |
0 |
for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } |
|
|
0 |
0 |
for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } |
|
451
|
48 |
0 |
if((last - first) != (b - a)) { |
|
452
|
0 |
48 |
next = (ISA[*a] != v) ? tr_ilg(b - a) : -1; |
|
455
|
48 |
48 |
for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } |
|
456
|
0 |
48 |
if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } } |
|
|
0 |
0 |
if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } } |
|
459
|
48 |
0 |
if((1 < (b - a)) && (trbudget_check(budget, b - a))) { |
|
|
48 |
0 |
if((1 < (b - a)) && (trbudget_check(budget, b - a))) { |
|
460
|
0 |
48 |
if((a - first) <= (last - b)) { |
|
461
|
0 |
0 |
if((last - b) <= (b - a)) { |
|
462
|
0 |
0 |
if(1 < (a - first)) { |
|
466
|
0 |
0 |
} else if(1 < (last - b)) { |
|
472
|
0 |
0 |
} else if((a - first) <= (b - a)) { |
|
473
|
0 |
0 |
if(1 < (a - first)) { |
|
487
|
48 |
0 |
if((a - first) <= (b - a)) { |
|
488
|
0 |
48 |
if(1 < (last - b)) { |
|
492
|
0 |
48 |
} else if(1 < (a - first)) { |
|
498
|
0 |
0 |
} else if((last - b) <= (b - a)) { |
|
499
|
0 |
0 |
if(1 < (last - b)) { |
|
514
|
0 |
0 |
if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; } |
|
|
0 |
0 |
if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; } |
|
515
|
0 |
0 |
if((a - first) <= (last - b)) { |
|
516
|
0 |
0 |
if(1 < (a - first)) { |
|
519
|
0 |
0 |
} else if(1 < (last - b)) { |
|
522
|
0 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
525
|
0 |
0 |
if(1 < (last - b)) { |
|
528
|
0 |
0 |
} else if(1 < (a - first)) { |
|
531
|
0 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
536
|
0 |
0 |
if(trbudget_check(budget, last - first)) { |
|
539
|
0 |
0 |
if(0 <= trlink) { stack[trlink].d = -1; } |
|
540
|
0 |
0 |
STACK_POP5(ISAd, first, last, limit, trlink); |
|
563
|
48 |
0 |
for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) { |
|
568
|
48 |
48 |
if((t = *first) < 0) { first -= t; skip += t; } |
|
570
|
48 |
0 |
if(skip != 0) { *(first + skip) = skip; skip = 0; } |
|
572
|
48 |
0 |
if(1 < (last - first)) { |
|
575
|
0 |
48 |
if(budget.count != 0) { unsorted += budget.count; } |
|
577
|
0 |
0 |
} else if((last - first) == 1) { |
|
582
|
48 |
48 |
} while(first < (SA + n)); |
|
583
|
48 |
0 |
if(skip != 0) { *(first + skip) = skip; } |
|
584
|
48 |
0 |
if(unsorted == 0) { break; } |