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 {@code LinkedBlockingDeque} with a capacity of
     * {@link Integer#MAX_VALUE}.
     */
    public LinkedBlockingDeque() {
        this(Integer.MAX_VALUE);
    }

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

    /**
     * Creates a {@code LinkedBlockingDeque} 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 {@code c} or any element within it
     * is {@code null}
     */
    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

    /**
     * Links e as first element, or returns 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;
    }

    /**
     * Links e as last element, or returns 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;
    }

    /**
     * Removes and returns 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;
    }

    /**
     * Removes and returns 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 {@code size} of this deque.
     * <p>Note that you <em>cannot</em> always tell if
     * an attempt to {@code add} an element will succeed by
     * inspecting {@code remainingCapacity} because it may be the
     * case that a waiting consumer is ready to {@code take} 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 {@code Iterator} 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);
        }
    }

    /**
     * Saves the state to a stream (that is, serializes it).
     *
     * @serialData The capacity (int), followed by elements (each an
     * {@code Object}) 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();
        }
    }

    /**
     * Reconstitutes this deque instance from a stream (that is,
     * deserializes 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.15
Committed:	Tue Feb 5 17:34:19 2013 UTC (11 years, 2 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.14:	+2 -2 lines
Log Message:	javadoc style
#	Content
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/publicdomain/zero/1.0/
5	*/
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	E item;
54	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 {@code LinkedBlockingDeque} with a capacity of
80	* {@link Integer#MAX_VALUE}.
81	*/
82	public LinkedBlockingDeque() {
83	this(Integer.MAX_VALUE);
84	}
85
86	/**
87	* Creates a {@code LinkedBlockingDeque} with the given (fixed)
88	* capacity.
89	* @param capacity the capacity of this deque
90	* @throws IllegalArgumentException if {@code capacity} 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 {@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 {@code c} or any element within it
104	* is {@code null}
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	* Links e as first element, or returns 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	* Links e as last element, or returns 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	* Removes and returns 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	if (n == null)
161	last = null;
162	else
163	n.prev = null;
164	--count;
165	notFull.signal();
166	return f.item;
167	}
168
169	/**
170	* Removes and returns 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	if (p == null)
179	first = null;
180	else
181	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	if (n == null)
195	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	public void addFirst(E e) {
234	if (!offerFirst(e))
235	throw new IllegalStateException("Deque full");
236	}
237
238	public void addLast(E e) {
239	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	public E getFirst() {
292	E x = peekFirst();
293	if (x == null) throw new NoSuchElementException();
294	return x;
295	}
296
297	public E getLast() {
298	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
369	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	public E pollFirst(long timeout, TimeUnit unit)
388	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	public E pollLast(long timeout, TimeUnit unit)
406	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	public E element() { return getFirst(); }
433	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 {@code size} of this deque.
463	* <p>Note that you <em>cannot</em> always tell if
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() {
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	for (Node<E> p = first; p != null; p = p.next)
483	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	boolean removeNode(Node<E> e) {
528	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	for (Node<E> p = first; p != null; p = p.next)
548	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	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;
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	for (Node<E> p = first; p != null; p = p.next)
607	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 {@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
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	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;
689	} 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	* Saves the state to a stream (that is, serializes it).
721	*
722	* @serialData The capacity (int), followed by elements (each an
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)
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	* 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)
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
762	}