Debian Codegraph @

src/main/java/io/reactivex/rxjava3/internal/operators/flowable/FlowableGroupBy.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.*;
17 import java.util.concurrent.*;
18 import java.util.concurrent.atomic.*;
19
20 import org.reactivestreams.*;
21
22 import io.reactivex.rxjava3.annotations.Nullable;
23 import io.reactivex.rxjava3.core.*;
24 import io.reactivex.rxjava3.exceptions.*;
25 import io.reactivex.rxjava3.flowables.GroupedFlowable;
26 import io.reactivex.rxjava3.functions.*;
27 import io.reactivex.rxjava3.internal.subscriptions.*;
28 import io.reactivex.rxjava3.internal.util.*;
29 import io.reactivex.rxjava3.operators.SpscLinkedArrayQueue;
30 import io.reactivex.rxjava3.plugins.RxJavaPlugins;
31
32 public final class FlowableGroupBy<T, K, V> extends AbstractFlowableWithUpstream<T, GroupedFlowable<K, V>> {
33 final Function<? super T, ? extends K> keySelector;
34 final Function<? super T, ? extends V> valueSelector;
35 final int bufferSize;
36 final boolean delayError;
37 final Function<? super Consumer<Object>, ? extends Map<K, Object>> mapFactory;
38
39 public FlowableGroupBy(Flowable<T> source, Function<? super T, ? extends K> keySelector, Function<? super T, ? extends V> valueSelector,
40 int bufferSize, boolean delayError, Function<? super Consumer<Object>, ? extends Map<K, Object>> mapFactory) {
41 super(source);
42 this.keySelector = keySelector;
43 this.valueSelector = valueSelector;
44 this.bufferSize = bufferSize;
45 this.delayError = delayError;
46 this.mapFactory = mapFactory;
47 }
48
49 @Override
50 @SuppressWarnings({ "unchecked", "rawtypes" })
51 protected void subscribeActual(Subscriber<? super GroupedFlowable<K, V>> s) {
52
53 final Map<Object, GroupedUnicast<K, V>> groups;
54 final Queue<GroupedUnicast<K, V>> evictedGroups;
55
56 try {
57 if (mapFactory == null) {
58 evictedGroups = null;
59 groups = new ConcurrentHashMap<>();
60 } else {
61 evictedGroups = new ConcurrentLinkedQueue<>();
62 Consumer<Object> evictionAction = (Consumer) new EvictionAction<>(evictedGroups);
63 groups = (Map) mapFactory.apply(evictionAction);
64 }
65 } catch (Throwable e) {
66 Exceptions.throwIfFatal(e);
67 s.onSubscribe(EmptyComponent.INSTANCE);
68 s.onError(e);
69 return;
70 }
71 GroupBySubscriber<T, K, V> subscriber =
72 new GroupBySubscriber<>(s, keySelector, valueSelector, bufferSize, delayError, groups, evictedGroups);
73 source.subscribe(subscriber);
74 }
75
76 public static final class GroupBySubscriber<T, K, V>
77 extends AtomicLong
78 implements FlowableSubscriber<T>, Subscription {
79
80 private static final long serialVersionUID = -3688291656102519502L;
81
82 final Subscriber<? super GroupedFlowable<K, V>> downstream;
83 final Function<? super T, ? extends K> keySelector;
84 final Function<? super T, ? extends V> valueSelector;
85 final int bufferSize;
86 final int limit;
87 final boolean delayError;
88 final Map<Object, GroupedUnicast<K, V>> groups;
89 final Queue<GroupedUnicast<K, V>> evictedGroups;
90
91 static final Object NULL_KEY = new Object();
92
93 Subscription upstream;
94
95 final AtomicBoolean cancelled = new AtomicBoolean();
96
97 long emittedGroups;
98
99 final AtomicInteger groupCount = new AtomicInteger(1);
100
101 final AtomicLong groupConsumed = new AtomicLong();
102
103 boolean done;
104
105 public GroupBySubscriber(Subscriber<? super GroupedFlowable<K, V>> actual, Function<? super T, ? extends K> keySelector,
106 Function<? super T, ? extends V> valueSelector, int bufferSize, boolean delayError,
107 Map<Object, GroupedUnicast<K, V>> groups, Queue<GroupedUnicast<K, V>> evictedGroups) {
108 this.downstream = actual;
109 this.keySelector = keySelector;
110 this.valueSelector = valueSelector;
111 this.bufferSize = bufferSize;
112 this.limit = bufferSize - (bufferSize >> 2);
113 this.delayError = delayError;
114 this.groups = groups;
115 this.evictedGroups = evictedGroups;
116 }
117
118 @Override
119 public void onSubscribe(Subscription s) {
120 if (SubscriptionHelper.validate(this.upstream, s)) {
121 this.upstream = s;
122 downstream.onSubscribe(this);
123 s.request(bufferSize);
124 }
125 }
126
127 @Override
128 public void onNext(T t) {
129 if (done) {
130 return;
131 }
132
133 K key;
134 try {
135 key = keySelector.apply(t);
136 } catch (Throwable ex) {
137 Exceptions.throwIfFatal(ex);
138 upstream.cancel();
139 onError(ex);
140 return;
141 }
142
143 boolean newGroup = false;
144 Object mapKey = key != null ? key : NULL_KEY;
145 GroupedUnicast<K, V> group = groups.get(mapKey);
146 if (group == null) {
147 // if the main has been cancelled, stop creating groups
148 // and skip this value
149 if (cancelled.get()) {
150 return;
151 }
152
153 group = GroupedUnicast.createWith(key, bufferSize, this, delayError);
154 groups.put(mapKey, group);
155
156 groupCount.getAndIncrement();
157
158 newGroup = true;
159 }
160
161 V v;
162 try {
163 v = ExceptionHelper.nullCheck(valueSelector.apply(t), "The valueSelector returned a null value.");
164 } catch (Throwable ex) {
165 Exceptions.throwIfFatal(ex);
166 upstream.cancel();
167 if (newGroup) {
168 if (emittedGroups != get()) {
169 downstream.onNext(group);
170 } else {
171 MissingBackpressureException mbe = new MissingBackpressureException(groupHangWarning(emittedGroups));
172 mbe.initCause(ex);
173 onError(mbe);
174 return;
175 }
176 }
177 onError(ex);
178 return;
179 }
180
181 group.onNext(v);
182
183 completeEvictions();
184
185 if (newGroup) {
186 if (emittedGroups != get()) {
187 emittedGroups++;
188 downstream.onNext(group);
189 if (group.state.tryAbandon()) {
190 cancel(key);
191 group.onComplete();
192
193 requestGroup(1);
194 }
195 } else {
196 upstream.cancel();
197 onError(new MissingBackpressureException(groupHangWarning(emittedGroups)));
198 }
199 }
200 }
201
202 static String groupHangWarning(long n) {
203 return "Unable to emit a new group (#" + n + ") due to lack of requests. Please make sure the downstream can always accept a new group as well as each group is consumed in order for the whole operator to be able to proceed.";
204 }
205
206 @Override
207 public void onError(Throwable t) {
208 if (done) {
209 RxJavaPlugins.onError(t);
210 return;
211 }
212 done = true;
213 for (GroupedUnicast<K, V> g : groups.values()) {
214 g.onError(t);
215 }
216 groups.clear();
217 completeEvictions();
218 downstream.onError(t);
219 }
220
221 @Override
222 public void onComplete() {
223 if (!done) {
224 for (GroupedUnicast<K, V> g : groups.values()) {
225 g.onComplete();
226 }
227
228 groups.clear();
229 completeEvictions();
230
231 done = true;
232 downstream.onComplete();
233 }
234 }
235
236 @Override
237 public void request(long n) {
238 if (SubscriptionHelper.validate(n)) {
239 BackpressureHelper.add(this, n);
240 }
241 }
242
243 @Override
244 public void cancel() {
245 // cancelling the main source means we don't want any more groups
246 // but running groups still require new values
247 if (cancelled.compareAndSet(false, true)) {
248 completeEvictions();
249 if (groupCount.decrementAndGet() == 0) {
250 upstream.cancel();
251 }
252 }
253 }
254
255 private void completeEvictions() {
256 if (evictedGroups != null) {
257 int count = 0;
258 GroupedUnicast<K, V> evictedGroup;
259 while ((evictedGroup = evictedGroups.poll()) != null) {
260 if (evictedGroup.state.tryComplete()) {
261 count++;
262 }
263 }
264 if (count != 0) {
265 groupCount.addAndGet(-count);
266 }
267 }
268 }
269
270 public void cancel(K key) {
271 Object mapKey = key != null ? key : NULL_KEY;
272 if (groups.remove(mapKey) != null) {
273 if (groupCount.decrementAndGet() == 0) {
274 upstream.cancel();
275 }
276 }
277 }
278
279 void requestGroup(long n) {
280 // lots of atomics, save local
281 AtomicLong groupConsumed = this.groupConsumed;
282 int limit = this.limit;
283 // Concurrent groups can request at once, a CAS loop is needed
284 for (;;) {
285 long currentConsumed = groupConsumed.get();
286 long newConsumed = BackpressureHelper.addCap(currentConsumed, n);
287 // Accumulate the consumed amounts and atomically update the total
288 if (groupConsumed.compareAndSet(currentConsumed, newConsumed)) {
289 // if successful, let's see if the prefetch limit has been surpassed
290 for (;;) {
291 if (newConsumed < limit) {
292 // no further actions to be taken
293 return;
294 }
295
296 // Yes, remove one limit from total consumed
297 long newConsumedAfterLimit = newConsumed - limit;
298 // Only one thread should subtract
299 if (groupConsumed.compareAndSet(newConsumed, newConsumedAfterLimit)) {
300 // Then request up to limit
301 upstream.request(limit);
302 }
303 // We don't quit but loop to see if we are still above the prefetch limit
304 newConsumed = groupConsumed.get();
305 }
306 }
307 }
308 }
309 }
310
311 static final class EvictionAction<K, V> implements Consumer<GroupedUnicast<K, V>> {
312
313 final Queue<GroupedUnicast<K, V>> evictedGroups;
314
315 EvictionAction(Queue<GroupedUnicast<K, V>> evictedGroups) {
316 this.evictedGroups = evictedGroups;
317 }
318
319 @Override
320 public void accept(GroupedUnicast<K, V> value) {
321 evictedGroups.offer(value);
322 }
323 }
324
325 static final class GroupedUnicast<K, T> extends GroupedFlowable<K, T> {
326
327 final State<T, K> state;
328
329 public static <T, K> GroupedUnicast<K, T> createWith(K key, int bufferSize, GroupBySubscriber<?, K, T> parent, boolean delayError) {
330 State<T, K> state = new State<>(bufferSize, parent, key, delayError);
331 return new GroupedUnicast<>(key, state);
332 }
333
334 protected GroupedUnicast(K key, State<T, K> state) {
335 super(key);
336 this.state = state;
337 }
338
339 @Override
340 protected void subscribeActual(Subscriber<? super T> s) {
341 state.subscribe(s);
342 }
343
344 public void onNext(T t) {
345 state.onNext(t);
346 }
347
348 public void onError(Throwable e) {
349 state.onError(e);
350 }
351
352 public void onComplete() {
353 state.onComplete();
354 }
355 }
356
357 static final class State<T, K> extends BasicIntQueueSubscription<T> implements Publisher<T> {
358
359 private static final long serialVersionUID = -3852313036005250360L;
360
361 final K key;
362 final SpscLinkedArrayQueue<T> queue;
363 final GroupBySubscriber<?, K, T> parent;
364 final boolean delayError;
365
366 final AtomicLong requested = new AtomicLong();
367
368 volatile boolean done;
369 Throwable error;
370
371 final AtomicBoolean cancelled = new AtomicBoolean();
372
373 final AtomicReference<Subscriber<? super T>> actual = new AtomicReference<>();
374
375 boolean outputFused;
376 int produced;
377
378 final AtomicInteger once = new AtomicInteger();
379
380 static final int FRESH = 0;
381 static final int HAS_SUBSCRIBER = 1;
382 static final int ABANDONED = 2;
383 static final int ABANDONED_HAS_SUBSCRIBER = ABANDONED | HAS_SUBSCRIBER;
384
385 final AtomicBoolean evictOnce = new AtomicBoolean();
386
387 State(int bufferSize, GroupBySubscriber<?, K, T> parent, K key, boolean delayError) {
388 this.queue = new SpscLinkedArrayQueue<>(bufferSize);
389 this.parent = parent;
390 this.key = key;
391 this.delayError = delayError;
392 }
393
394 @Override
395 public void request(long n) {
396 if (SubscriptionHelper.validate(n)) {
397 BackpressureHelper.add(requested, n);
398 drain();
399 }
400 }
401
402 @Override
403 public void cancel() {
404 if (cancelled.compareAndSet(false, true)) {
405 cancelParent();
406 drain();
407 }
408 }
409
410 @Override
411 public void subscribe(Subscriber<? super T> subscriber) {
412 for (;;) {
413 int s = once.get();
414 if ((s & HAS_SUBSCRIBER) != 0) {
415 break;
416 }
417 int u = s | HAS_SUBSCRIBER;
418 if (once.compareAndSet(s, u)) {
419 subscriber.onSubscribe(this);
420 actual.lazySet(subscriber);
421 if (cancelled.get()) {
422 actual.lazySet(null);
423 } else {
424 drain();
425 }
426 return;
427 }
428 }
429 EmptySubscription.error(new IllegalStateException("Only one Subscriber allowed!"), subscriber);
430 }
431
432 public void onNext(T t) {
433 queue.offer(t);
434 drain();
435 }
436
437 public void onError(Throwable e) {
438 error = e;
439 done = true;
440 drain();
441 }
442
443 public void onComplete() {
444 done = true;
445 drain();
446 }
447
448 boolean tryComplete() {
449 boolean canEvict = evictOnce.compareAndSet(false, true);
450 done = true;
451 drain();
452 return canEvict;
453 }
454
455 void cancelParent() {
456 if ((once.get() & ABANDONED) == 0) {
457 if (evictOnce.compareAndSet(false, true)) {
458 parent.cancel(key);
459 }
460 }
461 }
462
463 boolean tryAbandon() {
464 return once.get() == FRESH && once.compareAndSet(FRESH, ABANDONED);
465 }
466
467 void drain() {
468 if (getAndIncrement() != 0) {
469 return;
470 }
471 if (outputFused) {
472 drainFused();
473 } else {
474 drainNormal();
475 }
476 }
477
478 void drainFused() {
479 int missed = 1;
480
481 final SpscLinkedArrayQueue<T> q = this.queue;
482 Subscriber<? super T> a = this.actual.get();
483
484 for (;;) {
485 if (a != null) {
486 if (cancelled.get()) {
487 return;
488 }
489
490 boolean d = done;
491
492 if (d && !delayError) {
493 Throwable ex = error;
494 if (ex != null) {
495 q.clear();
496 a.onError(ex);
497 return;
498 }
499 }
500
501 a.onNext(null);
502
503 if (d) {
504 Throwable ex = error;
505 if (ex != null) {
506 a.onError(ex);
507 } else {
508 a.onComplete();
509 }
510 return;
511 }
512 }
513
514 missed = addAndGet(-missed);
515 if (missed == 0) {
516 return;
517 }
518
519 if (a == null) {
520 a = this.actual.get();
521 }
522 }
523 }
524
525 void drainNormal() {
526 int missed = 1;
527
528 final SpscLinkedArrayQueue<T> q = queue;
529 final boolean delayError = this.delayError;
530 Subscriber<? super T> a = actual.get();
531 final AtomicBoolean cancelled = this.cancelled;
532
533 outer:
534 for (;;) {
535 if (cancelled.get()) {
536 cleanupQueue(0, false);
537 } else {
538 if (a != null) {
539 long r = requested.get();
540 long e = 0;
541
542 while (e != r) {
543 boolean d = done;
544 T v = q.poll();
545 boolean empty = v == null;
546
547 if (checkTerminated(d, empty, a, delayError, e, !empty)) {
548 continue outer;
549 }
550
551 if (empty) {
552 break;
553 }
554
555 a.onNext(v);
556
557 e++;
558 }
559
560 if (e == r && checkTerminated(done, q.isEmpty(), a, delayError, e, false)) {
561 continue outer;
562 }
563
564 if (e != 0L) {
565 BackpressureHelper.produced(requested, e);
566 // replenish based on this batch run
567 requestParent(e);
568 }
569 }
570 }
571
572 missed = addAndGet(-missed);
573 if (missed == 0) {
574 break;
575 }
576 if (a == null) {
577 a = actual.get();
578 }
579 }
580 }
581
582 void requestParent(long e) {
583 if ((once.get() & ABANDONED) == 0) {
584 parent.requestGroup(e);
585 }
586 }
587
588 void cleanupQueue(long emitted, boolean polled) {
589 // if this group is canceled, all accumulated emissions and
590 // remaining items in the queue should be requested
591 // so that other groups can proceed
592 while (queue.poll() != null) {
593 emitted++;
594 }
595
596 replenishParent(emitted, polled);
597 }
598
599 void replenishParent(long emitted, boolean polled) {
600 if (polled) {
601 emitted++;
602 }
603 if (emitted != 0L) {
604 requestParent(emitted);
605 }
606 }
607
608 boolean checkTerminated(boolean d, boolean empty, Subscriber<? super T> a,
609 boolean delayError, long emitted, boolean polled) {
610 if (cancelled.get()) {
611 cleanupQueue(emitted, polled);
612 return true;
613 }
614
615 if (d) {
616 if (delayError) {
617 if (empty) {
618 cancelled.lazySet(true);
619 Throwable e = error;
620 if (e != null) {
621 a.onError(e);
622 } else {
623 a.onComplete();
624 // completion doesn't mean the parent has completed
625 // because of evicted groups
626 replenishParent(emitted, polled);
627 }
628 return true;
629 }
630 } else {
631 Throwable e = error;
632 if (e != null) {
633 queue.clear();
634 cancelled.lazySet(true);
635 a.onError(e);
636 return true;
637 } else
638 if (empty) {
639 cancelled.lazySet(true);
640 a.onComplete();
641
642 // completion doesn't mean the parent has completed
643 // because of evicted groups
644 replenishParent(emitted, polled);
645 return true;
646 }
647 }
648 }
649
650 return false;
651 }
652
653 @Override
654 public int requestFusion(int mode) {
655 // FIXME fusion mode causes hangs
656 /*
657 if ((mode & ASYNC) != 0) {
658 outputFused = true;
659 return ASYNC;
660 }
661 */
662 return NONE;
663 }
664
665 void tryReplenish() {
666 int p = produced;
667 if (p != 0) {
668 produced = 0;
669 requestParent(p);
670 }
671 }
672
673 @Nullable
674 @Override
675 public T poll() {
676 T v = queue.poll();
677 if (v != null) {
678 produced++;
679 return v;
680 }
681 tryReplenish();
682 return null;
683 }
684
685 @Override
686 public boolean isEmpty() {
687 if (queue.isEmpty()) {
688 tryReplenish();
689 return true;
690 }
691 tryReplenish();
692 return false;
693 }
694
695 @Override
696 public void clear() {
697 SpscLinkedArrayQueue<T> q = queue;
698 // queue.clear() would drop submitted items and not replenish, possibly hanging other groups
699 while (q.poll() != null) {
700 produced++;
701 }
702 tryReplenish();
703 }
704 }
705 }