Debian Codegraph @

src/main/java/io/reactivex/rxjava3/operators/SpscLinkedArrayQueue.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 array-backed queue which can allocate new arrays in case the consumer is slower
28 * than the producer.
29 * @param <T> the contained value type
30 * @since 3.1.1
31 */
32 public final class SpscLinkedArrayQueue<T> implements SimplePlainQueue<T> {
33 static final int MAX_LOOK_AHEAD_STEP = Integer.getInteger("jctools.spsc.max.lookahead.step", 4096);
34 final AtomicLong producerIndex = new AtomicLong();
35
36 int producerLookAheadStep;
37 long producerLookAhead;
38
39 final int producerMask;
40
41 AtomicReferenceArray<Object> producerBuffer;
42 final int consumerMask;
43 AtomicReferenceArray<Object> consumerBuffer;
44 final AtomicLong consumerIndex = new AtomicLong();
45
46 private static final Object HAS_NEXT = new Object();
47
48 /**
49 * Constructs a linked array-based queue instance with the given
50 * island size rounded up to the next power of 2.
51 * @param bufferSize the maximum number of elements per island
52 */
53 public SpscLinkedArrayQueue(final int bufferSize) {
54 int p2capacity = Pow2.roundToPowerOfTwo(Math.max(8, bufferSize));
55 int mask = p2capacity - 1;
56 AtomicReferenceArray<Object> buffer = new AtomicReferenceArray<>(p2capacity + 1);
57 producerBuffer = buffer;
58 producerMask = mask;
59 adjustLookAheadStep(p2capacity);
60 consumerBuffer = buffer;
61 consumerMask = mask;
62 producerLookAhead = mask - 1; // we know it's all empty to start with
63 soProducerIndex(0L);
64 }
65
66 /**
67 * {@inheritDoc}
68 * <p>
69 * This implementation is correct for single producer thread use only.
70 */
71 @Override
72 public boolean offer(final T e) {
73 if (null == e) {
74 throw new NullPointerException("Null is not a valid element");
75 }
76 // local load of field to avoid repeated loads after volatile reads
77 final AtomicReferenceArray<Object> buffer = producerBuffer;
78 final long index = lpProducerIndex();
79 final int mask = producerMask;
80 final int offset = calcWrappedOffset(index, mask);
81 if (index < producerLookAhead) {
82 return writeToQueue(buffer, e, index, offset);
83 } else {
84 final int lookAheadStep = producerLookAheadStep;
85 // go around the buffer or resize if full (unless we hit max capacity)
86 int lookAheadElementOffset = calcWrappedOffset(index + lookAheadStep, mask);
87 if (null == lvElement(buffer, lookAheadElementOffset)) { // LoadLoad
88 producerLookAhead = index + lookAheadStep - 1; // joy, there's plenty of room
89 return writeToQueue(buffer, e, index, offset);
90 } else if (null == lvElement(buffer, calcWrappedOffset(index + 1, mask))) { // buffer is not full
91 return writeToQueue(buffer, e, index, offset);
92 } else {
93 resize(buffer, index, offset, e, mask); // add a buffer and link old to new
94 return true;
95 }
96 }
97 }
98
99 private boolean writeToQueue(final AtomicReferenceArray<Object> buffer, final T e, final long index, final int offset) {
100 soElement(buffer, offset, e); // StoreStore
101 soProducerIndex(index + 1); // this ensures atomic write of long on 32bit platforms
102 return true;
103 }
104
105 private void resize(final AtomicReferenceArray<Object> oldBuffer, final long currIndex, final int offset, final T e,
106 final long mask) {
107 final int capacity = oldBuffer.length();
108 final AtomicReferenceArray<Object> newBuffer = new AtomicReferenceArray<>(capacity);
109 producerBuffer = newBuffer;
110 producerLookAhead = currIndex + mask - 1;
111 soElement(newBuffer, offset, e); // StoreStore
112 soNext(oldBuffer, newBuffer);
113 soElement(oldBuffer, offset, HAS_NEXT); // new buffer is visible after element is
114 // inserted
115 soProducerIndex(currIndex + 1); // this ensures correctness on 32bit platforms
116 }
117
118 private void soNext(AtomicReferenceArray<Object> curr, AtomicReferenceArray<Object> next) {
119 soElement(curr, calcDirectOffset(curr.length() - 1), next);
120 }
121
122 @SuppressWarnings("unchecked")
123 private AtomicReferenceArray<Object> lvNextBufferAndUnlink(AtomicReferenceArray<Object> curr, int nextIndex) {
124 int nextOffset = calcDirectOffset(nextIndex);
125 AtomicReferenceArray<Object> nextBuffer = (AtomicReferenceArray<Object>)lvElement(curr, nextOffset);
126 soElement(curr, nextOffset, null); // Avoid GC nepotism
127 return nextBuffer;
128 }
129 /**
130 * {@inheritDoc}
131 * <p>
132 * This implementation is correct for single consumer thread use only.
133 */
134 @Nullable
135 @SuppressWarnings("unchecked")
136 @Override
137 public T poll() {
138 // local load of field to avoid repeated loads after volatile reads
139 final AtomicReferenceArray<Object> buffer = consumerBuffer;
140 final long index = lpConsumerIndex();
141 final int mask = consumerMask;
142 final int offset = calcWrappedOffset(index, mask);
143 final Object e = lvElement(buffer, offset); // LoadLoad
144 boolean isNextBuffer = e == HAS_NEXT;
145 if (null != e && !isNextBuffer) {
146 soElement(buffer, offset, null); // StoreStore
147 soConsumerIndex(index + 1); // this ensures correctness on 32bit platforms
148 return (T) e;
149 } else if (isNextBuffer) {
150 return newBufferPoll(lvNextBufferAndUnlink(buffer, mask + 1), index, mask);
151 }
152
153 return null;
154 }
155
156 @SuppressWarnings("unchecked")
157 private T newBufferPoll(AtomicReferenceArray<Object> nextBuffer, final long index, final int mask) {
158 consumerBuffer = nextBuffer;
159 final int offsetInNew = calcWrappedOffset(index, mask);
160 final T n = (T) lvElement(nextBuffer, offsetInNew); // LoadLoad
161 if (null != n) {
162 soElement(nextBuffer, offsetInNew, null); // StoreStore
163 soConsumerIndex(index + 1); // this ensures correctness on 32bit platforms
164 }
165 return n;
166 }
167
168 /**
169 * Returns the next element in this queue without removing it or {@code null}
170 * if this queue is empty
171 * @return the next element or {@code null}
172 */
173 @SuppressWarnings("unchecked")
174 @Nullable
175 public T peek() {
176 final AtomicReferenceArray<Object> buffer = consumerBuffer;
177 final long index = lpConsumerIndex();
178 final int mask = consumerMask;
179 final int offset = calcWrappedOffset(index, mask);
180 final Object e = lvElement(buffer, offset); // LoadLoad
181 if (e == HAS_NEXT) {
182 return newBufferPeek(lvNextBufferAndUnlink(buffer, mask + 1), index, mask);
183 }
184
185 return (T) e;
186 }
187
188 @SuppressWarnings("unchecked")
189 private T newBufferPeek(AtomicReferenceArray<Object> nextBuffer, final long index, final int mask) {
190 consumerBuffer = nextBuffer;
191 final int offsetInNew = calcWrappedOffset(index, mask);
192 return (T) lvElement(nextBuffer, offsetInNew); // LoadLoad
193 }
194
195 @Override
196 public void clear() {
197 while (poll() != null || !isEmpty()) { } // NOPMD
198 }
199
200 /**
201 * Returns the number of elements in the queue.
202 * @return the number of elements in the queue
203 */
204 public int size() {
205 /*
206 * It is possible for a thread to be interrupted or reschedule between the read of the producer and
207 * consumer indices, therefore protection is required to ensure size is within valid range. In the
208 * event of concurrent polls/offers to this method the size is OVER estimated as we read consumer
209 * index BEFORE the producer index.
210 */
211 long after = lvConsumerIndex();
212 while (true) {
213 final long before = after;
214 final long currentProducerIndex = lvProducerIndex();
215 after = lvConsumerIndex();
216 if (before == after) {
217 return (int) (currentProducerIndex - after);
218 }
219 }
220 }
221
222 @Override
223 public boolean isEmpty() {
224 return lvProducerIndex() == lvConsumerIndex();
225 }
226
227 private void adjustLookAheadStep(int capacity) {
228 producerLookAheadStep = Math.min(capacity / 4, MAX_LOOK_AHEAD_STEP);
229 }
230
231 private long lvProducerIndex() {
232 return producerIndex.get();
233 }
234
235 private long lvConsumerIndex() {
236 return consumerIndex.get();
237 }
238
239 private long lpProducerIndex() {
240 return producerIndex.get();
241 }
242
243 private long lpConsumerIndex() {
244 return consumerIndex.get();
245 }
246
247 private void soProducerIndex(long v) {
248 producerIndex.lazySet(v);
249 }
250
251 private void soConsumerIndex(long v) {
252 consumerIndex.lazySet(v);
253 }
254
255 private static int calcWrappedOffset(long index, int mask) {
256 return calcDirectOffset((int)index & mask);
257 }
258 private static int calcDirectOffset(int index) {
259 return index;
260 }
261 private static void soElement(AtomicReferenceArray<Object> buffer, int offset, Object e) {
262 buffer.lazySet(offset, e);
263 }
264
265 private static Object lvElement(AtomicReferenceArray<Object> buffer, int offset) {
266 return buffer.get(offset);
267 }
268
269 /**
270 * Offer two elements at the same time.
271 * <p>Don't use the regular offer() with this at all!
272 * @param first the first value, not null
273 * @param second the second value, not null
274 * @return true if the queue accepted the two new values
275 */
276 @Override
277 public boolean offer(T first, T second) {
278 final AtomicReferenceArray<Object> buffer = producerBuffer;
279 final long p = lvProducerIndex();
280 final int m = producerMask;
281
282 int pi = calcWrappedOffset(p + 2, m);
283
284 if (null == lvElement(buffer, pi)) {
285 pi = calcWrappedOffset(p, m);
286 soElement(buffer, pi + 1, second);
287 soElement(buffer, pi, first);
288 soProducerIndex(p + 2);
289 } else {
290 final int capacity = buffer.length();
291 final AtomicReferenceArray<Object> newBuffer = new AtomicReferenceArray<>(capacity);
292 producerBuffer = newBuffer;
293
294 pi = calcWrappedOffset(p, m);
295 soElement(newBuffer, pi + 1, second); // StoreStore
296 soElement(newBuffer, pi, first);
297 soNext(buffer, newBuffer);
298
299 soElement(buffer, pi, HAS_NEXT); // new buffer is visible after element is
300
301 soProducerIndex(p + 2); // this ensures correctness on 32bit platforms
302 }
303
304 return true;
305 }
306 }