util/concurrent/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/licenses/publicdomain
 */

package java.util.concurrent;
import java.util.*;
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

    /**
     * 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 additional 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 insert
     * an element will succeed by inspecting <tt>remainingCapacity</tt>
     * because it may be the case that another thread is about to
     * <tt>put</tt> or <tt>take</tt> an element.
     */
    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 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();
        }

        /**
         * Advances 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. Otherwise, trying to
            // re-remove could corrupt list.
            removeNode(n);
        }
    }

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