test/loops/BinaryAsyncAction.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

/**
 * AsyncActions that are always linked in binary parent-child
 * relationships. Compared to Recursive tasks, BinaryAsyncActions may
 * have smaller stack space footprints and faster completion mechanics
 * but higher per-task footprints. Compared to LinkedAsyncActions,
 * BinaryAsyncActions are simpler to use and have less overhead in
 * typical usages but are restricted to binary computation trees.
 *
 * <p>Upon construction, a BinaryAsyncAction does not bear any
 * linkages. For non-root tasks, links must be established using
 * method {@link #linkSubtasks} before use.
 *
 * <p><b>Sample Usage.</b>  A version of Fibonacci:
 * <pre>
 * class Fib extends BinaryAsyncAction {
 *   final int n;
 *   int result;
 *   Fib(int n) { this.n = n; }
 *   protected void compute() {
 *     if (n &gt; 1) {
 *       linkAndForkSubtasks(new Fib(n-1), new Fib(n-2));
 *     else {
 *       result = n; // fib(0)==0; fib(1)==1
 *       complete();
 *     }
 *   }
 *   protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {
 *     result = ((Fib)x).result + ((Fib)y).result;
 *   }
 * }
 * </pre>
 * An alternative, and usually faster, strategy is to instead use a
 * loop to fork subtasks:
 * <pre>
 *   protected void compute() {
 *     Fib f = this;
 *     while (f.n &gt; 1) {
 *       Fib left = new Fib(f.n - 1);
 *       Fib right = new Fib(f.n - 2);
 *       f.linkSubtasks(left, right);
 *       right.fork(); // fork right
 *       f = left;     // loop on left
 *     }
 *     f.result = f.n;
 *     f.complete();
 *   }
 * }
 * </pre>
 */
public abstract class BinaryAsyncAction extends ForkJoinTask<Void> {

    /**
     * Parent to propagate completion; nulled after completion to
     * avoid retaining entire tree as garbage
     */
    private BinaryAsyncAction parent;

    /**
     * Sibling to access on subtask joins, also nulled after completion.
     */
    private BinaryAsyncAction sibling;

    /**
     * Creates a new action. Unless this is a root task, you will need
     * to link it using method {@link #linkSubtasks} before forking as
     * a subtask.
     */
    protected BinaryAsyncAction() {
    }

    public final Void getRawResult() { return null; }
    protected final void setRawResult(Void mustBeNull) { }

    /**
     * Establishes links for the given tasks to have the current task
     * as parent, and each other as siblings.
     * @param x one subtask
     * @param y the other subtask
     * @throws NullPointerException if either argument is null
     */
    public final void linkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {
        x.parent = y.parent = this;
        x.sibling = y;
        y.sibling = x;
    }

    /**
     * Overridable callback action triggered upon {@code complete} of
     * subtasks.  Upon invocation, both subtasks have completed.
     * After return, this task {@code isDone} and is joinable by
     * other tasks. The default version of this method does nothing.
     * But it may be overridden in subclasses to perform some action
     * (for example a reduction) when this task is completes.
     * @param x one subtask
     * @param y the other subtask
     */
    protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {
    }

    /**
     * Overridable callback action triggered by
     * {@code completeExceptionally}.  Upon invocation, this task has
     * aborted due to an exception (accessible via
     * {@code getException}). If this method returns {@code true},
     * the exception propagates to the current task's
     * parent. Otherwise, normal completion is propagated.  The
     * default version of this method does nothing and returns
     * {@code true}.
     * @return true if this task's exception should be propagated to
     * this task's parent
     */
    protected boolean onException() {
        return true;
    }

    /**
     * Equivalent in effect to invoking {@link #linkSubtasks} and then
     * forking both tasks.
     * @param x one subtask
     * @param y the other subtask
     */
    public void linkAndForkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {
        linkSubtasks(x, y);
        y.fork();
        x.fork();
    }

    /** Basic per-task complete */
    private void completeThis() {
        super.complete(null);
    }

    /** Basic per-task completeExceptionally */
    private void completeThisExceptionally(Throwable ex) {
        super.completeExceptionally(ex);
    }

    /*
     * We use one bit join count on taskState. The first arriving
     * thread CAS's from 0 to 1. The second ultimately sets status
     * to signify completion.
     */

