Debian Codegraph @

src/main/java/io/reactivex/rxjava3/operators/SpscArrayQueue.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 /*
15 * The code was inspired by the similarly named JCTools class:
16 * https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/atomic
17 */
18
19 package io.reactivex.rxjava3.operators;
20
21 import java.util.concurrent.atomic.*;
22
23 import io.reactivex.rxjava3.annotations.Nullable;
24 import io.reactivex.rxjava3.internal.util.Pow2;
25
26 /**
27 * A Single-Producer-Single-Consumer queue backed by a pre-allocated buffer.
28 * <p>
29 * This implementation is a mashup of the <a href="http://sourceforge.net/projects/mc-fastflow/">Fast Flow</a>
30 * algorithm with an optimization of the offer method taken from the <a
31 * href="http://staff.ustc.edu.cn/~bhua/publications/IJPP_draft.pdf">BQueue</a> algorithm (a variation on Fast
32 * Flow), and adjusted to comply with Queue.offer semantics with regards to capacity.<br>
33 * For convenience the relevant papers are available in the resources folder:<br>
34 * <i>2010 - Pisa - SPSC Queues on Shared Cache Multi-Core Systems.pdf<br>
35 * 2012 - Junchang- BQueue- Efficient and Practical Queuing.pdf <br>
36 * </i> This implementation is wait free.
37 *
38 * @param <E> the element type of the queue
39 * @since 3.1.1
40 */
41 public final class SpscArrayQueue<E> extends AtomicReferenceArray<E> implements SimplePlainQueue<E> {
42 private static final long serialVersionUID = -1296597691183856449L;
43 private static final Integer MAX_LOOK_AHEAD_STEP = Integer.getInteger("jctools.spsc.max.lookahead.step", 4096);
44 final int mask;
45 final AtomicLong producerIndex;
46 long producerLookAhead;
47 final AtomicLong consumerIndex;
48 final int lookAheadStep;
49
50 /**
51 * Constructs an array-backed queue with the given capacity rounded
52 * up to the next power of 2 size.
53 * @param capacity the maximum number of elements the queue would hold,
54 * rounded up to the next power of 2
55 */
56 public SpscArrayQueue(int capacity) {
57 super(Pow2.roundToPowerOfTwo(capacity));
58 this.mask = length() - 1;
59 this.producerIndex = new AtomicLong();
60 this.consumerIndex = new AtomicLong();
61 lookAheadStep = Math.min(capacity / 4, MAX_LOOK_AHEAD_STEP);
62 }
63
64 @Override
65 public boolean offer(E e) {
66 if (null == e) {
67 throw new NullPointerException("Null is not a valid element");
68 }
69 // local load of field to avoid repeated loads after volatile reads
70 final int mask = this.mask;
71 final long index = producerIndex.get();
72 final int offset = calcElementOffset(index, mask);
73 if (index >= producerLookAhead) {
74 int step = lookAheadStep;
75 if (null == lvElement(calcElementOffset(index + step, mask))) { // LoadLoad
76 producerLookAhead = index + step;
77 } else if (null != lvElement(offset)) {
78 return false;
79 }
80 }
81 soElement(offset, e); // StoreStore
82 soProducerIndex(index + 1); // ordered store -> atomic and ordered for size()
83 return true;
84 }
85
86 @Override
87 public boolean offer(E v1, E v2) {
88 // FIXME
89 return offer(v1) && offer(v2);
90 }
91
92 @Nullable
93 @Override
94 public E poll() {
95 final long index = consumerIndex.get();
96 final int offset = calcElementOffset(index);
97 // local load of field to avoid repeated loads after volatile reads
98 final E e = lvElement(offset); // LoadLoad
99 if (null == e) {
100 return null;
101 }
102 soConsumerIndex(index + 1); // ordered store -> atomic and ordered for size()
103 soElement(offset, null); // StoreStore
104 return e;
105 }
106
107 @Override
108 public boolean isEmpty() {
109 return producerIndex.get() == consumerIndex.get();
110 }
111
112 void soProducerIndex(long newIndex) {
113 producerIndex.lazySet(newIndex);
114 }
115
116 void soConsumerIndex(long newIndex) {
117 consumerIndex.lazySet(newIndex);
118 }
119
120 @Override
121 public void clear() {
122 // we have to test isEmpty because of the weaker poll() guarantee
123 while (poll() != null || !isEmpty()) { } // NOPMD
124 }
125
126 int calcElementOffset(long index, int mask) {
127 return (int)index & mask;
128 }
129
130 int calcElementOffset(long index) {
131 return (int)index & mask;
132 }
133
134 void soElement(int offset, E value) {
135 lazySet(offset, value);
136 }
137
138 E lvElement(int offset) {
139 return get(offset);
140 }
141 }
142