Debian Codegraph @

src/main/java/io/reactivex/rxjava3/internal/util/QueueDrainHelper.java

raw
1 /*
2 * Copyright (c) 2016-present, RxJava Contributors.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in
5 * compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License is
10 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See
11 * the License for the specific language governing permissions and limitations under the License.
12 */
13
14 package io.reactivex.rxjava3.internal.util;
15
16 import java.util.Queue;
17 import java.util.concurrent.atomic.AtomicLong;
18
19 import org.reactivestreams.*;
20
21 import io.reactivex.rxjava3.core.Observer;
22 import io.reactivex.rxjava3.disposables.Disposable;
23 import io.reactivex.rxjava3.exceptions.*;
24 import io.reactivex.rxjava3.functions.BooleanSupplier;
25 import io.reactivex.rxjava3.operators.*;
26
27 /**
28 * Utility class to help with the queue-drain serialization idiom.
29 */
30 public final class QueueDrainHelper {
31 /** Utility class. */
32 private QueueDrainHelper() {
33 throw new IllegalStateException("No instances!");
34 }
35
36 /**
37 * Drain the queue but give up with an error if there aren't enough requests.
38 * @param <T> the queue value type
39 * @param <U> the emission value type
40 * @param q the queue
41 * @param a the subscriber
42 * @param delayError true if errors should be delayed after all normal items
43 * @param dispose the disposable to call when termination happens and cleanup is necessary
44 * @param qd the QueueDrain instance that gives status information to the drain logic
45 */
46 public static <T, U> void drainMaxLoop(SimplePlainQueue<T> q, Subscriber<? super U> a, boolean delayError,
47 Disposable dispose, QueueDrain<T, U> qd) {
48 int missed = 1;
49
50 for (;;) {
51 for (;;) {
52 boolean d = qd.done();
53
54 T v = q.poll();
55
56 boolean empty = v == null;
57
58 if (checkTerminated(d, empty, a, delayError, q, qd)) {
59 if (dispose != null) {
60 dispose.dispose();
61 }
62 return;
63 }
64
65 if (empty) {
66 break;
67 }
68
69 long r = qd.requested();
70 if (r != 0L) {
71 if (qd.accept(a, v)) {
72 if (r != Long.MAX_VALUE) {
73 qd.produced(1);
74 }
75 }
76 } else {
77 q.clear();
78 if (dispose != null) {
79 dispose.dispose();
80 }
81 a.onError(new MissingBackpressureException("Could not emit value due to lack of requests."));
82 return;
83 }
84 }
85
86 missed = qd.leave(-missed);
87 if (missed == 0) {
88 break;
89 }
90 }
91 }
92
93 public static <T, U> boolean checkTerminated(boolean d, boolean empty,
94 Subscriber<?> s, boolean delayError, SimpleQueue<?> q, QueueDrain<T, U> qd) {
95 if (qd.cancelled()) {
96 q.clear();
97 return true;
98 }
99
100 if (d) {
101 if (delayError) {
102 if (empty) {
103 Throwable err = qd.error();
104 if (err != null) {
105 s.onError(err);
106 } else {
107 s.onComplete();
108 }
109 return true;
110 }
111 } else {
112 Throwable err = qd.error();
113 if (err != null) {
114 q.clear();
115 s.onError(err);
116 return true;
117 } else
118 if (empty) {
119 s.onComplete();
120 return true;
121 }
122 }
123 }
124
125 return false;
126 }
127
128 public static <T, U> void drainLoop(SimplePlainQueue<T> q, Observer<? super U> a, boolean delayError, Disposable dispose, ObservableQueueDrain<T, U> qd) {
129
130 int missed = 1;
131
132 for (;;) {
133 if (checkTerminated(qd.done(), q.isEmpty(), a, delayError, q, dispose, qd)) {
134 return;
135 }
136
137 for (;;) {
138 boolean d = qd.done();
139 T v = q.poll();
140 boolean empty = v == null;
141
142 if (checkTerminated(d, empty, a, delayError, q, dispose, qd)) {
143 return;
144 }
145
146 if (empty) {
147 break;
148 }
149
150 qd.accept(a, v);
151 }
152
153 missed = qd.leave(-missed);
154 if (missed == 0) {
155 break;
156 }
157 }
158 }
159
160 public static <T, U> boolean checkTerminated(boolean d, boolean empty,
161 Observer<?> observer, boolean delayError, SimpleQueue<?> q, Disposable disposable, ObservableQueueDrain<T, U> qd) {
162 if (qd.cancelled()) {
163 q.clear();
164 disposable.dispose();
165 return true;
166 }
167
168 if (d) {
169 if (delayError) {
170 if (empty) {
171 if (disposable != null) {
172 disposable.dispose();
173 }
174 Throwable err = qd.error();
175 if (err != null) {
176 observer.onError(err);
177 } else {
178 observer.onComplete();
179 }
180 return true;
181 }
182 } else {
183 Throwable err = qd.error();
184 if (err != null) {
185 q.clear();
186 if (disposable != null) {
187 disposable.dispose();
188 }
189 observer.onError(err);
190 return true;
191 } else
192 if (empty) {
193 if (disposable != null) {
194 disposable.dispose();
195 }
196 observer.onComplete();
197 return true;
198 }
199 }
200 }
201
202 return false;
203 }
204
205 /**
206 * Creates a queue: spsc-array if capacityHint is positive and
207 * spsc-linked-array if capacityHint is negative; in both cases, the
208 * capacity is the absolute value of prefetch.
209 * @param <T> the value type of the queue
210 * @param capacityHint the capacity hint, negative value will create an array-based SPSC queue
211 * @return the queue instance
212 */
213 public static <T> SimpleQueue<T> createQueue(int capacityHint) {
214 if (capacityHint < 0) {
215 return new SpscLinkedArrayQueue<>(-capacityHint);
216 }
217 return new SpscArrayQueue<>(capacityHint);
218 }
219
220 /**
221 * Requests {@link Long#MAX_VALUE} if prefetch is negative or the exact
222 * amount if prefetch is positive.
223 * @param s the Subscription to request from
224 * @param prefetch the prefetch value
225 */
226 public static void request(Subscription s, int prefetch) {
227 s.request(prefetch < 0 ? Long.MAX_VALUE : prefetch);
228 }
229
230 static final long COMPLETED_MASK = 0x8000000000000000L;
231 static final long REQUESTED_MASK = 0x7FFFFFFFFFFFFFFFL;
232
233 /**
234 * Accumulates requests (not validated) and handles the completed mode draining of the queue based on the requests.
235 *
236 * <p>
237 * Post-completion backpressure handles the case when a source produces values based on
238 * requests when it is active but more values are available even after its completion.
239 * In this case, the onComplete() can't just emit the contents of the queue but has to
240 * coordinate with the requested amounts. This requires two distinct modes: active and
241 * completed. In active mode, requests flow through and the queue is not accessed but
242 * in completed mode, requests no-longer reach the upstream but help in draining the queue.
243 *
244 * @param <T> the value type emitted
245 * @param n the request amount, positive (not validated)
246 * @param actual the target Subscriber to send events to
247 * @param queue the queue to drain if in the post-complete state
248 * @param state holds the request amount and the post-completed flag
249 * @param isCancelled a supplier that returns true if the drain has been cancelled
250 * @return true if the state indicates a completion state.
251 */
252 public static <T> boolean postCompleteRequest(long n,
253 Subscriber<? super T> actual,
254 Queue<T> queue,
255 AtomicLong state,
256 BooleanSupplier isCancelled) {
257 for (; ; ) {
258 long r = state.get();
259
260 // extract the current request amount
261 long r0 = r & REQUESTED_MASK;
262
263 // preserve COMPLETED_MASK and calculate new requested amount
264 long u = (r & COMPLETED_MASK) | BackpressureHelper.addCap(r0, n);
265
266 if (state.compareAndSet(r, u)) {
267 // (complete, 0) -> (complete, n) transition then replay
268 if (r == COMPLETED_MASK) {
269
270 postCompleteDrain(n | COMPLETED_MASK, actual, queue, state, isCancelled);
271
272 return true;
273 }
274 // (active, r) -> (active, r + n) transition then continue with requesting from upstream
275 return false;
276 }
277 }
278
279 }
280
281 static boolean isCancelled(BooleanSupplier cancelled) {
282 try {
283 return cancelled.getAsBoolean();
284 } catch (Throwable ex) {
285 Exceptions.throwIfFatal(ex);
286 return true;
287 }
288 }
289
290 /**
291 * Drains the queue based on the outstanding requests in post-completed mode (only!).
292 *
293 * @param <T> the value type
294 * @param n the current request amount
295 * @param actual the target Subscriber to send events to
296 * @param queue the queue to drain if in the post-complete state
297 * @param state holds the request amount and the post-completed flag
298 * @param isCancelled a supplier that returns true if the drain has been cancelled
299 * @return true if the queue was completely drained or the drain process was cancelled
300 */
301 static <T> boolean postCompleteDrain(long n,
302 Subscriber<? super T> actual,
303 Queue<T> queue,
304 AtomicLong state,
305 BooleanSupplier isCancelled) {
306
307 // TODO enable fast-path
308 // if (n == -1 || n == Long.MAX_VALUE) {
309 // for (;;) {
310 // if (isCancelled.getAsBoolean()) {
311 // break;
312 // }
313 //
314 // T v = queue.poll();
315 //
316 // if (v == null) {
317 // actual.onComplete();
318 // break;
319 // }
320 //
321 // actual.onNext(v);
322 // }
323 //
324 // return true;
325 // }
326
327 long e = n & COMPLETED_MASK;
328
329 for (; ; ) {
330
331 while (e != n) {
332 if (isCancelled(isCancelled)) {
333 return true;
334 }
335
336 T t = queue.poll();
337
338 if (t == null) {
339 actual.onComplete();
340 return true;
341 }
342
343 actual.onNext(t);
344 e++;
345 }
346
347 if (isCancelled(isCancelled)) {
348 return true;
349 }
350
351 if (queue.isEmpty()) {
352 actual.onComplete();
353 return true;
354 }
355
356 n = state.get();
357
358 if (n == e) {
359
360 n = state.addAndGet(-(e & REQUESTED_MASK));
361
362 if ((n & REQUESTED_MASK) == 0L) {
363 return false;
364 }
365
366 e = n & COMPLETED_MASK;
367 }
368 }
369
370 }
371
372 /**
373 * Signals the completion of the main sequence and switches to post-completion replay mode.
374 *
375 * <p>
376 * Don't modify the queue after calling this method!
377 *
378 * <p>
379 * Post-completion backpressure handles the case when a source produces values based on
380 * requests when it is active but more values are available even after its completion.
381 * In this case, the onComplete() can't just emit the contents of the queue but has to
382 * coordinate with the requested amounts. This requires two distinct modes: active and
383 * completed. In active mode, requests flow through and the queue is not accessed but
384 * in completed mode, requests no-longer reach the upstream but help in draining the queue.
385 * <p>
386 * The algorithm utilizes the most significant bit (bit 63) of a long value (AtomicLong) since
387 * request amount only goes up to {@link Long#MAX_VALUE} (bits 0-62) and negative values aren't
388 * allowed.
389 *
390 * @param <T> the value type emitted
391 * @param actual the target Subscriber to send events to
392 * @param queue the queue to drain if in the post-complete state
393 * @param state holds the request amount and the post-completed flag
394 * @param isCancelled a supplier that returns true if the drain has been cancelled
395 */
396 public static <T> void postComplete(Subscriber<? super T> actual,
397 Queue<T> queue,
398 AtomicLong state,
399 BooleanSupplier isCancelled) {
400
401 if (queue.isEmpty()) {
402 actual.onComplete();
403 return;
404 }
405
406 if (postCompleteDrain(state.get(), actual, queue, state, isCancelled)) {
407 return;
408 }
409
410 for (; ; ) {
411 long r = state.get();
412
413 if ((r & COMPLETED_MASK) != 0L) {
414 return;
415 }
416
417 long u = r | COMPLETED_MASK;
418 // (active, r) -> (complete, r) transition
419 if (state.compareAndSet(r, u)) {
420 // if the requested amount was non-zero, drain the queue
421 if (r != 0L) {
422 postCompleteDrain(u, actual, queue, state, isCancelled);
423 }
424
425 return;
426 }
427 }
428
429 }
430 }