Lines Matching full:first
258 int *first, int *last, int depth) { in ss_insertionsort() argument
263 for(i = last - 2; first <= i; --i) { 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()
358 middle = first + t / 2; 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()
369 first = ss_median3(Td, PA, first, first + t, first + (t << 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()
393 if(first < a) { *first = ~*first; } 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()
427 if(1 < (a - first)) { break; } in ss_mintrosort()
429 first = a; in ss_mintrosort()
432 if(Td[PA[*first] - 1] < v) { in ss_mintrosort()
433 first = ss_partition(PA, first, a, depth); in ss_mintrosort()
435 if((a - first) <= (last - a)) { in ss_mintrosort()
436 if(1 < (a - first)) { in ss_mintrosort()
438 last = a, depth += 1, limit = ss_ilg(a - first); in ss_mintrosort()
440 first = a, limit = -1; in ss_mintrosort()
444 STACK_PUSH(first, a, depth + 1, ss_ilg(a - first)); in ss_mintrosort()
445 first = a, limit = -1; 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()
456 SWAP(*first, *a); in ss_mintrosort()
459 for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } in ss_mintrosort()
484 if((s = a - first) > (t = b - a)) { s = t; } in ss_mintrosort()
485 for(e = first, f = b - 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()
497 } else if((a - first) <= (c - b)) { in ss_mintrosort()
503 STACK_PUSH(first, a, depth, limit); in ss_mintrosort()
504 first = b, last = c, depth += 1, limit = ss_ilg(c - b); in ss_mintrosort()
507 if((a - first) <= (c - b)) { in ss_mintrosort()
509 STACK_PUSH(first, a, depth, limit); in ss_mintrosort()
510 first = c; in ss_mintrosort()
512 STACK_PUSH(first, a, depth, limit); in ss_mintrosort()
514 first = c; in ss_mintrosort()
516 STACK_PUSH(first, a, depth, limit); in ss_mintrosort()
518 first = b, last = c, depth += 1, limit = ss_ilg(c - b); in ss_mintrosort()
523 if(Td[PA[*first] - 1] < v) { 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()
556 if(l == r) { ss_blockswap(first, middle, l); break; } in ss_rotate()
562 if(b < first) { in ss_rotate()
571 a = first, b = middle; in ss_rotate()
577 first = a + 1; in ss_rotate()
593 int *first, int *middle, int *last, in ss_inplacemerge() argument
604 for(a = first, len = middle - first, half = len >> 1, r = -1; in ss_inplacemerge()
621 if(first == middle) { break; } in ss_inplacemerge()
636 int *first, int *middle, int *last, in ss_mergeforward() argument
642 bufend = buf + (middle - first) - 1; in ss_mergeforward()
643 ss_blockswap(buf, first, middle - first); in ss_mergeforward()
645 for(t = *(a = first), b = buf, c = middle;;) { in ss_mergeforward()
686 int *first, int *middle, int *last, in ss_mergebackward() argument
714 if(c < first) { in ss_mergebackward()
728 if(c < first) { in ss_mergebackward()
745 int *first, int *middle, int *last, in ss_swapmerge() argument
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()
775 if((middle - first) <= bufsize) { in ss_swapmerge()
776 if(first < middle) { 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()
801 if(first < lm) { for(; *--l < 0;) { } next |= 4; } in ss_swapmerge()
803 } else if(first < lm) { in ss_swapmerge()
809 if((l - first) <= (last - r)) { in ss_swapmerge()
814 STACK_PUSH(first, lm, l, (check & 3) | (next & 4)); in ss_swapmerge()
815 first = r, middle = rm, check = (next & 3) | (check & 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
847 if(lastsuffix != 0) { ++first; } in sssort()
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()
860 for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) { in sssort()
890 ss_inplacemerge(T, PA, first, middle, last, depth); in sssort()
896 int PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2; in sssort()
897 for(a = first, i = *(first - 1); 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()
933 do { *(b + 1) = *b; } while((first <= --b) && (*b < 0)); in tr_insertionsort()
934 if(b < first) { break; } in tr_insertionsort()
1015 tr_pivot(const int *ISAd, int *first, int *last) { in tr_pivot() argument
1019 t = last - first; in tr_pivot()
1020 middle = first + t / 2; 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()
1031 first = tr_median3(ISAd, first, first + t, first + (t << 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
1101 if((s = a - first) > (t = b - a)) { s = t; } in tr_partition()
1102 for(e = first, f = b - 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
1121 for(c = first, d = a - 1; c <= d; ++c) { in tr_copy()
1138 int *first, int *a, int *b, int *last, in tr_partialcopy() argument
1146 for(c = first, d = a - 1; c <= d; ++c) { in tr_partialcopy()
1156 for(e = d; first <= e; --e) { 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()
1196 for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } in tr_introsort()
1205 STACK_PUSH5(ISAd - incr, first, last, -2, trlink); in tr_introsort()
1208 if((a - first) <= (last - b)) { in tr_introsort()
1209 if(1 < (a - first)) { in tr_introsort()
1211 last = a, limit = tr_ilg(a - first); 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()
1219 STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink); in tr_introsort()
1220 first = b, limit = tr_ilg(last - b); in tr_introsort()
1221 } else if(1 < (a - first)) { 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()
1239 if(0 <= *first) { in tr_introsort()
1240 a = first; in tr_introsort()
1242 first = a; in tr_introsort()
1244 if(first < last) { in tr_introsort()
1245 a = first; do { *a = ~*a; } while(*++a < 0); in tr_introsort()
1246 next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1; in tr_introsort()
1247 if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } in tr_introsort()
1250 if(trbudget_check(budget, a - first)) { in tr_introsort()
1251 if((a - first) <= (last - a)) { in tr_introsort()
1256 STACK_PUSH5(ISAd + incr, first, a, next, trlink); in tr_introsort()
1257 first = a, limit = -3; in tr_introsort()
1265 first = a, limit = -3; 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()
1286 for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } in tr_introsort()
1293 a = tr_pivot(ISAd, first, last); in tr_introsort()
1294 SWAP(*first, *a); in tr_introsort()
1295 v = ISAd[*first]; 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()
1303 for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } in tr_introsort()
1308 if((a - first) <= (last - b)) { in tr_introsort()
1310 if(1 < (a - first)) { in tr_introsort()
1316 first = b; in tr_introsort()
1318 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1320 } else if((a - first) <= (b - a)) { in tr_introsort()
1321 if(1 < (a - first)) { in tr_introsort()
1327 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1331 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
1332 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1335 if((a - first) <= (b - a)) { in tr_introsort()
1338 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
1339 first = b; in tr_introsort()
1340 } else if(1 < (a - first)) { in tr_introsort()
1344 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1348 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
1350 first = b; in tr_introsort()
1352 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
1353 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
1356 STACK_PUSH5(ISAd, first, a, 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()
1364 if(1 < (a - first)) { in tr_introsort()
1368 first = b; in tr_introsort()
1370 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
1374 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
1375 first = b; in tr_introsort()
1376 } else if(1 < (a - first)) { 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
1411 first = SA; in trsort()
1415 if((t = *first) < 0) { first -= t; skip += t; } in trsort()
1417 if(skip != 0) { *(first + skip) = skip; skip = 0; } 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()
1429 } while(first < (SA + n)); in trsort()
1430 if(skip != 0) { *(first + skip) = skip; } in trsort()
1460 /* Count the number of occurrences of the first one or two characters of each in sort_typeBstar()
1480 begins with the same first two characters. in sort_typeBstar()
1496 /* Sort the type B* suffixes by their first two characters. */ in sort_typeBstar()