libdivsufsort/lib/sssort.c

264   saidx_t *middle;
268   middle = first + t / 2;
272       return ss_median3(Td, PA, first, middle, last - 1);
275       return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
280   middle = ss_median3(Td, PA, middle - t, middle, middle + t);
282   return ss_median3(Td, PA, first, middle, last);
461 ss_rotate(saidx_t *first, saidx_t *middle, saidx_t *last) {
464   l = middle - first, r = last - middle;
466     if(l == r) { ss_blockswap(first, middle, l); break; }
468       a = last - 1, b = middle - 1;
476           a -= 1, b = middle - 1;
481       a = first, b = middle;
489           a += 1, b = middle;
503                 saidx_t *first, saidx_t *middle, saidx_t *last,
514     for(a = first, len = middle - first, half = len >> 1, r = -1;
526     if(a < middle) {
528       ss_rotate(a, middle, last);
529       last -= middle - a;
530       middle = a;
531       if(first == middle) { break; }
535     if(middle == last) { break; }
546                 saidx_t *first, saidx_t *middle, saidx_t *last,
552   bufend = buf + (middle - first) - 1;
553   ss_blockswap(buf, first, middle - first);
555   for(t = *(a = first), b = buf, c = middle;;) {
596                  saidx_t *first, saidx_t *middle, saidx_t *last,
604   bufend = buf + (last - middle) - 1;
605   ss_blockswap(buf, middle, last - middle);
610   if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; }
611   else                  { p2 = PA +  *(middle - 1); }
612   for(t = *(a = last - 1), b = bufend, c = middle - 1;;) {
655              saidx_t *first, saidx_t *middle, saidx_t *last,
676     if((last - middle) <= bufsize) {
677       if((first < middle) && (middle < last)) {
678         ss_mergebackward(T, PA, first, middle, last, buf, depth);
681       STACK_POP(first, middle, last, check);
685     if((middle - first) <= bufsize) {
686       if(first < middle) {
687         ss_mergeforward(T, PA, first, middle, last, buf, depth);
690       STACK_POP(first, middle, last, check);
694     for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1;
697       if(ss_compare(T, PA + GETIDX(*(middle + m + half)),
698                        PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
705       lm = middle - m, rm = middle + m;
706       ss_blockswap(lm, middle, m);
707       l = r = middle, next = 0;
721         middle = lm, last = l, check = (check & 3) | (next & 4);
723         if((next & 2) && (r == middle)) { next ^= 6; }
725         first = r, middle = rm, check = (next & 3) | (check & 4);
728       if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
729         *middle = ~*middle;
732       STACK_POP(first, middle, last, check);
753   saidx_t *b, *middle, *curbuf;
767     buf = middle = last - limit, bufsize = limit;
769     middle = last, limit = 0;
771   for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) {
785   ss_mintrosort(T, PA, a, middle, depth);
787   ss_insertionsort(T, PA, a, middle, depth);
791       ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
797     ss_mintrosort(T, PA, middle, last, depth);
799     ss_insertionsort(T, PA, middle, last, depth);
801     ss_inplacemerge(T, PA, first, middle, last, depth);