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