ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/extra166y/PAS.java

Comparing jsr166/src/extra166y/PAS.java (file contents):
Revision 1.2 by dl, Mon Jan 12 17:16:36 2009 UTC vs.
Revision 1.19 by jsr166, Sun Jan 18 20:17:32 2015 UTC

#	Line 1 | Line 1
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;
8	+
9		import jsr166y.*;
10		import static extra166y.Ops.*;
11		import java.util.*;
#	Line 26 | Line 27 | class PAS {
27		static ForkJoinPool defaultExecutor() {
28		ForkJoinPool p = defaultExecutor; // double-check
29		if (p == null) {
30	<	synchronized(poolLock) {
30	>	synchronized (poolLock) {
31		p = defaultExecutor;
32		if (p == null) {
33		// use ceil(7/8 * ncpus)
#	Line 56 | Line 57 | class PAS {
57		* subclass, prefixed FJO (object reference), FJD (double) and FJL
58		* (long).
59		*/
60	<	static abstract class FJBase extends RecursiveAction {
60	>	abstract static class FJBase extends RecursiveAction {
61		final AbstractParallelAnyArray pap;
62		final int lo;
63		final int hi;
#	Line 676 | Line 677 | class PAS {
677		}
678		}
679
680	<	void  atLeaf(int l, int h) {
680	>	void atLeaf(int l, int h) {
681		if (pap.hasFilter())
682		filteredAtLeaf(l, h);
683		else {
#	Line 689 | Line 690 | class PAS {
690		}
691		}
692
693	<	void  filteredAtLeaf(int l, int h) {
693	>	void filteredAtLeaf(int l, int h) {
694		for (int i = l; i < h; ++i) {
695		if (pap.isSelected(i)) {
696		Object x = pap.oget(i);
#	Line 772 | Line 773 | class PAS {
773		}
774		}
775
776	<	void  filteredAtLeaf(int l, int h) {
776	>	void filteredAtLeaf(int l, int h) {
777		for (int i = l; i < h; ++i) {
778		if (pap.isSelected(i)) {
779		double x = pap.dget(i);
#	Line 843 | Line 844 | class PAS {
844		}
845		}
846
847	<	void  atLeaf(int l, int h) {
847	>	void atLeaf(int l, int h) {
848		if (pap.hasFilter())
849		filteredAtLeaf(l, h);
850		else {
#	Line 857 | Line 858 | class PAS {
858		}
859		}
860
861	<	void  filteredAtLeaf(int l, int h) {
861	>	void filteredAtLeaf(int l, int h) {
862		for (int i = l; i < h; ++i) {
863		if (pap.isSelected(i)) {
864		long x = pap.lget(i);
#	Line 906 | Line 907 | class PAS {
907		* Base for cancellable search tasks. Same idea as FJBase
908		* but cancels tasks when result nonnegative.
909		*/
910	<	static abstract class FJSearchBase extends RecursiveAction {
910	>	abstract static class FJSearchBase extends RecursiveAction {
911		final AbstractParallelAnyArray pap;
912		final int lo;
913		final int hi;
#	Line 1134 | Line 1135 | class PAS {
1135		}
1136		}
1137
1138	<	static abstract class FJSelectAllDriver extends RecursiveAction {
1138	>	abstract static class FJSelectAllDriver extends RecursiveAction {
1139		final int[] indices;
1140		final AbstractParallelAnyArray pap;
1141		final int initialOffset;
#	Line 1491 | Line 1492 | class PAS {
1492		if ((filtered && !pap.isSelected(k)) ||
1493		(x = src[k]) == null)
1494		continue;
1495	<	int hc = byIdentity? System.identityHashCode(x): x.hashCode();
1495	>	int hc = byIdentity ? System.identityHashCode(x) : x.hashCode();
1496		int hash = hash(hc);
1497		long entry = (((long)hash) << 32) + (k + 1);
1498		int idx = hash & mask;
#	Line 1524 | Line 1525 | class PAS {
1525		continue;
1526		double x = src[k];
1527		long bits = Double.doubleToLongBits(x);
1528	<	int hash = hash((int)(bits ^ (bits >>> 32)));;
1528	>	int hash = hash((int)(bits ^ (bits >>> 32)));
1529		long entry = (((long)hash) << 32) + (k + 1);
1530		int idx = hash & mask;
1531		for (;;) {
#	Line 1574 | Line 1575 | class PAS {
1575		}
1576
1577		/**
1578	<	* Return new array holding all elements.
1578	>	* Returns new array holding all elements.
1579		*/
1580		Object[] uniqueObjects(int size) {
1581		Object[] src = pap.ogetArray();
#	Line 1657 | Line 1658 | class PAS {
1658		this.gran = gran;
1659		}
1660
1661	<	public void compute()  {
1661	>	public void compute() {
1662		int l = origin;
1663		int g = gran;
1664		if (n > g) {
#	Line 1681 | Line 1682 | class PAS {
1682		l+h, n-h, l, g, null).compute();
1683		}
1684		else
1685	<	oquickSort(a, cmp, l, l+n-1);
1685	>	Arrays.sort(a, l, l+n, cmp);
1686		}
1687		}
1688
#	Line 1693 | Line 1694 | class PAS {
1694		this.a = a; this.w = w; this.origin = origin; this.n = n;
1695		this.gran = gran;
1696		}
1697	<	public void compute()  {
1697	>	public void compute() {
1698		int l = origin;
1699		int g = gran;
1700		if (n > g) {
#	Line 1717 | Line 1718 | class PAS {
1718		l+h, n-h, l, g, null).compute();
1719		}
1720		else
1721	<	ocquickSort(a, l, l+n-1);
1721	>	Arrays.sort(a, l, l+n);
1722		}
1723		}
1724
#	Line 1730 | Line 1731 | class PAS {
1731		this.a = a; this.w = w; this.origin = origin; this.n = n;
1732		this.gran = gran;
1733		}
1734	<	public void compute()  {
1734	>	public void compute() {
1735		int l = origin;
1736		int g = gran;
1737		if (n > g) {
#	Line 1766 | Line 1767 | class PAS {
1767		this.a = a; this.w = w; this.origin = origin; this.n = n;
1768		this.gran = gran;
1769		}
1770	<	public void compute()  {
1770	>	public void compute() {
1771		int l = origin;
1772		int g = gran;
1773		if (n > g) {
#	Line 1790 | Line 1791 | class PAS {
1791		l+h, n-h, l, g, null).compute();
1792		}
1793		else
1794	<	dcquickSort(a, l, l+n-1);
1794	>	Arrays.sort(a, l, l+n);
1795		}
1796		}
1797
#	Line 1804 | Line 1805 | class PAS {
1805		this.gran = gran;
1806		}
1807
1808	<	public void compute()  {
1808	>	public void compute() {
1809		int l = origin;
1810		int g = gran;
1811		if (n > g) {
#	Line 1840 | Line 1841 | class PAS {
1841		this.a = a; this.w = w; this.origin = origin; this.n = n;
1842		this.gran = gran;
1843		}
1844	<	public void compute()  {
1844	>	public void compute() {
1845		int l = origin;
1846		int g = gran;
1847		if (n > g) {
#	Line 1865 | Line 1866 | class PAS {
1866		l+h, n-h, l, g, null).compute();
1867		}
1868		else
1869	<	lcquickSort(a, l, l+n-1);
1869	>	Arrays.sort(a, l, l+n);
1870		}
1871		}
1872
#	Line 1875 | Line 1876 | class PAS {
1876		final RecursiveAction right;
1877		final RecursiveAction merger;
1878		FJSubSorter(RecursiveAction left, RecursiveAction right,
1879	<	RecursiveAction merger){
1879	>	RecursiveAction merger) {
1880		this.left = left; this.right = right; this.merger = merger;
1881		}
1882		public void compute() {
#	Line 1887 | Line 1888 | class PAS {
1888		}
1889
1890		/**
1891	<	* Perform merging for FJSorter. If big enough, splits Left
1891	>	* Performs merging for FJSorter. If big enough, splits Left
1892		* partition in half; finds the greatest point in Right partition
1893		* less than the beginning of the second half of Left via binary
1894		* search; and then, in parallel, merges left half of Left with
#	Line 2305 | Line 2306 | class PAS {
2306		/** Cutoff for when to use insertion-sort instead of quicksort */
2307		static final int INSERTION_SORT_THRESHOLD = 8;
2308
2309	<	// Six nearly identical versions of quicksort
2309	>	// versions of quicksort with comparators
2310
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	–	}
2402	–
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	–	}
2311
2312		static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2313		for (;;) {
#	Line 2440 | Line 2338 | class PAS {
2338		double pivot = a[mid];
2339		int left = lo+1;
2340		int right = hi-1;
2341	+	boolean sameLefts = true;
2342		for (;;) {
2343		while (cmp.compare(pivot, a[right]) < 0)
2344		--right;
2345	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2345	>	int c;
2346	>	while (left < right &&
2347	>	(c = cmp.compare(pivot, a[left])) >= 0) {
2348	>	if (c != 0)
2349	>	sameLefts = false;
2350		++left;
2448	–	if (left < right) {
2449	–	double t = a[left]; a[left] = a[right]; a[right] = t;
2450	–	--right;
2351		}
2452	–	else break;
2453	–	}
2454	–
2455	–	if (left - lo <= hi - right) {
2456	–	dquickSort(a, cmp, lo, left);
2457	–	lo = left + 1;
2458	–	}
2459	–	else {
2460	–	dquickSort(a, cmp, right, hi);
2461	–	hi = left;
2462	–	}
2463	–	}
2464	–	}
2465	–
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;
2352		if (left < right) {
2353		double t = a[left]; a[left] = a[right]; a[right] = t;
2354		--right;
#	Line 2504 | Line 2356 | class PAS {
2356		else break;
2357		}
2358
2359	+	if (sameLefts && right == hi - 1)
2360	+	return;
2361		if (left - lo <= hi - right) {
2362	<	dcquickSort(a, lo, left);
2362	>	dquickSort(a, cmp, lo, left);
2363		lo = left + 1;
2364		}
2365		else {
2366	<	dcquickSort(a, right, hi);
2366	>	dquickSort(a, cmp, right, hi);
2367		hi = left;
2368		}
2369		}
#	Line 2544 | Line 2398 | class PAS {
2398		long pivot = a[mid];
2399		int left = lo+1;
2400		int right = hi-1;
2401	+	boolean sameLefts = true;
2402		for (;;) {
2403		while (cmp.compare(pivot, a[right]) < 0)
2404		--right;
2405	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2405	>	int c;
2406	>	while (left < right &&
2407	>	(c = cmp.compare(pivot, a[left])) >= 0) {
2408	>	if (c != 0)
2409	>	sameLefts = false;
2410		++left;
2552	–	if (left < right) {
2553	–	long t = a[left]; a[left] = a[right]; a[right] = t;
2554	–	--right;
2555	–	}
2556	–	else break;
2557	–	}
2558	–
2559	–	if (left - lo <= hi - right) {
2560	–	lquickSort(a, cmp, lo, left);
2561	–	lo = left + 1;
2562	–	}
2563	–	else {
2564	–	lquickSort(a, cmp, right, hi);
2565	–	hi = left;
2566	–	}
2567	–	}
2568	–	}
2569	–
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;
2411		}
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;
2412		if (left < right) {
2413		long t = a[left]; a[left] = a[right]; a[right] = t;
2414		--right;
#	Line 2608 | Line 2416 | class PAS {
2416		else break;
2417		}
2418
2419	+	if (sameLefts && right == hi - 1)
2420	+	return;
2421		if (left - lo <= hi - right) {
2422	<	lcquickSort(a, lo, left);
2422	>	lquickSort(a, cmp, lo, left);
2423		lo = left + 1;
2424		}
2425		else {
2426	<	lcquickSort(a, right, hi);
2426	>	lquickSort(a, cmp, right, hi);
2427		hi = left;
2428		}
2429		}
#	Line 2652 | Line 2462 | class PAS {
2462		*
2463		* This class maintains only the basic control logic.  Subclasses
2464		* maintain the "in" and "out" fields, and *Ops classes perform
2465	<	* computations
2465	>	* computations.
2466		*/
2467	<	static abstract class FJScan extends ForkJoinTask<Void> {
2467	>	abstract static class FJScan extends ForkJoinTask<Void> {
2468		static final short CUMULATE = (short)1;
2469		static final short SUMMED   = (short)2;
2470		static final short FINISHED = (short)4;
#	Line 2709 | Line 2519 | class PAS {
2519		int cb;
2520		for (;;) { // Establish action: sum, cumulate, or both
2521		int b = phase;
2522	<	if ((b & FINISHED) != 0) // already done
2522	>	if ((b & FINISHED) != 0) // already done
2523		return false;
2524		if ((b & CUMULATE) != 0)
2525		cb = FINISHED;
#	Line 2746 | Line 2556 | class PAS {
2556		op.pushUp(par, par.left, par.right);
2557		int refork =
2558		((pb & CUMULATE) == 0 &&
2559	<	par.lo == op.origin)? CUMULATE : 0;
2559	>	par.lo == op.origin) ? CUMULATE : 0;
2560		int nextPhase = pb|cb|refork;
2561		if (pb == nextPhase ||
2562		phaseUpdater.compareAndSet(par, pb, nextPhase)) {
#	Line 2821 | Line 2631 | class PAS {
2631		}
2632
2633		/**
2634	<	* Computational operations for FJSCan
2634	>	* Computational operations for FJScan
2635		*/
2636	<	static abstract class FJScanOp {
2636	>	abstract static class FJScanOp {
2637		final int threshold;
2638		final int origin;
2639		final int fence;
#	Line 2840 | Line 2650 | class PAS {
2650		abstract FJScan newSubtask(FJScan parent, int lo, int hi);
2651		}
2652
2653	<	static abstract class FJOScanOp extends FJScanOp {
2653	>	abstract static class FJOScanOp extends FJScanOp {
2654		final Object[] array;
2655		final Reducer reducer;
2656		final Object base;
#	Line 2930 | Line 2740 | class PAS {
2740		}
2741		}
2742
2743	<	static abstract class FJDScanOp extends FJScanOp {
2743	>	abstract static class FJDScanOp extends FJScanOp {
2744		final double[] array;
2745		final DoubleReducer reducer;
2746		final double base;
#	Line 3020 | Line 2830 | class PAS {
2830		}
2831		}
2832
2833	<	static abstract class FJLScanOp extends FJScanOp {
2833	>	abstract static class FJLScanOp extends FJScanOp {
2834		final long[] array;
2835		final LongReducer reducer;
2836		final long base;
#	Line 3112 | Line 2922 | class PAS {
2922
2923		// specialized versions for plus
2924
2925	<	static abstract class FJDScanPlusOp extends FJScanOp {
2925	>	abstract static class FJDScanPlusOp extends FJScanOp {
2926		final double[] array;
2927		FJDScanPlusOp(AbstractParallelAnyArray.DPap pap) {
2928		super(pap);
#	Line 3194 | Line 3004 | class PAS {
3004		}
3005		}
3006
3007	<	static abstract class FJLScanPlusOp extends FJScanOp {
3007	>	abstract static class FJLScanPlusOp extends FJScanOp {
3008		final long[] array;
3009		FJLScanPlusOp(AbstractParallelAnyArray.LPap pap) {
3010		super(pap);

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines