Debian Codegraph @

src/main/java/io/reactivex/rxjava3/internal/queue/MpscLinkedQueue.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.internal.queue;
20
21 import java.util.concurrent.atomic.AtomicReference;
22
23 import io.reactivex.rxjava3.annotations.Nullable;
24 import io.reactivex.rxjava3.operators.SimplePlainQueue;
25
26 /**
27 * A multi-producer single consumer unbounded queue.
28 * @param <T> the contained value type
29 */
30 public final class MpscLinkedQueue<T> implements SimplePlainQueue<T> {
31 private final AtomicReference<LinkedQueueNode<T>> producerNode;
32 private final AtomicReference<LinkedQueueNode<T>> consumerNode;
33
34 public MpscLinkedQueue() {
35 producerNode = new AtomicReference<>();
36 consumerNode = new AtomicReference<>();
37 LinkedQueueNode<T> node = new LinkedQueueNode<>();
38 spConsumerNode(node);
39 xchgProducerNode(node); // this ensures correct construction: StoreLoad
40 }
41
42 /**
43 * {@inheritDoc} <br>
44 * <p>
45 * IMPLEMENTATION NOTES:<br>
46 * Offer is allowed from multiple threads.<br>
47 * Offer allocates a new node and:
48 * <ol>
49 * <li>Swaps it atomically with current producer node (only one producer 'wins')
50 * <li>Sets the new node as the node following from the swapped producer node
51 * </ol>
52 * This works because each producer is guaranteed to 'plant' a new node and link the old node. No 2 producers can
53 * get the same producer node as part of XCHG guarantee.
54 *
55 * @see java.util.Queue#offer(java.lang.Object)
56 */
57 @Override
58 public boolean offer(final T e) {
59 if (null == e) {
60 throw new NullPointerException("Null is not a valid element");
61 }
62 final LinkedQueueNode<T> nextNode = new LinkedQueueNode<>(e);
63 final LinkedQueueNode<T> prevProducerNode = xchgProducerNode(nextNode);
64 // Should a producer thread get interrupted here the chain WILL be broken until that thread is resumed
65 // and completes the store in prev.next.
66 prevProducerNode.soNext(nextNode); // StoreStore
67 return true;
68 }
69
70 /**
71 * {@inheritDoc} <br>
72 * <p>
73 * IMPLEMENTATION NOTES:<br>
74 * Poll is allowed from a SINGLE thread.<br>
75 * Poll reads the next node from the consumerNode and:
76 * <ol>
77 * <li>If it is null, the queue is assumed empty (though it might not be).
78 * <li>If it is not null set it as the consumer node and return it's now evacuated value.
79 * </ol>
80 * This means the consumerNode.value is always null, which is also the starting point for the queue. Because null
81 * values are not allowed to be offered this is the only node with it's value set to null at any one time.
82 *
83 * @see java.util.Queue#poll()
84 */
85 @Nullable
86 @Override
87 public T poll() {
88 LinkedQueueNode<T> currConsumerNode = lpConsumerNode(); // don't load twice, it's alright
89 LinkedQueueNode<T> nextNode = currConsumerNode.lvNext();
90 if (nextNode != null) {
91 // we have to null out the value because we are going to hang on to the node
92 final T nextValue = nextNode.getAndNullValue();
93 spConsumerNode(nextNode);
94 return nextValue;
95 }
96 else if (currConsumerNode != lvProducerNode()) {
97 // spin, we are no longer wait free
98 while ((nextNode = currConsumerNode.lvNext()) == null) { } // NOPMD
99 // got the next node...
100
101 // we have to null out the value because we are going to hang on to the node
102 final T nextValue = nextNode.getAndNullValue();
103 spConsumerNode(nextNode);
104 return nextValue;
105 }
106 return null;
107 }
108
109 @Override
110 public boolean offer(T v1, T v2) {
111 offer(v1);
112 offer(v2);
113 return true;
114 }
115
116 @Override
117 public void clear() {
118 while (poll() != null && !isEmpty()) { } // NOPMD
119 }
120 LinkedQueueNode<T> lvProducerNode() {
121 return producerNode.get();
122 }
123 LinkedQueueNode<T> xchgProducerNode(LinkedQueueNode<T> node) {
124 return producerNode.getAndSet(node);
125 }
126 LinkedQueueNode<T> lvConsumerNode() {
127 return consumerNode.get();
128 }
129
130 LinkedQueueNode<T> lpConsumerNode() {
131 return consumerNode.get();
132 }
133 void spConsumerNode(LinkedQueueNode<T> node) {
134 consumerNode.lazySet(node);
135 }
136
137 /**
138 * {@inheritDoc} <br>
139 * <p>
140 * IMPLEMENTATION NOTES:<br>
141 * Queue is empty when producerNode is the same as consumerNode. An alternative implementation would be to observe
142 * the producerNode.value is null, which also means an empty queue because only the consumerNode.value is allowed to
143 * be null.
144 */
145 @Override
146 public boolean isEmpty() {
147 return lvConsumerNode() == lvProducerNode();
148 }
149
150 static final class LinkedQueueNode<E> extends AtomicReference<LinkedQueueNode<E>> {
151
152 private static final long serialVersionUID = 2404266111789071508L;
153
154 private E value;
155
156 LinkedQueueNode() {
157 }
158
159 LinkedQueueNode(E val) {
160 spValue(val);
161 }
162 /**
163 * Gets the current value and nulls out the reference to it from this node.
164 *
165 * @return value
166 */
167 public E getAndNullValue() {
168 E temp = lpValue();
169 spValue(null);
170 return temp;
171 }
172
173 public E lpValue() {
174 return value;
175 }
176
177 public void spValue(E newValue) {
178 value = newValue;
179 }
180
181 public void soNext(LinkedQueueNode<E> n) {
182 lazySet(n);
183 }
184
185 public LinkedQueueNode<E> lvNext() {
186 return get();
187 }
188 }
189 }