    /**
     * Completes this task, and if this task has a sibling that is
     * also complete, invokes {@code onComplete} of parent task, and so
     * on. If an exception is encountered, tasks instead
     * {@code completeExceptionally}.
     */
    public final void complete() {
        // todo: Use tryUnfork without possibly blowing stack
        BinaryAsyncAction a = this;
        for (;;) {
            BinaryAsyncAction s = a.sibling;
            BinaryAsyncAction p = a.parent;
            a.sibling = null;
            a.parent = null;
            a.completeThis();
            if (p == null || p.markForkJoinTask())
                break;
            try {
                p.onComplete(a, s);
            } catch (Throwable rex) {
                p.completeExceptionally(rex);
                return;
            }
            a = p;
        }
    }

    /**
     * Completes this task abnormally. Unless this task already
     * cancelled or aborted, upon invocation, this method invokes
     * {@code onException}, and then, depending on its return value,
     * completes parent (if one exists) exceptionally or normally.  To
     * avoid unbounded exception loops, this method aborts if an
     * exception is encountered in any {@code onException}
     * invocation.
     * @param ex the exception to throw when joining this task
     * @throws NullPointerException if ex is null
     * @throws Throwable if any invocation of
     * {@code onException} does so
     */
    public final void completeExceptionally(Throwable ex) {
        BinaryAsyncAction a = this;
        while (!a.isCompletedAbnormally()) {
            a.completeThisExceptionally(ex);
            BinaryAsyncAction s = a.sibling;
            if (s != null)
                s.cancel(false);
            if (!a.onException() || (a = a.parent) == null)
                break;
        }
    }

    /**
     * Returns this task's parent, or null if none or this task
     * is already complete.
     * @return this task's parent, or null if none
     */
    public final BinaryAsyncAction getParent() {
        return parent;
    }

    /**
     * Returns this task's sibling, or null if none or this task is
     * already complete.
     * @return this task's sibling, or null if none
     */
    public BinaryAsyncAction getSibling() {
        return sibling;
    }

    /**
     * Resets the internal bookkeeping state of this task, erasing
     * parent and child linkages.
     */
    public void reinitialize() {
        parent = sibling = null;
        super.reinitialize();
    }

<<<<<<< BinaryAsyncAction.java
=======
    /**
     * Gets the control state, which is initially zero, or negative if
     * this task has completed or cancelled. Once negative, the value
     * cannot be changed.
     * @return control state
     */
    protected final int getControlState() {
        return controlState;
    }

    /**
     * Atomically sets the control state to the given updated value if
     * the current value is and equal to the expected value.
     * @param expect the expected value
     * @param update the new value
     * @return true if successful
     */
    protected final boolean compareAndSetControlState(int expect,
                                                      int update) {
        return controlStateUpdater.compareAndSet(this, expect, update);
    }

    /**
     * Attempts to set the control state to the given value, failing if
     * this task is already completed or the control state value would be
     * negative.
     * @param value the new value
     * @return true if successful
     */
    protected final void setControlState(int value) {
        controlState = value;
    }

    /**
     * Increments the control state.
     * @param value the new value
     */
    protected final void incrementControlState() {
        controlStateUpdater.incrementAndGet(this);
    }

