| line |
true |
false |
branch |
|
68
|
29837 |
4561 |
for (i = 1; i < len; i++) { |
|
70
|
46197 |
1058 |
for (j = i; j > 0 && array[j-1] > t; j--) |
|
|
17418 |
28779 |
for (j = i; j > 0 && array[j-1] > t; j--) |
|
77
|
216 |
49 |
for (i = 1; i < len; i++) { |
|
79
|
593 |
59 |
for (j = i; j > 0 && array[j-1] > t; j--) |
|
|
436 |
157 |
for (j = i; j > 0 && array[j-1] > t; j--) |
|
128
|
1728 |
1 |
for (i = 0; i < n; i++) { |
|
133
|
0 |
1 |
if (passmask < RADIX) { /* If all values < RADIX, Use *fast* counting sort */ |
|
134
|
0 |
0 |
if (passmask) { |
|
136
|
0 |
0 |
for (r = 0; r < RADIX; r++) |
|
137
|
0 |
0 |
for (lim += count[r]; j < lim; j++) |
|
145
|
0 |
1 |
if (b == 0) return 0; |
|
147
|
7 |
1 |
for (sh = 0; UV_MAX >> sh >= RADIX; sh += RADIX_BIT) { |
|
149
|
3 |
4 |
if ((passmask >> sh) % RADIX == 0) |
|
151
|
1024 |
4 |
for (r = 0; r < RADIX; r++) { |
|
157
|
6912 |
4 |
for (i = 0; i < n; i++) { |
|
165
|
0 |
1 |
if (passmask >> sh) { |
|
167
|
0 |
0 |
unsigned signbit = is_iv ? 1 << (BITS_PER_WORD-1)%RADIX_BIT : 0; |
|
168
|
0 |
0 |
for (r = 0; r < RADIX; r++) { |
|
173
|
0 |
0 |
for (i = 0; i < n; i++) { |
|
180
|
0 |
1 |
if (a != array) { |
|
197
|
0 |
0 |
if (!a) /* Trivial cases: len < 2 */ |
|
209
|
0 |
0 |
if (a > 0) /* Building heap: sift down array[--a] */ |
|
211
|
0 |
0 |
else if (len > 0) { /* Extracting: Swap root<->array[n--] */ |
|
217
|
0 |
0 |
if (!is_iv) { |
|
218
|
0 |
0 |
for (b = a; (c = 2*b + 1) < len; b = c) { |
|
220
|
0 |
0 |
if (array[c+1] >= s) |
|
222
|
0 |
0 |
if (r >= s) |
|
227
|
0 |
0 |
for (b = a; (c = 2*b + 1) < len; b = c) { |
|
229
|
0 |
0 |
if ((IV)array[c+1] >= s) |
|
231
|
0 |
0 |
if ((IV)r >= s) |
|
236
|
0 |
0 |
if (c == len) { /* Corner case: last leaf with no sibling */ |
|
237
|
0 |
0 |
if ( (!is_iv && r < array[c]) || (is_iv && (IV)r < (IV)array[c]) ) { |
|
|
0 |
0 |
if ( (!is_iv && r < array[c]) || (is_iv && (IV)r < (IV)array[c]) ) { |
|
|
0 |
0 |
if ( (!is_iv && r < array[c]) || (is_iv && (IV)r < (IV)array[c]) ) { |
|
|
0 |
0 |
if ( (!is_iv && r < array[c]) || (is_iv && (IV)r < (IV)array[c]) ) { |
|
274
|
171 |
165 |
x = L[0] > L[1]; swap = L[!x]; L[0]=L[x]; L[1]=swap; |
|
275
|
187 |
149 |
L += 2; x = L[0] > L[1]; swap = L[!x]; L[0]=L[x]; L[1]=swap; |
|
276
|
187 |
149 |
L -= 2; x = (L[0] <= L[2]) * 2; L[2] = L[x]; |
|
277
|
151 |
185 |
L += 1; x = (L[0] > L[2]) * 2; L[0] = L[x]; |
|
282
|
1 |
5 |
x = L[0] > L[1]; swap = L[!x]; L[0]=L[x]; L[1]=swap; |
|
283
|
4 |
2 |
L += 2; x = L[0] > L[1]; swap = L[!x]; L[0]=L[x]; L[1]=swap; |
|
284
|
1 |
5 |
L -= 2; x = (L[0] <= L[2]) * 2; L[2] = L[x]; |
|
285
|
3 |
3 |
L += 1; x = (L[0] > L[2]) * 2; L[0] = L[x]; |
|
294
|
0 |
629 |
if (len <= 7) { |
|
296
|
517 |
112 |
} else if (len <= 40) { |
|
301
|
1008 |
112 |
for (x = 0; x < 9; x++) { swap[x] = *X; X += step; } |
|
309
|
9761 |
4571 |
do { i++; } while (L[i] < pivot); |
|
310
|
7300 |
4571 |
do { j--; } while (L[j] > pivot); |
|
311
|
629 |
3942 |
if (i >= j) return j; |
|
318
|
0 |
8 |
if (len <= 7) { |
|
320
|
6 |
2 |
} else if (len <= 40) { |
|
325
|
18 |
2 |
for (x = 0; x < 9; x++) { swap[x] = *X; X += step; } |
|
333
|
68 |
61 |
do { i++; } while (L[i] < pivot); |
|
334
|
58 |
61 |
do { j--; } while (L[j] > pivot); |
|
335
|
8 |
53 |
if (i >= j) return j; |
|
343
|
4561 |
629 |
if (size <= 16) |
|
351
|
626 |
3 |
bool highly_unbalanced = l_size < size / 8 || r_size < size / 8; |
|
|
2 |
624 |
bool highly_unbalanced = l_size < size / 8 || r_size < size / 8; |
|
352
|
5 |
624 |
if (highly_unbalanced && --badpartsleft <= 0) |
|
|
0 |
5 |
if (highly_unbalanced && --badpartsleft <= 0) |
|
362
|
49 |
8 |
if (size <= 16) |
|
370
|
8 |
0 |
bool highly_unbalanced = l_size < size / 8 || r_size < size / 8; |
|
|
0 |
8 |
bool highly_unbalanced = l_size < size / 8 || r_size < size / 8; |
|
371
|
0 |
8 |
if (highly_unbalanced && --badpartsleft <= 0) |
|
|
0 |
0 |
if (highly_unbalanced && --badpartsleft <= 0) |
|
380
|
3932 |
69 |
if (len > 1) _qs_uv(L, 0, len-1, log2floor(len)); |
|
|
3932 |
0 |
if (len > 1) _qs_uv(L, 0, len-1, log2floor(len)); |
|
383
|
41 |
0 |
if (len > 1) _qs_iv(L, 0, len-1, log2floor(len)); |
|
|
41 |
0 |
if (len > 1) _qs_iv(L, 0, len-1, log2floor(len)); |
|
397
|
4001 |
1 |
if (len < 800) { |
|
403
|
0 |
1 |
if (!radixsort_uv(L, len)) |
|
410
|
41 |
0 |
if (len < 800) { |
|
413
|
0 |
0 |
if (!radixsort_iv(L, len)) /* radixsort could fail aux allocation */ |
|
424
|
68 |
0 |
if (*len > 1) { |
|
426
|
27 |
41 |
if (data_is_signed) sort_iv_array((IV *)L, *len); |
|
428
|
329 |
68 |
for (i=0, j=1; j < *len; j++) { |