1a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson/* 229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is free software; you can redistribute it and/or modify it 529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * published by the Free Software Foundation. Oracle designates this 729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * particular file as subject to the "Classpath" exception as provided 829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 1129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 1429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * accompanied this code). 1529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * You should have received a copy of the GNU General Public License version 1729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 1829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * or visit www.oracle.com if you need additional information or have any 2229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * questions. 2329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer */ 2429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer 2529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer/* 2629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This file is available under and governed by the GNU General Public 2729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 2829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * However, the following notice accompanied the original version of this 2929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * file: 3029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 31a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 32a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Expert Group and released to the public domain, as explained at 33a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 34a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 35a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 36a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonpackage java.util.concurrent; 37a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 38a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson/** 39a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * A recursive resultless {@link ForkJoinTask}. This class 40a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * establishes conventions to parameterize resultless actions as 41a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the 42a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * only valid value of type {@code Void}, methods such as {@code join} 43a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * always return {@code null} upon completion. 44a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 45a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p><b>Sample Usages.</b> Here is a simple but complete ForkJoin 46a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * sort that sorts a given {@code long[]} array: 47a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 48b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 49a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * static class SortTask extends RecursiveAction { 50a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * final long[] array; final int lo, hi; 51a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * SortTask(long[] array, int lo, int hi) { 52a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this.array = array; this.lo = lo; this.hi = hi; 53a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 54a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * SortTask(long[] array) { this(array, 0, array.length); } 55a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * protected void compute() { 56a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if (hi - lo < THRESHOLD) 57a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * sortSequentially(lo, hi); 58a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else { 59a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int mid = (lo + hi) >>> 1; 60a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * invokeAll(new SortTask(array, lo, mid), 61a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * new SortTask(array, mid, hi)); 62a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * merge(lo, mid, hi); 63a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 64a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 65a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * // implementation details follow: 6691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * static final int THRESHOLD = 1000; 67a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * void sortSequentially(int lo, int hi) { 68a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Arrays.sort(array, lo, hi); 69a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 70a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * void merge(int lo, int mid, int hi) { 71a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * long[] buf = Arrays.copyOfRange(array, lo, mid); 72a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (int i = 0, j = lo, k = mid; i < buf.length; j++) 73a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * array[j] = (k == hi || buf[i] < array[k]) ? 74a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * buf[i++] : array[k++]; 75a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 76a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 77a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 78a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * You could then sort {@code anArray} by creating {@code new 79a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * SortTask(anArray)} and invoking it in a ForkJoinPool. As a more 80a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * concrete simple example, the following task increments each element 81a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of an array: 82b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 83a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * class IncrementTask extends RecursiveAction { 84a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * final long[] array; final int lo, hi; 85a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * IncrementTask(long[] array, int lo, int hi) { 86a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this.array = array; this.lo = lo; this.hi = hi; 87a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 88a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * protected void compute() { 89a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if (hi - lo < THRESHOLD) { 90a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (int i = lo; i < hi; ++i) 91a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * array[i]++; 92a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 93a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else { 94a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int mid = (lo + hi) >>> 1; 95a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * invokeAll(new IncrementTask(array, lo, mid), 96a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * new IncrementTask(array, mid, hi)); 97a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 98a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 99a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 100a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 101a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>The following example illustrates some refinements and idioms 102a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that may lead to better performance: RecursiveActions need not be 103a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * fully recursive, so long as they maintain the basic 104a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * divide-and-conquer approach. Here is a class that sums the squares 105a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of each element of a double array, by subdividing out only the 106a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * right-hand-sides of repeated divisions by two, and keeping track of 107a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * them with a chain of {@code next} references. It uses a dynamic 108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * threshold based on method {@code getSurplusQueuedTaskCount}, but 109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * counterbalances potential excess partitioning by directly 110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * performing leaf actions on unstolen tasks rather than further 111a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * subdividing. 112a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 113b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * double sumOfSquares(ForkJoinPool pool, double[] array) { 115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int n = array.length; 116a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Applyer a = new Applyer(array, 0, n, null); 117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * pool.invoke(a); 118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * return a.result; 119a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 120a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 121a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * class Applyer extends RecursiveAction { 122a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * final double[] array; 123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * final int lo, hi; 124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * double result; 125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Applyer next; // keeps track of right-hand-side tasks 126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Applyer(double[] array, int lo, int hi, Applyer next) { 127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this.array = array; this.lo = lo; this.hi = hi; 128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this.next = next; 129a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 130a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 131a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * double atLeaf(int l, int h) { 132a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * double sum = 0; 133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (int i = l; i < h; ++i) // perform leftmost base step 134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * sum += array[i] * array[i]; 135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * return sum; 136a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * protected void compute() { 139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int l = lo; 140a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int h = hi; 141a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Applyer right = null; 142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) { 14391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * int mid = (l + h) >>> 1; 14491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * right = new Applyer(array, mid, h, right); 14591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * right.fork(); 14691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * h = mid; 147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * double sum = atLeaf(l, h); 149a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * while (right != null) { 15091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * if (right.tryUnfork()) // directly calculate if not stolen 15191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * sum += right.atLeaf(right.lo, right.hi); 152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else { 15391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * right.join(); 15491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * sum += right.result; 15591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * } 15691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * right = right.next; 15791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * } 158a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * result = sum; 159a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 160a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 161a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @since 1.7 163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @author Doug Lea 164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 165a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonpublic abstract class RecursiveAction extends ForkJoinTask<Void> { 166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long serialVersionUID = 5232453952276485070L; 167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The main computation performed by this task. 170a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 171a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson protected abstract void compute(); 172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 173a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Always returns {@code null}. 175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code null} always 177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 178a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public final Void getRawResult() { return null; } 179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Requires null completion value. 182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson protected final void setRawResult(Void mustBeNull) { } 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Implements execution conventions for RecursiveActions. 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson protected final boolean exec() { 189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson compute(); 190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 191a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 192a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 193a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson} 194