Debian Codegraph @

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