1 /*
2 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util;
26
27 import java.util.concurrent.RecursiveAction;
28
29 /**
30 * Helper utilities for the parallel sort methods in Arrays.parallelSort.
31 *
32 * For each primitive type, plus Object, we define a static class to
33 * contain the Sorter and Merger implementations for that type:
34 *
35 * Sorter classes based mainly on CilkSort
36 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
37 * Basic algorithm:
38 * if array size is small, just use a sequential quicksort (via Arrays.sort)
39 * Otherwise:
40 * 1. Break array in half.
41 * 2. For each half,
42 * a. break the half in half (i.e., quarters),
43 * b. sort the quarters
44 * c. merge them together
45 * 3. merge together the two halves.
46 *
47 * One reason for splitting in quarters is that this guarantees
48 * that the final sort is in the main array, not the workspace
49 * array. (workspace and main swap roles on each subsort step.)
50 * Leaf-level sorts use a Sequential quicksort, that in turn uses
51 * insertion sort if under threshold. Otherwise it uses median of
52 * three to pick pivot, and loops rather than recurses along left
53 * path.
54 *
55 *
56 * Merger classes perform merging for Sorter. If big enough, splits Left
57 * partition in half; finds the greatest point in Right partition
58 * less than the beginning of the second half of Left via binary
59 * search; and then, in parallel, merges left half of Left with
60 * elements of Right up to split point, and merges right half of
61 * Left with elements of R past split point. At leaf, it just
62 * sequentially merges. This is all messy to code; sadly we need
63 * distinct versions for each type.
64 *
65 */
66 /*package*/ class ArraysParallelSortHelpers {
67
68 // RFE: we should only need a working array as large as the subarray
69 // to be sorted, but the logic assumes that indices in the two
70 // arrays always line-up
71
72 /** byte support class */
73 static final class FJByte {
74 static final class Sorter extends RecursiveAction {
75 static final long serialVersionUID = 749471161188027634L;
76 final byte[] a; // array to be sorted.
77 final byte[] w; // workspace for merge
78 final int origin; // origin of the part of array we deal with
79 final int n; // Number of elements in (sub)arrays.
80 final int gran; // split control
81
82 Sorter(byte[] a, byte[] w, int origin, int n, int gran) {
83 this.a = a;
84 this.w = w;
85 this.origin = origin;
86 this.n = n;
87 this.gran = gran;
88 }
89
90 public void compute() {
91 final int l = origin;
92 final int g = gran;
93 final int n = this.n;
94 final byte[] a = this.a;
95 final byte[] w = this.w;
96 if (n > g) {
97 int h = n >>> 1; // half
98 int q = n >>> 2; // lower quarter index
99 int u = h + q; // upper quarter
100 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
101 new Sorter(a, w, l+q, h-q, g),
102 new Merger(a, w, l, q,
103 l+q, h-q, l, g, null));
104 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l+h, q, g),
105 new Sorter(a, w, l+u, n-u, g),
106 new Merger(a, w, l+h, q,
107 l+u, n-u, l+h, g, null));
108 rs.fork();
109 ls.compute();
110 if (rs.tryUnfork()) rs.compute(); else rs.join();
111 new Merger(w, a, l, h,
112 l+h, n-h, l, g, null).compute();
113 } else {
114 DualPivotQuicksort.sort(a, l, l+n-1); //skip rangeCheck
115 }
116 }
117 }
118
119 static final class Merger extends RecursiveAction {
120 static final long serialVersionUID = -9090258248781844470L;
121 final byte[] a;
122 final byte[] w;
123 final int lo;
124 final int ln;
125 final int ro;
126 final int rn;
127 final int wo;
128 final int gran;
129 final Merger next;
130
131 Merger(byte[] a, byte[] w, int lo, int ln, int ro, int rn, int wo,
132 int gran, Merger next) {
133 this.a = a;
134 this.w = w;
135 this.lo = lo;
136 this.ln = ln;
137 this.ro = ro;
138 this.rn = rn;
139 this.wo = wo;
140 this.gran = gran;
141 this.next = next;
142 }
143
144 public void compute() {
145 final byte[] a = this.a;
146 final byte[] w = this.w;
147 Merger rights = null;
148 int nleft = ln;
149 int nright = rn;
150 while (nleft > gran) {
151 int lh = nleft >>> 1;
152 int splitIndex = lo + lh;
153 byte split = a[splitIndex];
154 int rl = 0;
155 int rh = nright;
156 while (rl < rh) {
157 int mid = (rl + rh) >>> 1;
158 if (split <= a[ro + mid])
159 rh = mid;
160 else
161 rl = mid + 1;
162 }
163 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
164 nright-rh, wo+lh+rh, gran, rights)).fork();
165 nleft = lh;
166 nright = rh;
167 }
168
169 int l = lo;
170 int lFence = l + nleft;
171 int r = ro;
172 int rFence = r + nright;
173 int k = wo;
174 while (l < lFence && r < rFence) {
175 byte al = a[l];
176 byte ar = a[r];
177 byte t;
178 if (al <= ar) {++l; t=al;} else {++r; t = ar;}
179 w[k++] = t;
180 }
181 while (l < lFence)
182 w[k++] = a[l++];
183 while (r < rFence)
184 w[k++] = a[r++];
185 while (rights != null) {
186 if (rights.tryUnfork())
187 rights.compute();
188 else
189 rights.join();
190 rights = rights.next;
191 }
192 }
193 }
194 } // FJByte
195
196 /** char support class */
197 static final class FJChar {
198 static final class Sorter extends RecursiveAction {
199 static final long serialVersionUID = 8723376019074596641L;
200 final char[] a; // array to be sorted.
201 final char[] w; // workspace for merge
202 final int origin; // origin of the part of array we deal with
203 final int n; // Number of elements in (sub)arrays.
204 final int gran; // split control
205
206 Sorter(char[] a, char[] w, int origin, int n, int gran) {
207 this.a = a;
208 this.w = w;
209 this.origin = origin;
210 this.n = n;
211 this.gran = gran;
212 }
213
214 public void compute() {
215 final int l = origin;
216 final int g = gran;
217 final int n = this.n;
218 final char[] a = this.a;
219 final char[] w = this.w;
220 if (n > g) {
221 int h = n >>> 1; // half
222 int q = n >>> 2; // lower quarter index
223 int u = h + q; // upper quarter
224 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
225 new Sorter(a, w, l+q, h-q, g),
226 new Merger(a, w, l, q,
227 l+q, h-q, l, g, null));
228 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g),
229 new Sorter(a, w, l+u, n-u, g),
230 new Merger(a, w, l+h, q,
231 l+u, n-u, l+h, g, null));
232 rs.fork();
233 ls.compute();
234 if (rs.tryUnfork()) rs.compute(); else rs.join();
235 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
236 } else {
237 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck
238 }
239 }
240 }
241
242 static final class Merger extends RecursiveAction {
243 static final long serialVersionUID = -1383975444621698926L;
244 final char[] a;
245 final char[] w;
246 final int lo;
247 final int ln;
248 final int ro;
249 final int rn;
250 final int wo;
251 final int gran;
252 final Merger next;
253
254 Merger(char[] a, char[] w, int lo, int ln, int ro, int rn, int wo,
255 int gran, Merger next) {
256 this.a = a;
257 this.w = w;
258 this.lo = lo;
259 this.ln = ln;
260 this.ro = ro;
261 this.rn = rn;
262 this.wo = wo;
263 this.gran = gran;
264 this.next = next;
265 }
266
267 public void compute() {
268 final char[] a = this.a;
269 final char[] w = this.w;
270 Merger rights = null;
271 int nleft = ln;
272 int nright = rn;
273 while (nleft > gran) {
274 int lh = nleft >>> 1;
275 int splitIndex = lo + lh;
276 char split = a[splitIndex];
277 int rl = 0;
278 int rh = nright;
279 while (rl < rh) {
280 int mid = (rl + rh) >>> 1;
281 if (split <= a[ro + mid])
282 rh = mid;
283 else
284 rl = mid + 1;
285 }
286 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
287 nright-rh, wo+lh+rh, gran, rights)).fork();
288 nleft = lh;
289 nright = rh;
290 }
291
292 int l = lo;
293 int lFence = l + nleft;
294 int r = ro;
295 int rFence = r + nright;
296 int k = wo;
297 while (l < lFence && r < rFence) {
298 char al = a[l];
299 char ar = a[r];
300 char t;
301 if (al <= ar) {++l; t=al;} else {++r; t = ar;}
302 w[k++] = t;
303 }
304 while (l < lFence)
305 w[k++] = a[l++];
306 while (r < rFence)
307 w[k++] = a[r++];
308 while (rights != null) {
309 if (rights.tryUnfork())
310 rights.compute();
311 else
312 rights.join();
313 rights = rights.next;
314 }
315 }
316 }
317 } // FJChar
318
319 /** short support class */
320 static final class FJShort {
321 static final class Sorter extends RecursiveAction {
322 static final long serialVersionUID = -7886754793730583084L;
323 final short[] a; // array to be sorted.
324 final short[] w; // workspace for merge
325 final int origin; // origin of the part of array we deal with
326 final int n; // Number of elements in (sub)arrays.
327 final int gran; // split control
328
329 Sorter(short[] a, short[] w, int origin, int n, int gran) {
330 this.a = a;
331 this.w = w;
332 this.origin = origin;
333 this.n = n;
334 this.gran = gran;
335 }
336
337 public void compute() {
338 final int l = origin;
339 final int g = gran;
340 final int n = this.n;
341 final short[] a = this.a;
342 final short[] w = this.w;
343 if (n > g) {
344 int h = n >>> 1; // half
345 int q = n >>> 2; // lower quarter index
346 int u = h + q; // upper quarter
347 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
348 new Sorter(a, w, l+q, h-q, g),
349 new Merger(a, w, l, q,
350 l+q, h-q, l, g, null));
351 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g),
352 new Sorter(a, w, l+u, n-u, g),
353 new Merger(a, w, l+h, q,
354 l+u, n-u, l+h, g, null));
355 rs.fork();
356 ls.compute();
357 if (rs.tryUnfork()) rs.compute(); else rs.join();
358 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
359 } else {
360 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck
361 }
362 }
363 }
364
365 static final class Merger extends RecursiveAction {
366 static final long serialVersionUID = 3895749408536700048L;
367 final short[] a;
368 final short[] w;
369 final int lo;
370 final int ln;
371 final int ro;
372 final int rn;
373 final int wo;
374 final int gran;
375 final Merger next;
376
377 Merger(short[] a, short[] w, int lo, int ln, int ro, int rn, int wo,
378 int gran, Merger next) {
379 this.a = a;
380 this.w = w;
381 this.lo = lo;
382 this.ln = ln;
383 this.ro = ro;
384 this.rn = rn;
385 this.wo = wo;
386 this.gran = gran;
387 this.next = next;
388 }
389
390 public void compute() {
391 final short[] a = this.a;
392 final short[] w = this.w;
393 Merger rights = null;
394 int nleft = ln;
395 int nright = rn;
396 while (nleft > gran) {
397 int lh = nleft >>> 1;
398 int splitIndex = lo + lh;
399 short split = a[splitIndex];
400 int rl = 0;
401 int rh = nright;
402 while (rl < rh) {
403 int mid = (rl + rh) >>> 1;
404 if (split <= a[ro + mid])
405 rh = mid;
406 else
407 rl = mid + 1;
408 }
409 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
410 nright-rh, wo+lh+rh, gran, rights)).fork();
411 nleft = lh;
412 nright = rh;
413 }
414
415 int l = lo;
416 int lFence = l + nleft;
417 int r = ro;
418 int rFence = r + nright;
419 int k = wo;
420 while (l < lFence && r < rFence) {
421 short al = a[l];
422 short ar = a[r];
423 short t;
424 if (al <= ar) {++l; t=al;} else {++r; t = ar;}
425 w[k++] = t;
426 }
427 while (l < lFence)
428 w[k++] = a[l++];
429 while (r < rFence)
430 w[k++] = a[r++];
431 while (rights != null) {
432 if (rights.tryUnfork())
433 rights.compute();
434 else
435 rights.join();
436 rights = rights.next;
437 }
438 }
439 }
440 } // FJShort
441
442 /** int support class */
443 static final class FJInt {
444 static final class Sorter extends RecursiveAction {
445 static final long serialVersionUID = 4263311808957292729L;
446 final int[] a; // array to be sorted.
447 final int[] w; // workspace for merge
448 final int origin; // origin of the part of array we deal with
449 final int n; // Number of elements in (sub)arrays.
450 final int gran; // split control
451
452 Sorter(int[] a, int[] w, int origin, int n, int gran) {
453 this.a = a;
454 this.w = w;
455 this.origin = origin;
456 this.n = n;
457 this.gran = gran;
458 }
459
460 public void compute() {
461 final int l = origin;
462 final int g = gran;
463 final int n = this.n;
464 final int[] a = this.a;
465 final int[] w = this.w;
466 if (n > g) {
467 int h = n >>> 1; // half
468 int q = n >>> 2; // lower quarter index
469 int u = h + q; // upper quarter
470 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
471 new Sorter(a, w, l+q, h-q, g),
472 new Merger(a, w, l, q,
473 l+q, h-q, l, g, null));
474 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g),
475 new Sorter(a, w, l+u, n-u, g),
476 new Merger(a, w, l+h, q,
477 l+u, n-u, l+h, g, null));
478 rs.fork();
479 ls.compute();
480 if (rs.tryUnfork()) rs.compute(); else rs.join();
481 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
482 } else {
483 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck
484 }
485 }
486 }
487
488 static final class Merger extends RecursiveAction {
489 static final long serialVersionUID = -8727507284219982792L;
490 final int[] a;
491 final int[] w;
492 final int lo;
493 final int ln;
494 final int ro;
495 final int rn;
496 final int wo;
497 final int gran;
498 final Merger next;
499
500 Merger(int[] a, int[] w, int lo, int ln, int ro, int rn, int wo,
501 int gran, Merger next) {
502 this.a = a;
503 this.w = w;
504 this.lo = lo;
505 this.ln = ln;
506 this.ro = ro;
507 this.rn = rn;
508 this.wo = wo;
509 this.gran = gran;
510 this.next = next;
511 }
512
513 public void compute() {
514 final int[] a = this.a;
515 final int[] w = this.w;
516 Merger rights = null;
517 int nleft = ln;
518 int nright = rn;
519 while (nleft > gran) {
520 int lh = nleft >>> 1;
521 int splitIndex = lo + lh;
522 int split = a[splitIndex];
523 int rl = 0;
524 int rh = nright;
525 while (rl < rh) {
526 int mid = (rl + rh) >>> 1;
527 if (split <= a[ro + mid])
528 rh = mid;
529 else
530 rl = mid + 1;
531 }
532 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
533 nright-rh, wo+lh+rh, gran, rights)).fork();
534 nleft = lh;
535 nright = rh;
536 }
537
538 int l = lo;
539 int lFence = l + nleft;
540 int r = ro;
541 int rFence = r + nright;
542 int k = wo;
543 while (l < lFence && r < rFence) {
544 int al = a[l];
545 int ar = a[r];
546 int t;
547 if (al <= ar) {++l; t=al;} else {++r; t = ar;}
548 w[k++] = t;
549 }
550 while (l < lFence)
551 w[k++] = a[l++];
552 while (r < rFence)
553 w[k++] = a[r++];
554 while (rights != null) {
555 if (rights.tryUnfork())
556 rights.compute();
557 else
558 rights.join();
559 rights = rights.next;
560 }
561 }
562 }
563 } // FJInt
564
565 /** long support class */
566 static final class FJLong {
567 static final class Sorter extends RecursiveAction {
568 static final long serialVersionUID = 6553695007444392455L;
569 final long[] a; // array to be sorted.
570 final long[] w; // workspace for merge
571 final int origin; // origin of the part of array we deal with
572 final int n; // Number of elements in (sub)arrays.
573 final int gran; // split control
574
575 Sorter(long[] a, long[] w, int origin, int n, int gran) {
576 this.a = a;
577 this.w = w;
578 this.origin = origin;
579 this.n = n;
580 this.gran = gran;
581 }
582
583 public void compute() {
584 final int l = origin;
585 final int g = gran;
586 final int n = this.n;
587 final long[] a = this.a;
588 final long[] w = this.w;
589 if (n > g) {
590 int h = n >>> 1; // half
591 int q = n >>> 2; // lower quarter index
592 int u = h + q; // upper quarter
593 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
594 new Sorter(a, w, l+q, h-q, g),
595 new Merger(a, w, l, q,
596 l+q, h-q, l, g, null));
597 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g),
598 new Sorter(a, w, l+u, n-u, g),
599 new Merger(a, w, l+h, q,
600 l+u, n-u, l+h, g, null));
601 rs.fork();
602 ls.compute();
603 if (rs.tryUnfork()) rs.compute(); else rs.join();
604 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
605 } else {
606 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck
607 }
608 }
609 }
610
611 static final class Merger extends RecursiveAction {
612 static final long serialVersionUID = 8843567516333283861L;
613 final long[] a;
614 final long[] w;
615 final int lo;
616 final int ln;
617 final int ro;
618 final int rn;
619 final int wo;
620 final int gran;
621 final Merger next;
622
623 Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo,
624 int gran, Merger next) {
625 this.a = a;
626 this.w = w;
627 this.lo = lo;
628 this.ln = ln;
629 this.ro = ro;
630 this.rn = rn;
631 this.wo = wo;
632 this.gran = gran;
633 this.next = next;
634 }
635
636 public void compute() {
637 final long[] a = this.a;
638 final long[] w = this.w;
639 Merger rights = null;
640 int nleft = ln;
641 int nright = rn;
642 while (nleft > gran) {
643 int lh = nleft >>> 1;
644 int splitIndex = lo + lh;
645 long split = a[splitIndex];
646 int rl = 0;
647 int rh = nright;
648 while (rl < rh) {
649 int mid = (rl + rh) >>> 1;
650 if (split <= a[ro + mid])
651 rh = mid;
652 else
653 rl = mid + 1;
654 }
655 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
656 nright-rh, wo+lh+rh, gran, rights)).fork();
657 nleft = lh;
658 nright = rh;
659 }
660
661 int l = lo;
662 int lFence = l + nleft;
663 int r = ro;
664 int rFence = r + nright;
665 int k = wo;
666 while (l < lFence && r < rFence) {
667 long al = a[l];
668 long ar = a[r];
669 long t;
670 if (al <= ar) {++l; t=al;} else {++r; t = ar;}
671 w[k++] = t;
672 }
673 while (l < lFence)
674 w[k++] = a[l++];
675 while (r < rFence)
676 w[k++] = a[r++];
677 while (rights != null) {
678 if (rights.tryUnfork())
679 rights.compute();
680 else
681 rights.join();
682 rights = rights.next;
683 }
684 }
685 }
686 } // FJLong
687
688 /** float support class */
689 static final class FJFloat {
690 static final class Sorter extends RecursiveAction {
691 static final long serialVersionUID = 1602600178202763377L;
692 final float[] a; // array to be sorted.
693 final float[] w; // workspace for merge
694 final int origin; // origin of the part of array we deal with
695 final int n; // Number of elements in (sub)arrays.
696 final int gran; // split control
697
698 Sorter(float[] a, float[] w, int origin, int n, int gran) {
699 this.a = a;
700 this.w = w;
701 this.origin = origin;
702 this.n = n;
703 this.gran = gran;
704 }
705
706 public void compute() {
707 final int l = origin;
708 final int g = gran;
709 final int n = this.n;
710 final float[] a = this.a;
711 final float[] w = this.w;
712 if (n > g) {
713 int h = n >>> 1; // half
714 int q = n >>> 2; // lower quarter index
715 int u = h + q; // upper quarter
716 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
717 new Sorter(a, w, l+q, h-q, g),
718 new Merger(a, w, l, q,
719 l+q, h-q, l, g, null));
720 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g),
721 new Sorter(a, w, l+u, n-u, g),
722 new Merger(a, w, l+h, q,
723 l+u, n-u, l+h, g, null));
724 rs.fork();
725 ls.compute();
726 if (rs.tryUnfork()) rs.compute(); else rs.join();
727 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
728 } else {
729 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck
730 }
731 }
732 }
733
734 static final class Merger extends RecursiveAction {
735 static final long serialVersionUID = 1518176433845397426L;
736 final float[] a;
737 final float[] w;
738 final int lo;
739 final int ln;
740 final int ro;
741 final int rn;
742 final int wo;
743 final int gran;
744 final Merger next;
745
746 Merger(float[] a, float[] w, int lo, int ln, int ro, int rn, int wo,
747 int gran, Merger next) {
748 this.a = a;
749 this.w = w;
750 this.lo = lo;
751 this.ln = ln;
752 this.ro = ro;
753 this.rn = rn;
754 this.wo = wo;
755 this.gran = gran;
756 this.next = next;
757 }
758
759 public void compute() {
760 final float[] a = this.a;
761 final float[] w = this.w;
762 Merger rights = null;
763 int nleft = ln;
764 int nright = rn;
765 while (nleft > gran) {
766 int lh = nleft >>> 1;
767 int splitIndex = lo + lh;
768 float split = a[splitIndex];
769 int rl = 0;
770 int rh = nright;
771 while (rl < rh) {
772 int mid = (rl + rh) >>> 1;
773 if (Float.compare(split, a[ro+mid]) <= 0)
774 rh = mid;
775 else
776 rl = mid + 1;
777 }
778 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
779 nright-rh, wo+lh+rh, gran, rights)).fork();
780 nleft = lh;
781 nright = rh;
782 }
783
784 int l = lo;
785 int lFence = l + nleft;
786 int r = ro;
787 int rFence = r + nright;
788 int k = wo;
789 while (l < lFence && r < rFence) {
790 float al = a[l];
791 float ar = a[r];
792 float t;
793 if (Float.compare(al, ar) <= 0) {
794 ++l;
795 t = al;
796 } else {
797 ++r;
798 t = ar;
799 }
800 w[k++] = t;
801 }
802 while (l < lFence)
803 w[k++] = a[l++];
804 while (r < rFence)
805 w[k++] = a[r++];
806 while (rights != null) {
807 if (rights.tryUnfork())
808 rights.compute();
809 else
810 rights.join();
811 rights = rights.next;
812 }
813 }
814 }
815 } // FJFloat
816
817 /** double support class */
818 static final class FJDouble {
819 static final class Sorter extends RecursiveAction {
820 static final long serialVersionUID = 2446542900576103244L;
821 final double[] a; // array to be sorted.
822 final double[] w; // workspace for merge
823 final int origin; // origin of the part of array we deal with
824 final int n; // Number of elements in (sub)arrays.
825 final int gran; // split control
826
827 Sorter(double[] a, double[] w, int origin, int n, int gran) {
828 this.a = a;
829 this.w = w;
830 this.origin = origin;
831 this.n = n;
832 this.gran = gran;
833 }
834
835 public void compute() {
836 final int l = origin;
837 final int g = gran;
838 final int n = this.n;
839 final double[] a = this.a;
840 final double[] w = this.w;
841 if (n > g) {
842 int h = n >>> 1; // half
843 int q = n >>> 2; // lower quarter index
844 int u = h + q; // upper quarter
845 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g),
846 new Sorter(a, w, l+q, h-q, g),
847 new Merger(a, w, l, q,
848 l+q, h-q, l, g, null));
849 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g),
850 new Sorter(a, w, l+u, n-u, g),
851 new Merger(a, w, l+h, q,
852 l+u, n-u, l+h, g, null));
853 rs.fork();
854 ls.compute();
855 if (rs.tryUnfork()) rs.compute(); else rs.join();
856 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
857 } else {
858 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck
859 }
860 }
861 }
862
863 static final class Merger extends RecursiveAction {
864 static final long serialVersionUID = 8076242187166127592L;
865 final double[] a;
866 final double[] w;
867 final int lo;
868 final int ln;
869 final int ro;
870 final int rn;
871 final int wo;
872 final int gran;
873 final Merger next;
874
875 Merger(double[] a, double[] w, int lo, int ln, int ro, int rn, int wo,
876 int gran, Merger next) {
877 this.a = a;
878 this.w = w;
879 this.lo = lo;
880 this.ln = ln;
881 this.ro = ro;
882 this.rn = rn;
883 this.wo = wo;
884 this.gran = gran;
885 this.next = next;
886 }
887
888 public void compute() {
889 final double[] a = this.a;
890 final double[] w = this.w;
891 Merger rights = null;
892 int nleft = ln;
893 int nright = rn;
894 while (nleft > gran) {
895 int lh = nleft >>> 1;
896 int splitIndex = lo + lh;
897 double split = a[splitIndex];
898 int rl = 0;
899 int rh = nright;
900 while (rl < rh) {
901 int mid = (rl + rh) >>> 1;
902 if (Double.compare(split, a[ro+mid]) <= 0)
903 rh = mid;
904 else
905 rl = mid + 1;
906 }
907 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
908 nright-rh, wo+lh+rh, gran, rights)).fork();
909 nleft = lh;
910 nright = rh;
911 }
912
913 int l = lo;
914 int lFence = l + nleft;
915 int r = ro;
916 int rFence = r + nright;
917 int k = wo;
918 while (l < lFence && r < rFence) {
919 double al = a[l];
920 double ar = a[r];
921 double t;
922 if (Double.compare(al, ar) <= 0) {
923 ++l;
924 t = al;
925 } else {
926 ++r;
927 t = ar;
928 }
929 w[k++] = t;
930 }
931 while (l < lFence)
932 w[k++] = a[l++];
933 while (r < rFence)
934 w[k++] = a[r++];
935 while (rights != null) {
936 if (rights.tryUnfork())
937 rights.compute();
938 else
939 rights.join();
940 rights = rights.next;
941 }
942 }
943 }
944 } // FJDouble
945
946 /** Comparable support class */
947 static final class FJComparable {
948 static final class Sorter<T extends Comparable<? super T>> extends RecursiveAction {
949 static final long serialVersionUID = -1024003289463302522L;
950 final T[] a;
951 final T[] w;
952 final int origin;
953 final int n;
954 final int gran;
955
956 Sorter(T[] a, T[] w, int origin, int n, int gran) {
957 this.a = a;
958 this.w = w;
959 this.origin = origin;
960 this.n = n;
961 this.gran = gran;
962 }
963
964 public void compute() {
965 final int l = origin;
966 final int g = gran;
967 final int n = this.n;
968 final T[] a = this.a;
969 final T[] w = this.w;
970 if (n > g) {
971 int h = n >>> 1;
972 int q = n >>> 2;
973 int u = h + q;
974 FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q, g),
975 new Sorter<>(a, w, l+q, h-q, g),
976 new Merger<>(a, w, l, q,
977 l+q, h-q, l, g, null));
978 FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l+h, q, g),
979 new Sorter<>(a, w, l+u, n-u, g),
980 new Merger<>(a, w, l+h, q,
981 l+u, n-u, l+h, g, null));
982 rs.fork();
983 ls.compute();
984 if (rs.tryUnfork()) rs.compute(); else rs.join();
985 new Merger<>(w, a, l, h, l + h, n - h, l, g, null).compute();
986 } else {
987 Arrays.sort(a, l, l+n);
988 }
989 }
990 }
991
992 static final class Merger<T extends Comparable<? super T>> extends RecursiveAction {
993 static final long serialVersionUID = -3989771675258379302L;
994 final T[] a;
995 final T[] w;
996 final int lo;
997 final int ln;
998 final int ro;
999 final int rn;
1000 final int wo;
1001 final int gran;
1002 final Merger<T> next;
1003
1004 Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo,
1005 int gran, Merger<T> next) {
1006 this.a = a;
1007 this.w = w;
1008 this.lo = lo;
1009 this.ln = ln;
1010 this.ro = ro;
1011 this.rn = rn;
1012 this.wo = wo;
1013 this.gran = gran;
1014 this.next = next;
1015 }
1016
1017 public void compute() {
1018 final T[] a = this.a;
1019 final T[] w = this.w;
1020 Merger<T> rights = null;
1021 int nleft = ln;
1022 int nright = rn;
1023 while (nleft > gran) {
1024 int lh = nleft >>> 1;
1025 int splitIndex = lo + lh;
1026 T split = a[splitIndex];
1027 int rl = 0;
1028 int rh = nright;
1029 while (rl < rh) {
1030 int mid = (rl + rh) >>> 1;
1031 if (split.compareTo(a[ro + mid]) <= 0)
1032 rh = mid;
1033 else
1034 rl = mid + 1;
1035 }
1036 (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh,
1037 nright-rh, wo+lh+rh, gran, rights)).fork();
1038 nleft = lh;
1039 nright = rh;
1040 }
1041
1042 int l = lo;
1043 int lFence = l + nleft;
1044 int r = ro;
1045 int rFence = r + nright;
1046 int k = wo;
1047 while (l < lFence && r < rFence) {
1048 T al = a[l];
1049 T ar = a[r];
1050 T t;
1051 if (al.compareTo(ar) <= 0) {++l; t=al;} else {++r; t=ar; }
1052 w[k++] = t;
1053 }
1054 while (l < lFence)
1055 w[k++] = a[l++];
1056 while (r < rFence)
1057 w[k++] = a[r++];
1058 while (rights != null) {
1059 if (rights.tryUnfork())
1060 rights.compute();
1061 else
1062 rights.join();
1063 rights = rights.next;
1064 }
1065 }
1066 }
1067 } // FJComparable
1068
1069 /** Object + Comparator support class */
1070 static final class FJComparator {
1071 static final class Sorter<T> extends RecursiveAction {
1072 static final long serialVersionUID = 9191600840025808581L;
1073 final T[] a; // array to be sorted.
1074 final T[] w; // workspace for merge
1075 final int origin; // origin of the part of array we deal with
1076 final int n; // Number of elements in (sub)arrays.
1077 final int gran; // split control
1078 final Comparator<? super T> cmp; // Comparator to use
1079
1080 Sorter(T[] a, T[] w, int origin, int n, int gran, Comparator<? super T> cmp) {
1081 this.a = a;
1082 this.w = w;
1083 this.origin = origin;
1084 this.n = n;
1085 this.cmp = cmp;
1086 this.gran = gran;
1087 }
1088
1089 public void compute() {
1090 final int l = origin;
1091 final int g = gran;
1092 final int n = this.n;
1093 final T[] a = this.a;
1094 final T[] w = this.w;
1095 if (n > g) {
1096 int h = n >>> 1; // half
1097 int q = n >>> 2; // lower quarter index
1098 int u = h + q; // upper quarter
1099 FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q, g, cmp),
1100 new Sorter<>(a, w, l+q, h-q, g, cmp),
1101 new Merger<>(a, w, l, q,
1102 l+q, h-q, l, g, null, cmp));
1103 FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l + h, q, g, cmp),
1104 new Sorter<>(a, w, l+u, n-u, g, cmp),
1105 new Merger<>(a, w, l+h, q,
1106 l+u, n-u, l+h, g, null, cmp));
1107 rs.fork();
1108 ls.compute();
1109 if (rs.tryUnfork()) rs.compute(); else rs.join();
1110 new Merger<>(w, a, l, h, l + h, n - h, l, g, null, cmp).compute();
1111 } else {
1112 Arrays.sort(a, l, l+n, cmp);
1113 }
1114 }
1115 }
1116
1117 static final class Merger<T> extends RecursiveAction {
1118 static final long serialVersionUID = -2679539040379156203L;
1119 final T[] a;
1120 final T[] w;
1121 final int lo;
1122 final int ln;
1123 final int ro;
1124 final int rn;
1125 final int wo;
1126 final int gran;
1127 final Merger<T> next;
1128 final Comparator<? super T> cmp;
1129
1130 Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo,
1131 int gran, Merger<T> next, Comparator<? super T> cmp) {
1132 this.a = a;
1133 this.w = w;
1134 this.lo = lo;
1135 this.ln = ln;
1136 this.ro = ro;
1137 this.rn = rn;
1138 this.wo = wo;
1139 this.gran = gran;
1140 this.next = next;
1141 this.cmp = cmp;
1142 }
1143
1144 public void compute() {
1145 final T[] a = this.a;
1146 final T[] w = this.w;
1147 Merger<T> rights = null;
1148 int nleft = ln;
1149 int nright = rn;
1150 while (nleft > gran) {
1151 int lh = nleft >>> 1;
1152 int splitIndex = lo + lh;
1153 T split = a[splitIndex];
1154 int rl = 0;
1155 int rh = nright;
1156 while (rl < rh) {
1157 int mid = (rl + rh) >>> 1;
1158 if (cmp.compare(split, a[ro+mid]) <= 0)
1159 rh = mid;
1160 else
1161 rl = mid + 1;
1162 }
1163 (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh,
1164 nright-rh, wo+lh+rh, gran, rights, cmp)).fork();
1165 nleft = lh;
1166 nright = rh;
1167 }
1168
1169 int l = lo;
1170 int lFence = l + nleft;
1171 int r = ro;
1172 int rFence = r + nright;
1173 int k = wo;
1174 while (l < lFence && r < rFence) {
1175 T al = a[l];
1176 T ar = a[r];
1177 T t;
1178 if (cmp.compare(al, ar) <= 0) {
1179 ++l;
1180 t = al;
1181 } else {
1182 ++r;
1183 t = ar;
1184 }
1185 w[k++] = t;
1186 }
1187 while (l < lFence)
1188 w[k++] = a[l++];
1189 while (r < rFence)
1190 w[k++] = a[r++];
1191 while (rights != null) {
1192 if (rights.tryUnfork())
1193 rights.compute();
1194 else
1195 rights.join();
1196 rights = rights.next;
1197 }
1198 }
1199 }
1200 } // FJComparator
1201
1202 /** Utility class to sort half a partitioned array */
1203 private static final class FJSubSorter extends RecursiveAction {
1204 static final long serialVersionUID = 9159249695527935512L;
1205 final RecursiveAction left;
1206 final RecursiveAction right;
1207 final RecursiveAction merger;
1208
1209 FJSubSorter(RecursiveAction left, RecursiveAction right,
1210 RecursiveAction merger) {
1211 this.left = left;
1212 this.right = right;
1213 this.merger = merger;
1214 }
1215
1216 public void compute() {
1217 right.fork();
1218 left.invoke();
1219 right.join();
1220 merger.invoke();
1221 }
1222 }
1223 }