Debian Codegraph @

src/main/java/io/reactivex/rxjava3/internal/operators/flowable/FlowableCache.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.operators.flowable;
15
16 import java.util.concurrent.atomic.*;
17
18 import org.reactivestreams.*;
19
20 import io.reactivex.rxjava3.core.*;
21 import io.reactivex.rxjava3.internal.subscriptions.SubscriptionHelper;
22 import io.reactivex.rxjava3.internal.util.BackpressureHelper;
23 import io.reactivex.rxjava3.plugins.RxJavaPlugins;
24
25 /**
26 * An observable which auto-connects to another observable, caches the elements
27 * from that observable but allows terminating the connection and completing the cache.
28 *
29 * @param <T> the source element type
30 */
31 public final class FlowableCache<T> extends AbstractFlowableWithUpstream<T, T>
32 implements FlowableSubscriber<T> {
33
34 /**
35 * The subscription to the source should happen at most once.
36 */
37 final AtomicBoolean once;
38
39 /**
40 * The number of items per cached nodes.
41 */
42 final int capacityHint;
43
44 /**
45 * The current known array of subscriber state to notify.
46 */
47 final AtomicReference<CacheSubscription<T>[]> subscribers;
48
49 /**
50 * A shared instance of an empty array of subscribers to avoid creating
51 * a new empty array when all subscribers cancel.
52 */
53 @SuppressWarnings("rawtypes")
54 static final CacheSubscription[] EMPTY = new CacheSubscription[0];
55 /**
56 * A shared instance indicating the source has no more events and there
57 * is no need to remember subscribers anymore.
58 */
59 @SuppressWarnings("rawtypes")
60 static final CacheSubscription[] TERMINATED = new CacheSubscription[0];
61
62 /**
63 * The total number of elements in the list available for reads.
64 */
65 volatile long size;
66
67 /**
68 * The starting point of the cached items.
69 */
70 final Node<T> head;
71
72 /**
73 * The current tail of the linked structure holding the items.
74 */
75 Node<T> tail;
76
77 /**
78 * How many items have been put into the tail node so far.
79 */
80 int tailOffset;
81
82 /**
83 * If {@link #subscribers} is {@link #TERMINATED}, this holds the terminal error if not null.
84 */
85 Throwable error;
86
87 /**
88 * True if the source has terminated.
89 */
90 volatile boolean done;
91
92 /**
93 * Constructs an empty, non-connected cache.
94 * @param source the source to subscribe to for the first incoming subscriber
95 * @param capacityHint the number of items expected (reduce allocation frequency)
96 */
97 @SuppressWarnings("unchecked")
98 public FlowableCache(Flowable<T> source, int capacityHint) {
99 super(source);
100 this.capacityHint = capacityHint;
101 this.once = new AtomicBoolean();
102 Node<T> n = new Node<>(capacityHint);
103 this.head = n;
104 this.tail = n;
105 this.subscribers = new AtomicReference<>(EMPTY);
106 }
107
108 @Override
109 protected void subscribeActual(Subscriber<? super T> t) {
110 CacheSubscription<T> consumer = new CacheSubscription<>(t, this);
111 t.onSubscribe(consumer);
112 add(consumer);
113
114 if (!once.get() && once.compareAndSet(false, true)) {
115 source.subscribe(this);
116 } else {
117 replay(consumer);
118 }
119 }
120
121 /**
122 * Check if this cached observable is connected to its source.
123 * @return true if already connected
124 */
125 /* public */boolean isConnected() {
126 return once.get();
127 }
128
129 /**
130 * Returns true if there are observers subscribed to this observable.
131 * @return true if the cache has Subscribers
132 */
133 /* public */ boolean hasSubscribers() {
134 return subscribers.get().length != 0;
135 }
136
137 /**
138 * Returns the number of events currently cached.
139 * @return the number of currently cached event count
140 */
141 /* public */ long cachedEventCount() {
142 return size;
143 }
144
145 /**
146 * Atomically adds the consumer to the {@link #subscribers} copy-on-write array
147 * if the source has not yet terminated.
148 * @param consumer the consumer to add
149 */
150 void add(CacheSubscription<T> consumer) {
151 for (;;) {
152 CacheSubscription<T>[] current = subscribers.get();
153 if (current == TERMINATED) {
154 return;
155 }
156 int n = current.length;
157
158 @SuppressWarnings("unchecked")
159 CacheSubscription<T>[] next = new CacheSubscription[n + 1];
160 System.arraycopy(current, 0, next, 0, n);
161 next[n] = consumer;
162
163 if (subscribers.compareAndSet(current, next)) {
164 return;
165 }
166 }
167 }
168
169 /**
170 * Atomically removes the consumer from the {@link #subscribers} copy-on-write array.
171 * @param consumer the consumer to remove
172 */
173 @SuppressWarnings("unchecked")
174 void remove(CacheSubscription<T> consumer) {
175 for (;;) {
176 CacheSubscription<T>[] current = subscribers.get();
177 int n = current.length;
178 if (n == 0) {
179 return;
180 }
181
182 int j = -1;
183 for (int i = 0; i < n; i++) {
184 if (current[i] == consumer) {
185 j = i;
186 break;
187 }
188 }
189
190 if (j < 0) {
191 return;
192 }
193 CacheSubscription<T>[] next;
194
195 if (n == 1) {
196 next = EMPTY;
197 } else {
198 next = new CacheSubscription[n - 1];
199 System.arraycopy(current, 0, next, 0, j);
200 System.arraycopy(current, j + 1, next, j, n - j - 1);
201 }
202
203 if (subscribers.compareAndSet(current, next)) {
204 return;
205 }
206 }
207 }
208
209 /**
210 * Replays the contents of this cache to the given consumer based on its
211 * current state and number of items requested by it.
212 * @param consumer the consumer to continue replaying items to
213 */
214 void replay(CacheSubscription<T> consumer) {
215 // make sure there is only one replay going on at a time
216 if (consumer.getAndIncrement() != 0) {
217 return;
218 }
219
220 // see if there were more replay request in the meantime
221 int missed = 1;
222 // read out state into locals upfront to avoid being re-read due to volatile reads
223 long index = consumer.index;
224 int offset = consumer.offset;
225 Node<T> node = consumer.node;
226 AtomicLong requested = consumer.requested;
227 Subscriber<? super T> downstream = consumer.downstream;
228 int capacity = capacityHint;
229
230 for (;;) {
231 // first see if the source has terminated, read order matters!
232 boolean sourceDone = done;
233 // and if the number of items is the same as this consumer has received
234 boolean empty = size == index;
235
236 // if the source is done and we have all items so far, terminate the consumer
237 if (sourceDone && empty) {
238 // release the node object to avoid leaks through retained consumers
239 consumer.node = null;
240 // if error is not null then the source failed
241 Throwable ex = error;
242 if (ex != null) {
243 downstream.onError(ex);
244 } else {
245 downstream.onComplete();
246 }
247 return;
248 }
249
250 // there are still items not sent to the consumer
251 if (!empty) {
252 // see how many items the consumer has requested in total so far
253 long consumerRequested = requested.get();
254 // MIN_VALUE indicates a cancelled consumer, we stop replaying
255 if (consumerRequested == Long.MIN_VALUE) {
256 // release the node object to avoid leaks through retained consumers
257 consumer.node = null;
258 return;
259 }
260 // if the consumer has requested more and there is more, we will emit an item
261 if (consumerRequested != index) {
262
263 // if the offset in the current node has reached the node capacity
264 if (offset == capacity) {
265 // switch to the subsequent node
266 node = node.next;
267 // reset the in-node offset
268 offset = 0;
269 }
270
271 // emit the cached item
272 downstream.onNext(node.values[offset]);
273
274 // move the node offset forward
275 offset++;
276 // move the total consumed item count forward
277 index++;
278
279 // retry for the next item/terminal event if any
280 continue;
281 }
282 }
283
284 // commit the changed references back
285 consumer.index = index;
286 consumer.offset = offset;
287 consumer.node = node;
288 // release the changes and see if there were more replay request in the meantime
289 missed = consumer.addAndGet(-missed);
290 if (missed == 0) {
291 break;
292 }
293 }
294 }
295
296 @Override
297 public void onSubscribe(Subscription s) {
298 s.request(Long.MAX_VALUE);
299 }
300
301 @Override
302 public void onNext(T t) {
303 int tailOffset = this.tailOffset;
304 // if the current tail node is full, create a fresh node
305 if (tailOffset == capacityHint) {
306 Node<T> n = new Node<>(tailOffset);
307 n.values[0] = t;
308 this.tailOffset = 1;
309 tail.next = n;
310 tail = n;
311 } else {
312 tail.values[tailOffset] = t;
313 this.tailOffset = tailOffset + 1;
314 }
315 size++;
316 for (CacheSubscription<T> consumer : subscribers.get()) {
317 replay(consumer);
318 }
319 }
320
321 @SuppressWarnings("unchecked")
322 @Override
323 public void onError(Throwable t) {
324 if (done) {
325 RxJavaPlugins.onError(t);
326 return;
327 }
328 error = t;
329 done = true;
330 for (CacheSubscription<T> consumer : subscribers.getAndSet(TERMINATED)) {
331 replay(consumer);
332 }
333 }
334
335 @SuppressWarnings("unchecked")
336 @Override
337 public void onComplete() {
338 done = true;
339 for (CacheSubscription<T> consumer : subscribers.getAndSet(TERMINATED)) {
340 replay(consumer);
341 }
342 }
343
344 /**
345 * Hosts the downstream consumer and its current requested and replay states.
346 * {@code this} holds the work-in-progress counter for the serialized replay.
347 * @param <T> the value type
348 */
349 static final class CacheSubscription<T> extends AtomicInteger
350 implements Subscription {
351
352 private static final long serialVersionUID = 6770240836423125754L;
353
354 final Subscriber<? super T> downstream;
355
356 final FlowableCache<T> parent;
357
358 final AtomicLong requested;
359
360 Node<T> node;
361
362 int offset;
363
364 long index;
365
366 /**
367 * Constructs a new instance with the actual downstream consumer and
368 * the parent cache object.
369 * @param downstream the actual consumer
370 * @param parent the parent that holds onto the cached items
371 */
372 CacheSubscription(Subscriber<? super T> downstream, FlowableCache<T> parent) {
373 this.downstream = downstream;
374 this.parent = parent;
375 this.node = parent.head;
376 this.requested = new AtomicLong();
377 }
378
379 @Override
380 public void request(long n) {
381 if (SubscriptionHelper.validate(n)) {
382 BackpressureHelper.addCancel(requested, n);
383 parent.replay(this);
384 }
385 }
386
387 @Override
388 public void cancel() {
389 if (requested.getAndSet(Long.MIN_VALUE) != Long.MIN_VALUE) {
390 parent.remove(this);
391 }
392 }
393 }
394
395 /**
396 * Represents a segment of the cached item list as
397 * part of a linked-node-list structure.
398 * @param <T> the element type
399 */
400 static final class Node<T> {
401
402 /**
403 * The array of values held by this node.
404 */
405 final T[] values;
406
407 /**
408 * The next node if not null.
409 */
410 volatile Node<T> next;
411
412 @SuppressWarnings("unchecked")
413 Node(int capacityHint) {
414 this.values = (T[])new Object[capacityHint];
415 }
416 }
417 }