--- jsr166/src/extra166y/PAS.java 2009/01/12 17:16:36 1.2 +++ jsr166/src/extra166y/PAS.java 2015/01/18 20:17:32 1.19 @@ -1,10 +1,11 @@ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ package extra166y; + import jsr166y.*; import static extra166y.Ops.*; import java.util.*; @@ -26,7 +27,7 @@ class PAS { static ForkJoinPool defaultExecutor() { ForkJoinPool p = defaultExecutor; // double-check if (p == null) { - synchronized(poolLock) { + synchronized (poolLock) { p = defaultExecutor; if (p == null) { // use ceil(7/8 * ncpus) @@ -56,7 +57,7 @@ class PAS { * subclass, prefixed FJO (object reference), FJD (double) and FJL * (long). */ - static abstract class FJBase extends RecursiveAction { + abstract static class FJBase extends RecursiveAction { final AbstractParallelAnyArray pap; final int lo; final int hi; @@ -676,7 +677,7 @@ class PAS { } } - void atLeaf(int l, int h) { + void atLeaf(int l, int h) { if (pap.hasFilter()) filteredAtLeaf(l, h); else { @@ -689,7 +690,7 @@ class PAS { } } - void filteredAtLeaf(int l, int h) { + void filteredAtLeaf(int l, int h) { for (int i = l; i < h; ++i) { if (pap.isSelected(i)) { Object x = pap.oget(i); @@ -772,7 +773,7 @@ class PAS { } } - void filteredAtLeaf(int l, int h) { + void filteredAtLeaf(int l, int h) { for (int i = l; i < h; ++i) { if (pap.isSelected(i)) { double x = pap.dget(i); @@ -843,7 +844,7 @@ class PAS { } } - void atLeaf(int l, int h) { + void atLeaf(int l, int h) { if (pap.hasFilter()) filteredAtLeaf(l, h); else { @@ -857,7 +858,7 @@ class PAS { } } - void filteredAtLeaf(int l, int h) { + void filteredAtLeaf(int l, int h) { for (int i = l; i < h; ++i) { if (pap.isSelected(i)) { long x = pap.lget(i); @@ -906,7 +907,7 @@ class PAS { * Base for cancellable search tasks. Same idea as FJBase * but cancels tasks when result nonnegative. */ - static abstract class FJSearchBase extends RecursiveAction { + abstract static class FJSearchBase extends RecursiveAction { final AbstractParallelAnyArray pap; final int lo; final int hi; @@ -1134,7 +1135,7 @@ class PAS { } } - static abstract class FJSelectAllDriver extends RecursiveAction { + abstract static class FJSelectAllDriver extends RecursiveAction { final int[] indices; final AbstractParallelAnyArray pap; final int initialOffset; @@ -1491,7 +1492,7 @@ class PAS { if ((filtered && !pap.isSelected(k)) || (x = src[k]) == null) continue; - int hc = byIdentity? System.identityHashCode(x): x.hashCode(); + int hc = byIdentity ? System.identityHashCode(x) : x.hashCode(); int hash = hash(hc); long entry = (((long)hash) << 32) + (k + 1); int idx = hash & mask; @@ -1524,7 +1525,7 @@ class PAS { continue; double x = src[k]; long bits = Double.doubleToLongBits(x); - int hash = hash((int)(bits ^ (bits >>> 32)));; + int hash = hash((int)(bits ^ (bits >>> 32))); long entry = (((long)hash) << 32) + (k + 1); int idx = hash & mask; for (;;) { @@ -1574,7 +1575,7 @@ class PAS { } /** - * Return new array holding all elements. + * Returns new array holding all elements. */ Object[] uniqueObjects(int size) { Object[] src = pap.ogetArray(); @@ -1657,7 +1658,7 @@ class PAS { this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1681,7 +1682,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - oquickSort(a, cmp, l, l+n-1); + Arrays.sort(a, l, l+n, cmp); } } @@ -1693,7 +1694,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1717,7 +1718,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - ocquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1730,7 +1731,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1766,7 +1767,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1790,7 +1791,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - dcquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1804,7 +1805,7 @@ class PAS { this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1840,7 +1841,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1865,7 +1866,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - lcquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1875,7 +1876,7 @@ class PAS { final RecursiveAction right; final RecursiveAction merger; FJSubSorter(RecursiveAction left, RecursiveAction right, - RecursiveAction merger){ + RecursiveAction merger) { this.left = left; this.right = right; this.merger = merger; } public void compute() { @@ -1887,7 +1888,7 @@ class PAS { } /** - * Perform merging for FJSorter. If big enough, splits Left + * Performs merging for FJSorter. If big enough, splits Left * partition in half; finds the greatest point in Right partition * less than the beginning of the second half of Left via binary * search; and then, in parallel, merges left half of Left with @@ -2305,111 +2306,8 @@ class PAS { /** Cutoff for when to use insertion-sort instead of quicksort */ static final int INSERTION_SORT_THRESHOLD = 8; - // Six nearly identical versions of quicksort + // versions of quicksort with comparators - static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - Object t = a[i]; - int j = i - 1; - while (j >= lo && cmp.compare(t, a[j]) < 0) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } - return; - } - - int mid = (lo + hi) >>> 1; - if (cmp.compare(a[lo], a[mid]) > 0) { - Object t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (cmp.compare(a[mid], a[hi]) > 0) { - Object t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (cmp.compare(a[lo], a[mid]) > 0) { - Object u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - Object pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (cmp.compare(pivot, a[right]) < 0) - --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) - ++left; - if (left < right) { - Object t = a[left]; a[left] = a[right]; a[right] = t; - --right; - } - else break; - } - - if (left - lo <= hi - right) { - oquickSort(a, cmp, lo, left); - lo = left + 1; - } - else { - oquickSort(a, cmp, right, hi); - hi = left; - } - } - } - - static void ocquickSort(Comparable[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - Comparable t = a[i]; - int j = i - 1; - while (j >= lo && t.compareTo(a[j]) < 0) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } - return; - } - - int mid = (lo + hi) >>> 1; - if (a[lo].compareTo(a[mid]) > 0) { - Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid].compareTo(a[hi]) > 0) { - Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo].compareTo(a[mid]) > 0) { - Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - Comparable pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot.compareTo(a[right]) < 0) - --right; - while (left < right && pivot.compareTo(a[left]) >= 0) - ++left; - if (left < right) { - Comparable t = a[left]; a[left] = a[right]; a[right] = t; - --right; - } - else break; - } - - if (left - lo <= hi - right) { - ocquickSort(a, lo, left); - lo = left + 1; - } - else { - ocquickSort(a, right, hi); - hi = left; - } - } - } static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { for (;;) { @@ -2440,63 +2338,17 @@ class PAS { double pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && + (c = cmp.compare(pivot, a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; - if (left < right) { - double t = a[left]; a[left] = a[right]; a[right] = t; - --right; } - else break; - } - - if (left - lo <= hi - right) { - dquickSort(a, cmp, lo, left); - lo = left + 1; - } - else { - dquickSort(a, cmp, right, hi); - hi = left; - } - } - } - - static void dcquickSort(double[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - double t = a[i]; - int j = i - 1; - while (j >= lo && t < a[j]) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } - return; - } - - int mid = (lo + hi) >>> 1; - if (a[lo] > a[mid]) { - double t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid] > a[hi]) { - double t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo] > a[mid]) { - double u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - double pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot < a[right]) - --right; - while (left < right && pivot >= a[left]) - ++left; if (left < right) { double t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2504,12 +2356,14 @@ class PAS { else break; } + if (sameLefts && right == hi - 1) + return; if (left - lo <= hi - right) { - dcquickSort(a, lo, left); + dquickSort(a, cmp, lo, left); lo = left + 1; } else { - dcquickSort(a, right, hi); + dquickSort(a, cmp, right, hi); hi = left; } } @@ -2544,63 +2398,17 @@ class PAS { long pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && + (c = cmp.compare(pivot, a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; - if (left < right) { - long t = a[left]; a[left] = a[right]; a[right] = t; - --right; - } - else break; - } - - if (left - lo <= hi - right) { - lquickSort(a, cmp, lo, left); - lo = left + 1; - } - else { - lquickSort(a, cmp, right, hi); - hi = left; - } - } - } - - static void lcquickSort(long[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - long t = a[i]; - int j = i - 1; - while (j >= lo && t < a[j]) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } - return; - } - - int mid = (lo + hi) >>> 1; - if (a[lo] > a[mid]) { - long t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid] > a[hi]) { - long t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo] > a[mid]) { - long u = a[lo]; a[lo] = a[mid]; a[mid] = u; } - } - - long pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot < a[right]) - --right; - while (left < right && pivot >= a[left]) - ++left; if (left < right) { long t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2608,12 +2416,14 @@ class PAS { else break; } + if (sameLefts && right == hi - 1) + return; if (left - lo <= hi - right) { - lcquickSort(a, lo, left); + lquickSort(a, cmp, lo, left); lo = left + 1; } else { - lcquickSort(a, right, hi); + lquickSort(a, cmp, right, hi); hi = left; } } @@ -2652,9 +2462,9 @@ class PAS { * * This class maintains only the basic control logic. Subclasses * maintain the "in" and "out" fields, and *Ops classes perform - * computations + * computations. */ - static abstract class FJScan extends ForkJoinTask { + abstract static class FJScan extends ForkJoinTask { static final short CUMULATE = (short)1; static final short SUMMED = (short)2; static final short FINISHED = (short)4; @@ -2709,7 +2519,7 @@ class PAS { int cb; for (;;) { // Establish action: sum, cumulate, or both int b = phase; - if ((b & FINISHED) != 0) // already done + if ((b & FINISHED) != 0) // already done return false; if ((b & CUMULATE) != 0) cb = FINISHED; @@ -2746,7 +2556,7 @@ class PAS { op.pushUp(par, par.left, par.right); int refork = ((pb & CUMULATE) == 0 && - par.lo == op.origin)? CUMULATE : 0; + par.lo == op.origin) ? CUMULATE : 0; int nextPhase = pb|cb|refork; if (pb == nextPhase || phaseUpdater.compareAndSet(par, pb, nextPhase)) { @@ -2821,9 +2631,9 @@ class PAS { } /** - * Computational operations for FJSCan + * Computational operations for FJScan */ - static abstract class FJScanOp { + abstract static class FJScanOp { final int threshold; final int origin; final int fence; @@ -2840,7 +2650,7 @@ class PAS { abstract FJScan newSubtask(FJScan parent, int lo, int hi); } - static abstract class FJOScanOp extends FJScanOp { + abstract static class FJOScanOp extends FJScanOp { final Object[] array; final Reducer reducer; final Object base; @@ -2930,7 +2740,7 @@ class PAS { } } - static abstract class FJDScanOp extends FJScanOp { + abstract static class FJDScanOp extends FJScanOp { final double[] array; final DoubleReducer reducer; final double base; @@ -3020,7 +2830,7 @@ class PAS { } } - static abstract class FJLScanOp extends FJScanOp { + abstract static class FJLScanOp extends FJScanOp { final long[] array; final LongReducer reducer; final long base; @@ -3112,7 +2922,7 @@ class PAS { // specialized versions for plus - static abstract class FJDScanPlusOp extends FJScanOp { + abstract static class FJDScanPlusOp extends FJScanOp { final double[] array; FJDScanPlusOp(AbstractParallelAnyArray.DPap pap) { super(pap); @@ -3194,7 +3004,7 @@ class PAS { } } - static abstract class FJLScanPlusOp extends FJScanOp { + abstract static class FJLScanPlusOp extends FJScanOp { final long[] array; FJLScanPlusOp(AbstractParallelAnyArray.LPap pap) { super(pap);