author | mduigou |
Tue, 16 Apr 2013 22:50:48 -0400 | |
changeset 17163 | 6a5e9b4f27d2 |
child 18572 | 53b8b8c30086 |
permissions | -rw-r--r-- |
17163
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
1 |
/* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
2 |
* Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
4 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
5 |
* This code is free software; you can redistribute it and/or modify it |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
7 |
* published by the Free Software Foundation. Oracle designates this |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
8 |
* particular file as subject to the "Classpath" exception as provided |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
9 |
* by Oracle in the LICENSE file that accompanied this code. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
10 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
15 |
* accompanied this code). |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
16 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
17 |
* You should have received a copy of the GNU General Public License version |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
20 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
22 |
* or visit www.oracle.com if you need additional information or have any |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
23 |
* questions. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
24 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
25 |
package java.util.stream; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
26 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
27 |
import java.util.Spliterator; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
28 |
import java.util.concurrent.CountedCompleter; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
29 |
import java.util.concurrent.ForkJoinPool; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
30 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
31 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
32 |
* Abstract base class for most fork-join tasks used to implement stream ops. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
33 |
* Manages splitting logic, tracking of child tasks, and intermediate results. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
34 |
* Each task is associated with a {@link Spliterator} that describes the portion |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
35 |
* of the input associated with the subtree rooted at this task. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
36 |
* Tasks may be leaf nodes (which will traverse the elements of |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
37 |
* the {@code Spliterator}) or internal nodes (which split the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
38 |
* {@code Spliterator} into multiple child tasks). |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
39 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
40 |
* @implNote |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
41 |
* <p>This class is based on {@link CountedCompleter}, a form of fork-join task |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
42 |
* where each task has a semaphore-like count of uncompleted children, and the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
43 |
* task is implicitly completed and notified when its last child completes. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
44 |
* Internal node tasks will likely override the {@code onCompletion} method from |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
45 |
* {@code CountedCompleter} to merge the results from child tasks into the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
46 |
* current task's result. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
47 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
48 |
* <p>Splitting and setting up the child task links is done by {@code compute()} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
49 |
* for internal nodes. At {@code compute()} time for leaf nodes, it is |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
50 |
* guaranteed that the parent's child-related fields (including sibling links |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
51 |
* for the parent's children) will be set up for all children. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
52 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
53 |
* <p>For example, a task that performs a reduce would override {@code doLeaf()} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
54 |
* to perform a reduction on that leaf node's chunk using the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
55 |
* {@code Spliterator}, and override {@code onCompletion()} to merge the results |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
56 |
* of the child tasks for internal nodes: |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
57 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
58 |
* <pre>{@code |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
59 |
* protected S doLeaf() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
60 |
* spliterator.forEach(...); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
61 |
* return localReductionResult; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
62 |
* } |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
63 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
64 |
* public void onCompletion(CountedCompleter caller) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
65 |
* if (!isLeaf()) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
66 |
* ReduceTask<P_IN, P_OUT, T, R> child = children; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
67 |
* R result = child.getLocalResult(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
68 |
* child = child.nextSibling; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
69 |
* for (; child != null; child = child.nextSibling) |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
70 |
* result = combine(result, child.getLocalResult()); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
71 |
* setLocalResult(result); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
72 |
* } |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
73 |
* } |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
74 |
* }</pre> |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
75 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
76 |
* @param <P_IN> Type of elements input to the pipeline |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
77 |
* @param <P_OUT> Type of elements output from the pipeline |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
78 |
* @param <R> Type of intermediate result, which may be different from operation |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
79 |
* result type |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
80 |
* @param <K> Type of parent, child and sibling tasks |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
81 |
* @since 1.8 |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
82 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
83 |
abstract class AbstractTask<P_IN, P_OUT, R, |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
84 |
K extends AbstractTask<P_IN, P_OUT, R, K>> |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
85 |
extends CountedCompleter<R> { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
86 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
87 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
88 |
* Default target factor of leaf tasks for parallel decomposition. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
89 |
* To allow load balancing, we over-partition, currently to approximately |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
90 |
* four tasks per processor, which enables others to help out |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
91 |
* if leaf tasks are uneven or some processors are otherwise busy. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
92 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
93 |
static final int LEAF_TARGET = ForkJoinPool.getCommonPoolParallelism() << 2; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
94 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
95 |
/** The pipeline helper, common to all tasks in a computation */ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
96 |
protected final PipelineHelper<P_OUT> helper; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
97 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
98 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
99 |
* The spliterator for the portion of the input associated with the subtree |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
100 |
* rooted at this task |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
101 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
102 |
protected Spliterator<P_IN> spliterator; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
103 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
104 |
/** Target leaf size, common to all tasks in a computation */ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
105 |
protected final long targetSize; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
106 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
107 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
108 |
* The left child. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
109 |
* null if no children |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
110 |
* if non-null rightChild is non-null |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
111 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
112 |
protected K leftChild; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
113 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
114 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
115 |
* The right child. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
116 |
* null if no children |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
117 |
* if non-null leftChild is non-null |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
118 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
119 |
protected K rightChild; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
120 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
121 |
/** The result of this node, if completed */ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
122 |
private R localResult; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
123 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
124 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
125 |
* Constructor for root nodes. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
126 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
127 |
* @param helper The {@code PipelineHelper} describing the stream pipeline |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
128 |
* up to this operation |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
129 |
* @param spliterator The {@code Spliterator} describing the source for this |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
130 |
* pipeline |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
131 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
132 |
protected AbstractTask(PipelineHelper<P_OUT> helper, |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
133 |
Spliterator<P_IN> spliterator) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
134 |
super(null); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
135 |
this.helper = helper; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
136 |
this.spliterator = spliterator; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
137 |
this.targetSize = suggestTargetSize(spliterator.estimateSize()); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
138 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
139 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
140 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
141 |
* Constructor for non-root nodes. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
142 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
143 |
* @param parent this node's parent task |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
144 |
* @param spliterator {@code Spliterator} describing the subtree rooted at |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
145 |
* this node, obtained by splitting the parent {@code Spliterator} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
146 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
147 |
protected AbstractTask(K parent, |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
148 |
Spliterator<P_IN> spliterator) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
149 |
super(parent); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
150 |
this.spliterator = spliterator; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
151 |
this.helper = parent.helper; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
152 |
this.targetSize = parent.targetSize; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
153 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
154 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
155 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
156 |
* Constructs a new node of type T whose parent is the receiver; must call |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
157 |
* the AbstractTask(T, Spliterator) constructor with the receiver and the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
158 |
* provided Spliterator. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
159 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
160 |
* @param spliterator {@code Spliterator} describing the subtree rooted at |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
161 |
* this node, obtained by splitting the parent {@code Spliterator} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
162 |
* @return newly constructed child node |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
163 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
164 |
protected abstract K makeChild(Spliterator<P_IN> spliterator); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
165 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
166 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
167 |
* Computes the result associated with a leaf node. Will be called by |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
168 |
* {@code compute()} and the result passed to @{code setLocalResult()} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
169 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
170 |
* @return the computed result of a leaf node |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
171 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
172 |
protected abstract R doLeaf(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
173 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
174 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
175 |
* Returns a suggested target leaf size based on the initial size estimate. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
176 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
177 |
* @return suggested target leaf size |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
178 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
179 |
public static long suggestTargetSize(long sizeEstimate) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
180 |
long est = sizeEstimate / LEAF_TARGET; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
181 |
return est > 0L ? est : 1L; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
182 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
183 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
184 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
185 |
* Returns a suggestion whether it is advisable to split the provided |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
186 |
* spliterator based on target size and other considerations, such as pool |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
187 |
* state. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
188 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
189 |
* @return {@code true} if a split is advised otherwise {@code false} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
190 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
191 |
public static boolean suggestSplit(Spliterator spliterator, |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
192 |
long targetSize) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
193 |
long remaining = spliterator.estimateSize(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
194 |
return (remaining > targetSize); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
195 |
// @@@ May additionally want to fold in pool characteristics such as surplus task count |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
196 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
197 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
198 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
199 |
* Returns a suggestion whether it is adviseable to split this task based on |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
200 |
* target size and other considerations. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
201 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
202 |
* @return {@code true} if a split is advised otherwise {@code false} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
203 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
204 |
public boolean suggestSplit() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
205 |
return suggestSplit(spliterator, targetSize); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
206 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
207 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
208 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
209 |
* Returns the local result, if any. Subclasses should use |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
210 |
* {@link #setLocalResult(Object)} and {@link #getLocalResult()} to manage |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
211 |
* results. This returns the local result so that calls from within the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
212 |
* fork-join framework will return the correct result. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
213 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
214 |
* @return local result for this node previously stored with |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
215 |
* {@link #setLocalResult} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
216 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
217 |
@Override |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
218 |
public R getRawResult() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
219 |
return localResult; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
220 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
221 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
222 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
223 |
* Does nothing; instead, subclasses should use |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
224 |
* {@link #setLocalResult(Object)}} to manage results. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
225 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
226 |
* @param result must be null, or an exception is thrown (this is a safety |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
227 |
* tripwire to detect when {@code setRawResult()} is being used |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
228 |
* instead of {@code setLocalResult()} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
229 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
230 |
@Override |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
231 |
protected void setRawResult(R result) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
232 |
if (result != null) |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
233 |
throw new IllegalStateException(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
234 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
235 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
236 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
237 |
* Retrieves a result previously stored with {@link #setLocalResult} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
238 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
239 |
* @return local result for this node previously stored with |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
240 |
* {@link #setLocalResult} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
241 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
242 |
protected R getLocalResult() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
243 |
return localResult; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
244 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
245 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
246 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
247 |
* Associates the result with the task, can be retrieved with |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
248 |
* {@link #getLocalResult} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
249 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
250 |
* @param localResult local result for this node |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
251 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
252 |
protected void setLocalResult(R localResult) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
253 |
this.localResult = localResult; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
254 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
255 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
256 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
257 |
* Indicates whether this task is a leaf node. (Only valid after |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
258 |
* {@link #compute} has been called on this node). If the node is not a |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
259 |
* leaf node, then children will be non-null and numChildren will be |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
260 |
* positive. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
261 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
262 |
* @return {@code true} if this task is a leaf node |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
263 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
264 |
protected boolean isLeaf() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
265 |
return leftChild == null; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
266 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
267 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
268 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
269 |
* Indicates whether this task is the root node |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
270 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
271 |
* @return {@code true} if this task is the root node. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
272 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
273 |
protected boolean isRoot() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
274 |
return getParent() == null; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
275 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
276 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
277 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
278 |
* Returns the parent of this task, or null if this task is the root |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
279 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
280 |
* @return the parent of this task, or null if this task is the root |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
281 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
282 |
@SuppressWarnings("unchecked") |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
283 |
protected K getParent() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
284 |
return (K) getCompleter(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
285 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
286 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
287 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
288 |
* Decides whether or not to split a task further or compute it directly. If |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
289 |
* computing directly, call {@code doLeaf} and pass the result to |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
290 |
* {@code setRawResult}. If splitting, set up the child-related fields, |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
291 |
* create the child tasks, fork the leftmost (prefix) child tasks, and |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
292 |
* compute the rightmost (remaining) child tasks. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
293 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
294 |
* <p> |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
295 |
* Computing will continue for rightmost tasks while a task can be computed |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
296 |
* as determined by {@link #canCompute()} and that task should and can be |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
297 |
* split into left and right tasks. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
298 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
299 |
* <p> |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
300 |
* The rightmost tasks are computed in a loop rather than recursively to |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
301 |
* avoid potential stack overflows when computing with a right-balanced |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
302 |
* tree, such as that produced when splitting with a {@link Spliterator} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
303 |
* created from an {@link java.util.Iterator}. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
304 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
305 |
@Override |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
306 |
public final void compute() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
307 |
@SuppressWarnings("unchecked") |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
308 |
K task = (K) this; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
309 |
while (task.canCompute()) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
310 |
Spliterator<P_IN> split; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
311 |
if (!task.suggestSplit() || (split = task.spliterator.trySplit()) == null) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
312 |
task.setLocalResult(task.doLeaf()); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
313 |
task.tryComplete(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
314 |
return; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
315 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
316 |
else { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
317 |
K l = task.leftChild = task.makeChild(split); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
318 |
K r = task.rightChild = task.makeChild(task.spliterator); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
319 |
task.setPendingCount(1); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
320 |
l.fork(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
321 |
task = r; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
322 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
323 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
324 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
325 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
326 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
327 |
* {@inheritDoc} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
328 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
329 |
* @implNote |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
330 |
* Clears spliterator and children fields. Overriders MUST call |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
331 |
* {@code super.onCompletion} as the last thing they do if they want these |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
332 |
* cleared. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
333 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
334 |
@Override |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
335 |
public void onCompletion(CountedCompleter<?> caller) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
336 |
spliterator = null; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
337 |
leftChild = rightChild = null; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
338 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
339 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
340 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
341 |
* Determines if the task can be computed. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
342 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
343 |
* @implSpec The default always returns true |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
344 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
345 |
* @return {@code true} if this task can be computed to either calculate the |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
346 |
* leaf via {@link #doLeaf()} or split, otherwise false if this task |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
347 |
* cannot be computed, for example if this task has been canceled |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
348 |
* and/or a result for the computation has been found by another |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
349 |
* task. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
350 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
351 |
protected boolean canCompute() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
352 |
return true; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
353 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
354 |
|
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
355 |
/** |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
356 |
* Returns whether this node is a "leftmost" node -- whether the path from |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
357 |
* the root to this node involves only traversing leftmost child links. For |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
358 |
* a leaf node, this means it is the first leaf node in the encounter order. |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
359 |
* |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
360 |
* @return {@code true} if this node is a "leftmost" node |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
361 |
*/ |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
362 |
protected boolean isLeftmostNode() { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
363 |
@SuppressWarnings("unchecked") |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
364 |
K node = (K) this; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
365 |
while (node != null) { |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
366 |
K parent = node.getParent(); |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
367 |
if (parent != null && parent.leftChild != node) |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
368 |
return false; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
369 |
node = parent; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
370 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
371 |
return true; |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
372 |
} |
6a5e9b4f27d2
8008670: Initial java.util.stream putback -- internal API classes
mduigou
parents:
diff
changeset
|
373 |
} |