src/jsr166y/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 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
 * #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.
 *
 * <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.
 *
 * <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 is 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. 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 {
 *
 *     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:
 *
 * <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();
 *     }
 * }</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}.
 * For clarity, this class uses explicit left and right subtasks, but
 * variants of other streamlinings seen in the above example 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;
 *     }
 *     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 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;
 *     }
 * } }</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 extends ForkJoinTask<Void> {
    /** 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();

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

    /**
     * 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);
    }

    /**
     * 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;
            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;
        }
    }

    /**
     * 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;
        onCompletion(this);
        quietlyComplete();
        if ((p = completer) != null)
            p.tryComplete();
    }

    /**
     * Implements execution conventions for CountedCompleters
     */
    protected final boolean exec() {
        compute();
        return false;
    }

    /**
     * Always returns {@code null}.
     *
     * @return {@code null} always
     */
    public final Void getRawResult() { return null; }

    /**
     * Requires null completion value.
     */
    protected final void setRawResult(Void mustBeNull) { }

    /**
     * Support for FJT exception propagation
     */
    final ForkJoinTask<?> internalGetCompleter() { return completer; }

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