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.5 by jsr166, Sat Aug 1 22:12:58 2009 UTC vs.
Revision 1.16 by jsr166, Tue Feb 21 01:54:03 2012 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 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 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 1681 | Line 1681 | class PAS {
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
#	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 1717 | Line 1717 | class PAS {
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
#	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 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 1790 | Line 1790 | class PAS {
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
#	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 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 1865 | Line 1865 | class PAS {
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
#	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 2305 | Line 2305 | class PAS {
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 (;;) {
#	Line 2440 | Line 2337 | class PAS {
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;
#	Line 2452 | Line 2355 | class PAS {
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;
#	Line 2463 | Line 2368 | class PAS {
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) {
#	Line 2544 | Line 2397 | class PAS {
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;
#	Line 2556 | Line 2415 | class PAS {
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;
#	Line 2567 | Line 2428 | class PAS {
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		*
#	Line 2746 | 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 2821 | Line 2630 | class PAS {
2630		}
2631
2632		/**
2633	<	* Computational operations for FJSCan
2633	>	* Computational operations for FJScan
2634		*/
2635		static abstract class FJScanOp {
2636		final int threshold;

Diff Legend

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