Lines Matching refs:PA
167 ss_insertionsort(const sauchar_t *T, const saidx_t *PA, in ss_insertionsort() argument
174 for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) { in ss_insertionsort()
192 ss_fixdown(const sauchar_t *Td, const saidx_t *PA, in ss_fixdown() argument
198 for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { in ss_fixdown()
199 d = Td[PA[SA[k = j++]]]; in ss_fixdown()
200 if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; } in ss_fixdown()
209 ss_heapsort(const sauchar_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size) { in ss_heapsort() argument
216 if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); } in ss_heapsort()
219 for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); } in ss_heapsort()
220 if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); } in ss_heapsort()
223 ss_fixdown(Td, PA, SA, 0, i); in ss_heapsort()
234 ss_median3(const sauchar_t *Td, const saidx_t *PA, in ss_median3() argument
237 if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); } in ss_median3()
238 if(Td[PA[*v2]] > Td[PA[*v3]]) { in ss_median3()
239 if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; } in ss_median3()
248 ss_median5(const sauchar_t *Td, const saidx_t *PA, in ss_median5() argument
251 if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); } in ss_median5()
252 if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); } in ss_median5()
253 if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); } in ss_median5()
254 if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); } in ss_median5()
255 if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); } in ss_median5()
256 if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; } in ss_median5()
263 ss_pivot(const sauchar_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last) { in ss_pivot() argument
272 return ss_median3(Td, PA, first, middle, last - 1); in ss_pivot()
275 return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1); in ss_pivot()
279 first = ss_median3(Td, PA, first, first + t, first + (t << 1)); in ss_pivot()
280 middle = ss_median3(Td, PA, middle - t, middle, middle + t); in ss_pivot()
281 last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1); in ss_pivot()
282 return ss_median3(Td, PA, first, middle, last); in ss_pivot()
291 ss_partition(const saidx_t *PA, in ss_partition() argument
296 for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; } in ss_partition()
297 for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { } in ss_partition()
310 ss_mintrosort(const sauchar_t *T, const saidx_t *PA, in ss_mintrosort() argument
326 if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); } in ss_mintrosort()
333 if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); } in ss_mintrosort()
335 for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) { in ss_mintrosort()
336 if((x = Td[PA[*a]]) != v) { in ss_mintrosort()
342 if(Td[PA[*first] - 1] < v) { in ss_mintrosort()
343 first = ss_partition(PA, first, a, depth); in ss_mintrosort()
364 a = ss_pivot(Td, PA, first, last); in ss_mintrosort()
365 v = Td[PA[*a]]; in ss_mintrosort()
369 for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } in ss_mintrosort()
371 for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) { in ss_mintrosort()
375 for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { } in ss_mintrosort()
377 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { in ss_mintrosort()
383 for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) { in ss_mintrosort()
386 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { in ss_mintrosort()
400 b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth); in ss_mintrosort()
433 if(Td[PA[*first] - 1] < v) { in ss_mintrosort()
434 first = ss_partition(PA, first, last, depth); in ss_mintrosort()
502 ss_inplacemerge(const sauchar_t *T, const saidx_t *PA, in ss_inplacemerge() argument
512 if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); } in ss_inplacemerge()
513 else { x = 0; p = PA + *(last - 1); } in ss_inplacemerge()
518 q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth); in ss_inplacemerge()
545 ss_mergeforward(const sauchar_t *T, const saidx_t *PA, in ss_mergeforward() argument
556 r = ss_compare(T, PA + *b, PA + *c, depth); in ss_mergeforward()
595 ss_mergebackward(const sauchar_t *T, const saidx_t *PA, in ss_mergebackward() argument
608 if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; } in ss_mergebackward()
609 else { p1 = PA + *bufend; } in ss_mergebackward()
610 if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; } in ss_mergebackward()
611 else { p2 = PA + *(middle - 1); } in ss_mergebackward()
619 if(*b < 0) { p1 = PA + ~*b; x |= 1; } in ss_mergebackward()
620 else { p1 = PA + *b; } in ss_mergebackward()
629 if(*c < 0) { p2 = PA + ~*c; x |= 2; } in ss_mergebackward()
630 else { p2 = PA + *c; } in ss_mergebackward()
643 if(*b < 0) { p1 = PA + ~*b; x |= 1; } in ss_mergebackward()
644 else { p1 = PA + *b; } in ss_mergebackward()
645 if(*c < 0) { p2 = PA + ~*c; x |= 2; } in ss_mergebackward()
646 else { p2 = PA + *c; } in ss_mergebackward()
654 ss_swapmerge(const sauchar_t *T, const saidx_t *PA, in ss_swapmerge() argument
662 (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\ in ss_swapmerge()
665 if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\ in ss_swapmerge()
678 ss_mergebackward(T, PA, first, middle, last, buf, depth); in ss_swapmerge()
687 ss_mergeforward(T, PA, first, middle, last, buf, depth); in ss_swapmerge()
697 if(ss_compare(T, PA + GETIDX(*(middle + m + half)), in ss_swapmerge()
698 PA + GETIDX(*(middle - m - half - 1)), depth) < 0) { in ss_swapmerge()
728 if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) { in ss_swapmerge()
747 sssort(const sauchar_t *T, const saidx_t *PA, in sssort() argument
761 ss_mintrosort(T, PA, first, last, depth); in sssort()
773 ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth); in sssort()
775 ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth); in sssort()
781 ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth); in sssort()
785 ss_mintrosort(T, PA, a, middle, depth); in sssort()
787 ss_insertionsort(T, PA, a, middle, depth); in sssort()
791 ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth); in sssort()
797 ss_mintrosort(T, PA, middle, last, depth); in sssort()
799 ss_insertionsort(T, PA, middle, last, depth); in sssort()
801 ss_inplacemerge(T, PA, first, middle, last, depth); in sssort()
807 saidx_t PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2; in sssort()
809 (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); in sssort()