< prev index next >
src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java
Print this page
*** 1,7 ****
/*
! * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
--- 1,7 ----
/*
! * Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
*** 34,55 ****
* 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)
* Otherwise:
* 1. Break array in half.
* 2. For each half,
* a. break the half in half (i.e., quarters),
* b. sort the quarters
* c. merge them together
* 3. merge together the two halves.
*
* One reason for splitting in quarters is that this guarantees that
! * the final sort is in the main array, not the workspace array.
! * (workspace and main swap roles on each subsort step.) Leaf-level
* sorts use the associated sequential sort.
*
* Merger classes perform merging for Sorter. They are structured
* such that if the underlying sort is stable (as is true for
* TimSort), then so is the full sort. If big enough, they split the
--- 34,55 ----
* 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 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
* c. merge them together
* 3. merge together the two halves.
*
* One reason for splitting in quarters is that this guarantees that
! * the final sort is in the main array, not the workspace array
! * (workspace and main swap roles on each subsort step). Leaf-level
* sorts use the associated sequential sort.
*
* Merger classes perform merging for Sorter. They are structured
* such that if the underlying sort is stable (as is true for
* TimSort), then so is the full sort. If big enough, they split the
*** 61,78 ****
* 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
! * temp workspace array slices that we will have already allocated, so
! * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
! * sort, that does not ever use a workspace array.)
*/
/*package*/ class ArraysParallelSortHelpers {
/*
* Style note: The task classes have a lot of parameters, that are
--- 61,74 ----
* 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 base sequential sorts rely on non-public versions of TimSort,
! * ComparableTimSort sort methods that accept temp workspace array
! * slices that we will have already allocated, so avoids redundant
! * allocation.
*/
/*package*/ class ArraysParallelSortHelpers {
/*
* Style note: The task classes have a lot of parameters, that are
*** 224,1010 ****
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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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> {
- 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
-
}
--- 220,227 ----
< prev index next >