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