1 /*
2 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util.stream;
26
27 import java.util.Spliterator;
28 import java.util.concurrent.atomic.AtomicReference;
29
30 /**
31 * Abstract class for fork-join tasks used to implement short-circuiting
32 * stream ops, which can produce a result without processing all elements of the
33 * stream.
34 *
35 * @param <P_IN> Type of elements input to the pipeline
36 * @param <P_OUT> Type of elements output from the pipeline
37 * @param <R> Type of intermediate result, may be different from operation
38 * result type
39 * @param <T> Type of child and sibling tasks
40 * @since 1.8
41 */
42 abstract class AbstractShortCircuitTask<P_IN, P_OUT, R, T extends AbstractShortCircuitTask<P_IN, P_OUT, R, T>>
43 extends AbstractTask<P_IN, P_OUT, R, T> {
44 /**
45 * The result for this computation; this is shared among all tasks and set
46 * exactly once
47 */
48 protected final AtomicReference<R> sharedResult;
49
50 /**
51 * Indicates whether this task has been canceled. Tasks may cancel other
52 * tasks in the computation under various conditions, such as in a
53 * find-first operation, a task that finds a value will cancel all tasks
54 * that are later in the encounter order.
55 */
56 protected volatile boolean canceled;
57
58 /** Constructor for root nodes */
59 protected AbstractShortCircuitTask(PipelineHelper<P_IN, P_OUT> helper) {
60 super(helper);
61 sharedResult = new AtomicReference<>(null);
62 }
63
64 /** Constructor for non-root nodes */
65 protected AbstractShortCircuitTask(T parent, Spliterator<P_IN> spliterator) {
66 super(parent, spliterator);
67 sharedResult = parent.sharedResult;
68 }
69
70 /**
71 * Returns the value indicating the computation completed with no task
72 * finding a short-circuitable result. For example, for a "find" operation,
73 * this might be null or an empty {@code Optional}.
74 */
75 protected abstract R getEmptyResult();
76
77 @Override
78 protected boolean canCompute() {
79 // Have we already found an answer?
80 if (sharedResult.get() != null) {
81 tryComplete();
82 return false;
83 } else if (taskCanceled()) {
84 setLocalResult(getEmptyResult());
85 tryComplete();
86 return false;
87 }
88 else {
89 return true;
90 }
91 }
92
93 /**
94 * Declares that a globally valid result has been found. If another task has
95 * not already found the answer, the result is installed in
96 * {@code sharedResult}. The {@code compute()} method will check
97 * {@code sharedResult} before proceeding with computation, so this causes
98 * the computation to terminate early.
99 */
100 protected void shortCircuit(R result) {
101 if (result != null)
102 sharedResult.compareAndSet(null, result);
103 }
104
105 /**
106 * Sets a local result for this task. If this task is the root, set the
107 * shared result instead (if not already set).
108 */
109 @Override
110 protected void setLocalResult(R localResult) {
111 if (isRoot()) {
112 if (localResult != null)
113 sharedResult.compareAndSet(null, localResult);
114 }
115 else
116 super.setLocalResult(localResult);
117 }
118
119 /** Retrieves the local result for this task */
120 @Override
121 public R getRawResult() {
122 return getLocalResult();
123 }
124
125 /**
126 * Retrieves the local result for this task. If this task is the root,
127 * retrieves the shared result instead.
128 */
129 @Override
130 public R getLocalResult() {
131 if (isRoot()) {
132 R answer = sharedResult.get();
133 return (answer == null) ? getEmptyResult() : answer;
134 }
135 else
136 return super.getLocalResult();
137 }
138
139 /** Set this node as canceled */
140 protected void cancel() {
141 canceled = true;
142 }
143
144 /**
145 * Queries whether this task is canceled. A task is considered canceled if it
146 * or any of its parents have been canceled.
147 */
148 protected boolean taskCanceled() {
149 boolean cancel = canceled;
150 if (!cancel)
151 for (T parent = getParent(); !cancel && parent != null; parent = parent.getParent())
152 cancel = parent.canceled;
153 return cancel;
154 }
155
156 /**
157 * Cancels all tasks which succeed this one in the encounter order. This
158 * includes canceling all the current task's later siblings, as well as the
159 * later siblings of all its parents.
160 */
161 protected void cancelLaterNodes() {
162 T parent = getParent();
163 for (T sibling = this.nextSibling; sibling != null; sibling = sibling.nextSibling)
164 if (!sibling.canceled)
165 sibling.canceled = true;
166 // Go up the tree, cancel later siblings of all parents
167 if (parent != null)
168 parent.cancelLaterNodes();
169 }
170
171 /**
172 * Returns whether this node is a "leftmost" node -- whether the path from
173 * the root to this node involves only traversing leftmost child links. For
174 * a leaf node, this means it is the first leaf node in the encounter order.
175 */
176 protected boolean isLeftmostNode() {
177 T node = (T) this;
178 while (node != null) {
179 T parent = node.getParent();
180 if (parent != null && parent.children != node)
181 return false;
182 node = parent;
183 }
184 return true;
185 }
186 }