src/jsr166x/LinkedBlockingDeque.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package jsr166x;

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

/**
 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
 * linked nodes.
 *
 * <p> The optional capacity bound constructor argument serves as a
 * way to prevent excessive expansion. The capacity, if unspecified,
 * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
 * dynamically created upon each insertion unless this would bring the
 * deque above capacity.
 *
 * <p>Most operations run in constant time (ignoring time spent
 * blocking).  Exceptions include {@link #remove(Object) remove},
 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
 * #removeLastOccurrence removeLastOccurrence}, {@link #contains
 * contains }, {@link #iterator iterator.remove()}, and the bulk
 * operations, all of which run in linear time.
 *
 * <p>This class and its iterator implement all of the
 * <em>optional</em> methods of the {@link Collection} and {@link
 * Iterator} interfaces.  This class is a member of the <a
 * href="{@docRoot}/../guide/collections/index.html"> Java Collections
 * Framework</a>.
 *
 * @since 1.6
 * @author  Doug Lea
 * @param <E> the type of elements held in this collection
 */
public class LinkedBlockingDeque<E>
    extends AbstractQueue<E>
    implements BlockingDeque<E>,  java.io.Serializable {

    /*
     * Implemented as a simple doubly-linked list protected by a
     * single lock and using conditions to manage blocking.
     */

    private static final long serialVersionUID = -387911632671998426L;

    /** Doubly-linked list node class */
    static final class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;
        Node(E x, Node<E> p, Node<E> n) {
            item = x;
            prev = p;
            next = n;
        }
    }

    /** Pointer to first node */
    private transient Node<E> first;
    /** Pointer to last node */
    private transient Node<E> last;
    /** Number of items in the deque */
    private transient int count;
    /** Maximum number of items in the deque */
    private final int capacity;
    /** Main lock guarding all access */
    private final ReentrantLock lock = new ReentrantLock();
    /** Condition for waiting takes */
    private final Condition notEmpty = lock.newCondition();
    /** Condition for waiting puts */
    private final Condition notFull = lock.newCondition();

    /**
     * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
     * {@link Integer#MAX_VALUE}.
     */
    public LinkedBlockingDeque() {
        this(Integer.MAX_VALUE);
    }

    /**
     * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed)
     * capacity.
     * @param capacity the capacity of this deque
     * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
     */
    public LinkedBlockingDeque(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
    }

    /**
     * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
     * {@link Integer#MAX_VALUE}, initially containing the elements of the
     * given collection,
     * added in traversal order of the collection's iterator.
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    public LinkedBlockingDeque(Collection<? extends E> c) {
        this(Integer.MAX_VALUE);
        for (E e : c)
            add(e);
    }


    // Basic linking and unlinking operations, called only while holding lock

    /**
     * Link e as first element, or return false if full
     */
    private boolean linkFirst(E e) {
        if (count >= capacity)
            return false;
        ++count;
        Node<E> f = first;
        Node<E> x = new Node<E>(e, null, f);
        first = x;
        if (last == null)
            last = x;
        else
            f.prev = x;
        notEmpty.signal();
        return true;
    }

    /**
     * Link e as last element, or return false if full
     */
    private boolean linkLast(E e) {
        if (count >= capacity)
            return false;
        ++count;
        Node<E> l = last;
        Node<E> x = new Node<E>(e, l, null);
        last = x;
        if (first == null)
            first = x;
        else
            l.next = x;
        notEmpty.signal();
        return true;
    }

    /**
     * Remove and return first element, or null if empty
     */
    private E unlinkFirst() {
        Node<E> f = first;
        if (f == null)
            return null;
        Node<E> n = f.next;
        first = n;
        if (n == null)
            last = null;
        else
            n.prev = null;
        --count;
        notFull.signal();
        return f.item;
    }

    /**
     * Remove and return last element, or null if empty
     */
    private E unlinkLast() {
        Node<E> l = last;
        if (l == null)
            return null;
        Node<E> p = l.prev;
        last = p;
        if (p == null)
            first = null;
        else
            p.next = null;
        --count;
        notFull.signal();
        return l.item;
    }

    /**
     * Unlink e
     */
    private void unlink(Node<E> x) {
        Node<E> p = x.prev;
        Node<E> n = x.next;
        if (p == null) {
            if (n == null)
                first = last = null;
            else {
                n.prev = null;
                first = n;
            }
        } else if (n == null) {
            p.next = null;
            last = p;
        } else {
            p.next = n;
            n.prev = p;
        }
        --count;
        notFull.signalAll();
    }

    // Deque methods

    public boolean offerFirst(E o) {
        if (o == null) throw new NullPointerException();
        lock.lock();
        try {
            return linkFirst(o);
        } finally {
            lock.unlock();
        }
    }

    public boolean offerLast(E o) {
        if (o == null) throw new NullPointerException();
        lock.lock();
        try {
            return linkLast(o);
        } finally {
            lock.unlock();
        }
    }

    public void addFirst(E e) {
        if (!offerFirst(e))
            throw new IllegalStateException("Deque full");
    }

    public void addLast(E e) {
        if (!offerLast(e))
            throw new IllegalStateException("Deque full");
    }

    public E pollFirst() {
        lock.lock();
        try {
            return unlinkFirst();
        } finally {
            lock.unlock();
        }
    }

    public E pollLast() {
        lock.lock();
        try {
            return unlinkLast();
        } finally {
            lock.unlock();
        }
    }

    public E removeFirst() {
        E x = pollFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

    public E removeLast() {
        E x = pollLast();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

    public E peekFirst() {
        lock.lock();
        try {
            return (first == null) ? null : first.item;
        } finally {
            lock.unlock();
        }
    }

    public E peekLast() {
        lock.lock();
        try {
            return (last == null) ? null : last.item;
        } finally {
            lock.unlock();
        }
    }

    public E getFirst() {
        E x = peekFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

    public E getLast() {
        E x = peekLast();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

    // BlockingDeque methods

    public void putFirst(E o) throws InterruptedException {
        if (o == null) throw new NullPointerException();
        lock.lock();
        try {
            while (!linkFirst(o))
                notFull.await();
        } finally {
            lock.unlock();
        }
    }

    public void putLast(E o) throws InterruptedException {
        if (o == null) throw new NullPointerException();
        lock.lock();
        try {
            while (!linkLast(o))
                notFull.await();
        } finally {
            lock.unlock();
        }
    }

    public E takeFirst() throws InterruptedException {
        lock.lock();
        try {
            E x;
            while ( (x = unlinkFirst()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

    public E takeLast() throws InterruptedException {
        lock.lock();
        try {
            E x;
            while ( (x = unlinkLast()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

    public boolean offerFirst(E o, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (o == null) throw new NullPointerException();
        lock.lockInterruptibly();
        try {
            long nanos = unit.toNanos(timeout);
            for (;;) {
                if (linkFirst(o))
                    return true;
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
        } finally {
            lock.unlock();
        }
    }

    public boolean offerLast(E o, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (o == null) throw new NullPointerException();
        lock.lockInterruptibly();
        try {
            long nanos = unit.toNanos(timeout);
            for (;;) {
                if (linkLast(o))
                    return true;
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
        } finally {
            lock.unlock();
        }
    }

    public E pollFirst(long timeout, TimeUnit unit)
        throws InterruptedException {
        lock.lockInterruptibly();
        try {
            long nanos = unit.toNanos(timeout);
            for (;;) {
                E x = unlinkFirst();
                if (x != null)
                    return x;
                if (nanos <= 0)
                    return null;
                nanos = notEmpty.awaitNanos(nanos);
            }
        } finally {
            lock.unlock();
        }
    }

    public E pollLast(long timeout, TimeUnit unit)
        throws InterruptedException {
        lock.lockInterruptibly();
        try {
            long nanos = unit.toNanos(timeout);
            for (;;) {
                E x = unlinkLast();
                if (x != null)
                    return x;
                if (nanos <= 0)
                    return null;
                nanos = notEmpty.awaitNanos(nanos);
            }
        } finally {
            lock.unlock();
        }
    }

    // Queue and stack methods

    public boolean offer(E e)       { return offerLast(e); }
    public boolean add(E e)         { addLast(e); return true; }
    public void push(E e)           { addFirst(e); }
    public E poll()                 { return pollFirst(); }
    public E remove()               { return removeFirst(); }
    public E pop()                  { return removeFirst(); }
    public E peek()                 { return peekFirst(); }
    public E element()              { return getFirst(); }
    public boolean remove(Object o) { return removeFirstOccurrence(o); }

    // BlockingQueue methods

    public void put(E o) throws InterruptedException  { putLast(o);  }
    public E take() throws InterruptedException       { return takeFirst(); }
    public boolean offer(E o, long timeout, TimeUnit unit)
        throws InterruptedException    { return offerLast(o, timeout, unit); }
    public E poll(long timeout, TimeUnit unit)
        throws InterruptedException    { return pollFirst(timeout, unit); }

    /**
     * Returns the number of elements in this deque.
     *
     * @return  the number of elements in this deque.
     */
    public int size() {
        lock.lock();
        try {
            return count;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Returns the number of elements that this deque can ideally (in
     * the absence of memory or resource constraints) accept without
     * blocking. This is always equal to the initial capacity of this deque
     * less the current <tt>size</tt> of this deque.
     * <p>Note that you <em>cannot</em> always tell if
     * an attempt to <tt>add</tt> an element will succeed by
     * inspecting <tt>remainingCapacity</tt> because it may be the
     * case that a waiting consumer is ready to <tt>take</tt> an
     * element out of an otherwise full deque.
     */
    public int remainingCapacity() {
        lock.lock();
        try {
            return capacity - count;
        } finally {
            lock.unlock();
        }
    }

    public boolean contains(Object o) {
        if (o == null) return false;
        lock.lock();
        try {
            for (Node<E> p = first; p != null; p = p.next)
                if (o.equals(p.item))
                    return true;
            return false;
        } finally {
            lock.unlock();
        }
    }

    public boolean removeFirstOccurrence(Object e) {
        if (e == null) throw new NullPointerException();
        lock.lock();
        try {
            for (Node<E> p = first; p != null; p = p.next) {
                if (e.equals(p.item)) {
                    unlink(p);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public boolean removeLastOccurrence(Object e) {
        if (e == null) throw new NullPointerException();
        lock.lock();
        try {
            for (Node<E> p = last; p != null; p = p.prev) {
                if (e.equals(p.item)) {
                    unlink(p);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Variant of removeFirstOccurrence needed by iterator.remove.
     * Searches for the node, not its contents.
     */
    boolean removeNode(Node<E> e) {
        lock.lock();
        try {
            for (Node<E> p = first; p != null; p = p.next) {
                if (p == e) {
                    unlink(p);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public Object[] toArray() {
        lock.lock();
        try {
            Object[] a = new Object[count];
            int k = 0;
            for (Node<E> p = first; p != null; p = p.next)
                a[k++] = p.item;
            return a;
        } finally {
            lock.unlock();
        }
    }

    public <T> T[] toArray(T[] a) {
        lock.lock();
        try {
            if (a.length < count)
                a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(),
                    count
                    );

            int k = 0;
            for (Node<E> p = first; p != null; p = p.next)
                a[k++] = (T)p.item;
            if (a.length > k)
                a[k] = null;
            return a;
        } finally {
            lock.unlock();
        }
    }

    public String toString() {
        lock.lock();
        try {
            return super.toString();
        } finally {
            lock.unlock();
        }
    }

    /**
     * Atomically removes all of the elements from this deque.
     * The deque will be empty after this call returns.
     */
    public void clear() {
        lock.lock();
        try {
            first = last = null;
            count = 0;
            notFull.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public int drainTo(Collection<? super E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        lock.lock();
        try {
            for (Node<E> p = first; p != null; p = p.next)
                c.add(p.item);
            int n = count;
            count = 0;
            first = last = null;
            notFull.signalAll();
            return n;
        } finally {
            lock.unlock();
        }
    }

    public int drainTo(Collection<? super E> c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        lock.lock();
        try {
            int n = 0;
            while (n < maxElements && first != null) {
                c.add(first.item);
                first.prev = null;
                first = first.next;
                --count;
                ++n;
            }
            if (first == null)
                last = null;
            notFull.signalAll();
            return n;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Returns an iterator over the elements in this deque in proper sequence.
     * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
     * will never throw {@link java.util.ConcurrentModificationException},
     * and guarantees to traverse elements as they existed upon
     * construction of the iterator, and may (but is not guaranteed to)
     * reflect any modifications subsequent to construction.
     *
     * @return an iterator over the elements in this deque in proper sequence.
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * Iterator for LinkedBlockingDeque
     */
    private class Itr implements Iterator<E> {
        private Node<E> next;

        /**
         * nextItem holds on to item fields because once we claim that
         * an element exists in hasNext(), we must return item read
         * under lock (in advance()) even if it was in the process of
         * being removed when hasNext() was called.
         **/
        private E nextItem;

        /**
         * Node returned by most recent call to next. Needed by remove.
         * Reset to null if this element is deleted by a call to remove.
         */
        private Node<E> last;

        Itr() {
            advance();
        }

        /**
         * Advance next, or if not yet initialized, set to first node.
         */
        private void advance() {
            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
            lock.lock();
            try {
                next = (next == null) ? first : next.next;
                nextItem = (next == null) ? null : next.item;
            } finally {
                lock.unlock();
            }
        }

        public boolean hasNext() {
            return next != null;
        }

        public E next() {
            if (next == null)
                throw new NoSuchElementException();
            last = next;
            E x = nextItem;
            advance();
            return x;
        }

        public void remove() {
            Node<E> n = last;
            if (n == null)
                throw new IllegalStateException();
            last = null;
            // Note: removeNode rescans looking for this node to make
            // sure it was not already removed. Otherwwise, trying to
            // re-remove could corrupt list.
            removeNode(n);
        }
    }

    /**
     * Save the state to a stream (that is, serialize it).
     *
     * @serialData The capacity (int), followed by elements (each an
     * <tt>Object</tt>) in the proper order, followed by a null
     * @param s the stream
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        lock.lock();
        try {
            // Write out capacity and any hidden stuff
            s.defaultWriteObject();
            // Write out all elements in the proper order.
            for (Node<E> p = first; p != null; p = p.next)
                s.writeObject(p.item);
            // Use trailing null as sentinel
            s.writeObject(null);
        } finally {
            lock.unlock();
        }
    }

    /**
     * Reconstitute this deque instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();
        count = 0;
        first = null;
        last = null;
        // Read in all elements and place in queue
        for (;;) {
            E item = (E)s.readObject();
            if (item == null)
                break;
            add(item);
        }
    }

}
Revision:	1.7
Committed:	Thu Apr 14 23:16:10 2011 UTC (13 years ago) by jsr166
Branch:	MAIN
CVS Tags:	jdk7-compat, release-1_7_0
Changes since 1.6:	+1 -1 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	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	jsr166	1.6	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7			package jsr166x;
8
9			import java.util.*;
10			import java.util.concurrent.*;
11			import java.util.concurrent.locks.*;
12
13			/**
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
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
21			* deque above capacity.
22			*
23			* <p>Most operations run in constant time (ignoring time spent
24			* blocking). Exceptions include {@link #remove(Object) remove},
25			* {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
26			* #removeLastOccurrence removeLastOccurrence}, {@link #contains
27			* contains }, {@link #iterator iterator.remove()}, and the bulk
28			* operations, all of which run in linear time.
29			*
30			* <p>This class and its iterator implement all of the
31			* <em>optional</em> methods of the {@link Collection} and {@link
32			* Iterator} interfaces. This class is a member of the <a
33			* href="{@docRoot}/../guide/collections/index.html"> Java Collections
34			* Framework</a>.
35			*
36			* @since 1.6
37			* @author Doug Lea
38			* @param <E> the type of elements held in this collection
39			*/
40			public class LinkedBlockingDeque<E>
41			extends AbstractQueue<E>
42			implements BlockingDeque<E>, java.io.Serializable {
43
44			/*
45			* Implemented as a simple doubly-linked list protected by a
46			* single lock and using conditions to manage blocking.
47			*/
48
49			private static final long serialVersionUID = -387911632671998426L;
50
51			/** Doubly-linked list node class */
52			static final class Node<E> {
53	jsr166	1.4	E item;
54	dl	1.1	Node<E> prev;
55			Node<E> next;
56			Node(E x, Node<E> p, Node<E> n) {
57			item = x;
58			prev = p;
59			next = n;
60			}
61			}
62
63			/** Pointer to first node */
64			private transient Node<E> first;
65			/** Pointer to last node */
66			private transient Node<E> last;
67			/** Number of items in the deque */
68			private transient int count;
69			/** Maximum number of items in the deque */
70			private final int capacity;
71			/** Main lock guarding all access */
72			private final ReentrantLock lock = new ReentrantLock();
73			/** Condition for waiting takes */
74			private final Condition notEmpty = lock.newCondition();
75			/** Condition for waiting puts */
76			private final Condition notFull = lock.newCondition();
77
78			/**
79			* Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
80			* {@link Integer#MAX_VALUE}.
81			*/
82			public LinkedBlockingDeque() {
83			this(Integer.MAX_VALUE);
84			}
85
86			/**
87			* Creates a <tt>LinkedBlockingDeque</tt> 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
91			*/
92			public LinkedBlockingDeque(int capacity) {
93			if (capacity <= 0) throw new IllegalArgumentException();
94			this.capacity = capacity;
95			}
96
97			/**
98			* Creates a <tt>LinkedBlockingDeque</tt> 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>
105			*/
106			public LinkedBlockingDeque(Collection<? extends E> c) {
107			this(Integer.MAX_VALUE);
108			for (E e : c)
109			add(e);
110			}
111
112
113			// Basic linking and unlinking operations, called only while holding lock
114
115			/**
116			* Link e as first element, or return false if full
117			*/
118			private boolean linkFirst(E e) {
119			if (count >= capacity)
120			return false;
121			++count;
122			Node<E> f = first;
123			Node<E> x = new Node<E>(e, null, f);
124			first = x;
125			if (last == null)
126			last = x;
127			else
128			f.prev = x;
129			notEmpty.signal();
130			return true;
131			}
132
133			/**
134			* Link e as last element, or return false if full
135			*/
136			private boolean linkLast(E e) {
137			if (count >= capacity)
138			return false;
139			++count;
140			Node<E> l = last;
141			Node<E> x = new Node<E>(e, l, null);
142			last = x;
143			if (first == null)
144			first = x;
145			else
146			l.next = x;
147			notEmpty.signal();
148			return true;
149			}
150
151			/**
152			* Remove and return first element, or null if empty
153			*/
154			private E unlinkFirst() {
155			Node<E> f = first;
156			if (f == null)
157			return null;
158			Node<E> n = f.next;
159			first = n;
160	jsr166	1.3	if (n == null)
161	dl	1.1	last = null;
162	jsr166	1.3	else
163	dl	1.1	n.prev = null;
164			--count;
165			notFull.signal();
166			return f.item;
167			}
168
169			/**
170			* Remove and return last element, or null if empty
171			*/
172			private E unlinkLast() {
173			Node<E> l = last;
174			if (l == null)
175			return null;
176			Node<E> p = l.prev;
177			last = p;
178	jsr166	1.3	if (p == null)
179	dl	1.1	first = null;
180	jsr166	1.3	else
181	dl	1.1	p.next = null;
182			--count;
183			notFull.signal();
184			return l.item;
185			}
186
187			/**
188			* Unlink e
189			*/
190			private void unlink(Node<E> x) {
191			Node<E> p = x.prev;
192			Node<E> n = x.next;
193			if (p == null) {
194	jsr166	1.3	if (n == null)
195	dl	1.1	first = last = null;
196			else {
197			n.prev = null;
198			first = n;
199			}
200			} else if (n == null) {
201			p.next = null;
202			last = p;
203			} else {
204			p.next = n;
205			n.prev = p;
206			}
207			--count;
208			notFull.signalAll();
209			}
210
211			// Deque methods
212
213			public boolean offerFirst(E o) {
214			if (o == null) throw new NullPointerException();
215			lock.lock();
216			try {
217			return linkFirst(o);
218			} finally {
219			lock.unlock();
220			}
221			}
222
223			public boolean offerLast(E o) {
224			if (o == null) throw new NullPointerException();
225			lock.lock();
226			try {
227			return linkLast(o);
228			} finally {
229			lock.unlock();
230			}
231			}
232
233	jsr166	1.3	public void addFirst(E e) {
234	dl	1.1	if (!offerFirst(e))
235			throw new IllegalStateException("Deque full");
236			}
237
238	jsr166	1.3	public void addLast(E e) {
239	dl	1.1	if (!offerLast(e))
240			throw new IllegalStateException("Deque full");
241			}
242
243			public E pollFirst() {
244			lock.lock();
245			try {
246			return unlinkFirst();
247			} finally {
248			lock.unlock();
249			}
250			}
251
252			public E pollLast() {
253			lock.lock();
254			try {
255			return unlinkLast();
256			} finally {
257			lock.unlock();
258			}
259			}
260
261			public E removeFirst() {
262			E x = pollFirst();
263			if (x == null) throw new NoSuchElementException();
264			return x;
265			}
266
267			public E removeLast() {
268			E x = pollLast();
269			if (x == null) throw new NoSuchElementException();
270			return x;
271			}
272
273			public E peekFirst() {
274			lock.lock();
275			try {
276			return (first == null) ? null : first.item;
277			} finally {
278			lock.unlock();
279			}
280			}
281
282			public E peekLast() {
283			lock.lock();
284			try {
285			return (last == null) ? null : last.item;
286			} finally {
287			lock.unlock();
288			}
289			}
290
291	dl	1.2	public E getFirst() {
292	dl	1.1	E x = peekFirst();
293			if (x == null) throw new NoSuchElementException();
294			return x;
295			}
296
297	dl	1.2	public E getLast() {
298	dl	1.1	E x = peekLast();
299			if (x == null) throw new NoSuchElementException();
300			return x;
301			}
302
303			// BlockingDeque methods
304
305			public void putFirst(E o) throws InterruptedException {
306			if (o == null) throw new NullPointerException();
307			lock.lock();
308			try {
309			while (!linkFirst(o))
310			notFull.await();
311			} finally {
312			lock.unlock();
313			}
314			}
315
316			public void putLast(E o) throws InterruptedException {
317			if (o == null) throw new NullPointerException();
318			lock.lock();
319			try {
320			while (!linkLast(o))
321			notFull.await();
322			} finally {
323			lock.unlock();
324			}
325			}
326
327			public E takeFirst() throws InterruptedException {
328			lock.lock();
329			try {
330			E x;
331			while ( (x = unlinkFirst()) == null)
332			notEmpty.await();
333			return x;
334			} finally {
335			lock.unlock();
336			}
337			}
338
339			public E takeLast() throws InterruptedException {
340			lock.lock();
341			try {
342			E x;
343			while ( (x = unlinkLast()) == null)
344			notEmpty.await();
345			return x;
346			} finally {
347			lock.unlock();
348			}
349			}
350
351			public boolean offerFirst(E o, long timeout, TimeUnit unit)
352			throws InterruptedException {
353			if (o == null) throw new NullPointerException();
354			lock.lockInterruptibly();
355			try {
356			long nanos = unit.toNanos(timeout);
357			for (;;) {
358			if (linkFirst(o))
359			return true;
360			if (nanos <= 0)
361			return false;
362			nanos = notFull.awaitNanos(nanos);
363			}
364			} finally {
365			lock.unlock();
366			}
367			}
368	jsr166	1.3
369	dl	1.1	public boolean offerLast(E o, long timeout, TimeUnit unit)
370			throws InterruptedException {
371			if (o == null) throw new NullPointerException();
372			lock.lockInterruptibly();
373			try {
374			long nanos = unit.toNanos(timeout);
375			for (;;) {
376			if (linkLast(o))
377			return true;
378			if (nanos <= 0)
379			return false;
380			nanos = notFull.awaitNanos(nanos);
381			}
382			} finally {
383			lock.unlock();
384			}
385			}
386
387	jsr166	1.3	public E pollFirst(long timeout, TimeUnit unit)
388	dl	1.1	throws InterruptedException {
389			lock.lockInterruptibly();
390			try {
391			long nanos = unit.toNanos(timeout);
392			for (;;) {
393			E x = unlinkFirst();
394			if (x != null)
395			return x;
396			if (nanos <= 0)
397			return null;
398			nanos = notEmpty.awaitNanos(nanos);
399			}
400			} finally {
401			lock.unlock();
402			}
403			}
404
405	jsr166	1.3	public E pollLast(long timeout, TimeUnit unit)
406	dl	1.1	throws InterruptedException {
407			lock.lockInterruptibly();
408			try {
409			long nanos = unit.toNanos(timeout);
410			for (;;) {
411			E x = unlinkLast();
412			if (x != null)
413			return x;
414			if (nanos <= 0)
415			return null;
416			nanos = notEmpty.awaitNanos(nanos);
417			}
418			} finally {
419			lock.unlock();
420			}
421			}
422
423			// Queue and stack methods
424
425			public boolean offer(E e) { return offerLast(e); }
426			public boolean add(E e) { addLast(e); return true; }
427			public void push(E e) { addFirst(e); }
428			public E poll() { return pollFirst(); }
429			public E remove() { return removeFirst(); }
430			public E pop() { return removeFirst(); }
431			public E peek() { return peekFirst(); }
432	dl	1.2	public E element() { return getFirst(); }
433	dl	1.1	public boolean remove(Object o) { return removeFirstOccurrence(o); }
434
435			// BlockingQueue methods
436
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)
442			throws InterruptedException { return pollFirst(timeout, unit); }
443
444			/**
445			* Returns the number of elements in this deque.
446			*
447			* @return the number of elements in this deque.
448			*/
449			public int size() {
450			lock.lock();
451			try {
452			return count;
453			} finally {
454			lock.unlock();
455			}
456			}
457
458			/**
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.
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
467			* element out of an otherwise full deque.
468			*/
469			public int remainingCapacity() {
470			lock.lock();
471			try {
472			return capacity - count;
473			} finally {
474			lock.unlock();
475			}
476			}
477
478			public boolean contains(Object o) {
479			if (o == null) return false;
480			lock.lock();
481			try {
482	jsr166	1.3	for (Node<E> p = first; p != null; p = p.next)
483	dl	1.1	if (o.equals(p.item))
484			return true;
485			return false;
486			} finally {
487			lock.unlock();
488			}
489			}
490
491			public boolean removeFirstOccurrence(Object e) {
492			if (e == null) throw new NullPointerException();
493			lock.lock();
494			try {
495			for (Node<E> p = first; p != null; p = p.next) {
496			if (e.equals(p.item)) {
497			unlink(p);
498			return true;
499			}
500			}
501			return false;
502			} finally {
503			lock.unlock();
504			}
505			}
506
507			public boolean removeLastOccurrence(Object e) {
508			if (e == null) throw new NullPointerException();
509			lock.lock();
510			try {
511			for (Node<E> p = last; p != null; p = p.prev) {
512			if (e.equals(p.item)) {
513			unlink(p);
514			return true;
515			}
516			}
517			return false;
518			} finally {
519			lock.unlock();
520			}
521			}
522
523			/**
524			* Variant of removeFirstOccurrence needed by iterator.remove.
525			* Searches for the node, not its contents.
526			*/
527	jsr166	1.7	boolean removeNode(Node<E> e) {
528	dl	1.1	lock.lock();
529			try {
530			for (Node<E> p = first; p != null; p = p.next) {
531			if (p == e) {
532			unlink(p);
533			return true;
534			}
535			}
536			return false;
537			} finally {
538			lock.unlock();
539			}
540			}
541
542			public Object[] toArray() {
543			lock.lock();
544			try {
545			Object[] a = new Object[count];
546			int k = 0;
547	jsr166	1.3	for (Node<E> p = first; p != null; p = p.next)
548	dl	1.1	a[k++] = p.item;
549			return a;
550			} finally {
551			lock.unlock();
552			}
553			}
554
555			public <T> T[] toArray(T[] a) {
556			lock.lock();
557			try {
558			if (a.length < count)
559			a = (T[])java.lang.reflect.Array.newInstance(
560			a.getClass().getComponentType(),
561			count
562			);
563
564			int k = 0;
565	jsr166	1.3	for (Node<E> p = first; p != null; p = p.next)
566	dl	1.1	a[k++] = (T)p.item;
567			if (a.length > k)
568			a[k] = null;
569			return a;
570			} finally {
571			lock.unlock();
572			}
573			}
574
575			public String toString() {
576			lock.lock();
577			try {
578			return super.toString();
579			} finally {
580			lock.unlock();
581			}
582			}
583
584			/**
585			* Atomically removes all of the elements from this deque.
586			* The deque will be empty after this call returns.
587			*/
588			public void clear() {
589			lock.lock();
590			try {
591			first = last = null;
592			count = 0;
593			notFull.signalAll();
594			} finally {
595			lock.unlock();
596			}
597			}
598
599			public int drainTo(Collection<? super E> c) {
600			if (c == null)
601			throw new NullPointerException();
602			if (c == this)
603			throw new IllegalArgumentException();
604			lock.lock();
605			try {
606	jsr166	1.3	for (Node<E> p = first; p != null; p = p.next)
607	dl	1.1	c.add(p.item);
608			int n = count;
609			count = 0;
610			first = last = null;
611			notFull.signalAll();
612			return n;
613			} finally {
614			lock.unlock();
615			}
616			}
617
618			public int drainTo(Collection<? super E> c, int maxElements) {
619			if (c == null)
620			throw new NullPointerException();
621			if (c == this)
622			throw new IllegalArgumentException();
623			lock.lock();
624			try {
625			int n = 0;
626			while (n < maxElements && first != null) {
627			c.add(first.item);
628			first.prev = null;
629			first = first.next;
630			--count;
631			++n;
632			}
633			if (first == null)
634			last = null;
635			notFull.signalAll();
636			return n;
637			} finally {
638			lock.unlock();
639			}
640			}
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
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.
651			*/
652			public Iterator<E> iterator() {
653			return new Itr();
654			}
655
656			/**
657			* Iterator for LinkedBlockingDeque
658			*/
659			private class Itr implements Iterator<E> {
660			private Node<E> next;
661
662			/**
663			* nextItem holds on to item fields because once we claim that
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			**/
668			private E nextItem;
669
670			/**
671			* Node returned by most recent call to next. Needed by remove.
672			* Reset to null if this element is deleted by a call to remove.
673			*/
674			private Node<E> last;
675
676			Itr() {
677			advance();
678			}
679
680			/**
681			* Advance next, or if not yet initialized, set to first node.
682			*/
683	jsr166	1.3	private void advance() {
684	dl	1.1	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
685			lock.lock();
686			try {
687	jsr166	1.5	next = (next == null) ? first : next.next;
688			nextItem = (next == null) ? null : next.item;
689	dl	1.1	} finally {
690			lock.unlock();
691			}
692			}
693
694			public boolean hasNext() {
695			return next != null;
696			}
697
698			public E next() {
699			if (next == null)
700			throw new NoSuchElementException();
701			last = next;
702			E x = nextItem;
703			advance();
704			return x;
705			}
706
707			public void remove() {
708			Node<E> n = last;
709			if (n == null)
710			throw new IllegalStateException();
711			last = null;
712			// Note: removeNode rescans looking for this node to make
713			// sure it was not already removed. Otherwwise, trying to
714			// re-remove could corrupt list.
715			removeNode(n);
716			}
717			}
718
719			/**
720			* Save the state to a stream (that is, serialize it).
721			*
722			* @serialData The capacity (int), followed by elements (each an
723			* <tt>Object</tt>) in the proper order, followed by a null
724			* @param s the stream
725			*/
726			private void writeObject(java.io.ObjectOutputStream s)
727			throws java.io.IOException {
728			lock.lock();
729			try {
730			// Write out capacity and any hidden stuff
731			s.defaultWriteObject();
732			// Write out all elements in the proper order.
733			for (Node<E> p = first; p != null; p = p.next)
734			s.writeObject(p.item);
735			// Use trailing null as sentinel
736			s.writeObject(null);
737			} finally {
738			lock.unlock();
739			}
740			}
741
742			/**
743			* Reconstitute this deque instance from a stream (that is,
744			* deserialize it).
745			* @param s the stream
746			*/
747			private void readObject(java.io.ObjectInputStream s)
748			throws java.io.IOException, ClassNotFoundException {
749			s.defaultReadObject();
750			count = 0;
751			first = null;
752			last = null;
753			// Read in all elements and place in queue
754			for (;;) {
755			E item = (E)s.readObject();
756			if (item == null)
757			break;
758			add(item);
759			}
760			}
761	jsr166	1.3
762	dl	1.1	}