ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166y/CountedCompleter.java

Comparing jsr166/src/jsr166y/CountedCompleter.java (file contents):
Revision 1.3 by dl, Thu Aug 16 12:25:03 2012 UTC vs.
Revision 1.16 by jsr166, Sat Nov 24 03:46:28 2012 UTC

#	Line 7 | Line 7
7		package jsr166y;
8
9		/**
10	<	* A {@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
10	>	* A {@link ForkJoinTask} with a completion action performed when
11	>	* triggered and there are no remaining pending
12	>	* actions. CountedCompleters are in general more robust in the
13	>	* presence of subtask stalls and blockage than are other forms of
14	>	* ForkJoinTasks, but are less intuitive to program.  Uses of
15	>	* CountedCompleter are similar to those of other completion based
16	>	* components (such as {@link java.nio.channels.CompletionHandler})
17	>	* except that multiple <em>pending</em> completions may be necessary
18	>	* to trigger the {@link #onCompletion} action, not just one. Unless
19	>	* initialized otherwise, the {@link #getPendingCount pending count}
20	>	* starts at zero, but may be (atomically) changed using methods
21	>	* {@link #setPendingCount}, {@link #addToPendingCount}, and {@link
22		* #compareAndSetPendingCount}. Upon invocation of {@link
23		* #tryComplete}, if the pending action count is nonzero, it is
24		* decremented; otherwise, the completion action is performed, and if
25		* this completer itself has a completer, the process is continued
26		* with its completer.  As is the case with related synchronization
27	<	* components such as {@link Phaser} and {@link
28	<	* java.util.concurrent.Semaphore} these methods affect only internal
29	<	* counts; they do not establish any further internal bookkeeping. In
30	<	* particular, the identities of pending tasks are not maintained. As
31	<	* illustrated below, you can create subclasses that do record some or
32	<	* all pended tasks or their results when needed.
27	>	* components such as {@link java.util.concurrent.Phaser Phaser} and
28	>	* {@link java.util.concurrent.Semaphore Semaphore}, these methods
29	>	* affect only internal counts; they do not establish any further
30	>	* internal bookkeeping. In particular, the identities of pending
31	>	* tasks are not maintained. As illustrated below, you can create
32	>	* subclasses that do record some or all pending tasks or their
33	>	* results when needed.  As illustrated below, utility methods
34	>	* supporting customization of completion traversals are also
35	>	* provided. However, because CountedCompleters provide only basic
36	>	* synchronization mechanisms, it may be useful to create further
37	>	* abstract subclasses that maintain linkages, fields, and additional
38	>	* support methods appropriate for a set of related usages.
39		*
40		* <p>A concrete CountedCompleter class must define method {@link
41	<	* #compute}, that should, in almost all use cases, invoke {@code
42	<	* tryComplete()} once before returning. The class may also optionally
43	<	* override method {@link #onCompletion} to perform an action upon
44	<	* normal completion, and method {@link #onExceptionalCompletion} to
45	<	* perform an action upon any exception.
41	>	* #compute}, that should in most cases (as illustrated below), invoke
42	>	* {@code tryComplete()} once before returning. The class may also
43	>	* optionally override method {@link #onCompletion} to perform an
44	>	* action upon normal completion, and method {@link
45	>	* #onExceptionalCompletion} to perform an action upon any exception.
46		*
47		* <p>CountedCompleters most often do not bear results, in which case
48		* they are normally declared as {@code CountedCompleter<Void>}, and
49		* will always return {@code null} as a result value.  In other cases,
50		* you should override method {@link #getRawResult} to provide a
51	<	* result from {@code join(), invoke()}, and related methods. (Method
52	<	* {@link #setRawResult} by default plays no role in CountedCompleters
53	<	* but may be overridden for example to maintain fields holding result
54	<	* data.)
51	>	* result from {@code join(), invoke()}, and related methods.  In
52	>	* general, this method should return the value of a field (or a
53	>	* function of one or more fields) of the CountedCompleter object that
54	>	* holds the result upon completion. Method {@link #setRawResult} by
55	>	* default plays no role in CountedCompleters.  It is possible, but
56	>	* rarely applicable, to override this method to maintain other
57	>	* objects or fields holding result data.
58		*
59		* <p>A CountedCompleter that does not itself have a completer (i.e.,
60		* one for which {@link #getCompleter} returns {@code null}) can be
#	Line 57 | Line 68 | package jsr166y;
68		* of method {@code compute}. Upon any exceptional completion, the
69		* exception may be relayed to a task's completer (and its completer,
70		* and so on), if one exists and it has not otherwise already
71	<	* completed.
71	>	* completed. Similarly, cancelling an internal CountedCompleter has
72	>	* only a local effect on that completer, so is not often useful.
73		*
74		* <p><b>Sample Usages.</b>
75		*
#	Line 76 | Line 88 | package jsr166y;
88		* continuations, other threads need not block waiting to perform
89		* them.
90		*
91	<	* <p> For example, here is an initial version of a class that uses
91	>	* <p>For example, here is an initial version of a class that uses
92		* divide-by-two recursive decomposition to divide work into single
93		* pieces (leaf tasks). Even when work is split into individual calls,
94		* tree-based techniques are usually preferable to directly forking
#	Line 85 | Line 97 | package jsr166y;
97		* pair of subtasks to finish triggers completion of its parent
98		* (because no result combination is performed, the default no-op
99		* implementation of method {@code onCompletion} is not overridden). A
100	<	* static utility method sets up the base task and invokes it:
100	>	* static utility method sets up the base task and invokes it
101	>	* (here, implicitly using the {@link ForkJoinPool#commonPool()}).
102		*
103		* <pre> {@code
104		* class MyOperation<E> { void apply(E e) { ... }  }
105		*
106		* class ForEach<E> extends CountedCompleter<Void> {
107		*
108	<	*     public static <E> void forEach(ForkJoinPool pool, E[] array, MyOperation<E> op) {
109	<	*         pool.invoke(new ForEach<E>(null, array, op, 0, array.length));
110	<	*     }
111	<	*
112	<	*     final E[] array; final MyOperation<E> op; final int lo, hi;
113	<	*     ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) {
114	<	*         super(p);
115	<	*         this.array = array; this.op = op; this.lo = lo; this.hi = hi;
116	<	*     }
117	<	*
118	<	*     public void compute() { // version 1
119	<	*         if (hi - lo >= 2) {
120	<	*             int mid = (lo + hi) >>> 1;
121	<	*             setPendingCount(2); // must set pending count before fork
122	<	*             new ForEach(this, array, op, mid, hi).fork(); // right child
123	<	*             new ForEach(this, array, op, lo, mid).fork(); // left child
111	<	*         }
112	<	*         else if (hi > lo)
113	<	*             op.apply(array[lo]);
114	<	*         tryComplete();
108	>	*   public static <E> void forEach(E[] array, MyOperation<E> op) {
109	>	*     new ForEach<E>(null, array, op, 0, array.length).invoke();
110	>	*   }
111	>	*
112	>	*   final E[] array; final MyOperation<E> op; final int lo, hi;
113	>	*   ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) {
114	>	*     super(p);
115	>	*     this.array = array; this.op = op; this.lo = lo; this.hi = hi;
116	>	*   }
117	>	*
118	>	*   public void compute() { // version 1
119	>	*     if (hi - lo >= 2) {
120	>	*       int mid = (lo + hi) >>> 1;
121	>	*       setPendingCount(2); // must set pending count before fork
122	>	*       new ForEach(this, array, op, mid, hi).fork(); // right child
123	>	*       new ForEach(this, array, op, lo, mid).fork(); // left child
124		*     }
125	+	*     else if (hi > lo)
126	+	*       op.apply(array[lo]);
127	+	*     tryComplete();
128	+	*   }
129		* } }</pre>
130		*
131		* This design can be improved by noticing that in the recursive case,
#	Line 124 | Line 137 | package jsr166y;
137		*
138		* <pre> {@code
139		* class ForEach<E> ...
140	<	*     public void compute() { // version 2
141	<	*         if (hi - lo >= 2) {
142	<	*             int mid = (lo + hi) >>> 1;
143	<	*             setPendingCount(1); // only one pending
144	<	*             new ForEach(this, array, op, mid, hi).fork(); // right child
145	<	*             new ForEach(this, array, op, lo, mid).compute(); // direct invoke
146	<	*         }
147	<	*         else {
148	<	*             if (hi > lo)
149	<	*                 op.apply(array[lo]);
150	<	*             tryComplete();
138	<	*         }
140	>	*   public void compute() { // version 2
141	>	*     if (hi - lo >= 2) {
142	>	*       int mid = (lo + hi) >>> 1;
143	>	*       setPendingCount(1); // only one pending
144	>	*       new ForEach(this, array, op, mid, hi).fork(); // right child
145	>	*       new ForEach(this, array, op, lo, mid).compute(); // direct invoke
146	>	*     }
147	>	*     else {
148	>	*       if (hi > lo)
149	>	*         op.apply(array[lo]);
150	>	*       tryComplete();
151		*     }
152	+	*   }
153		* }</pre>
154		*
155		* As a further improvement, notice that the left task need not even
156		* exist.  Instead of creating a new one, we can iterate using the
157	<	* original task, and add a pending count for each fork:
157	>	* original task, and add a pending count for each fork. Additionally,
158	>	* because no task in this tree implements an {@link #onCompletion}
159	>	* method, {@code tryComplete()} can be replaced with {@link
160	>	* #propagateCompletion}.
161		*
162		* <pre> {@code
163		* class ForEach<E> ...
164	<	*     public void compute() { // version 3
165	<	*         int l = lo,  h = hi;
166	<	*         while (h - l >= 2) {
167	<	*             int mid = (l + h) >>> 1;
168	<	*             addToPendingCount(1);
169	<	*             new ForEach(this, array, op, mid, h).fork(); // right child
170	<	*             h = mid;
155	<	*         }
156	<	*         if (h > l)
157	<	*             op.apply(array[l]);
158	<	*         tryComplete();
164	>	*   public void compute() { // version 3
165	>	*     int l = lo,  h = hi;
166	>	*     while (h - l >= 2) {
167	>	*       int mid = (l + h) >>> 1;
168	>	*       addToPendingCount(1);
169	>	*       new ForEach(this, array, op, mid, h).fork(); // right child
170	>	*       h = mid;
171		*     }
172	+	*     if (h > l)
173	+	*       op.apply(array[l]);
174	+	*     propagateCompletion();
175	+	*   }
176		* }</pre>
177		*
178		* Additional improvements of such classes might entail precomputing
#	Line 165 | Line 181 | package jsr166y;
181		* instead of two per iteration, and using an adaptive threshold
182		* instead of always subdividing down to single elements.
183		*
184	+	* <p><b>Searching.</b> A tree of CountedCompleters can search for a
185	+	* value or property in different parts of a data structure, and
186	+	* report a result in an {@link java.util.concurrent.AtomicReference}
187	+	* as soon as one is found. The others can poll the result to avoid
188	+	* unnecessary work. (You could additionally {@link #cancel} other
189	+	* tasks, but it is usually simpler and more efficient to just let
190	+	* them notice that the result is set and if so skip further
191	+	* processing.)  Illustrating again with an array using full
192	+	* partitioning (again, in practice, leaf tasks will almost always
193	+	* process more than one element):
194	+	*
195	+	* <pre> {@code
196	+	* class Searcher<E> extends CountedCompleter<E> {
197	+	*   final E[] array; final AtomicReference<E> result; final int lo, hi;
198	+	*   Searcher(CountedCompleter<?> p, E[] array, AtomicReference<E> result, int lo, int hi) {
199	+	*     super(p);
200	+	*     this.array = array; this.result = result; this.lo = lo; this.hi = hi;
201	+	*   }
202	+	*   public E getRawResult() { return result.get(); }
203	+	*   public void compute() { // similar to ForEach version 3
204	+	*     int l = lo,  h = hi;
205	+	*     while (result.get() == null && h >= l) {
206	+	*       if (h - l >= 2) {
207	+	*         int mid = (l + h) >>> 1;
208	+	*         addToPendingCount(1);
209	+	*         new Searcher(this, array, result, mid, h).fork();
210	+	*         h = mid;
211	+	*       }
212	+	*       else {
213	+	*         E x = array[l];
214	+	*         if (matches(x) && result.compareAndSet(null, x))
215	+	*           quietlyCompleteRoot(); // root task is now joinable
216	+	*         break;
217	+	*       }
218	+	*     }
219	+	*     tryComplete(); // normally complete whether or not found
220	+	*   }
221	+	*   boolean matches(E e) { ... } // return true if found
222	+	*
223	+	*   public static <E> E search(E[] array) {
224	+	*       return new Searcher<E>(null, array, new AtomicReference<E>(), 0, array.length).invoke();
225	+	*   }
226	+	*}}</pre>
227	+	*
228	+	* In this example, as well as others in which tasks have no other
229	+	* effects except to compareAndSet a common result, the trailing
230	+	* unconditional invocation of {@code tryComplete} could be made
231	+	* conditional ({@code if (result.get() == null) tryComplete();})
232	+	* because no further bookkeeping is required to manage completions
233	+	* once the root task completes.
234	+	*
235		* <p><b>Recording subtasks.</b> CountedCompleter tasks that combine
236		* results of multiple subtasks usually need to access these results
237		* in method {@link #onCompletion}. As illustrated in the following
#	Line 181 | Line 248 | package jsr166y;
248		* class MyMapper<E> { E apply(E v) {  ...  } }
249		* class MyReducer<E> { E apply(E x, E y) {  ...  } }
250		* class MapReducer<E> extends CountedCompleter<E> {
251	<	*     final E[] array; final MyMapper<E> mapper;
252	<	*     final MyReducer<E> reducer; final int lo, hi;
253	<	*     MapReducer<E> sibling;
254	<	*     E result;
255	<	*     MapReducer(CountedCompleter p, E[] array, MyMapper<E> mapper,
256	<	*                MyReducer<E> reducer, int lo, int hi) {
257	<	*         super(p);
258	<	*         this.array = array; this.mapper = mapper;
259	<	*         this.reducer = reducer; this.lo = lo; this.hi = hi;
251	>	*   final E[] array; final MyMapper<E> mapper;
252	>	*   final MyReducer<E> reducer; final int lo, hi;
253	>	*   MapReducer<E> sibling;
254	>	*   E result;
255	>	*   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
256	>	*              MyReducer<E> reducer, int lo, int hi) {
257	>	*     super(p);
258	>	*     this.array = array; this.mapper = mapper;
259	>	*     this.reducer = reducer; this.lo = lo; this.hi = hi;
260	>	*   }
261	>	*   public void compute() {
262	>	*     if (hi - lo >= 2) {
263	>	*       int mid = (lo + hi) >>> 1;
264	>	*       MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
265	>	*       MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
266	>	*       left.sibling = right;
267	>	*       right.sibling = left;
268	>	*       setPendingCount(1); // only right is pending
269	>	*       right.fork();
270	>	*       left.compute();     // directly execute left
271		*     }
272	<	*     public void compute() {
273	<	*         if (hi - lo >= 2) {
274	<	*             int mid = (lo + hi) >>> 1;
275	<	*             MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
198	<	*             MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
199	<	*             left.sibling = right;
200	<	*             right.sibling = left;
201	<	*             setPendingCount(1); // only right is pending
202	<	*             right.fork();
203	<	*             left.compute();     // directly execute left
204	<	*         }
205	<	*         else {
206	<	*             if (hi > lo)
207	<	*                 result = mapper.apply(array[lo]);
208	<	*             tryComplete();
209	<	*         }
272	>	*     else {
273	>	*       if (hi > lo)
274	>	*           result = mapper.apply(array[lo]);
275	>	*       tryComplete();
276		*     }
277	<	*     public void onCompletion(CountedCompleter caller) {
278	<	*         if (caller != this) {
279	<	*            MapReducer<E> child = (MapReducer<E>)caller;
280	<	*            MapReducer<E> sib = child.sibling;
281	<	*            if (sib == null || sib.result == null)
282	<	*                result = child.result;
283	<	*            else
284	<	*                result = reducer.apply(child.result, sib.result);
285	<	*         }
277	>	*   }
278	>	*   public void onCompletion(CountedCompleter<?> caller) {
279	>	*     if (caller != this) {
280	>	*      MapReducer<E> child = (MapReducer<E>)caller;
281	>	*      MapReducer<E> sib = child.sibling;
282	>	*      if (sib == null || sib.result == null)
283	>	*        result = child.result;
284	>	*      else
285	>	*        result = reducer.apply(child.result, sib.result);
286		*     }
287	<	*     public E getRawResult() { return result; }
287	>	*   }
288	>	*   public E getRawResult() { return result; }
289		*
290	<	*     public static <E> E mapReduce(ForkJoinPool pool, E[] array,
291	<	*                                   MyMapper<E> mapper, MyReducer<E> reducer) {
292	<	*         return pool.invoke(new MapReducer<E>(null, array, mapper,
293	<	*                                              reducer, 0, array.length));
227	<	*     }
290	>	*   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
291	>	*     return new MapReducer<E>(null, array, mapper, reducer,
292	>	*                              0, array.length).invoke();
293	>	*   }
294		* } }</pre>
295		*
296	+	* Here, method {@code onCompletion} takes a form common to many
297	+	* completion designs that combine results. This callback-style method
298	+	* is triggered once per task, in either of the two different contexts
299	+	* in which the pending count is, or becomes, zero: (1) by a task
300	+	* itself, if its pending count is zero upon invocation of {@code
301	+	* tryComplete}, or (2) by any of its subtasks when they complete and
302	+	* decrement the pending count to zero. The {@code caller} argument
303	+	* distinguishes cases.  Most often, when the caller is {@code this},
304	+	* no action is necessary. Otherwise the caller argument can be used
305	+	* (usually via a cast) to supply a value (and/or links to other
306	+	* values) to be combined.  Asuuming proper use of pending counts, the
307	+	* actions inside {@code onCompletion} occur (once) upon completion of
308	+	* a task and its subtasks. No additional synchronization is required
309	+	* within this method to ensure thread safety of accesses to fields of
310	+	* this task or other completed tasks.
311	+	*
312	+	* <p><b>Completion Traversals</b>. If using {@code onCompletion} to
313	+	* process completions is inapplicable or inconvenient, you can use
314	+	* methods {@link #firstComplete} and {@link #nextComplete} to create
315	+	* custom traversals.  For example, to define a MapReducer that only
316	+	* splits out right-hand tasks in the form of the third ForEach
317	+	* example, the completions must cooperatively reduce along
318	+	* unexhausted subtask links, which can be done as follows:
319	+	*
320	+	* <pre> {@code
321	+	* class MapReducer<E> extends CountedCompleter<E> { // version 2
322	+	*   final E[] array; final MyMapper<E> mapper;
323	+	*   final MyReducer<E> reducer; final int lo, hi;
324	+	*   MapReducer<E> forks, next; // record subtask forks in list
325	+	*   E result;
326	+	*   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
327	+	*              MyReducer<E> reducer, int lo, int hi, MapReducer<E> next) {
328	+	*     super(p);
329	+	*     this.array = array; this.mapper = mapper;
330	+	*     this.reducer = reducer; this.lo = lo; this.hi = hi;
331	+	*     this.next = next;
332	+	*   }
333	+	*   public void compute() {
334	+	*     int l = lo,  h = hi;
335	+	*     while (h - l >= 2) {
336	+	*       int mid = (l + h) >>> 1;
337	+	*       addToPendingCount(1);
338	+	*       (forks = new MapReducer(this, array, mapper, reducer, mid, h, forks)).fork;
339	+	*       h = mid;
340	+	*     }
341	+	*     if (h > l)
342	+	*       result = mapper.apply(array[l]);
343	+	*     // process completions by reducing along and advancing subtask links
344	+	*     for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
345	+	*       for (MapReducer t = (MapReducer)c, s = t.forks;  s != null; s = t.forks = s.next)
346	+	*         t.result = reducer.apply(t.result, s.result);
347	+	*     }
348	+	*   }
349	+	*   public E getRawResult() { return result; }
350	+	*
351	+	*   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
352	+	*     return new MapReducer<E>(null, array, mapper, reducer,
353	+	*                              0, array.length, null).invoke();
354	+	*   }
355	+	* }}</pre>
356	+	*
357		* <p><b>Triggers.</b> Some CountedCompleters are themselves never
358		* forked, but instead serve as bits of plumbing in other designs;
359		* including those in which the completion of one of more async tasks
#	Line 236 | Line 363 | package jsr166y;
363		* class HeaderBuilder extends CountedCompleter<...> { ... }
364		* class BodyBuilder extends CountedCompleter<...> { ... }
365		* class PacketSender extends CountedCompleter<...> {
366	<	*     PacketSender(...) { super(null, 1); ... } // trigger on second completion
367	<	*     public void compute() { } // never called
368	<	*     public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
366	>	*   PacketSender(...) { super(null, 1); ... } // trigger on second completion
367	>	*   public void compute() { } // never called
368	>	*   public void onCompletion(CountedCompleter<?> caller) { sendPacket(); }
369		* }
370		* // sample use:
371		* PacketSender p = new PacketSender();
#	Line 297 | Line 424 | public abstract class CountedCompleter<T
424		* Performs an action when method {@link #tryComplete} is invoked
425		* and there are no pending counts, or when the unconditional
426		* method {@link #complete} is invoked.  By default, this method
427	<	* does nothing.
427	>	* does nothing. You can distinguish cases by checking the
428	>	* identity of the given caller argument. If not equal to {@code
429	>	* this}, then it is typically a subtask that may contain results
430	>	* (and/or links to other results) to combine.
431		*
432		* @param caller the task invoking this method (which may
433		* be this task itself).
#	Line 370 | Line 500 | public abstract class CountedCompleter<T
500		*
501		* @param expected the expected value
502		* @param count the new value
503	<	* @return true is successful
503	>	* @return true if successful
504		*/
505		public final boolean compareAndSetPendingCount(int expected, int count) {
506		return U.compareAndSwapInt(this, PENDING, expected, count);
507		}
508
509		/**
510	+	* If the pending count is nonzero, (atomically) decrements it.
511	+	*
512	+	* @return the initial (undecremented) pending count holding on entry
513	+	* to this method
514	+	*/
515	+	public final int decrementPendingCountUnlessZero() {
516	+	int c;
517	+	do {} while ((c = pending) != 0 &&
518	+	!U.compareAndSwapInt(this, PENDING, c, c - 1));
519	+	return c;
520	+	}
521	+
522	+	/**
523	+	* Returns the root of the current computation; i.e., this
524	+	* task if it has no completer, else its completer's root.
525	+	*
526	+	* @return the root of the current computation
527	+	*/
528	+	public final CountedCompleter<?> getRoot() {
529	+	CountedCompleter<?> a = this, p;
530	+	while ((p = a.completer) != null)
531	+	a = p;
532	+	return a;
533	+	}
534	+
535	+	/**
536		* If the pending count is nonzero, decrements the count;
537		* otherwise invokes {@link #onCompletion} and then similarly
538		* tries to complete this task's completer, if one exists,
#	Line 398 | Line 554 | public abstract class CountedCompleter<T
554		}
555
556		/**
557	+	* Equivalent to {@link #tryComplete} but does not invoke {@link
558	+	* #onCompletion} along the completion path: If the pending count
559	+	* is nonzero, decrements the count; otherwise, similarly tries to
560	+	* complete this task's completer, if one exists, else marks this
561	+	* task as complete. This method may be useful in cases where
562	+	* {@code onCompletion} should not, or need not, be invoked for
563	+	* each completer in a computation.
564	+	*/
565	+	public final void propagateCompletion() {
566	+	CountedCompleter<?> a = this, s = a;
567	+	for (int c;;) {
568	+	if ((c = a.pending) == 0) {
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		* Regardless of pending count, invokes {@link #onCompletion},
581		* marks this task as complete and further triggers {@link
582	<	* #tryComplete} on this task's completer, if one exists. This
404	<	* method may be useful when forcing completion as soon as any one
405	<	* (versus all) of several subtask results are obtained.  The
582	>	* #tryComplete} on this task's completer, if one exists.  The
583		* given rawResult is used as an argument to {@link #setRawResult}
584	<	* before marking this task as complete; its value is meaningful
585	<	* only for classes overriding {@code setRawResult}.
584	>	* before invoking {@link #onCompletion} or marking this task as
585	>	* complete; its value is meaningful only for classes overriding
586	>	* {@code setRawResult}.
587	>	*
588	>	* <p>This method may be useful when forcing completion as soon as
589	>	* any one (versus all) of several subtask results are obtained.
590	>	* However, in the common (and recommended) case in which {@code
591	>	* setRawResult} is not overridden, this effect can be obtained
592	>	* more simply using {@code quietlyCompleteRoot();}.
593		*
594		* @param rawResult the raw result
595		*/
596		public void complete(T rawResult) {
597		CountedCompleter<?> p;
414	–	onCompletion(this);
598		setRawResult(rawResult);
599	+	onCompletion(this);
600		quietlyComplete();
601		if ((p = completer) != null)
602		p.tryComplete();
603		}
604
605	+
606	+	/**
607	+	* If this task's pending count is zero, returns this task;
608	+	* otherwise decrements its pending count and returns {@code
609	+	* null}. This method is designed to be used with {@link
610	+	* #nextComplete} in completion traversal loops.
611	+	*
612	+	* @return this task, if pending count was zero, else {@code null}
613	+	*/
614	+	public final CountedCompleter<?> firstComplete() {
615	+	for (int c;;) {
616	+	if ((c = pending) == 0)
617	+	return this;
618	+	else if (U.compareAndSwapInt(this, PENDING, c, c - 1))
619	+	return null;
620	+	}
621	+	}
622	+
623	+	/**
624	+	* If this task does not have a completer, invokes {@link
625	+	* ForkJoinTask#quietlyComplete} and returns {@code null}.  Or, if
626	+	* this task's pending count is non-zero, decrements its pending
627	+	* count and returns {@code null}.  Otherwise, returns the
628	+	* completer.  This method can be used as part of a completion
629	+	* traversal loop for homogenous task hierarchies:
630	+	*
631	+	* <pre> {@code
632	+	* for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
633	+	*   // ... process c ...
634	+	* }}</pre>
635	+	*
636	+	* @return the completer, or {@code null} if none
637	+	*/
638	+	public final CountedCompleter<?> nextComplete() {
639	+	CountedCompleter<?> p;
640	+	if ((p = completer) != null)
641	+	return p.firstComplete();
642	+	else {
643	+	quietlyComplete();
644	+	return null;
645	+	}
646	+	}
647	+
648	+	/**
649	+	* Equivalent to {@code getRoot().quietlyComplete()}.
650	+	*/
651	+	public final void quietlyCompleteRoot() {
652	+	for (CountedCompleter<?> a = this, p;;) {
653	+	if ((p = a.completer) == null) {
654	+	a.quietlyComplete();
655	+	return;
656	+	}
657	+	a = p;
658	+	}
659	+	}
660	+
661		/**
662		* Support for FJT exception propagation
663		*/
#	Line 439 | Line 679 | public abstract class CountedCompleter<T
679		/**
680		* Returns the result of the computation. By default
681		* returns {@code null}, which is appropriate for {@code Void}
682	<	* actions, but in other cases should be overridden.
682	>	* actions, but in other cases should be overridden, almost
683	>	* always to return a field or function of a field that
684	>	* holds the result upon completion.
685		*
686		* @return the result of the computation
687		*/
#	Line 448 | Line 690 | public abstract class CountedCompleter<T
690		/**
691		* A method that result-bearing CountedCompleters may optionally
692		* use to help maintain result data.  By default, does nothing.
693	+	* Overrides are not recommended. However, if this method is
694	+	* overridden to update existing objects or fields, then it must
695	+	* in general be defined to be thread-safe.
696		*/
697		protected void setRawResult(T t) { }
698
#	Line 456 | Line 701 | public abstract class CountedCompleter<T
701		private static final long PENDING;
702		static {
703		try {
704	<	U = getUnsafe();
704	>	U = sun.misc.Unsafe.getUnsafe();
705		PENDING = U.objectFieldOffset
706		(CountedCompleter.class.getDeclaredField("pending"));
707		} catch (Exception e) {
#	Line 464 | Line 709 | public abstract class CountedCompleter<T
709		}
710		}
711
467	–
712		/**
713		* Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
714		* Replace with a simple call to Unsafe.getUnsafe when integrating
#	Line 492 | Line 736 | public abstract class CountedCompleter<T
736		}
737		}
738		}
495	–
739		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines