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