src/jsr166e/CountedCompleter.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package jsr166e;
/**
 * A {@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
 * #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 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.
 *
 * <p>A concrete CountedCompleter class must define method {@link
 * #compute}, that should, in almost all use cases, 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. (Method
 * {@link #setRawResult} by default plays no role in CountedCompleters
 * but may be overridden for example to maintain 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
 * used as a regular ForkJoinTask with this added functionality.
 * However, any completer that in turn has another completer serves
 * only as an internal helper for other computations, so its own task
 * status (as reported in methods such as {@link ForkJoinTask#isDone})
 * is arbitrary; this status changes only upon explicit invocations of
 * {@link #complete}, {@link ForkJoinTask#cancel}, {@link
 * ForkJoinTask#completeExceptionally} or upon exceptional completion
 * of method {@code compute}. Upon any exceptional completion, the
 * 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.
 *
 * <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. 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
 * when the operation takes a significantly different amount of time
 * to complete for some elements than others, either because of
 * intrinsic variation (for example IO) or auxiliary effects such as
 * garbage collection.  Because CountedCompleters provide their own
 * continuations, other threads need not block waiting to perform
 * them.
 *
 * <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
 * leaf tasks, because they reduce inter-thread communication and
 * improve load balancing. In the recursive case, the second of each
 * 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:
 *
 * <pre> {@code
 * class MyOperation<E> { void apply(E e) { ... }  }
 *
 * 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();
 *     }
 * } }</pre>
 *
 * This design can be improved by noticing that in the recursive case,
 * the task has nothing to do after forking its right task, so can
 * directly invoke its left task before returning. (This is an analog
 * of tail recursion removal.)  Also, because the task returns upon
 * executing its left task (rather than falling through to invoke
 * tryComplete) the pending count is set to one:
 *
 * <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();
 *         }
 *     }
 * }</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. Additionally,
 * this version uses {@code helpComplete} to streamline assistance in
 * the execution of forked tasks.
 *
 * <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]);
 *         helpComplete();
 *     }
 * }</pre>
 *
 * Additional improvements of such classes might entail precomputing
 * pending counts so that they can be established in constructors,
 * specializing classes for leaf steps, subdividing by say, four,
 * instead of two per iteration, and using an adaptive threshold
 * instead of always subdividing down to single elements.
 *
 * <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
 * class (that performs a simplified form of map-reduce where mappings
 * 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}.
 * 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<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
 *         }
 *         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 E getRawResult() { return result; }
 *
 *     public static <E> E mapReduce(ForkJoinPool pool, E[] array,
 *                                   MyMapper<E> mapper, MyReducer<E> reducer) {
 *         return pool.invoke(new MapReducer<E>(null, array, mapper,
 *                                              reducer, 0, array.length));
 *     }
 * } }</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(); }
 * }
 * // sample use:
 * PacketSender p = new PacketSender();
 * new HeaderBuilder(p, ...).fork();
 * new BodyBuilder(p, ...).fork();
 * }</pre>
 *
 * @since 1.8
 * @author Doug Lea
 */
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;
    /** The number of pending tasks until completion */
    volatile int pending;

    /**
     * Creates a new CountedCompleter with the given completer
     * and initial pending count.
     *
     * @param completer this tasks completer, or {@code null} if none
     * @param initialPendingCount the initial pending count
     */
    protected CountedCompleter(CountedCompleter<?> completer,
                               int initialPendingCount) {
        this.completer = completer;
        this.pending = initialPendingCount;
    }

    /**
     * Creates a new CountedCompleter with the given completer
     * and an initial pending count of zero.
     *
     * @param completer this tasks completer, or {@code null} if none
     */
    protected CountedCompleter(CountedCompleter<?> completer) {
        this.completer = completer;
    }

    /**
     * Creates a new CountedCompleter with no completer
     * and an initial pending count of zero.
     */
    protected CountedCompleter() {
        this.completer = null;
    }

    /**
     * The main computation performed by this task.
     */
    public abstract void compute();

    /**
     * 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.
     *
     * @param caller the task invoking this method (which may
     * be this task itself).
     */
    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;
    }

    /**
     * Returns the completer established in this task's constructor,
     * or {@code null} if none.
     *
     * @return the completer
     */
    public final CountedCompleter<?> getCompleter() {
        return completer;
    }

    /**
     * Returns the current pending count.
     *
     * @return the current pending count
     */
    public final int getPendingCount() {
        return pending;
    }

    /**
     * Sets the pending count to the given value.
     *
     * @param count the count
     */
    public final void setPendingCount(int count) {
        pending = count;
    }

    /**
     * Adds (atomically) the given value to the pending count.
     *
     * @param delta the value to add
     */
    public final void addToPendingCount(int delta) {
        int c; // note: can replace with intrinsic in jdk8
        do {} while (!U.compareAndSwapInt(this, PENDING, c = pending, c+delta));
    }

    /**
     * Sets (atomically) the pending count to the given count only if
     * it currently holds the given expected value.
     *
     * @param expected the expected value
     * @param count the new value
     * @return true is successful
     */
    public final boolean compareAndSetPendingCount(int expected, int count) {
        return U.compareAndSwapInt(this, PENDING, expected, count);
    }

    /**
     * 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() {
        CountedCompleter<?> a = this, s = a;
        for (int c;;) {
            if ((c = a.pending) == 0) {
                a.onCompletion(s);
                if ((a = (s = a).completer) == null) {
                    s.quietlyComplete();
                    return;
                }
            }
            else if (U.compareAndSwapInt(a, PENDING, c, c - 1))
                return;
        }
    }

    /**
     * Identical to {@link #tryComplete}, but may additionally execute
     * other tasks within the current computation (i.e., those
     * with the same {@link #getRoot}.
     */
    public final void helpComplete() {
        CountedCompleter<?> a = this, s = a;
        for (int c;;) {
            if ((c = a.pending) == 0) {
                a.onCompletion(s);
                if ((a = (s = a).completer) == null) {
                    s.quietlyComplete();
                    return;
                }
            }
            else if (U.compareAndSwapInt(a, PENDING, c, c - 1)) {
                CountedCompleter<?> root = a.getRoot();
                Thread thread = Thread.currentThread();
                ForkJoinPool.WorkQueue wq =
                    (thread instanceof ForkJoinWorkerThread) ?
                    ((ForkJoinWorkerThread)thread).workQueue : null;
                ForkJoinTask<?> t;
                while ((t = (wq != null) ? wq.popCC(root) :
                        ForkJoinPool.popCCFromCommonPool(root)) != null) {
                    t.doExec();
                    if (root.isDone())
                        break;
                }
                return;
            }
        }
    }

    /**
     * Regardless of pending count, invokes {@link #onCompletion},
     * marks this task as complete 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.  The
     * given rawResult is used as an argument to {@link #setRawResult}
     * before marking this task as complete; its value is meaningful
     * only for classes overriding {@code setRawResult}.
     *
     * @param rawResult the raw result
     */
    public void complete(T rawResult) {
        CountedCompleter<?> p;
        onCompletion(this);
        setRawResult(rawResult);
        quietlyComplete();
        if ((p = completer) != null)
            p.tryComplete();
    }

    /**
     * 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
     */
    protected final boolean exec() {
        compute();
        return false;
    }

    /**
     * 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.
     *
     * @return the result of the computation
     */
    public T getRawResult() { return null; }

    /**
     * A method that result-bearing CountedCompleters may optionally
     * use to help maintain result data.  By default, does nothing.
     */
    protected void setRawResult(T t) { }

    // Unsafe mechanics
    private static final sun.misc.Unsafe U;
    private static final long PENDING;
    static {
        try {
            U = getUnsafe();
            PENDING = U.objectFieldOffset
                (CountedCompleter.class.getDeclaredField("pending"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }

    /**
     * Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
     * Replace with a simple call to Unsafe.getUnsafe when integrating
     * into a jdk.
     *
     * @return a sun.misc.Unsafe
     */
    private static sun.misc.Unsafe getUnsafe() {
        try {
            return sun.misc.Unsafe.getUnsafe();
        } catch (SecurityException se) {
            try {
                return java.security.AccessController.doPrivileged
                    (new java.security
                     .PrivilegedExceptionAction<sun.misc.Unsafe>() {
                        public sun.misc.Unsafe run() throws Exception {
                            java.lang.reflect.Field f = sun.misc
                                .Unsafe.class.getDeclaredField("theUnsafe");
                            f.setAccessible(true);
                            return (sun.misc.Unsafe) f.get(null);
                        }});
            } catch (java.security.PrivilegedActionException e) {
                throw new RuntimeException("Could not initialize intrinsics",
                                           e.getCause());
            }
        }
    }

}
Revision:	1.6
Committed:	Tue Oct 30 16:05:35 2012 UTC (11 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.5:	+1 -1 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/publicdomain/zero/1.0/
5			*/
6
7			package jsr166e;
8			/**
9	dl	1.2	* A {@link ForkJoinTask} with a completion action
10	dl	1.1	* performed when triggered and there are no remaining pending
11			* actions. Uses of CountedCompleter are similar to those of other
12			* completion based components (such as {@link
13			* java.nio.channels.CompletionHandler}) except that multiple
14			* <em>pending</em> completions may be necessary to trigger the {@link
15			* #onCompletion} action, not just one. Unless initialized otherwise,
16			* the {@link #getPendingCount pending count} starts at zero, but may
17			* be (atomically) changed using methods {@link #setPendingCount},
18			* {@link #addToPendingCount}, and {@link
19			* #compareAndSetPendingCount}. Upon invocation of {@link
20			* #tryComplete}, if the pending action count is nonzero, it is
21			* decremented; otherwise, the completion action is performed, and if
22			* this completer itself has a completer, the process is continued
23			* with its completer. As is the case with related synchronization
24	jsr166	1.3	* components such as {@link java.util.concurrent.Phaser Phaser} and
25			* {@link java.util.concurrent.Semaphore Semaphore}, these methods
26			* affect only internal counts; they do not establish any further
27			* internal bookkeeping. In particular, the identities of pending
28			* tasks are not maintained. As illustrated below, you can create
29	jsr166	1.4	* subclasses that do record some or all pending tasks or their
30			* results when needed.
31	dl	1.1	*
32			* <p>A concrete CountedCompleter class must define method {@link
33			* #compute}, that should, in almost all use cases, invoke {@code
34			* tryComplete()} once before returning. The class may also optionally
35			* override method {@link #onCompletion} to perform an action upon
36			* normal completion, and method {@link #onExceptionalCompletion} to
37			* perform an action upon any exception.
38			*
39	dl	1.2	* <p>CountedCompleters most often do not bear results, in which case
40			* they are normally declared as {@code CountedCompleter<Void>}, and
41			* will always return {@code null} as a result value. In other cases,
42			* you should override method {@link #getRawResult} to provide a
43			* result from {@code join(), invoke()}, and related methods. (Method
44			* {@link #setRawResult} by default plays no role in CountedCompleters
45			* but may be overridden for example to maintain fields holding result
46			* data.)
47			*
48	dl	1.1	* <p>A CountedCompleter that does not itself have a completer (i.e.,
49			* one for which {@link #getCompleter} returns {@code null}) can be
50			* used as a regular ForkJoinTask with this added functionality.
51			* However, any completer that in turn has another completer serves
52			* only as an internal helper for other computations, so its own task
53			* status (as reported in methods such as {@link ForkJoinTask#isDone})
54			* is arbitrary; this status changes only upon explicit invocations of
55			* {@link #complete}, {@link ForkJoinTask#cancel}, {@link
56			* ForkJoinTask#completeExceptionally} or upon exceptional completion
57			* of method {@code compute}. Upon any exceptional completion, the
58			* exception may be relayed to a task's completer (and its completer,
59			* and so on), if one exists and it has not otherwise already
60			* completed.
61			*
62			* <p><b>Sample Usages.</b>
63			*
64			* <p><b>Parallel recursive decomposition.</b> CountedCompleters may
65			* be arranged in trees similar to those often used with {@link
66			* RecursiveAction}s, although the constructions involved in setting
67	dl	1.2	* them up typically vary. Here, the completer of each task is its
68			* parent in the computation tree. Even though they entail a bit more
69	dl	1.1	* bookkeeping, CountedCompleters may be better choices when applying
70			* a possibly time-consuming operation (that cannot be further
71			* subdivided) to each element of an array or collection; especially
72			* when the operation takes a significantly different amount of time
73			* to complete for some elements than others, either because of
74			* intrinsic variation (for example IO) or auxiliary effects such as
75			* garbage collection. Because CountedCompleters provide their own
76			* continuations, other threads need not block waiting to perform
77			* them.
78			*
79			* <p> For example, here is an initial version of a class that uses
80			* divide-by-two recursive decomposition to divide work into single
81			* pieces (leaf tasks). Even when work is split into individual calls,
82			* tree-based techniques are usually preferable to directly forking
83			* leaf tasks, because they reduce inter-thread communication and
84			* improve load balancing. In the recursive case, the second of each
85			* pair of subtasks to finish triggers completion of its parent
86			* (because no result combination is performed, the default no-op
87			* implementation of method {@code onCompletion} is not overridden). A
88			* static utility method sets up the base task and invokes it:
89			*
90			* <pre> {@code
91			* class MyOperation<E> { void apply(E e) { ... } }
92			*
93	dl	1.2	* class ForEach<E> extends CountedCompleter<Void> {
94	dl	1.1	*
95			* public static <E> void forEach(ForkJoinPool pool, E[] array, MyOperation<E> op) {
96			* pool.invoke(new ForEach<E>(null, array, op, 0, array.length));
97			* }
98			*
99			* final E[] array; final MyOperation<E> op; final int lo, hi;
100	dl	1.2	* ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) {
101	dl	1.1	* super(p);
102			* this.array = array; this.op = op; this.lo = lo; this.hi = hi;
103			* }
104			*
105			* public void compute() { // version 1
106			* if (hi - lo >= 2) {
107			* int mid = (lo + hi) >>> 1;
108			* setPendingCount(2); // must set pending count before fork
109			* new ForEach(this, array, op, mid, hi).fork(); // right child
110			* new ForEach(this, array, op, lo, mid).fork(); // left child
111			* }
112			* else if (hi > lo)
113			* op.apply(array[lo]);
114			* tryComplete();
115			* }
116			* } }</pre>
117			*
118			* This design can be improved by noticing that in the recursive case,
119			* the task has nothing to do after forking its right task, so can
120			* directly invoke its left task before returning. (This is an analog
121			* of tail recursion removal.) Also, because the task returns upon
122			* executing its left task (rather than falling through to invoke
123			* tryComplete) the pending count is set to one:
124			*
125			* <pre> {@code
126			* class ForEach<E> ...
127			* public void compute() { // version 2
128			* if (hi - lo >= 2) {
129			* int mid = (lo + hi) >>> 1;
130			* setPendingCount(1); // only one pending
131			* new ForEach(this, array, op, mid, hi).fork(); // right child
132			* new ForEach(this, array, op, lo, mid).compute(); // direct invoke
133			* }
134			* else {
135			* if (hi > lo)
136			* op.apply(array[lo]);
137			* tryComplete();
138			* }
139			* }
140			* }</pre>
141			*
142			* As a further improvement, notice that the left task need not even
143			* exist. Instead of creating a new one, we can iterate using the
144	dl	1.5	* original task, and add a pending count for each fork. Additionally,
145			* this version uses {@code helpComplete} to streamline assistance in
146			* the execution of forked tasks.
147	dl	1.1	*
148			* <pre> {@code
149			* class ForEach<E> ...
150			* public void compute() { // version 3
151			* int l = lo, h = hi;
152			* while (h - l >= 2) {
153			* int mid = (l + h) >>> 1;
154			* addToPendingCount(1);
155			* new ForEach(this, array, op, mid, h).fork(); // right child
156			* h = mid;
157			* }
158			* if (h > l)
159			* op.apply(array[l]);
160	dl	1.5	* helpComplete();
161	dl	1.1	* }
162			* }</pre>
163			*
164			* Additional improvements of such classes might entail precomputing
165			* pending counts so that they can be established in constructors,
166			* specializing classes for leaf steps, subdividing by say, four,
167			* instead of two per iteration, and using an adaptive threshold
168			* instead of always subdividing down to single elements.
169			*
170			* <p><b>Recording subtasks.</b> CountedCompleter tasks that combine
171			* results of multiple subtasks usually need to access these results
172			* in method {@link #onCompletion}. As illustrated in the following
173			* class (that performs a simplified form of map-reduce where mappings
174			* and reductions are all of type {@code E}), one way to do this in
175			* divide and conquer designs is to have each subtask record its
176			* sibling, so that it can be accessed in method {@code onCompletion}.
177	dl	1.2	* This technique applies to reductions in which the order of
178			* combining left and right results does not matter; ordered
179			* reductions require explicit left/right designations. Variants of
180			* other streamlinings seen in the above examples may also apply.
181	dl	1.1	*
182			* <pre> {@code
183			* class MyMapper<E> { E apply(E v) { ... } }
184			* class MyReducer<E> { E apply(E x, E y) { ... } }
185	dl	1.2	* class MapReducer<E> extends CountedCompleter<E> {
186	dl	1.1	* final E[] array; final MyMapper<E> mapper;
187			* final MyReducer<E> reducer; final int lo, hi;
188	dl	1.2	* MapReducer<E> sibling;
189	dl	1.1	* E result;
190			* MapReducer(CountedCompleter p, E[] array, MyMapper<E> mapper,
191			* MyReducer<E> reducer, int lo, int hi) {
192			* super(p);
193			* this.array = array; this.mapper = mapper;
194			* this.reducer = reducer; this.lo = lo; this.hi = hi;
195			* }
196			* public void compute() {
197			* if (hi - lo >= 2) {
198			* int mid = (lo + hi) >>> 1;
199			* MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
200			* MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
201			* left.sibling = right;
202			* right.sibling = left;
203			* setPendingCount(1); // only right is pending
204			* right.fork();
205			* left.compute(); // directly execute left
206			* }
207			* else {
208			* if (hi > lo)
209			* result = mapper.apply(array[lo]);
210			* tryComplete();
211			* }
212			* }
213			* public void onCompletion(CountedCompleter caller) {
214			* if (caller != this) {
215			* MapReducer<E> child = (MapReducer<E>)caller;
216			* MapReducer<E> sib = child.sibling;
217			* if (sib == null \|\| sib.result == null)
218			* result = child.result;
219			* else
220			* result = reducer.apply(child.result, sib.result);
221			* }
222			* }
223	dl	1.2	* public E getRawResult() { return result; }
224	dl	1.1	*
225			* public static <E> E mapReduce(ForkJoinPool pool, E[] array,
226			* MyMapper<E> mapper, MyReducer<E> reducer) {
227	dl	1.2	* return pool.invoke(new MapReducer<E>(null, array, mapper,
228			* reducer, 0, array.length));
229	dl	1.1	* }
230			* } }</pre>
231			*
232			* <p><b>Triggers.</b> Some CountedCompleters are themselves never
233			* forked, but instead serve as bits of plumbing in other designs;
234			* including those in which the completion of one of more async tasks
235			* triggers another async task. For example:
236			*
237			* <pre> {@code
238	dl	1.2	* class HeaderBuilder extends CountedCompleter<...> { ... }
239			* class BodyBuilder extends CountedCompleter<...> { ... }
240			* class PacketSender extends CountedCompleter<...> {
241	dl	1.1	* PacketSender(...) { super(null, 1); ... } // trigger on second completion
242			* public void compute() { } // never called
243	dl	1.2	* public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
244	dl	1.1	* }
245			* // sample use:
246			* PacketSender p = new PacketSender();
247			* new HeaderBuilder(p, ...).fork();
248			* new BodyBuilder(p, ...).fork();
249			* }</pre>
250			*
251			* @since 1.8
252			* @author Doug Lea
253			*/
254	dl	1.2	public abstract class CountedCompleter<T> extends ForkJoinTask<T> {
255	dl	1.1	private static final long serialVersionUID = 5232453752276485070L;
256
257			/** This task's completer, or null if none */
258	dl	1.2	final CountedCompleter<?> completer;
259	dl	1.1	/** The number of pending tasks until completion */
260			volatile int pending;
261
262			/**
263			* Creates a new CountedCompleter with the given completer
264			* and initial pending count.
265			*
266			* @param completer this tasks completer, or {@code null} if none
267			* @param initialPendingCount the initial pending count
268			*/
269	dl	1.2	protected CountedCompleter(CountedCompleter<?> completer,
270	dl	1.1	int initialPendingCount) {
271			this.completer = completer;
272			this.pending = initialPendingCount;
273			}
274
275			/**
276			* Creates a new CountedCompleter with the given completer
277			* and an initial pending count of zero.
278			*
279			* @param completer this tasks completer, or {@code null} if none
280			*/
281	dl	1.2	protected CountedCompleter(CountedCompleter<?> completer) {
282	dl	1.1	this.completer = completer;
283			}
284
285			/**
286			* Creates a new CountedCompleter with no completer
287			* and an initial pending count of zero.
288			*/
289			protected CountedCompleter() {
290			this.completer = null;
291			}
292
293			/**
294			* The main computation performed by this task.
295			*/
296			public abstract void compute();
297
298			/**
299			* Performs an action when method {@link #tryComplete} is invoked
300			* and there are no pending counts, or when the unconditional
301			* method {@link #complete} is invoked. By default, this method
302			* does nothing.
303			*
304			* @param caller the task invoking this method (which may
305			* be this task itself).
306			*/
307	dl	1.2	public void onCompletion(CountedCompleter<?> caller) {
308	dl	1.1	}
309
310			/**
311			* Performs an action when method {@link #completeExceptionally}
312			* is invoked or method {@link #compute} throws an exception, and
313			* this task has not otherwise already completed normally. On
314			* entry to this method, this task {@link
315			* ForkJoinTask#isCompletedAbnormally}. The return value of this
316			* method controls further propagation: If {@code true} and this
317			* task has a completer, then this completer is also completed
318			* exceptionally. The default implementation of this method does
319			* nothing except return {@code true}.
320			*
321			* @param ex the exception
322			* @param caller the task invoking this method (which may
323			* be this task itself).
324			* @return true if this exception should be propagated to this
325			* tasks completer, if one exists.
326			*/
327	dl	1.2	public boolean onExceptionalCompletion(Throwable ex, CountedCompleter<?> caller) {
328	dl	1.1	return true;
329			}
330
331			/**
332			* Returns the completer established in this task's constructor,
333			* or {@code null} if none.
334			*
335			* @return the completer
336			*/
337	dl	1.2	public final CountedCompleter<?> getCompleter() {
338	dl	1.1	return completer;
339			}
340
341			/**
342			* Returns the current pending count.
343			*
344			* @return the current pending count
345			*/
346			public final int getPendingCount() {
347			return pending;
348			}
349
350			/**
351			* Sets the pending count to the given value.
352			*
353			* @param count the count
354			*/
355			public final void setPendingCount(int count) {
356			pending = count;
357			}
358
359			/**
360			* Adds (atomically) the given value to the pending count.
361			*
362			* @param delta the value to add
363			*/
364			public final void addToPendingCount(int delta) {
365			int c; // note: can replace with intrinsic in jdk8
366			do {} while (!U.compareAndSwapInt(this, PENDING, c = pending, c+delta));
367			}
368
369			/**
370			* Sets (atomically) the pending count to the given count only if
371			* it currently holds the given expected value.
372			*
373			* @param expected the expected value
374			* @param count the new value
375			* @return true is successful
376			*/
377			public final boolean compareAndSetPendingCount(int expected, int count) {
378			return U.compareAndSwapInt(this, PENDING, expected, count);
379			}
380
381			/**
382	dl	1.5	* Returns the root of the current computation; i.e., this
383			* task if it has no completer, else its completer's root.
384			*
385			* @return the root of the current computation
386			*/
387			public final CountedCompleter<?> getRoot() {
388			CountedCompleter<?> a = this, p;
389			while ((p = a.completer) != null)
390			a = p;
391			return a;
392			}
393
394			/**
395	dl	1.1	* If the pending count is nonzero, decrements the count;
396			* otherwise invokes {@link #onCompletion} and then similarly
397			* tries to complete this task's completer, if one exists,
398			* else marks this task as complete.
399			*/
400			public final void tryComplete() {
401	dl	1.2	CountedCompleter<?> a = this, s = a;
402	dl	1.1	for (int c;;) {
403			if ((c = a.pending) == 0) {
404			a.onCompletion(s);
405			if ((a = (s = a).completer) == null) {
406			s.quietlyComplete();
407			return;
408			}
409			}
410			else if (U.compareAndSwapInt(a, PENDING, c, c - 1))
411			return;
412			}
413			}
414
415			/**
416	dl	1.5	* Identical to {@link #tryComplete}, but may additionally execute
417			* other tasks within the current computation (i.e., those
418			* with the same {@link #getRoot}.
419			*/
420			public final void helpComplete() {
421			CountedCompleter<?> a = this, s = a;
422			for (int c;;) {
423			if ((c = a.pending) == 0) {
424			a.onCompletion(s);
425			if ((a = (s = a).completer) == null) {
426			s.quietlyComplete();
427			return;
428			}
429			}
430			else if (U.compareAndSwapInt(a, PENDING, c, c - 1)) {
431			CountedCompleter<?> root = a.getRoot();
432			Thread thread = Thread.currentThread();
433			ForkJoinPool.WorkQueue wq =
434	jsr166	1.6	(thread instanceof ForkJoinWorkerThread) ?
435	dl	1.5	((ForkJoinWorkerThread)thread).workQueue : null;
436			ForkJoinTask<?> t;
437			while ((t = (wq != null) ? wq.popCC(root) :
438			ForkJoinPool.popCCFromCommonPool(root)) != null) {
439			t.doExec();
440			if (root.isDone())
441			break;
442			}
443			return;
444			}
445			}
446			}
447
448			/**
449	dl	1.1	* Regardless of pending count, invokes {@link #onCompletion},
450	dl	1.2	* marks this task as complete and further triggers {@link
451			* #tryComplete} on this task's completer, if one exists. This
452			* method may be useful when forcing completion as soon as any one
453			* (versus all) of several subtask results are obtained. The
454			* given rawResult is used as an argument to {@link #setRawResult}
455			* before marking this task as complete; its value is meaningful
456			* only for classes overriding {@code setRawResult}.
457	dl	1.1	*
458	dl	1.2	* @param rawResult the raw result
459	dl	1.1	*/
460	dl	1.2	public void complete(T rawResult) {
461			CountedCompleter<?> p;
462	dl	1.1	onCompletion(this);
463	dl	1.2	setRawResult(rawResult);
464	dl	1.1	quietlyComplete();
465			if ((p = completer) != null)
466			p.tryComplete();
467			}
468
469			/**
470			* Support for FJT exception propagation
471			*/
472			void internalPropagateException(Throwable ex) {
473	dl	1.2	CountedCompleter<?> a = this, s = a;
474	dl	1.1	while (a.onExceptionalCompletion(ex, s) &&
475			(a = (s = a).completer) != null && a.status >= 0)
476			a.recordExceptionalCompletion(ex);
477			}
478
479			/**
480			* Implements execution conventions for CountedCompleters
481			*/
482			protected final boolean exec() {
483			compute();
484			return false;
485			}
486
487			/**
488	dl	1.2	* Returns the result of the computation. By default
489			* returns {@code null}, which is appropriate for {@code Void}
490			* actions, but in other cases should be overridden.
491	dl	1.1	*
492	dl	1.2	* @return the result of the computation
493	dl	1.1	*/
494	dl	1.2	public T getRawResult() { return null; }
495	dl	1.1
496			/**
497	dl	1.2	* A method that result-bearing CountedCompleters may optionally
498			* use to help maintain result data. By default, does nothing.
499	dl	1.1	*/
500	dl	1.2	protected void setRawResult(T t) { }
501	dl	1.1
502			// Unsafe mechanics
503			private static final sun.misc.Unsafe U;
504			private static final long PENDING;
505			static {
506			try {
507			U = getUnsafe();
508			PENDING = U.objectFieldOffset
509			(CountedCompleter.class.getDeclaredField("pending"));
510			} catch (Exception e) {
511			throw new Error(e);
512			}
513			}
514
515			/**
516			* Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package.
517			* Replace with a simple call to Unsafe.getUnsafe when integrating
518			* into a jdk.
519			*
520			* @return a sun.misc.Unsafe
521			*/
522			private static sun.misc.Unsafe getUnsafe() {
523			try {
524			return sun.misc.Unsafe.getUnsafe();
525			} catch (SecurityException se) {
526			try {
527			return java.security.AccessController.doPrivileged
528			(new java.security
529			.PrivilegedExceptionAction<sun.misc.Unsafe>() {
530			public sun.misc.Unsafe run() throws Exception {
531			java.lang.reflect.Field f = sun.misc
532			.Unsafe.class.getDeclaredField("theUnsafe");
533			f.setAccessible(true);
534			return (sun.misc.Unsafe) f.get(null);
535			}});
536			} catch (java.security.PrivilegedActionException e) {
537			throw new RuntimeException("Could not initialize intrinsics",
538			e.getCause());
539			}
540			}
541			}
542
543			}