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 29 /** 30 * Helper utilities for the parallel sort methods in Arrays.parallelSort. 31 * 32 * For each primitive type, plus Object, we define a static class to 33 * contain the Sorter and Merger implementations for that type: 34 * 35 * Sorter classes based mainly on CilkSort 36 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>: 37 * Basic algorithm: 38 * if array size is small, just use a sequential quicksort (via Arrays.sort) 39 * Otherwise: 40 * 1. Break array in half. 41 * 2. For each half, 42 * a. break the half in half (i.e., quarters), 43 * b. sort the quarters 44 * c. merge them together 45 * 3. merge together the two halves. 46 * 47 * One reason for splitting in quarters is that this guarantees 48 * that the final sort is in the main array, not the workspace 49 * array. (workspace and main swap roles on each subsort step.) 50 * Leaf-level sorts use a Sequential quicksort, that in turn uses 51 * insertion sort if under threshold. Otherwise it uses median of 52 * three to pick pivot, and loops rather than recurses along left 53 * path. 54 * 55 * 56 * Merger classes perform merging for Sorter. If big enough, splits Left 57 * partition in half; finds the greatest point in Right partition 58 * less than the beginning of the second half of Left via binary 59 * search; and then, in parallel, merges left half of Left with 60 * elements of Right up to split point, and merges right half of 61 * Left with elements of R past split point. At leaf, it just 62 * sequentially merges. This is all messy to code; sadly we need 63 * distinct versions for each type. 64 * 65 */ 66 /*package*/ class ArraysParallelSortHelpers { 67 68 // RFE: we should only need a working array as large as the subarray 69 // to be sorted, but the logic assumes that indices in the two 70 // arrays always line-up 71 72 /** byte support class */ 73 static final class FJByte { 74 static final class Sorter extends RecursiveAction { 75 static final long serialVersionUID = 749471161188027634L; 76 final byte[] a; // array to be sorted. 77 final byte[] w; // workspace for merge 78 final int origin; // origin of the part of array we deal with 79 final int n; // Number of elements in (sub)arrays. 80 final int gran; // split control 81 82 Sorter(byte[] a, byte[] w, int origin, int n, int gran) { 83 this.a = a; 84 this.w = w; 85 this.origin = origin; 86 this.n = n; 87 this.gran = gran; 88 } 89 90 public void compute() { 91 final int l = origin; 92 final int g = gran; 93 final int n = this.n; 94 final byte[] a = this.a; 95 final byte[] w = this.w; 96 if (n > g) { 97 int h = n >>> 1; // half 98 int q = n >>> 2; // lower quarter index 99 int u = h + q; // upper quarter 100 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 101 new Sorter(a, w, l+q, h-q, g), 102 new Merger(a, w, l, q, 103 l+q, h-q, l, g, null)); 104 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l+h, q, g), 105 new Sorter(a, w, l+u, n-u, g), 106 new Merger(a, w, l+h, q, 107 l+u, n-u, l+h, g, null)); 108 rs.fork(); 109 ls.compute(); 110 if (rs.tryUnfork()) rs.compute(); else rs.join(); 111 new Merger(w, a, l, h, 112 l+h, n-h, l, g, null).compute(); 113 } else { 114 DualPivotQuicksort.sort(a, l, l+n-1); //skip rangeCheck 115 } 116 } 117 } 118 119 static final class Merger extends RecursiveAction { 120 static final long serialVersionUID = -9090258248781844470L; 121 final byte[] a; 122 final byte[] w; 123 final int lo; 124 final int ln; 125 final int ro; 126 final int rn; 127 final int wo; 128 final int gran; 129 final Merger next; 130 131 Merger(byte[] a, byte[] w, int lo, int ln, int ro, int rn, int wo, 132 int gran, Merger next) { 133 this.a = a; 134 this.w = w; 135 this.lo = lo; 136 this.ln = ln; 137 this.ro = ro; 138 this.rn = rn; 139 this.wo = wo; 140 this.gran = gran; 141 this.next = next; 142 } 143 144 public void compute() { 145 final byte[] a = this.a; 146 final byte[] w = this.w; 147 Merger rights = null; 148 int nleft = ln; 149 int nright = rn; 150 while (nleft > gran) { 151 int lh = nleft >>> 1; 152 int splitIndex = lo + lh; 153 byte split = a[splitIndex]; 154 int rl = 0; 155 int rh = nright; 156 while (rl < rh) { 157 int mid = (rl + rh) >>> 1; 158 if (split <= a[ro + mid]) 159 rh = mid; 160 else 161 rl = mid + 1; 162 } 163 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 164 nright-rh, wo+lh+rh, gran, rights)).fork(); 165 nleft = lh; 166 nright = rh; 167 } 168 169 int l = lo; 170 int lFence = l + nleft; 171 int r = ro; 172 int rFence = r + nright; 173 int k = wo; 174 while (l < lFence && r < rFence) { 175 byte al = a[l]; 176 byte ar = a[r]; 177 byte t; 178 if (al <= ar) {++l; t=al;} else {++r; t = ar;} 179 w[k++] = t; 180 } 181 while (l < lFence) 182 w[k++] = a[l++]; 183 while (r < rFence) 184 w[k++] = a[r++]; 185 while (rights != null) { 186 if (rights.tryUnfork()) 187 rights.compute(); 188 else 189 rights.join(); 190 rights = rights.next; 191 } 192 } 193 } 194 } // FJByte 195 196 /** char support class */ 197 static final class FJChar { 198 static final class Sorter extends RecursiveAction { 199 static final long serialVersionUID = 8723376019074596641L; 200 final char[] a; // array to be sorted. 201 final char[] w; // workspace for merge 202 final int origin; // origin of the part of array we deal with 203 final int n; // Number of elements in (sub)arrays. 204 final int gran; // split control 205 206 Sorter(char[] a, char[] w, int origin, int n, int gran) { 207 this.a = a; 208 this.w = w; 209 this.origin = origin; 210 this.n = n; 211 this.gran = gran; 212 } 213 214 public void compute() { 215 final int l = origin; 216 final int g = gran; 217 final int n = this.n; 218 final char[] a = this.a; 219 final char[] w = this.w; 220 if (n > g) { 221 int h = n >>> 1; // half 222 int q = n >>> 2; // lower quarter index 223 int u = h + q; // upper quarter 224 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 225 new Sorter(a, w, l+q, h-q, g), 226 new Merger(a, w, l, q, 227 l+q, h-q, l, g, null)); 228 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), 229 new Sorter(a, w, l+u, n-u, g), 230 new Merger(a, w, l+h, q, 231 l+u, n-u, l+h, g, null)); 232 rs.fork(); 233 ls.compute(); 234 if (rs.tryUnfork()) rs.compute(); else rs.join(); 235 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); 236 } else { 237 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck 238 } 239 } 240 } 241 242 static final class Merger extends RecursiveAction { 243 static final long serialVersionUID = -1383975444621698926L; 244 final char[] a; 245 final char[] w; 246 final int lo; 247 final int ln; 248 final int ro; 249 final int rn; 250 final int wo; 251 final int gran; 252 final Merger next; 253 254 Merger(char[] a, char[] w, int lo, int ln, int ro, int rn, int wo, 255 int gran, Merger next) { 256 this.a = a; 257 this.w = w; 258 this.lo = lo; 259 this.ln = ln; 260 this.ro = ro; 261 this.rn = rn; 262 this.wo = wo; 263 this.gran = gran; 264 this.next = next; 265 } 266 267 public void compute() { 268 final char[] a = this.a; 269 final char[] w = this.w; 270 Merger rights = null; 271 int nleft = ln; 272 int nright = rn; 273 while (nleft > gran) { 274 int lh = nleft >>> 1; 275 int splitIndex = lo + lh; 276 char split = a[splitIndex]; 277 int rl = 0; 278 int rh = nright; 279 while (rl < rh) { 280 int mid = (rl + rh) >>> 1; 281 if (split <= a[ro + mid]) 282 rh = mid; 283 else 284 rl = mid + 1; 285 } 286 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 287 nright-rh, wo+lh+rh, gran, rights)).fork(); 288 nleft = lh; 289 nright = rh; 290 } 291 292 int l = lo; 293 int lFence = l + nleft; 294 int r = ro; 295 int rFence = r + nright; 296 int k = wo; 297 while (l < lFence && r < rFence) { 298 char al = a[l]; 299 char ar = a[r]; 300 char t; 301 if (al <= ar) {++l; t=al;} else {++r; t = ar;} 302 w[k++] = t; 303 } 304 while (l < lFence) 305 w[k++] = a[l++]; 306 while (r < rFence) 307 w[k++] = a[r++]; 308 while (rights != null) { 309 if (rights.tryUnfork()) 310 rights.compute(); 311 else 312 rights.join(); 313 rights = rights.next; 314 } 315 } 316 } 317 } // FJChar 318 319 /** short support class */ 320 static final class FJShort { 321 static final class Sorter extends RecursiveAction { 322 static final long serialVersionUID = -7886754793730583084L; 323 final short[] a; // array to be sorted. 324 final short[] w; // workspace for merge 325 final int origin; // origin of the part of array we deal with 326 final int n; // Number of elements in (sub)arrays. 327 final int gran; // split control 328 329 Sorter(short[] a, short[] w, int origin, int n, int gran) { 330 this.a = a; 331 this.w = w; 332 this.origin = origin; 333 this.n = n; 334 this.gran = gran; 335 } 336 337 public void compute() { 338 final int l = origin; 339 final int g = gran; 340 final int n = this.n; 341 final short[] a = this.a; 342 final short[] w = this.w; 343 if (n > g) { 344 int h = n >>> 1; // half 345 int q = n >>> 2; // lower quarter index 346 int u = h + q; // upper quarter 347 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 348 new Sorter(a, w, l+q, h-q, g), 349 new Merger(a, w, l, q, 350 l+q, h-q, l, g, null)); 351 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), 352 new Sorter(a, w, l+u, n-u, g), 353 new Merger(a, w, l+h, q, 354 l+u, n-u, l+h, g, null)); 355 rs.fork(); 356 ls.compute(); 357 if (rs.tryUnfork()) rs.compute(); else rs.join(); 358 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); 359 } else { 360 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck 361 } 362 } 363 } 364 365 static final class Merger extends RecursiveAction { 366 static final long serialVersionUID = 3895749408536700048L; 367 final short[] a; 368 final short[] w; 369 final int lo; 370 final int ln; 371 final int ro; 372 final int rn; 373 final int wo; 374 final int gran; 375 final Merger next; 376 377 Merger(short[] a, short[] w, int lo, int ln, int ro, int rn, int wo, 378 int gran, Merger next) { 379 this.a = a; 380 this.w = w; 381 this.lo = lo; 382 this.ln = ln; 383 this.ro = ro; 384 this.rn = rn; 385 this.wo = wo; 386 this.gran = gran; 387 this.next = next; 388 } 389 390 public void compute() { 391 final short[] a = this.a; 392 final short[] w = this.w; 393 Merger rights = null; 394 int nleft = ln; 395 int nright = rn; 396 while (nleft > gran) { 397 int lh = nleft >>> 1; 398 int splitIndex = lo + lh; 399 short split = a[splitIndex]; 400 int rl = 0; 401 int rh = nright; 402 while (rl < rh) { 403 int mid = (rl + rh) >>> 1; 404 if (split <= a[ro + mid]) 405 rh = mid; 406 else 407 rl = mid + 1; 408 } 409 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 410 nright-rh, wo+lh+rh, gran, rights)).fork(); 411 nleft = lh; 412 nright = rh; 413 } 414 415 int l = lo; 416 int lFence = l + nleft; 417 int r = ro; 418 int rFence = r + nright; 419 int k = wo; 420 while (l < lFence && r < rFence) { 421 short al = a[l]; 422 short ar = a[r]; 423 short t; 424 if (al <= ar) {++l; t=al;} else {++r; t = ar;} 425 w[k++] = t; 426 } 427 while (l < lFence) 428 w[k++] = a[l++]; 429 while (r < rFence) 430 w[k++] = a[r++]; 431 while (rights != null) { 432 if (rights.tryUnfork()) 433 rights.compute(); 434 else 435 rights.join(); 436 rights = rights.next; 437 } 438 } 439 } 440 } // FJShort 441 442 /** int support class */ 443 static final class FJInt { 444 static final class Sorter extends RecursiveAction { 445 static final long serialVersionUID = 4263311808957292729L; 446 final int[] a; // array to be sorted. 447 final int[] w; // workspace for merge 448 final int origin; // origin of the part of array we deal with 449 final int n; // Number of elements in (sub)arrays. 450 final int gran; // split control 451 452 Sorter(int[] a, int[] w, int origin, int n, int gran) { 453 this.a = a; 454 this.w = w; 455 this.origin = origin; 456 this.n = n; 457 this.gran = gran; 458 } 459 460 public void compute() { 461 final int l = origin; 462 final int g = gran; 463 final int n = this.n; 464 final int[] a = this.a; 465 final int[] w = this.w; 466 if (n > g) { 467 int h = n >>> 1; // half 468 int q = n >>> 2; // lower quarter index 469 int u = h + q; // upper quarter 470 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 471 new Sorter(a, w, l+q, h-q, g), 472 new Merger(a, w, l, q, 473 l+q, h-q, l, g, null)); 474 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), 475 new Sorter(a, w, l+u, n-u, g), 476 new Merger(a, w, l+h, q, 477 l+u, n-u, l+h, g, null)); 478 rs.fork(); 479 ls.compute(); 480 if (rs.tryUnfork()) rs.compute(); else rs.join(); 481 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); 482 } else { 483 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck 484 } 485 } 486 } 487 488 static final class Merger extends RecursiveAction { 489 static final long serialVersionUID = -8727507284219982792L; 490 final int[] a; 491 final int[] w; 492 final int lo; 493 final int ln; 494 final int ro; 495 final int rn; 496 final int wo; 497 final int gran; 498 final Merger next; 499 500 Merger(int[] a, int[] w, int lo, int ln, int ro, int rn, int wo, 501 int gran, Merger next) { 502 this.a = a; 503 this.w = w; 504 this.lo = lo; 505 this.ln = ln; 506 this.ro = ro; 507 this.rn = rn; 508 this.wo = wo; 509 this.gran = gran; 510 this.next = next; 511 } 512 513 public void compute() { 514 final int[] a = this.a; 515 final int[] w = this.w; 516 Merger rights = null; 517 int nleft = ln; 518 int nright = rn; 519 while (nleft > gran) { 520 int lh = nleft >>> 1; 521 int splitIndex = lo + lh; 522 int split = a[splitIndex]; 523 int rl = 0; 524 int rh = nright; 525 while (rl < rh) { 526 int mid = (rl + rh) >>> 1; 527 if (split <= a[ro + mid]) 528 rh = mid; 529 else 530 rl = mid + 1; 531 } 532 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 533 nright-rh, wo+lh+rh, gran, rights)).fork(); 534 nleft = lh; 535 nright = rh; 536 } 537 538 int l = lo; 539 int lFence = l + nleft; 540 int r = ro; 541 int rFence = r + nright; 542 int k = wo; 543 while (l < lFence && r < rFence) { 544 int al = a[l]; 545 int ar = a[r]; 546 int t; 547 if (al <= ar) {++l; t=al;} else {++r; t = ar;} 548 w[k++] = t; 549 } 550 while (l < lFence) 551 w[k++] = a[l++]; 552 while (r < rFence) 553 w[k++] = a[r++]; 554 while (rights != null) { 555 if (rights.tryUnfork()) 556 rights.compute(); 557 else 558 rights.join(); 559 rights = rights.next; 560 } 561 } 562 } 563 } // FJInt 564 565 /** long support class */ 566 static final class FJLong { 567 static final class Sorter extends RecursiveAction { 568 static final long serialVersionUID = 6553695007444392455L; 569 final long[] a; // array to be sorted. 570 final long[] w; // workspace for merge 571 final int origin; // origin of the part of array we deal with 572 final int n; // Number of elements in (sub)arrays. 573 final int gran; // split control 574 575 Sorter(long[] a, long[] w, int origin, int n, int gran) { 576 this.a = a; 577 this.w = w; 578 this.origin = origin; 579 this.n = n; 580 this.gran = gran; 581 } 582 583 public void compute() { 584 final int l = origin; 585 final int g = gran; 586 final int n = this.n; 587 final long[] a = this.a; 588 final long[] w = this.w; 589 if (n > g) { 590 int h = n >>> 1; // half 591 int q = n >>> 2; // lower quarter index 592 int u = h + q; // upper quarter 593 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 594 new Sorter(a, w, l+q, h-q, g), 595 new Merger(a, w, l, q, 596 l+q, h-q, l, g, null)); 597 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), 598 new Sorter(a, w, l+u, n-u, g), 599 new Merger(a, w, l+h, q, 600 l+u, n-u, l+h, g, null)); 601 rs.fork(); 602 ls.compute(); 603 if (rs.tryUnfork()) rs.compute(); else rs.join(); 604 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); 605 } else { 606 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck 607 } 608 } 609 } 610 611 static final class Merger extends RecursiveAction { 612 static final long serialVersionUID = 8843567516333283861L; 613 final long[] a; 614 final long[] w; 615 final int lo; 616 final int ln; 617 final int ro; 618 final int rn; 619 final int wo; 620 final int gran; 621 final Merger next; 622 623 Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo, 624 int gran, Merger next) { 625 this.a = a; 626 this.w = w; 627 this.lo = lo; 628 this.ln = ln; 629 this.ro = ro; 630 this.rn = rn; 631 this.wo = wo; 632 this.gran = gran; 633 this.next = next; 634 } 635 636 public void compute() { 637 final long[] a = this.a; 638 final long[] w = this.w; 639 Merger rights = null; 640 int nleft = ln; 641 int nright = rn; 642 while (nleft > gran) { 643 int lh = nleft >>> 1; 644 int splitIndex = lo + lh; 645 long split = a[splitIndex]; 646 int rl = 0; 647 int rh = nright; 648 while (rl < rh) { 649 int mid = (rl + rh) >>> 1; 650 if (split <= a[ro + mid]) 651 rh = mid; 652 else 653 rl = mid + 1; 654 } 655 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 656 nright-rh, wo+lh+rh, gran, rights)).fork(); 657 nleft = lh; 658 nright = rh; 659 } 660 661 int l = lo; 662 int lFence = l + nleft; 663 int r = ro; 664 int rFence = r + nright; 665 int k = wo; 666 while (l < lFence && r < rFence) { 667 long al = a[l]; 668 long ar = a[r]; 669 long t; 670 if (al <= ar) {++l; t=al;} else {++r; t = ar;} 671 w[k++] = t; 672 } 673 while (l < lFence) 674 w[k++] = a[l++]; 675 while (r < rFence) 676 w[k++] = a[r++]; 677 while (rights != null) { 678 if (rights.tryUnfork()) 679 rights.compute(); 680 else 681 rights.join(); 682 rights = rights.next; 683 } 684 } 685 } 686 } // FJLong 687 688 /** float support class */ 689 static final class FJFloat { 690 static final class Sorter extends RecursiveAction { 691 static final long serialVersionUID = 1602600178202763377L; 692 final float[] a; // array to be sorted. 693 final float[] w; // workspace for merge 694 final int origin; // origin of the part of array we deal with 695 final int n; // Number of elements in (sub)arrays. 696 final int gran; // split control 697 698 Sorter(float[] a, float[] w, int origin, int n, int gran) { 699 this.a = a; 700 this.w = w; 701 this.origin = origin; 702 this.n = n; 703 this.gran = gran; 704 } 705 706 public void compute() { 707 final int l = origin; 708 final int g = gran; 709 final int n = this.n; 710 final float[] a = this.a; 711 final float[] w = this.w; 712 if (n > g) { 713 int h = n >>> 1; // half 714 int q = n >>> 2; // lower quarter index 715 int u = h + q; // upper quarter 716 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 717 new Sorter(a, w, l+q, h-q, g), 718 new Merger(a, w, l, q, 719 l+q, h-q, l, g, null)); 720 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), 721 new Sorter(a, w, l+u, n-u, g), 722 new Merger(a, w, l+h, q, 723 l+u, n-u, l+h, g, null)); 724 rs.fork(); 725 ls.compute(); 726 if (rs.tryUnfork()) rs.compute(); else rs.join(); 727 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); 728 } else { 729 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck 730 } 731 } 732 } 733 734 static final class Merger extends RecursiveAction { 735 static final long serialVersionUID = 1518176433845397426L; 736 final float[] a; 737 final float[] w; 738 final int lo; 739 final int ln; 740 final int ro; 741 final int rn; 742 final int wo; 743 final int gran; 744 final Merger next; 745 746 Merger(float[] a, float[] w, int lo, int ln, int ro, int rn, int wo, 747 int gran, Merger next) { 748 this.a = a; 749 this.w = w; 750 this.lo = lo; 751 this.ln = ln; 752 this.ro = ro; 753 this.rn = rn; 754 this.wo = wo; 755 this.gran = gran; 756 this.next = next; 757 } 758 759 public void compute() { 760 final float[] a = this.a; 761 final float[] w = this.w; 762 Merger rights = null; 763 int nleft = ln; 764 int nright = rn; 765 while (nleft > gran) { 766 int lh = nleft >>> 1; 767 int splitIndex = lo + lh; 768 float split = a[splitIndex]; 769 int rl = 0; 770 int rh = nright; 771 while (rl < rh) { 772 int mid = (rl + rh) >>> 1; 773 if (Float.compare(split, a[ro+mid]) <= 0) 774 rh = mid; 775 else 776 rl = mid + 1; 777 } 778 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 779 nright-rh, wo+lh+rh, gran, rights)).fork(); 780 nleft = lh; 781 nright = rh; 782 } 783 784 int l = lo; 785 int lFence = l + nleft; 786 int r = ro; 787 int rFence = r + nright; 788 int k = wo; 789 while (l < lFence && r < rFence) { 790 float al = a[l]; 791 float ar = a[r]; 792 float t; 793 if (Float.compare(al, ar) <= 0) { 794 ++l; 795 t = al; 796 } else { 797 ++r; 798 t = ar; 799 } 800 w[k++] = t; 801 } 802 while (l < lFence) 803 w[k++] = a[l++]; 804 while (r < rFence) 805 w[k++] = a[r++]; 806 while (rights != null) { 807 if (rights.tryUnfork()) 808 rights.compute(); 809 else 810 rights.join(); 811 rights = rights.next; 812 } 813 } 814 } 815 } // FJFloat 816 817 /** double support class */ 818 static final class FJDouble { 819 static final class Sorter extends RecursiveAction { 820 static final long serialVersionUID = 2446542900576103244L; 821 final double[] a; // array to be sorted. 822 final double[] w; // workspace for merge 823 final int origin; // origin of the part of array we deal with 824 final int n; // Number of elements in (sub)arrays. 825 final int gran; // split control 826 827 Sorter(double[] a, double[] w, int origin, int n, int gran) { 828 this.a = a; 829 this.w = w; 830 this.origin = origin; 831 this.n = n; 832 this.gran = gran; 833 } 834 835 public void compute() { 836 final int l = origin; 837 final int g = gran; 838 final int n = this.n; 839 final double[] a = this.a; 840 final double[] w = this.w; 841 if (n > g) { 842 int h = n >>> 1; // half 843 int q = n >>> 2; // lower quarter index 844 int u = h + q; // upper quarter 845 FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), 846 new Sorter(a, w, l+q, h-q, g), 847 new Merger(a, w, l, q, 848 l+q, h-q, l, g, null)); 849 FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), 850 new Sorter(a, w, l+u, n-u, g), 851 new Merger(a, w, l+h, q, 852 l+u, n-u, l+h, g, null)); 853 rs.fork(); 854 ls.compute(); 855 if (rs.tryUnfork()) rs.compute(); else rs.join(); 856 new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); 857 } else { 858 DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck 859 } 860 } 861 } 862 863 static final class Merger extends RecursiveAction { 864 static final long serialVersionUID = 8076242187166127592L; 865 final double[] a; 866 final double[] w; 867 final int lo; 868 final int ln; 869 final int ro; 870 final int rn; 871 final int wo; 872 final int gran; 873 final Merger next; 874 875 Merger(double[] a, double[] w, int lo, int ln, int ro, int rn, int wo, 876 int gran, Merger next) { 877 this.a = a; 878 this.w = w; 879 this.lo = lo; 880 this.ln = ln; 881 this.ro = ro; 882 this.rn = rn; 883 this.wo = wo; 884 this.gran = gran; 885 this.next = next; 886 } 887 888 public void compute() { 889 final double[] a = this.a; 890 final double[] w = this.w; 891 Merger rights = null; 892 int nleft = ln; 893 int nright = rn; 894 while (nleft > gran) { 895 int lh = nleft >>> 1; 896 int splitIndex = lo + lh; 897 double split = a[splitIndex]; 898 int rl = 0; 899 int rh = nright; 900 while (rl < rh) { 901 int mid = (rl + rh) >>> 1; 902 if (Double.compare(split, a[ro+mid]) <= 0) 903 rh = mid; 904 else 905 rl = mid + 1; 906 } 907 (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, 908 nright-rh, wo+lh+rh, gran, rights)).fork(); 909 nleft = lh; 910 nright = rh; 911 } 912 913 int l = lo; 914 int lFence = l + nleft; 915 int r = ro; 916 int rFence = r + nright; 917 int k = wo; 918 while (l < lFence && r < rFence) { 919 double al = a[l]; 920 double ar = a[r]; 921 double t; 922 if (Double.compare(al, ar) <= 0) { 923 ++l; 924 t = al; 925 } else { 926 ++r; 927 t = ar; 928 } 929 w[k++] = t; 930 } 931 while (l < lFence) 932 w[k++] = a[l++]; 933 while (r < rFence) 934 w[k++] = a[r++]; 935 while (rights != null) { 936 if (rights.tryUnfork()) 937 rights.compute(); 938 else 939 rights.join(); 940 rights = rights.next; 941 } 942 } 943 } 944 } // FJDouble 945 946 /** Comparable support class */ 947 static final class FJComparable { 948 static final class Sorter<T extends Comparable<? super T>> extends RecursiveAction { 949 static final long serialVersionUID = -1024003289463302522L; 950 final T[] a; 951 final T[] w; 952 final int origin; 953 final int n; 954 final int gran; 955 956 Sorter(T[] a, T[] w, int origin, int n, int gran) { 957 this.a = a; 958 this.w = w; 959 this.origin = origin; 960 this.n = n; 961 this.gran = gran; 962 } 963 964 public void compute() { 965 final int l = origin; 966 final int g = gran; 967 final int n = this.n; 968 final T[] a = this.a; 969 final T[] w = this.w; 970 if (n > g) { 971 int h = n >>> 1; 972 int q = n >>> 2; 973 int u = h + q; 974 FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q, g), 975 new Sorter<>(a, w, l+q, h-q, g), 976 new Merger<>(a, w, l, q, 977 l+q, h-q, l, g, null)); 978 FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l+h, q, g), 979 new Sorter<>(a, w, l+u, n-u, g), 980 new Merger<>(a, w, l+h, q, 981 l+u, n-u, l+h, g, null)); 982 rs.fork(); 983 ls.compute(); 984 if (rs.tryUnfork()) rs.compute(); else rs.join(); 985 new Merger<>(w, a, l, h, l + h, n - h, l, g, null).compute(); 986 } else { 987 Arrays.sort(a, l, l+n); 988 } 989 } 990 } 991 992 static final class Merger<T extends Comparable<? super T>> extends RecursiveAction { 993 static final long serialVersionUID = -3989771675258379302L; 994 final T[] a; 995 final T[] w; 996 final int lo; 997 final int ln; 998 final int ro; 999 final int rn; 1000 final int wo; 1001 final int gran; 1002 final Merger<T> next; 1003 1004 Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo, 1005 int gran, Merger<T> next) { 1006 this.a = a; 1007 this.w = w; 1008 this.lo = lo; 1009 this.ln = ln; 1010 this.ro = ro; 1011 this.rn = rn; 1012 this.wo = wo; 1013 this.gran = gran; 1014 this.next = next; 1015 } 1016 1017 public void compute() { 1018 final T[] a = this.a; 1019 final T[] w = this.w; 1020 Merger<T> rights = null; 1021 int nleft = ln; 1022 int nright = rn; 1023 while (nleft > gran) { 1024 int lh = nleft >>> 1; 1025 int splitIndex = lo + lh; 1026 T split = a[splitIndex]; 1027 int rl = 0; 1028 int rh = nright; 1029 while (rl < rh) { 1030 int mid = (rl + rh) >>> 1; 1031 if (split.compareTo(a[ro + mid]) <= 0) 1032 rh = mid; 1033 else 1034 rl = mid + 1; 1035 } 1036 (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh, 1037 nright-rh, wo+lh+rh, gran, rights)).fork(); 1038 nleft = lh; 1039 nright = rh; 1040 } 1041 1042 int l = lo; 1043 int lFence = l + nleft; 1044 int r = ro; 1045 int rFence = r + nright; 1046 int k = wo; 1047 while (l < lFence && r < rFence) { 1048 T al = a[l]; 1049 T ar = a[r]; 1050 T t; 1051 if (al.compareTo(ar) <= 0) {++l; t=al;} else {++r; t=ar; } 1052 w[k++] = t; 1053 } 1054 while (l < lFence) 1055 w[k++] = a[l++]; 1056 while (r < rFence) 1057 w[k++] = a[r++]; 1058 while (rights != null) { 1059 if (rights.tryUnfork()) 1060 rights.compute(); 1061 else 1062 rights.join(); 1063 rights = rights.next; 1064 } 1065 } 1066 } 1067 } // FJComparable 1068 1069 /** Object + Comparator support class */ 1070 static final class FJComparator { 1071 static final class Sorter<T> extends RecursiveAction { 1072 static final long serialVersionUID = 9191600840025808581L; 1073 final T[] a; // array to be sorted. 1074 final T[] w; // workspace for merge 1075 final int origin; // origin of the part of array we deal with 1076 final int n; // Number of elements in (sub)arrays. 1077 final int gran; // split control 1078 final Comparator<? super T> cmp; // Comparator to use 1079 1080 Sorter(T[] a, T[] w, int origin, int n, int gran, Comparator<? super T> cmp) { 1081 this.a = a; 1082 this.w = w; 1083 this.origin = origin; 1084 this.n = n; 1085 this.cmp = cmp; 1086 this.gran = gran; 1087 } 1088 1089 public void compute() { 1090 final int l = origin; 1091 final int g = gran; 1092 final int n = this.n; 1093 final T[] a = this.a; 1094 final T[] w = this.w; 1095 if (n > g) { 1096 int h = n >>> 1; // half 1097 int q = n >>> 2; // lower quarter index 1098 int u = h + q; // upper quarter 1099 FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q, g, cmp), 1100 new Sorter<>(a, w, l+q, h-q, g, cmp), 1101 new Merger<>(a, w, l, q, 1102 l+q, h-q, l, g, null, cmp)); 1103 FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l + h, q, g, cmp), 1104 new Sorter<>(a, w, l+u, n-u, g, cmp), 1105 new Merger<>(a, w, l+h, q, 1106 l+u, n-u, l+h, g, null, cmp)); 1107 rs.fork(); 1108 ls.compute(); 1109 if (rs.tryUnfork()) rs.compute(); else rs.join(); 1110 new Merger<>(w, a, l, h, l + h, n - h, l, g, null, cmp).compute(); 1111 } else { 1112 Arrays.sort(a, l, l+n, cmp); 1113 } 1114 } 1115 } 1116 1117 static final class Merger<T> extends RecursiveAction { 1118 static final long serialVersionUID = -2679539040379156203L; 1119 final T[] a; 1120 final T[] w; 1121 final int lo; 1122 final int ln; 1123 final int ro; 1124 final int rn; 1125 final int wo; 1126 final int gran; 1127 final Merger<T> next; 1128 final Comparator<? super T> cmp; 1129 1130 Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo, 1131 int gran, Merger<T> next, Comparator<? super T> cmp) { 1132 this.a = a; 1133 this.w = w; 1134 this.lo = lo; 1135 this.ln = ln; 1136 this.ro = ro; 1137 this.rn = rn; 1138 this.wo = wo; 1139 this.gran = gran; 1140 this.next = next; 1141 this.cmp = cmp; 1142 } 1143 1144 public void compute() { 1145 final T[] a = this.a; 1146 final T[] w = this.w; 1147 Merger<T> rights = null; 1148 int nleft = ln; 1149 int nright = rn; 1150 while (nleft > gran) { 1151 int lh = nleft >>> 1; 1152 int splitIndex = lo + lh; 1153 T split = a[splitIndex]; 1154 int rl = 0; 1155 int rh = nright; 1156 while (rl < rh) { 1157 int mid = (rl + rh) >>> 1; 1158 if (cmp.compare(split, a[ro+mid]) <= 0) 1159 rh = mid; 1160 else 1161 rl = mid + 1; 1162 } 1163 (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh, 1164 nright-rh, wo+lh+rh, gran, rights, cmp)).fork(); 1165 nleft = lh; 1166 nright = rh; 1167 } 1168 1169 int l = lo; 1170 int lFence = l + nleft; 1171 int r = ro; 1172 int rFence = r + nright; 1173 int k = wo; 1174 while (l < lFence && r < rFence) { 1175 T al = a[l]; 1176 T ar = a[r]; 1177 T t; 1178 if (cmp.compare(al, ar) <= 0) { 1179 ++l; 1180 t = al; 1181 } else { 1182 ++r; 1183 t = ar; 1184 } 1185 w[k++] = t; 1186 } 1187 while (l < lFence) 1188 w[k++] = a[l++]; 1189 while (r < rFence) 1190 w[k++] = a[r++]; 1191 while (rights != null) { 1192 if (rights.tryUnfork()) 1193 rights.compute(); 1194 else 1195 rights.join(); 1196 rights = rights.next; 1197 } 1198 } 1199 } 1200 } // FJComparator 1201 1202 /** Utility class to sort half a partitioned array */ 1203 private static final class FJSubSorter extends RecursiveAction { 1204 static final long serialVersionUID = 9159249695527935512L; 1205 final RecursiveAction left; 1206 final RecursiveAction right; 1207 final RecursiveAction merger; 1208 1209 FJSubSorter(RecursiveAction left, RecursiveAction right, 1210 RecursiveAction merger) { 1211 this.left = left; 1212 this.right = right; 1213 this.merger = merger; 1214 } 1215 1216 public void compute() { 1217 right.fork(); 1218 left.invoke(); 1219 right.join(); 1220 merger.invoke(); 1221 } 1222 } 1223 } | 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; 91 EmptyCompleter(CountedCompleter<?> p) { super(p); } 92 public final void compute() { } 93 } 94 95 /** 96 * A trigger for secondary merge of two merges 97 */ 98 static final class Relay extends CountedCompleter<Void> { 99 static final long serialVersionUID = 2446542900576103244L; 100 final CountedCompleter<?> task; 101 Relay(CountedCompleter<?> task) { 102 super(null, 1); 103 this.task = task; 104 } 105 public final void compute() { } 106 public final void onCompletion(CountedCompleter<?> t) { 107 task.compute(); 108 } 109 } 110 111 /** Object + Comparator support class */ 112 static final class FJObject { 113 static final class Sorter<T> extends CountedCompleter<Void> { 114 static final long serialVersionUID = 2446542900576103244L; 115 final T[] a, w; 116 final int base, size, wbase, gran; 117 Comparator<? super T> comparator; 118 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, 119 int wbase, int gran, 120 Comparator<? super T> comparator) { 121 super(par); 122 this.a = a; this.w = w; this.base = base; this.size = size; 123 this.wbase = wbase; this.gran = gran; 124 this.comparator = comparator; 125 } 126 public final void compute() { 127 CountedCompleter<?> s = this; 128 Comparator<? super T> c = this.comparator; 129 T[] a = this.a, w = this.w; // localize all params 130 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 131 while (n > g) { 132 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 133 Relay fc = new Relay(new Merger<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; 155 Merger(CountedCompleter<?> par, T[] a, T[] w, 156 int lbase, int lsize, int rbase, 157 int rsize, int wbase, int gran, 158 Comparator<? super T> comparator) { 159 super(par); 160 this.a = a; this.w = w; 161 this.lbase = lbase; this.lsize = lsize; 162 this.rbase = rbase; this.rsize = rsize; 163 this.wbase = wbase; this.gran = gran; 164 this.comparator = comparator; 165 } 166 167 public final void compute() { 168 Comparator<? super T> c = this.comparator; 169 T[] a = this.a, w = this.w; // localize all params 170 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 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; 239 Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base, 240 int size, int wbase, int gran) { 241 super(par); 242 this.a = a; this.w = w; this.base = base; this.size = size; 243 this.wbase = wbase; this.gran = gran; 244 } 245 public final void compute() { 246 CountedCompleter<?> s = this; 247 byte[] a = this.a, w = this.w; // localize all params 248 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 249 while (n > g) { 250 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 251 Relay fc = new Relay(new Merger(s, w, a, wb, h, 252 wb+h, n-h, b, g)); 253 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 254 b+u, n-u, wb+h, g)); 255 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 256 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 257 Relay bc = new Relay(new Merger(fc, a, w, b, q, 258 b+q, h-q, wb, g)); 259 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 260 s = new EmptyCompleter(bc); 261 n = q; 262 } 263 DualPivotQuicksort.sort(a, b, b + n - 1); 264 s.tryComplete(); 265 } 266 } 267 268 static final class Merger extends CountedCompleter<Void> { 269 static final long serialVersionUID = 2446542900576103244L; 270 final byte[] a, w; // main and workspace arrays 271 final int lbase, lsize, rbase, rsize, wbase, gran; 272 Merger(CountedCompleter<?> par, byte[] a, byte[] w, 273 int lbase, int lsize, int rbase, 274 int rsize, int wbase, int gran) { 275 super(par); 276 this.a = a; this.w = w; 277 this.lbase = lbase; this.lsize = lsize; 278 this.rbase = rbase; this.rsize = rsize; 279 this.wbase = wbase; this.gran = gran; 280 } 281 282 public final void compute() { 283 byte[] a = this.a, w = this.w; // localize all params 284 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 285 rn = this.rsize, k = this.wbase, g = this.gran; 286 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 287 throw new IllegalStateException(); // hoist checks 288 for (int lh, rh;;) { // split larger, find point in smaller 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; 350 Sorter(CountedCompleter<?> par, char[] a, char[] w, int base, 351 int size, int wbase, int gran) { 352 super(par); 353 this.a = a; this.w = w; this.base = base; this.size = size; 354 this.wbase = wbase; this.gran = gran; 355 } 356 public final void compute() { 357 CountedCompleter<?> s = this; 358 char[] a = this.a, w = this.w; // localize all params 359 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 360 while (n > g) { 361 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 362 Relay fc = new Relay(new Merger(s, w, a, wb, h, 363 wb+h, n-h, b, g)); 364 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 365 b+u, n-u, wb+h, g)); 366 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 367 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 368 Relay bc = new Relay(new Merger(fc, a, w, b, q, 369 b+q, h-q, wb, g)); 370 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 371 s = new EmptyCompleter(bc); 372 n = q; 373 } 374 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); 375 s.tryComplete(); 376 } 377 } 378 379 static final class Merger extends CountedCompleter<Void> { 380 static final long serialVersionUID = 2446542900576103244L; 381 final char[] a, w; // main and workspace arrays 382 final int lbase, lsize, rbase, rsize, wbase, gran; 383 Merger(CountedCompleter<?> par, char[] a, char[] w, 384 int lbase, int lsize, int rbase, 385 int rsize, int wbase, int gran) { 386 super(par); 387 this.a = a; this.w = w; 388 this.lbase = lbase; this.lsize = lsize; 389 this.rbase = rbase; this.rsize = rsize; 390 this.wbase = wbase; this.gran = gran; 391 } 392 393 public final void compute() { 394 char[] a = this.a, w = this.w; // localize all params 395 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 396 rn = this.rsize, k = this.wbase, g = this.gran; 397 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 398 throw new IllegalStateException(); // hoist checks 399 for (int lh, rh;;) { // split larger, find point in smaller 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; 461 Sorter(CountedCompleter<?> par, short[] a, short[] w, int base, 462 int size, int wbase, int gran) { 463 super(par); 464 this.a = a; this.w = w; this.base = base; this.size = size; 465 this.wbase = wbase; this.gran = gran; 466 } 467 public final void compute() { 468 CountedCompleter<?> s = this; 469 short[] a = this.a, w = this.w; // localize all params 470 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 471 while (n > g) { 472 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 473 Relay fc = new Relay(new Merger(s, w, a, wb, h, 474 wb+h, n-h, b, g)); 475 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 476 b+u, n-u, wb+h, g)); 477 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 478 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 479 Relay bc = new Relay(new Merger(fc, a, w, b, q, 480 b+q, h-q, wb, g)); 481 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 482 s = new EmptyCompleter(bc); 483 n = q; 484 } 485 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); 486 s.tryComplete(); 487 } 488 } 489 490 static final class Merger extends CountedCompleter<Void> { 491 static final long serialVersionUID = 2446542900576103244L; 492 final short[] a, w; // main and workspace arrays 493 final int lbase, lsize, rbase, rsize, wbase, gran; 494 Merger(CountedCompleter<?> par, short[] a, short[] w, 495 int lbase, int lsize, int rbase, 496 int rsize, int wbase, int gran) { 497 super(par); 498 this.a = a; this.w = w; 499 this.lbase = lbase; this.lsize = lsize; 500 this.rbase = rbase; this.rsize = rsize; 501 this.wbase = wbase; this.gran = gran; 502 } 503 504 public final void compute() { 505 short[] a = this.a, w = this.w; // localize all params 506 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 507 rn = this.rsize, k = this.wbase, g = this.gran; 508 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 509 throw new IllegalStateException(); // hoist checks 510 for (int lh, rh;;) { // split larger, find point in smaller 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; 572 Sorter(CountedCompleter<?> par, int[] a, int[] w, int base, 573 int size, int wbase, int gran) { 574 super(par); 575 this.a = a; this.w = w; this.base = base; this.size = size; 576 this.wbase = wbase; this.gran = gran; 577 } 578 public final void compute() { 579 CountedCompleter<?> s = this; 580 int[] a = this.a, w = this.w; // localize all params 581 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 582 while (n > g) { 583 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 584 Relay fc = new Relay(new Merger(s, w, a, wb, h, 585 wb+h, n-h, b, g)); 586 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 587 b+u, n-u, wb+h, g)); 588 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 589 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 590 Relay bc = new Relay(new Merger(fc, a, w, b, q, 591 b+q, h-q, wb, g)); 592 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 593 s = new EmptyCompleter(bc); 594 n = q; 595 } 596 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); 597 s.tryComplete(); 598 } 599 } 600 601 static final class Merger extends CountedCompleter<Void> { 602 static final long serialVersionUID = 2446542900576103244L; 603 final int[] a, w; // main and workspace arrays 604 final int lbase, lsize, rbase, rsize, wbase, gran; 605 Merger(CountedCompleter<?> par, int[] a, int[] w, 606 int lbase, int lsize, int rbase, 607 int rsize, int wbase, int gran) { 608 super(par); 609 this.a = a; this.w = w; 610 this.lbase = lbase; this.lsize = lsize; 611 this.rbase = rbase; this.rsize = rsize; 612 this.wbase = wbase; this.gran = gran; 613 } 614 615 public final void compute() { 616 int[] a = this.a, w = this.w; // localize all params 617 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 618 rn = this.rsize, k = this.wbase, g = this.gran; 619 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 620 throw new IllegalStateException(); // hoist checks 621 for (int lh, rh;;) { // split larger, find point in smaller 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; 683 Sorter(CountedCompleter<?> par, long[] a, long[] w, int base, 684 int size, int wbase, int gran) { 685 super(par); 686 this.a = a; this.w = w; this.base = base; this.size = size; 687 this.wbase = wbase; this.gran = gran; 688 } 689 public final void compute() { 690 CountedCompleter<?> s = this; 691 long[] a = this.a, w = this.w; // localize all params 692 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 693 while (n > g) { 694 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 695 Relay fc = new Relay(new Merger(s, w, a, wb, h, 696 wb+h, n-h, b, g)); 697 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 698 b+u, n-u, wb+h, g)); 699 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 700 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 701 Relay bc = new Relay(new Merger(fc, a, w, b, q, 702 b+q, h-q, wb, g)); 703 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 704 s = new EmptyCompleter(bc); 705 n = q; 706 } 707 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); 708 s.tryComplete(); 709 } 710 } 711 712 static final class Merger extends CountedCompleter<Void> { 713 static final long serialVersionUID = 2446542900576103244L; 714 final long[] a, w; // main and workspace arrays 715 final int lbase, lsize, rbase, rsize, wbase, gran; 716 Merger(CountedCompleter<?> par, long[] a, long[] w, 717 int lbase, int lsize, int rbase, 718 int rsize, int wbase, int gran) { 719 super(par); 720 this.a = a; this.w = w; 721 this.lbase = lbase; this.lsize = lsize; 722 this.rbase = rbase; this.rsize = rsize; 723 this.wbase = wbase; this.gran = gran; 724 } 725 726 public final void compute() { 727 long[] a = this.a, w = this.w; // localize all params 728 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 729 rn = this.rsize, k = this.wbase, g = this.gran; 730 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 731 throw new IllegalStateException(); // hoist checks 732 for (int lh, rh;;) { // split larger, find point in smaller 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; 794 Sorter(CountedCompleter<?> par, float[] a, float[] w, int base, 795 int size, int wbase, int gran) { 796 super(par); 797 this.a = a; this.w = w; this.base = base; this.size = size; 798 this.wbase = wbase; this.gran = gran; 799 } 800 public final void compute() { 801 CountedCompleter<?> s = this; 802 float[] a = this.a, w = this.w; // localize all params 803 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 804 while (n > g) { 805 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 806 Relay fc = new Relay(new Merger(s, w, a, wb, h, 807 wb+h, n-h, b, g)); 808 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 809 b+u, n-u, wb+h, g)); 810 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 811 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 812 Relay bc = new Relay(new Merger(fc, a, w, b, q, 813 b+q, h-q, wb, g)); 814 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 815 s = new EmptyCompleter(bc); 816 n = q; 817 } 818 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); 819 s.tryComplete(); 820 } 821 } 822 823 static final class Merger extends CountedCompleter<Void> { 824 static final long serialVersionUID = 2446542900576103244L; 825 final float[] a, w; // main and workspace arrays 826 final int lbase, lsize, rbase, rsize, wbase, gran; 827 Merger(CountedCompleter<?> par, float[] a, float[] w, 828 int lbase, int lsize, int rbase, 829 int rsize, int wbase, int gran) { 830 super(par); 831 this.a = a; this.w = w; 832 this.lbase = lbase; this.lsize = lsize; 833 this.rbase = rbase; this.rsize = rsize; 834 this.wbase = wbase; this.gran = gran; 835 } 836 837 public final void compute() { 838 float[] a = this.a, w = this.w; // localize all params 839 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 840 rn = this.rsize, k = this.wbase, g = this.gran; 841 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 842 throw new IllegalStateException(); // hoist checks 843 for (int lh, rh;;) { // split larger, find point in smaller 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; 905 Sorter(CountedCompleter<?> par, double[] a, double[] w, int base, 906 int size, int wbase, int gran) { 907 super(par); 908 this.a = a; this.w = w; this.base = base; this.size = size; 909 this.wbase = wbase; this.gran = gran; 910 } 911 public final void compute() { 912 CountedCompleter<?> s = this; 913 double[] a = this.a, w = this.w; // localize all params 914 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 915 while (n > g) { 916 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 917 Relay fc = new Relay(new Merger(s, w, a, wb, h, 918 wb+h, n-h, b, g)); 919 Relay rc = new Relay(new Merger(fc, a, w, b+h, q, 920 b+u, n-u, wb+h, g)); 921 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); 922 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; 923 Relay bc = new Relay(new Merger(fc, a, w, b, q, 924 b+q, h-q, wb, g)); 925 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); 926 s = new EmptyCompleter(bc); 927 n = q; 928 } 929 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); 930 s.tryComplete(); 931 } 932 } 933 934 static final class Merger extends CountedCompleter<Void> { 935 static final long serialVersionUID = 2446542900576103244L; 936 final double[] a, w; // main and workspace arrays 937 final int lbase, lsize, rbase, rsize, wbase, gran; 938 Merger(CountedCompleter<?> par, double[] a, double[] w, 939 int lbase, int lsize, int rbase, 940 int rsize, int wbase, int gran) { 941 super(par); 942 this.a = a; this.w = w; 943 this.lbase = lbase; this.lsize = lsize; 944 this.rbase = rbase; this.rsize = rsize; 945 this.wbase = wbase; this.gran = gran; 946 } 947 948 public final void compute() { 949 double[] a = this.a, w = this.w; // localize all params 950 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 951 rn = this.rsize, k = this.wbase, g = this.gran; 952 if (a == null || w == null || lb < 0 || rb < 0 || k < 0) 953 throw new IllegalStateException(); // hoist checks 954 for (int lh, rh;;) { // split larger, find point in smaller 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 } |