--- jsr166/src/extra166y/PAS.java 2010/05/25 13:39:40 1.7 +++ jsr166/src/extra166y/PAS.java 2011/03/15 19:47:02 1.14 @@ -1,7 +1,7 @@ /* * 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; @@ -26,7 +26,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) @@ -1491,7 +1491,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; @@ -1657,7 +1657,7 @@ class PAS { this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1693,7 +1693,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) { @@ -1730,7 +1730,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) { @@ -1754,7 +1754,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - Arrays.sort(a, l, l+n, cmp); + dquickSort(a, cmp, l, l+n-1); } } @@ -1766,7 +1766,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) { @@ -1804,7 +1804,7 @@ class PAS { this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1828,7 +1828,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - Arrays.sort(a, l, l+n, cmp); + lquickSort(a, cmp, l, l+n-1); } } @@ -1840,7 +1840,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) { @@ -2302,6 +2302,132 @@ class PAS { } } + /** Cutoff for when to use insertion-sort instead of quicksort */ + static final int INSERTION_SORT_THRESHOLD = 8; + + // versions of quicksort with comparators + + + static void dquickSort(double[] a, DoubleComparator cmp, 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 && 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) { + double t = a[lo]; a[lo] = a[mid]; a[mid] = t; + } + if (cmp.compare(a[mid], a[hi]) > 0) { + double t = a[mid]; a[mid] = a[hi]; a[hi] = t; + if (cmp.compare(a[lo], a[mid]) > 0) { + double u = a[lo]; a[lo] = a[mid]; a[mid] = u; + } + } + + double pivot = a[mid]; + int left = lo+1; + int right = hi-1; + boolean sameLefts = true; + for (;;) { + while (cmp.compare(pivot, a[right]) < 0) + --right; + 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 (sameLefts && right == hi - 1) + return; + if (left - lo <= hi - right) { + dquickSort(a, cmp, lo, left); + lo = left + 1; + } + else { + dquickSort(a, cmp, right, hi); + hi = left; + } + } + } + + static void lquickSort(long[] a, LongComparator cmp, 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 && 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) { + long t = a[lo]; a[lo] = a[mid]; a[mid] = t; + } + if (cmp.compare(a[mid], a[hi]) > 0) { + long t = a[mid]; a[mid] = a[hi]; a[hi] = t; + if (cmp.compare(a[lo], a[mid]) > 0) { + long u = a[lo]; a[lo] = a[mid]; a[mid] = u; + } + } + + long pivot = a[mid]; + int left = lo+1; + int right = hi-1; + boolean sameLefts = true; + for (;;) { + while (cmp.compare(pivot, a[right]) < 0) + --right; + 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 (sameLefts && right == hi - 1) + return; + if (left - lo <= hi - right) { + lquickSort(a, cmp, lo, left); + lo = left + 1; + } + else { + lquickSort(a, cmp, right, hi); + hi = left; + } + } + } + /** * Cumulative scan * @@ -2429,7 +2555,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)) {