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 stream.
33 *
34 * @param <P_IN> Type of elements input to the pipeline
35 * @param <P_OUT> Type of elements output from the pipeline
36 * @param <R> Type of intermediate result, may be different from operation result type
37 * @param <T> Type of child and sibling tasks
38 * @since 1.8
39 */
40 abstract class AbstractShortCircuitTask<P_IN, P_OUT, R, T extends AbstractShortCircuitTask<P_IN, P_OUT, R, T>>
41 extends AbstractTask<P_IN, P_OUT, R, T> {
42 /** The result for this computation; this is shared among all tasks and set exactly once */
43 protected final AtomicReference<R> sharedResult;
44
45 /**
46 * Indicates whether this task has been canceled. Tasks may cancel other tasks in the computation
47 * under various conditions, such as in a find-first operation, a task that finds a value will cancel
48 * all tasks that are later in the encounter order.
49 */
50 protected volatile boolean canceled;
51
52 /** Constructor for root nodes */
53 protected AbstractShortCircuitTask(PipelineHelper<P_IN, P_OUT> helper) {
54 super(helper);
55 sharedResult = new AtomicReference<>(null);
56 }
57
58 /** Constructor for non-root nodes */
59 protected AbstractShortCircuitTask(T parent, Spliterator<P_IN> spliterator) {
60 super(parent, spliterator);
61 sharedResult = parent.sharedResult;
62 }
63
64 /**
65 * Return the value indicating the computation completed with no task finding a short-circuitable result.
66 * For example, for a "find" operation, this might be null or an empty {@code Optional}.
67 */
68 protected abstract R getEmptyResult();
69
70 @Override
71 protected boolean canCompute() {
72 // Have we already found an answer?
73 if (sharedResult.get() != null) {
74 tryComplete();
75 return false;
76 } else if (taskCanceled()) {
77 setLocalResult(getEmptyResult());
78 tryComplete();
79 return false;
80 }
81 else {
82 return true;
83 }
84 }
85
86 /**
87 * Declare that a globally valid result has been found. If another task has not already found the answer,
88 * the result is installed in {@code sharedResult}. The {@code compute()} method will check {@code sharedResult}
89 * before proceeding with computation, so this causes the computation to terminate early.
90 */
91 protected void shortCircuit(R result) {
92 if (result != null)
93 sharedResult.compareAndSet(null, result);
94 }
95
96 /**
97 * Set a local result for this task. If this task is the root, set the shared result instead (if not already set).
98 */
99 @Override
100 protected void setLocalResult(R localResult) {
101 if (isRoot()) {
102 if (localResult != null)
103 sharedResult.compareAndSet(null, localResult);
104 }
105 else
106 super.setLocalResult(localResult);
107 }
108
109 /** Retrieve the local result for this task */
110 @Override
111 public R getRawResult() {
112 return getLocalResult();
113 }
114
115 /** Retrieve the local result for this task. If this task is the root, retrieves the shared result instead. */
116 @Override
117 public R getLocalResult() {
118 if (isRoot()) {
119 R answer = sharedResult.get();
120 return (answer == null) ? getEmptyResult() : answer;
121 }
122 else
123 return super.getLocalResult();
124 }
125
126 /** Set this node as canceled */
127 protected void cancel() {
128 canceled = true;
129 }
130
131 /**
132 * Query whether this task is canceled. A task is considered canceled if it or any of its parents
133 * have been canceled.
134 */
135 protected boolean taskCanceled() {
136 boolean cancel = canceled;
137 if (!cancel)
138 for (T parent = getParent(); !cancel && parent != null; parent = parent.getParent())
139 cancel = parent.canceled;
140 return cancel;
141 }
142
143 /**
144 * Cancel all tasks which succeed this one in the encounter order. This includes canceling all the current
145 * task's later siblings, as well as the later siblings of all its parents.
146 */
147 protected void cancelLaterNodes() {
148 T parent = getParent();
149 for (T sibling = this.nextSibling; sibling != null; sibling = sibling.nextSibling)
150 if (!sibling.canceled)
151 sibling.canceled = true;
152 // Go up the tree, cancel later siblings of all parents
153 if (parent != null)
154 parent.cancelLaterNodes();
155 }
156
157 /**
158 * Returns whether this node is a "leftmost" node -- whether the path from the root to this node involves
159 * only traversing leftmost child links. For a leaf node, this means it is the first leaf node in the
160 * encounter order.
161 */
162 protected boolean isLeftmostNode() {
163 T node = (T) this;
164 while (node != null) {
165 T parent = node.getParent();
166 if (parent != null && parent.children != node)
167 return false;
168 node = parent;
169 }
170 return true;
171 }
172 }