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