- /* We just started, or just reversed sense.
- ** Set t at end of pairs with the prevailing sense.
- */
- for (p = b+2, t = p; ++p < last; t = ++p) {
- if ((cmp(aTHX_ *t, *p) > 0) != sense) break;
- }
- q = b;
- /* Having laid out the playing field, look for long runs */
- do {
- p = r = b + (2 * PTHRESH);
- if (r >= t) p = r = t; /* too short to care about */
- else {
- while (((cmp(aTHX_ *(p-1), *p) > 0) == sense) &&
- ((p -= 2) > q)) {}
- if (p <= q) {
- /* b through r is a (long) run.
- ** Extend it as far as possible.
- */
- p = q = r;
- while (((p += 2) < t) &&
- ((cmp(aTHX_ *(p-1), *p) > 0) == sense)) q = p;
- r = p = q + 2; /* no simple pairs, no after-run */
- }
- }
- if (q > b) { /* run of greater than 2 at b */
- gptr *savep = p;
-
- p = q += 2;
- /* pick up singleton, if possible */
- if ((p == t) &&
- ((t + 1) == last) &&
- ((cmp(aTHX_ *(p-1), *p) > 0) == sense))
- savep = r = p = q = last;
- p2 = NEXT(p2) = p2 + (p - b); ++runs;
- if (sense)
- while (b < --p) {
- const gptr c = *b;
- *b++ = *p;
- *p = c;
- }
- p = savep;
- }
- while (q < p) { /* simple pairs */
- p2 = NEXT(p2) = p2 + 2; ++runs;
- if (sense) {
- const gptr c = *q++;
- *(q-1) = *q;
- *q++ = c;
- } else q += 2;
- }
- if (((b = p) == t) && ((t+1) == last)) {
- NEXT(p2) = p2 + 1; ++runs;
- b++;
- }
- q = r;
- } while (b < t);
- sense = !sense;
+ /* We just started, or just reversed sense.
+ ** Set t at end of pairs with the prevailing sense.
+ */
+ for (p = b+2, t = p; ++p < last; t = ++p) {
+ if ((cmp(aTHX_ *t, *p) > 0) != sense) break;
+ }
+ q = b;
+ /* Having laid out the playing field, look for long runs */
+ do {
+ p = r = b + (2 * PTHRESH);
+ if (r >= t) p = r = t; /* too short to care about */
+ else {
+ while (((cmp(aTHX_ *(p-1), *p) > 0) == sense) &&
+ ((p -= 2) > q)) {}
+ if (p <= q) {
+ /* b through r is a (long) run.
+ ** Extend it as far as possible.
+ */
+ p = q = r;
+ while (((p += 2) < t) &&
+ ((cmp(aTHX_ *(p-1), *p) > 0) == sense)) q = p;
+ r = p = q + 2; /* no simple pairs, no after-run */
+ }
+ }
+ if (q > b) { /* run of greater than 2 at b */
+ gptr *savep = p;
+
+ p = q += 2;
+ /* pick up singleton, if possible */
+ if ((p == t) &&
+ ((t + 1) == last) &&
+ ((cmp(aTHX_ *(p-1), *p) > 0) == sense))
+ savep = r = p = q = last;
+ p2 = NEXT(p2) = p2 + (p - b); ++runs;
+ if (sense)
+ while (b < --p) {
+ const gptr c = *b;
+ *b++ = *p;
+ *p = c;
+ }
+ p = savep;
+ }
+ while (q < p) { /* simple pairs */
+ p2 = NEXT(p2) = p2 + 2; ++runs;
+ if (sense) {
+ const gptr c = *q++;
+ *(q-1) = *q;
+ *q++ = c;
+ } else q += 2;
+ }
+ if (((b = p) == t) && ((t+1) == last)) {
+ NEXT(p2) = p2 + 1; ++runs;
+ b++;
+ }
+ q = r;
+ } while (b < t);
+ sense = !sense;
- /* On levels where both runs have be constructed (stackp->runs == 0),
- * merge them, and note the offset of their end, in case the offset
- * is needed at the next level up. Hop up a level, and,
- * as long as stackp->runs is 0, keep merging.
- */
- IV runs = stackp->runs;
- if (runs == 0) {
- gptr *list1, *list2;
- iwhich = level & 1;
- list1 = which[iwhich]; /* area where runs are now */
- list2 = which[++iwhich]; /* area for merged runs */
- do {
- gptr *l1, *l2, *tp2;
- offset = stackp->offset;
- f1 = p1 = list1 + offset; /* start of first run */
- p = tp2 = list2 + offset; /* where merged run will go */
- t = NEXT(p); /* where first run ends */
- f2 = l1 = POTHER(t, list2, list1); /* ... on the other side */
- t = NEXT(t); /* where second runs ends */
- l2 = POTHER(t, list2, list1); /* ... on the other side */
- offset = PNELEM(list2, t);
- while (f1 < l1 && f2 < l2) {
- /* If head 1 is larger than head 2, find ALL the elements
- ** in list 2 strictly less than head1, write them all,
- ** then head 1. Then compare the new heads, and repeat,
- ** until one or both lists are exhausted.
- **
- ** In all comparisons (after establishing
- ** which head to merge) the item to merge
- ** (at pointer q) is the first operand of
- ** the comparison. When we want to know
- ** if "q is strictly less than the other",
- ** we can't just do
- ** cmp(q, other) < 0
- ** because stability demands that we treat equality
- ** as high when q comes from l2, and as low when
- ** q was from l1. So we ask the question by doing
- ** cmp(q, other) <= sense
- ** and make sense == 0 when equality should look low,
- ** and -1 when equality should look high.
- */
-
- gptr *q;
- if (cmp(aTHX_ *f1, *f2) <= 0) {
- q = f2; b = f1; t = l1;
- sense = -1;
- } else {
- q = f1; b = f2; t = l2;
- sense = 0;
- }
-
-
- /* ramp up
- **
- ** Leave t at something strictly
- ** greater than q (or at the end of the list),
- ** and b at something strictly less than q.
- */
- for (i = 1, run = 0 ;;) {
- if ((p = PINDEX(b, i)) >= t) {
- /* off the end */
- if (((p = PINDEX(t, -1)) > b) &&
- (cmp(aTHX_ *q, *p) <= sense))
- t = p;
- else b = p;
- break;
- } else if (cmp(aTHX_ *q, *p) <= sense) {
- t = p;
- break;
- } else b = p;
- if (++run >= RTHRESH) i += i;
- }
-
-
- /* q is known to follow b and must be inserted before t.
- ** Increment b, so the range of possibilities is [b,t).
- ** Round binary split down, to favor early appearance.
- ** Adjust b and t until q belongs just before t.
- */
-
- b++;
- while (b < t) {
- p = PINDEX(b, (PNELEM(b, t) - 1) / 2);
- if (cmp(aTHX_ *q, *p) <= sense) {
- t = p;
- } else b = p + 1;
- }
-
-
- /* Copy all the strictly low elements */
-
- if (q == f1) {
- FROMTOUPTO(f2, tp2, t);
- *tp2++ = *f1++;
- } else {
- FROMTOUPTO(f1, tp2, t);
- *tp2++ = *f2++;
- }
- }
-
-
- /* Run out remaining list */
- if (f1 == l1) {
- if (f2 < l2) FROMTOUPTO(f2, tp2, l2);
- } else FROMTOUPTO(f1, tp2, l1);
- p1 = NEXT(p1) = POTHER(tp2, list2, list1);
-
- if (--level == 0) goto done;
- --stackp;
- t = list1; list1 = list2; list2 = t; /* swap lists */
- } while ((runs = stackp->runs) == 0);
- }
-
-
- stackp->runs = 0; /* current run will finish level */
- /* While there are more than 2 runs remaining,
- * turn them into exactly 2 runs (at the "other" level),
- * each made up of approximately half the runs.
- * Stack the second half for later processing,
- * and set about producing the first half now.
- */
- while (runs > 2) {
- ++level;
- ++stackp;
- stackp->offset = offset;
- runs -= stackp->runs = runs / 2;
- }
- /* We must construct a single run from 1 or 2 runs.
- * All the original runs are in which[0] == base.
- * The run we construct must end up in which[level&1].
- */
- iwhich = level & 1;
- if (runs == 1) {
- /* Constructing a single run from a single run.
- * If it's where it belongs already, there's nothing to do.
- * Otherwise, copy it to where it belongs.
- * A run of 1 is either a singleton at level 0,
- * or the second half of a split 3. In neither event
- * is it necessary to set offset. It will be set by the merge
- * that immediately follows.
- */
- if (iwhich) { /* Belongs in aux, currently in base */
- f1 = b = PINDEX(base, offset); /* where list starts */
- f2 = PINDEX(aux, offset); /* where list goes */
- t = NEXT(f2); /* where list will end */
- offset = PNELEM(aux, t); /* offset thereof */
- t = PINDEX(base, offset); /* where it currently ends */
- FROMTOUPTO(f1, f2, t); /* copy */
- NEXT(b) = t; /* set up parallel pointer */
- } else if (level == 0) goto done; /* single run at level 0 */
- } else {
- /* Constructing a single run from two runs.
- * The merge code at the top will do that.
- * We need only make sure the two runs are in the "other" array,
- * so they'll end up in the correct array after the merge.
- */
- ++level;
- ++stackp;
- stackp->offset = offset;
- stackp->runs = 0; /* take care of both runs, trigger merge */
- if (!iwhich) { /* Merged runs belong in aux, copy 1st */
- f1 = b = PINDEX(base, offset); /* where first run starts */
- f2 = PINDEX(aux, offset); /* where it will be copied */
- t = NEXT(f2); /* where first run will end */
- offset = PNELEM(aux, t); /* offset thereof */
- p = PINDEX(base, offset); /* end of first run */
- t = NEXT(t); /* where second run will end */
- t = PINDEX(base, PNELEM(aux, t)); /* where it now ends */
- FROMTOUPTO(f1, f2, t); /* copy both runs */
- NEXT(b) = p; /* paralleled pointer for 1st */
- NEXT(p) = t; /* ... and for second */
- }
- }
+ /* On levels where both runs have be constructed (stackp->runs == 0),
+ * merge them, and note the offset of their end, in case the offset
+ * is needed at the next level up. Hop up a level, and,
+ * as long as stackp->runs is 0, keep merging.
+ */
+ IV runs = stackp->runs;
+ if (runs == 0) {
+ gptr *list1, *list2;
+ iwhich = level & 1;
+ list1 = which[iwhich]; /* area where runs are now */
+ list2 = which[++iwhich]; /* area for merged runs */
+ do {
+ gptr *l1, *l2, *tp2;
+ offset = stackp->offset;
+ f1 = p1 = list1 + offset; /* start of first run */
+ p = tp2 = list2 + offset; /* where merged run will go */
+ t = NEXT(p); /* where first run ends */
+ f2 = l1 = POTHER(t, list2, list1); /* ... on the other side */
+ t = NEXT(t); /* where second runs ends */
+ l2 = POTHER(t, list2, list1); /* ... on the other side */
+ offset = PNELEM(list2, t);
+ while (f1 < l1 && f2 < l2) {
+ /* If head 1 is larger than head 2, find ALL the elements
+ ** in list 2 strictly less than head1, write them all,
+ ** then head 1. Then compare the new heads, and repeat,
+ ** until one or both lists are exhausted.
+ **
+ ** In all comparisons (after establishing
+ ** which head to merge) the item to merge
+ ** (at pointer q) is the first operand of
+ ** the comparison. When we want to know
+ ** if "q is strictly less than the other",
+ ** we can't just do
+ ** cmp(q, other) < 0
+ ** because stability demands that we treat equality
+ ** as high when q comes from l2, and as low when
+ ** q was from l1. So we ask the question by doing
+ ** cmp(q, other) <= sense
+ ** and make sense == 0 when equality should look low,
+ ** and -1 when equality should look high.
+ */
+
+ gptr *q;
+ if (cmp(aTHX_ *f1, *f2) <= 0) {
+ q = f2; b = f1; t = l1;
+ sense = -1;
+ } else {
+ q = f1; b = f2; t = l2;
+ sense = 0;
+ }
+
+
+ /* ramp up
+ **
+ ** Leave t at something strictly
+ ** greater than q (or at the end of the list),
+ ** and b at something strictly less than q.
+ */
+ for (i = 1, run = 0 ;;) {
+ if ((p = PINDEX(b, i)) >= t) {
+ /* off the end */
+ if (((p = PINDEX(t, -1)) > b) &&
+ (cmp(aTHX_ *q, *p) <= sense))
+ t = p;
+ else b = p;
+ break;
+ } else if (cmp(aTHX_ *q, *p) <= sense) {
+ t = p;
+ break;
+ } else b = p;
+ if (++run >= RTHRESH) i += i;
+ }
+
+
+ /* q is known to follow b and must be inserted before t.
+ ** Increment b, so the range of possibilities is [b,t).
+ ** Round binary split down, to favor early appearance.
+ ** Adjust b and t until q belongs just before t.
+ */
+
+ b++;
+ while (b < t) {
+ p = PINDEX(b, (PNELEM(b, t) - 1) / 2);
+ if (cmp(aTHX_ *q, *p) <= sense) {
+ t = p;
+ } else b = p + 1;
+ }
+
+
+ /* Copy all the strictly low elements */
+
+ if (q == f1) {
+ FROMTOUPTO(f2, tp2, t);
+ *tp2++ = *f1++;
+ } else {
+ FROMTOUPTO(f1, tp2, t);
+ *tp2++ = *f2++;
+ }
+ }
+
+
+ /* Run out remaining list */
+ if (f1 == l1) {
+ if (f2 < l2) FROMTOUPTO(f2, tp2, l2);
+ } else FROMTOUPTO(f1, tp2, l1);
+ p1 = NEXT(p1) = POTHER(tp2, list2, list1);
+
+ if (--level == 0) goto done;
+ --stackp;
+ t = list1; list1 = list2; list2 = t; /* swap lists */
+ } while ((runs = stackp->runs) == 0);
+ }
+
+
+ stackp->runs = 0; /* current run will finish level */
+ /* While there are more than 2 runs remaining,
+ * turn them into exactly 2 runs (at the "other" level),
+ * each made up of approximately half the runs.
+ * Stack the second half for later processing,
+ * and set about producing the first half now.
+ */
+ while (runs > 2) {
+ ++level;
+ ++stackp;
+ stackp->offset = offset;
+ runs -= stackp->runs = runs / 2;
+ }
+ /* We must construct a single run from 1 or 2 runs.
+ * All the original runs are in which[0] == base.
+ * The run we construct must end up in which[level&1].
+ */
+ iwhich = level & 1;
+ if (runs == 1) {
+ /* Constructing a single run from a single run.
+ * If it's where it belongs already, there's nothing to do.
+ * Otherwise, copy it to where it belongs.
+ * A run of 1 is either a singleton at level 0,
+ * or the second half of a split 3. In neither event
+ * is it necessary to set offset. It will be set by the merge
+ * that immediately follows.
+ */
+ if (iwhich) { /* Belongs in aux, currently in base */
+ f1 = b = PINDEX(base, offset); /* where list starts */
+ f2 = PINDEX(aux, offset); /* where list goes */
+ t = NEXT(f2); /* where list will end */
+ offset = PNELEM(aux, t); /* offset thereof */
+ t = PINDEX(base, offset); /* where it currently ends */
+ FROMTOUPTO(f1, f2, t); /* copy */
+ NEXT(b) = t; /* set up parallel pointer */
+ } else if (level == 0) goto done; /* single run at level 0 */
+ } else {
+ /* Constructing a single run from two runs.
+ * The merge code at the top will do that.
+ * We need only make sure the two runs are in the "other" array,
+ * so they'll end up in the correct array after the merge.
+ */
+ ++level;
+ ++stackp;
+ stackp->offset = offset;
+ stackp->runs = 0; /* take care of both runs, trigger merge */
+ if (!iwhich) { /* Merged runs belong in aux, copy 1st */
+ f1 = b = PINDEX(base, offset); /* where first run starts */
+ f2 = PINDEX(aux, offset); /* where it will be copied */
+ t = NEXT(f2); /* where first run will end */
+ offset = PNELEM(aux, t); /* offset thereof */
+ p = PINDEX(base, offset); /* end of first run */
+ t = NEXT(t); /* where second run will end */
+ t = PINDEX(base, PNELEM(aux, t)); /* where it now ends */
+ FROMTOUPTO(f1, f2, t); /* copy both runs */
+ NEXT(b) = p; /* paralleled pointer for 1st */
+ NEXT(p) = t; /* ... and for second */
+ }
+ }