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.1 by dl, Tue Jan 6 14:30:57 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() {
1882	<	invokeAll(left, right);
1882	>	right.fork();
1883	>	left.invoke();
1884	>	right.join();
1885		merger.invoke();
1886		}
1887		}
#	Line 2303 | 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 2334 | 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 2346 | Line 2354 | class PAS {
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
#	Line 2376 | Line 2392 | class PAS {
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;
#	Line 2392 | Line 2412 | class PAS {
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) {
#	Line 2426 | 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;
2468	+	}
2469		if (left < right) {
2470		double t = a[left]; a[left] = a[right]; a[right] = t;
2471		--right;
#	Line 2438 | Line 2473 | class PAS {
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
#	Line 2518 | 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;
2528	+	}
2529		if (left < right) {
2530		long t = a[left]; a[left] = a[right]; a[right] = t;
2531		--right;
#	Line 2530 | Line 2533 | class PAS {
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
#	Line 2671 | 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 2708 | 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 2783 | 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