| 67 |
|
* |
| 68 |
|
* We extend the techniques developed for ConcurrentLinkedQueue and |
| 69 |
|
* LinkedTransferQueue (see the internal docs for those classes). |
| 70 |
+ |
* Understanding the ConcurrentLinkedQueue implementation is a |
| 71 |
+ |
* prerequisite for understanding the implementation of this class. |
| 72 |
|
* |
| 73 |
|
* The data structure is a symmetrical doubly-linked "GC-robust" |
| 74 |
|
* linked list of nodes. We minimize the number of volatile writes |
| 195 |
|
* except that most public methods that iterate through the list |
| 196 |
|
* follow next pointers ("forward" direction). |
| 197 |
|
* |
| 198 |
< |
* There is one desirable property we would like to have, but |
| 199 |
< |
* don't: it is possible, when an addFirst(A) is racing with |
| 200 |
< |
* pollFirst() removing B, for an iterating observer to see A B C |
| 201 |
< |
* and subsequently see A C, even though no interior removes are |
| 202 |
< |
* ever performed. I believe this wart can only be removed at |
| 203 |
< |
* significant runtime cost. |
| 198 |
> |
* We believe (without full proof) that all single-element deque |
| 199 |
> |
* operations (e.g., addFirst, peekLast, pollLast) are linearizable |
| 200 |
> |
* (see Herlihy and Shavit's book). However, some combinations of |
| 201 |
> |
* operations are known not to be linearizable. In particular, |
| 202 |
> |
* when an addFirst(A) is racing with pollFirst() removing B, it is |
| 203 |
> |
* possible for an observer iterating over the elements to observe |
| 204 |
> |
* A B C and subsequently observe A C, even though no interior |
| 205 |
> |
* removes are ever performed. Nevertheless, iterators behave |
| 206 |
> |
* reasonably, providing the "weakly consistent" guarantees. |
| 207 |
|
* |
| 208 |
|
* Empirically, microbenchmarks suggest that this class adds about |
| 209 |
|
* 40% overhead relative to ConcurrentLinkedQueue, which feels as |
| 472 |
|
(isFirst ? activePred.prev == null : activePred.item != null) && |
| 473 |
|
(isLast ? activeSucc.next == null : activeSucc.item != null)) { |
| 474 |
|
|
| 475 |
< |
// Ensure x is not reachable from head or tail |
| 476 |
< |
updateHead(); |
| 472 |
< |
updateTail(); |
| 475 |
> |
updateHead(); // Ensure x is not reachable from head |
| 476 |
> |
updateTail(); // Ensure x is not reachable from tail |
| 477 |
|
|
| 478 |
|
// Finally, actually gc-unlink |
| 479 |
|
x.lazySetPrev(isFirst ? prevTerminator() : x); |
| 497 |
|
(p.next == null || p.item != null) && |
| 498 |
|
p.prev == first) { |
| 499 |
|
|
| 500 |
< |
updateHead(); |
| 501 |
< |
updateTail(); |
| 500 |
> |
updateHead(); // Ensure o is not reachable from head |
| 501 |
> |
updateTail(); // Ensure o is not reachable from tail |
| 502 |
> |
|
| 503 |
> |
// Finally, actually gc-unlink |
| 504 |
|
o.lazySetNext(o); |
| 505 |
|
o.lazySetPrev(prevTerminator()); |
| 506 |
|
} |
| 531 |
|
(p.prev == null || p.item != null) && |
| 532 |
|
p.next == last) { |
| 533 |
|
|
| 534 |
< |
updateHead(); |
| 535 |
< |
updateTail(); |
| 534 |
> |
updateHead(); // Ensure o is not reachable from head |
| 535 |
> |
updateTail(); // Ensure o is not reachable from tail |
| 536 |
> |
|
| 537 |
> |
// Finally, actually gc-unlink |
| 538 |
|
o.lazySetPrev(o); |
| 539 |
|
o.lazySetNext(nextTerminator()); |
| 540 |
|
} |
