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.12 by jsr166, Fri Oct 22 05:18:30 2010 UTC

#	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 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 1524 | Line 1524 | class PAS {
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 (;;) {
#	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 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 1875 | Line 1875 | class PAS {
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() {
#	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
2308	>	// versions of quicksort with comparators
2309
2310		static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
2311		for (;;) {
#	Line 2336 | Line 2336 | class PAS {
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;
#	Line 2348 | Line 2354 | class PAS {
2354		else break;
2355		}
2356
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	<	}
2362	>	}
2363		else {
2364		oquickSort(a, cmp, right, hi);
2365		hi = left;
#	Line 2384 | Line 2392 | class PAS {
2392		Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2393		}
2394		}
2387	–
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;
#	Line 2400 | Line 2412 | class PAS {
2412		else break;
2413		}
2414
2415	+	if (sameLefts && right == hi - 1)
2416	+	return;
2417		if (left - lo <= hi - right) {
2418		ocquickSort(a, lo, left);
2419		lo = left + 1;
#	Line 2411 | Line 2425 | class PAS {
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) {
#	Line 2440 | Line 2455 | class PAS {
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;
2448	–	if (left < right) {
2449	–	double t = a[left]; a[left] = a[right]; a[right] = t;
2450	–	--right;
2468		}
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;
2469		if (left < right) {
2470		double t = a[left]; a[left] = a[right]; a[right] = t;
2471		--right;
#	Line 2504 | Line 2473 | class PAS {
2473		else break;
2474		}
2475
2476	+	if (sameLefts && right == hi - 1)
2477	+	return;
2478		if (left - lo <= hi - right) {
2479	<	dcquickSort(a, lo, left);
2479	>	dquickSort(a, cmp, lo, left);
2480		lo = left + 1;
2481		}
2482		else {
2483	<	dcquickSort(a, right, hi);
2483	>	dquickSort(a, cmp, right, hi);
2484		hi = left;
2485		}
2486		}
#	Line 2544 | Line 2515 | class PAS {
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;
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;
2528		}
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;
2529		if (left < right) {
2530		long t = a[left]; a[left] = a[right]; a[right] = t;
2531		--right;
#	Line 2608 | Line 2533 | class PAS {
2533		else break;
2534		}
2535
2536	+	if (sameLefts && right == hi - 1)
2537	+	return;
2538		if (left - lo <= hi - right) {
2539	<	lcquickSort(a, lo, left);
2539	>	lquickSort(a, cmp, lo, left);
2540		lo = left + 1;
2541		}
2542		else {
2543	<	lcquickSort(a, right, hi);
2543	>	lquickSort(a, cmp, right, hi);
2544		hi = left;
2545		}
2546		}
#	Line 2709 | Line 2636 | class PAS {
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;
#	Line 2746 | Line 2673 | class PAS {
2673		op.pushUp(par, par.left, par.right);
2674		int refork =
2675		((pb & CUMULATE) == 0 &&
2676	<	par.lo == op.origin)? CUMULATE : 0;
2676	>	par.lo == op.origin) ? CUMULATE : 0;
2677		int nextPhase = pb|cb|refork;
2678		if (pb == nextPhase ||
2679		phaseUpdater.compareAndSet(par, pb, nextPhase)) {
#	Line 2821 | Line 2748 | class PAS {
2748		}
2749
2750		/**
2751	<	* Computational operations for FJSCan
2751	>	* Computational operations for FJScan
2752		*/
2753		static abstract class FJScanOp {
2754		final int threshold;

Diff Legend

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