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
7 package java.util.concurrent;
9 import java.util.concurrent.locks.*;
12 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
15 * <p> The optional capacity bound constructor argument serves as a
16 * way to prevent excessive expansion. The capacity, if unspecified,
17 * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
18 * dynamically created upon each insertion unless this would bring the
19 * deque above capacity.
21 * <p>Most operations run in constant time (ignoring time spent
22 * blocking). Exceptions include {@link #remove(Object) remove},
23 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
24 * #removeLastOccurrence removeLastOccurrence}, {@link #contains
25 * contains}, {@link #iterator iterator.remove()}, and the bulk
26 * operations, all of which run in linear time.
28 * <p>This class and its iterator implement all of the
29 * <em>optional</em> methods of the {@link Collection} and {@link
30 * Iterator} interfaces.
32 * <p>This class is a member of the
33 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
34 * Java Collections Framework</a>.
38 * @param <E> the type of elements held in this collection
40 public class LinkedBlockingDeque<E>
41 extends AbstractQueue<E>
42 implements BlockingDeque<E>, java.io.Serializable {
45 * Implemented as a simple doubly-linked list protected by a
46 * single lock and using conditions to manage blocking.
50 * We have "diamond" multiple interface/abstract class inheritance
51 * here, and that introduces ambiguities. Often we want the
52 * BlockingDeque javadoc combined with the AbstractQueue
53 * implementation, so a lot of method specs are duplicated here.
56 private static final long serialVersionUID = -387911632671998426L;
58 /** Doubly-linked list node class */
59 static final class Node<E> {
63 Node(E x, Node<E> p, Node<E> n) {
70 /** Pointer to first node */
71 private transient Node<E> first;
72 /** Pointer to last node */
73 private transient Node<E> last;
74 /** Number of items in the deque */
75 private transient int count;
76 /** Maximum number of items in the deque */
77 private final int capacity;
78 /** Main lock guarding all access */
79 private final ReentrantLock lock = new ReentrantLock();
80 /** Condition for waiting takes */
81 private final Condition notEmpty = lock.newCondition();
82 /** Condition for waiting puts */
83 private final Condition notFull = lock.newCondition();
86 * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
87 * {@link Integer#MAX_VALUE}.
89 public LinkedBlockingDeque() {
90 this(Integer.MAX_VALUE);
94 * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.
96 * @param capacity the capacity of this deque
97 * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
99 public LinkedBlockingDeque(int capacity) {
100 if (capacity <= 0) throw new IllegalArgumentException();
101 this.capacity = capacity;
105 * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
106 * {@link Integer#MAX_VALUE}, initially containing the elements of
107 * the given collection, added in traversal order of the
108 * collection's iterator.
110 * @param c the collection of elements to initially contain
111 * @throws NullPointerException if the specified collection or any
112 * of its elements are null
114 public LinkedBlockingDeque(Collection<? extends E> c) {
115 this(Integer.MAX_VALUE);
121 // Basic linking and unlinking operations, called only while holding lock
124 * Links e as first element, or returns false if full.
126 private boolean linkFirst(E e) {
127 if (count >= capacity)
131 Node<E> x = new Node<E>(e, null, f);
142 * Links e as last element, or returns false if full.
144 private boolean linkLast(E e) {
145 if (count >= capacity)
149 Node<E> x = new Node<E>(e, l, null);
160 * Removes and returns first element, or null if empty.
162 private E unlinkFirst() {
178 * Removes and returns last element, or null if empty.
180 private E unlinkLast() {
198 private void unlink(Node<E> x) {
208 } else if (n == null) {
219 // BlockingDeque methods
222 * @throws IllegalStateException {@inheritDoc}
223 * @throws NullPointerException {@inheritDoc}
225 public void addFirst(E e) {
227 throw new IllegalStateException("Deque full");
231 * @throws IllegalStateException {@inheritDoc}
232 * @throws NullPointerException {@inheritDoc}
234 public void addLast(E e) {
236 throw new IllegalStateException("Deque full");
240 * @throws NullPointerException {@inheritDoc}
242 public boolean offerFirst(E e) {
243 if (e == null) throw new NullPointerException();
253 * @throws NullPointerException {@inheritDoc}
255 public boolean offerLast(E e) {
256 if (e == null) throw new NullPointerException();
266 * @throws NullPointerException {@inheritDoc}
267 * @throws InterruptedException {@inheritDoc}
269 public void putFirst(E e) throws InterruptedException {
270 if (e == null) throw new NullPointerException();
273 while (!linkFirst(e))
281 * @throws NullPointerException {@inheritDoc}
282 * @throws InterruptedException {@inheritDoc}
284 public void putLast(E e) throws InterruptedException {
285 if (e == null) throw new NullPointerException();
296 * @throws NullPointerException {@inheritDoc}
297 * @throws InterruptedException {@inheritDoc}
299 public boolean offerFirst(E e, long timeout, TimeUnit unit)
300 throws InterruptedException {
301 if (e == null) throw new NullPointerException();
302 long nanos = unit.toNanos(timeout);
303 lock.lockInterruptibly();
310 nanos = notFull.awaitNanos(nanos);
318 * @throws NullPointerException {@inheritDoc}
319 * @throws InterruptedException {@inheritDoc}
321 public boolean offerLast(E e, long timeout, TimeUnit unit)
322 throws InterruptedException {
323 if (e == null) throw new NullPointerException();
324 long nanos = unit.toNanos(timeout);
325 lock.lockInterruptibly();
332 nanos = notFull.awaitNanos(nanos);
340 * @throws NoSuchElementException {@inheritDoc}
342 public E removeFirst() {
344 if (x == null) throw new NoSuchElementException();
349 * @throws NoSuchElementException {@inheritDoc}
351 public E removeLast() {
353 if (x == null) throw new NoSuchElementException();
357 public E pollFirst() {
360 return unlinkFirst();
366 public E pollLast() {
375 public E takeFirst() throws InterruptedException {
379 while ( (x = unlinkFirst()) == null)
387 public E takeLast() throws InterruptedException {
391 while ( (x = unlinkLast()) == null)
399 public E pollFirst(long timeout, TimeUnit unit)
400 throws InterruptedException {
401 long nanos = unit.toNanos(timeout);
402 lock.lockInterruptibly();
410 nanos = notEmpty.awaitNanos(nanos);
417 public E pollLast(long timeout, TimeUnit unit)
418 throws InterruptedException {
419 long nanos = unit.toNanos(timeout);
420 lock.lockInterruptibly();
428 nanos = notEmpty.awaitNanos(nanos);
436 * @throws NoSuchElementException {@inheritDoc}
438 public E getFirst() {
440 if (x == null) throw new NoSuchElementException();
445 * @throws NoSuchElementException {@inheritDoc}
449 if (x == null) throw new NoSuchElementException();
453 public E peekFirst() {
456 return (first == null) ? null : first.item;
462 public E peekLast() {
465 return (last == null) ? null : last.item;
471 public boolean removeFirstOccurrence(Object o) {
472 if (o == null) return false;
475 for (Node<E> p = first; p != null; p = p.next) {
476 if (o.equals(p.item)) {
487 public boolean removeLastOccurrence(Object o) {
488 if (o == null) return false;
491 for (Node<E> p = last; p != null; p = p.prev) {
492 if (o.equals(p.item)) {
503 // BlockingQueue methods
506 * Inserts the specified element at the end of this deque unless it would
507 * violate capacity restrictions. When using a capacity-restricted deque,
508 * it is generally preferable to use method {@link #offer(Object) offer}.
510 * <p>This method is equivalent to {@link #addLast}.
512 * @throws IllegalStateException if the element cannot be added at this
513 * time due to capacity restrictions
514 * @throws NullPointerException if the specified element is null
516 public boolean add(E e) {
522 * @throws NullPointerException if the specified element is null
524 public boolean offer(E e) {
529 * @throws NullPointerException {@inheritDoc}
530 * @throws InterruptedException {@inheritDoc}
532 public void put(E e) throws InterruptedException {
537 * @throws NullPointerException {@inheritDoc}
538 * @throws InterruptedException {@inheritDoc}
540 public boolean offer(E e, long timeout, TimeUnit unit)
541 throws InterruptedException {
542 return offerLast(e, timeout, unit);
546 * Retrieves and removes the head of the queue represented by this deque.
547 * This method differs from {@link #poll poll} only in that it throws an
548 * exception if this deque is empty.
550 * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
552 * @return the head of the queue represented by this deque
553 * @throws NoSuchElementException if this deque is empty
556 return removeFirst();
563 public E take() throws InterruptedException {
567 public E poll(long timeout, TimeUnit unit) throws InterruptedException {
568 return pollFirst(timeout, unit);
572 * Retrieves, but does not remove, the head of the queue represented by
573 * this deque. This method differs from {@link #peek peek} only in that
574 * it throws an exception if this deque is empty.
576 * <p>This method is equivalent to {@link #getFirst() getFirst}.
578 * @return the head of the queue represented by this deque
579 * @throws NoSuchElementException if this deque is empty
590 * Returns the number of additional elements that this deque can ideally
591 * (in the absence of memory or resource constraints) accept without
592 * blocking. This is always equal to the initial capacity of this deque
593 * less the current <tt>size</tt> of this deque.
595 * <p>Note that you <em>cannot</em> always tell if an attempt to insert
596 * an element will succeed by inspecting <tt>remainingCapacity</tt>
597 * because it may be the case that another thread is about to
598 * insert or remove an element.
600 public int remainingCapacity() {
603 return capacity - count;
610 * @throws UnsupportedOperationException {@inheritDoc}
611 * @throws ClassCastException {@inheritDoc}
612 * @throws NullPointerException {@inheritDoc}
613 * @throws IllegalArgumentException {@inheritDoc}
615 public int drainTo(Collection<? super E> c) {
617 throw new NullPointerException();
619 throw new IllegalArgumentException();
622 for (Node<E> p = first; p != null; p = p.next)
635 * @throws UnsupportedOperationException {@inheritDoc}
636 * @throws ClassCastException {@inheritDoc}
637 * @throws NullPointerException {@inheritDoc}
638 * @throws IllegalArgumentException {@inheritDoc}
640 public int drainTo(Collection<? super E> c, int maxElements) {
642 throw new NullPointerException();
644 throw new IllegalArgumentException();
648 while (n < maxElements && first != null) {
667 * @throws IllegalStateException {@inheritDoc}
668 * @throws NullPointerException {@inheritDoc}
670 public void push(E e) {
675 * @throws NoSuchElementException {@inheritDoc}
678 return removeFirst();
681 // Collection methods
684 * Removes the first occurrence of the specified element from this deque.
685 * If the deque does not contain the element, it is unchanged.
686 * More formally, removes the first element <tt>e</tt> such that
687 * <tt>o.equals(e)</tt> (if such an element exists).
688 * Returns <tt>true</tt> if this deque contained the specified element
689 * (or equivalently, if this deque changed as a result of the call).
691 * <p>This method is equivalent to
692 * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
694 * @param o element to be removed from this deque, if present
695 * @return <tt>true</tt> if this deque changed as a result of the call
697 public boolean remove(Object o) {
698 return removeFirstOccurrence(o);
702 * Returns the number of elements in this deque.
704 * @return the number of elements in this deque
716 * Returns <tt>true</tt> if this deque contains the specified element.
717 * More formally, returns <tt>true</tt> if and only if this deque contains
718 * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
720 * @param o object to be checked for containment in this deque
721 * @return <tt>true</tt> if this deque contains the specified element
723 public boolean contains(Object o) {
724 if (o == null) return false;
727 for (Node<E> p = first; p != null; p = p.next)
728 if (o.equals(p.item))
737 * Variant of removeFirstOccurrence needed by iterator.remove.
738 * Searches for the node, not its contents.
740 boolean removeNode(Node<E> e) {
743 for (Node<E> p = first; p != null; p = p.next) {
756 * Returns an array containing all of the elements in this deque, in
757 * proper sequence (from first to last element).
759 * <p>The returned array will be "safe" in that no references to it are
760 * maintained by this deque. (In other words, this method must allocate
761 * a new array). The caller is thus free to modify the returned array.
763 * <p>This method acts as bridge between array-based and collection-based
766 * @return an array containing all of the elements in this deque
768 public Object[] toArray() {
771 Object[] a = new Object[count];
773 for (Node<E> p = first; p != null; p = p.next)
782 * Returns an array containing all of the elements in this deque, in
783 * proper sequence; the runtime type of the returned array is that of
784 * the specified array. If the deque fits in the specified array, it
785 * is returned therein. Otherwise, a new array is allocated with the
786 * runtime type of the specified array and the size of this deque.
788 * <p>If this deque fits in the specified array with room to spare
789 * (i.e., the array has more elements than this deque), the element in
790 * the array immediately following the end of the deque is set to
793 * <p>Like the {@link #toArray()} method, this method acts as bridge between
794 * array-based and collection-based APIs. Further, this method allows
795 * precise control over the runtime type of the output array, and may,
796 * under certain circumstances, be used to save allocation costs.
798 * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
799 * The following code can be used to dump the deque into a newly
800 * allocated array of <tt>String</tt>:
803 * String[] y = x.toArray(new String[0]);</pre>
805 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
806 * <tt>toArray()</tt>.
808 * @param a the array into which the elements of the deque are to
809 * be stored, if it is big enough; otherwise, a new array of the
810 * same runtime type is allocated for this purpose
811 * @return an array containing all of the elements in this deque
812 * @throws ArrayStoreException if the runtime type of the specified array
813 * is not a supertype of the runtime type of every element in
815 * @throws NullPointerException if the specified array is null
817 public <T> T[] toArray(T[] a) {
820 if (a.length < count)
821 a = (T[])java.lang.reflect.Array.newInstance(
822 a.getClass().getComponentType(),
827 for (Node<E> p = first; p != null; p = p.next)
837 public String toString() {
840 return super.toString();
847 * Atomically removes all of the elements from this deque.
848 * The deque will be empty after this call returns.
850 public void clear() {
862 * Returns an iterator over the elements in this deque in proper sequence.
863 * The elements will be returned in order from first (head) to last (tail).
864 * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
865 * will never throw {@link ConcurrentModificationException},
866 * and guarantees to traverse elements as they existed upon
867 * construction of the iterator, and may (but is not guaranteed to)
868 * reflect any modifications subsequent to construction.
870 * @return an iterator over the elements in this deque in proper sequence
872 public Iterator<E> iterator() {
877 * Returns an iterator over the elements in this deque in reverse
878 * sequential order. The elements will be returned in order from
879 * last (tail) to first (head).
880 * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
881 * will never throw {@link ConcurrentModificationException},
882 * and guarantees to traverse elements as they existed upon
883 * construction of the iterator, and may (but is not guaranteed to)
884 * reflect any modifications subsequent to construction.
886 public Iterator<E> descendingIterator() {
887 return new DescendingItr();
891 * Base class for Iterators for LinkedBlockingDeque
893 private abstract class AbstractItr implements Iterator<E> {
895 * The next node to return in next
900 * nextItem holds on to item fields because once we claim that
901 * an element exists in hasNext(), we must return item read
902 * under lock (in advance()) even if it was in the process of
903 * being removed when hasNext() was called.
908 * Node returned by most recent call to next. Needed by remove.
909 * Reset to null if this element is deleted by a call to remove.
911 private Node<E> lastRet;
914 advance(); // set to initial position
918 * Advances next, or if not yet initialized, sets to first node.
919 * Implemented to move forward vs backward in the two subclasses.
921 abstract void advance();
923 public boolean hasNext() {
929 throw new NoSuchElementException();
936 public void remove() {
939 throw new IllegalStateException();
941 // Note: removeNode rescans looking for this node to make
942 // sure it was not already removed. Otherwise, trying to
943 // re-remove could corrupt list.
948 /** Forward iterator */
949 private class Itr extends AbstractItr {
951 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
954 next = (next == null)? first : next.next;
955 nextItem = (next == null)? null : next.item;
963 * Descending iterator for LinkedBlockingDeque
965 private class DescendingItr extends AbstractItr {
967 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
970 next = (next == null)? last : next.prev;
971 nextItem = (next == null)? null : next.item;
979 * Save the state of this deque to a stream (that is, serialize it).
981 * @serialData The capacity (int), followed by elements (each an
982 * <tt>Object</tt>) in the proper order, followed by a null
983 * @param s the stream
985 private void writeObject(java.io.ObjectOutputStream s)
986 throws java.io.IOException {
989 // Write out capacity and any hidden stuff
990 s.defaultWriteObject();
991 // Write out all elements in the proper order.
992 for (Node<E> p = first; p != null; p = p.next)
993 s.writeObject(p.item);
994 // Use trailing null as sentinel
1002 * Reconstitute this deque from a stream (that is,
1004 * @param s the stream
1006 private void readObject(java.io.ObjectInputStream s)
1007 throws java.io.IOException, ClassNotFoundException {
1008 s.defaultReadObject();
1012 // Read in all elements and place in queue
1014 E item = (E)s.readObject();