124 |
|
* |
125 |
|
* We introduce here an approach that lies between the extremes of |
126 |
|
* never versus always updating queue (head and tail) pointers |
127 |
< |
* that reflects the tradeoff of sometimes require extra traversal |
127 |
> |
* that reflects the tradeoff of sometimes requiring extra traversal |
128 |
|
* steps to locate the first and/or last unmatched nodes, versus |
129 |
|
* the reduced overhead and contention of fewer updates to queue |
130 |
|
* pointers. For example, a possible snapshot of a queue is: |
180 |
|
* (Similar issues arise in non-GC environments.) To cope with |
181 |
|
* this in our implementation, upon CASing to advance the head |
182 |
|
* pointer, we set the "next" link of the previous head to point |
183 |
< |
* only to itself; thus limiting the length connected dead lists. |
183 |
> |
* only to itself; thus limiting the length of connected dead lists. |
184 |
|
* (We also take similar care to wipe out possibly garbage |
185 |
|
* retaining values held in other Node fields.) However, doing so |
186 |
|
* adds some further complexity to traversal: If any "next" |
270 |
|
* safely jump to a node on the list by continuing the |
271 |
|
* traversal at current head. |
272 |
|
* |
273 |
< |
* On successful append, if the call was ASYNC, return |
273 |
> |
* On successful append, if the call was ASYNC, return. |
274 |
|
* |
275 |
|
* 3. Await match or cancellation (method awaitMatch) |
276 |
|
* |
322 |
|
private static final int CHAINED_SPINS = FRONT_SPINS >>> 2; |
323 |
|
|
324 |
|
/** |
325 |
< |
* Queue nodes. Uses Object, not E for items to allow forgetting |
325 |
> |
* Queue nodes. Uses Object, not E, for items to allow forgetting |
326 |
|
* them after use. Relies heavily on Unsafe mechanics to minimize |
327 |
< |
* unecessary ordering constraints: Writes that intrinsically |
327 |
> |
* unnecessary ordering constraints: Writes that intrinsically |
328 |
|
* precede or follow CASes use simple relaxed forms. Other |
329 |
|
* cleanups use releasing/lazy writes. |
330 |
|
*/ |
331 |
|
static final class Node { |
332 |
|
final boolean isData; // false if this is a request node |
333 |
< |
volatile Object item; // initially nonnull if isData; CASed to match |
333 |
> |
volatile Object item; // initially non-null if isData; CASed to match |
334 |
|
volatile Node next; |
335 |
|
volatile Thread waiter; // null until waiting |
336 |
|
|
344 |
|
} |
345 |
|
|
346 |
|
/** |
347 |
< |
* Create a new node. Uses relaxed write because item can only |
348 |
< |
* be seen if followed by CAS |
347 |
> |
* Creates a new node. Uses relaxed write because item can only |
348 |
> |
* be seen if followed by CAS. |
349 |
|
*/ |
350 |
|
Node(Object item, boolean isData) { |
351 |
|
UNSAFE.putObject(this, itemOffset, item); // relaxed write |
391 |
|
} |
392 |
|
|
393 |
|
/** |
394 |
< |
* Tries to artifically match a data node -- used by remove. |
394 |
> |
* Tries to artificially match a data node -- used by remove. |
395 |
|
*/ |
396 |
|
final boolean tryMatchData() { |
397 |
|
Object x = item; |
449 |
|
* Implements all queuing methods. See above for explanation. |
450 |
|
* |
451 |
|
* @param e the item or null for take |
452 |
< |
* @param haveData true if this is a put else a take |
452 |
> |
* @param haveData true if this is a put, else a take |
453 |
|
* @param how NOW, ASYNC, SYNC, or TIMEOUT |
454 |
|
* @param nanos timeout in nanosecs, used only if mode is TIMEOUT |
455 |
< |
* @return an item if matched, else e; |
455 |
> |
* @return an item if matched, else e |
456 |
|
* @throws NullPointerException if haveData mode but e is null |
457 |
|
*/ |
458 |
|
private Object xfer(Object e, boolean haveData, int how, long nanos) { |
487 |
|
} |
488 |
|
} |
489 |
|
Node n = p.next; |
490 |
< |
p = p != n ? n : (h = head); // Use head if p offlist |
490 |
> |
p = (p != n) ? n : (h = head); // Use head if p offlist |
491 |
|
} |
492 |
|
|
493 |
|
if (how >= ASYNC) { // No matches available |
504 |
|
} |
505 |
|
|
506 |
|
/** |
507 |
< |
* Tries to append node s as tail |
507 |
> |
* Tries to append node s as tail. |
508 |
> |
* |
509 |
|
* @param haveData true if appending in data mode |
510 |
|
* @param s the node to append |
511 |
|
* @return null on failure due to losing race with append in |
523 |
|
return null; // lost race vs opposite mode |
524 |
|
else if ((n = p.next) != null) // Not tail; keep traversing |
525 |
|
p = p != t && t != (u = tail) ? (t = u) : // stale tail |
526 |
< |
p != n ? n : null; // restart if off list |
526 |
> |
(p != n) ? n : null; // restart if off list |
527 |
|
else if (!p.casNext(null, s)) |
528 |
|
p = p.next; // re-read on CAS failure |
529 |
|
else { |
594 |
|
} |
595 |
|
|
596 |
|
/** |
597 |
< |
* Return spin/yield value for a node with given predecessor and |
597 |
> |
* Returns spin/yield value for a node with given predecessor and |
598 |
|
* data mode. See above for explanation. |
599 |
|
*/ |
600 |
|
private static int spinsFor(Node pred, boolean haveData) { |
634 |
|
/* -------------- Traversal methods -------------- */ |
635 |
|
|
636 |
|
/** |
637 |
< |
* Return the first unmatched node of the given mode, or null if |
637 |
> |
* Returns the first unmatched node of the given mode, or null if |
638 |
|
* none. Used by methods isEmpty, hasWaitingConsumer. |
639 |
|
*/ |
640 |
|
private Node firstOfMode(boolean data) { |
641 |
|
for (Node p = head; p != null; ) { |
642 |
|
if (!p.isMatched()) |
643 |
< |
return p.isData == data? p : null; |
643 |
> |
return (p.isData == data) ? p : null; |
644 |
|
Node n = p.next; |
645 |
< |
p = n != p ? n : head; |
645 |
> |
p = (n != p) ? n : head; |
646 |
|
} |
647 |
|
return null; |
648 |
|
} |
658 |
|
if (item != p && (item != null) == isData) |
659 |
|
return isData ? item : null; |
660 |
|
Node n = p.next; |
661 |
< |
p = n != p ? n : head; |
661 |
> |
p = (n != p) ? n : head; |
662 |
|
} |
663 |
|
return null; |
664 |
|
} |
665 |
|
|
666 |
|
/** |
667 |
< |
* Traverse and count nodes of the given mode. |
668 |
< |
* Used by methds size and getWaitingConsumerCount. |
667 |
> |
* Traverses and counts unmatched nodes of the given mode. |
668 |
> |
* Used by methods size and getWaitingConsumerCount. |
669 |
|
*/ |
670 |
|
private int countOfMode(boolean data) { |
671 |
|
int count = 0; |
712 |
|
else if (item == null) |
713 |
|
break; |
714 |
|
Node n = p.next; |
715 |
< |
p = n != p ? n : head; |
715 |
> |
p = (n != p) ? n : head; |
716 |
|
} |
717 |
|
nextNode = null; |
718 |
|
} |
763 |
|
*/ |
764 |
|
if (pred != null && pred != s) { |
765 |
|
while (pred.next == s) { |
766 |
< |
Node oldpred = cleanMe == null? null : reclean(); |
766 |
> |
Node oldpred = (cleanMe == null) ? null : reclean(); |
767 |
|
Node n = s.next; |
768 |
|
if (n != null) { |
769 |
|
if (n != s) |
1125 |
|
} |
1126 |
|
|
1127 |
|
/** |
1128 |
< |
* Save the state to a stream (that is, serialize it). |
1128 |
> |
* Saves the state to a stream (that is, serializes it). |
1129 |
|
* |
1130 |
|
* @serialData All of the elements (each an {@code E}) in |
1131 |
|
* the proper order, followed by a null |
1141 |
|
} |
1142 |
|
|
1143 |
|
/** |
1144 |
< |
* Reconstitute the Queue instance from a stream (that is, |
1145 |
< |
* deserialize it). |
1144 |
> |
* Reconstitutes the Queue instance from a stream (that is, |
1145 |
> |
* deserializes it). |
1146 |
|
* |
1147 |
|
* @param s the stream |
1148 |
|
*/ |