| 93 |
|
* in extending them for use in synchronous queues, as well as |
| 94 |
|
* dealing with cancellation. The main differences include: |
| 95 |
|
* |
| 96 |
< |
* 1. The orginal algorithms used bit-marked pointers, but |
| 96 |
> |
* 1. The original algorithms used bit-marked pointers, but |
| 97 |
|
* the ones here use mode bits in nodes, leading to a number |
| 98 |
|
* of further adaptations. |
| 99 |
|
* 2. SynchronousQueues must block threads waiting to become |
| 120 |
|
* |
| 121 |
|
* While garbage collection takes care of most node reclamation |
| 122 |
|
* issues that otherwise complicate nonblocking algorithms, care |
| 123 |
< |
* is made to "forget" references to data, other nodes, and |
| 123 |
> |
* is taken to "forget" references to data, other nodes, and |
| 124 |
|
* threads that might be held on to long-term by blocked |
| 125 |
|
* threads. In cases where setting to null would otherwise |
| 126 |
|
* conflict with main algorithms, this is done by changing a |
| 127 |
|
* node's link to now point to the node itself. This doesn't arise |
| 128 |
|
* much for Stack nodes (because blocked threads do not hang on to |
| 129 |
|
* old head pointers), but references in Queue nodes must be |
| 130 |
< |
* agressively forgotten to avoid reachability of everything any |
| 130 |
> |
* aggressively forgotten to avoid reachability of everything any |
| 131 |
|
* node has ever referred to since arrival. |
| 132 |
|
*/ |
| 133 |
|
|
| 136 |
|
*/ |
| 137 |
|
static abstract class Transferer { |
| 138 |
|
/** |
| 139 |
< |
* Perform a put or take. |
| 139 |
> |
* Performs a put or take. |
| 140 |
> |
* |
| 141 |
|
* @param e if non-null, the item to be handed to a consumer; |
| 142 |
< |
* if null, requests that transfer return an item offered by |
| 143 |
< |
* producer. |
| 142 |
> |
* if null, requests that transfer return an item |
| 143 |
> |
* offered by producer. |
| 144 |
|
* @param timed if this operation should timeout |
| 145 |
|
* @param nanos the timeout, in nanoseconds |
| 146 |
< |
* @return if nonnull, the item provided or received; if null, |
| 147 |
< |
* the operation failed due to timeout or interrupt -- the |
| 148 |
< |
* caller can distinguish which of these occurred by checking |
| 149 |
< |
* Thread.interrupted. |
| 146 |
> |
* @return if non-null, the item provided or received; if null, |
| 147 |
> |
* the operation failed due to timeout or interrupt -- |
| 148 |
> |
* the caller can distinguish which of these occurred |
| 149 |
> |
* by checking Thread.interrupted. |
| 150 |
|
*/ |
| 151 |
|
abstract Object transfer(Object e, boolean timed, long nanos); |
| 152 |
|
} |
| 227 |
|
(SNode.class, SNode.class, "match"); |
| 228 |
|
|
| 229 |
|
/** |
| 230 |
< |
* Try to match node s to this node, if so, waking up |
| 230 |
> |
* Tries to match node s to this node, if so, waking up |
| 231 |
|
* thread. Fulfillers call tryMatch to identify their |
| 232 |
|
* waiters. Waiters block until they have been |
| 233 |
|
* matched. |
| 248 |
|
} |
| 249 |
|
|
| 250 |
|
/** |
| 251 |
< |
* Try to cancel a wait by matching node to itself. |
| 251 |
> |
* Tries to cancel a wait by matching node to itself. |
| 252 |
|
*/ |
| 253 |
|
void tryCancel() { |
| 254 |
|
matchUpdater.compareAndSet(this, null, this); |
| 376 |
|
* When a node/thread is about to block, it sets its waiter |
| 377 |
|
* field and then rechecks state at least one more time |
| 378 |
|
* before actually parking, thus covering race vs |
| 379 |
< |
* fulfiller noticing that waiter is nonnull so should be |
| 379 |
> |
* fulfiller noticing that waiter is non-null so should be |
| 380 |
|
* woken. |
| 381 |
|
* |
| 382 |
|
* When invoked by nodes that appear at the point of call |
| 448 |
|
* it. But we can stop when we see any node known to |
| 449 |
|
* follow s. We use s.next unless it too is cancelled, in |
| 450 |
|
* which case we try the node one past. We don't check any |
| 451 |
< |
* futher because we don't want to doubly traverse just to |
| 451 |
> |
* further because we don't want to doubly traverse just to |
| 452 |
|
* find sentinel. |
| 453 |
|
*/ |
| 454 |
|
|
| 480 |
|
* marked pointers. The algorithm is a little simpler than |
| 481 |
|
* that for stacks because fulfillers do not need explicit |
| 482 |
|
* nodes, and matching is done by CAS'ing QNode.item field |
| 483 |
< |
* from nonnull to null (for put) or vice versa (for take). |
| 483 |
> |
* from non-null to null (for put) or vice versa (for take). |
| 484 |
|
*/ |
| 485 |
|
|
| 486 |
|
/** Node class for TransferQueue. */ |
| 514 |
|
} |
| 515 |
|
|
| 516 |
|
/** |
| 517 |
< |
* Try to cancel by CAS'ing ref to this as item. |
| 517 |
> |
* Tries to cancel by CAS'ing ref to this as item. |
| 518 |
|
*/ |
| 519 |
|
void tryCancel(Object cmp) { |
| 520 |
|
itemUpdater.compareAndSet(this, cmp, this); |
| 556 |
|
(TransferQueue.class, QNode.class, "head"); |
| 557 |
|
|
| 558 |
|
/** |
| 559 |
< |
* Tries to cas nh as new head; if successful unlink |
| 559 |
> |
* Tries to cas nh as new head; if successful, unlink |
| 560 |
|
* old head's next node to avoid garbage retention. |
| 561 |
|
*/ |
| 562 |
|
void advanceHead(QNode h, QNode nh) { |
| 623 |
|
for (;;) { |
| 624 |
|
QNode t = tail; |
| 625 |
|
QNode h = head; |
| 626 |
< |
if (t == null || h == null) // saw unitialized values |
| 626 |
> |
if (t == null || h == null) // saw uninitialized values |
| 627 |
|
continue; // spin |
| 628 |
|
|
| 629 |
|
if (h == t || t.isData == isData) { // empty or same-mode |
| 939 |
|
} |
| 940 |
|
|
| 941 |
|
/** |
| 942 |
< |
* Returns <tt>false</tt> unless given collection is empty. |
| 942 |
> |
* Returns <tt>false</tt> unless the given collection is empty. |
| 943 |
|
* A <tt>SynchronousQueue</tt> has no internal capacity. |
| 944 |
|
* @param c the collection |
| 945 |
|
* @return <tt>false</tt> unless given collection is empty |
