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
7package 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 */
136public abstract class RecursiveAction extends ForkJoinTask<Void> {
137    private static final long serialVersionUID = 5232453952276485070L;
138
139    /**
140     * The main computation performed by this task.
141     */
142    protected abstract void compute();
143
144    /**
145     * Always returns {@code null}.
146     *
147     * @return {@code null} always
148     */
149    public final Void getRawResult() { return null; }
150
151    /**
152     * Requires null completion value.
153     */
154    protected final void setRawResult(Void mustBeNull) { }
155
156    /**
157     * Implements execution conventions for RecursiveActions.
158     */
159    protected final boolean exec() {
160        compute();
161        return true;
162    }
163
164}
165