RecursiveAction.java revision 2362
84N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 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 * 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 * 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. 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 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 * 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 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 * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that 623N/A * sorts a given {@code long[]} array: 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 * protected void compute() { 1186N/A * sequentiallySort(array, lo, hi); 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); 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: 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 * protected void compute() { 828N/A * if (hi - lo < THRESHOLD) { 828N/A * for (int i = lo; i < hi; ++i) 1777N/A * int mid = (lo + hi) >>> 1; 828N/A * invokeAll(new IncrementTask(array, lo, mid), 84N/A * new IncrementTask(array, mid, hi)); 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 * double sumOfSquares(ForkJoinPool pool, double[] array) { * Applyer a = new Applyer(array, 0, n, null); * class Applyer extends RecursiveAction { * 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; * double atLeaf(int l, int h) { * for (int i = l; i < h; ++i) // perform leftmost base step * sum += array[i] * array[i]; * protected void compute() { * while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) { * int mid = (l + h) >>> 1; * right = new Applyer(array, mid, h, right); * double sum = atLeaf(l, h); * while (right != null) { * if (right.tryUnfork()) // directly calculate if not stolen * sum += right.atLeaf(right.lo, right.hi); * The main computation performed by this task. * Requires null completion value. * Implements execution conventions for RecursiveActions. protected final boolean exec() {