1 /*
2 * Copyright (c) 2012, 2013, 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 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,
175 rn = this.rsize, k = this.wbase, g = this.gran;
176 if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
177 c == null)
178 throw new IllegalStateException(); // hoist checks
179 for (int lh, rh;;) { // split larger, find point in smaller
180 if (ln >= rn) {
181 if (ln <= g)
182 break;
183 rh = rn;
184 T split = a[(lh = ln >>> 1) + lb];
185 for (int lo = 0; lo < rh; ) {
186 int rm = (lo + rh) >>> 1;
187 if (c.compare(split, a[rm + rb]) <= 0)
188 rh = rm;
189 else
190 lo = rm + 1;
191 }
192 }
193 else {
194 if (rn <= g)
195 break;
196 lh = ln;
197 T split = a[(rh = rn >>> 1) + rb];
198 for (int lo = 0; lo < lh; ) {
199 int lm = (lo + lh) >>> 1;
200 if (c.compare(split, a[lm + lb]) <= 0)
201 lh = lm;
202 else
203 lo = lm + 1;
204 }
205 }
206 Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh,
207 rb + rh, rn - rh,
208 k + lh + rh, g, c);
209 rn = rh;
210 ln = lh;
211 addToPendingCount(1);
212 m.fork();
213 }
214
215 int lf = lb + ln, rf = rb + rn; // index bounds
216 while (lb < lf && rb < rf) {
217 T t, al, ar;
218 if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
219 lb++; t = al;
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
295 if (ln >= rn) {
296 if (ln <= g)
297 break;
298 rh = rn;
299 byte split = a[(lh = ln >>> 1) + lb];
300 for (int lo = 0; lo < rh; ) {
301 int rm = (lo + rh) >>> 1;
302 if (split <= a[rm + rb])
303 rh = rm;
304 else
305 lo = rm + 1;
306 }
307 }
308 else {
309 if (rn <= g)
310 break;
311 lh = ln;
312 byte split = a[(rh = rn >>> 1) + rb];
313 for (int lo = 0; lo < lh; ) {
314 int lm = (lo + lh) >>> 1;
315 if (split <= a[lm + lb])
316 lh = lm;
317 else
318 lo = lm + 1;
319 }
320 }
321 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
322 rb + rh, rn - rh,
323 k + lh + rh, g);
324 rn = rh;
325 ln = lh;
326 addToPendingCount(1);
327 m.fork();
328 }
329
330 int lf = lb + ln, rf = rb + rn; // index bounds
331 while (lb < lf && rb < rf) {
332 byte t, al, ar;
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
408 if (ln >= rn) {
409 if (ln <= g)
410 break;
411 rh = rn;
412 char split = a[(lh = ln >>> 1) + lb];
413 for (int lo = 0; lo < rh; ) {
414 int rm = (lo + rh) >>> 1;
415 if (split <= a[rm + rb])
416 rh = rm;
417 else
418 lo = rm + 1;
419 }
420 }
421 else {
422 if (rn <= g)
423 break;
424 lh = ln;
425 char split = a[(rh = rn >>> 1) + rb];
426 for (int lo = 0; lo < lh; ) {
427 int lm = (lo + lh) >>> 1;
428 if (split <= a[lm + lb])
429 lh = lm;
430 else
431 lo = lm + 1;
432 }
433 }
434 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
435 rb + rh, rn - rh,
436 k + lh + rh, g);
437 rn = rh;
438 ln = lh;
439 addToPendingCount(1);
440 m.fork();
441 }
442
443 int lf = lb + ln, rf = rb + rn; // index bounds
444 while (lb < lf && rb < rf) {
445 char t, al, ar;
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
521 if (ln >= rn) {
522 if (ln <= g)
523 break;
524 rh = rn;
525 short split = a[(lh = ln >>> 1) + lb];
526 for (int lo = 0; lo < rh; ) {
527 int rm = (lo + rh) >>> 1;
528 if (split <= a[rm + rb])
529 rh = rm;
530 else
531 lo = rm + 1;
532 }
533 }
534 else {
535 if (rn <= g)
536 break;
537 lh = ln;
538 short split = a[(rh = rn >>> 1) + rb];
539 for (int lo = 0; lo < lh; ) {
540 int lm = (lo + lh) >>> 1;
541 if (split <= a[lm + lb])
542 lh = lm;
543 else
544 lo = lm + 1;
545 }
546 }
547 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
548 rb + rh, rn - rh,
549 k + lh + rh, g);
550 rn = rh;
551 ln = lh;
552 addToPendingCount(1);
553 m.fork();
554 }
555
556 int lf = lb + ln, rf = rb + rn; // index bounds
557 while (lb < lf && rb < rf) {
558 short t, al, ar;
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
634 if (ln >= rn) {
635 if (ln <= g)
636 break;
637 rh = rn;
638 int split = a[(lh = ln >>> 1) + lb];
639 for (int lo = 0; lo < rh; ) {
640 int rm = (lo + rh) >>> 1;
641 if (split <= a[rm + rb])
642 rh = rm;
643 else
644 lo = rm + 1;
645 }
646 }
647 else {
648 if (rn <= g)
649 break;
650 lh = ln;
651 int split = a[(rh = rn >>> 1) + rb];
652 for (int lo = 0; lo < lh; ) {
653 int lm = (lo + lh) >>> 1;
654 if (split <= a[lm + lb])
655 lh = lm;
656 else
657 lo = lm + 1;
658 }
659 }
660 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
661 rb + rh, rn - rh,
662 k + lh + rh, g);
663 rn = rh;
664 ln = lh;
665 addToPendingCount(1);
666 m.fork();
667 }
668
669 int lf = lb + ln, rf = rb + rn; // index bounds
670 while (lb < lf && rb < rf) {
671 int t, al, ar;
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
747 if (ln >= rn) {
748 if (ln <= g)
749 break;
750 rh = rn;
751 long split = a[(lh = ln >>> 1) + lb];
752 for (int lo = 0; lo < rh; ) {
753 int rm = (lo + rh) >>> 1;
754 if (split <= a[rm + rb])
755 rh = rm;
756 else
757 lo = rm + 1;
758 }
759 }
760 else {
761 if (rn <= g)
762 break;
763 lh = ln;
764 long split = a[(rh = rn >>> 1) + rb];
765 for (int lo = 0; lo < lh; ) {
766 int lm = (lo + lh) >>> 1;
767 if (split <= a[lm + lb])
768 lh = lm;
769 else
770 lo = lm + 1;
771 }
772 }
773 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
774 rb + rh, rn - rh,
775 k + lh + rh, g);
776 rn = rh;
777 ln = lh;
778 addToPendingCount(1);
779 m.fork();
780 }
781
782 int lf = lb + ln, rf = rb + rn; // index bounds
783 while (lb < lf && rb < rf) {
784 long t, al, ar;
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
860 if (ln >= rn) {
861 if (ln <= g)
862 break;
863 rh = rn;
864 float split = a[(lh = ln >>> 1) + lb];
865 for (int lo = 0; lo < rh; ) {
866 int rm = (lo + rh) >>> 1;
867 if (split <= a[rm + rb])
868 rh = rm;
869 else
870 lo = rm + 1;
871 }
872 }
873 else {
874 if (rn <= g)
875 break;
876 lh = ln;
877 float split = a[(rh = rn >>> 1) + rb];
878 for (int lo = 0; lo < lh; ) {
879 int lm = (lo + lh) >>> 1;
880 if (split <= a[lm + lb])
881 lh = lm;
882 else
883 lo = lm + 1;
884 }
885 }
886 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
887 rb + rh, rn - rh,
888 k + lh + rh, g);
889 rn = rh;
890 ln = lh;
891 addToPendingCount(1);
892 m.fork();
893 }
894
895 int lf = lb + ln, rf = rb + rn; // index bounds
896 while (lb < lf && rb < rf) {
897 float t, al, ar;
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
973 if (ln >= rn) {
974 if (ln <= g)
975 break;
976 rh = rn;
977 double split = a[(lh = ln >>> 1) + lb];
978 for (int lo = 0; lo < rh; ) {
979 int rm = (lo + rh) >>> 1;
980 if (split <= a[rm + rb])
981 rh = rm;
982 else
983 lo = rm + 1;
984 }
985 }
986 else {
987 if (rn <= g)
988 break;
989 lh = ln;
990 double split = a[(rh = rn >>> 1) + rb];
991 for (int lo = 0; lo < lh; ) {
992 int lm = (lo + lh) >>> 1;
993 if (split <= a[lm + lb])
994 lh = lm;
995 else
996 lo = lm + 1;
997 }
998 }
999 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
1000 rb + rh, rn - rh,
1001 k + lh + rh, g);
1002 rn = rh;
1003 ln = lh;
1004 addToPendingCount(1);
1005 m.fork();
1006 }
1007
1008 int lf = lb + ln, rf = rb + rn; // index bounds
1009 while (lb < lf && rb < rf) {
1010 double t, al, ar;
1011 if ((al = a[lb]) <= (ar = a[rb])) {
1012 lb++; t = al;
1013 }
1014 else {
1015 rb++; t = ar;
1016 }
1017 w[k++] = t;
1018 }
1019 if (rb < rf)
1020 System.arraycopy(a, rb, w, k, rf - rb);
1021 else if (lb < lf)
1022 System.arraycopy(a, lb, w, k, lf - lb);
1023 tryComplete();
1024 }
1025 }
1026 } // FJDouble
1027
1028 }