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