1 |
|
/* |
2 |
|
* Written by Doug Lea with assistance from members of JCP JSR-166 |
3 |
|
* Expert Group and released to the public domain, as explained at |
4 |
< |
* http://creativecommons.org/licenses/publicdomain |
4 |
> |
* http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
|
*/ |
6 |
|
|
7 |
|
package extra166y; |
26 |
|
static ForkJoinPool defaultExecutor() { |
27 |
|
ForkJoinPool p = defaultExecutor; // double-check |
28 |
|
if (p == null) { |
29 |
< |
synchronized(poolLock) { |
29 |
> |
synchronized (poolLock) { |
30 |
|
p = defaultExecutor; |
31 |
|
if (p == null) { |
32 |
|
// use ceil(7/8 * ncpus) |
56 |
|
* subclass, prefixed FJO (object reference), FJD (double) and FJL |
57 |
|
* (long). |
58 |
|
*/ |
59 |
< |
static abstract class FJBase extends RecursiveAction { |
59 |
> |
abstract static class FJBase extends RecursiveAction { |
60 |
|
final AbstractParallelAnyArray pap; |
61 |
|
final int lo; |
62 |
|
final int hi; |
676 |
|
} |
677 |
|
} |
678 |
|
|
679 |
< |
void atLeaf(int l, int h) { |
679 |
> |
void atLeaf(int l, int h) { |
680 |
|
if (pap.hasFilter()) |
681 |
|
filteredAtLeaf(l, h); |
682 |
|
else { |
689 |
|
} |
690 |
|
} |
691 |
|
|
692 |
< |
void filteredAtLeaf(int l, int h) { |
692 |
> |
void filteredAtLeaf(int l, int h) { |
693 |
|
for (int i = l; i < h; ++i) { |
694 |
|
if (pap.isSelected(i)) { |
695 |
|
Object x = pap.oget(i); |
772 |
|
} |
773 |
|
} |
774 |
|
|
775 |
< |
void filteredAtLeaf(int l, int h) { |
775 |
> |
void filteredAtLeaf(int l, int h) { |
776 |
|
for (int i = l; i < h; ++i) { |
777 |
|
if (pap.isSelected(i)) { |
778 |
|
double x = pap.dget(i); |
843 |
|
} |
844 |
|
} |
845 |
|
|
846 |
< |
void atLeaf(int l, int h) { |
846 |
> |
void atLeaf(int l, int h) { |
847 |
|
if (pap.hasFilter()) |
848 |
|
filteredAtLeaf(l, h); |
849 |
|
else { |
857 |
|
} |
858 |
|
} |
859 |
|
|
860 |
< |
void filteredAtLeaf(int l, int h) { |
860 |
> |
void filteredAtLeaf(int l, int h) { |
861 |
|
for (int i = l; i < h; ++i) { |
862 |
|
if (pap.isSelected(i)) { |
863 |
|
long x = pap.lget(i); |
906 |
|
* Base for cancellable search tasks. Same idea as FJBase |
907 |
|
* but cancels tasks when result nonnegative. |
908 |
|
*/ |
909 |
< |
static abstract class FJSearchBase extends RecursiveAction { |
909 |
> |
abstract static class FJSearchBase extends RecursiveAction { |
910 |
|
final AbstractParallelAnyArray pap; |
911 |
|
final int lo; |
912 |
|
final int hi; |
1134 |
|
} |
1135 |
|
} |
1136 |
|
|
1137 |
< |
static abstract class FJSelectAllDriver extends RecursiveAction { |
1137 |
> |
abstract static class FJSelectAllDriver extends RecursiveAction { |
1138 |
|
final int[] indices; |
1139 |
|
final AbstractParallelAnyArray pap; |
1140 |
|
final int initialOffset; |
1491 |
|
if ((filtered && !pap.isSelected(k)) || |
1492 |
|
(x = src[k]) == null) |
1493 |
|
continue; |
1494 |
< |
int hc = byIdentity? System.identityHashCode(x): x.hashCode(); |
1494 |
> |
int hc = byIdentity ? System.identityHashCode(x) : x.hashCode(); |
1495 |
|
int hash = hash(hc); |
1496 |
|
long entry = (((long)hash) << 32) + (k + 1); |
1497 |
|
int idx = hash & mask; |
1574 |
|
} |
1575 |
|
|
1576 |
|
/** |
1577 |
< |
* Return new array holding all elements. |
1577 |
> |
* Returns new array holding all elements. |
1578 |
|
*/ |
1579 |
|
Object[] uniqueObjects(int size) { |
1580 |
|
Object[] src = pap.ogetArray(); |
1657 |
|
this.gran = gran; |
1658 |
|
} |
1659 |
|
|
1660 |
< |
public void compute() { |
1660 |
> |
public void compute() { |
1661 |
|
int l = origin; |
1662 |
|
int g = gran; |
1663 |
|
if (n > g) { |
1681 |
|
l+h, n-h, l, g, null).compute(); |
1682 |
|
} |
1683 |
|
else |
1684 |
< |
oquickSort(a, cmp, l, l+n-1); |
1684 |
> |
Arrays.sort(a, l, l+n, cmp); |
1685 |
|
} |
1686 |
|
} |
1687 |
|
|
1693 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1694 |
|
this.gran = gran; |
1695 |
|
} |
1696 |
< |
public void compute() { |
1696 |
> |
public void compute() { |
1697 |
|
int l = origin; |
1698 |
|
int g = gran; |
1699 |
|
if (n > g) { |
1717 |
|
l+h, n-h, l, g, null).compute(); |
1718 |
|
} |
1719 |
|
else |
1720 |
< |
ocquickSort(a, l, l+n-1); |
1720 |
> |
Arrays.sort(a, l, l+n); |
1721 |
|
} |
1722 |
|
} |
1723 |
|
|
1730 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1731 |
|
this.gran = gran; |
1732 |
|
} |
1733 |
< |
public void compute() { |
1733 |
> |
public void compute() { |
1734 |
|
int l = origin; |
1735 |
|
int g = gran; |
1736 |
|
if (n > g) { |
1766 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1767 |
|
this.gran = gran; |
1768 |
|
} |
1769 |
< |
public void compute() { |
1769 |
> |
public void compute() { |
1770 |
|
int l = origin; |
1771 |
|
int g = gran; |
1772 |
|
if (n > g) { |
1790 |
|
l+h, n-h, l, g, null).compute(); |
1791 |
|
} |
1792 |
|
else |
1793 |
< |
dcquickSort(a, l, l+n-1); |
1793 |
> |
Arrays.sort(a, l, l+n); |
1794 |
|
} |
1795 |
|
} |
1796 |
|
|
1804 |
|
this.gran = gran; |
1805 |
|
} |
1806 |
|
|
1807 |
< |
public void compute() { |
1807 |
> |
public void compute() { |
1808 |
|
int l = origin; |
1809 |
|
int g = gran; |
1810 |
|
if (n > g) { |
1840 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1841 |
|
this.gran = gran; |
1842 |
|
} |
1843 |
< |
public void compute() { |
1843 |
> |
public void compute() { |
1844 |
|
int l = origin; |
1845 |
|
int g = gran; |
1846 |
|
if (n > g) { |
1865 |
|
l+h, n-h, l, g, null).compute(); |
1866 |
|
} |
1867 |
|
else |
1868 |
< |
lcquickSort(a, l, l+n-1); |
1868 |
> |
Arrays.sort(a, l, l+n); |
1869 |
|
} |
1870 |
|
} |
1871 |
|
|
1887 |
|
} |
1888 |
|
|
1889 |
|
/** |
1890 |
< |
* Perform merging for FJSorter. If big enough, splits Left |
1890 |
> |
* Performs merging for FJSorter. If big enough, splits Left |
1891 |
|
* partition in half; finds the greatest point in Right partition |
1892 |
|
* less than the beginning of the second half of Left via binary |
1893 |
|
* search; and then, in parallel, merges left half of Left with |
2305 |
|
/** Cutoff for when to use insertion-sort instead of quicksort */ |
2306 |
|
static final int INSERTION_SORT_THRESHOLD = 8; |
2307 |
|
|
2308 |
< |
// Six nearly identical versions of quicksort |
2309 |
< |
|
2310 |
< |
static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) { |
2311 |
< |
for (;;) { |
2312 |
< |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2313 |
< |
for (int i = lo + 1; i <= hi; i++) { |
2314 |
< |
Object t = a[i]; |
2315 |
< |
int j = i - 1; |
2316 |
< |
while (j >= lo && cmp.compare(t, a[j]) < 0) { |
2317 |
< |
a[j+1] = a[j]; |
2318 |
< |
--j; |
2319 |
< |
} |
2320 |
< |
a[j+1] = t; |
2321 |
< |
} |
2322 |
< |
return; |
2323 |
< |
} |
2324 |
< |
|
2325 |
< |
int mid = (lo + hi) >>> 1; |
2326 |
< |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2327 |
< |
Object t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2328 |
< |
} |
2329 |
< |
if (cmp.compare(a[mid], a[hi]) > 0) { |
2330 |
< |
Object t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2331 |
< |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2332 |
< |
Object u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2333 |
< |
} |
2334 |
< |
} |
2335 |
< |
|
2336 |
< |
Object pivot = a[mid]; |
2337 |
< |
int left = lo+1; |
2338 |
< |
int right = hi-1; |
2339 |
< |
for (;;) { |
2340 |
< |
while (cmp.compare(pivot, a[right]) < 0) |
2341 |
< |
--right; |
2342 |
< |
while (left < right && cmp.compare(pivot, a[left]) >= 0) |
2343 |
< |
++left; |
2344 |
< |
if (left < right) { |
2345 |
< |
Object t = a[left]; a[left] = a[right]; a[right] = t; |
2346 |
< |
--right; |
2347 |
< |
} |
2348 |
< |
else break; |
2349 |
< |
} |
2350 |
< |
|
2351 |
< |
if (left - lo <= hi - right) { |
2352 |
< |
oquickSort(a, cmp, lo, left); |
2353 |
< |
lo = left + 1; |
2354 |
< |
} |
2355 |
< |
else { |
2356 |
< |
oquickSort(a, cmp, right, hi); |
2357 |
< |
hi = left; |
2358 |
< |
} |
2359 |
< |
} |
2360 |
< |
} |
2361 |
< |
|
2362 |
< |
static void ocquickSort(Comparable[] a, int lo, int hi) { |
2363 |
< |
for (;;) { |
2364 |
< |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2365 |
< |
for (int i = lo + 1; i <= hi; i++) { |
2366 |
< |
Comparable t = a[i]; |
2367 |
< |
int j = i - 1; |
2368 |
< |
while (j >= lo && t.compareTo(a[j]) < 0) { |
2369 |
< |
a[j+1] = a[j]; |
2370 |
< |
--j; |
2371 |
< |
} |
2372 |
< |
a[j+1] = t; |
2373 |
< |
} |
2374 |
< |
return; |
2375 |
< |
} |
2376 |
< |
|
2377 |
< |
int mid = (lo + hi) >>> 1; |
2378 |
< |
if (a[lo].compareTo(a[mid]) > 0) { |
2379 |
< |
Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2380 |
< |
} |
2381 |
< |
if (a[mid].compareTo(a[hi]) > 0) { |
2382 |
< |
Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2383 |
< |
if (a[lo].compareTo(a[mid]) > 0) { |
2384 |
< |
Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2385 |
< |
} |
2386 |
< |
} |
2387 |
< |
|
2388 |
< |
Comparable pivot = a[mid]; |
2389 |
< |
int left = lo+1; |
2390 |
< |
int right = hi-1; |
2391 |
< |
for (;;) { |
2392 |
< |
while (pivot.compareTo(a[right]) < 0) |
2393 |
< |
--right; |
2394 |
< |
while (left < right && pivot.compareTo(a[left]) >= 0) |
2395 |
< |
++left; |
2396 |
< |
if (left < right) { |
2397 |
< |
Comparable t = a[left]; a[left] = a[right]; a[right] = t; |
2398 |
< |
--right; |
2399 |
< |
} |
2400 |
< |
else break; |
2401 |
< |
} |
2308 |
> |
// versions of quicksort with comparators |
2309 |
|
|
2403 |
– |
if (left - lo <= hi - right) { |
2404 |
– |
ocquickSort(a, lo, left); |
2405 |
– |
lo = left + 1; |
2406 |
– |
} |
2407 |
– |
else { |
2408 |
– |
ocquickSort(a, right, hi); |
2409 |
– |
hi = left; |
2410 |
– |
} |
2411 |
– |
} |
2412 |
– |
} |
2310 |
|
|
2311 |
|
static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { |
2312 |
|
for (;;) { |
2337 |
|
double pivot = a[mid]; |
2338 |
|
int left = lo+1; |
2339 |
|
int right = hi-1; |
2340 |
+ |
boolean sameLefts = true; |
2341 |
|
for (;;) { |
2342 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2343 |
|
--right; |
2344 |
< |
while (left < right && cmp.compare(pivot, a[left]) >= 0) |
2344 |
> |
int c; |
2345 |
> |
while (left < right && |
2346 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2347 |
> |
if (c != 0) |
2348 |
> |
sameLefts = false; |
2349 |
|
++left; |
2350 |
+ |
} |
2351 |
|
if (left < right) { |
2352 |
|
double t = a[left]; a[left] = a[right]; a[right] = t; |
2353 |
|
--right; |
2355 |
|
else break; |
2356 |
|
} |
2357 |
|
|
2358 |
+ |
if (sameLefts && right == hi - 1) |
2359 |
+ |
return; |
2360 |
|
if (left - lo <= hi - right) { |
2361 |
|
dquickSort(a, cmp, lo, left); |
2362 |
|
lo = left + 1; |
2368 |
|
} |
2369 |
|
} |
2370 |
|
|
2466 |
– |
static void dcquickSort(double[] a, int lo, int hi) { |
2467 |
– |
for (;;) { |
2468 |
– |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2469 |
– |
for (int i = lo + 1; i <= hi; i++) { |
2470 |
– |
double t = a[i]; |
2471 |
– |
int j = i - 1; |
2472 |
– |
while (j >= lo && t < a[j]) { |
2473 |
– |
a[j+1] = a[j]; |
2474 |
– |
--j; |
2475 |
– |
} |
2476 |
– |
a[j+1] = t; |
2477 |
– |
} |
2478 |
– |
return; |
2479 |
– |
} |
2480 |
– |
|
2481 |
– |
int mid = (lo + hi) >>> 1; |
2482 |
– |
if (a[lo] > a[mid]) { |
2483 |
– |
double t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2484 |
– |
} |
2485 |
– |
if (a[mid] > a[hi]) { |
2486 |
– |
double t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2487 |
– |
if (a[lo] > a[mid]) { |
2488 |
– |
double u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2489 |
– |
} |
2490 |
– |
} |
2491 |
– |
|
2492 |
– |
double pivot = a[mid]; |
2493 |
– |
int left = lo+1; |
2494 |
– |
int right = hi-1; |
2495 |
– |
for (;;) { |
2496 |
– |
while (pivot < a[right]) |
2497 |
– |
--right; |
2498 |
– |
while (left < right && pivot >= a[left]) |
2499 |
– |
++left; |
2500 |
– |
if (left < right) { |
2501 |
– |
double t = a[left]; a[left] = a[right]; a[right] = t; |
2502 |
– |
--right; |
2503 |
– |
} |
2504 |
– |
else break; |
2505 |
– |
} |
2506 |
– |
|
2507 |
– |
if (left - lo <= hi - right) { |
2508 |
– |
dcquickSort(a, lo, left); |
2509 |
– |
lo = left + 1; |
2510 |
– |
} |
2511 |
– |
else { |
2512 |
– |
dcquickSort(a, right, hi); |
2513 |
– |
hi = left; |
2514 |
– |
} |
2515 |
– |
} |
2516 |
– |
} |
2517 |
– |
|
2371 |
|
static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) { |
2372 |
|
for (;;) { |
2373 |
|
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2397 |
|
long pivot = a[mid]; |
2398 |
|
int left = lo+1; |
2399 |
|
int right = hi-1; |
2400 |
+ |
boolean sameLefts = true; |
2401 |
|
for (;;) { |
2402 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2403 |
|
--right; |
2404 |
< |
while (left < right && cmp.compare(pivot, a[left]) >= 0) |
2404 |
> |
int c; |
2405 |
> |
while (left < right && |
2406 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2407 |
> |
if (c != 0) |
2408 |
> |
sameLefts = false; |
2409 |
|
++left; |
2410 |
+ |
} |
2411 |
|
if (left < right) { |
2412 |
|
long t = a[left]; a[left] = a[right]; a[right] = t; |
2413 |
|
--right; |
2415 |
|
else break; |
2416 |
|
} |
2417 |
|
|
2418 |
+ |
if (sameLefts && right == hi - 1) |
2419 |
+ |
return; |
2420 |
|
if (left - lo <= hi - right) { |
2421 |
|
lquickSort(a, cmp, lo, left); |
2422 |
|
lo = left + 1; |
2428 |
|
} |
2429 |
|
} |
2430 |
|
|
2570 |
– |
static void lcquickSort(long[] a, int lo, int hi) { |
2571 |
– |
for (;;) { |
2572 |
– |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2573 |
– |
for (int i = lo + 1; i <= hi; i++) { |
2574 |
– |
long t = a[i]; |
2575 |
– |
int j = i - 1; |
2576 |
– |
while (j >= lo && t < a[j]) { |
2577 |
– |
a[j+1] = a[j]; |
2578 |
– |
--j; |
2579 |
– |
} |
2580 |
– |
a[j+1] = t; |
2581 |
– |
} |
2582 |
– |
return; |
2583 |
– |
} |
2584 |
– |
|
2585 |
– |
int mid = (lo + hi) >>> 1; |
2586 |
– |
if (a[lo] > a[mid]) { |
2587 |
– |
long t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2588 |
– |
} |
2589 |
– |
if (a[mid] > a[hi]) { |
2590 |
– |
long t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2591 |
– |
if (a[lo] > a[mid]) { |
2592 |
– |
long u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2593 |
– |
} |
2594 |
– |
} |
2595 |
– |
|
2596 |
– |
long pivot = a[mid]; |
2597 |
– |
int left = lo+1; |
2598 |
– |
int right = hi-1; |
2599 |
– |
for (;;) { |
2600 |
– |
while (pivot < a[right]) |
2601 |
– |
--right; |
2602 |
– |
while (left < right && pivot >= a[left]) |
2603 |
– |
++left; |
2604 |
– |
if (left < right) { |
2605 |
– |
long t = a[left]; a[left] = a[right]; a[right] = t; |
2606 |
– |
--right; |
2607 |
– |
} |
2608 |
– |
else break; |
2609 |
– |
} |
2610 |
– |
|
2611 |
– |
if (left - lo <= hi - right) { |
2612 |
– |
lcquickSort(a, lo, left); |
2613 |
– |
lo = left + 1; |
2614 |
– |
} |
2615 |
– |
else { |
2616 |
– |
lcquickSort(a, right, hi); |
2617 |
– |
hi = left; |
2618 |
– |
} |
2619 |
– |
} |
2620 |
– |
} |
2621 |
– |
|
2431 |
|
/** |
2432 |
|
* Cumulative scan |
2433 |
|
* |
2461 |
|
* |
2462 |
|
* This class maintains only the basic control logic. Subclasses |
2463 |
|
* maintain the "in" and "out" fields, and *Ops classes perform |
2464 |
< |
* computations |
2464 |
> |
* computations. |
2465 |
|
*/ |
2466 |
< |
static abstract class FJScan extends ForkJoinTask<Void> { |
2466 |
> |
abstract static class FJScan extends ForkJoinTask<Void> { |
2467 |
|
static final short CUMULATE = (short)1; |
2468 |
|
static final short SUMMED = (short)2; |
2469 |
|
static final short FINISHED = (short)4; |
2555 |
|
op.pushUp(par, par.left, par.right); |
2556 |
|
int refork = |
2557 |
|
((pb & CUMULATE) == 0 && |
2558 |
< |
par.lo == op.origin)? CUMULATE : 0; |
2558 |
> |
par.lo == op.origin) ? CUMULATE : 0; |
2559 |
|
int nextPhase = pb|cb|refork; |
2560 |
|
if (pb == nextPhase || |
2561 |
|
phaseUpdater.compareAndSet(par, pb, nextPhase)) { |
2630 |
|
} |
2631 |
|
|
2632 |
|
/** |
2633 |
< |
* Computational operations for FJSCan |
2633 |
> |
* Computational operations for FJScan |
2634 |
|
*/ |
2635 |
< |
static abstract class FJScanOp { |
2635 |
> |
abstract static class FJScanOp { |
2636 |
|
final int threshold; |
2637 |
|
final int origin; |
2638 |
|
final int fence; |
2649 |
|
abstract FJScan newSubtask(FJScan parent, int lo, int hi); |
2650 |
|
} |
2651 |
|
|
2652 |
< |
static abstract class FJOScanOp extends FJScanOp { |
2652 |
> |
abstract static class FJOScanOp extends FJScanOp { |
2653 |
|
final Object[] array; |
2654 |
|
final Reducer reducer; |
2655 |
|
final Object base; |
2739 |
|
} |
2740 |
|
} |
2741 |
|
|
2742 |
< |
static abstract class FJDScanOp extends FJScanOp { |
2742 |
> |
abstract static class FJDScanOp extends FJScanOp { |
2743 |
|
final double[] array; |
2744 |
|
final DoubleReducer reducer; |
2745 |
|
final double base; |
2829 |
|
} |
2830 |
|
} |
2831 |
|
|
2832 |
< |
static abstract class FJLScanOp extends FJScanOp { |
2832 |
> |
abstract static class FJLScanOp extends FJScanOp { |
2833 |
|
final long[] array; |
2834 |
|
final LongReducer reducer; |
2835 |
|
final long base; |
2921 |
|
|
2922 |
|
// specialized versions for plus |
2923 |
|
|
2924 |
< |
static abstract class FJDScanPlusOp extends FJScanOp { |
2924 |
> |
abstract static class FJDScanPlusOp extends FJScanOp { |
2925 |
|
final double[] array; |
2926 |
|
FJDScanPlusOp(AbstractParallelAnyArray.DPap pap) { |
2927 |
|
super(pap); |
3003 |
|
} |
3004 |
|
} |
3005 |
|
|
3006 |
< |
static abstract class FJLScanPlusOp extends FJScanOp { |
3006 |
> |
abstract static class FJLScanPlusOp extends FJScanOp { |
3007 |
|
final long[] array; |
3008 |
|
FJLScanPlusOp(AbstractParallelAnyArray.LPap pap) { |
3009 |
|
super(pap); |