1 /*
2 * Copyright (c) 2012, 2019, 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 import java.util.concurrent.CountedCompleter;
29
30 /**
31 * Helper utilities for the parallel sort methods in Arrays.parallelSort.
32 *
33 * For each primitive type, plus Object, we define a static class to
34 * contain the Sorter and Merger implementations for that type:
35 *
36 * Sorter classes based mainly on CilkSort
37 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
38 * Basic algorithm:
39 * if array size is small, just use a sequential quicksort (via Arrays.sort)
40 * Otherwise:
41 * 1. Break array in half.
42 * 2. For each half,
43 * a. break the half in half (i.e., quarters),
44 * b. sort the quarters
45 * c. merge them together
46 * 3. merge together the two halves.
47 *
48 * One reason for splitting in quarters is that this guarantees that
49 * the final sort is in the main array, not the workspace array.
50 * (workspace and main swap roles on each subsort step.) Leaf-level
51 * sorts use the associated sequential sort.
52 *
53 * Merger classes perform merging for Sorter. They are structured
54 * such that if the underlying sort is stable (as is true for
55 * TimSort), then so is the full sort. If big enough, they split the
56 * largest of the two partitions in half, find the greatest point in
57 * smaller partition less than the beginning of the second half of
58 * larger via binary search; and then merge in parallel the two
59 * partitions. In part to ensure tasks are triggered in
60 * stability-preserving order, the current CountedCompleter design
61 * requires some little tasks to serve as place holders for triggering
62 * completion tasks. These classes (EmptyCompleter and Relay) don't
63 * need to keep track of the arrays, and are never themselves forked,
64 * so don't hold any task state.
65 *
66 * The primitive class versions (FJByte... FJDouble) are
67 * identical to each other except for type declarations.
68 *
69 * The base sequential sorts rely on non-public versions of TimSort,
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 @SuppressWarnings("serial") // Not statically typed as Serializable
119 final T[] a;
120 @SuppressWarnings("serial") // Not statically typed as Serializable
121 final T[] w;
122 final int base, size, wbase, gran;
123 @SuppressWarnings("serial") // Not statically typed as Serializable
124 Comparator<? super T> comparator;
125 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
126 int wbase, int gran,
127 Comparator<? super T> comparator) {
128 super(par);
129 this.a = a; this.w = w; this.base = base; this.size = size;
130 this.wbase = wbase; this.gran = gran;
131 this.comparator = comparator;
132 }
133 public final void compute() {
134 CountedCompleter<?> s = this;
135 Comparator<? super T> c = this.comparator;
136 T[] a = this.a, w = this.w; // localize all params
137 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
138 while (n > g) {
139 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
140 Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
141 wb+h, n-h, b, g, c));
142 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
143 b+u, n-u, wb+h, g, c));
144 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
145 new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
146 Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
147 b+q, h-q, wb, g, c));
148 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
149 s = new EmptyCompleter(bc);
150 n = q;
151 }
152 TimSort.sort(a, b, b + n, c, w, wb, n);
153 s.tryComplete();
154 }
155 }
156
157 static final class Merger<T> extends CountedCompleter<Void> {
158 @java.io.Serial
159 static final long serialVersionUID = 2446542900576103244L;
160 // main and workspace arrays
161 @SuppressWarnings("serial") // Not statically typed as Serializable
162 final T[] a;
163 @SuppressWarnings("serial") // Not statically typed as Serializable
164 final T[] w;
165 final int lbase, lsize, rbase, rsize, wbase, gran;
166 @SuppressWarnings("serial") // Not statically typed as Serializable
167 Comparator<? super T> comparator;
168 Merger(CountedCompleter<?> par, T[] a, T[] w,
169 int lbase, int lsize, int rbase,
170 int rsize, int wbase, int gran,
171 Comparator<? super T> comparator) {
172 super(par);
173 this.a = a; this.w = w;
174 this.lbase = lbase; this.lsize = lsize;
175 this.rbase = rbase; this.rsize = rsize;
176 this.wbase = wbase; this.gran = gran;
177 this.comparator = comparator;
178 }
179
180 public final void compute() {
181 Comparator<? super T> c = this.comparator;
182 T[] a = this.a, w = this.w; // localize all params
183 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
184 rn = this.rsize, k = this.wbase, g = this.gran;
185 if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
186 c == null)
187 throw new IllegalStateException(); // hoist checks
188 for (int lh, rh;;) { // split larger, find point in smaller
189 if (ln >= rn) {
190 if (ln <= g)
191 break;
192 rh = rn;
193 T split = a[(lh = ln >>> 1) + lb];
194 for (int lo = 0; lo < rh; ) {
195 int rm = (lo + rh) >>> 1;
196 if (c.compare(split, a[rm + rb]) <= 0)
197 rh = rm;
198 else
199 lo = rm + 1;
200 }
201 }
202 else {
203 if (rn <= g)
204 break;
205 lh = ln;
206 T split = a[(rh = rn >>> 1) + rb];
207 for (int lo = 0; lo < lh; ) {
208 int lm = (lo + lh) >>> 1;
209 if (c.compare(split, a[lm + lb]) <= 0)
210 lh = lm;
211 else
212 lo = lm + 1;
213 }
214 }
215 Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh,
216 rb + rh, rn - rh,
217 k + lh + rh, g, c);
218 rn = rh;
219 ln = lh;
220 addToPendingCount(1);
221 m.fork();
222 }
223
224 int lf = lb + ln, rf = rb + rn; // index bounds
225 while (lb < lf && rb < rf) {
226 T t, al, ar;
227 if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
228 lb++; t = al;
229 }
230 else {
231 rb++; t = ar;
232 }
233 w[k++] = t;
234 }
235 if (rb < rf)
236 System.arraycopy(a, rb, w, k, rf - rb);
237 else if (lb < lf)
238 System.arraycopy(a, lb, w, k, lf - lb);
239
240 tryComplete();
241 }
242
243 }
244 } // FJObject
245
246 /** byte support class */
247 static final class FJByte {
248 static final class Sorter extends CountedCompleter<Void> {
249 @java.io.Serial
250 static final long serialVersionUID = 2446542900576103244L;
251 final byte[] a, w;
252 final int base, size, wbase, gran;
253 Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
254 int size, int wbase, int gran) {
255 super(par);
256 this.a = a; this.w = w; this.base = base; this.size = size;
257 this.wbase = wbase; this.gran = gran;
258 }
259 public final void compute() {
260 CountedCompleter<?> s = this;
261 byte[] a = this.a, w = this.w; // localize all params
262 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
263 while (n > g) {
264 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
265 Relay fc = new Relay(new Merger(s, w, a, wb, h,
266 wb+h, n-h, b, g));
267 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
268 b+u, n-u, wb+h, g));
269 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
270 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
271 Relay bc = new Relay(new Merger(fc, a, w, b, q,
272 b+q, h-q, wb, g));
273 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
274 s = new EmptyCompleter(bc);
275 n = q;
276 }
277 DualPivotQuicksort.sort(a, b, b + n - 1);
278 s.tryComplete();
279 }
280 }
281
282 static final class Merger extends CountedCompleter<Void> {
283 @java.io.Serial
284 static final long serialVersionUID = 2446542900576103244L;
285 // main and workspace arrays
286 final byte[] a, w;
287 final int lbase, lsize, rbase, rsize, wbase, gran;
288 Merger(CountedCompleter<?> par, byte[] a, byte[] w,
289 int lbase, int lsize, int rbase,
290 int rsize, int wbase, int gran) {
291 super(par);
292 this.a = a; this.w = w;
293 this.lbase = lbase; this.lsize = lsize;
294 this.rbase = rbase; this.rsize = rsize;
295 this.wbase = wbase; this.gran = gran;
296 }
297
298 public final void compute() {
299 byte[] a = this.a, w = this.w; // localize all params
300 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
301 rn = this.rsize, k = this.wbase, g = this.gran;
302 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
303 throw new IllegalStateException(); // hoist checks
304 for (int lh, rh;;) { // split larger, find point in smaller
305 if (ln >= rn) {
306 if (ln <= g)
307 break;
308 rh = rn;
309 byte split = a[(lh = ln >>> 1) + lb];
310 for (int lo = 0; lo < rh; ) {
311 int rm = (lo + rh) >>> 1;
312 if (split <= a[rm + rb])
313 rh = rm;
314 else
315 lo = rm + 1;
316 }
317 }
318 else {
319 if (rn <= g)
320 break;
321 lh = ln;
322 byte split = a[(rh = rn >>> 1) + rb];
323 for (int lo = 0; lo < lh; ) {
324 int lm = (lo + lh) >>> 1;
325 if (split <= a[lm + lb])
326 lh = lm;
327 else
328 lo = lm + 1;
329 }
330 }
331 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
332 rb + rh, rn - rh,
333 k + lh + rh, g);
334 rn = rh;
335 ln = lh;
336 addToPendingCount(1);
337 m.fork();
338 }
339
340 int lf = lb + ln, rf = rb + rn; // index bounds
341 while (lb < lf && rb < rf) {
342 byte t, al, ar;
343 if ((al = a[lb]) <= (ar = a[rb])) {
344 lb++; t = al;
345 }
346 else {
347 rb++; t = ar;
348 }
349 w[k++] = t;
350 }
351 if (rb < rf)
352 System.arraycopy(a, rb, w, k, rf - rb);
353 else if (lb < lf)
354 System.arraycopy(a, lb, w, k, lf - lb);
355 tryComplete();
356 }
357 }
358 } // FJByte
359
360 /** char support class */
361 static final class FJChar {
362 static final class Sorter extends CountedCompleter<Void> {
363 @java.io.Serial
364 static final long serialVersionUID = 2446542900576103244L;
365 final char[] a, w;
366 final int base, size, wbase, gran;
367 Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
368 int size, int wbase, int gran) {
369 super(par);
370 this.a = a; this.w = w; this.base = base; this.size = size;
371 this.wbase = wbase; this.gran = gran;
372 }
373 public final void compute() {
374 CountedCompleter<?> s = this;
375 char[] a = this.a, w = this.w; // localize all params
376 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
377 while (n > g) {
378 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
379 Relay fc = new Relay(new Merger(s, w, a, wb, h,
380 wb+h, n-h, b, g));
381 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
382 b+u, n-u, wb+h, g));
383 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
384 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
385 Relay bc = new Relay(new Merger(fc, a, w, b, q,
386 b+q, h-q, wb, g));
387 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
388 s = new EmptyCompleter(bc);
389 n = q;
390 }
391 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
392 s.tryComplete();
393 }
394 }
395
396 static final class Merger extends CountedCompleter<Void> {
397 @java.io.Serial
398 static final long serialVersionUID = 2446542900576103244L;
399 final char[] a, w; // main and workspace arrays
400 final int lbase, lsize, rbase, rsize, wbase, gran;
401 Merger(CountedCompleter<?> par, char[] a, char[] w,
402 int lbase, int lsize, int rbase,
403 int rsize, int wbase, int gran) {
404 super(par);
405 this.a = a; this.w = w;
406 this.lbase = lbase; this.lsize = lsize;
407 this.rbase = rbase; this.rsize = rsize;
408 this.wbase = wbase; this.gran = gran;
409 }
410
411 public final void compute() {
412 char[] a = this.a, w = this.w; // localize all params
413 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
414 rn = this.rsize, k = this.wbase, g = this.gran;
415 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
416 throw new IllegalStateException(); // hoist checks
417 for (int lh, rh;;) { // split larger, find point in smaller
418 if (ln >= rn) {
419 if (ln <= g)
420 break;
421 rh = rn;
422 char split = a[(lh = ln >>> 1) + lb];
423 for (int lo = 0; lo < rh; ) {
424 int rm = (lo + rh) >>> 1;
425 if (split <= a[rm + rb])
426 rh = rm;
427 else
428 lo = rm + 1;
429 }
430 }
431 else {
432 if (rn <= g)
433 break;
434 lh = ln;
435 char split = a[(rh = rn >>> 1) + rb];
436 for (int lo = 0; lo < lh; ) {
437 int lm = (lo + lh) >>> 1;
438 if (split <= a[lm + lb])
439 lh = lm;
440 else
441 lo = lm + 1;
442 }
443 }
444 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
445 rb + rh, rn - rh,
446 k + lh + rh, g);
447 rn = rh;
448 ln = lh;
449 addToPendingCount(1);
450 m.fork();
451 }
452
453 int lf = lb + ln, rf = rb + rn; // index bounds
454 while (lb < lf && rb < rf) {
455 char t, al, ar;
456 if ((al = a[lb]) <= (ar = a[rb])) {
457 lb++; t = al;
458 }
459 else {
460 rb++; t = ar;
461 }
462 w[k++] = t;
463 }
464 if (rb < rf)
465 System.arraycopy(a, rb, w, k, rf - rb);
466 else if (lb < lf)
467 System.arraycopy(a, lb, w, k, lf - lb);
468 tryComplete();
469 }
470 }
471 } // FJChar
472
473 /** short support class */
474 static final class FJShort {
475 static final class Sorter extends CountedCompleter<Void> {
476 @java.io.Serial
477 static final long serialVersionUID = 2446542900576103244L;
478 final short[] a, w;
479 final int base, size, wbase, gran;
480 Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
481 int size, int wbase, int gran) {
482 super(par);
483 this.a = a; this.w = w; this.base = base; this.size = size;
484 this.wbase = wbase; this.gran = gran;
485 }
486 public final void compute() {
487 CountedCompleter<?> s = this;
488 short[] a = this.a, w = this.w; // localize all params
489 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
490 while (n > g) {
491 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
492 Relay fc = new Relay(new Merger(s, w, a, wb, h,
493 wb+h, n-h, b, g));
494 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
495 b+u, n-u, wb+h, g));
496 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
497 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
498 Relay bc = new Relay(new Merger(fc, a, w, b, q,
499 b+q, h-q, wb, g));
500 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
501 s = new EmptyCompleter(bc);
502 n = q;
503 }
504 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
505 s.tryComplete();
506 }
507 }
508
509 static final class Merger extends CountedCompleter<Void> {
510 @java.io.Serial
511 static final long serialVersionUID = 2446542900576103244L;
512 final short[] a, w; // main and workspace arrays
513 final int lbase, lsize, rbase, rsize, wbase, gran;
514 Merger(CountedCompleter<?> par, short[] a, short[] w,
515 int lbase, int lsize, int rbase,
516 int rsize, int wbase, int gran) {
517 super(par);
518 this.a = a; this.w = w;
519 this.lbase = lbase; this.lsize = lsize;
520 this.rbase = rbase; this.rsize = rsize;
521 this.wbase = wbase; this.gran = gran;
522 }
523
524 public final void compute() {
525 short[] a = this.a, w = this.w; // localize all params
526 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
527 rn = this.rsize, k = this.wbase, g = this.gran;
528 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
529 throw new IllegalStateException(); // hoist checks
530 for (int lh, rh;;) { // split larger, find point in smaller
531 if (ln >= rn) {
532 if (ln <= g)
533 break;
534 rh = rn;
535 short split = a[(lh = ln >>> 1) + lb];
536 for (int lo = 0; lo < rh; ) {
537 int rm = (lo + rh) >>> 1;
538 if (split <= a[rm + rb])
539 rh = rm;
540 else
541 lo = rm + 1;
542 }
543 }
544 else {
545 if (rn <= g)
546 break;
547 lh = ln;
548 short split = a[(rh = rn >>> 1) + rb];
549 for (int lo = 0; lo < lh; ) {
550 int lm = (lo + lh) >>> 1;
551 if (split <= a[lm + lb])
552 lh = lm;
553 else
554 lo = lm + 1;
555 }
556 }
557 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
558 rb + rh, rn - rh,
559 k + lh + rh, g);
560 rn = rh;
561 ln = lh;
562 addToPendingCount(1);
563 m.fork();
564 }
565
566 int lf = lb + ln, rf = rb + rn; // index bounds
567 while (lb < lf && rb < rf) {
568 short t, al, ar;
569 if ((al = a[lb]) <= (ar = a[rb])) {
570 lb++; t = al;
571 }
572 else {
573 rb++; t = ar;
574 }
575 w[k++] = t;
576 }
577 if (rb < rf)
578 System.arraycopy(a, rb, w, k, rf - rb);
579 else if (lb < lf)
580 System.arraycopy(a, lb, w, k, lf - lb);
581 tryComplete();
582 }
583 }
584 } // FJShort
585
586 /** int support class */
587 static final class FJInt {
588 static final class Sorter extends CountedCompleter<Void> {
589 @java.io.Serial
590 static final long serialVersionUID = 2446542900576103244L;
591 final int[] a, w;
592 final int base, size, wbase, gran;
593 Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
594 int size, int wbase, int gran) {
595 super(par);
596 this.a = a; this.w = w; this.base = base; this.size = size;
597 this.wbase = wbase; this.gran = gran;
598 }
599 public final void compute() {
600 CountedCompleter<?> s = this;
601 int[] a = this.a, w = this.w; // localize all params
602 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
603 while (n > g) {
604 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
605 Relay fc = new Relay(new Merger(s, w, a, wb, h,
606 wb+h, n-h, b, g));
607 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
608 b+u, n-u, wb+h, g));
609 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
610 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
611 Relay bc = new Relay(new Merger(fc, a, w, b, q,
612 b+q, h-q, wb, g));
613 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
614 s = new EmptyCompleter(bc);
615 n = q;
616 }
617 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
618 s.tryComplete();
619 }
620 }
621
622 static final class Merger extends CountedCompleter<Void> {
623 @java.io.Serial
624 static final long serialVersionUID = 2446542900576103244L;
625 final int[] a, w; // main and workspace arrays
626 final int lbase, lsize, rbase, rsize, wbase, gran;
627 Merger(CountedCompleter<?> par, int[] a, int[] w,
628 int lbase, int lsize, int rbase,
629 int rsize, int wbase, int gran) {
630 super(par);
631 this.a = a; this.w = w;
632 this.lbase = lbase; this.lsize = lsize;
633 this.rbase = rbase; this.rsize = rsize;
634 this.wbase = wbase; this.gran = gran;
635 }
636
637 public final void compute() {
638 int[] a = this.a, w = this.w; // localize all params
639 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
640 rn = this.rsize, k = this.wbase, g = this.gran;
641 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
642 throw new IllegalStateException(); // hoist checks
643 for (int lh, rh;;) { // split larger, find point in smaller
644 if (ln >= rn) {
645 if (ln <= g)
646 break;
647 rh = rn;
648 int split = a[(lh = ln >>> 1) + lb];
649 for (int lo = 0; lo < rh; ) {
650 int rm = (lo + rh) >>> 1;
651 if (split <= a[rm + rb])
652 rh = rm;
653 else
654 lo = rm + 1;
655 }
656 }
657 else {
658 if (rn <= g)
659 break;
660 lh = ln;
661 int split = a[(rh = rn >>> 1) + rb];
662 for (int lo = 0; lo < lh; ) {
663 int lm = (lo + lh) >>> 1;
664 if (split <= a[lm + lb])
665 lh = lm;
666 else
667 lo = lm + 1;
668 }
669 }
670 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
671 rb + rh, rn - rh,
672 k + lh + rh, g);
673 rn = rh;
674 ln = lh;
675 addToPendingCount(1);
676 m.fork();
677 }
678
679 int lf = lb + ln, rf = rb + rn; // index bounds
680 while (lb < lf && rb < rf) {
681 int t, al, ar;
682 if ((al = a[lb]) <= (ar = a[rb])) {
683 lb++; t = al;
684 }
685 else {
686 rb++; t = ar;
687 }
688 w[k++] = t;
689 }
690 if (rb < rf)
691 System.arraycopy(a, rb, w, k, rf - rb);
692 else if (lb < lf)
693 System.arraycopy(a, lb, w, k, lf - lb);
694 tryComplete();
695 }
696 }
697 } // FJInt
698
699 /** long support class */
700 static final class FJLong {
701 static final class Sorter extends CountedCompleter<Void> {
702 @java.io.Serial
703 static final long serialVersionUID = 2446542900576103244L;
704 final long[] a, w;
705 final int base, size, wbase, gran;
706 Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
707 int size, int wbase, int gran) {
708 super(par);
709 this.a = a; this.w = w; this.base = base; this.size = size;
710 this.wbase = wbase; this.gran = gran;
711 }
712 public final void compute() {
713 CountedCompleter<?> s = this;
714 long[] a = this.a, w = this.w; // localize all params
715 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
716 while (n > g) {
717 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
718 Relay fc = new Relay(new Merger(s, w, a, wb, h,
719 wb+h, n-h, b, g));
720 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
721 b+u, n-u, wb+h, g));
722 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
723 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
724 Relay bc = new Relay(new Merger(fc, a, w, b, q,
725 b+q, h-q, wb, g));
726 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
727 s = new EmptyCompleter(bc);
728 n = q;
729 }
730 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
731 s.tryComplete();
732 }
733 }
734
735 static final class Merger extends CountedCompleter<Void> {
736 @java.io.Serial
737 static final long serialVersionUID = 2446542900576103244L;
738 final long[] a, w; // main and workspace arrays
739 final int lbase, lsize, rbase, rsize, wbase, gran;
740 Merger(CountedCompleter<?> par, long[] a, long[] w,
741 int lbase, int lsize, int rbase,
742 int rsize, int wbase, int gran) {
743 super(par);
744 this.a = a; this.w = w;
745 this.lbase = lbase; this.lsize = lsize;
746 this.rbase = rbase; this.rsize = rsize;
747 this.wbase = wbase; this.gran = gran;
748 }
749
750 public final void compute() {
751 long[] a = this.a, w = this.w; // localize all params
752 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
753 rn = this.rsize, k = this.wbase, g = this.gran;
754 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
755 throw new IllegalStateException(); // hoist checks
756 for (int lh, rh;;) { // split larger, find point in smaller
757 if (ln >= rn) {
758 if (ln <= g)
759 break;
760 rh = rn;
761 long split = a[(lh = ln >>> 1) + lb];
762 for (int lo = 0; lo < rh; ) {
763 int rm = (lo + rh) >>> 1;
764 if (split <= a[rm + rb])
765 rh = rm;
766 else
767 lo = rm + 1;
768 }
769 }
770 else {
771 if (rn <= g)
772 break;
773 lh = ln;
774 long split = a[(rh = rn >>> 1) + rb];
775 for (int lo = 0; lo < lh; ) {
776 int lm = (lo + lh) >>> 1;
777 if (split <= a[lm + lb])
778 lh = lm;
779 else
780 lo = lm + 1;
781 }
782 }
783 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
784 rb + rh, rn - rh,
785 k + lh + rh, g);
786 rn = rh;
787 ln = lh;
788 addToPendingCount(1);
789 m.fork();
790 }
791
792 int lf = lb + ln, rf = rb + rn; // index bounds
793 while (lb < lf && rb < rf) {
794 long t, al, ar;
795 if ((al = a[lb]) <= (ar = a[rb])) {
796 lb++; t = al;
797 }
798 else {
799 rb++; t = ar;
800 }
801 w[k++] = t;
802 }
803 if (rb < rf)
804 System.arraycopy(a, rb, w, k, rf - rb);
805 else if (lb < lf)
806 System.arraycopy(a, lb, w, k, lf - lb);
807 tryComplete();
808 }
809 }
810 } // FJLong
811
812 /** float support class */
813 static final class FJFloat {
814 static final class Sorter extends CountedCompleter<Void> {
815 @java.io.Serial
816 static final long serialVersionUID = 2446542900576103244L;
817 final float[] a, w;
818 final int base, size, wbase, gran;
819 Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
820 int size, int wbase, int gran) {
821 super(par);
822 this.a = a; this.w = w; this.base = base; this.size = size;
823 this.wbase = wbase; this.gran = gran;
824 }
825 public final void compute() {
826 CountedCompleter<?> s = this;
827 float[] a = this.a, w = this.w; // localize all params
828 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
829 while (n > g) {
830 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
831 Relay fc = new Relay(new Merger(s, w, a, wb, h,
832 wb+h, n-h, b, g));
833 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
834 b+u, n-u, wb+h, g));
835 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
836 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
837 Relay bc = new Relay(new Merger(fc, a, w, b, q,
838 b+q, h-q, wb, g));
839 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
840 s = new EmptyCompleter(bc);
841 n = q;
842 }
843 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
844 s.tryComplete();
845 }
846 }
847
848 static final class Merger extends CountedCompleter<Void> {
849 @java.io.Serial
850 static final long serialVersionUID = 2446542900576103244L;
851 final float[] a, w; // main and workspace arrays
852 final int lbase, lsize, rbase, rsize, wbase, gran;
853 Merger(CountedCompleter<?> par, float[] a, float[] w,
854 int lbase, int lsize, int rbase,
855 int rsize, int wbase, int gran) {
856 super(par);
857 this.a = a; this.w = w;
858 this.lbase = lbase; this.lsize = lsize;
859 this.rbase = rbase; this.rsize = rsize;
860 this.wbase = wbase; this.gran = gran;
861 }
862
863 public final void compute() {
864 float[] a = this.a, w = this.w; // localize all params
865 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
866 rn = this.rsize, k = this.wbase, g = this.gran;
867 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
868 throw new IllegalStateException(); // hoist checks
869 for (int lh, rh;;) { // split larger, find point in smaller
870 if (ln >= rn) {
871 if (ln <= g)
872 break;
873 rh = rn;
874 float split = a[(lh = ln >>> 1) + lb];
875 for (int lo = 0; lo < rh; ) {
876 int rm = (lo + rh) >>> 1;
877 if (split <= a[rm + rb])
878 rh = rm;
879 else
880 lo = rm + 1;
881 }
882 }
883 else {
884 if (rn <= g)
885 break;
886 lh = ln;
887 float split = a[(rh = rn >>> 1) + rb];
888 for (int lo = 0; lo < lh; ) {
889 int lm = (lo + lh) >>> 1;
890 if (split <= a[lm + lb])
891 lh = lm;
892 else
893 lo = lm + 1;
894 }
895 }
896 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
897 rb + rh, rn - rh,
898 k + lh + rh, g);
899 rn = rh;
900 ln = lh;
901 addToPendingCount(1);
902 m.fork();
903 }
904
905 int lf = lb + ln, rf = rb + rn; // index bounds
906 while (lb < lf && rb < rf) {
907 float t, al, ar;
908 if ((al = a[lb]) <= (ar = a[rb])) {
909 lb++; t = al;
910 }
911 else {
912 rb++; t = ar;
913 }
914 w[k++] = t;
915 }
916 if (rb < rf)
917 System.arraycopy(a, rb, w, k, rf - rb);
918 else if (lb < lf)
919 System.arraycopy(a, lb, w, k, lf - lb);
920 tryComplete();
921 }
922 }
923 } // FJFloat
924
925 /** double support class */
926 static final class FJDouble {
927 static final class Sorter extends CountedCompleter<Void> {
928 @java.io.Serial
929 static final long serialVersionUID = 2446542900576103244L;
930 final double[] a, w;
931 final int base, size, wbase, gran;
932 Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
933 int size, int wbase, int gran) {
934 super(par);
935 this.a = a; this.w = w; this.base = base; this.size = size;
936 this.wbase = wbase; this.gran = gran;
937 }
938 public final void compute() {
939 CountedCompleter<?> s = this;
940 double[] a = this.a, w = this.w; // localize all params
941 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
942 while (n > g) {
943 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
944 Relay fc = new Relay(new Merger(s, w, a, wb, h,
945 wb+h, n-h, b, g));
946 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
947 b+u, n-u, wb+h, g));
948 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
949 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
950 Relay bc = new Relay(new Merger(fc, a, w, b, q,
951 b+q, h-q, wb, g));
952 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
953 s = new EmptyCompleter(bc);
954 n = q;
955 }
956 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
957 s.tryComplete();
958 }
959 }
960
961 static final class Merger extends CountedCompleter<Void> {
962 @java.io.Serial
963 static final long serialVersionUID = 2446542900576103244L;
964 final double[] a, w; // main and workspace arrays
965 final int lbase, lsize, rbase, rsize, wbase, gran;
966 Merger(CountedCompleter<?> par, double[] a, double[] w,
967 int lbase, int lsize, int rbase,
968 int rsize, int wbase, int gran) {
969 super(par);
970 this.a = a; this.w = w;
971 this.lbase = lbase; this.lsize = lsize;
972 this.rbase = rbase; this.rsize = rsize;
973 this.wbase = wbase; this.gran = gran;
974 }
975
976 public final void compute() {
977 double[] a = this.a, w = this.w; // localize all params
978 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
979 rn = this.rsize, k = this.wbase, g = this.gran;
980 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
981 throw new IllegalStateException(); // hoist checks
982 for (int lh, rh;;) { // split larger, find point in smaller
983 if (ln >= rn) {
984 if (ln <= g)
985 break;
986 rh = rn;
987 double split = a[(lh = ln >>> 1) + lb];
988 for (int lo = 0; lo < rh; ) {
989 int rm = (lo + rh) >>> 1;
990 if (split <= a[rm + rb])
991 rh = rm;
992 else
993 lo = rm + 1;
994 }
995 }
996 else {
997 if (rn <= g)
998 break;
999 lh = ln;
1000 double split = a[(rh = rn >>> 1) + rb];
1001 for (int lo = 0; lo < lh; ) {
1002 int lm = (lo + lh) >>> 1;
1003 if (split <= a[lm + lb])
1004 lh = lm;
1005 else
1006 lo = lm + 1;
1007 }
1008 }
1009 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
1010 rb + rh, rn - rh,
1011 k + lh + rh, g);
1012 rn = rh;
1013 ln = lh;
1014 addToPendingCount(1);
1015 m.fork();
1016 }
1017
1018 int lf = lb + ln, rf = rb + rn; // index bounds
1019 while (lb < lf && rb < rf) {
1020 double t, al, ar;
1021 if ((al = a[lb]) <= (ar = a[rb])) {
1022 lb++; t = al;
1023 }
1024 else {
1025 rb++; t = ar;
1026 }
1027 w[k++] = t;
1028 }
1029 if (rb < rf)
1030 System.arraycopy(a, rb, w, k, rf - rb);
1031 else if (lb < lf)
1032 System.arraycopy(a, lb, w, k, lf - lb);
1033 tryComplete();
1034 }
1035 }
1036 } // FJDouble
1037
1038 }