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) |
1524 |
|
continue; |
1525 |
|
double x = src[k]; |
1526 |
|
long bits = Double.doubleToLongBits(x); |
1527 |
< |
int hash = hash((int)(bits ^ (bits >>> 32)));; |
1527 |
> |
int hash = hash((int)(bits ^ (bits >>> 32))); |
1528 |
|
long entry = (((long)hash) << 32) + (k + 1); |
1529 |
|
int idx = hash & mask; |
1530 |
|
for (;;) { |
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) { |
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) { |
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 |
|
|
1875 |
|
final RecursiveAction right; |
1876 |
|
final RecursiveAction merger; |
1877 |
|
FJSubSorter(RecursiveAction left, RecursiveAction right, |
1878 |
< |
RecursiveAction merger){ |
1878 |
> |
RecursiveAction merger) { |
1879 |
|
this.left = left; this.right = right; this.merger = merger; |
1880 |
|
} |
1881 |
|
public void compute() { |
1882 |
< |
invokeAll(left, right); |
1882 |
> |
right.fork(); |
1883 |
> |
left.invoke(); |
1884 |
> |
right.join(); |
1885 |
|
merger.invoke(); |
1886 |
|
} |
1887 |
|
} |
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 |
2308 |
> |
// versions of quicksort with comparators |
2309 |
|
|
2310 |
|
static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) { |
2311 |
|
for (;;) { |
2336 |
|
Object pivot = a[mid]; |
2337 |
|
int left = lo+1; |
2338 |
|
int right = hi-1; |
2339 |
+ |
boolean sameLefts = true; |
2340 |
|
for (;;) { |
2341 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2342 |
|
--right; |
2343 |
< |
while (left < right && cmp.compare(pivot, a[left]) >= 0) |
2343 |
> |
int c; |
2344 |
> |
while (left < right && |
2345 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2346 |
> |
if (c != 0) |
2347 |
> |
sameLefts = false; |
2348 |
|
++left; |
2349 |
+ |
} |
2350 |
|
if (left < right) { |
2351 |
|
Object t = a[left]; a[left] = a[right]; a[right] = t; |
2352 |
|
--right; |
2354 |
|
else break; |
2355 |
|
} |
2356 |
|
|
2357 |
< |
oquickSort(a, cmp, lo, left); |
2358 |
< |
lo = left + 1; |
2357 |
> |
if (sameLefts && right == hi - 1) |
2358 |
> |
return; |
2359 |
> |
if (left - lo <= hi - right) { |
2360 |
> |
oquickSort(a, cmp, lo, left); |
2361 |
> |
lo = left + 1; |
2362 |
> |
} |
2363 |
> |
else { |
2364 |
> |
oquickSort(a, cmp, right, hi); |
2365 |
> |
hi = left; |
2366 |
> |
} |
2367 |
|
} |
2368 |
|
} |
2369 |
|
|
2392 |
|
Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2393 |
|
} |
2394 |
|
} |
2379 |
– |
|
2395 |
|
Comparable pivot = a[mid]; |
2396 |
|
int left = lo+1; |
2397 |
|
int right = hi-1; |
2398 |
+ |
boolean sameLefts = true; |
2399 |
|
for (;;) { |
2400 |
|
while (pivot.compareTo(a[right]) < 0) |
2401 |
|
--right; |
2402 |
< |
while (left < right && pivot.compareTo(a[left]) >= 0) |
2402 |
> |
int c; |
2403 |
> |
while (left < right && (c = pivot.compareTo(a[left])) >= 0) { |
2404 |
> |
if (c != 0) |
2405 |
> |
sameLefts = false; |
2406 |
|
++left; |
2407 |
+ |
} |
2408 |
|
if (left < right) { |
2409 |
|
Comparable t = a[left]; a[left] = a[right]; a[right] = t; |
2410 |
|
--right; |
2412 |
|
else break; |
2413 |
|
} |
2414 |
|
|
2415 |
< |
ocquickSort(a, lo, left); |
2416 |
< |
lo = left + 1; |
2415 |
> |
if (sameLefts && right == hi - 1) |
2416 |
> |
return; |
2417 |
> |
if (left - lo <= hi - right) { |
2418 |
> |
ocquickSort(a, lo, left); |
2419 |
> |
lo = left + 1; |
2420 |
> |
} |
2421 |
> |
else { |
2422 |
> |
ocquickSort(a, right, hi); |
2423 |
> |
hi = left; |
2424 |
> |
} |
2425 |
|
} |
2426 |
|
} |
2427 |
|
|
2428 |
+ |
|
2429 |
|
static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { |
2430 |
|
for (;;) { |
2431 |
|
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2455 |
|
double pivot = a[mid]; |
2456 |
|
int left = lo+1; |
2457 |
|
int right = hi-1; |
2458 |
+ |
boolean sameLefts = true; |
2459 |
|
for (;;) { |
2460 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2461 |
|
--right; |
2462 |
< |
while (left < right && cmp.compare(pivot, a[left]) >= 0) |
2462 |
> |
int c; |
2463 |
> |
while (left < right && |
2464 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2465 |
> |
if (c != 0) |
2466 |
> |
sameLefts = false; |
2467 |
|
++left; |
2468 |
+ |
} |
2469 |
|
if (left < right) { |
2470 |
|
double t = a[left]; a[left] = a[right]; a[right] = t; |
2471 |
|
--right; |
2473 |
|
else break; |
2474 |
|
} |
2475 |
|
|
2476 |
< |
dquickSort(a, cmp, lo, left); |
2442 |
< |
lo = left + 1; |
2443 |
< |
} |
2444 |
< |
} |
2445 |
< |
|
2446 |
< |
static void dcquickSort(double[] a, int lo, int hi) { |
2447 |
< |
for (;;) { |
2448 |
< |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2449 |
< |
for (int i = lo + 1; i <= hi; i++) { |
2450 |
< |
double t = a[i]; |
2451 |
< |
int j = i - 1; |
2452 |
< |
while (j >= lo && t < a[j]) { |
2453 |
< |
a[j+1] = a[j]; |
2454 |
< |
--j; |
2455 |
< |
} |
2456 |
< |
a[j+1] = t; |
2457 |
< |
} |
2476 |
> |
if (sameLefts && right == hi - 1) |
2477 |
|
return; |
2478 |
+ |
if (left - lo <= hi - right) { |
2479 |
+ |
dquickSort(a, cmp, lo, left); |
2480 |
+ |
lo = left + 1; |
2481 |
|
} |
2482 |
< |
|
2483 |
< |
int mid = (lo + hi) >>> 1; |
2484 |
< |
if (a[lo] > a[mid]) { |
2463 |
< |
double t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2464 |
< |
} |
2465 |
< |
if (a[mid] > a[hi]) { |
2466 |
< |
double t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2467 |
< |
if (a[lo] > a[mid]) { |
2468 |
< |
double u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2469 |
< |
} |
2470 |
< |
} |
2471 |
< |
|
2472 |
< |
double pivot = a[mid]; |
2473 |
< |
int left = lo+1; |
2474 |
< |
int right = hi-1; |
2475 |
< |
for (;;) { |
2476 |
< |
while (pivot < a[right]) |
2477 |
< |
--right; |
2478 |
< |
while (left < right && pivot >= a[left]) |
2479 |
< |
++left; |
2480 |
< |
if (left < right) { |
2481 |
< |
double t = a[left]; a[left] = a[right]; a[right] = t; |
2482 |
< |
--right; |
2483 |
< |
} |
2484 |
< |
else break; |
2482 |
> |
else { |
2483 |
> |
dquickSort(a, cmp, right, hi); |
2484 |
> |
hi = left; |
2485 |
|
} |
2486 |
– |
|
2487 |
– |
dcquickSort(a, lo, left); |
2488 |
– |
lo = left + 1; |
2486 |
|
} |
2487 |
|
} |
2488 |
|
|
2515 |
|
long pivot = a[mid]; |
2516 |
|
int left = lo+1; |
2517 |
|
int right = hi-1; |
2518 |
+ |
boolean sameLefts = true; |
2519 |
|
for (;;) { |
2520 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2521 |
|
--right; |
2522 |
< |
while (left < right && cmp.compare(pivot, a[left]) >= 0) |
2522 |
> |
int c; |
2523 |
> |
while (left < right && |
2524 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2525 |
> |
if (c != 0) |
2526 |
> |
sameLefts = false; |
2527 |
|
++left; |
2528 |
+ |
} |
2529 |
|
if (left < right) { |
2530 |
|
long t = a[left]; a[left] = a[right]; a[right] = t; |
2531 |
|
--right; |
2533 |
|
else break; |
2534 |
|
} |
2535 |
|
|
2536 |
< |
lquickSort(a, cmp, lo, left); |
2534 |
< |
lo = left + 1; |
2535 |
< |
} |
2536 |
< |
} |
2537 |
< |
|
2538 |
< |
static void lcquickSort(long[] a, int lo, int hi) { |
2539 |
< |
for (;;) { |
2540 |
< |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2541 |
< |
for (int i = lo + 1; i <= hi; i++) { |
2542 |
< |
long t = a[i]; |
2543 |
< |
int j = i - 1; |
2544 |
< |
while (j >= lo && t < a[j]) { |
2545 |
< |
a[j+1] = a[j]; |
2546 |
< |
--j; |
2547 |
< |
} |
2548 |
< |
a[j+1] = t; |
2549 |
< |
} |
2536 |
> |
if (sameLefts && right == hi - 1) |
2537 |
|
return; |
2538 |
+ |
if (left - lo <= hi - right) { |
2539 |
+ |
lquickSort(a, cmp, lo, left); |
2540 |
+ |
lo = left + 1; |
2541 |
|
} |
2542 |
< |
|
2543 |
< |
int mid = (lo + hi) >>> 1; |
2544 |
< |
if (a[lo] > a[mid]) { |
2555 |
< |
long t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2556 |
< |
} |
2557 |
< |
if (a[mid] > a[hi]) { |
2558 |
< |
long t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2559 |
< |
if (a[lo] > a[mid]) { |
2560 |
< |
long u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2561 |
< |
} |
2562 |
< |
} |
2563 |
< |
|
2564 |
< |
long pivot = a[mid]; |
2565 |
< |
int left = lo+1; |
2566 |
< |
int right = hi-1; |
2567 |
< |
for (;;) { |
2568 |
< |
while (pivot < a[right]) |
2569 |
< |
--right; |
2570 |
< |
while (left < right && pivot >= a[left]) |
2571 |
< |
++left; |
2572 |
< |
if (left < right) { |
2573 |
< |
long t = a[left]; a[left] = a[right]; a[right] = t; |
2574 |
< |
--right; |
2575 |
< |
} |
2576 |
< |
else break; |
2542 |
> |
else { |
2543 |
> |
lquickSort(a, cmp, right, hi); |
2544 |
> |
hi = left; |
2545 |
|
} |
2578 |
– |
|
2579 |
– |
lcquickSort(a, lo, left); |
2580 |
– |
lo = left + 1; |
2546 |
|
} |
2547 |
|
} |
2548 |
|
|
2636 |
|
int cb; |
2637 |
|
for (;;) { // Establish action: sum, cumulate, or both |
2638 |
|
int b = phase; |
2639 |
< |
if ((b & FINISHED) != 0) // already done |
2639 |
> |
if ((b & FINISHED) != 0) // already done |
2640 |
|
return false; |
2641 |
|
if ((b & CUMULATE) != 0) |
2642 |
|
cb = FINISHED; |
2748 |
|
} |
2749 |
|
|
2750 |
|
/** |
2751 |
< |
* Computational operations for FJSCan |
2751 |
> |
* Computational operations for FJScan |
2752 |
|
*/ |
2753 |
|
static abstract class FJScanOp { |
2754 |
|
final int threshold; |