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.7 by dl, Tue May 25 13:39:40 2010 UTC vs.
Revision 1.18 by jsr166, Tue Feb 5 17:36:44 2013 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;
#	Line 26 | Line 26 | class PAS {
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)
#	Line 56 | Line 56 | class PAS {
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;
#	Line 676 | Line 676 | class PAS {
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 {
#	Line 689 | Line 689 | class PAS {
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);
#	Line 772 | Line 772 | class PAS {
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);
#	Line 843 | Line 843 | class PAS {
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 {
#	Line 857 | Line 857 | class PAS {
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);
#	Line 906 | Line 906 | class PAS {
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;
#	Line 1134 | Line 1134 | class PAS {
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;
#	Line 1491 | Line 1491 | class PAS {
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;
#	Line 1574 | Line 1574 | class PAS {
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();
#	Line 1657 | Line 1657 | class PAS {
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) {
#	Line 1693 | Line 1693 | class PAS {
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) {
#	Line 1730 | Line 1730 | class PAS {
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) {
#	Line 1754 | Line 1754 | class PAS {
1754		l+h, n-h, l, g, null).compute();
1755		}
1756		else
1757	<	Arrays.sort(a, l, l+n, cmp);
1757	>	dquickSort(a, cmp, l, l+n-1);
1758		}
1759		}
1760
#	Line 1766 | Line 1766 | class PAS {
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) {
#	Line 1804 | Line 1804 | class PAS {
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) {
#	Line 1828 | Line 1828 | class PAS {
1828		l+h, n-h, l, g, null).compute();
1829		}
1830		else
1831	<	Arrays.sort(a, l, l+n, cmp);
1831	>	lquickSort(a, cmp, l, l+n-1);
1832		}
1833		}
1834
#	Line 1840 | Line 1840 | class PAS {
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) {
#	Line 1887 | Line 1887 | class PAS {
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
#	Line 2302 | Line 2302 | class PAS {
2302		}
2303		}
2304
2305	+	/** Cutoff for when to use insertion-sort instead of quicksort */
2306	+	static final int INSERTION_SORT_THRESHOLD = 8;
2307	+
2308	+	// versions of quicksort with comparators
2309	+
2310	+
2311	+	static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2312	+	for (;;) {
2313	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2314	+	for (int i = lo + 1; i <= hi; i++) {
2315	+	double t = a[i];
2316	+	int j = i - 1;
2317	+	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2318	+	a[j+1] = a[j];
2319	+	--j;
2320	+	}
2321	+	a[j+1] = t;
2322	+	}
2323	+	return;
2324	+	}
2325	+
2326	+	int mid = (lo + hi) >>> 1;
2327	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2328	+	double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2329	+	}
2330	+	if (cmp.compare(a[mid], a[hi]) > 0) {
2331	+	double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2332	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2333	+	double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2334	+	}
2335	+	}
2336	+
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	+	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;
2354	+	}
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;
2363	+	}
2364	+	else {
2365	+	dquickSort(a, cmp, right, hi);
2366	+	hi = left;
2367	+	}
2368	+	}
2369	+	}
2370	+
2371	+	static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2372	+	for (;;) {
2373	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2374	+	for (int i = lo + 1; i <= hi; i++) {
2375	+	long t = a[i];
2376	+	int j = i - 1;
2377	+	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2378	+	a[j+1] = a[j];
2379	+	--j;
2380	+	}
2381	+	a[j+1] = t;
2382	+	}
2383	+	return;
2384	+	}
2385	+
2386	+	int mid = (lo + hi) >>> 1;
2387	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2388	+	long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2389	+	}
2390	+	if (cmp.compare(a[mid], a[hi]) > 0) {
2391	+	long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2392	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2393	+	long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2394	+	}
2395	+	}
2396	+
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	+	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;
2414	+	}
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;
2423	+	}
2424	+	else {
2425	+	lquickSort(a, cmp, right, hi);
2426	+	hi = left;
2427	+	}
2428	+	}
2429	+	}
2430	+
2431		/**
2432		* Cumulative scan
2433		*
#	Line 2335 | Line 2461 | class PAS {
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;
#	Line 2429 | Line 2555 | class PAS {
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)) {
#	Line 2506 | Line 2632 | class PAS {
2632		/**
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;
#	Line 2523 | Line 2649 | class PAS {
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;
#	Line 2613 | Line 2739 | class PAS {
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;
#	Line 2703 | Line 2829 | class PAS {
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;
#	Line 2795 | Line 2921 | class PAS {
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);
#	Line 2877 | Line 3003 | class PAS {
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);

Diff Legend

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