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/licenses/publicdomain
  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 join always
  43  * return {@code null} upon completion.
  44  *
  45  * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that
  46  * sorts a given {@code long[]} array:
  47  *
  48  *  <pre> {@code
  49  * class SortTask extends RecursiveAction {
  50  *   final long[] array; final int lo; final int hi;
  51  *   SortTask(long[] array, int lo, int hi) {
  52  *     this.array = array; this.lo = lo; this.hi = hi;
  53  *   }
  54  *   protected void compute() {
  55  *     if (hi - lo < THRESHOLD)
  56  *       sequentiallySort(array, lo, hi);
  57  *     else {
  58  *       int mid = (lo + hi) >>> 1;
  59  *       invokeAll(new SortTask(array, lo, mid),
  60  *                 new SortTask(array, mid, hi));
  61  *       merge(array, lo, hi);
  62  *     }
  63  *   }
  64  * }}</pre>
  65  *
  66  * You could then sort {@code anArray} by creating {@code new
  67  * SortTask(anArray, 0, anArray.length-1) } and invoking it in a
  68  * ForkJoinPool.  As a more concrete simple example, the following
  69  * task increments each element of an array:
  70  *  <pre> {@code
  71  * class IncrementTask extends RecursiveAction {
  72  *   final long[] array; final int lo; final int hi;
  73  *   IncrementTask(long[] array, int lo, int hi) {
  74  *     this.array = array; this.lo = lo; this.hi = hi;
  75  *   }
  76  *   protected void compute() {
  77  *     if (hi - lo < THRESHOLD) {
  78  *       for (int i = lo; i < hi; ++i)
  79  *         array[i]++;
  80  *     }
  81  *     else {
  82  *       int mid = (lo + hi) >>> 1;
  83  *       invokeAll(new IncrementTask(array, lo, mid),
  84  *                 new IncrementTask(array, mid, hi));
  85  *     }
  86  *   }
  87  * }}</pre>
  88  *
  89  * <p>The following example illustrates some refinements and idioms
  90  * that may lead to better performance: RecursiveActions need not be
  91  * fully recursive, so long as they maintain the basic
  92  * divide-and-conquer approach. Here is a class that sums the squares
  93  * of each element of a double array, by subdividing out only the
  94  * right-hand-sides of repeated divisions by two, and keeping track of
  95  * them with a chain of {@code next} references. It uses a dynamic
  96  * threshold based on method {@code getSurplusQueuedTaskCount}, but
  97  * counterbalances potential excess partitioning by directly
  98  * performing leaf actions on unstolen tasks rather than further
  99  * subdividing.
 100  *
 101  *  <pre> {@code
 102  * double sumOfSquares(ForkJoinPool pool, double[] array) {
 103  *   int n = array.length;
 104  *   Applyer a = new Applyer(array, 0, n, null);
 105  *   pool.invoke(a);
 106  *   return a.result;
 107  * }
 108  *
 109  * class Applyer extends RecursiveAction {
 110  *   final double[] array;
 111  *   final int lo, hi;
 112  *   double result;
 113  *   Applyer next; // keeps track of right-hand-side tasks
 114  *   Applyer(double[] array, int lo, int hi, Applyer next) {
 115  *     this.array = array; this.lo = lo; this.hi = hi;
 116  *     this.next = next;
 117  *   }
 118  *
 119  *   double atLeaf(int l, int h) {
 120  *     double sum = 0;
 121  *     for (int i = l; i < h; ++i) // perform leftmost base step
 122  *       sum += array[i] * array[i];
 123  *     return sum;
 124  *   }
 125  *
 126  *   protected void compute() {
 127  *     int l = lo;
 128  *     int h = hi;
 129  *     Applyer right = null;
 130  *     while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
 131  *        int mid = (l + h) >>> 1;
 132  *        right = new Applyer(array, mid, h, right);
 133  *        right.fork();
 134  *        h = mid;
 135  *     }
 136  *     double sum = atLeaf(l, h);
 137  *     while (right != null) {
 138  *        if (right.tryUnfork()) // directly calculate if not stolen
 139  *          sum += right.atLeaf(right.lo, right.hi);
 140  *       else {
 141  *          right.join();
 142  *          sum += right.result;
 143  *        }
 144  *        right = right.next;
 145  *      }
 146  *     result = sum;
 147  *   }
 148  * }}</pre>
 149  *
 150  * @since 1.7
 151  * @author Doug Lea
 152  */
 153 public abstract class RecursiveAction extends ForkJoinTask<Void> {
 154     private static final long serialVersionUID = 5232453952276485070L;
 155 
 156     /**
 157      * The main computation performed by this task.
 158      */
 159     protected abstract void compute();
 160 
 161     /**
 162      * Always returns {@code null}.
 163      *
 164      * @return {@code null} always
 165      */
 166     public final Void getRawResult() { return null; }
 167 
 168     /**
 169      * Requires null completion value.
 170      */
 171     protected final void setRawResult(Void mustBeNull) { }
 172 
 173     /**
 174      * Implements execution conventions for RecursiveActions.
 175      */
 176     protected final boolean exec() {
 177         compute();
 178         return true;
 179     }
 180 
 181 }