Lines Matching refs:last
79 tr_insertionsort(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { in tr_insertionsort() argument
83 for(a = first + 1; a < last; ++a) { in tr_insertionsort()
167 tr_pivot(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { in tr_pivot() argument
171 t = last - first; in tr_pivot()
176 return tr_median3(ISAd, first, middle, last - 1); in tr_pivot()
179 return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1); in tr_pivot()
185 last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1); in tr_pivot()
186 return tr_median3(ISAd, first, middle, last); in tr_pivot()
223 saidx_t *first, saidx_t *middle, saidx_t *last, in tr_partition() argument
229 for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { } in tr_partition()
230 if(((a = b) < last) && (x < v)) { in tr_partition()
231 for(; (++b < last) && ((x = ISAd[*b]) <= v);) { in tr_partition()
235 for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { } in tr_partition()
255 if((s = d - c) > (t = last - d - 1)) { s = t; } in tr_partition()
256 for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } in tr_partition()
257 first += (b - a), last -= (d - c); in tr_partition()
259 *pa = first, *pb = last; in tr_partition()
265 saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, in tr_copy() argument
279 for(c = last - 1, e = d + 1, d = b; e < d; --c) { in tr_copy()
290 saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, in tr_partialcopy() argument
315 for(c = last - 1, e = d + 1, d = b; e < d; --c) { in tr_partialcopy()
328 saidx_t *SA, saidx_t *first, saidx_t *last, in tr_introsort() argument
339 for(ssize = 0, limit = tr_ilg(last - first);;) { in tr_introsort()
344 tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1); in tr_introsort()
347 if(a < last) { in tr_introsort()
350 if(b < last) { in tr_introsort()
357 STACK_PUSH5(ISAd - incr, first, last, -2, trlink); in tr_introsort()
360 if((a - first) <= (last - b)) { in tr_introsort()
362 STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink); in tr_introsort()
363 last = a, limit = tr_ilg(a - first); in tr_introsort()
364 } else if(1 < (last - b)) { in tr_introsort()
365 first = b, limit = tr_ilg(last - b); in tr_introsort()
367 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
370 if(1 < (last - b)) { in tr_introsort()
372 first = b, limit = tr_ilg(last - b); in tr_introsort()
374 last = a, limit = tr_ilg(a - first); in tr_introsort()
376 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
383 tr_copy(ISA, SA, first, a, b, last, ISAd - ISA); in tr_introsort()
386 tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA); in tr_introsort()
388 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
393 do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a)); in tr_introsort()
396 if(first < last) { in tr_introsort()
399 if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } in tr_introsort()
403 if((a - first) <= (last - a)) { in tr_introsort()
404 STACK_PUSH5(ISAd, a, last, -3, trlink); in tr_introsort()
405 ISAd += incr, last = a, limit = next; in tr_introsort()
407 if(1 < (last - a)) { in tr_introsort()
411 ISAd += incr, last = a, limit = next; in tr_introsort()
416 if(1 < (last - a)) { in tr_introsort()
419 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
423 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
429 if((last - first) <= TR_INSERTIONSORT_THRESHOLD) { in tr_introsort()
430 tr_insertionsort(ISAd, first, last); in tr_introsort()
436 tr_heapsort(ISAd, first, last - first); in tr_introsort()
437 for(a = last - 1; first < a; a = b) { in tr_introsort()
445 a = tr_pivot(ISAd, first, last); in tr_introsort()
450 tr_partition(ISAd, first, first + 1, last, &a, &b, v); in tr_introsort()
451 if((last - first) != (b - a)) { in tr_introsort()
456 if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } } in tr_introsort()
460 if((a - first) <= (last - b)) { in tr_introsort()
461 if((last - b) <= (b - a)) { in tr_introsort()
464 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
465 last = a; in tr_introsort()
466 } else if(1 < (last - b)) { in tr_introsort()
470 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
474 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
476 last = a; in tr_introsort()
478 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
479 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
482 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
484 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
488 if(1 < (last - b)) { in tr_introsort()
494 last = a; in tr_introsort()
496 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
498 } else if((last - b) <= (b - a)) { in tr_introsort()
499 if(1 < (last - b)) { in tr_introsort()
505 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
509 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
510 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
515 if((a - first) <= (last - b)) { in tr_introsort()
517 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
518 last = a; in tr_introsort()
519 } else if(1 < (last - b)) { in tr_introsort()
522 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
525 if(1 < (last - b)) { in tr_introsort()
529 last = a; in tr_introsort()
531 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
536 if(trbudget_check(budget, last - first)) { in tr_introsort()
537 limit = tr_ilg(last - first), ISAd += incr; in tr_introsort()
540 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
557 saidx_t *first, *last; in trsort() local
571 last = SA + ISA[t] + 1; in trsort()
572 if(1 < (last - first)) { in trsort()
574 tr_introsort(ISA, ISAd, SA, first, last, &budget); in trsort()
576 else { skip = first - last; } in trsort()
577 } else if((last - first) == 1) { in trsort()
580 first = last; in trsort()