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
 *
 */

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 uasges but are restricted to binary computation trees.
 *
 * <p> Upon construction, an BinaryAsyncAction does not bear any
 * linkages. For non-root tasks, links must be established using
 * method <tt>linkSubtasks</tt> 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> {
    private volatile int controlState;

    static final AtomicIntegerFieldUpdater<BinaryAsyncAction> controlStateUpdater =
        AtomicIntegerFieldUpdater.newUpdater(BinaryAsyncAction.class, "controlState");

    /**
     * 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 <tt>linkSubtasks</tt> 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 <tt>complete</tt> of
     * subtasks.  Upon invocation, both subtasks have completed.
     * After return, this task <tt>isDone</tt> and is joinable by
     * other tasks. The default version of this method does
     * nothing. But it may 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
     * <tt>completeExceptionally</tt>.  Upon invocation, this task has
     * aborted due to an exception (accessible via
     * <tt>getException</tt>). If this method returns <tt>true</tt>,
     * the exception propagates to the current task's
     * parent. Otherwise, normal completion is propagated.  The
     * default version of this method does nothing and returns
     * <tt>true</tt>.
     * @return true if this task's exception should be propagated to
     * this tasks parent.
     */
    protected boolean onException() {
        return true;
    }

    /**
     * Equivalent in effect to invoking <tt>linkSubtasks</tt> 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 <tt>onComplete</tt> of parent task, and so
     * on. If an exception is encountered, tasks instead
     * <tt>completeExceptionally</tt>.
     */
    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.compareAndSetControlState(0, 1))
                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
     * <tt>onException</tt>, and then, depending on its return value,
     * completees parent (if one exists) exceptionally or normally.  To
     * avoid unbounded exception loops, this method aborts if an
     * exception is encountered in any <tt>onException</tt>
     * invocation.
     * @param ex the exception to throw when joining this task
     * @throws NullPointerException if ex is null
     * @throws Throwable if any invocation of
     * <tt>onException</tt> 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();
    }

    /**
     * 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;
    }

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

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

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