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.10 by jsr166, Thu Sep 16 03:57:13 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 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 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 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 && (c = cmp.compare(pivot, a[left])) >= 0){
2345	>	if (c != 0)
2346	>	sameLefts = false;
2347		++left;
2348	+	}
2349		if (left < right) {
2350		Object t = a[left]; a[left] = a[right]; a[right] = t;
2351		--right;
#	Line 2348 | Line 2353 | class PAS {
2353		else break;
2354		}
2355
2356	+	if (sameLefts && right == hi - 1)
2357	+	return;
2358		if (left - lo <= hi - right) {
2359		oquickSort(a, cmp, lo, left);
2360		lo = left + 1;
2361	<	}
2361	>	}
2362		else {
2363		oquickSort(a, cmp, right, hi);
2364		hi = left;
#	Line 2384 | Line 2391 | class PAS {
2391		Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2392		}
2393		}
2387	–
2394		Comparable pivot = a[mid];
2395		int left = lo+1;
2396		int right = hi-1;
2397	+	boolean sameLefts = true;
2398		for (;;) {
2399		while (pivot.compareTo(a[right]) < 0)
2400		--right;
2401	<	while (left < right && pivot.compareTo(a[left]) >= 0)
2401	>	int c;
2402	>	while (left < right && (c = pivot.compareTo(a[left])) >= 0) {
2403	>	if (c != 0)
2404	>	sameLefts = false;
2405		++left;
2406	+	}
2407		if (left < right) {
2408		Comparable t = a[left]; a[left] = a[right]; a[right] = t;
2409		--right;
#	Line 2400 | Line 2411 | class PAS {
2411		else break;
2412		}
2413
2414	+	if (sameLefts && right == hi - 1)
2415	+	return;
2416		if (left - lo <= hi - right) {
2417		ocquickSort(a, lo, left);
2418		lo = left + 1;
#	Line 2411 | Line 2424 | class PAS {
2424		}
2425		}
2426
2427	+
2428		static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2429		for (;;) {
2430		if (hi - lo <= INSERTION_SORT_THRESHOLD) {
#	Line 2440 | Line 2454 | class PAS {
2454		double pivot = a[mid];
2455		int left = lo+1;
2456		int right = hi-1;
2457	+	boolean sameLefts = true;
2458		for (;;) {
2459		while (cmp.compare(pivot, a[right]) < 0)
2460		--right;
2461	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2461	>	int c;
2462	>	while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){
2463	>	if (c != 0)
2464	>	sameLefts = false;
2465		++left;
2448	–	if (left < right) {
2449	–	double t = a[left]; a[left] = a[right]; a[right] = t;
2450	–	--right;
2451	–	}
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;
2466		}
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;
2467		if (left < right) {
2468		double t = a[left]; a[left] = a[right]; a[right] = t;
2469		--right;
#	Line 2504 | Line 2471 | class PAS {
2471		else break;
2472		}
2473
2474	+	if (sameLefts && right == hi - 1)
2475	+	return;
2476		if (left - lo <= hi - right) {
2477	<	dcquickSort(a, lo, left);
2477	>	dquickSort(a, cmp, lo, left);
2478		lo = left + 1;
2479		}
2480		else {
2481	<	dcquickSort(a, right, hi);
2481	>	dquickSort(a, cmp, right, hi);
2482		hi = left;
2483		}
2484		}
#	Line 2544 | Line 2513 | class PAS {
2513		long pivot = a[mid];
2514		int left = lo+1;
2515		int right = hi-1;
2516	+	boolean sameLefts = true;
2517		for (;;) {
2518		while (cmp.compare(pivot, a[right]) < 0)
2519		--right;
2520	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2520	>	int c;
2521	>	while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){
2522	>	if (c != 0)
2523	>	sameLefts = false;
2524		++left;
2552	–	if (left < right) {
2553	–	long t = a[left]; a[left] = a[right]; a[right] = t;
2554	–	--right;
2525		}
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;
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;
2526		if (left < right) {
2527		long t = a[left]; a[left] = a[right]; a[right] = t;
2528		--right;
#	Line 2608 | Line 2530 | class PAS {
2530		else break;
2531		}
2532
2533	+	if (sameLefts && right == hi - 1)
2534	+	return;
2535		if (left - lo <= hi - right) {
2536	<	lcquickSort(a, lo, left);
2536	>	lquickSort(a, cmp, lo, left);
2537		lo = left + 1;
2538		}
2539		else {
2540	<	lcquickSort(a, right, hi);
2540	>	lquickSort(a, cmp, right, hi);
2541		hi = left;
2542		}
2543		}
#	Line 2709 | Line 2633 | class PAS {
2633		int cb;
2634		for (;;) { // Establish action: sum, cumulate, or both
2635		int b = phase;
2636	<	if ((b & FINISHED) != 0) // already done
2636	>	if ((b & FINISHED) != 0) // already done
2637		return false;
2638		if ((b & CUMULATE) != 0)
2639		cb = FINISHED;
#	Line 2821 | Line 2745 | class PAS {
2745		}
2746
2747		/**
2748	<	* Computational operations for FJSCan
2748	>	* Computational operations for FJScan
2749		*/
2750		static abstract class FJScanOp {
2751		final int threshold;

Diff Legend

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