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