ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentLinkedDeque.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentLinkedDeque.java (file contents):
Revision 1.2 by jsr166, Thu May 20 18:48:50 2010 UTC vs.
Revision 1.3 by jsr166, Wed Aug 25 21:40:03 2010 UTC

#	Line 16 | Line 16 | import java.util.NoSuchElementException;
16		import java.util.concurrent.atomic.AtomicReference;
17
18		/**
19	<	* A concurrent linked-list implementation of a {@link Deque}
20	<	* (double-ended queue).  Concurrent insertion, removal, and access
21	<	* operations execute safely across multiple threads. Iterators are
22	<	* <i>weakly consistent</i>, returning elements reflecting the state
23	<	* of the deque at some point at or since the creation of the
24	<	* iterator.  They do <em>not</em> throw {@link
19	>	* An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
20	>	* Concurrent insertion, removal, and access operations execute safely
21	>	* across multiple threads.
22	>	* A {@code ConcurrentLinkedDeque} is an appropriate choice when
23	>	* many threads will share access to a common collection.
24	>	* Like most other concurrent collection implementations, this class
25	>	* does not permit the use of {@code null} elements.
26	>	*
27	>	* <p>Iterators are <i>weakly consistent</i>, returning elements
28	>	* reflecting the state of the deque at some point at or since the
29	>	* creation of the iterator.  They do <em>not</em> throw {@link
30	>	* java.util.ConcurrentModificationException
31		* ConcurrentModificationException}, and may proceed concurrently with
32		* other operations.
33		*
34	<	* <p>This class and its iterators implement all of the
29	<	* <em>optional</em> methods of the {@link Collection} and {@link
30	<	* Iterator} interfaces. Like most other concurrent collection
31	<	* implementations, this class does not permit the use of
32	<	* {@code null} elements.  because some null arguments and return
33	<	* values cannot be reliably distinguished from the absence of
34	<	* elements. Arbitrarily, the {@link Collection#remove} method is
35	<	* mapped to {@code removeFirstOccurrence}, and {@link
36	<	* Collection#add} is mapped to {@code addLast}.
37	<	*
38	<	* <p>Beware that, unlike in most collections, the {@link #size}
34	>	* <p>Beware that, unlike in most collections, the {@code size}
35		* method is <em>NOT</em> a constant-time operation. Because of the
36		* asynchronous nature of these deques, determining the current number
37	<	* of elements requires traversing them all to count them.
38	<	* Additionally, it is possible for the size to change during
39	<	* execution of this method, in which case the returned result will be
40	<	* inaccurate. Thus, this method is typically not very useful in
45	<	* concurrent applications.
37	>	* of elements requires a traversal of the elements.
38	>	*
39	>	* <p>This class and its iterator implement all of the <em>optional</em>
40	>	* methods of the {@link Deque} and {@link Iterator} interfaces.
41		*
42	<	* <p>This class is {@code Serializable}, but relies on default
43	<	* serialization mechanisms.  Usually, it is a better idea for any
44	<	* serializable class using a {@code ConcurrentLinkedDeque} to instead
45	<	* serialize a snapshot of the elements obtained by method
46	<	* {@code toArray}.
42	>	* <p>Memory consistency effects: As with other concurrent collections,
43	>	* actions in a thread prior to placing an object into a
44	>	* {@code ConcurrentLinkedDeque}
45	>	* <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
46	>	* actions subsequent to the access or removal of that element from
47	>	* the {@code ConcurrentLinkedDeque} in another thread.
48		*
49	<	* @author  Doug Lea
50	<	* @author  Martin Buchholz
49	>	* <p>This class is a member of the
50	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
51	>	* Java Collections Framework</a>.
52	>	*
53	>	* @since 1.7
54	>	* @author Doug Lea
55	>	* @author Martin Buchholz
56		* @param <E> the type of elements held in this collection
57		*/
58
#	Line 62 | Line 63 | public class ConcurrentLinkedDeque<E>
63		/*
64		* This is an implementation of a concurrent lock-free deque
65		* supporting interior removes but not interior insertions, as
66	<	* required to fully support the Deque interface.
66	>	* required to support the entire Deque interface.
67	>	*
68	>	* We extend the techniques developed for ConcurrentLinkedQueue and
69	>	* LinkedTransferQueue (see the internal docs for those classes).
70	>	*
71	>	* The data structure is a symmetrical doubly-linked "GC-robust"
72	>	* linked list of nodes.  We minimize the number of volatile writes
73	>	* using two techniques: advancing multiple hops with a single CAS
74	>	* and mixing volatile and non-volatile writes of the same memory
75	>	* locations.
76	>	*
77	>	* A node contains the expected E ("item") and links to predecessor
78	>	* ("prev") and successor ("next") nodes:
79	>	*
80	>	* class Node<E> { volatile Node<E> prev, next; volatile E item; }
81	>	*
82	>	* A node p is considered "live" if it contains a non-null item
83	>	* (p.item != null).  When an item is CASed to null, the item is
84	>	* atomically logically deleted from the collection.
85	>	*
86	>	* At any time, there is precisely one "first" node with a null
87	>	* prev reference that terminates any chain of prev references
88	>	* starting at a live node.  Similarly there is precisely one
89	>	* "last" node terminating any chain of next references starting at
90	>	* a live node.  The "first" and "last" nodes may or may not be live.
91	>	* The "first" and "last" nodes are always mutually reachable.
92	>	*
93	>	* A new element is added atomically by CASing the null prev or
94	>	* next reference in the first or last node to a fresh node
95	>	* containing the element.
96	>	*
97	>	* A node is considered "active" if it is a live node, or the
98	>	* first or last node.  Active nodes cannot be unlinked.
99	>	*
100	>	* A "self-link" is a next or prev reference that is the same node:
101	>	*   p.prev == p  or  p.next == p
102	>	* Self-links are used in the node unlinking process.  Active nodes
103	>	* never have self-links.
104		*
105	<	* We extend the techniques developed for
68	<	* ConcurrentLinkedQueue and LinkedTransferQueue
69	<	* (see the internal docs for those classes).
70	<	*
71	<	* At any time, there is precisely one "first" active node with a
72	<	* null prev pointer.  Similarly there is one "last" active node
73	<	* with a null next pointer.  New nodes are simply enqueued by
74	<	* null-CASing.
75	<	*
76	<	* A node p is considered "active" if it either contains an
77	<	* element, or is an end node and neither next nor prev pointers
78	<	* are self-links:
105	>	* A node p is active if and only if:
106		*
107		* p.item != null ||
108		* (p.prev == null && p.next != p) ||
109		* (p.next == null && p.prev != p)
110		*
111	<	* The head and tail pointers are only approximations to the start
112	<	* and end of the deque.  The first node can always be found by
111	>	* The deque object has two node references, "head" and "tail".
112	>	* The head and tail are only approximations to the first and last
113	>	* nodes of the deque.  The first node can always be found by
114		* following prev pointers from head; likewise for tail.  However,
115	<	* head and tail may be pointing at deleted nodes that have been
116	<	* unlinked and so may not be reachable from any live node.
117	<	*
118	<	* There are 3 levels of node deletion:
119	<	* - logical deletion atomically removes the element
120	<	* - "unlinking" makes a deleted node unreachable from active
121	<	*   nodes, and thus eventually reclaimable by GC
122	<	* - "gc-unlinking" further does the reverse of making active
123	<	*   nodes unreachable from deleted nodes, making it easier for
124	<	*   the GC to reclaim future deleted nodes
125	<	*
126	<	* TODO: find a better name for "gc-unlinked"
127	<	*
128	<	* Logical deletion of a node simply involves CASing its element
129	<	* to null.  Physical deletion is merely an optimization (albeit a
130	<	* critical one), and can be performed at our convenience.  At any
131	<	* time, the set of non-logically-deleted nodes maintained by prev
132	<	* and next links are identical, that is the live elements found
133	<	* via next links from the first node is equal to the elements
134	<	* found via prev links from the last node.  However, this is not
135	<	* true for nodes that have already been logically deleted - such
136	<	* nodes may only be reachable in one direction.
137	<	*
138	<	* When a node is dequeued at either end, e.g. via poll(), we
139	<	* would like to break any references from the node to live nodes,
140	<	* to stop old garbage from causing retention of new garbage with
141	<	* a generational or conservative GC.  We develop further the
142	<	* self-linking trick that was very effective in other concurrent
143	<	* collection classes.  The idea is to replace prev and next
144	<	* pointers to active nodes with special values that are
145	<	* interpreted to mean off-the-list-at-one-end.  These are
146	<	* approximations, but good enough to preserve the properties we
147	<	* want in our traversals, e.g. we guarantee that a traversal will
148	<	* never hit the same element twice, but we don't guarantee
149	<	* whether a traversal that runs out of elements will be able to
150	<	* see more elements later after more elements are added at that
151	<	* end.  Doing gc-unlinking safely is particularly tricky, since
152	<	* any node can be in use indefinitely (for example by an
153	<	* iterator).  We must make sure that the nodes pointed at by
154	<	* head/tail do not get gc-unlinked, since head/tail are needed to
155	<	* get "back on track" by other nodes that are gc-unlinked.
156	<	* gc-unlinking accounts for much of the implementation complexity.
115	>	* it is permissible for head and tail to be referring to deleted
116	>	* nodes that have been unlinked and so may not be reachable from
117	>	* any live node.
118	>	*
119	>	* There are 3 stages of node deletion;
120	>	* "logical deletion", "unlinking", and "gc-unlinking".
121	>	*
122	>	* 1. "logical deletion" by CASing item to null atomically removes
123	>	* the element from the collection, and makes the containing node
124	>	* eligible for unlinking.
125	>	*
126	>	* 2. "unlinking" makes a deleted node unreachable from active
127	>	* nodes, and thus eventually reclaimable by GC.  Unlinked nodes
128	>	* may remain reachable indefinitely from an iterator.
129	>	*
130	>	* Physical node unlinking is merely an optimization (albeit a
131	>	* critical one), and so can be performed at our convenience.  At
132	>	* any time, the set of live nodes maintained by prev and next
133	>	* links are identical, that is, the live nodes found via next
134	>	* links from the first node is equal to the elements found via
135	>	* prev links from the last node.  However, this is not true for
136	>	* nodes that have already been logically deleted - such nodes may
137	>	* be reachable in one direction only.
138	>	*
139	>	* 3. "gc-unlinking" takes unlinking further by making active
140	>	* nodes unreachable from deleted nodes, making it easier for the
141	>	* GC to reclaim future deleted nodes.  This step makes the data
142	>	* structure "gc-robust", as first described in detail by Boehm
143	>	* (http://portal.acm.org/citation.cfm?doid=503272.503282).
144	>	*
145	>	* GC-unlinked nodes may remain reachable indefinitely from an
146	>	* iterator, but unlike unlinked nodes, are never reachable from
147	>	* head or tail.
148	>	*
149	>	* Making the data structure GC-robust will eliminate the risk of
150	>	* unbounded memory retention with conservative GCs and is likely
151	>	* to improve performance with generational GCs.
152	>	*
153	>	* When a node is dequeued at either end, e.g. via poll(), we would
154	>	* like to break any references from the node to active nodes.  We
155	>	* develop further the use of self-links that was very effective in
156	>	* other concurrent collection classes.  The idea is to replace
157	>	* prev and next pointers with special values that are interpreted
158	>	* to mean off-the-list-at-one-end.  These are approximations, but
159	>	* good enough to preserve the properties we want in our
160	>	* traversals, e.g. we guarantee that a traversal will never visit
161	>	* the same element twice, but we don't guarantee whether a
162	>	* traversal that runs out of elements will be able to see more
163	>	* elements later after enqueues at that end.  Doing gc-unlinking
164	>	* safely is particularly tricky, since any node can be in use
165	>	* indefinitely (for example by an iterator).  We must ensure that
166	>	* the nodes pointed at by head/tail never get gc-unlinked, since
167	>	* head/tail are needed to get "back on track" by other nodes that
168	>	* are gc-unlinked.  gc-unlinking accounts for much of the
169	>	* implementation complexity.
170		*
171		* Since neither unlinking nor gc-unlinking are necessary for
172		* correctness, there are many implementation choices regarding
#	Line 137 | Line 178 | public class ConcurrentLinkedDeque<E>
178		* are occasionally broken.
179		*
180		* The actual representation we use is that p.next == p means to
181	<	* goto the first node, and p.next == null && p.prev == p means
181	>	* goto the first node (which in turn is reached by following prev
182	>	* pointers from head), and p.next == null && p.prev == p means
183		* that the iteration is at an end and that p is a (final static)
184		* dummy node, NEXT_TERMINATOR, and not the last active node.
185		* Finishing the iteration when encountering such a TERMINATOR is
186	<	* good enough for read-only traversals.  When the last active
187	<	* node is desired, for example when enqueueing, goto tail and
188	<	* continue traversal.
186	>	* good enough for read-only traversals, so such traversals can use
187	>	* p.next == null as the termination condition.  When we need to
188	>	* find the last (active) node, for enqueueing a new node, we need
189	>	* to check whether we have reached a TERMINATOR node; if so,
190	>	* restart traversal from tail.
191		*
192		* The implementation is completely directionally symmetrical,
193		* except that most public methods that iterate through the list
#	Line 161 | Line 205 | public class ConcurrentLinkedDeque<E>
205		* good as we can hope for.
206		*/
207
208	+	private static final long serialVersionUID = 876323262645176354L;
209	+
210		/**
211	<	* A node from which the first node on list (that is, the unique
212	<	* node with node.prev == null) can be reached in O(1) time.
211	>	* A node from which the first node on list (that is, the unique node p
212	>	* with p.prev == null && p.next != p) can be reached in O(1) time.
213		* Invariants:
214		* - the first node is always O(1) reachable from head via prev links
215		* - all live nodes are reachable from the first node via succ()
216		* - head != null
217		* - (tmp = head).next != tmp || tmp != head
218	+	* - head is never gc-unlinked (but may be unlinked)
219		* Non-invariants:
220		* - head.item may or may not be null
221		* - head may not be reachable from the first or last node, or from tail
222		*/
223	<	private transient volatile Node<E> head = new Node<E>(null);
223	>	private transient volatile Node<E> head;
224	>
225	>	/**
226	>	* A node from which the last node on list (that is, the unique node p
227	>	* with p.next == null && p.prev != p) can be reached in O(1) time.
228	>	* Invariants:
229	>	* - the last node is always O(1) reachable from tail via next links
230	>	* - all live nodes are reachable from the last node via pred()
231	>	* - tail != null
232	>	* - tail is never gc-unlinked (but may be unlinked)
233	>	* Non-invariants:
234	>	* - tail.item may or may not be null
235	>	* - tail may not be reachable from the first or last node, or from head
236	>	*/
237	>	private transient volatile Node<E> tail;
238
239		private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
240
#	Line 194 | Line 255 | public class ConcurrentLinkedDeque<E>
255		return (Node<E>) NEXT_TERMINATOR;
256		}
257
197	–	/**
198	–	* A node from which the last node on list (that is, the unique
199	–	* node with node.next == null) can be reached in O(1) time.
200	–	* Invariants:
201	–	* - the last node is always O(1) reachable from tail via next links
202	–	* - all live nodes are reachable from the last node via pred()
203	–	* - tail != null
204	–	* Non-invariants:
205	–	* - tail.item may or may not be null
206	–	* - tail may not be reachable from the first or last node, or from head
207	–	*/
208	–	private transient volatile Node<E> tail = head;
209	–
258		static final class Node<E> {
259		volatile Node<E> prev;
260		volatile E item;
#	Line 265 | Line 313 | public class ConcurrentLinkedDeque<E>
313		for (Node<E> h = head, p = h;;) {
314		Node<E> q = p.prev;
315		if (q == null) {
316	<	if (p.next == p)
316	>	if (p.next == p) // PREV_TERMINATOR
317		continue retry;
318	+	// p is first node
319		newNode.lazySetNext(p); // CAS piggyback
320		if (p.casPrev(null, newNode)) {
321		if (p != h) // hop two nodes at a time
#	Line 296 | Line 345 | public class ConcurrentLinkedDeque<E>
345		for (Node<E> t = tail, p = t;;) {
346		Node<E> q = p.next;
347		if (q == null) {
348	<	if (p.prev == p)
348	>	if (p.prev == p) // NEXT_TERMINATOR
349		continue retry;
350	+	// p is last node
351		newNode.lazySetPrev(p); // CAS piggyback
352		if (p.casNext(null, newNode)) {
353		if (p != t) // hop two nodes at a time
#	Line 315 | Line 365 | public class ConcurrentLinkedDeque<E>
365		}
366		}
367
318	–	// TODO: Is there a better cheap way of performing some cleanup
319	–	// operation "occasionally"?
320	–	static class Count {
321	–	int count = 0;
322	–	}
323	–	private final static ThreadLocal<Count> tlc =
324	–	new ThreadLocal<Count>() {
325	–	protected Count initialValue() { return new Count(); }
326	–	};
327	–	private static boolean shouldGCUnlinkOccasionally() {
328	–	return (tlc.get().count++ & 0x3) == 0;
329	–	}
330	–
368		private final static int HOPS = 2;
369
370		/**
371		* Unlinks non-null node x.
372		*/
373		void unlink(Node<E> x) {
374	<	assert x != null;
375	<	assert x.item == null;
376	<	assert x != PREV_TERMINATOR;
377	<	assert x != NEXT_TERMINATOR;
374	>	// assert x != null;
375	>	// assert x.item == null;
376	>	// assert x != PREV_TERMINATOR;
377	>	// assert x != NEXT_TERMINATOR;
378
379		final Node<E> prev = x.prev;
380		final Node<E> next = x.next;
#	Line 350 | Line 387 | public class ConcurrentLinkedDeque<E>
387		//
388		// This is the common case, since a series of polls at the
389		// same end will be "interior" removes, except perhaps for
390	<	// the first one, since end nodes cannot be physically removed.
390	>	// the first one, since end nodes cannot be unlinked.
391		//
392		// At any time, all active nodes are mutually reachable by
393		// following a sequence of either next or prev pointers.
#	Line 359 | Line 396 | public class ConcurrentLinkedDeque<E>
396		// and successor of x.  Try to fix up their links so that
397		// they point to each other, leaving x unreachable from
398		// active nodes.  If successful, and if x has no live
399	<	// predecessor/successor, we additionally try to leave
400	<	// active nodes unreachable from x, by rechecking that
401	<	// the status of predecessor and successor are unchanged
402	<	// and ensuring that x is not reachable from tail/head,
403	<	// before setting x's prev/next links to their logical
404	<	// approximate replacements, self/TERMINATOR.
399	>	// predecessor/successor, we additionally try to gc-unlink,
400	>	// leaving active nodes unreachable from x, by rechecking
401	>	// that the status of predecessor and successor are
402	>	// unchanged and ensuring that x is not reachable from
403	>	// tail/head, before setting x's prev/next links to their
404	>	// logical approximate replacements, self/TERMINATOR.
405		Node<E> activePred, activeSucc;
406		boolean isFirst, isLast;
407		int hops = 1;
408
409		// Find active predecessor
410	<	for (Node<E> p = prev;; ++hops) {
410	>	for (Node<E> p = prev; ; ++hops) {
411		if (p.item != null) {
412		activePred = p;
413		isFirst = false;
#	Line 378 | Line 415 | public class ConcurrentLinkedDeque<E>
415		}
416		Node<E> q = p.prev;
417		if (q == null) {
418	<	if (p == p.next)
418	>	if (p.next == p)
419		return;
420		activePred = p;
421		isFirst = true;
#	Line 391 | Line 428 | public class ConcurrentLinkedDeque<E>
428		}
429
430		// Find active successor
431	<	for (Node<E> p = next;; ++hops) {
431	>	for (Node<E> p = next; ; ++hops) {
432		if (p.item != null) {
433		activeSucc = p;
434		isLast = false;
#	Line 399 | Line 436 | public class ConcurrentLinkedDeque<E>
436		}
437		Node<E> q = p.next;
438		if (q == null) {
439	<	if (p == p.prev)
439	>	if (p.prev == p)
440		return;
441		activeSucc = p;
442		isLast = true;
#	Line 424 | Line 461 | public class ConcurrentLinkedDeque<E>
461
462		// Try to gc-unlink, if possible
463		if ((isFirst | isLast) &&
427	–	//shouldGCUnlinkOccasionally() &&
464
465		// Recheck expected state of predecessor and successor
466		(activePred.next == activeSucc) &&
#	Line 435 | Line 471 | public class ConcurrentLinkedDeque<E>
471		// Ensure x is not reachable from head or tail
472		updateHead();
473		updateTail();
474	+
475	+	// Finally, actually gc-unlink
476		x.lazySetPrev(isFirst ? prevTerminator() : x);
477		x.lazySetNext(isLast  ? nextTerminator() : x);
478		}
#	Line 445 | Line 483 | public class ConcurrentLinkedDeque<E>
483		* Unlinks non-null first node.
484		*/
485		private void unlinkFirst(Node<E> first, Node<E> next) {
486	<	assert first != null && next != null && first.item == null;
486	>	// assert first != null && next != null && first.item == null;
487		Node<E> o = null, p = next;
488	<	for (int hops = 0;; ++hops) {
488	>	for (int hops = 0; ; ++hops) {
489		Node<E> q;
490		if (p.item != null || (q = p.next) == null) {
491	<	if (hops >= HOPS) {
492	<	if (p == p.prev)
493	<	return;
494	<	if (first.casNext(next, p)) {
495	<	skipDeletedPredecessors(p);
496	<	if (//shouldGCUnlinkOccasionally() &&
497	<	first.prev == null &&
498	<	(p.next == null || p.item != null) &&
499	<	p.prev == first) {
500	<
463	<	updateHead();
464	<	updateTail();
465	<	o.lazySetNext(o);
466	<	o.lazySetPrev(prevTerminator());
467	<	}
491	>	if (hops >= HOPS && p.prev != p && first.casNext(next, p)) {
492	>	skipDeletedPredecessors(p);
493	>	if (first.prev == null &&
494	>	(p.next == null || p.item != null) &&
495	>	p.prev == first) {
496	>
497	>	updateHead();
498	>	updateTail();
499	>	o.lazySetNext(o);
500	>	o.lazySetPrev(prevTerminator());
501		}
502		}
503		return;
#	Line 482 | Line 515 | public class ConcurrentLinkedDeque<E>
515		* Unlinks non-null last node.
516		*/
517		private void unlinkLast(Node<E> last, Node<E> prev) {
518	<	assert last != null && prev != null && last.item == null;
518	>	// assert last != null && prev != null && last.item == null;
519		Node<E> o = null, p = prev;
520	<	for (int hops = 0;; ++hops) {
520	>	for (int hops = 0; ; ++hops) {
521		Node<E> q;
522		if (p.item != null || (q = p.prev) == null) {
523	<	if (hops >= HOPS) {
524	<	if (p == p.next)
525	<	return;
526	<	if (last.casPrev(prev, p)) {
527	<	skipDeletedSuccessors(p);
528	<	if (//shouldGCUnlinkOccasionally() &&
529	<	last.next == null &&
530	<	(p.prev == null || p.item != null) &&
531	<	p.next == last) {
532	<
500	<	updateHead();
501	<	updateTail();
502	<	o.lazySetPrev(o);
503	<	o.lazySetNext(nextTerminator());
504	<	}
523	>	if (hops >= HOPS && p.next != p && last.casPrev(prev, p)) {
524	>	skipDeletedSuccessors(p);
525	>	if (last.next == null &&
526	>	(p.prev == null || p.item != null) &&
527	>	p.next == last) {
528	>
529	>	updateHead();
530	>	updateTail();
531	>	o.lazySetPrev(o);
532	>	o.lazySetNext(nextTerminator());
533		}
534		}
535		return;
#	Line 515 | Line 543 | public class ConcurrentLinkedDeque<E>
543		}
544		}
545
546	+	/**
547	+	* Sets head to first node.  Guarantees that any node which was
548	+	* unlinked before a call to this method will be unreachable from
549	+	* head after it returns.
550	+	*/
551		private final void updateHead() {
552		first();
553		}
554
555	+	/**
556	+	* Sets tail to last node.  Guarantees that any node which was
557	+	* unlinked before a call to this method will be unreachable from
558	+	* tail after it returns.
559	+	*/
560		private final void updateTail() {
561		last();
562		}
#	Line 527 | Line 565 | public class ConcurrentLinkedDeque<E>
565		whileActive:
566		do {
567		Node<E> prev = x.prev;
568	<	assert prev != null;
569	<	assert x != NEXT_TERMINATOR;
570	<	assert x != PREV_TERMINATOR;
568	>	// assert prev != null;
569	>	// assert x != NEXT_TERMINATOR;
570	>	// assert x != PREV_TERMINATOR;
571		Node<E> p = prev;
572		findActive:
573		for (;;) {
#	Line 558 | Line 596 | public class ConcurrentLinkedDeque<E>
596		whileActive:
597		do {
598		Node<E> next = x.next;
599	<	assert next != null;
600	<	assert x != NEXT_TERMINATOR;
601	<	assert x != PREV_TERMINATOR;
599	>	// assert next != null;
600	>	// assert x != NEXT_TERMINATOR;
601	>	// assert x != PREV_TERMINATOR;
602		Node<E> p = next;
603		findActive:
604		for (;;) {
#	Line 607 | Line 645 | public class ConcurrentLinkedDeque<E>
645		}
646
647		/**
648	<	* Returns the first node, the unique node which has a null prev link.
648	>	* Returns the first node, the unique node p for which:
649	>	*     p.prev == null && p.next != p
650		* The returned node may or may not be logically deleted.
651		* Guarantees that head is set to the returned node.
652		*/
#	Line 619 | Line 658 | public class ConcurrentLinkedDeque<E>
658		if (q == null) {
659		if (p == h
660		// It is possible that p is PREV_TERMINATOR,
661	<	// but if so, the CAS will fail.
661	>	// but if so, the CAS is guaranteed to fail.
662		|| casHead(h, p))
663		return p;
664		else
#	Line 634 | Line 673 | public class ConcurrentLinkedDeque<E>
673		}
674
675		/**
676	<	* Returns the last node, the unique node which has a null next link.
676	>	* Returns the last node, the unique node p for which:
677	>	*     p.next == null && p.prev != p
678		* The returned node may or may not be logically deleted.
679		* Guarantees that tail is set to the returned node.
680		*/
#	Line 646 | Line 686 | public class ConcurrentLinkedDeque<E>
686		if (q == null) {
687		if (p == t
688		// It is possible that p is NEXT_TERMINATOR,
689	<	// but if so, the CAS will fail.
689	>	// but if so, the CAS is guaranteed to fail.
690		|| casTail(t, p))
691		return p;
692		else
#	Line 692 | Line 732 | public class ConcurrentLinkedDeque<E>
732		* @return the arrayList
733		*/
734		private ArrayList<E> toArrayList() {
735	<	ArrayList<E> c = new ArrayList<E>();
735	>	ArrayList<E> list = new ArrayList<E>();
736		for (Node<E> p = first(); p != null; p = succ(p)) {
737		E item = p.item;
738		if (item != null)
739	<	c.add(item);
739	>	list.add(item);
740		}
741	<	return c;
741	>	return list;
742		}
743
704	–	// Fields and constructors
705	–
706	–	private static final long serialVersionUID = 876323262645176354L;
707	–
744		/**
745		* Constructs an empty deque.
746		*/
747	<	public ConcurrentLinkedDeque() {}
747	>	public ConcurrentLinkedDeque() {
748	>	head = tail = new Node<E>(null);
749	>	}
750
751		/**
752		* Constructs a deque initially containing the elements of
#	Line 719 | Line 757 | public class ConcurrentLinkedDeque<E>
757		* @throws NullPointerException if the specified collection or any
758		*         of its elements are null
759		*/
760	<	public ConcurrentLinkedDeque(Collection<? extends E> c) {
761	<	this();
762	<	addAll(c);
763	<	}
760	>	public ConcurrentLinkedDeque(Collection<? extends E> c) {
761	>	// Copy c into a private chain of Nodes
762	>	Node<E> h = null, t = null;
763	>	for (E e : c) {
764	>	checkNotNull(e);
765	>	Node<E> newNode = new Node<E>(e);
766	>	if (h == null)
767	>	h = t = newNode;
768	>	else {
769	>	t.next = newNode;
770	>	newNode.prev = t;
771	>	t = newNode;
772	>	}
773	>	}
774	>	if (h == null)
775	>	h = t = new Node<E>(null);
776	>	head = h;
777	>	tail = t;
778	>	}
779
780		/**
781		* Inserts the specified element at the front of this deque.
#	Line 735 | Line 788 | public class ConcurrentLinkedDeque<E>
788
789		/**
790		* Inserts the specified element at the end of this deque.
791	<	* This is identical in function to the {@code add} method.
791	>	*
792	>	* <p>This method is equivalent to {@link #add}.
793		*
794		* @throws NullPointerException {@inheritDoc}
795		*/
#	Line 972 | Line 1026 | public class ConcurrentLinkedDeque<E>
1026		/**
1027		* Appends all of the elements in the specified collection to the end of
1028		* this deque, in the order that they are returned by the specified
1029	<	* collection's iterator.  The behavior of this operation is undefined if
1030	<	* the specified collection is modified while the operation is in
977	<	* progress.  (This implies that the behavior of this call is undefined if
978	<	* the specified Collection is this deque, and this deque is nonempty.)
1029	>	* collection's iterator.  Attempts to {@code addAll} of a deque to
1030	>	* itself result in {@code IllegalArgumentException}.
1031		*
1032		* @param c the elements to be inserted into this deque
1033		* @return {@code true} if this deque changed as a result of the call
1034	<	* @throws NullPointerException if {@code c} or any element within it
1035	<	* is {@code null}
1034	>	* @throws NullPointerException if the specified collection or any
1035	>	*         of its elements are null
1036	>	* @throws IllegalArgumentException if the collection is this deque
1037		*/
1038		public boolean addAll(Collection<? extends E> c) {
1039	<	Iterator<? extends E> it = c.iterator();
1040	<	if (!it.hasNext())
1039	>	if (c == this)
1040	>	// As historically specified in AbstractQueue#addAll
1041	>	throw new IllegalArgumentException();
1042	>
1043	>	// Copy c into a private chain of Nodes
1044	>	Node<E> splice = null, last = null;
1045	>	for (E e : c) {
1046	>	checkNotNull(e);
1047	>	Node<E> newNode = new Node<E>(e);
1048	>	if (splice == null)
1049	>	splice = last = newNode;
1050	>	else {
1051	>	last.next = newNode;
1052	>	newNode.prev = last;
1053	>	last = newNode;
1054	>	}
1055	>	}
1056	>	if (splice == null)
1057		return false;
1058	<	do {
1059	<	addLast(it.next());
1060	<	} while (it.hasNext());
1061	<	return true;
1058	>
1059	>	// Atomically splice the chain as the tail of this collection
1060	>	retry:
1061	>	for (;;) {
1062	>	for (Node<E> t = tail, p = t;;) {
1063	>	Node<E> q = p.next;
1064	>	if (q == null) {
1065	>	if (p.prev == p) // NEXT_TERMINATOR
1066	>	continue retry;
1067	>	// p is last node
1068	>	splice.lazySetPrev(p); // CAS piggyback
1069	>	if (p.casNext(null, splice)) {
1070	>	if (! casTail(t, last)) {
1071	>	// Try a little harder to update tail,
1072	>	// since we may be adding many elements.
1073	>	t = tail;
1074	>	if (last.next == null)
1075	>	casTail(t, last);
1076	>	}
1077	>	return true;
1078	>	} else {
1079	>	p = p.next; // lost CAS race to another thread
1080	>	}
1081	>	}
1082	>	else if (p == q)
1083	>	continue retry;
1084	>	else
1085	>	p = q;
1086	>	}
1087	>	}
1088		}
1089
1090		/**
#	Line 1030 | Line 1125 | public class ConcurrentLinkedDeque<E>
1125		* the array immediately following the end of the deque is set to
1126		* {@code null}.
1127		*
1128	<	* <p>Like the {@link #toArray()} method, this method acts as bridge between
1129	<	* array-based and collection-based APIs.  Further, this method allows
1130	<	* precise control over the runtime type of the output array, and may,
1131	<	* under certain circumstances, be used to save allocation costs.
1128	>	* <p>Like the {@link #toArray()} method, this method acts as
1129	>	* bridge between array-based and collection-based APIs.  Further,
1130	>	* this method allows precise control over the runtime type of the
1131	>	* output array, and may, under certain circumstances, be used to
1132	>	* save allocation costs.
1133		*
1134		* <p>Suppose {@code x} is a deque known to contain only strings.
1135		* The following code can be used to dump the deque into a newly
#	Line 1086 | Line 1182 | public class ConcurrentLinkedDeque<E>
1182		* and guarantees to traverse elements as they existed upon
1183		* construction of the iterator, and may (but is not guaranteed to)
1184		* reflect any modifications subsequent to construction.
1185	+	*
1186	+	* @return an iterator over the elements in this deque in reverse order
1187		*/
1188		public Iterator<E> descendingIterator() {
1189		return new DescendingItr();
#	Line 1175 | Line 1273 | public class ConcurrentLinkedDeque<E>
1273		}
1274
1275		/**
1276	<	* Save the state to a stream (that is, serialize it).
1276	>	* Saves the state to a stream (that is, serializes it).
1277		*
1278		* @serialData All of the elements (each an {@code E}) in
1279		* the proper order, followed by a null
#	Line 1199 | Line 1297 | public class ConcurrentLinkedDeque<E>
1297		}
1298
1299		/**
1300	<	* Reconstitute the Queue instance from a stream (that is,
1203	<	* deserialize it).
1300	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1301		* @param s the stream
1302		*/
1303		private void readObject(java.io.ObjectInputStream s)
1304		throws java.io.IOException, ClassNotFoundException {
1208	–	// Read in capacity, and any hidden stuff
1305		s.defaultReadObject();
1306	<	tail = head = new Node<E>(null);
1307	<	// Read in all elements and place in queue
1308	<	for (;;) {
1306	>
1307	>	// Read in elements until trailing null sentinel found
1308	>	Node<E> h = null, t = null;
1309	>	Object item;
1310	>	while ((item = s.readObject()) != null) {
1311		@SuppressWarnings("unchecked")
1312	<	E item = (E)s.readObject();
1313	<	if (item == null)
1314	<	break;
1315	<	else
1316	<	offer(item);
1312	>	Node<E> newNode = new Node<E>((E) item);
1313	>	if (h == null)
1314	>	h = t = newNode;
1315	>	else {
1316	>	t.next = newNode;
1317	>	newNode.prev = t;
1318	>	t = newNode;
1319	>	}
1320		}
1321	+	if (h == null)
1322	+	h = t = new Node<E>(null);
1323	+	head = h;
1324	+	tail = t;
1325		}
1326
1327		// Unsafe mechanics

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines