1 /*
2  * Written by Doug Lea with assistance from members of JCP JSR-166
3  * Expert Group and released to the public domain, as explained at
4  * http://creativecommons.org/publicdomain/zero/1.0/
5  */
6 
7 package java.util.concurrent;
8 
9 /**
10  * A recursive resultless {@link ForkJoinTask}.  This class
11  * establishes conventions to parameterize resultless actions as
12  * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the
13  * only valid value of type {@code Void}, methods such as {@code join}
14  * always return {@code null} upon completion.
15  *
16  * <p><b>Sample Usages.</b> Here is a simple but complete ForkJoin
17  * sort that sorts a given {@code long[]} array:
18  *
19  *  <pre> {@code
20  * static class SortTask extends RecursiveAction {
21  *   final long[] array; final int lo, hi;
22  *   SortTask(long[] array, int lo, int hi) {
23  *     this.array = array; this.lo = lo; this.hi = hi;
24  *   }
25  *   SortTask(long[] array) { this(array, 0, array.length); }
26  *   protected void compute() {
27  *     if (hi - lo < THRESHOLD)
28  *       sortSequentially(lo, hi);
29  *     else {
30  *       int mid = (lo + hi) >>> 1;
31  *       invokeAll(new SortTask(array, lo, mid),
32  *                 new SortTask(array, mid, hi));
33  *       merge(lo, mid, hi);
34  *     }
35  *   }
36  *   // implementation details follow:
37  *   static final int THRESHOLD = 1000;
38  *   void sortSequentially(int lo, int hi) {
39  *     Arrays.sort(array, lo, hi);
40  *   }
41  *   void merge(int lo, int mid, int hi) {
42  *     long[] buf = Arrays.copyOfRange(array, lo, mid);
43  *     for (int i = 0, j = lo, k = mid; i < buf.length; j++)
44  *       array[j] = (k == hi || buf[i] < array[k]) ?
45  *         buf[i++] : array[k++];
46  *   }
47  * }}</pre>
48  *
49  * You could then sort {@code anArray} by creating {@code new
50  * SortTask(anArray)} and invoking it in a ForkJoinPool.  As a more
51  * concrete simple example, the following task increments each element
52  * of an array:
53  *  <pre> {@code
54  * class IncrementTask extends RecursiveAction {
55  *   final long[] array; final int lo, hi;
56  *   IncrementTask(long[] array, int lo, int hi) {
57  *     this.array = array; this.lo = lo; this.hi = hi;
58  *   }
59  *   protected void compute() {
60  *     if (hi - lo < THRESHOLD) {
61  *       for (int i = lo; i < hi; ++i)
62  *         array[i]++;
63  *     }
64  *     else {
65  *       int mid = (lo + hi) >>> 1;
66  *       invokeAll(new IncrementTask(array, lo, mid),
67  *                 new IncrementTask(array, mid, hi));
68  *     }
69  *   }
70  * }}</pre>
71  *
72  * <p>The following example illustrates some refinements and idioms
73  * that may lead to better performance: RecursiveActions need not be
74  * fully recursive, so long as they maintain the basic
75  * divide-and-conquer approach. Here is a class that sums the squares
76  * of each element of a double array, by subdividing out only the
77  * right-hand-sides of repeated divisions by two, and keeping track of
78  * them with a chain of {@code next} references. It uses a dynamic
79  * threshold based on method {@code getSurplusQueuedTaskCount}, but
80  * counterbalances potential excess partitioning by directly
81  * performing leaf actions on unstolen tasks rather than further
82  * subdividing.
83  *
84  *  <pre> {@code
85  * double sumOfSquares(ForkJoinPool pool, double[] array) {
86  *   int n = array.length;
87  *   Applyer a = new Applyer(array, 0, n, null);
88  *   pool.invoke(a);
89  *   return a.result;
90  * }
91  *
92  * class Applyer extends RecursiveAction {
93  *   final double[] array;
94  *   final int lo, hi;
95  *   double result;
96  *   Applyer next; // keeps track of right-hand-side tasks
97  *   Applyer(double[] array, int lo, int hi, Applyer next) {
98  *     this.array = array; this.lo = lo; this.hi = hi;
99  *     this.next = next;
100  *   }
101  *
102  *   double atLeaf(int l, int h) {
103  *     double sum = 0;
104  *     for (int i = l; i < h; ++i) // perform leftmost base step
105  *       sum += array[i] * array[i];
106  *     return sum;
107  *   }
108  *
109  *   protected void compute() {
110  *     int l = lo;
111  *     int h = hi;
112  *     Applyer right = null;
113  *     while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
114  *       int mid = (l + h) >>> 1;
115  *       right = new Applyer(array, mid, h, right);
116  *       right.fork();
117  *       h = mid;
118  *     }
119  *     double sum = atLeaf(l, h);
120  *     while (right != null) {
121  *       if (right.tryUnfork()) // directly calculate if not stolen
122  *         sum += right.atLeaf(right.lo, right.hi);
123  *       else {
124  *         right.join();
125  *         sum += right.result;
126  *       }
127  *       right = right.next;
128  *     }
129  *     result = sum;
130  *   }
131  * }}</pre>
132  *
133  * @since 1.7
134  * @author Doug Lea
135  */
136 public abstract class RecursiveAction extends ForkJoinTask<Void> {
137     private static final long serialVersionUID = 5232453952276485070L;
138 
139     /**
140      * The main computation performed by this task.
141      */
compute()142     protected abstract void compute();
143 
144     /**
145      * Always returns {@code null}.
146      *
147      * @return {@code null} always
148      */
getRawResult()149     public final Void getRawResult() { return null; }
150 
151     /**
152      * Requires null completion value.
153      */
setRawResult(Void mustBeNull)154     protected final void setRawResult(Void mustBeNull) { }
155 
156     /**
157      * Implements execution conventions for RecursiveActions.
158      */
exec()159     protected final boolean exec() {
160         compute();
161         return true;
162     }
163 
164 }
165