ViewVC Help

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

root/jsr166/jsr166/src/jsr166x/LinkedBlockingDeque.java

Comparing jsr166/src/jsr166x/LinkedBlockingDeque.java (file contents):
Revision 1.2 by dl, Sun Dec 26 20:13:15 2004 UTC vs.
Revision 1.15 by jsr166, Tue Feb 5 17:34:19 2013 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package jsr166x;
#	Line 14 | Line 14 | import java.util.concurrent.locks.*;
14		* An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
15		* linked nodes.
16		*
17	<	* <p> The optional capacity bound constructor argument serves as a
17	>	* <p>The optional capacity bound constructor argument serves as a
18		* way to prevent excessive expansion. The capacity, if unspecified,
19		* is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
20		* dynamically created upon each insertion unless this would bring the
#	Line 39 | Line 39 | import java.util.concurrent.locks.*;
39		*/
40		public class LinkedBlockingDeque<E>
41		extends AbstractQueue<E>
42	<	implements BlockingDeque<E>,  java.io.Serializable {
42	>	implements BlockingDeque<E>, java.io.Serializable {
43
44		/*
45		* Implemented as a simple doubly-linked list protected by a
#	Line 50 | Line 50 | public class LinkedBlockingDeque<E>
50
51		/** Doubly-linked list node class */
52		static final class Node<E> {
53	<	E item;
53	>	E item;
54		Node<E> prev;
55		Node<E> next;
56		Node(E x, Node<E> p, Node<E> n) {
#	Line 76 | Line 76 | public class LinkedBlockingDeque<E>
76		private final Condition notFull = lock.newCondition();
77
78		/**
79	<	* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
79	>	* Creates a {@code LinkedBlockingDeque} with a capacity of
80		* {@link Integer#MAX_VALUE}.
81		*/
82		public LinkedBlockingDeque() {
#	Line 84 | Line 84 | public class LinkedBlockingDeque<E>
84		}
85
86		/**
87	<	* Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed)
87	>	* Creates a {@code LinkedBlockingDeque} with the given (fixed)
88		* capacity.
89		* @param capacity the capacity of this deque
90	<	* @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
90	>	* @throws IllegalArgumentException if {@code capacity} is less than 1
91		*/
92		public LinkedBlockingDeque(int capacity) {
93		if (capacity <= 0) throw new IllegalArgumentException();
#	Line 95 | Line 95 | public class LinkedBlockingDeque<E>
95		}
96
97		/**
98	<	* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
98	>	* Creates a {@code LinkedBlockingDeque} with a capacity of
99		* {@link Integer#MAX_VALUE}, initially containing the elements of the
100		* given collection,
101		* added in traversal order of the collection's iterator.
102		* @param c the collection of elements to initially contain
103	<	* @throws NullPointerException if <tt>c</tt> or any element within it
104	<	* is <tt>null</tt>
103	>	* @throws NullPointerException if {@code c} or any element within it
104	>	* is {@code null}
105		*/
106		public LinkedBlockingDeque(Collection<? extends E> c) {
107		this(Integer.MAX_VALUE);
#	Line 113 | Line 113 | public class LinkedBlockingDeque<E>
113		// Basic linking and unlinking operations, called only while holding lock
114
115		/**
116	<	* Link e as first element, or return false if full
116	>	* Links e as first element, or returns false if full.
117		*/
118		private boolean linkFirst(E e) {
119		if (count >= capacity)
#	Line 131 | Line 131 | public class LinkedBlockingDeque<E>
131		}
132
133		/**
134	<	* Link e as last element, or return false if full
134	>	* Links e as last element, or returns false if full.
135		*/
136		private boolean linkLast(E e) {
137		if (count >= capacity)
#	Line 149 | Line 149 | public class LinkedBlockingDeque<E>
149		}
150
151		/**
152	<	* Remove and return first element, or null if empty
152	>	* Removes and returns first element, or null if empty.
153		*/
154		private E unlinkFirst() {
155		Node<E> f = first;
#	Line 157 | Line 157 | public class LinkedBlockingDeque<E>
157		return null;
158		Node<E> n = f.next;
159		first = n;
160	<	if (n == null)
160	>	if (n == null)
161		last = null;
162	<	else
162	>	else
163		n.prev = null;
164		--count;
165		notFull.signal();
#	Line 167 | Line 167 | public class LinkedBlockingDeque<E>
167		}
168
169		/**
170	<	* Remove and return last element, or null if empty
170	>	* Removes and returns last element, or null if empty.
171		*/
172		private E unlinkLast() {
173		Node<E> l = last;
#	Line 175 | Line 175 | public class LinkedBlockingDeque<E>
175		return null;
176		Node<E> p = l.prev;
177		last = p;
178	<	if (p == null)
178	>	if (p == null)
179		first = null;
180	<	else
180	>	else
181		p.next = null;
182		--count;
183		notFull.signal();
#	Line 191 | Line 191 | public class LinkedBlockingDeque<E>
191		Node<E> p = x.prev;
192		Node<E> n = x.next;
193		if (p == null) {
194	<	if (n == null)
194	>	if (n == null)
195		first = last = null;
196		else {
197		n.prev = null;
#	Line 230 | Line 230 | public class LinkedBlockingDeque<E>
230		}
231		}
232
233	<	public void addFirst(E e) {
233	>	public void addFirst(E e) {
234		if (!offerFirst(e))
235		throw new IllegalStateException("Deque full");
236		}
237
238	<	public void addLast(E e) {
238	>	public void addLast(E e) {
239		if (!offerLast(e))
240		throw new IllegalStateException("Deque full");
241		}
#	Line 365 | Line 365 | public class LinkedBlockingDeque<E>
365		lock.unlock();
366		}
367		}
368	<
368	>
369		public boolean offerLast(E o, long timeout, TimeUnit unit)
370		throws InterruptedException {
371		if (o == null) throw new NullPointerException();
#	Line 384 | Line 384 | public class LinkedBlockingDeque<E>
384		}
385		}
386
387	<	public E pollFirst(long timeout, TimeUnit unit)
387	>	public E pollFirst(long timeout, TimeUnit unit)
388		throws InterruptedException {
389		lock.lockInterruptibly();
390		try {
#	Line 402 | Line 402 | public class LinkedBlockingDeque<E>
402		}
403		}
404
405	<	public E pollLast(long timeout, TimeUnit unit)
405	>	public E pollLast(long timeout, TimeUnit unit)
406		throws InterruptedException {
407		lock.lockInterruptibly();
408		try {
#	Line 434 | Line 434 | public class LinkedBlockingDeque<E>
434
435		// BlockingQueue methods
436
437	<	public void put(E o) throws InterruptedException  { putLast(o);  }
438	<	public E take() throws InterruptedException       { return takeFirst(); }
437	>	public void put(E o) throws InterruptedException { putLast(o); }
438	>	public E take() throws InterruptedException      { return takeFirst(); }
439		public boolean offer(E o, long timeout, TimeUnit unit)
440		throws InterruptedException    { return offerLast(o, timeout, unit); }
441		public E poll(long timeout, TimeUnit unit)
#	Line 444 | Line 444 | public class LinkedBlockingDeque<E>
444		/**
445		* Returns the number of elements in this deque.
446		*
447	<	* @return  the number of elements in this deque.
447	>	* @return  the number of elements in this deque
448		*/
449		public int size() {
450		lock.lock();
#	Line 459 | Line 459 | public class LinkedBlockingDeque<E>
459		* Returns the number of elements that this deque can ideally (in
460		* the absence of memory or resource constraints) accept without
461		* blocking. This is always equal to the initial capacity of this deque
462	<	* less the current <tt>size</tt> of this deque.
462	>	* less the current {@code size} of this deque.
463		* <p>Note that you <em>cannot</em> always tell if
464	<	* an attempt to <tt>add</tt> an element will succeed by
465	<	* inspecting <tt>remainingCapacity</tt> because it may be the
466	<	* case that a waiting consumer is ready to <tt>take</tt> an
464	>	* an attempt to {@code add} an element will succeed by
465	>	* inspecting {@code remainingCapacity} because it may be the
466	>	* case that a waiting consumer is ready to {@code take} an
467		* element out of an otherwise full deque.
468		*/
469		public int remainingCapacity() {
#	Line 479 | Line 479 | public class LinkedBlockingDeque<E>
479		if (o == null) return false;
480		lock.lock();
481		try {
482	<	for (Node<E> p = first; p != null; p = p.next)
482	>	for (Node<E> p = first; p != null; p = p.next)
483		if (o.equals(p.item))
484		return true;
485		return false;
#	Line 524 | Line 524 | public class LinkedBlockingDeque<E>
524		* Variant of removeFirstOccurrence needed by iterator.remove.
525		* Searches for the node, not its contents.
526		*/
527	<	boolean removeNode(Node<E> e) {
527	>	boolean removeNode(Node<E> e) {
528		lock.lock();
529		try {
530		for (Node<E> p = first; p != null; p = p.next) {
#	Line 544 | Line 544 | public class LinkedBlockingDeque<E>
544		try {
545		Object[] a = new Object[count];
546		int k = 0;
547	<	for (Node<E> p = first; p != null; p = p.next)
547	>	for (Node<E> p = first; p != null; p = p.next)
548		a[k++] = p.item;
549		return a;
550		} finally {
#	Line 562 | Line 562 | public class LinkedBlockingDeque<E>
562		);
563
564		int k = 0;
565	<	for (Node<E> p = first; p != null; p = p.next)
565	>	for (Node<E> p = first; p != null; p = p.next)
566		a[k++] = (T)p.item;
567		if (a.length > k)
568		a[k] = null;
#	Line 603 | Line 603 | public class LinkedBlockingDeque<E>
603		throw new IllegalArgumentException();
604		lock.lock();
605		try {
606	<	for (Node<E> p = first; p != null; p = p.next)
606	>	for (Node<E> p = first; p != null; p = p.next)
607		c.add(p.item);
608		int n = count;
609		count = 0;
#	Line 641 | Line 641 | public class LinkedBlockingDeque<E>
641
642		/**
643		* Returns an iterator over the elements in this deque in proper sequence.
644	<	* The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
644	>	* The returned {@code Iterator} is a "weakly consistent" iterator that
645		* will never throw {@link java.util.ConcurrentModificationException},
646		* and guarantees to traverse elements as they existed upon
647		* construction of the iterator, and may (but is not guaranteed to)
648		* reflect any modifications subsequent to construction.
649		*
650	<	* @return an iterator over the elements in this deque in proper sequence.
650	>	* @return an iterator over the elements in this deque in proper sequence
651		*/
652		public Iterator<E> iterator() {
653		return new Itr();
#	Line 664 | Line 664 | public class LinkedBlockingDeque<E>
664		* an element exists in hasNext(), we must return item read
665		* under lock (in advance()) even if it was in the process of
666		* being removed when hasNext() was called.
667	<	**/
667	>	*/
668		private E nextItem;
669
670		/**
#	Line 680 | Line 680 | public class LinkedBlockingDeque<E>
680		/**
681		* Advance next, or if not yet initialized, set to first node.
682		*/
683	<	private void advance() {
683	>	private void advance() {
684		final ReentrantLock lock = LinkedBlockingDeque.this.lock;
685		lock.lock();
686		try {
687	<	next = (next == null)? first : next.next;
688	<	nextItem = (next == null)? null : next.item;
687	>	next = (next == null) ? first : next.next;
688	>	nextItem = (next == null) ? null : next.item;
689		} finally {
690		lock.unlock();
691		}
#	Line 717 | Line 717 | public class LinkedBlockingDeque<E>
717		}
718
719		/**
720	<	* Save the state to a stream (that is, serialize it).
720	>	* Saves the state to a stream (that is, serializes it).
721		*
722		* @serialData The capacity (int), followed by elements (each an
723	<	* <tt>Object</tt>) in the proper order, followed by a null
723	>	* {@code Object}) in the proper order, followed by a null
724		* @param s the stream
725		*/
726		private void writeObject(java.io.ObjectOutputStream s)
#	Line 740 | Line 740 | public class LinkedBlockingDeque<E>
740		}
741
742		/**
743	<	* Reconstitute this deque instance from a stream (that is,
744	<	* deserialize it).
743	>	* Reconstitutes this deque instance from a stream (that is,
744	>	* deserializes it).
745		* @param s the stream
746		*/
747		private void readObject(java.io.ObjectInputStream s)
#	Line 758 | Line 758 | public class LinkedBlockingDeque<E>
758		add(item);
759		}
760		}
761	<
761	>
762		}

Diff Legend

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