1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Doug Lea with assistance from members of JCP JSR-166 32 * Expert Group and released to the public domain, as explained at 33 * http://creativecommons.org/publicdomain/zero/1.0/ 34 */ 35 36 package java.util; 37 38 import java.util.concurrent.CountedCompleter; 39 import java.util.concurrent.ForkJoinPool; 40 import java.util.function.BinaryOperator; 41 import java.util.function.DoubleBinaryOperator; 42 import java.util.function.IntBinaryOperator; 43 import java.util.function.LongBinaryOperator; 44 45 /** 46 * ForkJoin tasks to perform Arrays.parallelPrefix operations. 47 * 48 * @author Doug Lea 49 * @since 1.8 50 */ 51 class ArrayPrefixHelpers { ArrayPrefixHelpers()52 private ArrayPrefixHelpers() {} // non-instantiable 53 54 /* 55 * Parallel prefix (aka cumulate, scan) task classes 56 * are based loosely on Guy Blelloch's original 57 * algorithm (http://www.cs.cmu.edu/~scandal/alg/scan.html): 58 * Keep dividing by two to threshold segment size, and then: 59 * Pass 1: Create tree of partial sums for each segment 60 * Pass 2: For each segment, cumulate with offset of left sibling 61 * 62 * This version improves performance within FJ framework mainly by 63 * allowing the second pass of ready left-hand sides to proceed 64 * even if some right-hand side first passes are still executing. 65 * It also combines first and second pass for leftmost segment, 66 * and skips the first pass for rightmost segment (whose result is 67 * not needed for second pass). It similarly manages to avoid 68 * requiring that users supply an identity basis for accumulations 69 * by tracking those segments/subtasks for which the first 70 * existing element is used as base. 71 * 72 * Managing this relies on ORing some bits in the pendingCount for 73 * phases/states: CUMULATE, SUMMED, and FINISHED. CUMULATE is the 74 * main phase bit. When false, segments compute only their sum. 75 * When true, they cumulate array elements. CUMULATE is set at 76 * root at beginning of second pass and then propagated down. But 77 * it may also be set earlier for subtrees with lo==0 (the left 78 * spine of tree). SUMMED is a one bit join count. For leafs, it 79 * is set when summed. For internal nodes, it becomes true when 80 * one child is summed. When the second child finishes summing, 81 * we then moves up tree to trigger the cumulate phase. FINISHED 82 * is also a one bit join count. For leafs, it is set when 83 * cumulated. For internal nodes, it becomes true when one child 84 * is cumulated. When the second child finishes cumulating, it 85 * then moves up tree, completing at the root. 86 * 87 * To better exploit locality and reduce overhead, the compute 88 * method loops starting with the current task, moving if possible 89 * to one of its subtasks rather than forking. 90 * 91 * As usual for this sort of utility, there are 4 versions, that 92 * are simple copy/paste/adapt variants of each other. (The 93 * double and int versions differ from long version solely by 94 * replacing "long" (with case-matching)). 95 */ 96 97 // see above 98 static final int CUMULATE = 1; 99 static final int SUMMED = 2; 100 static final int FINISHED = 4; 101 102 /** The smallest subtask array partition size to use as threshold */ 103 static final int MIN_PARTITION = 16; 104 105 static final class CumulateTask<T> extends CountedCompleter<Void> { 106 final T[] array; 107 final BinaryOperator<T> function; 108 CumulateTask<T> left, right; 109 T in, out; 110 final int lo, hi, origin, fence, threshold; 111 112 /** Root task constructor */ CumulateTask(CumulateTask<T> parent, BinaryOperator<T> function, T[] array, int lo, int hi)113 public CumulateTask(CumulateTask<T> parent, 114 BinaryOperator<T> function, 115 T[] array, int lo, int hi) { 116 super(parent); 117 this.function = function; this.array = array; 118 this.lo = this.origin = lo; this.hi = this.fence = hi; 119 int p; 120 this.threshold = 121 (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 122 <= MIN_PARTITION ? MIN_PARTITION : p; 123 } 124 125 /** Subtask constructor */ CumulateTask(CumulateTask<T> parent, BinaryOperator<T> function, T[] array, int origin, int fence, int threshold, int lo, int hi)126 CumulateTask(CumulateTask<T> parent, BinaryOperator<T> function, 127 T[] array, int origin, int fence, int threshold, 128 int lo, int hi) { 129 super(parent); 130 this.function = function; this.array = array; 131 this.origin = origin; this.fence = fence; 132 this.threshold = threshold; 133 this.lo = lo; this.hi = hi; 134 } 135 compute()136 public final void compute() { 137 final BinaryOperator<T> fn; 138 final T[] a; 139 if ((fn = this.function) == null || (a = this.array) == null) 140 throw new NullPointerException(); // hoist checks 141 int th = threshold, org = origin, fnc = fence, l, h; 142 CumulateTask<T> t = this; 143 outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 144 if (h - l > th) { 145 CumulateTask<T> lt = t.left, rt = t.right, f; 146 if (lt == null) { // first pass 147 int mid = (l + h) >>> 1; 148 f = rt = t.right = 149 new CumulateTask<T>(t, fn, a, org, fnc, th, mid, h); 150 t = lt = t.left = 151 new CumulateTask<T>(t, fn, a, org, fnc, th, l, mid); 152 } 153 else { // possibly refork 154 T pin = t.in; 155 lt.in = pin; 156 f = t = null; 157 if (rt != null) { 158 T lout = lt.out; 159 rt.in = (l == org ? lout : 160 fn.apply(pin, lout)); 161 for (int c;;) { 162 if (((c = rt.getPendingCount()) & CUMULATE) != 0) 163 break; 164 if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 165 t = rt; 166 break; 167 } 168 } 169 } 170 for (int c;;) { 171 if (((c = lt.getPendingCount()) & CUMULATE) != 0) 172 break; 173 if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 174 if (t != null) 175 f = t; 176 t = lt; 177 break; 178 } 179 } 180 if (t == null) 181 break; 182 } 183 if (f != null) 184 f.fork(); 185 } 186 else { 187 int state; // Transition to sum, cumulate, or both 188 for (int b;;) { 189 if (((b = t.getPendingCount()) & FINISHED) != 0) 190 break outer; // already done 191 state = ((b & CUMULATE) != 0 ? FINISHED : 192 (l > org) ? SUMMED : (SUMMED|FINISHED)); 193 if (t.compareAndSetPendingCount(b, b|state)) 194 break; 195 } 196 197 T sum; 198 if (state != SUMMED) { 199 int first; 200 if (l == org) { // leftmost; no in 201 sum = a[org]; 202 first = org + 1; 203 } 204 else { 205 sum = t.in; 206 first = l; 207 } 208 for (int i = first; i < h; ++i) // cumulate 209 a[i] = sum = fn.apply(sum, a[i]); 210 } 211 else if (h < fnc) { // skip rightmost 212 sum = a[l]; 213 for (int i = l + 1; i < h; ++i) // sum only 214 sum = fn.apply(sum, a[i]); 215 } 216 else 217 sum = t.in; 218 t.out = sum; 219 for (CumulateTask<T> par;;) { // propagate 220 @SuppressWarnings("unchecked") CumulateTask<T> partmp 221 = (CumulateTask<T>)t.getCompleter(); 222 if ((par = partmp) == null) { 223 if ((state & FINISHED) != 0) // enable join 224 t.quietlyComplete(); 225 break outer; 226 } 227 int b = par.getPendingCount(); 228 if ((b & state & FINISHED) != 0) 229 t = par; // both done 230 else if ((b & state & SUMMED) != 0) { // both summed 231 int nextState; CumulateTask<T> lt, rt; 232 if ((lt = par.left) != null && 233 (rt = par.right) != null) { 234 T lout = lt.out; 235 par.out = (rt.hi == fnc ? lout : 236 fn.apply(lout, rt.out)); 237 } 238 int refork = (((b & CUMULATE) == 0 && 239 par.lo == org) ? CUMULATE : 0); 240 if ((nextState = b|state|refork) == b || 241 par.compareAndSetPendingCount(b, nextState)) { 242 state = SUMMED; // drop finished 243 t = par; 244 if (refork != 0) 245 par.fork(); 246 } 247 } 248 else if (par.compareAndSetPendingCount(b, b|state)) 249 break outer; // sib not ready 250 } 251 } 252 } 253 } 254 private static final long serialVersionUID = 5293554502939613543L; 255 } 256 257 static final class LongCumulateTask extends CountedCompleter<Void> { 258 final long[] array; 259 final LongBinaryOperator function; 260 LongCumulateTask left, right; 261 long in, out; 262 final int lo, hi, origin, fence, threshold; 263 264 /** Root task constructor */ LongCumulateTask(LongCumulateTask parent, LongBinaryOperator function, long[] array, int lo, int hi)265 public LongCumulateTask(LongCumulateTask parent, 266 LongBinaryOperator function, 267 long[] array, int lo, int hi) { 268 super(parent); 269 this.function = function; this.array = array; 270 this.lo = this.origin = lo; this.hi = this.fence = hi; 271 int p; 272 this.threshold = 273 (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 274 <= MIN_PARTITION ? MIN_PARTITION : p; 275 } 276 277 /** Subtask constructor */ LongCumulateTask(LongCumulateTask parent, LongBinaryOperator function, long[] array, int origin, int fence, int threshold, int lo, int hi)278 LongCumulateTask(LongCumulateTask parent, LongBinaryOperator function, 279 long[] array, int origin, int fence, int threshold, 280 int lo, int hi) { 281 super(parent); 282 this.function = function; this.array = array; 283 this.origin = origin; this.fence = fence; 284 this.threshold = threshold; 285 this.lo = lo; this.hi = hi; 286 } 287 compute()288 public final void compute() { 289 final LongBinaryOperator fn; 290 final long[] a; 291 if ((fn = this.function) == null || (a = this.array) == null) 292 throw new NullPointerException(); // hoist checks 293 int th = threshold, org = origin, fnc = fence, l, h; 294 LongCumulateTask t = this; 295 outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 296 if (h - l > th) { 297 LongCumulateTask lt = t.left, rt = t.right, f; 298 if (lt == null) { // first pass 299 int mid = (l + h) >>> 1; 300 f = rt = t.right = 301 new LongCumulateTask(t, fn, a, org, fnc, th, mid, h); 302 t = lt = t.left = 303 new LongCumulateTask(t, fn, a, org, fnc, th, l, mid); 304 } 305 else { // possibly refork 306 long pin = t.in; 307 lt.in = pin; 308 f = t = null; 309 if (rt != null) { 310 long lout = lt.out; 311 rt.in = (l == org ? lout : 312 fn.applyAsLong(pin, lout)); 313 for (int c;;) { 314 if (((c = rt.getPendingCount()) & CUMULATE) != 0) 315 break; 316 if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 317 t = rt; 318 break; 319 } 320 } 321 } 322 for (int c;;) { 323 if (((c = lt.getPendingCount()) & CUMULATE) != 0) 324 break; 325 if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 326 if (t != null) 327 f = t; 328 t = lt; 329 break; 330 } 331 } 332 if (t == null) 333 break; 334 } 335 if (f != null) 336 f.fork(); 337 } 338 else { 339 int state; // Transition to sum, cumulate, or both 340 for (int b;;) { 341 if (((b = t.getPendingCount()) & FINISHED) != 0) 342 break outer; // already done 343 state = ((b & CUMULATE) != 0 ? FINISHED : 344 (l > org) ? SUMMED : (SUMMED|FINISHED)); 345 if (t.compareAndSetPendingCount(b, b|state)) 346 break; 347 } 348 349 long sum; 350 if (state != SUMMED) { 351 int first; 352 if (l == org) { // leftmost; no in 353 sum = a[org]; 354 first = org + 1; 355 } 356 else { 357 sum = t.in; 358 first = l; 359 } 360 for (int i = first; i < h; ++i) // cumulate 361 a[i] = sum = fn.applyAsLong(sum, a[i]); 362 } 363 else if (h < fnc) { // skip rightmost 364 sum = a[l]; 365 for (int i = l + 1; i < h; ++i) // sum only 366 sum = fn.applyAsLong(sum, a[i]); 367 } 368 else 369 sum = t.in; 370 t.out = sum; 371 for (LongCumulateTask par;;) { // propagate 372 if ((par = (LongCumulateTask)t.getCompleter()) == null) { 373 if ((state & FINISHED) != 0) // enable join 374 t.quietlyComplete(); 375 break outer; 376 } 377 int b = par.getPendingCount(); 378 if ((b & state & FINISHED) != 0) 379 t = par; // both done 380 else if ((b & state & SUMMED) != 0) { // both summed 381 int nextState; LongCumulateTask lt, rt; 382 if ((lt = par.left) != null && 383 (rt = par.right) != null) { 384 long lout = lt.out; 385 par.out = (rt.hi == fnc ? lout : 386 fn.applyAsLong(lout, rt.out)); 387 } 388 int refork = (((b & CUMULATE) == 0 && 389 par.lo == org) ? CUMULATE : 0); 390 if ((nextState = b|state|refork) == b || 391 par.compareAndSetPendingCount(b, nextState)) { 392 state = SUMMED; // drop finished 393 t = par; 394 if (refork != 0) 395 par.fork(); 396 } 397 } 398 else if (par.compareAndSetPendingCount(b, b|state)) 399 break outer; // sib not ready 400 } 401 } 402 } 403 } 404 private static final long serialVersionUID = -5074099945909284273L; 405 } 406 407 static final class DoubleCumulateTask extends CountedCompleter<Void> { 408 final double[] array; 409 final DoubleBinaryOperator function; 410 DoubleCumulateTask left, right; 411 double in, out; 412 final int lo, hi, origin, fence, threshold; 413 414 /** Root task constructor */ DoubleCumulateTask(DoubleCumulateTask parent, DoubleBinaryOperator function, double[] array, int lo, int hi)415 public DoubleCumulateTask(DoubleCumulateTask parent, 416 DoubleBinaryOperator function, 417 double[] array, int lo, int hi) { 418 super(parent); 419 this.function = function; this.array = array; 420 this.lo = this.origin = lo; this.hi = this.fence = hi; 421 int p; 422 this.threshold = 423 (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 424 <= MIN_PARTITION ? MIN_PARTITION : p; 425 } 426 427 /** Subtask constructor */ DoubleCumulateTask(DoubleCumulateTask parent, DoubleBinaryOperator function, double[] array, int origin, int fence, int threshold, int lo, int hi)428 DoubleCumulateTask(DoubleCumulateTask parent, DoubleBinaryOperator function, 429 double[] array, int origin, int fence, int threshold, 430 int lo, int hi) { 431 super(parent); 432 this.function = function; this.array = array; 433 this.origin = origin; this.fence = fence; 434 this.threshold = threshold; 435 this.lo = lo; this.hi = hi; 436 } 437 compute()438 public final void compute() { 439 final DoubleBinaryOperator fn; 440 final double[] a; 441 if ((fn = this.function) == null || (a = this.array) == null) 442 throw new NullPointerException(); // hoist checks 443 int th = threshold, org = origin, fnc = fence, l, h; 444 DoubleCumulateTask t = this; 445 outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 446 if (h - l > th) { 447 DoubleCumulateTask lt = t.left, rt = t.right, f; 448 if (lt == null) { // first pass 449 int mid = (l + h) >>> 1; 450 f = rt = t.right = 451 new DoubleCumulateTask(t, fn, a, org, fnc, th, mid, h); 452 t = lt = t.left = 453 new DoubleCumulateTask(t, fn, a, org, fnc, th, l, mid); 454 } 455 else { // possibly refork 456 double pin = t.in; 457 lt.in = pin; 458 f = t = null; 459 if (rt != null) { 460 double lout = lt.out; 461 rt.in = (l == org ? lout : 462 fn.applyAsDouble(pin, lout)); 463 for (int c;;) { 464 if (((c = rt.getPendingCount()) & CUMULATE) != 0) 465 break; 466 if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 467 t = rt; 468 break; 469 } 470 } 471 } 472 for (int c;;) { 473 if (((c = lt.getPendingCount()) & CUMULATE) != 0) 474 break; 475 if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 476 if (t != null) 477 f = t; 478 t = lt; 479 break; 480 } 481 } 482 if (t == null) 483 break; 484 } 485 if (f != null) 486 f.fork(); 487 } 488 else { 489 int state; // Transition to sum, cumulate, or both 490 for (int b;;) { 491 if (((b = t.getPendingCount()) & FINISHED) != 0) 492 break outer; // already done 493 state = ((b & CUMULATE) != 0 ? FINISHED : 494 (l > org) ? SUMMED : (SUMMED|FINISHED)); 495 if (t.compareAndSetPendingCount(b, b|state)) 496 break; 497 } 498 499 double sum; 500 if (state != SUMMED) { 501 int first; 502 if (l == org) { // leftmost; no in 503 sum = a[org]; 504 first = org + 1; 505 } 506 else { 507 sum = t.in; 508 first = l; 509 } 510 for (int i = first; i < h; ++i) // cumulate 511 a[i] = sum = fn.applyAsDouble(sum, a[i]); 512 } 513 else if (h < fnc) { // skip rightmost 514 sum = a[l]; 515 for (int i = l + 1; i < h; ++i) // sum only 516 sum = fn.applyAsDouble(sum, a[i]); 517 } 518 else 519 sum = t.in; 520 t.out = sum; 521 for (DoubleCumulateTask par;;) { // propagate 522 if ((par = (DoubleCumulateTask)t.getCompleter()) == null) { 523 if ((state & FINISHED) != 0) // enable join 524 t.quietlyComplete(); 525 break outer; 526 } 527 int b = par.getPendingCount(); 528 if ((b & state & FINISHED) != 0) 529 t = par; // both done 530 else if ((b & state & SUMMED) != 0) { // both summed 531 int nextState; DoubleCumulateTask lt, rt; 532 if ((lt = par.left) != null && 533 (rt = par.right) != null) { 534 double lout = lt.out; 535 par.out = (rt.hi == fnc ? lout : 536 fn.applyAsDouble(lout, rt.out)); 537 } 538 int refork = (((b & CUMULATE) == 0 && 539 par.lo == org) ? CUMULATE : 0); 540 if ((nextState = b|state|refork) == b || 541 par.compareAndSetPendingCount(b, nextState)) { 542 state = SUMMED; // drop finished 543 t = par; 544 if (refork != 0) 545 par.fork(); 546 } 547 } 548 else if (par.compareAndSetPendingCount(b, b|state)) 549 break outer; // sib not ready 550 } 551 } 552 } 553 } 554 private static final long serialVersionUID = -586947823794232033L; 555 } 556 557 static final class IntCumulateTask extends CountedCompleter<Void> { 558 final int[] array; 559 final IntBinaryOperator function; 560 IntCumulateTask left, right; 561 int in, out; 562 final int lo, hi, origin, fence, threshold; 563 564 /** Root task constructor */ IntCumulateTask(IntCumulateTask parent, IntBinaryOperator function, int[] array, int lo, int hi)565 public IntCumulateTask(IntCumulateTask parent, 566 IntBinaryOperator function, 567 int[] array, int lo, int hi) { 568 super(parent); 569 this.function = function; this.array = array; 570 this.lo = this.origin = lo; this.hi = this.fence = hi; 571 int p; 572 this.threshold = 573 (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3)) 574 <= MIN_PARTITION ? MIN_PARTITION : p; 575 } 576 577 /** Subtask constructor */ IntCumulateTask(IntCumulateTask parent, IntBinaryOperator function, int[] array, int origin, int fence, int threshold, int lo, int hi)578 IntCumulateTask(IntCumulateTask parent, IntBinaryOperator function, 579 int[] array, int origin, int fence, int threshold, 580 int lo, int hi) { 581 super(parent); 582 this.function = function; this.array = array; 583 this.origin = origin; this.fence = fence; 584 this.threshold = threshold; 585 this.lo = lo; this.hi = hi; 586 } 587 compute()588 public final void compute() { 589 final IntBinaryOperator fn; 590 final int[] a; 591 if ((fn = this.function) == null || (a = this.array) == null) 592 throw new NullPointerException(); // hoist checks 593 int th = threshold, org = origin, fnc = fence, l, h; 594 IntCumulateTask t = this; 595 outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) { 596 if (h - l > th) { 597 IntCumulateTask lt = t.left, rt = t.right, f; 598 if (lt == null) { // first pass 599 int mid = (l + h) >>> 1; 600 f = rt = t.right = 601 new IntCumulateTask(t, fn, a, org, fnc, th, mid, h); 602 t = lt = t.left = 603 new IntCumulateTask(t, fn, a, org, fnc, th, l, mid); 604 } 605 else { // possibly refork 606 int pin = t.in; 607 lt.in = pin; 608 f = t = null; 609 if (rt != null) { 610 int lout = lt.out; 611 rt.in = (l == org ? lout : 612 fn.applyAsInt(pin, lout)); 613 for (int c;;) { 614 if (((c = rt.getPendingCount()) & CUMULATE) != 0) 615 break; 616 if (rt.compareAndSetPendingCount(c, c|CUMULATE)){ 617 t = rt; 618 break; 619 } 620 } 621 } 622 for (int c;;) { 623 if (((c = lt.getPendingCount()) & CUMULATE) != 0) 624 break; 625 if (lt.compareAndSetPendingCount(c, c|CUMULATE)) { 626 if (t != null) 627 f = t; 628 t = lt; 629 break; 630 } 631 } 632 if (t == null) 633 break; 634 } 635 if (f != null) 636 f.fork(); 637 } 638 else { 639 int state; // Transition to sum, cumulate, or both 640 for (int b;;) { 641 if (((b = t.getPendingCount()) & FINISHED) != 0) 642 break outer; // already done 643 state = ((b & CUMULATE) != 0 ? FINISHED : 644 (l > org) ? SUMMED : (SUMMED|FINISHED)); 645 if (t.compareAndSetPendingCount(b, b|state)) 646 break; 647 } 648 649 int sum; 650 if (state != SUMMED) { 651 int first; 652 if (l == org) { // leftmost; no in 653 sum = a[org]; 654 first = org + 1; 655 } 656 else { 657 sum = t.in; 658 first = l; 659 } 660 for (int i = first; i < h; ++i) // cumulate 661 a[i] = sum = fn.applyAsInt(sum, a[i]); 662 } 663 else if (h < fnc) { // skip rightmost 664 sum = a[l]; 665 for (int i = l + 1; i < h; ++i) // sum only 666 sum = fn.applyAsInt(sum, a[i]); 667 } 668 else 669 sum = t.in; 670 t.out = sum; 671 for (IntCumulateTask par;;) { // propagate 672 if ((par = (IntCumulateTask)t.getCompleter()) == null) { 673 if ((state & FINISHED) != 0) // enable join 674 t.quietlyComplete(); 675 break outer; 676 } 677 int b = par.getPendingCount(); 678 if ((b & state & FINISHED) != 0) 679 t = par; // both done 680 else if ((b & state & SUMMED) != 0) { // both summed 681 int nextState; IntCumulateTask lt, rt; 682 if ((lt = par.left) != null && 683 (rt = par.right) != null) { 684 int lout = lt.out; 685 par.out = (rt.hi == fnc ? lout : 686 fn.applyAsInt(lout, rt.out)); 687 } 688 int refork = (((b & CUMULATE) == 0 && 689 par.lo == org) ? CUMULATE : 0); 690 if ((nextState = b|state|refork) == b || 691 par.compareAndSetPendingCount(b, nextState)) { 692 state = SUMMED; // drop finished 693 t = par; 694 if (refork != 0) 695 par.fork(); 696 } 697 } 698 else if (par.compareAndSetPendingCount(b, b|state)) 699 break outer; // sib not ready 700 } 701 } 702 } 703 } 704 private static final long serialVersionUID = 3731755594596840961L; 705 } 706 } 707