    /**
     * Decrements the control state.
     * @return true if successful
     */
    protected final void decrementControlState() {
        controlStateUpdater.decrementAndGet(this);
    }
>>>>>>> 1.14

}
Revision:	1.17
Committed:	Sat Sep 12 18:11:24 2015 UTC (8 years, 8 months ago) by dl
Branch:	MAIN
Changes since 1.16:	+4 -5 lines
Log Message:	Use jdk8 methods
#	User	Rev	Content
1	dl	1.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	jsr166	1.6	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7			import java.util.concurrent.*;
8			import java.util.concurrent.atomic.*;
9
10			/**
11			* AsyncActions that are always linked in binary parent-child
12			* relationships. Compared to Recursive tasks, BinaryAsyncActions may
13			* have smaller stack space footprints and faster completion mechanics
14			* but higher per-task footprints. Compared to LinkedAsyncActions,
15			* BinaryAsyncActions are simpler to use and have less overhead in
16	jsr166	1.16	* typical usages but are restricted to binary computation trees.
17	dl	1.1	*
18	jsr166	1.11	* <p>Upon construction, a BinaryAsyncAction does not bear any
19	dl	1.1	* linkages. For non-root tasks, links must be established using
20	jsr166	1.12	* method {@link #linkSubtasks} before use.
21	dl	1.1	*
22	jsr166	1.7	* <p><b>Sample Usage.</b> A version of Fibonacci:
23	dl	1.1	* <pre>
24			* class Fib extends BinaryAsyncAction {
25			* final int n;
26			* int result;
27			* Fib(int n) { this.n = n; }
28			* protected void compute() {
29			* if (n > 1) {
30	jsr166	1.9	* linkAndForkSubtasks(new Fib(n-1), new Fib(n-2));
31	dl	1.1	* else {
32	jsr166	1.9	* result = n; // fib(0)==0; fib(1)==1
33			* complete();
34	dl	1.1	* }
35			* }
36			* protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {
37	jsr166	1.8	* result = ((Fib)x).result + ((Fib)y).result;
38	dl	1.1	* }
39			* }
40			* </pre>
41	jsr166	1.14	* An alternative, and usually faster, strategy is to instead use a
42	dl	1.1	* loop to fork subtasks:
43			* <pre>
44			* protected void compute() {
45			* Fib f = this;
46			* while (f.n > 1) {
47	jsr166	1.9	* Fib left = new Fib(f.n - 1);
48			* Fib right = new Fib(f.n - 2);
49			* f.linkSubtasks(left, right);
50			* right.fork(); // fork right
51			* f = left; // loop on left
52	dl	1.1	* }
53			* f.result = f.n;
54			* f.complete();
55			* }
56			* }
57			* </pre>
58			*/
59			public abstract class BinaryAsyncAction extends ForkJoinTask<Void> {
60
61			/**
62			* Parent to propagate completion; nulled after completion to
63			* avoid retaining entire tree as garbage
64			*/
65			private BinaryAsyncAction parent;
66
67			/**
68			* Sibling to access on subtask joins, also nulled after completion.
69			*/
70			private BinaryAsyncAction sibling;
71
72			/**
73			* Creates a new action. Unless this is a root task, you will need
74	jsr166	1.12	* to link it using method {@link #linkSubtasks} before forking as
75	dl	1.1	* a subtask.
76			*/
77			protected BinaryAsyncAction() {
78			}
79
80			public final Void getRawResult() { return null; }
81			protected final void setRawResult(Void mustBeNull) { }
82
83			/**
84			* Establishes links for the given tasks to have the current task
85			* as parent, and each other as siblings.
86			* @param x one subtask
87			* @param y the other subtask
88	jsr166	1.14	* @throws NullPointerException if either argument is null
89	dl	1.1	*/
90			public final void linkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {
91			x.parent = y.parent = this;
92			x.sibling = y;
93			y.sibling = x;
94			}
95
96			/**
97	jsr166	1.12	* Overridable callback action triggered upon {@code complete} of
98	dl	1.1	* subtasks. Upon invocation, both subtasks have completed.
99	jsr166	1.12	* After return, this task {@code isDone} and is joinable by
100	jsr166	1.5	* other tasks. The default version of this method does nothing.
101			* But it may be overridden in subclasses to perform some action
102			* (for example a reduction) when this task is completes.
103	dl	1.1	* @param x one subtask
104			* @param y the other subtask
105			*/
106			protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {
107			}
108
109			/**
110			* Overridable callback action triggered by
111	jsr166	1.12	* {@code completeExceptionally}. Upon invocation, this task has
112	dl	1.1	* aborted due to an exception (accessible via
113	jsr166	1.12	* {@code getException}). If this method returns {@code true},
114	dl	1.1	* the exception propagates to the current task's
115			* parent. Otherwise, normal completion is propagated. The
116			* default version of this method does nothing and returns
117	jsr166	1.12	* {@code true}.
118	dl	1.1	* @return true if this task's exception should be propagated to
119	jsr166	1.15	* this task's parent
120	dl	1.1	*/
121			protected boolean onException() {
122			return true;
123			}
124
125			/**
126	jsr166	1.12	* Equivalent in effect to invoking {@link #linkSubtasks} and then
127	dl	1.1	* forking both tasks.
128			* @param x one subtask
129			* @param y the other subtask
130			*/
131			public void linkAndForkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {
132			linkSubtasks(x, y);
133			y.fork();
134			x.fork();
135			}
136
137			/** Basic per-task complete */
138			private void completeThis() {
139			super.complete(null);
140			}
141
142			/** Basic per-task completeExceptionally */
143			private void completeThisExceptionally(Throwable ex) {
144			super.completeExceptionally(ex);
145			}
146
147			/*
148			* We use one bit join count on taskState. The first arriving
149			* thread CAS's from 0 to 1. The second ultimately sets status
150			* to signify completion.
151			*/
152
153			/**
154			* Completes this task, and if this task has a sibling that is
155	jsr166	1.12	* also complete, invokes {@code onComplete} of parent task, and so
156	dl	1.1	* on. If an exception is encountered, tasks instead
157	jsr166	1.12	* {@code completeExceptionally}.
158	dl	1.1	*/
159			public final void complete() {
160			// todo: Use tryUnfork without possibly blowing stack
161			BinaryAsyncAction a = this;
162			for (;;) {
163			BinaryAsyncAction s = a.sibling;
164			BinaryAsyncAction p = a.parent;
165			a.sibling = null;
166			a.parent = null;
167			a.completeThis();
168	dl	1.17	if (p == null \|\| p.markForkJoinTask())
169	dl	1.1	break;
170			try {
171			p.onComplete(a, s);
172	jsr166	1.3	} catch (Throwable rex) {
173	dl	1.1	p.completeExceptionally(rex);
174			return;
175			}
176			a = p;
177			}
178			}
179
180			/**
181			* Completes this task abnormally. Unless this task already
182			* cancelled or aborted, upon invocation, this method invokes
183	jsr166	1.12	* {@code onException}, and then, depending on its return value,
184	jsr166	1.13	* completes parent (if one exists) exceptionally or normally. To
185	dl	1.1	* avoid unbounded exception loops, this method aborts if an
186	jsr166	1.12	* exception is encountered in any {@code onException}
187	dl	1.1	* invocation.
188			* @param ex the exception to throw when joining this task
189			* @throws NullPointerException if ex is null
190			* @throws Throwable if any invocation of
191	jsr166	1.14	* {@code onException} does so
192	dl	1.1	*/
193			public final void completeExceptionally(Throwable ex) {
194			BinaryAsyncAction a = this;
195			while (!a.isCompletedAbnormally()) {
196			a.completeThisExceptionally(ex);
197			BinaryAsyncAction s = a.sibling;
198			if (s != null)
199			s.cancel(false);
200			if (!a.onException() \|\| (a = a.parent) == null)
201			break;
202			}
203			}
204
205			/**
206			* Returns this task's parent, or null if none or this task
207			* is already complete.
208	jsr166	1.14	* @return this task's parent, or null if none
209	dl	1.1	*/
210			public final BinaryAsyncAction getParent() {
211			return parent;
212			}
213
214			/**
215			* Returns this task's sibling, or null if none or this task is
216			* already complete.
217	jsr166	1.14	* @return this task's sibling, or null if none
218	dl	1.1	*/
219			public BinaryAsyncAction getSibling() {
220			return sibling;
221			}
222
223			/**
224			* Resets the internal bookkeeping state of this task, erasing
225			* parent and child linkages.
226			*/
227			public void reinitialize() {
228			parent = sibling = null;
229			super.reinitialize();
230			}
231
232	dl	1.17	<<<<<<< BinaryAsyncAction.java
233			=======
234	dl	1.1	/**
235			* Gets the control state, which is initially zero, or negative if
236			* this task has completed or cancelled. Once negative, the value
237			* cannot be changed.
238			* @return control state
239			*/
240			protected final int getControlState() {
241			return controlState;
242			}
243
244			/**
245			* Atomically sets the control state to the given updated value if
246			* the current value is and equal to the expected value.
247			* @param expect the expected value
248			* @param update the new value
249			* @return true if successful
250			*/
251	jsr166	1.2	protected final boolean compareAndSetControlState(int expect,
252	dl	1.1	int update) {
253			return controlStateUpdater.compareAndSet(this, expect, update);
254			}
255
256			/**
257			* Attempts to set the control state to the given value, failing if
258			* this task is already completed or the control state value would be
259			* negative.
260			* @param value the new value
261			* @return true if successful
262			*/
263			protected final void setControlState(int value) {
264			controlState = value;
265			}
266
267			/**
268	jsr166	1.14	* Increments the control state.
269	dl	1.1	* @param value the new value
270			*/
271			protected final void incrementControlState() {
272			controlStateUpdater.incrementAndGet(this);
273			}
274
275			/**
276	jsr166	1.14	* Decrements the control state.
277	dl	1.1	* @return true if successful
278			*/
279			protected final void decrementControlState() {
280			controlStateUpdater.decrementAndGet(this);
281			}
282	dl	1.17	>>>>>>> 1.14
283	dl	1.1
284			}