--- jsr166/src/jsr166y/CountedCompleter.java	2012/04/09 13:12:18	1.1
+++ jsr166/src/jsr166y/CountedCompleter.java	2012/11/25 18:39:07	1.19
@@ -7,32 +7,54 @@
 package jsr166y;
 
 /**
- * A resultless {@link ForkJoinTask} with a completion action
- * performed when triggered and there are no remaining pending
- * actions. Uses of CountedCompleter are similar to those of other
- * completion based components (such as {@link
- * java.nio.channels.CompletionHandler}) except that multiple
- * <em>pending</em> completions may be necessary to trigger the {@link
- * #onCompletion} action, not just one. Unless initialized otherwise,
- * the {@link #getPendingCount pending count} starts at zero, but may
- * be (atomically) changed using methods {@link #setPendingCount},
- * {@link #addToPendingCount}, and {@link
+ * A {@link ForkJoinTask} with a completion action performed when
+ * triggered and there are no remaining pending
+ * actions. CountedCompleters are in general more robust in the
+ * presence of subtask stalls and blockage than are other forms of
+ * ForkJoinTasks, but are less intuitive to program.  Uses of
+ * CountedCompleter are similar to those of other completion based
+ * components (such as {@link java.nio.channels.CompletionHandler})
+ * except that multiple <em>pending</em> completions may be necessary
+ * to trigger the {@link #onCompletion} action, not just one. Unless
+ * initialized otherwise, the {@link #getPendingCount pending count}
+ * starts at zero, but may be (atomically) changed using methods
+ * {@link #setPendingCount}, {@link #addToPendingCount}, and {@link
  * #compareAndSetPendingCount}. Upon invocation of {@link
  * #tryComplete}, if the pending action count is nonzero, it is
  * decremented; otherwise, the completion action is performed, and if
  * this completer itself has a completer, the process is continued
- * with its completer.  As is the case with most basic synchronization
- * constructs, these methods affect only internal counts; they do not
- * establish any further internal bookkeeping. In particular, the
- * identities of pending tasks are not maintained. As illustrated
- * below, you can create subclasses that do record some or all pended
- * tasks or their results when needed.
+ * with its completer.  As is the case with related synchronization
+ * components such as {@link java.util.concurrent.Phaser Phaser} and
+ * {@link java.util.concurrent.Semaphore Semaphore}, these methods
+ * affect only internal counts; they do not establish any further
+ * internal bookkeeping. In particular, the identities of pending
+ * tasks are not maintained. As illustrated below, you can create
+ * subclasses that do record some or all pending tasks or their
+ * results when needed.  As illustrated below, utility methods
+ * supporting customization of completion traversals are also
+ * provided. However, because CountedCompleters provide only basic
+ * synchronization mechanisms, it may be useful to create further
+ * abstract subclasses that maintain linkages, fields, and additional
+ * support methods appropriate for a set of related usages.
  *
  * <p>A concrete CountedCompleter class must define method {@link
- * #compute}, that should, in almost all use cases, invoke {@code
- * tryComplete()} before returning. The class may also optionally
- * override method {@link #onCompletion} to perform an action upon
- * normal completion.
+ * #compute}, that should in most cases (as illustrated below), invoke
+ * {@code tryComplete()} once before returning. The class may also
+ * optionally override method {@link #onCompletion} to perform an
+ * action upon normal completion, and method {@link
+ * #onExceptionalCompletion} to perform an action upon any exception.
+ *
+ * <p>CountedCompleters most often do not bear results, in which case
+ * they are normally declared as {@code CountedCompleter<Void>}, and
+ * will always return {@code null} as a result value.  In other cases,
+ * you should override method {@link #getRawResult} to provide a
+ * result from {@code join(), invoke()}, and related methods.  In
+ * general, this method should return the value of a field (or a
+ * function of one or more fields) of the CountedCompleter object that
+ * holds the result upon completion. Method {@link #setRawResult} by
+ * default plays no role in CountedCompleters.  It is possible, but
+ * rarely applicable, to override this method to maintain other
+ * objects or fields holding result data.
  *
  * <p>A CountedCompleter that does not itself have a completer (i.e.,
  * one for which {@link #getCompleter} returns {@code null}) can be
@@ -44,15 +66,18 @@ package jsr166y;
  * {@link #complete}, {@link ForkJoinTask#cancel}, {@link
  * ForkJoinTask#completeExceptionally} or upon exceptional completion
  * of method {@code compute}. Upon any exceptional completion, the
- * exception is relayed to a task's completer (and its completer, and
- * so on), if one exists and it has not otherwise already completed.
+ * exception may be relayed to a task's completer (and its completer,
+ * and so on), if one exists and it has not otherwise already
+ * completed. Similarly, cancelling an internal CountedCompleter has
+ * only a local effect on that completer, so is not often useful.
  *
  * <p><b>Sample Usages.</b>
  *
  * <p><b>Parallel recursive decomposition.</b> CountedCompleters may
  * be arranged in trees similar to those often used with {@link
  * RecursiveAction}s, although the constructions involved in setting
- * them up typically vary. Even though they entail a bit more
+ * them up typically vary. Here, the completer of each task is its
+ * parent in the computation tree. Even though they entail a bit more
  * bookkeeping, CountedCompleters may be better choices when applying
  * a possibly time-consuming operation (that cannot be further
  * subdivided) to each element of an array or collection; especially
@@ -63,7 +88,7 @@ package jsr166y;
  * continuations, other threads need not block waiting to perform
  * them.
  *
- * <p> For example, here is an initial version of a class that uses
+ * <p>For example, here is an initial version of a class that uses
  * divide-by-two recursive decomposition to divide work into single
  * pieces (leaf tasks). Even when work is split into individual calls,
  * tree-based techniques are usually preferable to directly forking
@@ -72,34 +97,35 @@ package jsr166y;
  * pair of subtasks to finish triggers completion of its parent
  * (because no result combination is performed, the default no-op
  * implementation of method {@code onCompletion} is not overridden). A
- * static utility method sets up the base task and invokes it:
+ * static utility method sets up the base task and invokes it
+ * (here, implicitly using the {@link ForkJoinPool#commonPool()}).
  *
  * <pre> {@code
  * class MyOperation<E> { void apply(E e) { ... }  }
  *
- * class ForEach<E> extends CountedCompleter {
+ * class ForEach<E> extends CountedCompleter<Void> {
  *
- *     public static <E> void forEach(ForkJoinPool pool, E[] array, MyOperation<E> op) {
- *         pool.invoke(new ForEach<E>(null, array, op, 0, array.length));
- *     }
- *
- *     final E[] array; final MyOperation<E> op; final int lo, hi;
- *     ForEach(CountedCompleter p, E[] array, MyOperation<E> op, int lo, int hi) {
- *         super(p);
- *         this.array = array; this.op = op; this.lo = lo; this.hi = hi;
- *     }
- *
- *     public void compute() { // version 1
- *         if (hi - lo >= 2) {
- *             int mid = (lo + hi) >>> 1;
- *             setPendingCount(2); // must set pending count before fork
- *             new ForEach(this, array, op, mid, hi).fork(); // right child
- *             new ForEach(this, array, op, lo, mid).fork(); // left child
- *         }
- *         else if (hi > lo)
- *             op.apply(array[lo]);
- *         tryComplete();
+ *   public static <E> void forEach(E[] array, MyOperation<E> op) {
+ *     new ForEach<E>(null, array, op, 0, array.length).invoke();
+ *   }
+ *
+ *   final E[] array; final MyOperation<E> op; final int lo, hi;
+ *   ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) {
+ *     super(p);
+ *     this.array = array; this.op = op; this.lo = lo; this.hi = hi;
+ *   }
+ *
+ *   public void compute() { // version 1
+ *     if (hi - lo >= 2) {
+ *       int mid = (lo + hi) >>> 1;
+ *       setPendingCount(2); // must set pending count before fork
+ *       new ForEach(this, array, op, mid, hi).fork(); // right child
+ *       new ForEach(this, array, op, lo, mid).fork(); // left child
  *     }
+ *     else if (hi > lo)
+ *       op.apply(array[lo]);
+ *     tryComplete();
+ *   }
  * } }</pre>
  *
  * This design can be improved by noticing that in the recursive case,
@@ -111,39 +137,42 @@ package jsr166y;
  *
  * <pre> {@code
  * class ForEach<E> ...
- *     public void compute() { // version 2
- *         if (hi - lo >= 2) {
- *             int mid = (lo + hi) >>> 1;
- *             setPendingCount(1); // only one pending
- *             new ForEach(this, array, op, mid, hi).fork(); // right child
- *             new ForEach(this, array, op, lo, mid).compute(); // direct invoke
- *         }
- *         else {
- *             if (hi > lo)
- *                 op.apply(array[lo]);
- *             tryComplete();
- *         }
+ *   public void compute() { // version 2
+ *     if (hi - lo >= 2) {
+ *       int mid = (lo + hi) >>> 1;
+ *       setPendingCount(1); // only one pending
+ *       new ForEach(this, array, op, mid, hi).fork(); // right child
+ *       new ForEach(this, array, op, lo, mid).compute(); // direct invoke
+ *     }
+ *     else {
+ *       if (hi > lo)
+ *         op.apply(array[lo]);
+ *       tryComplete();
  *     }
+ *   }
  * }</pre>
  *
  * As a further improvement, notice that the left task need not even
  * exist.  Instead of creating a new one, we can iterate using the
- * original task, and add a pending count for each fork:
+ * original task, and add a pending count for each fork. Additionally,
+ * because no task in this tree implements an {@link #onCompletion}
+ * method, {@code tryComplete()} can be replaced with {@link
+ * #propagateCompletion}.
  *
  * <pre> {@code
  * class ForEach<E> ...
- *     public void compute() { // version 3
- *         int l = lo,  h = hi;
- *         while (h - l >= 2) {
- *             int mid = (l + h) >>> 1;
- *             addToPendingCount(1);
- *             new ForEach(this, array, op, mid, h).fork(); // right child
- *             h = mid;
- *         }
- *         if (h > l)
- *             op.apply(array[l]);
- *         tryComplete();
+ *   public void compute() { // version 3
+ *     int l = lo,  h = hi;
+ *     while (h - l >= 2) {
+ *       int mid = (l + h) >>> 1;
+ *       addToPendingCount(1);
+ *       new ForEach(this, array, op, mid, h).fork(); // right child
+ *       h = mid;
  *     }
+ *     if (h > l)
+ *       op.apply(array[l]);
+ *     propagateCompletion();
+ *   }
  * }</pre>
  *
  * Additional improvements of such classes might entail precomputing
@@ -152,6 +181,57 @@ package jsr166y;
  * instead of two per iteration, and using an adaptive threshold
  * instead of always subdividing down to single elements.
  *
+ * <p><b>Searching.</b> A tree of CountedCompleters can search for a
+ * value or property in different parts of a data structure, and
+ * report a result in an {@link java.util.concurrent.AtomicReference}
+ * as soon as one is found. The others can poll the result to avoid
+ * unnecessary work. (You could additionally {@link #cancel} other
+ * tasks, but it is usually simpler and more efficient to just let
+ * them notice that the result is set and if so skip further
+ * processing.)  Illustrating again with an array using full
+ * partitioning (again, in practice, leaf tasks will almost always
+ * process more than one element):
+ *
+ * <pre> {@code
+ * class Searcher<E> extends CountedCompleter<E> {
+ *   final E[] array; final AtomicReference<E> result; final int lo, hi;
+ *   Searcher(CountedCompleter<?> p, E[] array, AtomicReference<E> result, int lo, int hi) {
+ *     super(p);
+ *     this.array = array; this.result = result; this.lo = lo; this.hi = hi;
+ *   }
+ *   public E getRawResult() { return result.get(); }
+ *   public void compute() { // similar to ForEach version 3
+ *     int l = lo,  h = hi;
+ *     while (result.get() == null && h >= l) {
+ *       if (h - l >= 2) {
+ *         int mid = (l + h) >>> 1;
+ *         addToPendingCount(1);
+ *         new Searcher(this, array, result, mid, h).fork();
+ *         h = mid;
+ *       }
+ *       else {
+ *         E x = array[l];
+ *         if (matches(x) && result.compareAndSet(null, x))
+ *           quietlyCompleteRoot(); // root task is now joinable
+ *         break;
+ *       }
+ *     }
+ *     tryComplete(); // normally complete whether or not found
+ *   }
+ *   boolean matches(E e) { ... } // return true if found
+ *
+ *   public static <E> E search(E[] array) {
+ *       return new Searcher<E>(null, array, new AtomicReference<E>(), 0, array.length).invoke();
+ *   }
+ *}}</pre>
+ *
+ * In this example, as well as others in which tasks have no other
+ * effects except to compareAndSet a common result, the trailing
+ * unconditional invocation of {@code tryComplete} could be made
+ * conditional ({@code if (result.get() == null) tryComplete();})
+ * because no further bookkeeping is required to manage completions
+ * once the root task completes.
+ *
  * <p><b>Recording subtasks.</b> CountedCompleter tasks that combine
  * results of multiple subtasks usually need to access these results
  * in method {@link #onCompletion}. As illustrated in the following
@@ -159,73 +239,133 @@ package jsr166y;
  * and reductions are all of type {@code E}), one way to do this in
  * divide and conquer designs is to have each subtask record its
  * sibling, so that it can be accessed in method {@code onCompletion}.
- * For clarity, this class uses explicit left and right subtasks, but
- * variants of other streamlinings seen in the above example may also
- * apply.
+ * This technique applies to reductions in which the order of
+ * combining left and right results does not matter; ordered
+ * reductions require explicit left/right designations.  Variants of
+ * other streamlinings seen in the above examples may also apply.
  *
  * <pre> {@code
  * class MyMapper<E> { E apply(E v) {  ...  } }
  * class MyReducer<E> { E apply(E x, E y) {  ...  } }
- * class MapReducer<E> extends CountedCompleter {
- *     final E[] array; final MyMapper<E> mapper;
- *     final MyReducer<E> reducer; final int lo, hi;
- *     MapReducer sibling;
- *     E result;
- *     MapReducer(CountedCompleter p, E[] array, MyMapper<E> mapper,
- *                MyReducer<E> reducer, int lo, int hi) {
- *         super(p);
- *         this.array = array; this.mapper = mapper;
- *         this.reducer = reducer; this.lo = lo; this.hi = hi;
+ * class MapReducer<E> extends CountedCompleter<E> {
+ *   final E[] array; final MyMapper<E> mapper;
+ *   final MyReducer<E> reducer; final int lo, hi;
+ *   MapReducer<E> sibling;
+ *   E result;
+ *   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
+ *              MyReducer<E> reducer, int lo, int hi) {
+ *     super(p);
+ *     this.array = array; this.mapper = mapper;
+ *     this.reducer = reducer; this.lo = lo; this.hi = hi;
+ *   }
+ *   public void compute() {
+ *     if (hi - lo >= 2) {
+ *       int mid = (lo + hi) >>> 1;
+ *       MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
+ *       MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
+ *       left.sibling = right;
+ *       right.sibling = left;
+ *       setPendingCount(1); // only right is pending
+ *       right.fork();
+ *       left.compute();     // directly execute left
  *     }
- *     public void compute() {
- *         if (hi - lo >= 2) {
- *             int mid = (lo + hi) >>> 1;
- *             MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
- *             MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
- *             left.sibling = right;
- *             right.sibling = left;
- *             setPendingCount(1); // only right is pending
- *             right.fork();
- *             left.compute();     // directly execute left
- *         }
- *         else {
- *             if (hi > lo)
- *                 result = mapper.apply(array[lo]);
- *             tryComplete();
- *         }
+ *     else {
+ *       if (hi > lo)
+ *           result = mapper.apply(array[lo]);
+ *       tryComplete();
  *     }
- *     public void onCompletion(CountedCompleter caller) {
- *         if (caller != this) {
- *            MapReducer<E> child = (MapReducer<E>)caller;
- *            MapReducer<E> sib = child.sibling;
- *            if (sib == null || sib.result == null)
- *                result = child.result;
- *            else
- *                result = reducer.apply(child.result, sib.result);
- *         }
+ *   }
+ *   public void onCompletion(CountedCompleter<?> caller) {
+ *     if (caller != this) {
+ *      MapReducer<E> child = (MapReducer<E>)caller;
+ *      MapReducer<E> sib = child.sibling;
+ *      if (sib == null || sib.result == null)
+ *        result = child.result;
+ *      else
+ *        result = reducer.apply(child.result, sib.result);
  *     }
+ *   }
+ *   public E getRawResult() { return result; }
  *
- *     public static <E> E mapReduce(ForkJoinPool pool, E[] array,
- *                                   MyMapper<E> mapper, MyReducer<E> reducer) {
- *         MapReducer<E> mr = new MapReducer<E>(null, array, mapper,
- *                                              reducer, 0, array.length);
- *         pool.invoke(mr);
- *         return mr.result;
- *     }
+ *   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
+ *     return new MapReducer<E>(null, array, mapper, reducer,
+ *                              0, array.length).invoke();
+ *   }
  * } }</pre>
  *
+ * Here, method {@code onCompletion} takes a form common to many
+ * completion designs that combine results. This callback-style method
+ * is triggered once per task, in either of the two different contexts
+ * in which the pending count is, or becomes, zero: (1) by a task
+ * itself, if its pending count is zero upon invocation of {@code
+ * tryComplete}, or (2) by any of its subtasks when they complete and
+ * decrement the pending count to zero. The {@code caller} argument
+ * distinguishes cases.  Most often, when the caller is {@code this},
+ * no action is necessary. Otherwise the caller argument can be used
+ * (usually via a cast) to supply a value (and/or links to other
+ * values) to be combined.  Assuming proper use of pending counts, the
+ * actions inside {@code onCompletion} occur (once) upon completion of
+ * a task and its subtasks. No additional synchronization is required
+ * within this method to ensure thread safety of accesses to fields of
+ * this task or other completed tasks.
+ *
+ * <p><b>Completion Traversals</b>. If using {@code onCompletion} to
+ * process completions is inapplicable or inconvenient, you can use
+ * methods {@link #firstComplete} and {@link #nextComplete} to create
+ * custom traversals.  For example, to define a MapReducer that only
+ * splits out right-hand tasks in the form of the third ForEach
+ * example, the completions must cooperatively reduce along
+ * unexhausted subtask links, which can be done as follows:
+ *
+ * <pre> {@code
+ * class MapReducer<E> extends CountedCompleter<E> { // version 2
+ *   final E[] array; final MyMapper<E> mapper;
+ *   final MyReducer<E> reducer; final int lo, hi;
+ *   MapReducer<E> forks, next; // record subtask forks in list
+ *   E result;
+ *   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
+ *              MyReducer<E> reducer, int lo, int hi, MapReducer<E> next) {
+ *     super(p);
+ *     this.array = array; this.mapper = mapper;
+ *     this.reducer = reducer; this.lo = lo; this.hi = hi;
+ *     this.next = next;
+ *   }
+ *   public void compute() {
+ *     int l = lo,  h = hi;
+ *     while (h - l >= 2) {
+ *       int mid = (l + h) >>> 1;
+ *       addToPendingCount(1);
+ *       (forks = new MapReducer(this, array, mapper, reducer, mid, h, forks)).fork;
+ *       h = mid;
+ *     }
+ *     if (h > l)
+ *       result = mapper.apply(array[l]);
+ *     // process completions by reducing along and advancing subtask links
+ *     for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
+ *       for (MapReducer t = (MapReducer)c, s = t.forks;  s != null; s = t.forks = s.next)
+ *         t.result = reducer.apply(t.result, s.result);
+ *     }
+ *   }
+ *   public E getRawResult() { return result; }
+ *
+ *   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
+ *     return new MapReducer<E>(null, array, mapper, reducer,
+ *                              0, array.length, null).invoke();
+ *   }
+ * }}</pre>
+ *
  * <p><b>Triggers.</b> Some CountedCompleters are themselves never
  * forked, but instead serve as bits of plumbing in other designs;
  * including those in which the completion of one of more async tasks
  * triggers another async task. For example:
  *
  * <pre> {@code
- * class HeaderBuilder extends CountedCompleter { ... }
- * class BodyBuilder extends CountedCompleter { ... }
- * class PacketSender extends CountedCompleter {
- *     PacketSender(...) { super(null, 1); ... } // trigger on second completion
- *     public void compute() { } // never called
- *     public void onCompletion(CountedCompleter caller) { sendPacket(); }
+ * class HeaderBuilder extends CountedCompleter<...> { ... }
+ * class BodyBuilder extends CountedCompleter<...> { ... }
+ * class PacketSender extends CountedCompleter<...> {
+ *   PacketSender(...) { super(null, 1); ... } // trigger on second completion
+ *   public void compute() { } // never called
+ *   public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
  * }
  * // sample use:
  * PacketSender p = new PacketSender();
@@ -236,9 +376,11 @@ package jsr166y;
  * @since 1.8
  * @author Doug Lea
  */
