70 * ComparableTimSort, and DualPivotQuicksort sort methods that accept
71 * temp workspace array slices that we will have already allocated, so
72 * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
73 * sort, that does not ever use a workspace array.)
74 */
75 /*package*/ class ArraysParallelSortHelpers {
76
77 /*
78 * Style note: The task classes have a lot of parameters, that are
79 * stored as task fields and copied to local variables and used in
80 * compute() methods, We pack these into as few lines as possible,
81 * and hoist consistency checks among them before main loops, to
82 * reduce distraction.
83 */
84
85 /**
86 * A placeholder task for Sorters, used for the lowest
87 * quartile task, that does not need to maintain array state.
88 */
89 static final class EmptyCompleter extends CountedCompleter<Void> {
90 static final long serialVersionUID = 2446542900576103244L;
91 EmptyCompleter(CountedCompleter<?> p) { super(p); }
92 public final void compute() { }
93 }
94
95 /**
96 * A trigger for secondary merge of two merges
97 */
98 static final class Relay extends CountedCompleter<Void> {
99 static final long serialVersionUID = 2446542900576103244L;
100 final CountedCompleter<?> task;
101 Relay(CountedCompleter<?> task) {
102 super(null, 1);
103 this.task = task;
104 }
105 public final void compute() { }
106 public final void onCompletion(CountedCompleter<?> t) {
107 task.compute();
108 }
109 }
110
111 /** Object + Comparator support class */
112 static final class FJObject {
113 static final class Sorter<T> extends CountedCompleter<Void> {
114 static final long serialVersionUID = 2446542900576103244L;
115 final T[] a, w;
116 final int base, size, wbase, gran;
117 Comparator<? super T> comparator;
118 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
119 int wbase, int gran,
120 Comparator<? super T> comparator) {
121 super(par);
122 this.a = a; this.w = w; this.base = base; this.size = size;
123 this.wbase = wbase; this.gran = gran;
124 this.comparator = comparator;
125 }
126 public final void compute() {
127 CountedCompleter<?> s = this;
128 Comparator<? super T> c = this.comparator;
129 T[] a = this.a, w = this.w; // localize all params
130 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
131 while (n > g) {
132 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
133 Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
134 wb+h, n-h, b, g, c));
135 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
136 b+u, n-u, wb+h, g, c));
137 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
138 new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
139 Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
140 b+q, h-q, wb, g, c));
141 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
142 s = new EmptyCompleter(bc);
143 n = q;
144 }
145 TimSort.sort(a, b, b + n, c, w, wb, n);
146 s.tryComplete();
147 }
148 }
149
150 static final class Merger<T> extends CountedCompleter<Void> {
151 static final long serialVersionUID = 2446542900576103244L;
152 final T[] a, w; // main and workspace arrays
153 final int lbase, lsize, rbase, rsize, wbase, gran;
154 Comparator<? super T> comparator;
155 Merger(CountedCompleter<?> par, T[] a, T[] w,
156 int lbase, int lsize, int rbase,
157 int rsize, int wbase, int gran,
158 Comparator<? super T> comparator) {
159 super(par);
160 this.a = a; this.w = w;
161 this.lbase = lbase; this.lsize = lsize;
162 this.rbase = rbase; this.rsize = rsize;
163 this.wbase = wbase; this.gran = gran;
164 this.comparator = comparator;
165 }
166
167 public final void compute() {
168 Comparator<? super T> c = this.comparator;
169 T[] a = this.a, w = this.w; // localize all params
170 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
216 }
217 else {
218 rb++; t = ar;
219 }
220 w[k++] = t;
221 }
222 if (rb < rf)
223 System.arraycopy(a, rb, w, k, rf - rb);
224 else if (lb < lf)
225 System.arraycopy(a, lb, w, k, lf - lb);
226
227 tryComplete();
228 }
229
230 }
231 } // FJObject
232
233 /** byte support class */
234 static final class FJByte {
235 static final class Sorter extends CountedCompleter<Void> {
236 static final long serialVersionUID = 2446542900576103244L;
237 final byte[] a, w;
238 final int base, size, wbase, gran;
239 Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
240 int size, int wbase, int gran) {
241 super(par);
242 this.a = a; this.w = w; this.base = base; this.size = size;
243 this.wbase = wbase; this.gran = gran;
244 }
245 public final void compute() {
246 CountedCompleter<?> s = this;
247 byte[] a = this.a, w = this.w; // localize all params
248 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
249 while (n > g) {
250 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
251 Relay fc = new Relay(new Merger(s, w, a, wb, h,
252 wb+h, n-h, b, g));
253 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
254 b+u, n-u, wb+h, g));
255 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
256 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
257 Relay bc = new Relay(new Merger(fc, a, w, b, q,
258 b+q, h-q, wb, g));
259 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
260 s = new EmptyCompleter(bc);
261 n = q;
262 }
263 DualPivotQuicksort.sort(a, b, b + n - 1);
264 s.tryComplete();
265 }
266 }
267
268 static final class Merger extends CountedCompleter<Void> {
269 static final long serialVersionUID = 2446542900576103244L;
270 final byte[] a, w; // main and workspace arrays
271 final int lbase, lsize, rbase, rsize, wbase, gran;
272 Merger(CountedCompleter<?> par, byte[] a, byte[] w,
273 int lbase, int lsize, int rbase,
274 int rsize, int wbase, int gran) {
275 super(par);
276 this.a = a; this.w = w;
277 this.lbase = lbase; this.lsize = lsize;
278 this.rbase = rbase; this.rsize = rsize;
279 this.wbase = wbase; this.gran = gran;
280 }
281
282 public final void compute() {
283 byte[] a = this.a, w = this.w; // localize all params
284 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
285 rn = this.rsize, k = this.wbase, g = this.gran;
286 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
287 throw new IllegalStateException(); // hoist checks
288 for (int lh, rh;;) { // split larger, find point in smaller
327 if ((al = a[lb]) <= (ar = a[rb])) {
328 lb++; t = al;
329 }
330 else {
331 rb++; t = ar;
332 }
333 w[k++] = t;
334 }
335 if (rb < rf)
336 System.arraycopy(a, rb, w, k, rf - rb);
337 else if (lb < lf)
338 System.arraycopy(a, lb, w, k, lf - lb);
339 tryComplete();
340 }
341 }
342 } // FJByte
343
344 /** char support class */
345 static final class FJChar {
346 static final class Sorter extends CountedCompleter<Void> {
347 static final long serialVersionUID = 2446542900576103244L;
348 final char[] a, w;
349 final int base, size, wbase, gran;
350 Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
351 int size, int wbase, int gran) {
352 super(par);
353 this.a = a; this.w = w; this.base = base; this.size = size;
354 this.wbase = wbase; this.gran = gran;
355 }
356 public final void compute() {
357 CountedCompleter<?> s = this;
358 char[] a = this.a, w = this.w; // localize all params
359 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
360 while (n > g) {
361 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
362 Relay fc = new Relay(new Merger(s, w, a, wb, h,
363 wb+h, n-h, b, g));
364 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
365 b+u, n-u, wb+h, g));
366 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
367 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
368 Relay bc = new Relay(new Merger(fc, a, w, b, q,
369 b+q, h-q, wb, g));
370 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
371 s = new EmptyCompleter(bc);
372 n = q;
373 }
374 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
375 s.tryComplete();
376 }
377 }
378
379 static final class Merger extends CountedCompleter<Void> {
380 static final long serialVersionUID = 2446542900576103244L;
381 final char[] a, w; // main and workspace arrays
382 final int lbase, lsize, rbase, rsize, wbase, gran;
383 Merger(CountedCompleter<?> par, char[] a, char[] w,
384 int lbase, int lsize, int rbase,
385 int rsize, int wbase, int gran) {
386 super(par);
387 this.a = a; this.w = w;
388 this.lbase = lbase; this.lsize = lsize;
389 this.rbase = rbase; this.rsize = rsize;
390 this.wbase = wbase; this.gran = gran;
391 }
392
393 public final void compute() {
394 char[] a = this.a, w = this.w; // localize all params
395 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
396 rn = this.rsize, k = this.wbase, g = this.gran;
397 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
398 throw new IllegalStateException(); // hoist checks
399 for (int lh, rh;;) { // split larger, find point in smaller
438 if ((al = a[lb]) <= (ar = a[rb])) {
439 lb++; t = al;
440 }
441 else {
442 rb++; t = ar;
443 }
444 w[k++] = t;
445 }
446 if (rb < rf)
447 System.arraycopy(a, rb, w, k, rf - rb);
448 else if (lb < lf)
449 System.arraycopy(a, lb, w, k, lf - lb);
450 tryComplete();
451 }
452 }
453 } // FJChar
454
455 /** short support class */
456 static final class FJShort {
457 static final class Sorter extends CountedCompleter<Void> {
458 static final long serialVersionUID = 2446542900576103244L;
459 final short[] a, w;
460 final int base, size, wbase, gran;
461 Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
462 int size, int wbase, int gran) {
463 super(par);
464 this.a = a; this.w = w; this.base = base; this.size = size;
465 this.wbase = wbase; this.gran = gran;
466 }
467 public final void compute() {
468 CountedCompleter<?> s = this;
469 short[] a = this.a, w = this.w; // localize all params
470 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
471 while (n > g) {
472 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
473 Relay fc = new Relay(new Merger(s, w, a, wb, h,
474 wb+h, n-h, b, g));
475 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
476 b+u, n-u, wb+h, g));
477 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
478 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
479 Relay bc = new Relay(new Merger(fc, a, w, b, q,
480 b+q, h-q, wb, g));
481 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
482 s = new EmptyCompleter(bc);
483 n = q;
484 }
485 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
486 s.tryComplete();
487 }
488 }
489
490 static final class Merger extends CountedCompleter<Void> {
491 static final long serialVersionUID = 2446542900576103244L;
492 final short[] a, w; // main and workspace arrays
493 final int lbase, lsize, rbase, rsize, wbase, gran;
494 Merger(CountedCompleter<?> par, short[] a, short[] w,
495 int lbase, int lsize, int rbase,
496 int rsize, int wbase, int gran) {
497 super(par);
498 this.a = a; this.w = w;
499 this.lbase = lbase; this.lsize = lsize;
500 this.rbase = rbase; this.rsize = rsize;
501 this.wbase = wbase; this.gran = gran;
502 }
503
504 public final void compute() {
505 short[] a = this.a, w = this.w; // localize all params
506 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
507 rn = this.rsize, k = this.wbase, g = this.gran;
508 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
509 throw new IllegalStateException(); // hoist checks
510 for (int lh, rh;;) { // split larger, find point in smaller
549 if ((al = a[lb]) <= (ar = a[rb])) {
550 lb++; t = al;
551 }
552 else {
553 rb++; t = ar;
554 }
555 w[k++] = t;
556 }
557 if (rb < rf)
558 System.arraycopy(a, rb, w, k, rf - rb);
559 else if (lb < lf)
560 System.arraycopy(a, lb, w, k, lf - lb);
561 tryComplete();
562 }
563 }
564 } // FJShort
565
566 /** int support class */
567 static final class FJInt {
568 static final class Sorter extends CountedCompleter<Void> {
569 static final long serialVersionUID = 2446542900576103244L;
570 final int[] a, w;
571 final int base, size, wbase, gran;
572 Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
573 int size, int wbase, int gran) {
574 super(par);
575 this.a = a; this.w = w; this.base = base; this.size = size;
576 this.wbase = wbase; this.gran = gran;
577 }
578 public final void compute() {
579 CountedCompleter<?> s = this;
580 int[] a = this.a, w = this.w; // localize all params
581 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
582 while (n > g) {
583 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
584 Relay fc = new Relay(new Merger(s, w, a, wb, h,
585 wb+h, n-h, b, g));
586 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
587 b+u, n-u, wb+h, g));
588 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
589 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
590 Relay bc = new Relay(new Merger(fc, a, w, b, q,
591 b+q, h-q, wb, g));
592 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
593 s = new EmptyCompleter(bc);
594 n = q;
595 }
596 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
597 s.tryComplete();
598 }
599 }
600
601 static final class Merger extends CountedCompleter<Void> {
602 static final long serialVersionUID = 2446542900576103244L;
603 final int[] a, w; // main and workspace arrays
604 final int lbase, lsize, rbase, rsize, wbase, gran;
605 Merger(CountedCompleter<?> par, int[] a, int[] w,
606 int lbase, int lsize, int rbase,
607 int rsize, int wbase, int gran) {
608 super(par);
609 this.a = a; this.w = w;
610 this.lbase = lbase; this.lsize = lsize;
611 this.rbase = rbase; this.rsize = rsize;
612 this.wbase = wbase; this.gran = gran;
613 }
614
615 public final void compute() {
616 int[] a = this.a, w = this.w; // localize all params
617 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
618 rn = this.rsize, k = this.wbase, g = this.gran;
619 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
620 throw new IllegalStateException(); // hoist checks
621 for (int lh, rh;;) { // split larger, find point in smaller
660 if ((al = a[lb]) <= (ar = a[rb])) {
661 lb++; t = al;
662 }
663 else {
664 rb++; t = ar;
665 }
666 w[k++] = t;
667 }
668 if (rb < rf)
669 System.arraycopy(a, rb, w, k, rf - rb);
670 else if (lb < lf)
671 System.arraycopy(a, lb, w, k, lf - lb);
672 tryComplete();
673 }
674 }
675 } // FJInt
676
677 /** long support class */
678 static final class FJLong {
679 static final class Sorter extends CountedCompleter<Void> {
680 static final long serialVersionUID = 2446542900576103244L;
681 final long[] a, w;
682 final int base, size, wbase, gran;
683 Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
684 int size, int wbase, int gran) {
685 super(par);
686 this.a = a; this.w = w; this.base = base; this.size = size;
687 this.wbase = wbase; this.gran = gran;
688 }
689 public final void compute() {
690 CountedCompleter<?> s = this;
691 long[] a = this.a, w = this.w; // localize all params
692 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
693 while (n > g) {
694 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
695 Relay fc = new Relay(new Merger(s, w, a, wb, h,
696 wb+h, n-h, b, g));
697 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
698 b+u, n-u, wb+h, g));
699 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
700 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
701 Relay bc = new Relay(new Merger(fc, a, w, b, q,
702 b+q, h-q, wb, g));
703 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
704 s = new EmptyCompleter(bc);
705 n = q;
706 }
707 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
708 s.tryComplete();
709 }
710 }
711
712 static final class Merger extends CountedCompleter<Void> {
713 static final long serialVersionUID = 2446542900576103244L;
714 final long[] a, w; // main and workspace arrays
715 final int lbase, lsize, rbase, rsize, wbase, gran;
716 Merger(CountedCompleter<?> par, long[] a, long[] w,
717 int lbase, int lsize, int rbase,
718 int rsize, int wbase, int gran) {
719 super(par);
720 this.a = a; this.w = w;
721 this.lbase = lbase; this.lsize = lsize;
722 this.rbase = rbase; this.rsize = rsize;
723 this.wbase = wbase; this.gran = gran;
724 }
725
726 public final void compute() {
727 long[] a = this.a, w = this.w; // localize all params
728 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
729 rn = this.rsize, k = this.wbase, g = this.gran;
730 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
731 throw new IllegalStateException(); // hoist checks
732 for (int lh, rh;;) { // split larger, find point in smaller
771 if ((al = a[lb]) <= (ar = a[rb])) {
772 lb++; t = al;
773 }
774 else {
775 rb++; t = ar;
776 }
777 w[k++] = t;
778 }
779 if (rb < rf)
780 System.arraycopy(a, rb, w, k, rf - rb);
781 else if (lb < lf)
782 System.arraycopy(a, lb, w, k, lf - lb);
783 tryComplete();
784 }
785 }
786 } // FJLong
787
788 /** float support class */
789 static final class FJFloat {
790 static final class Sorter extends CountedCompleter<Void> {
791 static final long serialVersionUID = 2446542900576103244L;
792 final float[] a, w;
793 final int base, size, wbase, gran;
794 Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
795 int size, int wbase, int gran) {
796 super(par);
797 this.a = a; this.w = w; this.base = base; this.size = size;
798 this.wbase = wbase; this.gran = gran;
799 }
800 public final void compute() {
801 CountedCompleter<?> s = this;
802 float[] a = this.a, w = this.w; // localize all params
803 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
804 while (n > g) {
805 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
806 Relay fc = new Relay(new Merger(s, w, a, wb, h,
807 wb+h, n-h, b, g));
808 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
809 b+u, n-u, wb+h, g));
810 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
811 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
812 Relay bc = new Relay(new Merger(fc, a, w, b, q,
813 b+q, h-q, wb, g));
814 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
815 s = new EmptyCompleter(bc);
816 n = q;
817 }
818 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
819 s.tryComplete();
820 }
821 }
822
823 static final class Merger extends CountedCompleter<Void> {
824 static final long serialVersionUID = 2446542900576103244L;
825 final float[] a, w; // main and workspace arrays
826 final int lbase, lsize, rbase, rsize, wbase, gran;
827 Merger(CountedCompleter<?> par, float[] a, float[] w,
828 int lbase, int lsize, int rbase,
829 int rsize, int wbase, int gran) {
830 super(par);
831 this.a = a; this.w = w;
832 this.lbase = lbase; this.lsize = lsize;
833 this.rbase = rbase; this.rsize = rsize;
834 this.wbase = wbase; this.gran = gran;
835 }
836
837 public final void compute() {
838 float[] a = this.a, w = this.w; // localize all params
839 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
840 rn = this.rsize, k = this.wbase, g = this.gran;
841 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
842 throw new IllegalStateException(); // hoist checks
843 for (int lh, rh;;) { // split larger, find point in smaller
882 if ((al = a[lb]) <= (ar = a[rb])) {
883 lb++; t = al;
884 }
885 else {
886 rb++; t = ar;
887 }
888 w[k++] = t;
889 }
890 if (rb < rf)
891 System.arraycopy(a, rb, w, k, rf - rb);
892 else if (lb < lf)
893 System.arraycopy(a, lb, w, k, lf - lb);
894 tryComplete();
895 }
896 }
897 } // FJFloat
898
899 /** double support class */
900 static final class FJDouble {
901 static final class Sorter extends CountedCompleter<Void> {
902 static final long serialVersionUID = 2446542900576103244L;
903 final double[] a, w;
904 final int base, size, wbase, gran;
905 Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
906 int size, int wbase, int gran) {
907 super(par);
908 this.a = a; this.w = w; this.base = base; this.size = size;
909 this.wbase = wbase; this.gran = gran;
910 }
911 public final void compute() {
912 CountedCompleter<?> s = this;
913 double[] a = this.a, w = this.w; // localize all params
914 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
915 while (n > g) {
916 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
917 Relay fc = new Relay(new Merger(s, w, a, wb, h,
918 wb+h, n-h, b, g));
919 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
920 b+u, n-u, wb+h, g));
921 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
922 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
923 Relay bc = new Relay(new Merger(fc, a, w, b, q,
924 b+q, h-q, wb, g));
925 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
926 s = new EmptyCompleter(bc);
927 n = q;
928 }
929 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
930 s.tryComplete();
931 }
932 }
933
934 static final class Merger extends CountedCompleter<Void> {
935 static final long serialVersionUID = 2446542900576103244L;
936 final double[] a, w; // main and workspace arrays
937 final int lbase, lsize, rbase, rsize, wbase, gran;
938 Merger(CountedCompleter<?> par, double[] a, double[] w,
939 int lbase, int lsize, int rbase,
940 int rsize, int wbase, int gran) {
941 super(par);
942 this.a = a; this.w = w;
943 this.lbase = lbase; this.lsize = lsize;
944 this.rbase = rbase; this.rsize = rsize;
945 this.wbase = wbase; this.gran = gran;
946 }
947
948 public final void compute() {
949 double[] a = this.a, w = this.w; // localize all params
950 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
951 rn = this.rsize, k = this.wbase, g = this.gran;
952 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
953 throw new IllegalStateException(); // hoist checks
954 for (int lh, rh;;) { // split larger, find point in smaller
|
70 * ComparableTimSort, and DualPivotQuicksort sort methods that accept
71 * temp workspace array slices that we will have already allocated, so
72 * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
73 * sort, that does not ever use a workspace array.)
74 */
75 /*package*/ class ArraysParallelSortHelpers {
76
77 /*
78 * Style note: The task classes have a lot of parameters, that are
79 * stored as task fields and copied to local variables and used in
80 * compute() methods, We pack these into as few lines as possible,
81 * and hoist consistency checks among them before main loops, to
82 * reduce distraction.
83 */
84
85 /**
86 * A placeholder task for Sorters, used for the lowest
87 * quartile task, that does not need to maintain array state.
88 */
89 static final class EmptyCompleter extends CountedCompleter<Void> {
90 @java.io.Serial
91 static final long serialVersionUID = 2446542900576103244L;
92 EmptyCompleter(CountedCompleter<?> p) { super(p); }
93 public final void compute() { }
94 }
95
96 /**
97 * A trigger for secondary merge of two merges
98 */
99 static final class Relay extends CountedCompleter<Void> {
100 @java.io.Serial
101 static final long serialVersionUID = 2446542900576103244L;
102 final CountedCompleter<?> task;
103 Relay(CountedCompleter<?> task) {
104 super(null, 1);
105 this.task = task;
106 }
107 public final void compute() { }
108 public final void onCompletion(CountedCompleter<?> t) {
109 task.compute();
110 }
111 }
112
113 /** Object + Comparator support class */
114 static final class FJObject {
115 static final class Sorter<T> extends CountedCompleter<Void> {
116 @java.io.Serial
117 static final long serialVersionUID = 2446542900576103244L;
118 final T[] a, w;
119 final int base, size, wbase, gran;
120 Comparator<? super T> comparator;
121 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
122 int wbase, int gran,
123 Comparator<? super T> comparator) {
124 super(par);
125 this.a = a; this.w = w; this.base = base; this.size = size;
126 this.wbase = wbase; this.gran = gran;
127 this.comparator = comparator;
128 }
129 public final void compute() {
130 CountedCompleter<?> s = this;
131 Comparator<? super T> c = this.comparator;
132 T[] a = this.a, w = this.w; // localize all params
133 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
134 while (n > g) {
135 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
136 Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
137 wb+h, n-h, b, g, c));
138 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
139 b+u, n-u, wb+h, g, c));
140 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
141 new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
142 Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
143 b+q, h-q, wb, g, c));
144 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
145 s = new EmptyCompleter(bc);
146 n = q;
147 }
148 TimSort.sort(a, b, b + n, c, w, wb, n);
149 s.tryComplete();
150 }
151 }
152
153 static final class Merger<T> extends CountedCompleter<Void> {
154 @java.io.Serial
155 static final long serialVersionUID = 2446542900576103244L;
156 final T[] a, w; // main and workspace arrays
157 final int lbase, lsize, rbase, rsize, wbase, gran;
158 Comparator<? super T> comparator;
159 Merger(CountedCompleter<?> par, T[] a, T[] w,
160 int lbase, int lsize, int rbase,
161 int rsize, int wbase, int gran,
162 Comparator<? super T> comparator) {
163 super(par);
164 this.a = a; this.w = w;
165 this.lbase = lbase; this.lsize = lsize;
166 this.rbase = rbase; this.rsize = rsize;
167 this.wbase = wbase; this.gran = gran;
168 this.comparator = comparator;
169 }
170
171 public final void compute() {
172 Comparator<? super T> c = this.comparator;
173 T[] a = this.a, w = this.w; // localize all params
174 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
220 }
221 else {
222 rb++; t = ar;
223 }
224 w[k++] = t;
225 }
226 if (rb < rf)
227 System.arraycopy(a, rb, w, k, rf - rb);
228 else if (lb < lf)
229 System.arraycopy(a, lb, w, k, lf - lb);
230
231 tryComplete();
232 }
233
234 }
235 } // FJObject
236
237 /** byte support class */
238 static final class FJByte {
239 static final class Sorter extends CountedCompleter<Void> {
240 @java.io.Serial
241 static final long serialVersionUID = 2446542900576103244L;
242 final byte[] a, w;
243 final int base, size, wbase, gran;
244 Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
245 int size, int wbase, int gran) {
246 super(par);
247 this.a = a; this.w = w; this.base = base; this.size = size;
248 this.wbase = wbase; this.gran = gran;
249 }
250 public final void compute() {
251 CountedCompleter<?> s = this;
252 byte[] a = this.a, w = this.w; // localize all params
253 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
254 while (n > g) {
255 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
256 Relay fc = new Relay(new Merger(s, w, a, wb, h,
257 wb+h, n-h, b, g));
258 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
259 b+u, n-u, wb+h, g));
260 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
261 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
262 Relay bc = new Relay(new Merger(fc, a, w, b, q,
263 b+q, h-q, wb, g));
264 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
265 s = new EmptyCompleter(bc);
266 n = q;
267 }
268 DualPivotQuicksort.sort(a, b, b + n - 1);
269 s.tryComplete();
270 }
271 }
272
273 static final class Merger extends CountedCompleter<Void> {
274 @java.io.Serial
275 static final long serialVersionUID = 2446542900576103244L;
276 final byte[] a, w; // main and workspace arrays
277 final int lbase, lsize, rbase, rsize, wbase, gran;
278 Merger(CountedCompleter<?> par, byte[] a, byte[] w,
279 int lbase, int lsize, int rbase,
280 int rsize, int wbase, int gran) {
281 super(par);
282 this.a = a; this.w = w;
283 this.lbase = lbase; this.lsize = lsize;
284 this.rbase = rbase; this.rsize = rsize;
285 this.wbase = wbase; this.gran = gran;
286 }
287
288 public final void compute() {
289 byte[] a = this.a, w = this.w; // localize all params
290 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
291 rn = this.rsize, k = this.wbase, g = this.gran;
292 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
293 throw new IllegalStateException(); // hoist checks
294 for (int lh, rh;;) { // split larger, find point in smaller
333 if ((al = a[lb]) <= (ar = a[rb])) {
334 lb++; t = al;
335 }
336 else {
337 rb++; t = ar;
338 }
339 w[k++] = t;
340 }
341 if (rb < rf)
342 System.arraycopy(a, rb, w, k, rf - rb);
343 else if (lb < lf)
344 System.arraycopy(a, lb, w, k, lf - lb);
345 tryComplete();
346 }
347 }
348 } // FJByte
349
350 /** char support class */
351 static final class FJChar {
352 static final class Sorter extends CountedCompleter<Void> {
353 @java.io.Serial
354 static final long serialVersionUID = 2446542900576103244L;
355 final char[] a, w;
356 final int base, size, wbase, gran;
357 Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
358 int size, int wbase, int gran) {
359 super(par);
360 this.a = a; this.w = w; this.base = base; this.size = size;
361 this.wbase = wbase; this.gran = gran;
362 }
363 public final void compute() {
364 CountedCompleter<?> s = this;
365 char[] a = this.a, w = this.w; // localize all params
366 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
367 while (n > g) {
368 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
369 Relay fc = new Relay(new Merger(s, w, a, wb, h,
370 wb+h, n-h, b, g));
371 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
372 b+u, n-u, wb+h, g));
373 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
374 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
375 Relay bc = new Relay(new Merger(fc, a, w, b, q,
376 b+q, h-q, wb, g));
377 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
378 s = new EmptyCompleter(bc);
379 n = q;
380 }
381 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
382 s.tryComplete();
383 }
384 }
385
386 static final class Merger extends CountedCompleter<Void> {
387 @java.io.Serial
388 static final long serialVersionUID = 2446542900576103244L;
389 final char[] a, w; // main and workspace arrays
390 final int lbase, lsize, rbase, rsize, wbase, gran;
391 Merger(CountedCompleter<?> par, char[] a, char[] w,
392 int lbase, int lsize, int rbase,
393 int rsize, int wbase, int gran) {
394 super(par);
395 this.a = a; this.w = w;
396 this.lbase = lbase; this.lsize = lsize;
397 this.rbase = rbase; this.rsize = rsize;
398 this.wbase = wbase; this.gran = gran;
399 }
400
401 public final void compute() {
402 char[] a = this.a, w = this.w; // localize all params
403 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
404 rn = this.rsize, k = this.wbase, g = this.gran;
405 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
406 throw new IllegalStateException(); // hoist checks
407 for (int lh, rh;;) { // split larger, find point in smaller
446 if ((al = a[lb]) <= (ar = a[rb])) {
447 lb++; t = al;
448 }
449 else {
450 rb++; t = ar;
451 }
452 w[k++] = t;
453 }
454 if (rb < rf)
455 System.arraycopy(a, rb, w, k, rf - rb);
456 else if (lb < lf)
457 System.arraycopy(a, lb, w, k, lf - lb);
458 tryComplete();
459 }
460 }
461 } // FJChar
462
463 /** short support class */
464 static final class FJShort {
465 static final class Sorter extends CountedCompleter<Void> {
466 @java.io.Serial
467 static final long serialVersionUID = 2446542900576103244L;
468 final short[] a, w;
469 final int base, size, wbase, gran;
470 Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
471 int size, int wbase, int gran) {
472 super(par);
473 this.a = a; this.w = w; this.base = base; this.size = size;
474 this.wbase = wbase; this.gran = gran;
475 }
476 public final void compute() {
477 CountedCompleter<?> s = this;
478 short[] a = this.a, w = this.w; // localize all params
479 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
480 while (n > g) {
481 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
482 Relay fc = new Relay(new Merger(s, w, a, wb, h,
483 wb+h, n-h, b, g));
484 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
485 b+u, n-u, wb+h, g));
486 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
487 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
488 Relay bc = new Relay(new Merger(fc, a, w, b, q,
489 b+q, h-q, wb, g));
490 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
491 s = new EmptyCompleter(bc);
492 n = q;
493 }
494 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
495 s.tryComplete();
496 }
497 }
498
499 static final class Merger extends CountedCompleter<Void> {
500 @java.io.Serial
501 static final long serialVersionUID = 2446542900576103244L;
502 final short[] a, w; // main and workspace arrays
503 final int lbase, lsize, rbase, rsize, wbase, gran;
504 Merger(CountedCompleter<?> par, short[] a, short[] w,
505 int lbase, int lsize, int rbase,
506 int rsize, int wbase, int gran) {
507 super(par);
508 this.a = a; this.w = w;
509 this.lbase = lbase; this.lsize = lsize;
510 this.rbase = rbase; this.rsize = rsize;
511 this.wbase = wbase; this.gran = gran;
512 }
513
514 public final void compute() {
515 short[] a = this.a, w = this.w; // localize all params
516 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
517 rn = this.rsize, k = this.wbase, g = this.gran;
518 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
519 throw new IllegalStateException(); // hoist checks
520 for (int lh, rh;;) { // split larger, find point in smaller
559 if ((al = a[lb]) <= (ar = a[rb])) {
560 lb++; t = al;
561 }
562 else {
563 rb++; t = ar;
564 }
565 w[k++] = t;
566 }
567 if (rb < rf)
568 System.arraycopy(a, rb, w, k, rf - rb);
569 else if (lb < lf)
570 System.arraycopy(a, lb, w, k, lf - lb);
571 tryComplete();
572 }
573 }
574 } // FJShort
575
576 /** int support class */
577 static final class FJInt {
578 static final class Sorter extends CountedCompleter<Void> {
579 @java.io.Serial
580 static final long serialVersionUID = 2446542900576103244L;
581 final int[] a, w;
582 final int base, size, wbase, gran;
583 Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
584 int size, int wbase, int gran) {
585 super(par);
586 this.a = a; this.w = w; this.base = base; this.size = size;
587 this.wbase = wbase; this.gran = gran;
588 }
589 public final void compute() {
590 CountedCompleter<?> s = this;
591 int[] a = this.a, w = this.w; // localize all params
592 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
593 while (n > g) {
594 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
595 Relay fc = new Relay(new Merger(s, w, a, wb, h,
596 wb+h, n-h, b, g));
597 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
598 b+u, n-u, wb+h, g));
599 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
600 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
601 Relay bc = new Relay(new Merger(fc, a, w, b, q,
602 b+q, h-q, wb, g));
603 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
604 s = new EmptyCompleter(bc);
605 n = q;
606 }
607 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
608 s.tryComplete();
609 }
610 }
611
612 static final class Merger extends CountedCompleter<Void> {
613 @java.io.Serial
614 static final long serialVersionUID = 2446542900576103244L;
615 final int[] a, w; // main and workspace arrays
616 final int lbase, lsize, rbase, rsize, wbase, gran;
617 Merger(CountedCompleter<?> par, int[] a, int[] w,
618 int lbase, int lsize, int rbase,
619 int rsize, int wbase, int gran) {
620 super(par);
621 this.a = a; this.w = w;
622 this.lbase = lbase; this.lsize = lsize;
623 this.rbase = rbase; this.rsize = rsize;
624 this.wbase = wbase; this.gran = gran;
625 }
626
627 public final void compute() {
628 int[] a = this.a, w = this.w; // localize all params
629 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
630 rn = this.rsize, k = this.wbase, g = this.gran;
631 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
632 throw new IllegalStateException(); // hoist checks
633 for (int lh, rh;;) { // split larger, find point in smaller
672 if ((al = a[lb]) <= (ar = a[rb])) {
673 lb++; t = al;
674 }
675 else {
676 rb++; t = ar;
677 }
678 w[k++] = t;
679 }
680 if (rb < rf)
681 System.arraycopy(a, rb, w, k, rf - rb);
682 else if (lb < lf)
683 System.arraycopy(a, lb, w, k, lf - lb);
684 tryComplete();
685 }
686 }
687 } // FJInt
688
689 /** long support class */
690 static final class FJLong {
691 static final class Sorter extends CountedCompleter<Void> {
692 @java.io.Serial
693 static final long serialVersionUID = 2446542900576103244L;
694 final long[] a, w;
695 final int base, size, wbase, gran;
696 Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
697 int size, int wbase, int gran) {
698 super(par);
699 this.a = a; this.w = w; this.base = base; this.size = size;
700 this.wbase = wbase; this.gran = gran;
701 }
702 public final void compute() {
703 CountedCompleter<?> s = this;
704 long[] a = this.a, w = this.w; // localize all params
705 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
706 while (n > g) {
707 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
708 Relay fc = new Relay(new Merger(s, w, a, wb, h,
709 wb+h, n-h, b, g));
710 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
711 b+u, n-u, wb+h, g));
712 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
713 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
714 Relay bc = new Relay(new Merger(fc, a, w, b, q,
715 b+q, h-q, wb, g));
716 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
717 s = new EmptyCompleter(bc);
718 n = q;
719 }
720 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
721 s.tryComplete();
722 }
723 }
724
725 static final class Merger extends CountedCompleter<Void> {
726 @java.io.Serial
727 static final long serialVersionUID = 2446542900576103244L;
728 final long[] a, w; // main and workspace arrays
729 final int lbase, lsize, rbase, rsize, wbase, gran;
730 Merger(CountedCompleter<?> par, long[] a, long[] w,
731 int lbase, int lsize, int rbase,
732 int rsize, int wbase, int gran) {
733 super(par);
734 this.a = a; this.w = w;
735 this.lbase = lbase; this.lsize = lsize;
736 this.rbase = rbase; this.rsize = rsize;
737 this.wbase = wbase; this.gran = gran;
738 }
739
740 public final void compute() {
741 long[] a = this.a, w = this.w; // localize all params
742 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
743 rn = this.rsize, k = this.wbase, g = this.gran;
744 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
745 throw new IllegalStateException(); // hoist checks
746 for (int lh, rh;;) { // split larger, find point in smaller
785 if ((al = a[lb]) <= (ar = a[rb])) {
786 lb++; t = al;
787 }
788 else {
789 rb++; t = ar;
790 }
791 w[k++] = t;
792 }
793 if (rb < rf)
794 System.arraycopy(a, rb, w, k, rf - rb);
795 else if (lb < lf)
796 System.arraycopy(a, lb, w, k, lf - lb);
797 tryComplete();
798 }
799 }
800 } // FJLong
801
802 /** float support class */
803 static final class FJFloat {
804 static final class Sorter extends CountedCompleter<Void> {
805 @java.io.Serial
806 static final long serialVersionUID = 2446542900576103244L;
807 final float[] a, w;
808 final int base, size, wbase, gran;
809 Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
810 int size, int wbase, int gran) {
811 super(par);
812 this.a = a; this.w = w; this.base = base; this.size = size;
813 this.wbase = wbase; this.gran = gran;
814 }
815 public final void compute() {
816 CountedCompleter<?> s = this;
817 float[] a = this.a, w = this.w; // localize all params
818 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
819 while (n > g) {
820 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
821 Relay fc = new Relay(new Merger(s, w, a, wb, h,
822 wb+h, n-h, b, g));
823 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
824 b+u, n-u, wb+h, g));
825 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
826 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
827 Relay bc = new Relay(new Merger(fc, a, w, b, q,
828 b+q, h-q, wb, g));
829 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
830 s = new EmptyCompleter(bc);
831 n = q;
832 }
833 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
834 s.tryComplete();
835 }
836 }
837
838 static final class Merger extends CountedCompleter<Void> {
839 @java.io.Serial
840 static final long serialVersionUID = 2446542900576103244L;
841 final float[] a, w; // main and workspace arrays
842 final int lbase, lsize, rbase, rsize, wbase, gran;
843 Merger(CountedCompleter<?> par, float[] a, float[] w,
844 int lbase, int lsize, int rbase,
845 int rsize, int wbase, int gran) {
846 super(par);
847 this.a = a; this.w = w;
848 this.lbase = lbase; this.lsize = lsize;
849 this.rbase = rbase; this.rsize = rsize;
850 this.wbase = wbase; this.gran = gran;
851 }
852
853 public final void compute() {
854 float[] a = this.a, w = this.w; // localize all params
855 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
856 rn = this.rsize, k = this.wbase, g = this.gran;
857 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
858 throw new IllegalStateException(); // hoist checks
859 for (int lh, rh;;) { // split larger, find point in smaller
898 if ((al = a[lb]) <= (ar = a[rb])) {
899 lb++; t = al;
900 }
901 else {
902 rb++; t = ar;
903 }
904 w[k++] = t;
905 }
906 if (rb < rf)
907 System.arraycopy(a, rb, w, k, rf - rb);
908 else if (lb < lf)
909 System.arraycopy(a, lb, w, k, lf - lb);
910 tryComplete();
911 }
912 }
913 } // FJFloat
914
915 /** double support class */
916 static final class FJDouble {
917 static final class Sorter extends CountedCompleter<Void> {
918 @java.io.Serial
919 static final long serialVersionUID = 2446542900576103244L;
920 final double[] a, w;
921 final int base, size, wbase, gran;
922 Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
923 int size, int wbase, int gran) {
924 super(par);
925 this.a = a; this.w = w; this.base = base; this.size = size;
926 this.wbase = wbase; this.gran = gran;
927 }
928 public final void compute() {
929 CountedCompleter<?> s = this;
930 double[] a = this.a, w = this.w; // localize all params
931 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
932 while (n > g) {
933 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
934 Relay fc = new Relay(new Merger(s, w, a, wb, h,
935 wb+h, n-h, b, g));
936 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
937 b+u, n-u, wb+h, g));
938 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
939 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
940 Relay bc = new Relay(new Merger(fc, a, w, b, q,
941 b+q, h-q, wb, g));
942 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
943 s = new EmptyCompleter(bc);
944 n = q;
945 }
946 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
947 s.tryComplete();
948 }
949 }
950
951 static final class Merger extends CountedCompleter<Void> {
952 @java.io.Serial
953 static final long serialVersionUID = 2446542900576103244L;
954 final double[] a, w; // main and workspace arrays
955 final int lbase, lsize, rbase, rsize, wbase, gran;
956 Merger(CountedCompleter<?> par, double[] a, double[] w,
957 int lbase, int lsize, int rbase,
958 int rsize, int wbase, int gran) {
959 super(par);
960 this.a = a; this.w = w;
961 this.lbase = lbase; this.lsize = lsize;
962 this.rbase = rbase; this.rsize = rsize;
963 this.wbase = wbase; this.gran = gran;
964 }
965
966 public final void compute() {
967 double[] a = this.a, w = this.w; // localize all params
968 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
969 rn = this.rsize, k = this.wbase, g = this.gran;
970 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
971 throw new IllegalStateException(); // hoist checks
972 for (int lh, rh;;) { // split larger, find point in smaller
|