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 final byte[] a, w; // main and workspace arrays
286 final int lbase, lsize, rbase, rsize, wbase, gran;
287 Merger(CountedCompleter<?> par, byte[] a, byte[] w,
288 int lbase, int lsize, int rbase,
289 int rsize, int wbase, int gran) {
290 super(par);
291 this.a = a; this.w = w;
292 this.lbase = lbase; this.lsize = lsize;
293 this.rbase = rbase; this.rsize = rsize;
294 this.wbase = wbase; this.gran = gran;
295 }
296
297 public final void compute() {
298 byte[] a = this.a, w = this.w; // localize all params
299 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
300 rn = this.rsize, k = this.wbase, g = this.gran;
301 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
302 throw new IllegalStateException(); // hoist checks
303 for (int lh, rh;;) { // split larger, find point in smaller
304 if (ln >= rn) {
305 if (ln <= g)
306 break;
307 rh = rn;
308 byte split = a[(lh = ln >>> 1) + lb];
309 for (int lo = 0; lo < rh; ) {
310 int rm = (lo + rh) >>> 1;
311 if (split <= a[rm + rb])
312 rh = rm;
313 else
314 lo = rm + 1;
315 }
316 }
317 else {
318 if (rn <= g)
319 break;
320 lh = ln;
321 byte split = a[(rh = rn >>> 1) + rb];
322 for (int lo = 0; lo < lh; ) {
323 int lm = (lo + lh) >>> 1;
324 if (split <= a[lm + lb])
325 lh = lm;
326 else
327 lo = lm + 1;
328 }
329 }
330 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
331 rb + rh, rn - rh,
332 k + lh + rh, g);
333 rn = rh;
334 ln = lh;
335 addToPendingCount(1);
336 m.fork();
337 }
338
339 int lf = lb + ln, rf = rb + rn; // index bounds
340 while (lb < lf && rb < rf) {
341 byte t, al, ar;
342 if ((al = a[lb]) <= (ar = a[rb])) {
343 lb++; t = al;
344 }
345 else {
346 rb++; t = ar;
347 }
348 w[k++] = t;
349 }
350 if (rb < rf)
351 System.arraycopy(a, rb, w, k, rf - rb);
352 else if (lb < lf)
353 System.arraycopy(a, lb, w, k, lf - lb);
354 tryComplete();
355 }
356 }
357 } // FJByte
358
359 /** char support class */
360 static final class FJChar {
361 static final class Sorter extends CountedCompleter<Void> {
362 @java.io.Serial
363 static final long serialVersionUID = 2446542900576103244L;
364 final char[] a, w;
365 final int base, size, wbase, gran;
366 Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
367 int size, int wbase, int gran) {
368 super(par);
369 this.a = a; this.w = w; this.base = base; this.size = size;
370 this.wbase = wbase; this.gran = gran;
371 }
372 public final void compute() {
373 CountedCompleter<?> s = this;
374 char[] a = this.a, w = this.w; // localize all params
375 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
376 while (n > g) {
377 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
378 Relay fc = new Relay(new Merger(s, w, a, wb, h,
379 wb+h, n-h, b, g));
380 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
381 b+u, n-u, wb+h, g));
382 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
383 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
384 Relay bc = new Relay(new Merger(fc, a, w, b, q,
385 b+q, h-q, wb, g));
386 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
387 s = new EmptyCompleter(bc);
388 n = q;
389 }
390 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
391 s.tryComplete();
392 }
393 }
394
395 static final class Merger extends CountedCompleter<Void> {
396 @java.io.Serial
397 static final long serialVersionUID = 2446542900576103244L;
398 final char[] a, w; // main and workspace arrays
399 final int lbase, lsize, rbase, rsize, wbase, gran;
400 Merger(CountedCompleter<?> par, char[] a, char[] w,
401 int lbase, int lsize, int rbase,
402 int rsize, int wbase, int gran) {
403 super(par);
404 this.a = a; this.w = w;
405 this.lbase = lbase; this.lsize = lsize;
406 this.rbase = rbase; this.rsize = rsize;
407 this.wbase = wbase; this.gran = gran;
408 }
409
410 public final void compute() {
411 char[] a = this.a, w = this.w; // localize all params
412 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
413 rn = this.rsize, k = this.wbase, g = this.gran;
414 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
415 throw new IllegalStateException(); // hoist checks
416 for (int lh, rh;;) { // split larger, find point in smaller
417 if (ln >= rn) {
418 if (ln <= g)
419 break;
420 rh = rn;
421 char split = a[(lh = ln >>> 1) + lb];
422 for (int lo = 0; lo < rh; ) {
423 int rm = (lo + rh) >>> 1;
424 if (split <= a[rm + rb])
425 rh = rm;
426 else
427 lo = rm + 1;
428 }
429 }
430 else {
431 if (rn <= g)
432 break;
433 lh = ln;
434 char split = a[(rh = rn >>> 1) + rb];
435 for (int lo = 0; lo < lh; ) {
436 int lm = (lo + lh) >>> 1;
437 if (split <= a[lm + lb])
438 lh = lm;
439 else
440 lo = lm + 1;
441 }
442 }
443 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
444 rb + rh, rn - rh,
445 k + lh + rh, g);
446 rn = rh;
447 ln = lh;
448 addToPendingCount(1);
449 m.fork();
450 }
451
452 int lf = lb + ln, rf = rb + rn; // index bounds
453 while (lb < lf && rb < rf) {
454 char t, al, ar;
455 if ((al = a[lb]) <= (ar = a[rb])) {
456 lb++; t = al;
457 }
458 else {
459 rb++; t = ar;
460 }
461 w[k++] = t;
462 }
463 if (rb < rf)
464 System.arraycopy(a, rb, w, k, rf - rb);
465 else if (lb < lf)
466 System.arraycopy(a, lb, w, k, lf - lb);
467 tryComplete();
468 }
469 }
470 } // FJChar
471
472 /** short support class */
473 static final class FJShort {
474 static final class Sorter extends CountedCompleter<Void> {
475 @java.io.Serial
476 static final long serialVersionUID = 2446542900576103244L;
477 final short[] a, w;
478 final int base, size, wbase, gran;
479 Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
480 int size, int wbase, int gran) {
481 super(par);
482 this.a = a; this.w = w; this.base = base; this.size = size;
483 this.wbase = wbase; this.gran = gran;
484 }
485 public final void compute() {
486 CountedCompleter<?> s = this;
487 short[] a = this.a, w = this.w; // localize all params
488 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
489 while (n > g) {
490 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
491 Relay fc = new Relay(new Merger(s, w, a, wb, h,
492 wb+h, n-h, b, g));
493 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
494 b+u, n-u, wb+h, g));
495 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
496 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
497 Relay bc = new Relay(new Merger(fc, a, w, b, q,
498 b+q, h-q, wb, g));
499 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
500 s = new EmptyCompleter(bc);
501 n = q;
502 }
503 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
504 s.tryComplete();
505 }
506 }
507
508 static final class Merger extends CountedCompleter<Void> {
509 @java.io.Serial
510 static final long serialVersionUID = 2446542900576103244L;
511 final short[] a, w; // main and workspace arrays
512 final int lbase, lsize, rbase, rsize, wbase, gran;
513 Merger(CountedCompleter<?> par, short[] a, short[] w,
514 int lbase, int lsize, int rbase,
515 int rsize, int wbase, int gran) {
516 super(par);
517 this.a = a; this.w = w;
518 this.lbase = lbase; this.lsize = lsize;
519 this.rbase = rbase; this.rsize = rsize;
520 this.wbase = wbase; this.gran = gran;
521 }
522
523 public final void compute() {
524 short[] a = this.a, w = this.w; // localize all params
525 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
526 rn = this.rsize, k = this.wbase, g = this.gran;
527 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
528 throw new IllegalStateException(); // hoist checks
529 for (int lh, rh;;) { // split larger, find point in smaller
530 if (ln >= rn) {
531 if (ln <= g)
532 break;
533 rh = rn;
534 short split = a[(lh = ln >>> 1) + lb];
535 for (int lo = 0; lo < rh; ) {
536 int rm = (lo + rh) >>> 1;
537 if (split <= a[rm + rb])
538 rh = rm;
539 else
540 lo = rm + 1;
541 }
542 }
543 else {
544 if (rn <= g)
545 break;
546 lh = ln;
547 short split = a[(rh = rn >>> 1) + rb];
548 for (int lo = 0; lo < lh; ) {
549 int lm = (lo + lh) >>> 1;
550 if (split <= a[lm + lb])
551 lh = lm;
552 else
553 lo = lm + 1;
554 }
555 }
556 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
557 rb + rh, rn - rh,
558 k + lh + rh, g);
559 rn = rh;
560 ln = lh;
561 addToPendingCount(1);
562 m.fork();
563 }
564
565 int lf = lb + ln, rf = rb + rn; // index bounds
566 while (lb < lf && rb < rf) {
567 short t, al, ar;
568 if ((al = a[lb]) <= (ar = a[rb])) {
569 lb++; t = al;
570 }
571 else {
572 rb++; t = ar;
573 }
574 w[k++] = t;
575 }
576 if (rb < rf)
577 System.arraycopy(a, rb, w, k, rf - rb);
578 else if (lb < lf)
579 System.arraycopy(a, lb, w, k, lf - lb);
580 tryComplete();
581 }
582 }
583 } // FJShort
584
585 /** int support class */
586 static final class FJInt {
587 static final class Sorter extends CountedCompleter<Void> {
588 @java.io.Serial
589 static final long serialVersionUID = 2446542900576103244L;
590 final int[] a, w;
591 final int base, size, wbase, gran;
592 Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
593 int size, int wbase, int gran) {
594 super(par);
595 this.a = a; this.w = w; this.base = base; this.size = size;
596 this.wbase = wbase; this.gran = gran;
597 }
598 public final void compute() {
599 CountedCompleter<?> s = this;
600 int[] a = this.a, w = this.w; // localize all params
601 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
602 while (n > g) {
603 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
604 Relay fc = new Relay(new Merger(s, w, a, wb, h,
605 wb+h, n-h, b, g));
606 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
607 b+u, n-u, wb+h, g));
608 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
609 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
610 Relay bc = new Relay(new Merger(fc, a, w, b, q,
611 b+q, h-q, wb, g));
612 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
613 s = new EmptyCompleter(bc);
614 n = q;
615 }
616 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
617 s.tryComplete();
618 }
619 }
620
621 static final class Merger extends CountedCompleter<Void> {
622 @java.io.Serial
623 static final long serialVersionUID = 2446542900576103244L;
624 final int[] a, w; // main and workspace arrays
625 final int lbase, lsize, rbase, rsize, wbase, gran;
626 Merger(CountedCompleter<?> par, int[] a, int[] w,
627 int lbase, int lsize, int rbase,
628 int rsize, int wbase, int gran) {
629 super(par);
630 this.a = a; this.w = w;
631 this.lbase = lbase; this.lsize = lsize;
632 this.rbase = rbase; this.rsize = rsize;
633 this.wbase = wbase; this.gran = gran;
634 }
635
636 public final void compute() {
637 int[] a = this.a, w = this.w; // localize all params
638 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
639 rn = this.rsize, k = this.wbase, g = this.gran;
640 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
641 throw new IllegalStateException(); // hoist checks
642 for (int lh, rh;;) { // split larger, find point in smaller
643 if (ln >= rn) {
644 if (ln <= g)
645 break;
646 rh = rn;
647 int split = a[(lh = ln >>> 1) + lb];
648 for (int lo = 0; lo < rh; ) {
649 int rm = (lo + rh) >>> 1;
650 if (split <= a[rm + rb])
651 rh = rm;
652 else
653 lo = rm + 1;
654 }
655 }
656 else {
657 if (rn <= g)
658 break;
659 lh = ln;
660 int split = a[(rh = rn >>> 1) + rb];
661 for (int lo = 0; lo < lh; ) {
662 int lm = (lo + lh) >>> 1;
663 if (split <= a[lm + lb])
664 lh = lm;
665 else
666 lo = lm + 1;
667 }
668 }
669 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
670 rb + rh, rn - rh,
671 k + lh + rh, g);
672 rn = rh;
673 ln = lh;
674 addToPendingCount(1);
675 m.fork();
676 }
677
678 int lf = lb + ln, rf = rb + rn; // index bounds
679 while (lb < lf && rb < rf) {
680 int t, al, ar;
681 if ((al = a[lb]) <= (ar = a[rb])) {
682 lb++; t = al;
683 }
684 else {
685 rb++; t = ar;
686 }
687 w[k++] = t;
688 }
689 if (rb < rf)
690 System.arraycopy(a, rb, w, k, rf - rb);
691 else if (lb < lf)
692 System.arraycopy(a, lb, w, k, lf - lb);
693 tryComplete();
694 }
695 }
696 } // FJInt
697
698 /** long support class */
699 static final class FJLong {
700 static final class Sorter extends CountedCompleter<Void> {
701 @java.io.Serial
702 static final long serialVersionUID = 2446542900576103244L;
703 final long[] a, w;
704 final int base, size, wbase, gran;
705 Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
706 int size, int wbase, int gran) {
707 super(par);
708 this.a = a; this.w = w; this.base = base; this.size = size;
709 this.wbase = wbase; this.gran = gran;
710 }
711 public final void compute() {
712 CountedCompleter<?> s = this;
713 long[] a = this.a, w = this.w; // localize all params
714 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
715 while (n > g) {
716 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
717 Relay fc = new Relay(new Merger(s, w, a, wb, h,
718 wb+h, n-h, b, g));
719 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
720 b+u, n-u, wb+h, g));
721 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
722 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
723 Relay bc = new Relay(new Merger(fc, a, w, b, q,
724 b+q, h-q, wb, g));
725 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
726 s = new EmptyCompleter(bc);
727 n = q;
728 }
729 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
730 s.tryComplete();
731 }
732 }
733
734 static final class Merger extends CountedCompleter<Void> {
735 @java.io.Serial
736 static final long serialVersionUID = 2446542900576103244L;
737 final long[] a, w; // main and workspace arrays
738 final int lbase, lsize, rbase, rsize, wbase, gran;
739 Merger(CountedCompleter<?> par, long[] a, long[] w,
740 int lbase, int lsize, int rbase,
741 int rsize, int wbase, int gran) {
742 super(par);
743 this.a = a; this.w = w;
744 this.lbase = lbase; this.lsize = lsize;
745 this.rbase = rbase; this.rsize = rsize;
746 this.wbase = wbase; this.gran = gran;
747 }
748
749 public final void compute() {
750 long[] a = this.a, w = this.w; // localize all params
751 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
752 rn = this.rsize, k = this.wbase, g = this.gran;
753 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
754 throw new IllegalStateException(); // hoist checks
755 for (int lh, rh;;) { // split larger, find point in smaller
756 if (ln >= rn) {
757 if (ln <= g)
758 break;
759 rh = rn;
760 long split = a[(lh = ln >>> 1) + lb];
761 for (int lo = 0; lo < rh; ) {
762 int rm = (lo + rh) >>> 1;
763 if (split <= a[rm + rb])
764 rh = rm;
765 else
766 lo = rm + 1;
767 }
768 }
769 else {
770 if (rn <= g)
771 break;
772 lh = ln;
773 long split = a[(rh = rn >>> 1) + rb];
774 for (int lo = 0; lo < lh; ) {
775 int lm = (lo + lh) >>> 1;
776 if (split <= a[lm + lb])
777 lh = lm;
778 else
779 lo = lm + 1;
780 }
781 }
782 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
783 rb + rh, rn - rh,
784 k + lh + rh, g);
785 rn = rh;
786 ln = lh;
787 addToPendingCount(1);
788 m.fork();
789 }
790
791 int lf = lb + ln, rf = rb + rn; // index bounds
792 while (lb < lf && rb < rf) {
793 long t, al, ar;
794 if ((al = a[lb]) <= (ar = a[rb])) {
795 lb++; t = al;
796 }
797 else {
798 rb++; t = ar;
799 }
800 w[k++] = t;
801 }
802 if (rb < rf)
803 System.arraycopy(a, rb, w, k, rf - rb);
804 else if (lb < lf)
805 System.arraycopy(a, lb, w, k, lf - lb);
806 tryComplete();
807 }
808 }
809 } // FJLong
810
811 /** float support class */
812 static final class FJFloat {
813 static final class Sorter extends CountedCompleter<Void> {
814 @java.io.Serial
815 static final long serialVersionUID = 2446542900576103244L;
816 final float[] a, w;
817 final int base, size, wbase, gran;
818 Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
819 int size, int wbase, int gran) {
820 super(par);
821 this.a = a; this.w = w; this.base = base; this.size = size;
822 this.wbase = wbase; this.gran = gran;
823 }
824 public final void compute() {
825 CountedCompleter<?> s = this;
826 float[] a = this.a, w = this.w; // localize all params
827 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
828 while (n > g) {
829 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
830 Relay fc = new Relay(new Merger(s, w, a, wb, h,
831 wb+h, n-h, b, g));
832 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
833 b+u, n-u, wb+h, g));
834 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
835 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
836 Relay bc = new Relay(new Merger(fc, a, w, b, q,
837 b+q, h-q, wb, g));
838 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
839 s = new EmptyCompleter(bc);
840 n = q;
841 }
842 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
843 s.tryComplete();
844 }
845 }
846
847 static final class Merger extends CountedCompleter<Void> {
848 @java.io.Serial
849 static final long serialVersionUID = 2446542900576103244L;
850 final float[] a, w; // main and workspace arrays
851 final int lbase, lsize, rbase, rsize, wbase, gran;
852 Merger(CountedCompleter<?> par, float[] a, float[] w,
853 int lbase, int lsize, int rbase,
854 int rsize, int wbase, int gran) {
855 super(par);
856 this.a = a; this.w = w;
857 this.lbase = lbase; this.lsize = lsize;
858 this.rbase = rbase; this.rsize = rsize;
859 this.wbase = wbase; this.gran = gran;
860 }
861
862 public final void compute() {
863 float[] a = this.a, w = this.w; // localize all params
864 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
865 rn = this.rsize, k = this.wbase, g = this.gran;
866 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
867 throw new IllegalStateException(); // hoist checks
868 for (int lh, rh;;) { // split larger, find point in smaller
869 if (ln >= rn) {
870 if (ln <= g)
871 break;
872 rh = rn;
873 float split = a[(lh = ln >>> 1) + lb];
874 for (int lo = 0; lo < rh; ) {
875 int rm = (lo + rh) >>> 1;
876 if (split <= a[rm + rb])
877 rh = rm;
878 else
879 lo = rm + 1;
880 }
881 }
882 else {
883 if (rn <= g)
884 break;
885 lh = ln;
886 float split = a[(rh = rn >>> 1) + rb];
887 for (int lo = 0; lo < lh; ) {
888 int lm = (lo + lh) >>> 1;
889 if (split <= a[lm + lb])
890 lh = lm;
891 else
892 lo = lm + 1;
893 }
894 }
895 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
896 rb + rh, rn - rh,
897 k + lh + rh, g);
898 rn = rh;
899 ln = lh;
900 addToPendingCount(1);
901 m.fork();
902 }
903
904 int lf = lb + ln, rf = rb + rn; // index bounds
905 while (lb < lf && rb < rf) {
906 float t, al, ar;
907 if ((al = a[lb]) <= (ar = a[rb])) {
908 lb++; t = al;
909 }
910 else {
911 rb++; t = ar;
912 }
913 w[k++] = t;
914 }
915 if (rb < rf)
916 System.arraycopy(a, rb, w, k, rf - rb);
917 else if (lb < lf)
918 System.arraycopy(a, lb, w, k, lf - lb);
919 tryComplete();
920 }
921 }
922 } // FJFloat
923
924 /** double support class */
925 static final class FJDouble {
926 static final class Sorter extends CountedCompleter<Void> {
927 @java.io.Serial
928 static final long serialVersionUID = 2446542900576103244L;
929 final double[] a, w;
930 final int base, size, wbase, gran;
931 Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
932 int size, int wbase, int gran) {
933 super(par);
934 this.a = a; this.w = w; this.base = base; this.size = size;
935 this.wbase = wbase; this.gran = gran;
936 }
937 public final void compute() {
938 CountedCompleter<?> s = this;
939 double[] a = this.a, w = this.w; // localize all params
940 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
941 while (n > g) {
942 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
943 Relay fc = new Relay(new Merger(s, w, a, wb, h,
944 wb+h, n-h, b, g));
945 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
946 b+u, n-u, wb+h, g));
947 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
948 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
949 Relay bc = new Relay(new Merger(fc, a, w, b, q,
950 b+q, h-q, wb, g));
951 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
952 s = new EmptyCompleter(bc);
953 n = q;
954 }
955 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
956 s.tryComplete();
957 }
958 }
959
960 static final class Merger extends CountedCompleter<Void> {
961 @java.io.Serial
962 static final long serialVersionUID = 2446542900576103244L;
963 final double[] a, w; // main and workspace arrays
964 final int lbase, lsize, rbase, rsize, wbase, gran;
965 Merger(CountedCompleter<?> par, double[] a, double[] w,
966 int lbase, int lsize, int rbase,
967 int rsize, int wbase, int gran) {
968 super(par);
969 this.a = a; this.w = w;
970 this.lbase = lbase; this.lsize = lsize;
971 this.rbase = rbase; this.rsize = rsize;
972 this.wbase = wbase; this.gran = gran;
973 }
974
975 public final void compute() {
976 double[] a = this.a, w = this.w; // localize all params
977 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
978 rn = this.rsize, k = this.wbase, g = this.gran;
979 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
980 throw new IllegalStateException(); // hoist checks
981 for (int lh, rh;;) { // split larger, find point in smaller
982 if (ln >= rn) {
983 if (ln <= g)
984 break;
985 rh = rn;
986 double split = a[(lh = ln >>> 1) + lb];
987 for (int lo = 0; lo < rh; ) {
988 int rm = (lo + rh) >>> 1;
989 if (split <= a[rm + rb])
990 rh = rm;
991 else
992 lo = rm + 1;
993 }
994 }
995 else {
996 if (rn <= g)
997 break;
998 lh = ln;
999 double split = a[(rh = rn >>> 1) + rb];
1000 for (int lo = 0; lo < lh; ) {
1001 int lm = (lo + lh) >>> 1;
1002 if (split <= a[lm + lb])
1003 lh = lm;
1004 else
1005 lo = lm + 1;
1006 }
1007 }
1008 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
1009 rb + rh, rn - rh,
1010 k + lh + rh, g);
1011 rn = rh;
1012 ln = lh;
1013 addToPendingCount(1);
1014 m.fork();
1015 }
1016
1017 int lf = lb + ln, rf = rb + rn; // index bounds
1018 while (lb < lf && rb < rf) {
1019 double t, al, ar;
1020 if ((al = a[lb]) <= (ar = a[rb])) {
1021 lb++; t = al;
1022 }
1023 else {
1024 rb++; t = ar;
1025 }
1026 w[k++] = t;
1027 }
1028 if (rb < rf)
1029 System.arraycopy(a, rb, w, k, rf - rb);
1030 else if (lb < lf)
1031 System.arraycopy(a, lb, w, k, lf - lb);
1032 tryComplete();
1033 }
1034 }
1035 } // FJDouble
1036
1037 }