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

package jsr166y.forkjoin;

/**
 * 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 <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
 *        finish();
 *     }
 *   }
 *   protected void onFinish(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.finish();
 *   }
 * }
 * </pre>
 */
public abstract class BinaryAsyncAction extends AsyncAction {
    /**
     * 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;

    /*
     * Note: we also piggyback one bit join count on
     * ForkJoinTask.status field. The first arriving thread CAS's
     * status from 0 to 1. The second ultimately sets to negative
     * value to signify completion.
     */

    /**
     * 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() {
    }

    /**
     * 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>finish</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 onFinish(BinaryAsyncAction x, BinaryAsyncAction y) {
    }

    /**
     * Overridable callback action triggered by
     * <tt>finishExceptionally</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 task's 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();
    }

    /**
     * Completes this task, and if this task has a sibling that is
     * also complete, invokes <tt>onFinish</tt> of parent task, and so
     * on. If an exception is encountered, tasks instead
     * <tt>finishExceptionally</tt>.
     */
    public final void finish() {
        // todo: Use removeIfNextLocalTask(s) without possibly blowing stack
        BinaryAsyncAction a = this;
        for (;;) {
            BinaryAsyncAction s = a.sibling;
            BinaryAsyncAction p = a.parent;
            a.sibling = null;
            a.parent = null;
            a.setDone();
            if (p == null || p.casStatus(0, 1))
                break;
            try {
                p.onFinish(a, s);
            } catch(Throwable rex) {
                p.doFinishExceptionally(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,
     * finishes 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 finishExceptionally(Throwable ex) {
        if (!(ex instanceof RuntimeException) && !(ex instanceof Error))
            throw new IllegalArgumentException(ex);
        doFinishExceptionally(ex);
    }

    /**
     * Internal version without argument screening
     */
    private void doFinishExceptionally(Throwable ex) {
        BinaryAsyncAction a = this;
        while (a.status != ForkJoinTask.HAS_EXCEPTION) {
            a.setDoneExceptionally(ex);
            BinaryAsyncAction s = a.sibling;
            if (s != null)
                s.cancel();
            if (!a.onException() || (a = a.parent) == null)
                break;
        }
    }

    /**
     * Returns this task's parent, or null if none or this task
     * is already finished.
     * @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 finished.
     * @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();
    }

    final boolean exec() {
        if (status >= 0) {
            try {
                compute();
            } catch(Throwable rex) {
                doFinishExceptionally(rex);
            }
        }
        return false;
    }
}
Revision:	1.4
Committed:	Tue Jan 6 14:34:58 2009 UTC (15 years, 5 months ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.3:	+0 -0 lines
State:	*FILE REMOVED*
Log Message:	Repackaging
#	Content
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	package jsr166y.forkjoin;
8
9	/**
10	* AsyncActions that are always linked in binary parent-child
11	* relationships. Compared to Recursive tasks, BinaryAsyncActions may
12	* have smaller stack space footprints and faster completion mechanics
13	* but higher per-task footprints. Compared to LinkedAsyncActions,
14	* BinaryAsyncActions are simpler to use and have less overhead in
15	* typical usages but are restricted to binary computation trees.
16	*
17	* <p> Upon construction, a BinaryAsyncAction does not bear any
18	* linkages. For non-root tasks, links must be established using
19	* method <tt>linkSubtasks</tt> before use.
20	*
21	* <p> <b>Sample Usage.</b> A version of Fibonacci:
22	* <pre>
23	* class Fib extends BinaryAsyncAction {
24	* final int n;
25	* int result;
26	* Fib(int n) { this.n = n; }
27	* protected void compute() {
28	* if (n > 1) {
29	* linkAndForkSubtasks(new Fib(n-1), new Fib(n-2));
30	* else {
31	* result = n; // fib(0)==0; fib(1)==1
32	* finish();
33	* }
34	* }
35	* protected void onFinish(BinaryAsyncAction x, BinaryAsyncAction y) {
36	* result = ((Fib)x).result + ((Fib)y).result;
37	* }
38	* }
39	* </pre>
40	* An alternative, and usually faster strategy is to instead use a
41	* loop to fork subtasks:
42	* <pre>
43	* protected void compute() {
44	* Fib f = this;
45	* while (f.n > 1) {
46	* Fib left = new Fib(f.n - 1);
47	* Fib right = new Fib(f.n - 2);
48	* f.linkSubtasks(left, right);
49	* right.fork(); // fork right
50	* f = left; // loop on left
51	* }
52	* f.result = f.n;
53	* f.finish();
54	* }
55	* }
56	* </pre>
57	*/
58	public abstract class BinaryAsyncAction extends AsyncAction {
59	/**
60	* Parent to propagate completion; nulled after completion to
61	* avoid retaining entire tree as garbage
62	*/
63	private BinaryAsyncAction parent;
64
65	/**
66	* Sibling to access on subtask joins, also nulled after completion.
67	*/
68	private BinaryAsyncAction sibling;
69
70	/*
71	* Note: we also piggyback one bit join count on
72	* ForkJoinTask.status field. The first arriving thread CAS's
73	* status from 0 to 1. The second ultimately sets to negative
74	* value to signify completion.
75	*/
76
77	/**
78	* Creates a new action. Unless this is a root task, you will need
79	* to link it using method <tt>linkSubtasks</tt> before forking as
80	* a subtask.
81	*/
82	protected BinaryAsyncAction() {
83	}
84
85	/**
86	* Establishes links for the given tasks to have the current task
87	* as parent, and each other as siblings.
88	* @param x one subtask
89	* @param y the other subtask
90	* @throws NullPointerException if either argument is null.
91	*/
92	public final void linkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {
93	x.parent = y.parent = this;
94	x.sibling = y;
95	y.sibling = x;
96	}
97
98	/**
99	* Overridable callback action triggered upon <tt>finish</tt> of
100	* subtasks. Upon invocation, both subtasks have completed.
101	* After return, this task <tt>isDone</tt> and is joinable by
102	* other tasks. The default version of this method does
103	* nothing. But it may may be overridden in subclasses to perform
104	* some action (for example a reduction) when this task is
105	* completes.
106	* @param x one subtask
107	* @param y the other subtask
108	*/
109	protected void onFinish(BinaryAsyncAction x, BinaryAsyncAction y) {
110	}
111
112	/**
113	* Overridable callback action triggered by
114	* <tt>finishExceptionally</tt>. Upon invocation, this task has
115	* aborted due to an exception (accessible via
116	* <tt>getException</tt>). If this method returns <tt>true</tt>,
117	* the exception propagates to the current task's
118	* parent. Otherwise, normal completion is propagated. The
119	* default version of this method does nothing and returns
120	* <tt>true</tt>.
121	* @return true if this task's exception should be propagated to
122	* this task's parent.
123	*/
124	protected boolean onException() {
125	return true;
126	}
127
128	/**
129	* Equivalent in effect to invoking <tt>linkSubtasks</tt> and then
130	* forking both tasks.
131	* @param x one subtask
132	* @param y the other subtask
133	*/
134	public void linkAndForkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {
135	linkSubtasks(x, y);
136	y.fork();
137	x.fork();
138	}
139
140	/**
141	* Completes this task, and if this task has a sibling that is
142	* also complete, invokes <tt>onFinish</tt> of parent task, and so
143	* on. If an exception is encountered, tasks instead
144	* <tt>finishExceptionally</tt>.
145	*/
146	public final void finish() {
147	// todo: Use removeIfNextLocalTask(s) without possibly blowing stack
148	BinaryAsyncAction a = this;
149	for (;;) {
150	BinaryAsyncAction s = a.sibling;
151	BinaryAsyncAction p = a.parent;
152	a.sibling = null;
153	a.parent = null;
154	a.setDone();
155	if (p == null \|\| p.casStatus(0, 1))
156	break;
157	try {
158	p.onFinish(a, s);
159	} catch(Throwable rex) {
160	p.doFinishExceptionally(rex);
161	return;
162	}
163	a = p;
164	}
165	}
166
167	/**
168	* Completes this task abnormally. Unless this task already
169	* cancelled or aborted, upon invocation, this method invokes
170	* <tt>onException</tt>, and then, depending on its return value,
171	* finishes parent (if one exists) exceptionally or normally. To
172	* avoid unbounded exception loops, this method aborts if an
173	* exception is encountered in any <tt>onException</tt>
174	* invocation.
175	* @param ex the exception to throw when joining this task
176	* @throws NullPointerException if ex is null
177	* @throws Throwable if any invocation of
178	* <tt>onException</tt> does so.
179	*/
180	public final void finishExceptionally(Throwable ex) {
181	if (!(ex instanceof RuntimeException) && !(ex instanceof Error))
182	throw new IllegalArgumentException(ex);
183	doFinishExceptionally(ex);
184	}
185
186	/**
187	* Internal version without argument screening
188	*/
189	private void doFinishExceptionally(Throwable ex) {
190	BinaryAsyncAction a = this;
191	while (a.status != ForkJoinTask.HAS_EXCEPTION) {
192	a.setDoneExceptionally(ex);
193	BinaryAsyncAction s = a.sibling;
194	if (s != null)
195	s.cancel();
196	if (!a.onException() \|\| (a = a.parent) == null)
197	break;
198	}
199	}
200
201	/**
202	* Returns this task's parent, or null if none or this task
203	* is already finished.
204	* @return this task's parent, or null if none.
205	*/
206	public final BinaryAsyncAction getParent() {
207	return parent;
208	}
209
210	/**
211	* Returns this task's sibling, or null if none or this task is
212	* already finished.
213	* @return this task's sibling, or null if none.
214	*/
215	public BinaryAsyncAction getSibling() {
216	return sibling;
217	}
218
219	/**
220	* Resets the internal bookkeeping state of this task, erasing
221	* parent and child linkages.
222	*/
223	public void reinitialize() {
224	parent = sibling = null;
225	super.reinitialize();
226	}
227
228	final boolean exec() {
229	if (status >= 0) {
230	try {
231	compute();
232	} catch(Throwable rex) {
233	doFinishExceptionally(rex);
234	}
235	}
236	return false;
237	}
238	}