RecursiveAction.java revision 2362
84N/A/*
84N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
84N/A *
84N/A * This code is free software; you can redistribute it and/or modify it
84N/A * under the terms of the GNU General Public License version 2 only, as
84N/A * published by the Free Software Foundation. Oracle designates this
84N/A * particular file as subject to the "Classpath" exception as provided
84N/A * by Oracle in the LICENSE file that accompanied this code.
84N/A *
84N/A * This code is distributed in the hope that it will be useful, but WITHOUT
84N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
84N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
84N/A * version 2 for more details (a copy is included in the LICENSE file that
84N/A * accompanied this code).
84N/A *
84N/A * You should have received a copy of the GNU General Public License version
84N/A * 2 along with this work; if not, write to the Free Software Foundation,
84N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
84N/A *
873N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
84N/A * or visit www.oracle.com if you need additional information or have any
84N/A * questions.
84N/A */
84N/A
84N/A/*
828N/A * This file is available under and governed by the GNU General Public
84N/A * License version 2 only, as published by the Free Software Foundation.
84N/A * However, the following notice accompanied the original version of this
84N/A * file:
828N/A *
84N/A * Written by Doug Lea with assistance from members of JCP JSR-166
84N/A * Expert Group and released to the public domain, as explained at
623N/A * http://creativecommons.org/licenses/publicdomain
84N/A */
84N/A
84N/Apackage java.util.concurrent;
84N/A
84N/A/**
84N/A * A recursive resultless {@link ForkJoinTask}. This class
619N/A * establishes conventions to parameterize resultless actions as
84N/A * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the
623N/A * only valid value of type {@code Void}, methods such as join always
84N/A * return {@code null} upon completion.
1194N/A *
1194N/A * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that
623N/A * sorts a given {@code long[]} array:
623N/A *
623N/A * <pre> {@code
623N/A * class SortTask extends RecursiveAction {
84N/A * final long[] array; final int lo; final int hi;
1186N/A * SortTask(long[] array, int lo, int hi) {
1304N/A * this.array = array; this.lo = lo; this.hi = hi;
84N/A * }
84N/A * protected void compute() {
1186N/A * if (hi - lo < THRESHOLD)
1186N/A * sequentiallySort(array, lo, hi);
1186N/A * else {
1304N/A * int mid = (lo + hi) >>> 1;
1186N/A * invokeAll(new SortTask(array, lo, mid),
84N/A * new SortTask(array, mid, hi));
84N/A * merge(array, lo, hi);
1194N/A * }
1591N/A * }
84N/A * }}</pre>
481N/A *
84N/A * You could then sort {@code anArray} by creating {@code new
1186N/A * SortTask(anArray, 0, anArray.length-1) } and invoking it in a
1186N/A * ForkJoinPool. As a more concrete simple example, the following
1186N/A * task increments each element of an array:
1186N/A * <pre> {@code
1510N/A * class IncrementTask extends RecursiveAction {
828N/A * final long[] array; final int lo; final int hi;
828N/A * IncrementTask(long[] array, int lo, int hi) {
828N/A * this.array = array; this.lo = lo; this.hi = hi;
828N/A * }
828N/A * protected void compute() {
828N/A * if (hi - lo < THRESHOLD) {
828N/A * for (int i = lo; i < hi; ++i)
623N/A * array[i]++;
1777N/A * }
1777N/A * else {
1777N/A * int mid = (lo + hi) >>> 1;
828N/A * invokeAll(new IncrementTask(array, lo, mid),
84N/A * new IncrementTask(array, mid, hi));
1777N/A * }
1777N/A * }
1777N/A * }}</pre>
1777N/A *
84N/A * <p>The following example illustrates some refinements and idioms
84N/A * that may lead to better performance: RecursiveActions need not be
* fully recursive, so long as they maintain the basic
* divide-and-conquer approach. Here is a class that sums the squares
* of each element of a double array, by subdividing out only the
* right-hand-sides of repeated divisions by two, and keeping track of
* them with a chain of {@code next} references. It uses a dynamic
* threshold based on method {@code getSurplusQueuedTaskCount}, but
* counterbalances potential excess partitioning by directly
* performing leaf actions on unstolen tasks rather than further
* subdividing.
*
* <pre> {@code
* double sumOfSquares(ForkJoinPool pool, double[] array) {
* int n = array.length;
* Applyer a = new Applyer(array, 0, n, null);
* pool.invoke(a);
* return a.result;
* }
*
* class Applyer extends RecursiveAction {
* final double[] array;
* final int lo, hi;
* double result;
* Applyer next; // keeps track of right-hand-side tasks
* Applyer(double[] array, int lo, int hi, Applyer next) {
* this.array = array; this.lo = lo; this.hi = hi;
* this.next = next;
* }
*
* double atLeaf(int l, int h) {
* double sum = 0;
* for (int i = l; i < h; ++i) // perform leftmost base step
* sum += array[i] * array[i];
* return sum;
* }
*
* protected void compute() {
* int l = lo;
* int h = hi;
* Applyer right = null;
* while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
* int mid = (l + h) >>> 1;
* right = new Applyer(array, mid, h, right);
* right.fork();
* h = mid;
* }
* double sum = atLeaf(l, h);
* while (right != null) {
* if (right.tryUnfork()) // directly calculate if not stolen
* sum += right.atLeaf(right.lo, right.hi);
* else {
* right.helpJoin();
* sum += right.result;
* }
* right = right.next;
* }
* result = sum;
* }
* }}</pre>
*
* @since 1.7
* @author Doug Lea
*/
public abstract class RecursiveAction extends ForkJoinTask<Void> {
private static final long serialVersionUID = 5232453952276485070L;
/**
* The main computation performed by this task.
*/
protected abstract void compute();
/**
* Always returns null.
*/
public final Void getRawResult() { return null; }
/**
* Requires null completion value.
*/
protected final void setRawResult(Void mustBeNull) { }
/**
* Implements execution conventions for RecursiveActions.
*/
protected final boolean exec() {
compute();
return true;
}
}