| 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 |
} |