Lines Matching refs:last
258 int *first, int *last, int depth) { in ss_insertionsort() argument
263 for(i = last - 2; first <= i; --i) { in ss_insertionsort()
265 do { *(j - 1) = *j; } while((++j < last) && (*j < 0)); in ss_insertionsort()
266 if(last <= j) { break; } in ss_insertionsort()
353 ss_pivot(const unsigned char *Td, const int *PA, int *first, int *last) { in ss_pivot() argument
357 t = last - first; in ss_pivot()
362 return ss_median3(Td, PA, first, middle, last - 1); in ss_pivot()
365 return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1); in ss_pivot()
371 last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1); in ss_pivot()
372 return ss_median3(Td, PA, first, middle, last); in ss_pivot()
382 int *first, int *last, int depth) { in ss_partition() argument
385 for(a = first - 1, b = last;;) { in ss_partition()
401 int *first, int *last, in ss_mintrosort() argument
412 for(ssize = 0, limit = ss_ilg(last - first);;) { in ss_mintrosort()
414 if((last - first) <= SS_INSERTIONSORT_THRESHOLD) { in ss_mintrosort()
416 if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); } in ss_mintrosort()
418 STACK_POP(first, last, depth, limit); in ss_mintrosort()
423 if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); } in ss_mintrosort()
425 for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) { in ss_mintrosort()
435 if((a - first) <= (last - a)) { in ss_mintrosort()
437 STACK_PUSH(a, last, depth, -1); in ss_mintrosort()
438 last = a, depth += 1, limit = ss_ilg(a - first); in ss_mintrosort()
443 if(1 < (last - a)) { in ss_mintrosort()
447 last = a, depth += 1, limit = ss_ilg(a - first); in ss_mintrosort()
454 a = ss_pivot(Td, PA, first, last); in ss_mintrosort()
459 for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } in ss_mintrosort()
460 if(((a = b) < last) && (x < v)) { in ss_mintrosort()
461 for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) { in ss_mintrosort()
465 for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { } in ss_mintrosort()
486 if((s = d - c) > (t = last - d - 1)) { s = t; } in ss_mintrosort()
487 for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } in ss_mintrosort()
489 a = first + (b - a), c = last - (d - c); in ss_mintrosort()
492 if((a - first) <= (last - c)) { in ss_mintrosort()
493 if((last - c) <= (c - b)) { in ss_mintrosort()
495 STACK_PUSH(c, last, depth, limit); in ss_mintrosort()
496 last = a; in ss_mintrosort()
498 STACK_PUSH(c, last, depth, limit); in ss_mintrosort()
500 last = a; in ss_mintrosort()
502 STACK_PUSH(c, last, depth, limit); in ss_mintrosort()
504 first = b, last = c, depth += 1, limit = ss_ilg(c - b); in ss_mintrosort()
511 } else if((last - c) <= (c - b)) { in ss_mintrosort()
517 STACK_PUSH(c, last, depth, limit); in ss_mintrosort()
518 first = b, last = c, depth += 1, limit = ss_ilg(c - b); in ss_mintrosort()
524 first = ss_partition(PA, first, last, depth); in ss_mintrosort()
525 limit = ss_ilg(last - first); in ss_mintrosort()
551 ss_rotate(int *first, int *middle, int *last) { in ss_rotate() argument
554 l = middle - first, r = last - middle; in ss_rotate()
558 a = last - 1, b = middle - 1; in ss_rotate()
564 last = a; in ss_rotate()
575 if(last <= b) { in ss_rotate()
593 int *first, int *middle, int *last, in ss_inplacemerge() argument
602 if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); } in ss_inplacemerge()
603 else { x = 0; p = PA + *(last - 1); } in ss_inplacemerge()
618 ss_rotate(a, middle, last); in ss_inplacemerge()
619 last -= middle - a; in ss_inplacemerge()
623 --last; in ss_inplacemerge()
624 if(x != 0) { while(*--last < 0) { } } in ss_inplacemerge()
625 if(middle == last) { break; } in ss_inplacemerge()
636 int *first, int *middle, int *last, in ss_mergeforward() argument
656 if(last <= c) { in ss_mergeforward()
672 if(last <= c) { in ss_mergeforward()
686 int *first, int *middle, int *last, in ss_mergebackward() argument
694 bufend = buf + (last - middle) - 1; in ss_mergebackward()
695 ss_blockswap(buf, middle, last - middle); in ss_mergebackward()
702 for(t = *(a = last - 1), b = bufend, c = middle - 1;;) { in ss_mergebackward()
745 int *first, int *middle, int *last, in ss_swapmerge() argument
766 if((last - middle) <= bufsize) { in ss_swapmerge()
767 if((first < middle) && (middle < last)) { in ss_swapmerge()
768 ss_mergebackward(T, PA, first, middle, last, buf, depth); in ss_swapmerge()
770 MERGE_CHECK(first, last, check); in ss_swapmerge()
771 STACK_POP(first, middle, last, check); in ss_swapmerge()
777 ss_mergeforward(T, PA, first, middle, last, buf, depth); in ss_swapmerge()
779 MERGE_CHECK(first, last, check); in ss_swapmerge()
780 STACK_POP(first, middle, last, check); in ss_swapmerge()
784 for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1; in ss_swapmerge()
798 if(rm < last) { in ss_swapmerge()
809 if((l - first) <= (last - r)) { in ss_swapmerge()
810 STACK_PUSH(r, rm, last, (next & 3) | (check & 4)); in ss_swapmerge()
811 middle = lm, last = l, check = (check & 3) | (next & 4); in ss_swapmerge()
821 MERGE_CHECK(first, last, check); in ss_swapmerge()
822 STACK_POP(first, middle, last, check); in ss_swapmerge()
837 int *first, int *last, in sssort() argument
850 ss_mintrosort(T, PA, first, last, depth); in sssort()
853 (bufsize < (last - first)) && in sssort()
854 (bufsize < (limit = ss_isqrt(last - first)))) { in sssort()
856 buf = middle = last - limit, bufsize = limit; in sssort()
858 middle = last, limit = 0; in sssort()
866 curbufsize = last - (a + SS_BLOCKSIZE); in sssort()
886 ss_mintrosort(T, PA, middle, last, depth); in sssort()
888 ss_insertionsort(T, PA, middle, last, depth); in sssort()
890 ss_inplacemerge(T, PA, first, middle, last, depth); in sssort()
898 (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); in sssort()
927 tr_insertionsort(const int *ISAd, int *first, int *last) { in tr_insertionsort() argument
931 for(a = first + 1; a < last; ++a) { in tr_insertionsort()
1015 tr_pivot(const int *ISAd, int *first, int *last) { in tr_pivot() argument
1019 t = last - first; in tr_pivot()
1024 return tr_median3(ISAd, first, middle, last - 1); in tr_pivot()
1027 return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1); in tr_pivot()
1033 last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1); in tr_pivot()
1034 return tr_median3(ISAd, first, middle, last); in tr_pivot()
1071 int *first, int *middle, int *last, in tr_partition() argument
1077 for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { } in tr_partition()
1078 if(((a = b) < last) && (x < v)) { in tr_partition()
1079 for(; (++b < last) && ((x = ISAd[*b]) <= v);) { in tr_partition()
1083 for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { } in tr_partition()
1103 if((s = d - c) > (t = last - d - 1)) { s = t; } in tr_partition()
1104 for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } in tr_partition()
1105 first += (b - a), last -= (d - c); in tr_partition()
1107 *pa = first, *pb = last; in tr_partition()
1113 int *first, int *a, int *b, int *last, in tr_copy() argument
1127 for(c = last - 1, e = d + 1, d = b; e < d; --c) { in tr_copy()
1138 int *first, int *a, int *b, int *last, in tr_partialcopy() argument
1163 for(c = last - 1, e = d + 1, d = b; e < d; --c) { in tr_partialcopy()
1176 int *SA, int *first, int *last, in tr_introsort() argument
1187 for(ssize = 0, limit = tr_ilg(last - first);;) { in tr_introsort()
1192 tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1); in tr_introsort()
1195 if(a < last) { in tr_introsort()
1198 if(b < last) { in tr_introsort()
1205 STACK_PUSH5(ISAd - incr, first, last, -2, trlink); in tr_introsort()
1208 if((a - first) <= (last - b)) { in tr_introsort()
1210 STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink); in tr_introsort()
1211 last = a, limit = tr_ilg(a - first); in tr_introsort()
1212 } else if(1 < (last - b)) { in tr_introsort()
1213 first = b, limit = tr_ilg(last - b); in tr_introsort()
1215 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1218 if(1 < (last - b)) { in tr_introsort()
1220 first = b, limit = tr_ilg(last - b); in tr_introsort()
1222 last = a, limit = tr_ilg(a - first); in tr_introsort()
1224 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1231 tr_copy(ISA, SA, first, a, b, last, ISAd - ISA); in tr_introsort()
1234 tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA); in tr_introsort()
1236 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1241 do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a)); in tr_introsort()
1244 if(first < last) { in tr_introsort()
1247 if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } in tr_introsort()
1251 if((a - first) <= (last - a)) { in tr_introsort()
1252 STACK_PUSH5(ISAd, a, last, -3, trlink); in tr_introsort()
1253 ISAd += incr, last = a, limit = next; in tr_introsort()
1255 if(1 < (last - a)) { in tr_introsort()
1259 ISAd += incr, last = a, limit = next; in tr_introsort()
1264 if(1 < (last - a)) { in tr_introsort()
1267 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1271 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1277 if((last - first) <= TR_INSERTIONSORT_THRESHOLD) { in tr_introsort()
1278 tr_insertionsort(ISAd, first, last); in tr_introsort()
1284 tr_heapsort(ISAd, first, last - first); in tr_introsort()
1285 for(a = last - 1; first < a; a = b) { in tr_introsort()
1293 a = tr_pivot(ISAd, first, last); in tr_introsort()
1298 tr_partition(ISAd, first, first + 1, last, &a, &b, v); in tr_introsort()
1299 if((last - first) != (b - a)) { in tr_introsort()
1304 if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } } in tr_introsort()
1308 if((a - first) <= (last - b)) { in tr_introsort()
1309 if((last - b) <= (b - a)) { in tr_introsort()
1312 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
1313 last = a; in tr_introsort()
1314 } else if(1 < (last - b)) { in tr_introsort()
1318 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1322 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
1324 last = a; in tr_introsort()
1326 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
1327 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1330 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
1332 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1336 if(1 < (last - b)) { in tr_introsort()
1342 last = a; in tr_introsort()
1344 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1346 } else if((last - b) <= (b - a)) { in tr_introsort()
1347 if(1 < (last - b)) { in tr_introsort()
1353 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1357 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
1358 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1363 if((a - first) <= (last - b)) { in tr_introsort()
1365 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
1366 last = a; in tr_introsort()
1367 } else if(1 < (last - b)) { in tr_introsort()
1370 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1373 if(1 < (last - b)) { in tr_introsort()
1377 last = a; in tr_introsort()
1379 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1384 if(trbudget_check(budget, last - first)) { in tr_introsort()
1385 limit = tr_ilg(last - first), ISAd += incr; in tr_introsort()
1388 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1404 int *first, *last; in trsort() local
1418 last = SA + ISA[t] + 1; in trsort()
1419 if(1 < (last - first)) { in trsort()
1421 tr_introsort(ISA, ISAd, SA, first, last, &budget); in trsort()
1423 else { skip = first - last; } in trsort()
1424 } else if((last - first) == 1) { in trsort()
1427 first = last; in trsort()