ViewVC Help

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

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

Comparing jsr166/src/main/java/util/concurrent/LinkedBlockingDeque.java (file contents):
Revision 1.20 by dl, Sun Feb 15 23:41:38 2009 UTC vs.
Revision 1.21 by jsr166, Wed Jul 29 18:13:43 2009 UTC

#	Line 5 | Line 5
5		*/
6
7		package java.util.concurrent;
8	<	import java.util.*;
9	<	import java.util.concurrent.locks.*;
8	>
9	>	import java.util.AbstractQueue;
10	>	import java.util.Collection;
11	>	import java.util.Iterator;
12	>	import java.util.NoSuchElementException;
13	>	import java.util.concurrent.locks.Condition;
14	>	import java.util.concurrent.locks.ReentrantLock;
15
16		/**
17		* An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
#	Line 44 | Line 49 | public class LinkedBlockingDeque<E>
49		/*
50		* Implemented as a simple doubly-linked list protected by a
51		* single lock and using conditions to manage blocking.
52	+	*
53	+	* To implement weakly consistent iterators, it appears we need to
54	+	* keep all Nodes GC-reachable from a predecessor dequeued Node.
55	+	* That would cause two problems:
56	+	* - allow a rogue Iterator to cause unbounded memory retention
57	+	* - cause cross-generational linking of old Nodes to new Nodes if
58	+	*   a Node was tenured while live, which generational GCs have a
59	+	*   hard time dealing with, causing repeated major collections.
60	+	* However, only non-deleted Nodes need to be reachable from
61	+	* dequeued Nodes, and reachability does not necessarily have to
62	+	* be of the kind understood by the GC.  We use the trick of
63	+	* linking a Node that has just been dequeued to itself.  Such a
64	+	* self-link implicitly means to jump to "first" (for next links)
65	+	* or "last" (for prev links).
66		*/
67
68		/*
#	Line 57 | Line 76 | public class LinkedBlockingDeque<E>
76
77		/** Doubly-linked list node class */
78		static final class Node<E> {
79	+	/**
80	+	* The item, or null if this node has been removed.
81	+	*/
82		E item;
83	+
84	+	/**
85	+	* One of:
86	+	* - the real predecessor Node
87	+	* - this Node, meaning the predecessor is tail
88	+	* - null, meaning there is no predecessor
89	+	*/
90		Node<E> prev;
91	+
92	+	/**
93	+	* One of:
94	+	* - the real successor Node
95	+	* - this Node, meaning the successor is head
96	+	* - null, meaning there is no successor
97	+	*/
98		Node<E> next;
99	+
100		Node(E x, Node<E> p, Node<E> n) {
101		item = x;
102		prev = p;
#	Line 67 | Line 104 | public class LinkedBlockingDeque<E>
104		}
105		}
106
107	<	/** Pointer to first node */
108	<	private transient Node<E> first;
109	<	/** Pointer to last node */
110	<	private transient Node<E> last;
107	>	/**
108	>	* Pointer to first node.
109	>	* Invariant: (first == null && last == null) ||
110	>	*            (first.prev == null && first.item != null)
111	>	*/
112	>	transient Node<E> first;
113	>
114	>	/**
115	>	* Pointer to last node.
116	>	* Invariant: (first == null && last == null) ||
117	>	*            (last.next == null && last.item != null)
118	>	*/
119	>	transient Node<E> last;
120	>
121		/** Number of items in the deque */
122		private transient int count;
123	+
124		/** Maximum number of items in the deque */
125		private final int capacity;
126	+
127		/** Main lock guarding all access */
128	<	private final ReentrantLock lock = new ReentrantLock();
128	>	final ReentrantLock lock = new ReentrantLock();
129	>
130		/** Condition for waiting takes */
131		private final Condition notEmpty = lock.newCondition();
132	+
133		/** Condition for waiting puts */
134		private final Condition notFull = lock.newCondition();
135
136		/**
137	<	* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
137	>	* Creates a {@code LinkedBlockingDeque} with a capacity of
138		* {@link Integer#MAX_VALUE}.
139		*/
140		public LinkedBlockingDeque() {
#	Line 91 | Line 142 | public class LinkedBlockingDeque<E>
142		}
143
144		/**
145	<	* Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.
145	>	* Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
146		*
147		* @param capacity the capacity of this deque
148	<	* @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
148	>	* @throws IllegalArgumentException if {@code capacity} is less than 1
149		*/
150		public LinkedBlockingDeque(int capacity) {
151		if (capacity <= 0) throw new IllegalArgumentException();
#	Line 102 | Line 153 | public class LinkedBlockingDeque<E>
153		}
154
155		/**
156	<	* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
156	>	* Creates a {@code LinkedBlockingDeque} with a capacity of
157		* {@link Integer#MAX_VALUE}, initially containing the elements of
158		* the given collection, added in traversal order of the
159		* collection's iterator.
#	Line 113 | Line 164 | public class LinkedBlockingDeque<E>
164		*/
165		public LinkedBlockingDeque(Collection<? extends E> c) {
166		this(Integer.MAX_VALUE);
167	<	for (E e : c)
168	<	add(e);
167	>	final ReentrantLock lock = this.lock;
168	>	lock.lock(); // Never contended, but necessary for visibility
169	>	try {
170	>	for (E e : c) {
171	>	if (e == null)
172	>	throw new NullPointerException();
173	>	if (!linkLast(e))
174	>	throw new IllegalStateException("Deque full");
175	>	}
176	>	} finally {
177	>	lock.unlock();
178	>	}
179		}
180
181
#	Line 124 | Line 185 | public class LinkedBlockingDeque<E>
185		* Links e as first element, or returns false if full.
186		*/
187		private boolean linkFirst(E e) {
188	+	// assert lock.isHeldByCurrentThread();
189		if (count >= capacity)
190		return false;
129	–	++count;
191		Node<E> f = first;
192		Node<E> x = new Node<E>(e, null, f);
193		first = x;
#	Line 134 | Line 195 | public class LinkedBlockingDeque<E>
195		last = x;
196		else
197		f.prev = x;
198	+	++count;
199		notEmpty.signal();
200		return true;
201		}
#	Line 142 | Line 204 | public class LinkedBlockingDeque<E>
204		* Links e as last element, or returns false if full.
205		*/
206		private boolean linkLast(E e) {
207	+	// assert lock.isHeldByCurrentThread();
208		if (count >= capacity)
209		return false;
147	–	++count;
210		Node<E> l = last;
211		Node<E> x = new Node<E>(e, l, null);
212		last = x;
#	Line 152 | Line 214 | public class LinkedBlockingDeque<E>
214		first = x;
215		else
216		l.next = x;
217	+	++count;
218		notEmpty.signal();
219		return true;
220		}
#	Line 160 | Line 223 | public class LinkedBlockingDeque<E>
223		* Removes and returns first element, or null if empty.
224		*/
225		private E unlinkFirst() {
226	+	// assert lock.isHeldByCurrentThread();
227		Node<E> f = first;
228		if (f == null)
229		return null;
230		Node<E> n = f.next;
231	<	f.next = null; // help GC
231	>	E item = f.item;
232	>	f.item = null;
233	>	f.next = f; // help GC
234		first = n;
235		if (n == null)
236		last = null;
#	Line 172 | Line 238 | public class LinkedBlockingDeque<E>
238		n.prev = null;
239		--count;
240		notFull.signal();
241	<	return f.item;
241	>	return item;
242		}
243
244		/**
245		* Removes and returns last element, or null if empty.
246		*/
247		private E unlinkLast() {
248	+	// assert lock.isHeldByCurrentThread();
249		Node<E> l = last;
250		if (l == null)
251		return null;
252		Node<E> p = l.prev;
253	<	l.prev = null; // help GC
253	>	E item = l.item;
254	>	l.item = null;
255	>	l.prev = l; // help GC
256		last = p;
257		if (p == null)
258		first = null;
#	Line 191 | Line 260 | public class LinkedBlockingDeque<E>
260		p.next = null;
261		--count;
262		notFull.signal();
263	<	return l.item;
263	>	return item;
264		}
265
266		/**
267	<	* Unlink e
267	>	* Unlinks x.
268		*/
269	<	private void unlink(Node<E> x) {
269	>	void unlink(Node<E> x) {
270	>	// assert lock.isHeldByCurrentThread();
271		Node<E> p = x.prev;
272		Node<E> n = x.next;
273		if (p == null) {
274	<	if (n == null)
205	<	first = last = null;
206	<	else {
207	<	n.prev = null;
208	<	first = n;
209	<	}
274	>	unlinkFirst();
275		} else if (n == null) {
276	<	p.next = null;
212	<	last = p;
276	>	unlinkLast();
277		} else {
278		p.next = n;
279		n.prev = p;
280	+	x.item = null;
281	+	// Don't mess with x's links.  They may still be in use by
282	+	// an iterator.
283	+	--count;
284	+	notFull.signal();
285		}
217	–	--count;
218	–	notFull.signalAll();
286		}
287
288		// BlockingDeque methods
#	Line 243 | Line 310 | public class LinkedBlockingDeque<E>
310		*/
311		public boolean offerFirst(E e) {
312		if (e == null) throw new NullPointerException();
313	+	final ReentrantLock lock = this.lock;
314		lock.lock();
315		try {
316		return linkFirst(e);
#	Line 256 | Line 324 | public class LinkedBlockingDeque<E>
324		*/
325		public boolean offerLast(E e) {
326		if (e == null) throw new NullPointerException();
327	+	final ReentrantLock lock = this.lock;
328		lock.lock();
329		try {
330		return linkLast(e);
#	Line 270 | Line 339 | public class LinkedBlockingDeque<E>
339		*/
340		public void putFirst(E e) throws InterruptedException {
341		if (e == null) throw new NullPointerException();
342	+	final ReentrantLock lock = this.lock;
343		lock.lock();
344		try {
345		while (!linkFirst(e))
#	Line 285 | Line 355 | public class LinkedBlockingDeque<E>
355		*/
356		public void putLast(E e) throws InterruptedException {
357		if (e == null) throw new NullPointerException();
358	+	final ReentrantLock lock = this.lock;
359		lock.lock();
360		try {
361		while (!linkLast(e))
#	Line 302 | Line 373 | public class LinkedBlockingDeque<E>
373		throws InterruptedException {
374		if (e == null) throw new NullPointerException();
375		long nanos = unit.toNanos(timeout);
376	+	final ReentrantLock lock = this.lock;
377		lock.lockInterruptibly();
378		try {
379	<	for (;;) {
308	<	if (linkFirst(e))
309	<	return true;
379	>	while (!linkFirst(e)) {
380		if (nanos <= 0)
381		return false;
382		nanos = notFull.awaitNanos(nanos);
383		}
384	+	return true;
385		} finally {
386		lock.unlock();
387		}
#	Line 324 | Line 395 | public class LinkedBlockingDeque<E>
395		throws InterruptedException {
396		if (e == null) throw new NullPointerException();
397		long nanos = unit.toNanos(timeout);
398	+	final ReentrantLock lock = this.lock;
399		lock.lockInterruptibly();
400		try {
401	<	for (;;) {
330	<	if (linkLast(e))
331	<	return true;
401	>	while (!linkLast(e)) {
402		if (nanos <= 0)
403		return false;
404		nanos = notFull.awaitNanos(nanos);
405		}
406	+	return true;
407		} finally {
408		lock.unlock();
409		}
#	Line 357 | Line 428 | public class LinkedBlockingDeque<E>
428		}
429
430		public E pollFirst() {
431	+	final ReentrantLock lock = this.lock;
432		lock.lock();
433		try {
434		return unlinkFirst();
#	Line 366 | Line 438 | public class LinkedBlockingDeque<E>
438		}
439
440		public E pollLast() {
441	+	final ReentrantLock lock = this.lock;
442		lock.lock();
443		try {
444		return unlinkLast();
#	Line 375 | Line 448 | public class LinkedBlockingDeque<E>
448		}
449
450		public E takeFirst() throws InterruptedException {
451	+	final ReentrantLock lock = this.lock;
452		lock.lock();
453		try {
454		E x;
#	Line 387 | Line 461 | public class LinkedBlockingDeque<E>
461		}
462
463		public E takeLast() throws InterruptedException {
464	+	final ReentrantLock lock = this.lock;
465		lock.lock();
466		try {
467		E x;
#	Line 401 | Line 476 | public class LinkedBlockingDeque<E>
476		public E pollFirst(long timeout, TimeUnit unit)
477		throws InterruptedException {
478		long nanos = unit.toNanos(timeout);
479	+	final ReentrantLock lock = this.lock;
480		lock.lockInterruptibly();
481		try {
482	<	for (;;) {
483	<	E x = unlinkFirst();
408	<	if (x != null)
409	<	return x;
482	>	E x;
483	>	while ( (x = unlinkFirst()) == null) {
484		if (nanos <= 0)
485		return null;
486		nanos = notEmpty.awaitNanos(nanos);
487		}
488	+	return x;
489		} finally {
490		lock.unlock();
491		}
#	Line 419 | Line 494 | public class LinkedBlockingDeque<E>
494		public E pollLast(long timeout, TimeUnit unit)
495		throws InterruptedException {
496		long nanos = unit.toNanos(timeout);
497	+	final ReentrantLock lock = this.lock;
498		lock.lockInterruptibly();
499		try {
500	<	for (;;) {
501	<	E x = unlinkLast();
426	<	if (x != null)
427	<	return x;
500	>	E x;
501	>	while ( (x = unlinkLast()) == null) {
502		if (nanos <= 0)
503		return null;
504		nanos = notEmpty.awaitNanos(nanos);
505		}
506	+	return x;
507		} finally {
508		lock.unlock();
509		}
#	Line 453 | Line 528 | public class LinkedBlockingDeque<E>
528		}
529
530		public E peekFirst() {
531	+	final ReentrantLock lock = this.lock;
532		lock.lock();
533		try {
534		return (first == null) ? null : first.item;
#	Line 462 | Line 538 | public class LinkedBlockingDeque<E>
538		}
539
540		public E peekLast() {
541	+	final ReentrantLock lock = this.lock;
542		lock.lock();
543		try {
544		return (last == null) ? null : last.item;
#	Line 472 | Line 549 | public class LinkedBlockingDeque<E>
549
550		public boolean removeFirstOccurrence(Object o) {
551		if (o == null) return false;
552	+	final ReentrantLock lock = this.lock;
553		lock.lock();
554		try {
555		for (Node<E> p = first; p != null; p = p.next) {
#	Line 488 | Line 566 | public class LinkedBlockingDeque<E>
566
567		public boolean removeLastOccurrence(Object o) {
568		if (o == null) return false;
569	+	final ReentrantLock lock = this.lock;
570		lock.lock();
571		try {
572		for (Node<E> p = last; p != null; p = p.prev) {
#	Line 592 | Line 671 | public class LinkedBlockingDeque<E>
671		* Returns the number of additional elements that this deque can ideally
672		* (in the absence of memory or resource constraints) accept without
673		* blocking. This is always equal to the initial capacity of this deque
674	<	* less the current <tt>size</tt> of this deque.
674	>	* less the current {@code size} of this deque.
675		*
676		* <p>Note that you <em>cannot</em> always tell if an attempt to insert
677	<	* an element will succeed by inspecting <tt>remainingCapacity</tt>
677	>	* an element will succeed by inspecting {@code remainingCapacity}
678		* because it may be the case that another thread is about to
679		* insert or remove an element.
680		*/
681		public int remainingCapacity() {
682	+	final ReentrantLock lock = this.lock;
683		lock.lock();
684		try {
685		return capacity - count;
#	Line 615 | Line 695 | public class LinkedBlockingDeque<E>
695		* @throws IllegalArgumentException      {@inheritDoc}
696		*/
697		public int drainTo(Collection<? super E> c) {
698	<	if (c == null)
619	<	throw new NullPointerException();
620	<	if (c == this)
621	<	throw new IllegalArgumentException();
622	<	lock.lock();
623	<	try {
624	<	for (Node<E> p = first; p != null; p = p.next)
625	<	c.add(p.item);
626	<	int n = count;
627	<	count = 0;
628	<	first = last = null;
629	<	notFull.signalAll();
630	<	return n;
631	<	} finally {
632	<	lock.unlock();
633	<	}
698	>	return drainTo(c, Integer.MAX_VALUE);
699		}
700
701		/**
#	Line 644 | Line 709 | public class LinkedBlockingDeque<E>
709		throw new NullPointerException();
710		if (c == this)
711		throw new IllegalArgumentException();
712	+	final ReentrantLock lock = this.lock;
713		lock.lock();
714		try {
715	<	int n = 0;
716	<	while (n < maxElements && first != null) {
717	<	c.add(first.item);
718	<	first.prev = null;
653	<	first = first.next;
654	<	--count;
655	<	++n;
715	>	int n = Math.min(maxElements, count);
716	>	for (int i = 0; i < n; i++) {
717	>	c.add(first.item);   // In this order, in case add() throws.
718	>	unlinkFirst();
719		}
657	–	if (first == null)
658	–	last = null;
659	–	notFull.signalAll();
720		return n;
721		} finally {
722		lock.unlock();
#	Line 685 | Line 745 | public class LinkedBlockingDeque<E>
745		/**
746		* Removes the first occurrence of the specified element from this deque.
747		* If the deque does not contain the element, it is unchanged.
748	<	* More formally, removes the first element <tt>e</tt> such that
749	<	* <tt>o.equals(e)</tt> (if such an element exists).
750	<	* Returns <tt>true</tt> if this deque contained the specified element
748	>	* More formally, removes the first element {@code e} such that
749	>	* {@code o.equals(e)} (if such an element exists).
750	>	* Returns {@code true} if this deque contained the specified element
751		* (or equivalently, if this deque changed as a result of the call).
752		*
753		* <p>This method is equivalent to
754		* {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
755		*
756		* @param o element to be removed from this deque, if present
757	<	* @return <tt>true</tt> if this deque changed as a result of the call
757	>	* @return {@code true} if this deque changed as a result of the call
758		*/
759		public boolean remove(Object o) {
760		return removeFirstOccurrence(o);
#	Line 706 | Line 766 | public class LinkedBlockingDeque<E>
766		* @return the number of elements in this deque
767		*/
768		public int size() {
769	+	final ReentrantLock lock = this.lock;
770		lock.lock();
771		try {
772		return count;
#	Line 715 | Line 776 | public class LinkedBlockingDeque<E>
776		}
777
778		/**
779	<	* Returns <tt>true</tt> if this deque contains the specified element.
780	<	* More formally, returns <tt>true</tt> if and only if this deque contains
781	<	* at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
779	>	* Returns {@code true} if this deque contains the specified element.
780	>	* More formally, returns {@code true} if and only if this deque contains
781	>	* at least one element {@code e} such that {@code o.equals(e)}.
782		*
783		* @param o object to be checked for containment in this deque
784	<	* @return <tt>true</tt> if this deque contains the specified element
784	>	* @return {@code true} if this deque contains the specified element
785		*/
786		public boolean contains(Object o) {
787		if (o == null) return false;
788	+	final ReentrantLock lock = this.lock;
789		lock.lock();
790		try {
791		for (Node<E> p = first; p != null; p = p.next)
#	Line 735 | Line 797 | public class LinkedBlockingDeque<E>
797		}
798		}
799
800	<	/**
801	<	* Variant of removeFirstOccurrence needed by iterator.remove.
802	<	* Searches for the node, not its contents.
803	<	*/
804	<	boolean removeNode(Node<E> e) {
805	<	lock.lock();
806	<	try {
807	<	for (Node<E> p = first; p != null; p = p.next) {
808	<	if (p == e) {
809	<	unlink(p);
810	<	return true;
811	<	}
812	<	}
813	<	return false;
814	<	} finally {
815	<	lock.unlock();
816	<	}
817	<	}
800	>	/*
801	>	* TODO: Add support for more efficient bulk operations.
802	>	*
803	>	* We don't want to acquire the lock for every iteration, but we
804	>	* also want other threads a chance to interact with the
805	>	* collection, especially when count is close to capacity.
806	>	*/
807	>
808	>	//     /**
809	>	//      * Adds all of the elements in the specified collection to this
810	>	//      * queue.  Attempts to addAll of a queue to itself result in
811	>	//      * {@code IllegalArgumentException}. Further, the behavior of
812	>	//      * this operation is undefined if the specified collection is
813	>	//      * modified while the operation is in progress.
814	>	//      *
815	>	//      * @param c collection containing elements to be added to this queue
816	>	//      * @return {@code true} if this queue changed as a result of the call
817	>	//      * @throws ClassCastException            {@inheritDoc}
818	>	//      * @throws NullPointerException          {@inheritDoc}
819	>	//      * @throws IllegalArgumentException      {@inheritDoc}
820	>	//      * @throws IllegalStateException         {@inheritDoc}
821	>	//      * @see #add(Object)
822	>	//      */
823	>	//     public boolean addAll(Collection<? extends E> c) {
824	>	//         if (c == null)
825	>	//             throw new NullPointerException();
826	>	//         if (c == this)
827	>	//             throw new IllegalArgumentException();
828	>	//         final ReentrantLock lock = this.lock;
829	>	//         lock.lock();
830	>	//         try {
831	>	//             boolean modified = false;
832	>	//             for (E e : c)
833	>	//                 if (linkLast(e))
834	>	//                     modified = true;
835	>	//             return modified;
836	>	//         } finally {
837	>	//             lock.unlock();
838	>	//         }
839	>	//     }
840
841		/**
842		* Returns an array containing all of the elements in this deque, in
#	Line 767 | Line 851 | public class LinkedBlockingDeque<E>
851		*
852		* @return an array containing all of the elements in this deque
853		*/
854	+	@SuppressWarnings("unchecked")
855		public Object[] toArray() {
856	+	final ReentrantLock lock = this.lock;
857		lock.lock();
858		try {
859		Object[] a = new Object[count];
#	Line 790 | Line 876 | public class LinkedBlockingDeque<E>
876		* <p>If this deque fits in the specified array with room to spare
877		* (i.e., the array has more elements than this deque), the element in
878		* the array immediately following the end of the deque is set to
879	<	* <tt>null</tt>.
879	>	* {@code null}.
880		*
881		* <p>Like the {@link #toArray()} method, this method acts as bridge between
882		* array-based and collection-based APIs.  Further, this method allows
883		* precise control over the runtime type of the output array, and may,
884		* under certain circumstances, be used to save allocation costs.
885		*
886	<	* <p>Suppose <tt>x</tt> is a deque known to contain only strings.
886	>	* <p>Suppose {@code x} is a deque known to contain only strings.
887		* The following code can be used to dump the deque into a newly
888	<	* allocated array of <tt>String</tt>:
888	>	* allocated array of {@code String}:
889		*
890		* <pre>
891		*     String[] y = x.toArray(new String[0]);</pre>
892		*
893	<	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
894	<	* <tt>toArray()</tt>.
893	>	* Note that {@code toArray(new Object[0])} is identical in function to
894	>	* {@code toArray()}.
895		*
896		* @param a the array into which the elements of the deque are to
897		*          be stored, if it is big enough; otherwise, a new array of the
#	Line 816 | Line 902 | public class LinkedBlockingDeque<E>
902		*         this deque
903		* @throws NullPointerException if the specified array is null
904		*/
905	+	@SuppressWarnings("unchecked")
906		public <T> T[] toArray(T[] a) {
907	+	final ReentrantLock lock = this.lock;
908		lock.lock();
909		try {
910		if (a.length < count)
911	<	a = (T[])java.lang.reflect.Array.newInstance(
912	<	a.getClass().getComponentType(),
825	<	count
826	<	);
911	>	a = (T[])java.lang.reflect.Array.newInstance
912	>	(a.getClass().getComponentType(), count);
913
914		int k = 0;
915		for (Node<E> p = first; p != null; p = p.next)
#	Line 837 | Line 923 | public class LinkedBlockingDeque<E>
923		}
924
925		public String toString() {
926	+	final ReentrantLock lock = this.lock;
927		lock.lock();
928		try {
929		return super.toString();
#	Line 850 | Line 937 | public class LinkedBlockingDeque<E>
937		* The deque will be empty after this call returns.
938		*/
939		public void clear() {
940	+	final ReentrantLock lock = this.lock;
941		lock.lock();
942		try {
943	+	for (Node<E> f = first; f != null; ) {
944	+	f.item = null;
945	+	Node<E> n = f.next;
946	+	f.prev = null;
947	+	f.next = null;
948	+	f = n;
949	+	}
950		first = last = null;
951		count = 0;
952		notFull.signalAll();
#	Line 863 | Line 958 | public class LinkedBlockingDeque<E>
958		/**
959		* Returns an iterator over the elements in this deque in proper sequence.
960		* The elements will be returned in order from first (head) to last (tail).
961	<	* The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
961	>	* The returned {@code Iterator} is a "weakly consistent" iterator that
962		* will never throw {@link ConcurrentModificationException},
963		* and guarantees to traverse elements as they existed upon
964		* construction of the iterator, and may (but is not guaranteed to)
#	Line 879 | Line 974 | public class LinkedBlockingDeque<E>
974		* Returns an iterator over the elements in this deque in reverse
975		* sequential order.  The elements will be returned in order from
976		* last (tail) to first (head).
977	<	* The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
977	>	* The returned {@code Iterator} is a "weakly consistent" iterator that
978		* will never throw {@link ConcurrentModificationException},
979		* and guarantees to traverse elements as they existed upon
980		* construction of the iterator, and may (but is not guaranteed to)
#	Line 894 | Line 989 | public class LinkedBlockingDeque<E>
989		*/
990		private abstract class AbstractItr implements Iterator<E> {
991		/**
992	<	* The next node to return in next
992	>	* The next node to return in next()
993		*/
994		Node<E> next;
995
#	Line 912 | Line 1007 | public class LinkedBlockingDeque<E>
1007		*/
1008		private Node<E> lastRet;
1009
1010	+	abstract Node<E> firstNode();
1011	+	abstract Node<E> nextNode(Node<E> n);
1012	+
1013		AbstractItr() {
1014	<	advance(); // set to initial position
1014	>	// set to initial position
1015	>	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1016	>	lock.lock();
1017	>	try {
1018	>	next = firstNode();
1019	>	nextItem = (next == null) ? null : next.item;
1020	>	} finally {
1021	>	lock.unlock();
1022	>	}
1023		}
1024
1025		/**
1026	<	* Advances next, or if not yet initialized, sets to first node.
921	<	* Implemented to move forward vs backward in the two subclasses.
1026	>	* Advances next.
1027		*/
1028	<	abstract void advance();
1028	>	void advance() {
1029	>	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1030	>	lock.lock();
1031	>	try {
1032	>	// assert next != null;
1033	>	Node<E> s = nextNode(next);
1034	>	if (s == next) {
1035	>	next = firstNode();
1036	>	} else {
1037	>	// Skip over removed nodes.
1038	>	// May be necessary if multiple interior Nodes are removed.
1039	>	while (s != null && s.item == null)
1040	>	s = nextNode(s);
1041	>	next = s;
1042	>	}
1043	>	nextItem = (next == null) ? null : next.item;
1044	>	} finally {
1045	>	lock.unlock();
1046	>	}
1047	>	}
1048
1049		public boolean hasNext() {
1050		return next != null;
#	Line 940 | Line 1064 | public class LinkedBlockingDeque<E>
1064		if (n == null)
1065		throw new IllegalStateException();
1066		lastRet = null;
943	–	// Note: removeNode rescans looking for this node to make
944	–	// sure it was not already removed. Otherwise, trying to
945	–	// re-remove could corrupt list.
946	–	removeNode(n);
947	–	}
948	–	}
949	–
950	–	/** Forward iterator */
951	–	private class Itr extends AbstractItr {
952	–	void advance() {
1067		final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1068		lock.lock();
1069		try {
1070	<	next = (next == null)? first : next.next;
1071	<	nextItem = (next == null)? null : next.item;
1070	>	if (n.item != null)
1071	>	unlink(n);
1072		} finally {
1073		lock.unlock();
1074		}
1075		}
1076		}
1077
1078	<	/**
1079	<	* Descending iterator for LinkedBlockingDeque
1080	<	*/
1078	>	/** Forward iterator */
1079	>	private class Itr extends AbstractItr {
1080	>	Node<E> firstNode() { return first; }
1081	>	Node<E> nextNode(Node<E> n) { return n.next; }
1082	>	}
1083	>
1084	>	/** Descending iterator */
1085		private class DescendingItr extends AbstractItr {
1086	<	void advance() {
1087	<	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
970	<	lock.lock();
971	<	try {
972	<	next = (next == null)? last : next.prev;
973	<	nextItem = (next == null)? null : next.item;
974	<	} finally {
975	<	lock.unlock();
976	<	}
977	<	}
1086	>	Node<E> firstNode() { return last; }
1087	>	Node<E> nextNode(Node<E> n) { return n.prev; }
1088		}
1089
1090		/**
1091		* Save the state of this deque to a stream (that is, serialize it).
1092		*
1093		* @serialData The capacity (int), followed by elements (each an
1094	<	* <tt>Object</tt>) in the proper order, followed by a null
1094	>	* {@code Object}) in the proper order, followed by a null
1095		* @param s the stream
1096		*/
1097		private void writeObject(java.io.ObjectOutputStream s)
1098		throws java.io.IOException {
1099	+	final ReentrantLock lock = this.lock;
1100		lock.lock();
1101		try {
1102		// Write out capacity and any hidden stuff
#	Line 1013 | Line 1124 | public class LinkedBlockingDeque<E>
1124		last = null;
1125		// Read in all elements and place in queue
1126		for (;;) {
1127	+	@SuppressWarnings("unchecked")
1128		E item = (E)s.readObject();
1129		if (item == null)
1130		break;

Diff Legend

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