jdk-sandbox: comparison src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java

equal deleted inserted replaced

-:d6d8fdc95ed2
+:8910b995a2ee
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
 package java.util;
-import java.util.concurrent.RecursiveAction;
 import java.util.concurrent.CountedCompleter;
 /**
 * Helper utilities for the parallel sort methods in Arrays.parallelSort.
 *
 * contain the Sorter and Merger implementations for that type:
 *
 * Sorter classes based mainly on CilkSort
 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
 * Basic algorithm:
-* if array size is small, just use a sequential quicksort (via Arrays.sort)
+* if array size is small, just use a sequential sort (via Arrays.sort)
 *         Otherwise:
 *         1. Break array in half.
 *         2. For each half,
 *             a. break the half in half (i.e., quarters),
 *             b. sort the quarters
 * requires some little tasks to serve as place holders for triggering
 * completion tasks.  These classes (EmptyCompleter and Relay) don't
 * need to keep track of the arrays, and are never themselves forked,
 * so don't hold any task state.
 *
-* The primitive class versions (FJByte... FJDouble) are
-* identical to each other except for type declarations.
-*
 * The base sequential sorts rely on non-public versions of TimSort,
-* ComparableTimSort, and DualPivotQuicksort sort methods that accept
+* ComparableTimSort sort methods that accept temp workspace array
-* temp workspace array slices that we will have already allocated, so
+* slices that we will have already allocated, so avoids redundant
-* avoids redundant allocation. (Except for DualPivotQuicksort byte[]
+* allocation.
-* sort, that does not ever use a workspace array.)
 */
 /*package*/ class ArraysParallelSortHelpers {
 /*
 * Style note: The task classes have a lot of parameters, that are
 Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
 wb+h, n-h, b, g, c));
 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
 b+u, n-u, wb+h, g, c));
 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
-new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
+new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();
 Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
 b+q, h-q, wb, g, c));
 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
 s = new EmptyCompleter(bc);
 n = q;
 else if (lb < lf)
 System.arraycopy(a, lb, w, k, lf - lb);
 tryComplete();
 }
+}
 }
-} // FJObject
-/** byte support class */
-static final class FJByte {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final byte[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-byte[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final byte[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, byte[] a, byte[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-byte[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-byte split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-byte split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-byte t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJByte
-/** char support class */
-static final class FJChar {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final char[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-char[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final char[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, char[] a, char[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-char[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-char split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-char split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-char t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJChar
-/** short support class */
-static final class FJShort {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final short[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-short[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final short[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, short[] a, short[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-short[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-short split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-short split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-short t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJShort
-/** int support class */
-static final class FJInt {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final int[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-int[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final int[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, int[] a, int[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-int[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-int split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-int split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-int t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJInt
-/** long support class */
-static final class FJLong {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final long[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-long[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final long[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, long[] a, long[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-long[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-long split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-long split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-long t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJLong
-/** float support class */
-static final class FJFloat {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final float[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-float[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final float[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, float[] a, float[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-float[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-float split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-float split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-float t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJFloat
-/** double support class */
-static final class FJDouble {
-static final class Sorter extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final double[] a, w;
-final int base, size, wbase, gran;
-Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
-int size, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w; this.base = base; this.size = size;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-CountedCompleter<?> s = this;
-double[] a = this.a, w = this.w; // localize all params
-int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-while (n > g) {
-int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-Relay fc = new Relay(new Merger(s, w, a, wb, h,
-wb+h, n-h, b, g));
-Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-b+u, n-u, wb+h, g));
-new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-Relay bc = new Relay(new Merger(fc, a, w, b, q,
-b+q, h-q, wb, g));
-new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-s = new EmptyCompleter(bc);
-n = q;
-}
-DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-s.tryComplete();
-}
-}
-static final class Merger extends CountedCompleter<Void> {
-@java.io.Serial
-static final long serialVersionUID = 2446542900576103244L;
-final double[] a, w; // main and workspace arrays
-final int lbase, lsize, rbase, rsize, wbase, gran;
-Merger(CountedCompleter<?> par, double[] a, double[] w,
-int lbase, int lsize, int rbase,
-int rsize, int wbase, int gran) {
-super(par);
-this.a = a; this.w = w;
-this.lbase = lbase; this.lsize = lsize;
-this.rbase = rbase; this.rsize = rsize;
-this.wbase = wbase; this.gran = gran;
-}
-public final void compute() {
-double[] a = this.a, w = this.w; // localize all params
-int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-rn = this.rsize, k = this.wbase, g = this.gran;
-if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-throw new IllegalStateException(); // hoist checks
-for (int lh, rh;;) {  // split larger, find point in smaller
-if (ln >= rn) {
-if (ln <= g)
-break;
-rh = rn;
-double split = a[(lh = ln >>> 1) + lb];
-for (int lo = 0; lo < rh; ) {
-int rm = (lo + rh) >>> 1;
-if (split <= a[rm + rb])
-rh = rm;
-else
-lo = rm + 1;
-}
-}
-else {
-if (rn <= g)
-break;
-lh = ln;
-double split = a[(rh = rn >>> 1) + rb];
-for (int lo = 0; lo < lh; ) {
-int lm = (lo + lh) >>> 1;
-if (split <= a[lm + lb])
-lh = lm;
-else
-lo = lm + 1;
-}
-}
-Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-rb + rh, rn - rh,
-k + lh + rh, g);
-rn = rh;
-ln = lh;
-addToPendingCount(1);
-m.fork();
-}
-int lf = lb + ln, rf = rb + rn; // index bounds
-while (lb < lf && rb < rf) {
-double t, al, ar;
-if ((al = a[lb]) <= (ar = a[rb])) {
-lb++; t = al;
-}
-else {
-rb++; t = ar;
-}
-w[k++] = t;
-}
-if (rb < rf)
-System.arraycopy(a, rb, w, k, rf - rb);
-else if (lb < lf)
-System.arraycopy(a, lb, w, k, lf - lb);
-tryComplete();
-}
-}
-} // FJDouble
 }

changeset 59042	8910b995a2ee
parent 58520	e036ee8bae56