| 5 |
|
*/ |
| 6 |
|
|
| 7 |
|
package java.util.concurrent; |
| 8 |
– |
import java.util.*; |
| 9 |
– |
import java.util.concurrent.atomic.*; |
| 8 |
|
|
| 9 |
+ |
import java.util.AbstractQueue; |
| 10 |
+ |
import java.util.ArrayList; |
| 11 |
+ |
import java.util.Collection; |
| 12 |
+ |
import java.util.Iterator; |
| 13 |
+ |
import java.util.NoSuchElementException; |
| 14 |
+ |
import java.util.Queue; |
| 15 |
|
|
| 16 |
|
/** |
| 17 |
|
* An unbounded thread-safe {@linkplain Queue queue} based on linked nodes. |
| 130 |
|
* CAS, so they never regress, although again this is merely an |
| 131 |
|
* optimization. |
| 132 |
|
*/ |
| 133 |
+ |
|
| 134 |
|
private static class Node<E> { |
| 135 |
|
private volatile E item; |
| 136 |
|
private volatile Node<E> next; |
| 137 |
|
|
| 138 |
< |
Node(E item) { lazySetItem(item); } |
| 138 |
> |
Node(E item) { |
| 139 |
> |
// Piggyback on imminent casNext() |
| 140 |
> |
lazySetItem(item); |
| 141 |
> |
} |
| 142 |
|
|
| 143 |
|
E getItem() { |
| 144 |
|
return item; |
| 179 |
|
} |
| 180 |
|
|
| 181 |
|
/** |
| 182 |
< |
* Pointer to first node, initialized to a dummy node. |
| 182 |
> |
* A node from which the first live (non-deleted) node (if any) |
| 183 |
> |
* can be reached in O(1) time. |
| 184 |
> |
* Invariants: |
| 185 |
> |
* - all live nodes are reachable from head via succ() |
| 186 |
> |
* - head != null |
| 187 |
> |
* - (tmp = head).next != tmp || tmp != head |
| 188 |
> |
* Non-invariants: |
| 189 |
> |
* - head.item may or may not be null. |
| 190 |
> |
* - it is permitted for tail to lag behind head, that is, for tail |
| 191 |
> |
* to not be reachable from head! |
| 192 |
|
*/ |
| 193 |
|
private transient volatile Node<E> head = new Node<E>(null); |
| 194 |
|
|
| 195 |
< |
/** Pointer to last node on list */ |
| 195 |
> |
/** |
| 196 |
> |
* A node from which the last node on list (that is, the unique |
| 197 |
> |
* node with node.next == null) can be reached in O(1) time. |
| 198 |
> |
* Invariants: |
| 199 |
> |
* - the last node is always reachable from tail via succ() |
| 200 |
> |
* - tail != null |
| 201 |
> |
* Non-invariants: |
| 202 |
> |
* - tail.item may or may not be null. |
| 203 |
> |
* - it is permitted for tail to lag behind head, that is, for tail |
| 204 |
> |
* to not be reachable from head! |
| 205 |
> |
* - tail.next may or may not be self-pointing to tail. |
| 206 |
> |
*/ |
| 207 |
|
private transient volatile Node<E> tail = head; |
| 208 |
|
|
| 209 |
|
|
| 238 |
|
} |
| 239 |
|
|
| 240 |
|
/** |
| 241 |
< |
* We don't bother to update head or tail pointers if less than |
| 241 |
> |
* We don't bother to update head or tail pointers if fewer than |
| 242 |
|
* HOPS links from "true" location. We assume that volatile |
| 243 |
|
* writes are significantly more expensive than volatile reads. |
| 244 |
|
*/ |
| 335 |
|
} |
| 336 |
|
|
| 337 |
|
/** |
| 338 |
< |
* Returns the first actual (non-header) node on list. This is yet |
| 339 |
< |
* another variant of poll/peek; here returning out the first |
| 340 |
< |
* node, not element (so we cannot collapse with peek() without |
| 341 |
< |
* introducing race.) |
| 338 |
> |
* Returns the first live (non-deleted) node on list, or null if none. |
| 339 |
> |
* This is yet another variant of poll/peek; here returning the |
| 340 |
> |
* first node, not element. We could make peek() a wrapper around |
| 341 |
> |
* first(), but that would cost an extra volatile read of item, |
| 342 |
> |
* and the need to add a retry loop to deal with the possibility |
| 343 |
> |
* of losing a race to a concurrent poll(). |
| 344 |
|
*/ |
| 345 |
|
Node<E> first() { |
| 346 |
|
Node<E> h = head; |
| 431 |
|
Node<E> pred = null; |
| 432 |
|
for (Node<E> p = first(); p != null; p = succ(p)) { |
| 433 |
|
E item = p.getItem(); |
| 434 |
< |
if (item != null && o.equals(item) && p.casItem(item, null)) { |
| 434 |
> |
if (item != null && |
| 435 |
> |
o.equals(item) && |
| 436 |
> |
p.casItem(item, null)) { |
| 437 |
|
Node<E> next = succ(p); |
| 438 |
|
if (pred != null && next != null) |
| 439 |
|
pred.casNext(p, next); |
