Lines Matching refs:ISAd
79 tr_insertionsort(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { in tr_insertionsort() argument
84 for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) { in tr_insertionsort()
98 tr_fixdown(const saidx_t *ISAd, saidx_t *SA, saidx_t i, saidx_t size) { in tr_fixdown() argument
103 for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { in tr_fixdown()
104 d = ISAd[SA[k = j++]]; in tr_fixdown()
105 if(d < (e = ISAd[SA[j]])) { k = j; d = e; } in tr_fixdown()
114 tr_heapsort(const saidx_t *ISAd, saidx_t *SA, saidx_t size) { in tr_heapsort() argument
121 if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); } in tr_heapsort()
124 for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); } in tr_heapsort()
125 if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); } in tr_heapsort()
128 tr_fixdown(ISAd, SA, 0, i); in tr_heapsort()
139 tr_median3(const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3) { in tr_median3() argument
141 if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); } in tr_median3()
142 if(ISAd[*v2] > ISAd[*v3]) { in tr_median3()
143 if(ISAd[*v1] > ISAd[*v3]) { return v1; } in tr_median3()
152 tr_median5(const saidx_t *ISAd, in tr_median5() argument
155 if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); } in tr_median5()
156 if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); } in tr_median5()
157 if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); } in tr_median5()
158 if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); } in tr_median5()
159 if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); } in tr_median5()
160 if(ISAd[*v3] > ISAd[*v4]) { return v4; } in tr_median5()
167 tr_pivot(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { in tr_pivot() argument
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()
183 first = tr_median3(ISAd, first, first + t, first + (t << 1)); in tr_pivot()
184 middle = tr_median3(ISAd, middle - t, middle, middle + t); 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()
222 tr_partition(const saidx_t *ISAd, in tr_partition() argument
229 for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == 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()
237 for(; (b < --c) && ((x = ISAd[*c]) >= v);) { in tr_partition()
243 for(; (++b < c) && ((x = ISAd[*b]) <= v);) { in tr_partition()
246 for(; (b < --c) && ((x = ISAd[*c]) >= v);) { in tr_partition()
327 tr_introsort(saidx_t *ISA, const saidx_t *ISAd, in tr_introsort() argument
335 saidx_t incr = ISAd - ISA; in tr_introsort()
344 tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1); in tr_introsort()
357 STACK_PUSH5(ISAd - incr, first, last, -2, trlink); in tr_introsort()
362 STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink); in tr_introsort()
367 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
371 STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink); 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()
398 next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1; in tr_introsort()
404 STACK_PUSH5(ISAd, a, last, -3, trlink); in tr_introsort()
405 ISAd += incr, last = a, limit = next; in tr_introsort()
408 STACK_PUSH5(ISAd + incr, first, a, next, trlink); in tr_introsort()
411 ISAd += incr, last = a, limit = next; 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()
430 tr_insertionsort(ISAd, first, last); in tr_introsort()
436 tr_heapsort(ISAd, first, last - first); in tr_introsort()
438 for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } in tr_introsort()
445 a = tr_pivot(ISAd, first, last); in tr_introsort()
447 v = ISAd[*first]; in tr_introsort()
450 tr_partition(ISAd, first, first + 1, last, &a, &b, v); in tr_introsort()
463 STACK_PUSH5(ISAd + incr, a, b, next, trlink); in tr_introsort()
464 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
467 STACK_PUSH5(ISAd + incr, a, b, next, trlink); 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()
475 STACK_PUSH5(ISAd + incr, a, b, next, trlink); 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()
483 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
484 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
489 STACK_PUSH5(ISAd + incr, a, b, next, trlink); in tr_introsort()
490 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
493 STACK_PUSH5(ISAd + incr, a, b, next, trlink); in tr_introsort()
496 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
500 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
501 STACK_PUSH5(ISAd + incr, a, b, next, trlink); in tr_introsort()
504 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
505 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
508 STACK_PUSH5(ISAd, first, a, limit, trlink); 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()
517 STACK_PUSH5(ISAd, b, last, limit, trlink); in tr_introsort()
522 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
526 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
531 STACK_POP5(ISAd, first, last, limit, trlink); 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()
556 saidx_t *ISAd; in trsort() local
563 for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) { in trsort()
574 tr_introsort(ISA, ISAd, SA, first, last, &budget); in trsort()