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.concurrent;
  37 
  38 import java.lang.invoke.MethodHandles;
  39 import java.lang.invoke.VarHandle;
  40 
  41 /**
  42  * A {@link ForkJoinTask} with a completion action performed when
  43  * triggered and there are no remaining pending actions.
  44  * CountedCompleters are in general more robust in the
  45  * presence of subtask stalls and blockage than are other forms of
  46  * ForkJoinTasks, but are less intuitive to program.  Uses of
  47  * CountedCompleter are similar to those of other completion based
  48  * components (such as {@link java.nio.channels.CompletionHandler})
  49  * except that multiple <em>pending</em> completions may be necessary
  50  * to trigger the completion action {@link #onCompletion(CountedCompleter)},
  51  * not just one.
  52  * Unless initialized otherwise, the {@linkplain #getPendingCount pending
  53  * count} starts at zero, but may be (atomically) changed using
  54  * methods {@link #setPendingCount}, {@link #addToPendingCount}, and
  55  * {@link #compareAndSetPendingCount}. Upon invocation of {@link
  56  * #tryComplete}, if the pending action count is nonzero, it is
  57  * decremented; otherwise, the completion action is performed, and if
  58  * this completer itself has a completer, the process is continued
  59  * with its completer.  As is the case with related synchronization
  60  * components such as {@link Phaser} and {@link Semaphore}, these methods
  61  * affect only internal counts; they do not establish any further
  62  * internal bookkeeping. In particular, the identities of pending
  63  * tasks are not maintained. As illustrated below, you can create
  64  * subclasses that do record some or all pending tasks or their
  65  * results when needed.  As illustrated below, utility methods
  66  * supporting customization of completion traversals are also
  67  * provided. However, because CountedCompleters provide only basic
  68  * synchronization mechanisms, it may be useful to create further
  69  * abstract subclasses that maintain linkages, fields, and additional
  70  * support methods appropriate for a set of related usages.
  71  *
  72  * <p>A concrete CountedCompleter class must define method {@link
  73  * #compute}, that should in most cases (as illustrated below), invoke
  74  * {@code tryComplete()} once before returning. The class may also
  75  * optionally override method {@link #onCompletion(CountedCompleter)}
  76  * to perform an action upon normal completion, and method
  77  * {@link #onExceptionalCompletion(Throwable, CountedCompleter)} to
  78  * perform an action upon any exception.
  79  *
  80  * <p>CountedCompleters most often do not bear results, in which case
  81  * they are normally declared as {@code CountedCompleter<Void>}, and
  82  * will always return {@code null} as a result value.  In other cases,
  83  * you should override method {@link #getRawResult} to provide a
  84  * result from {@code join(), invoke()}, and related methods.  In
  85  * general, this method should return the value of a field (or a
  86  * function of one or more fields) of the CountedCompleter object that
  87  * holds the result upon completion. Method {@link #setRawResult} by
  88  * default plays no role in CountedCompleters.  It is possible, but
  89  * rarely applicable, to override this method to maintain other
  90  * objects or fields holding result data.
  91  *
  92  * <p>A CountedCompleter that does not itself have a completer (i.e.,
  93  * one for which {@link #getCompleter} returns {@code null}) can be
  94  * used as a regular ForkJoinTask with this added functionality.
  95  * However, any completer that in turn has another completer serves
  96  * only as an internal helper for other computations, so its own task
  97  * status (as reported in methods such as {@link ForkJoinTask#isDone})
  98  * is arbitrary; this status changes only upon explicit invocations of
  99  * {@link #complete}, {@link ForkJoinTask#cancel},
 100  * {@link ForkJoinTask#completeExceptionally(Throwable)} or upon
 101  * exceptional completion of method {@code compute}. Upon any
 102  * exceptional completion, the exception may be relayed to a task's
 103  * completer (and its completer, and so on), if one exists and it has
 104  * not otherwise already completed. Similarly, cancelling an internal
 105  * CountedCompleter has only a local effect on that completer, so is
 106  * not often useful.
 107  *
 108  * <p><b>Sample Usages.</b>
 109  *
 110  * <p><b>Parallel recursive decomposition.</b> CountedCompleters may
 111  * be arranged in trees similar to those often used with {@link
 112  * RecursiveAction}s, although the constructions involved in setting
 113  * them up typically vary. Here, the completer of each task is its
 114  * parent in the computation tree. Even though they entail a bit more
 115  * bookkeeping, CountedCompleters may be better choices when applying
 116  * a possibly time-consuming operation (that cannot be further
 117  * subdivided) to each element of an array or collection; especially
 118  * when the operation takes a significantly different amount of time
 119  * to complete for some elements than others, either because of
 120  * intrinsic variation (for example I/O) or auxiliary effects such as
 121  * garbage collection.  Because CountedCompleters provide their own
 122  * continuations, other tasks need not block waiting to perform them.
 123  *
 124  * <p>For example, here is an initial version of a utility method that
 125  * uses divide-by-two recursive decomposition to divide work into
 126  * single pieces (leaf tasks). Even when work is split into individual
 127  * calls, tree-based techniques are usually preferable to directly
 128  * forking leaf tasks, because they reduce inter-thread communication
 129  * and improve load balancing. In the recursive case, the second of
 130  * each pair of subtasks to finish triggers completion of their parent
 131  * (because no result combination is performed, the default no-op
 132  * implementation of method {@code onCompletion} is not overridden).
 133  * The utility method sets up the root task and invokes it (here,
 134  * implicitly using the {@link ForkJoinPool#commonPool()}).  It is
 135  * straightforward and reliable (but not optimal) to always set the
 136  * pending count to the number of child tasks and call {@code
 137  * tryComplete()} immediately before returning.
 138  *
 139  * <pre> {@code
 140  * public static <E> void forEach(E[] array, Consumer<E> action) {
 141  *   class Task extends CountedCompleter<Void> {
 142  *     final int lo, hi;
 143  *     Task(Task parent, int lo, int hi) {
 144  *       super(parent); this.lo = lo; this.hi = hi;
 145  *     }
 146  *
 147  *     public void compute() {
 148  *       if (hi - lo >= 2) {
 149  *         int mid = (lo + hi) >>> 1;
 150  *         // must set pending count before fork
 151  *         setPendingCount(2);
 152  *         new Task(this, mid, hi).fork(); // right child
 153  *         new Task(this, lo, mid).fork(); // left child
 154  *       }
 155  *       else if (hi > lo)
 156  *         action.accept(array[lo]);
 157  *       tryComplete();
 158  *     }
 159  *   }
 160  *   new Task(null, 0, array.length).invoke();
 161  * }}</pre>
 162  *
 163  * This design can be improved by noticing that in the recursive case,
 164  * the task has nothing to do after forking its right task, so can
 165  * directly invoke its left task before returning. (This is an analog
 166  * of tail recursion removal.)  Also, when the last action in a task
 167  * is to fork or invoke a subtask (a "tail call"), the call to {@code
 168  * tryComplete()} can be optimized away, at the cost of making the
 169  * pending count look "off by one".
 170  *
 171  * <pre> {@code
 172  *     public void compute() {
 173  *       if (hi - lo >= 2) {
 174  *         int mid = (lo + hi) >>> 1;
 175  *         setPendingCount(1); // looks off by one, but correct!
 176  *         new Task(this, mid, hi).fork(); // right child
 177  *         new Task(this, lo, mid).compute(); // direct invoke
 178  *       } else {
 179  *         if (hi > lo)
 180  *           action.accept(array[lo]);
 181  *         tryComplete();
 182  *       }
 183  *     }}</pre>
 184  *
 185  * As a further optimization, notice that the left task need not even exist.
 186  * Instead of creating a new one, we can continue using the original task,
 187  * and add a pending count for each fork.  Additionally, because no task
 188  * in this tree implements an {@link #onCompletion(CountedCompleter)} method,
 189  * {@code tryComplete} can be replaced with {@link #propagateCompletion}.
 190  *
 191  * <pre> {@code
 192  *     public void compute() {
 193  *       int n = hi - lo;
 194  *       for (; n >= 2; n /= 2) {
 195  *         addToPendingCount(1);
 196  *         new Task(this, lo + n/2, lo + n).fork();
 197  *       }
 198  *       if (n > 0)
 199  *         action.accept(array[lo]);
 200  *       propagateCompletion();
 201  *     }}</pre>
 202  *
 203  * When pending counts can be precomputed, they can be established in
 204  * the constructor:
 205  *
 206  * <pre> {@code
 207  * public static <E> void forEach(E[] array, Consumer<E> action) {
 208  *   class Task extends CountedCompleter<Void> {
 209  *     final int lo, hi;
 210  *     Task(Task parent, int lo, int hi) {
 211  *       super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo));
 212  *       this.lo = lo; this.hi = hi;
 213  *     }
 214  *
 215  *     public void compute() {
 216  *       for (int n = hi - lo; n >= 2; n /= 2)
 217  *         new Task(this, lo + n/2, lo + n).fork();
 218  *       action.accept(array[lo]);
 219  *       propagateCompletion();
 220  *     }
 221  *   }
 222  *   if (array.length > 0)
 223  *     new Task(null, 0, array.length).invoke();
 224  * }}</pre>
 225  *
 226  * Additional optimizations of such classes might entail specializing
 227  * classes for leaf steps, subdividing by say, four, instead of two
 228  * per iteration, and using an adaptive threshold instead of always
 229  * subdividing down to single elements.
 230  *
 231  * <p><b>Searching.</b> A tree of CountedCompleters can search for a
 232  * value or property in different parts of a data structure, and
 233  * report a result in an {@link
 234  * java.util.concurrent.atomic.AtomicReference AtomicReference} as
 235  * soon as one is found. The others can poll the result to avoid
 236  * unnecessary work. (You could additionally {@linkplain #cancel
 237  * cancel} other tasks, but it is usually simpler and more efficient
 238  * to just let them notice that the result is set and if so skip
 239  * further processing.)  Illustrating again with an array using full
 240  * partitioning (again, in practice, leaf tasks will almost always
 241  * process more than one element):
 242  *
 243  * <pre> {@code
 244  * class Searcher<E> extends CountedCompleter<E> {
 245  *   final E[] array; final AtomicReference<E> result; final int lo, hi;
 246  *   Searcher(CountedCompleter<?> p, E[] array, AtomicReference<E> result, int lo, int hi) {
 247  *     super(p);
 248  *     this.array = array; this.result = result; this.lo = lo; this.hi = hi;
 249  *   }
 250  *   public E getRawResult() { return result.get(); }
 251  *   public void compute() { // similar to ForEach version 3
 252  *     int l = lo, h = hi;
 253  *     while (result.get() == null && h >= l) {
 254  *       if (h - l >= 2) {
 255  *         int mid = (l + h) >>> 1;
 256  *         addToPendingCount(1);
 257  *         new Searcher(this, array, result, mid, h).fork();
 258  *         h = mid;
 259  *       }
 260  *       else {
 261  *         E x = array[l];
 262  *         if (matches(x) && result.compareAndSet(null, x))
 263  *           quietlyCompleteRoot(); // root task is now joinable
 264  *         break;
 265  *       }
 266  *     }
 267  *     tryComplete(); // normally complete whether or not found
 268  *   }
 269  *   boolean matches(E e) { ... } // return true if found
 270  *
 271  *   public static <E> E search(E[] array) {
 272  *       return new Searcher<E>(null, array, new AtomicReference<E>(), 0, array.length).invoke();
 273  *   }
 274  * }}</pre>
 275  *
 276  * In this example, as well as others in which tasks have no other
 277  * effects except to {@code compareAndSet} a common result, the
 278  * trailing unconditional invocation of {@code tryComplete} could be
 279  * made conditional ({@code if (result.get() == null) tryComplete();})
 280  * because no further bookkeeping is required to manage completions
 281  * once the root task completes.
 282  *
 283  * <p><b>Recording subtasks.</b> CountedCompleter tasks that combine
 284  * results of multiple subtasks usually need to access these results
 285  * in method {@link #onCompletion(CountedCompleter)}. As illustrated in the following
 286  * class (that performs a simplified form of map-reduce where mappings
 287  * and reductions are all of type {@code E}), one way to do this in
 288  * divide and conquer designs is to have each subtask record its
 289  * sibling, so that it can be accessed in method {@code onCompletion}.
 290  * This technique applies to reductions in which the order of
 291  * combining left and right results does not matter; ordered
 292  * reductions require explicit left/right designations.  Variants of
 293  * other streamlinings seen in the above examples may also apply.
 294  *
 295  * <pre> {@code
 296  * class MyMapper<E> { E apply(E v) {  ...  } }
 297  * class MyReducer<E> { E apply(E x, E y) {  ...  } }
 298  * class MapReducer<E> extends CountedCompleter<E> {
 299  *   final E[] array; final MyMapper<E> mapper;
 300  *   final MyReducer<E> reducer; final int lo, hi;
 301  *   MapReducer<E> sibling;
 302  *   E result;
 303  *   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
 304  *              MyReducer<E> reducer, int lo, int hi) {
 305  *     super(p);
 306  *     this.array = array; this.mapper = mapper;
 307  *     this.reducer = reducer; this.lo = lo; this.hi = hi;
 308  *   }
 309  *   public void compute() {
 310  *     if (hi - lo >= 2) {
 311  *       int mid = (lo + hi) >>> 1;
 312  *       MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
 313  *       MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
 314  *       left.sibling = right;
 315  *       right.sibling = left;
 316  *       setPendingCount(1); // only right is pending
 317  *       right.fork();
 318  *       left.compute();     // directly execute left
 319  *     }
 320  *     else {
 321  *       if (hi > lo)
 322  *           result = mapper.apply(array[lo]);
 323  *       tryComplete();
 324  *     }
 325  *   }
 326  *   public void onCompletion(CountedCompleter<?> caller) {
 327  *     if (caller != this) {
 328  *       MapReducer<E> child = (MapReducer<E>)caller;
 329  *       MapReducer<E> sib = child.sibling;
 330  *       if (sib == null || sib.result == null)
 331  *         result = child.result;
 332  *       else
 333  *         result = reducer.apply(child.result, sib.result);
 334  *     }
 335  *   }
 336  *   public E getRawResult() { return result; }
 337  *
 338  *   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
 339  *     return new MapReducer<E>(null, array, mapper, reducer,
 340  *                              0, array.length).invoke();
 341  *   }
 342  * }}</pre>
 343  *
 344  * Here, method {@code onCompletion} takes a form common to many
 345  * completion designs that combine results. This callback-style method
 346  * is triggered once per task, in either of the two different contexts
 347  * in which the pending count is, or becomes, zero: (1) by a task
 348  * itself, if its pending count is zero upon invocation of {@code
 349  * tryComplete}, or (2) by any of its subtasks when they complete and
 350  * decrement the pending count to zero. The {@code caller} argument
 351  * distinguishes cases.  Most often, when the caller is {@code this},
 352  * no action is necessary. Otherwise the caller argument can be used
 353  * (usually via a cast) to supply a value (and/or links to other
 354  * values) to be combined.  Assuming proper use of pending counts, the
 355  * actions inside {@code onCompletion} occur (once) upon completion of
 356  * a task and its subtasks. No additional synchronization is required
 357  * within this method to ensure thread safety of accesses to fields of
 358  * this task or other completed tasks.
 359  *
 360  * <p><b>Completion Traversals.</b> If using {@code onCompletion} to
 361  * process completions is inapplicable or inconvenient, you can use
 362  * methods {@link #firstComplete} and {@link #nextComplete} to create
 363  * custom traversals.  For example, to define a MapReducer that only
 364  * splits out right-hand tasks in the form of the third ForEach
 365  * example, the completions must cooperatively reduce along
 366  * unexhausted subtask links, which can be done as follows:
 367  *
 368  * <pre> {@code
 369  * class MapReducer<E> extends CountedCompleter<E> { // version 2
 370  *   final E[] array; final MyMapper<E> mapper;
 371  *   final MyReducer<E> reducer; final int lo, hi;
 372  *   MapReducer<E> forks, next; // record subtask forks in list
 373  *   E result;
 374  *   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
 375  *              MyReducer<E> reducer, int lo, int hi, MapReducer<E> next) {
 376  *     super(p);
 377  *     this.array = array; this.mapper = mapper;
 378  *     this.reducer = reducer; this.lo = lo; this.hi = hi;
 379  *     this.next = next;
 380  *   }
 381  *   public void compute() {
 382  *     int l = lo, h = hi;
 383  *     while (h - l >= 2) {
 384  *       int mid = (l + h) >>> 1;
 385  *       addToPendingCount(1);
 386  *       (forks = new MapReducer(this, array, mapper, reducer, mid, h, forks)).fork();
 387  *       h = mid;
 388  *     }
 389  *     if (h > l)
 390  *       result = mapper.apply(array[l]);
 391  *     // process completions by reducing along and advancing subtask links
 392  *     for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
 393  *       for (MapReducer t = (MapReducer)c, s = t.forks; s != null; s = t.forks = s.next)
 394  *         t.result = reducer.apply(t.result, s.result);
 395  *     }
 396  *   }
 397  *   public E getRawResult() { return result; }
 398  *
 399  *   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
 400  *     return new MapReducer<E>(null, array, mapper, reducer,
 401  *                              0, array.length, null).invoke();
 402  *   }
 403  * }}</pre>
 404  *
 405  * <p><b>Triggers.</b> Some CountedCompleters are themselves never
 406  * forked, but instead serve as bits of plumbing in other designs;
 407  * including those in which the completion of one or more async tasks
 408  * triggers another async task. For example:
 409  *
 410  * <pre> {@code
 411  * class HeaderBuilder extends CountedCompleter<...> { ... }
 412  * class BodyBuilder extends CountedCompleter<...> { ... }
 413  * class PacketSender extends CountedCompleter<...> {
 414  *   PacketSender(...) { super(null, 1); ... } // trigger on second completion
 415  *   public void compute() { } // never called
 416  *   public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
 417  * }
 418  * // sample use:
 419  * PacketSender p = new PacketSender();
 420  * new HeaderBuilder(p, ...).fork();
 421  * new BodyBuilder(p, ...).fork();}</pre>
 422  *
 423  * @since 1.8
 424  * @author Doug Lea
 425  */
 426 public abstract class CountedCompleter<T> extends ForkJoinTask<T> {
 427     private static final long serialVersionUID = 5232453752276485070L;
 428 
 429     /** This task's completer, or null if none */
 430     final CountedCompleter<?> completer;
 431     /** The number of pending tasks until completion */
 432     volatile int pending;
 433 
 434     /**
 435      * Creates a new CountedCompleter with the given completer
 436      * and initial pending count.
 437      *
 438      * @param completer this task's completer, or {@code null} if none
 439      * @param initialPendingCount the initial pending count
 440      */
 441     protected CountedCompleter(CountedCompleter<?> completer,
 442                                int initialPendingCount) {
 443         this.completer = completer;
 444         this.pending = initialPendingCount;
 445     }
 446 
 447     /**
 448      * Creates a new CountedCompleter with the given completer
 449      * and an initial pending count of zero.
 450      *
 451      * @param completer this task's completer, or {@code null} if none
 452      */
 453     protected CountedCompleter(CountedCompleter<?> completer) {
 454         this.completer = completer;
 455     }
 456 
 457     /**
 458      * Creates a new CountedCompleter with no completer
 459      * and an initial pending count of zero.
 460      */
 461     protected CountedCompleter() {
 462         this.completer = null;
 463     }
 464 
 465     /**
 466      * The main computation performed by this task.
 467      */
 468     public abstract void compute();
 469 
 470     /**
 471      * Performs an action when method {@link #tryComplete} is invoked
 472      * and the pending count is zero, or when the unconditional
 473      * method {@link #complete} is invoked.  By default, this method
 474      * does nothing. You can distinguish cases by checking the
 475      * identity of the given caller argument. If not equal to {@code
 476      * this}, then it is typically a subtask that may contain results
 477      * (and/or links to other results) to combine.
 478      *
 479      * @param caller the task invoking this method (which may
 480      * be this task itself)
 481      */
 482     public void onCompletion(CountedCompleter<?> caller) {
 483     }
 484 
 485     /**
 486      * Performs an action when method {@link
 487      * #completeExceptionally(Throwable)} is invoked or method {@link
 488      * #compute} throws an exception, and this task has not already
 489      * otherwise completed normally. On entry to this method, this task
 490      * {@link ForkJoinTask#isCompletedAbnormally}.  The return value
 491      * of this method controls further propagation: If {@code true}
 492      * and this task has a completer that has not completed, then that
 493      * completer is also completed exceptionally, with the same
 494      * exception as this completer.  The default implementation of
 495      * this method does nothing except return {@code true}.
 496      *
 497      * @param ex the exception
 498      * @param caller the task invoking this method (which may
 499      * be this task itself)
 500      * @return {@code true} if this exception should be propagated to this
 501      * task's completer, if one exists
 502      */
 503     public boolean onExceptionalCompletion(Throwable ex, CountedCompleter<?> caller) {
 504         return true;
 505     }
 506 
 507     /**
 508      * Returns the completer established in this task's constructor,
 509      * or {@code null} if none.
 510      *
 511      * @return the completer
 512      */
 513     public final CountedCompleter<?> getCompleter() {
 514         return completer;
 515     }
 516 
 517     /**
 518      * Returns the current pending count.
 519      *
 520      * @return the current pending count
 521      */
 522     public final int getPendingCount() {
 523         return pending;
 524     }
 525 
 526     /**
 527      * Sets the pending count to the given value.
 528      *
 529      * @param count the count
 530      */
 531     public final void setPendingCount(int count) {
 532         pending = count;
 533     }
 534 
 535     /**
 536      * Adds (atomically) the given value to the pending count.
 537      *
 538      * @param delta the value to add
 539      */
 540     public final void addToPendingCount(int delta) {
 541         PENDING.getAndAdd(this, delta);
 542     }
 543 
 544     /**
 545      * Sets (atomically) the pending count to the given count only if
 546      * it currently holds the given expected value.
 547      *
 548      * @param expected the expected value
 549      * @param count the new value
 550      * @return {@code true} if successful
 551      */
 552     public final boolean compareAndSetPendingCount(int expected, int count) {
 553         return PENDING.compareAndSet(this, expected, count);
 554     }
 555 
 556     // internal-only weak version
 557     final boolean weakCompareAndSetPendingCount(int expected, int count) {
 558         return PENDING.weakCompareAndSet(this, expected, count);
 559     }
 560 
 561     /**
 562      * If the pending count is nonzero, (atomically) decrements it.
 563      *
 564      * @return the initial (undecremented) pending count holding on entry
 565      * to this method
 566      */
 567     public final int decrementPendingCountUnlessZero() {
 568         int c;
 569         do {} while ((c = pending) != 0 &&
 570                      !weakCompareAndSetPendingCount(c, c - 1));
 571         return c;
 572     }
 573 
 574     /**
 575      * Returns the root of the current computation; i.e., this
 576      * task if it has no completer, else its completer's root.
 577      *
 578      * @return the root of the current computation
 579      */
 580     public final CountedCompleter<?> getRoot() {
 581         CountedCompleter<?> a = this, p;
 582         while ((p = a.completer) != null)
 583             a = p;
 584         return a;
 585     }
 586 
 587     /**
 588      * If the pending count is nonzero, decrements the count;
 589      * otherwise invokes {@link #onCompletion(CountedCompleter)}
 590      * and then similarly tries to complete this task's completer,
 591      * if one exists, else marks this task as complete.
 592      */
 593     public final void tryComplete() {
 594         CountedCompleter<?> a = this, s = a;
 595         for (int c;;) {
 596             if ((c = a.pending) == 0) {
 597                 a.onCompletion(s);
 598                 if ((a = (s = a).completer) == null) {
 599                     s.quietlyComplete();
 600                     return;
 601                 }
 602             }
 603             else if (a.weakCompareAndSetPendingCount(c, c - 1))
 604                 return;
 605         }
 606     }
 607 
 608     /**
 609      * Equivalent to {@link #tryComplete} but does not invoke {@link
 610      * #onCompletion(CountedCompleter)} along the completion path:
 611      * If the pending count is nonzero, decrements the count;
 612      * otherwise, similarly tries to complete this task's completer, if
 613      * one exists, else marks this task as complete. This method may be
 614      * useful in cases where {@code onCompletion} should not, or need
 615      * not, be invoked for each completer in a computation.
 616      */
 617     public final void propagateCompletion() {
 618         CountedCompleter<?> a = this, s;
 619         for (int c;;) {
 620             if ((c = a.pending) == 0) {
 621                 if ((a = (s = a).completer) == null) {
 622                     s.quietlyComplete();
 623                     return;
 624                 }
 625             }
 626             else if (a.weakCompareAndSetPendingCount(c, c - 1))
 627                 return;
 628         }
 629     }
 630 
 631     /**
 632      * Regardless of pending count, invokes
 633      * {@link #onCompletion(CountedCompleter)}, marks this task as
 634      * complete and further triggers {@link #tryComplete} on this
 635      * task's completer, if one exists.  The given rawResult is
 636      * used as an argument to {@link #setRawResult} before invoking
 637      * {@link #onCompletion(CountedCompleter)} or marking this task
 638      * as complete; its value is meaningful only for classes
 639      * overriding {@code setRawResult}.  This method does not modify
 640      * the pending count.
 641      *
 642      * <p>This method may be useful when forcing completion as soon as
 643      * any one (versus all) of several subtask results are obtained.
 644      * However, in the common (and recommended) case in which {@code
 645      * setRawResult} is not overridden, this effect can be obtained
 646      * more simply using {@link #quietlyCompleteRoot()}.
 647      *
 648      * @param rawResult the raw result
 649      */
 650     public void complete(T rawResult) {
 651         CountedCompleter<?> p;
 652         setRawResult(rawResult);
 653         onCompletion(this);
 654         quietlyComplete();
 655         if ((p = completer) != null)
 656             p.tryComplete();
 657     }
 658 
 659     /**
 660      * If this task's pending count is zero, returns this task;
 661      * otherwise decrements its pending count and returns {@code null}.
 662      * This method is designed to be used with {@link #nextComplete} in
 663      * completion traversal loops.
 664      *
 665      * @return this task, if pending count was zero, else {@code null}
 666      */
 667     public final CountedCompleter<?> firstComplete() {
 668         for (int c;;) {
 669             if ((c = pending) == 0)
 670                 return this;
 671             else if (weakCompareAndSetPendingCount(c, c - 1))
 672                 return null;
 673         }
 674     }
 675 
 676     /**
 677      * If this task does not have a completer, invokes {@link
 678      * ForkJoinTask#quietlyComplete} and returns {@code null}.  Or, if
 679      * the completer's pending count is non-zero, decrements that
 680      * pending count and returns {@code null}.  Otherwise, returns the
 681      * completer.  This method can be used as part of a completion
 682      * traversal loop for homogeneous task hierarchies:
 683      *
 684      * <pre> {@code
 685      * for (CountedCompleter<?> c = firstComplete();
 686      *      c != null;
 687      *      c = c.nextComplete()) {
 688      *   // ... process c ...
 689      * }}</pre>
 690      *
 691      * @return the completer, or {@code null} if none
 692      */
 693     public final CountedCompleter<?> nextComplete() {
 694         CountedCompleter<?> p;
 695         if ((p = completer) != null)
 696             return p.firstComplete();
 697         else {
 698             quietlyComplete();
 699             return null;
 700         }
 701     }
 702 
 703     /**
 704      * Equivalent to {@code getRoot().quietlyComplete()}.
 705      */
 706     public final void quietlyCompleteRoot() {
 707         for (CountedCompleter<?> a = this, p;;) {
 708             if ((p = a.completer) == null) {
 709                 a.quietlyComplete();
 710                 return;
 711             }
 712             a = p;
 713         }
 714     }
 715 
 716     /**
 717      * If this task has not completed, attempts to process at most the
 718      * given number of other unprocessed tasks for which this task is
 719      * on the completion path, if any are known to exist.
 720      *
 721      * @param maxTasks the maximum number of tasks to process.  If
 722      *                 less than or equal to zero, then no tasks are
 723      *                 processed.
 724      */
 725     public final void helpComplete(int maxTasks) {
 726         ForkJoinPool.WorkQueue q; Thread t; boolean owned;
 727         if (owned = (t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
 728             q = ((ForkJoinWorkerThread)t).workQueue;
 729         else
 730             q = ForkJoinPool.commonQueue();
 731         if (q != null && maxTasks > 0)
 732             q.helpComplete(this, owned, maxTasks);
 733     }
 734 
 735     // ForkJoinTask overrides
 736 
 737     /**
 738      * Supports ForkJoinTask exception propagation.
 739      */
 740     @Override
 741     final int trySetException(Throwable ex) {
 742         CountedCompleter<?> a = this, p = a;
 743         do {} while (isExceptionalStatus(a.trySetThrown(ex)) &&
 744                      a.onExceptionalCompletion(ex, p) &&
 745                      (a = (p = a).completer) != null && a.status >= 0);
 746         return status;
 747     }
 748 
 749     /**
 750      * Implements execution conventions for CountedCompleters.
 751      */
 752     @Override
 753     protected final boolean exec() {
 754         compute();
 755         return false;
 756     }
 757 
 758     /**
 759      * Returns the result of the computation.  By default,
 760      * returns {@code null}, which is appropriate for {@code Void}
 761      * actions, but in other cases should be overridden, almost
 762      * always to return a field or function of a field that
 763      * holds the result upon completion.
 764      *
 765      * @return the result of the computation
 766      */
 767     @Override
 768     public T getRawResult() { return null; }
 769 
 770     /**
 771      * A method that result-bearing CountedCompleters may optionally
 772      * use to help maintain result data.  By default, does nothing.
 773      * Overrides are not recommended. However, if this method is
 774      * overridden to update existing objects or fields, then it must
 775      * in general be defined to be thread-safe.
 776      */
 777     @Override
 778     protected void setRawResult(T t) { }
 779 
 780     // VarHandle mechanics
 781     private static final VarHandle PENDING;
 782     static {
 783         try {
 784             MethodHandles.Lookup l = MethodHandles.lookup();
 785             PENDING = l.findVarHandle(CountedCompleter.class, "pending", int.class);
 786 
 787         } catch (ReflectiveOperationException e) {
 788             throw new ExceptionInInitializerError(e);
 789         }
 790     }
 791 }