-public abstract class CountedCompleter extends ForkJoinTask<Void> {
+public abstract class CountedCompleter<T> extends ForkJoinTask<T> {
+    private static final long serialVersionUID = 5232453752276485070L;
+
     /** This task's completer, or null if none */
-    final CountedCompleter completer;
+    final CountedCompleter<?> completer;
     /** The number of pending tasks until completion */
     volatile int pending;
 
@@ -249,7 +391,7 @@ public abstract class CountedCompleter e
      * @param completer this tasks completer, or {@code null} if none
      * @param initialPendingCount the initial pending count
      */
-    protected CountedCompleter(CountedCompleter completer,
+    protected CountedCompleter(CountedCompleter<?> completer,
                                int initialPendingCount) {
         this.completer = completer;
         this.pending = initialPendingCount;
@@ -261,7 +403,7 @@ public abstract class CountedCompleter e
      *
      * @param completer this tasks completer, or {@code null} if none
      */
-    protected CountedCompleter(CountedCompleter completer) {
+    protected CountedCompleter(CountedCompleter<?> completer) {
         this.completer = completer;
     }
 
@@ -279,15 +421,39 @@ public abstract class CountedCompleter e
     public abstract void compute();
 
     /**
-     * Executes the completion action when method {@link #tryComplete}
-     * is invoked and there are no pending counts, or when the
-     * unconditional method {@link #complete} is invoked.  By default,
-     * this method does nothing.
+     * Performs an action when method {@link #tryComplete} is invoked
+     * and there are no pending counts, or when the unconditional
+     * method {@link #complete} is invoked.  By default, this method
+     * does nothing. You can distinguish cases by checking the
+     * identity of the given caller argument. If not equal to {@code
+     * this}, then it is typically a subtask that may contain results
+     * (and/or links to other results) to combine.
      *
      * @param caller the task invoking this method (which may
      * be this task itself).
      */
-    public void onCompletion(CountedCompleter caller) {
+    public void onCompletion(CountedCompleter<?> caller) {
+    }
+
+    /**
+     * Performs an action when method {@link #completeExceptionally}
+     * is invoked or method {@link #compute} throws an exception, and
+     * this task has not otherwise already completed normally. On
+     * entry to this method, this task {@link
+     * ForkJoinTask#isCompletedAbnormally}.  The return value of this
+     * method controls further propagation: If {@code true} and this
+     * task has a completer, then this completer is also completed
+     * exceptionally.  The default implementation of this method does
+     * nothing except return {@code true}.
+     *
+     * @param ex the exception
+     * @param caller the task invoking this method (which may
+     * be this task itself).
+     * @return true if this exception should be propagated to this
+     * tasks completer, if one exists.
+     */
+    public boolean onExceptionalCompletion(Throwable ex, CountedCompleter<?> caller) {
+        return true;
     }
 
     /**
@@ -296,7 +462,7 @@ public abstract class CountedCompleter e
      *
      * @return the completer
      */
-    public final CountedCompleter getCompleter() {
+    public final CountedCompleter<?> getCompleter() {
         return completer;
     }
 
@@ -334,21 +500,47 @@ public abstract class CountedCompleter e
      *
      * @param expected the expected value
      * @param count the new value
-     * @return true is successful
+     * @return true if successful
      */
     public final boolean compareAndSetPendingCount(int expected, int count) {
         return U.compareAndSwapInt(this, PENDING, expected, count);
     }
 
     /**
+     * If the pending count is nonzero, (atomically) decrements it.
+     *
+     * @return the initial (undecremented) pending count holding on entry
+     * to this method
+     */
+    public final int decrementPendingCountUnlessZero() {
+        int c;
+        do {} while ((c = pending) != 0 &&
+                     !U.compareAndSwapInt(this, PENDING, c, c - 1));
+        return c;
+    }
+
+    /**
+     * Returns the root of the current computation; i.e., this
+     * task if it has no completer, else its completer's root.
+     *
+     * @return the root of the current computation
+     */
+    public final CountedCompleter<?> getRoot() {
+        CountedCompleter<?> a = this, p;
+        while ((p = a.completer) != null)
+            a = p;
+        return a;
+    }
+
+    /**
      * If the pending count is nonzero, decrements the count;
      * otherwise invokes {@link #onCompletion} and then similarly
      * tries to complete this task's completer, if one exists,
      * else marks this task as complete.
      */
     public final void tryComplete() {
-        for (CountedCompleter a = this, s = a;;) {
-            int c;
+        CountedCompleter<?> a = this, s = a;
+        for (int c;;) {
             if ((c = a.pending) == 0) {
                 a.onCompletion(s);
                 if ((a = (s = a).completer) == null) {
@@ -362,23 +554,122 @@ public abstract class CountedCompleter e
     }
 
     /**
+     * Equivalent to {@link #tryComplete} but does not invoke {@link
+     * #onCompletion} along the completion path: If the pending count
+     * is nonzero, decrements the count; otherwise, similarly tries to
+     * complete this task's completer, if one exists, else marks this
+     * task as complete. This method may be useful in cases where
+     * {@code onCompletion} should not, or need not, be invoked for
+     * each completer in a computation.
+     */
+    public final void propagateCompletion() {
+        CountedCompleter<?> a = this, s = a;
+        for (int c;;) {
+            if ((c = a.pending) == 0) {
+                if ((a = (s = a).completer) == null) {
+                    s.quietlyComplete();
+                    return;
+                }
+            }
+            else if (U.compareAndSwapInt(a, PENDING, c, c - 1))
+                return;
+        }
+    }
+
+    /**
      * Regardless of pending count, invokes {@link #onCompletion},
-     * marks this task as complete with a {@code null} return value,
-     * and further triggers {@link #tryComplete} on this task's
-     * completer, if one exists. This method may be useful when
-     * forcing completion as soon as any one (versus all) of several
-     * subtask results are obtained.
-     *
-     * @param mustBeNull the {@code null} completion value
-     */
-    public void complete(Void mustBeNull) {
-        CountedCompleter p;
+     * marks this task as complete and further triggers {@link
+     * #tryComplete} on this task's completer, if one exists.  The
+     * given rawResult is used as an argument to {@link #setRawResult}
+     * before invoking {@link #onCompletion} or marking this task as
+     * complete; its value is meaningful only for classes overriding
+     * {@code setRawResult}.
+     *
+     * <p>This method may be useful when forcing completion as soon as
+     * any one (versus all) of several subtask results are obtained.
+     * However, in the common (and recommended) case in which {@code
+     * setRawResult} is not overridden, this effect can be obtained
+     * more simply using {@code quietlyCompleteRoot();}.
+     *
+     * @param rawResult the raw result
+     */
+    public void complete(T rawResult) {
+        CountedCompleter<?> p;
+        setRawResult(rawResult);
         onCompletion(this);
         quietlyComplete();
         if ((p = completer) != null)
             p.tryComplete();
     }
 
+
+    /**
+     * If this task's pending count is zero, returns this task;
+     * otherwise decrements its pending count and returns {@code
+     * null}. This method is designed to be used with {@link
+     * #nextComplete} in completion traversal loops.
+     *
+     * @return this task, if pending count was zero, else {@code null}
+     */
+    public final CountedCompleter<?> firstComplete() {
+        for (int c;;) {
+            if ((c = pending) == 0)
+                return this;
+            else if (U.compareAndSwapInt(this, PENDING, c, c - 1))
+                return null;
+        }
+    }
+
+    /**
+     * If this task does not have a completer, invokes {@link
+     * ForkJoinTask#quietlyComplete} and returns {@code null}.  Or, if
+     * this task's pending count is non-zero, decrements its pending
+     * count and returns {@code null}.  Otherwise, returns the
+     * completer.  This method can be used as part of a completion
+     * traversal loop for homogeneous task hierarchies:
+     *
+     * <pre> {@code
+     * for (CountedCompleter<?> c = firstComplete();
+     *      c != null;
+     *      c = c.nextComplete()) {
+     *   // ... process c ...
+     * }}</pre>
+     *
+     * @return the completer, or {@code null} if none
+     */
+    public final CountedCompleter<?> nextComplete() {
+        CountedCompleter<?> p;
+        if ((p = completer) != null)
+            return p.firstComplete();
+        else {
+            quietlyComplete();
+            return null;
+        }
+    }
+
+    /**
+     * Equivalent to {@code getRoot().quietlyComplete()}.
+     */
+    public final void quietlyCompleteRoot() {
+        for (CountedCompleter<?> a = this, p;;) {
+            if ((p = a.completer) == null) {
+                a.quietlyComplete();
+                return;
+            }
+            a = p;
+        }
+    }
+
+    /**
+     * Support for FJT exception propagation
+     */
+    void internalPropagateException(Throwable ex) {
+        CountedCompleter<?> a = this, s = a;
+        while (a.onExceptionalCompletion(ex, s) &&
+               (a = (s = a).completer) != null && a.status >= 0)
+            a.recordExceptionalCompletion(ex);
+    }
+
     /**
      * Implements execution conventions for CountedCompleters
      */
@@ -388,28 +679,31 @@ public abstract class CountedCompleter e
     }
 
     /**
-     * Always returns {@code null}.
+     * Returns the result of the computation. By default
+     * returns {@code null}, which is appropriate for {@code Void}
+     * actions, but in other cases should be overridden, almost
+     * always to return a field or function of a field that
+     * holds the result upon completion.
      *
-     * @return {@code null} always
+     * @return the result of the computation
      */
-    public final Void getRawResult() { return null; }
+    public T getRawResult() { return null; }
 
     /**
-     * Requires null completion value.
+     * A method that result-bearing CountedCompleters may optionally
+     * use to help maintain result data.  By default, does nothing.
+     * Overrides are not recommended. However, if this method is
+     * overridden to update existing objects or fields, then it must
+     * in general be defined to be thread-safe.
      */
-    protected final void setRawResult(Void mustBeNull) { }
-
-    /**
-     * Support for FJT exception propagation
-     */
-    final ForkJoinTask<?> internalGetCompleter() { return completer; }
+    protected void setRawResult(T t) { }
 
     // Unsafe mechanics
     private static final sun.misc.Unsafe U;
     private static final long PENDING;
     static {
         try {
-            U = getUnsafe();
+            U = sun.misc.Unsafe.getUnsafe();
             PENDING = U.objectFieldOffset
                 (CountedCompleter.class.getDeclaredField("pending"));
         } catch (Exception e) {
@@ -417,7 +711,6 @@ public abstract class CountedCompleter e
         }
     }
 
-
     /**
      * Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
      * Replace with a simple call to Unsafe.getUnsafe when integrating
@@ -445,5 +738,4 @@ public abstract class CountedCompleter e
             }
         }
     }
-
 }