util/concurrent/LinkedBlockingQueue.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain. Use, modify, and
 * redistribute this code in any way without acknowledgement.
 */

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

/**
 * An optionally-bounded {@linkplain BlockingQueue blocking queue} based on
 * linked nodes.
 * This queue orders elements FIFO (first-in-first-out).
 * The <em>head</em> of the queue is that element that has been on the
 * queue the longest time.
 * The <em>tail</em> of the queue is that element that has been on the
 * queue the shortest time. New elements
 * are inserted at the tail of the queue, and the queue retrieval
 * operations obtain elements at the head of the queue.
 * Linked queues typically have higher throughput than array-based queues but
 * less predictable performance in most concurrent applications.
 *
 * <p> The optional capacity bound constructor argument serves as a
 * way to prevent excessive queue 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
 * queue above capacity.
 *
 * <p>This class implements all of the <em>optional</em> methods
 * of the {@link Collection} and {@link Iterator} interfaces.
 *
 * @since 1.5
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 *
 **/
public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    private static final long serialVersionUID = -6903933977591709194L;

    /*
     * A variant of the "two lock queue" algorithm.  The putLock gates
     * entry to put (and offer), and has an associated condition for
     * waiting puts.  Similarly for the takeLock.  The "count" field
     * that they both rely on is maintained as an atomic to avoid
     * needing to get both locks in most cases. Also, to minimize need
     * for puts to get takeLock and vice-versa, cascading notifies are
     * used. When a put notices that it has enabled at least one take,
     * it signals taker. That taker in turn signals others if more
     * items have been entered since the signal. And symmetrically for
     * takes signalling puts. Operations such as remove(Object) and
     * iterators acquire both locks.
    */

    /**
     * Linked list node class
     */
    static class Node<E> {
        /** The item, volatile to ensure barrier separating write and read */
        volatile E item;
        Node<E> next;
        Node(E x) { item = x; }
    }

    /** The capacity bound, or Integer.MAX_VALUE if none */
    private final int capacity;

    /** Current number of elements */
    private final AtomicInteger count = new AtomicInteger(0);

    /** Head of linked list */
    private transient Node<E> head;

    /** Tail of linked list */
    private transient Node<E> last;

    /** Lock held by take, poll, etc */
    private final ReentrantLock takeLock = new ReentrantLock();

    /** Wait queue for waiting takes */
    private final Condition notEmpty = takeLock.newCondition();

    /** Lock held by put, offer, etc */
    private final ReentrantLock putLock = new ReentrantLock();

    /** Wait queue for waiting puts */
    private final Condition notFull = putLock.newCondition();

    /**
     * Signal a waiting take. Called only from put/offer (which do not
     * otherwise ordinarily lock takeLock.)
     */
    private void signalNotEmpty() {
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
    }

    /**
     * Signal a waiting put. Called only from take/poll.
     */
    private void signalNotFull() {
        final ReentrantLock putLock = this.putLock;
        putLock.lock();
        try {
            notFull.signal();
        } finally {
            putLock.unlock();
        }
    }

    /**
     * Create a node and link it at end of queue
     * @param x the item
     */
    private void insert(E x) {
        last = last.next = new Node<E>(x);
    }

    /**
     * Remove a node from head of queue,
     * @return the node
     */
    private E extract() {
        Node<E> first = head.next;
        head = first;
        E x = first.item;
        first.item = null;
        return x;
    }

    /**
     * Lock to prevent both puts and takes.
     */
    private void fullyLock() {
        putLock.lock();
        takeLock.lock();
    }

    /**
     * Unlock to allow both puts and takes.
     */
    private void fullyUnlock() {
        takeLock.unlock();
        putLock.unlock();
    }


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

    /**
     * Creates a <tt>LinkedBlockingQueue</tt> with the given (fixed) capacity.
     *
     * @param capacity the capacity of this queue.
     * @throws IllegalArgumentException if <tt>capacity</tt> is not greater
     *         than zero.
     */
    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node<E>(null);
    }

    /**
     * Creates a <tt>LinkedBlockingQueue</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 LinkedBlockingQueue(Collection<? extends E> c) {
        this(Integer.MAX_VALUE);
        for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
            add(it.next());
    }


    // this doc comment is overridden to remove the reference to collections
    // greater in size than Integer.MAX_VALUE
    /**
     * Returns the number of elements in this queue.
     *
     * @return  the number of elements in this queue.
     */
    public int size() {
        return count.get();
    }

    // this doc comment is a modified copy of the inherited doc comment,
    // without the reference to unlimited queues.
    /**
     * Returns the number of elements that this queue can ideally (in
     * the absence of memory or resource constraints) accept without
     * blocking. This is always equal to the initial capacity of this queue
     * less the current <tt>size</tt> of this queue.
     * <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 queue.
     */
    public int remainingCapacity() {
        return capacity - count.get();
    }

    /**
     * Adds the specified element to the tail of this queue, waiting if
     * necessary for space to become available.
     * @param o the element to add
     * @throws InterruptedException if interrupted while waiting.
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     */
    public void put(E o) throws InterruptedException {
        if (o == null) throw new NullPointerException();
        // Note: convention in all put/take/etc is to preset
        // local var holding count  negative to indicate failure unless set.
        int c = -1;
        final ReentrantLock putLock = this.putLock;
        final AtomicInteger count = this.count;
        putLock.lockInterruptibly();
        try {
            /*
             * Note that count is used in wait guard even though it is
             * not protected by lock. This works because count can
             * only decrease at this point (all other puts are shut
             * out by lock), and we (or some other waiting put) are
             * signalled if it ever changes from
             * capacity. Similarly for all other uses of count in
             * other wait guards.
             */
            try {
                while (count.get() == capacity)
                    notFull.await();
            } catch (InterruptedException ie) {
                notFull.signal(); // propagate to a non-interrupted thread
                throw ie;
            }
            insert(o);
            c = count.getAndIncrement();
            if (c + 1 < capacity)
                notFull.signal();
        } finally {
            putLock.unlock();
        }
        if (c == 0)
            signalNotEmpty();
    }

    /**
     * Inserts the specified element at the tail of this queue, waiting if
     * necessary up to the specified wait time for space to become available.
     * @param o the element to add
     * @param timeout how long to wait before giving up, in units of
     * <tt>unit</tt>
     * @param unit a <tt>TimeUnit</tt> determining how to interpret the
     * <tt>timeout</tt> parameter
     * @return <tt>true</tt> if successful, or <tt>false</tt> if
     * the specified waiting time elapses before space is available.
     * @throws InterruptedException if interrupted while waiting.
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     */
    public boolean offer(E o, long timeout, TimeUnit unit)
        throws InterruptedException {

        if (o == null) throw new NullPointerException();
        long nanos = unit.toNanos(timeout);
        int c = -1;
        final ReentrantLock putLock = this.putLock;
        final AtomicInteger count = this.count;
        putLock.lockInterruptibly();
        try {
            for (;;) {
                if (count.get() < capacity) {
                    insert(o);
                    c = count.getAndIncrement();
                    if (c + 1 < capacity)
                        notFull.signal();
                    break;
                }
                if (nanos <= 0)
                    return false;
                try {
                    nanos = notFull.awaitNanos(nanos);
                } catch (InterruptedException ie) {
                    notFull.signal(); // propagate to a non-interrupted thread
                    throw ie;
                }
            }
        } finally {
            putLock.unlock();
        }
        if (c == 0)
            signalNotEmpty();
        return true;
    }

    /**
     * Inserts the specified element at the tail of this queue if possible,
     * returning immediately if this queue is full.
     *
     * @param o the element to add.
     * @return <tt>true</tt> if it was possible to add the element to
     *         this queue, else <tt>false</tt>
     * @throws NullPointerException if the specified element is <tt>null</tt>
     */
    public boolean offer(E o) {
        if (o == null) throw new NullPointerException();
        final AtomicInteger count = this.count;
        if (count.get() == capacity)
            return false;
        int c = -1;
        final ReentrantLock putLock = this.putLock;
        putLock.lock();
        try {
            if (count.get() < capacity) {
                insert(o);
                c = count.getAndIncrement();
                if (c + 1 < capacity)
                    notFull.signal();
            }
        } finally {
            putLock.unlock();
        }
        if (c == 0)
            signalNotEmpty();
        return c >= 0;
    }


    public E take() throws InterruptedException {
        E x;
        int c = -1;
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();
        try {
            try {
                while (count.get() == 0)
                    notEmpty.await();
            } catch (InterruptedException ie) {
                notEmpty.signal(); // propagate to a non-interrupted thread
                throw ie;
            }

            x = extract();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }

    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        E x = null;
        int c = -1;
        long nanos = unit.toNanos(timeout);
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();
        try {
            for (;;) {
                if (count.get() > 0) {
                    x = extract();
                    c = count.getAndDecrement();
                    if (c > 1)
                        notEmpty.signal();
                    break;
                }
                if (nanos <= 0)
                    return null;
                try {
                    nanos = notEmpty.awaitNanos(nanos);
                } catch (InterruptedException ie) {
                    notEmpty.signal(); // propagate to a non-interrupted thread
                    throw ie;
                }
            }
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }

    public E poll() {
        final AtomicInteger count = this.count;
        if (count.get() == 0)
            return null;
        E x = null;
        int c = -1;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            if (count.get() > 0) {
                x = extract();
                c = count.getAndDecrement();
                if (c > 1)
                    notEmpty.signal();
            }
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }


    public E peek() {
        if (count.get() == 0)
            return null;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            Node<E> first = head.next;
            if (first == null)
                return null;
            else
                return first.item;
        } finally {
            takeLock.unlock();
        }
    }

    public boolean remove(Object o) {
        if (o == null) return false;
        boolean removed = false;
        fullyLock();
        try {
            Node<E> trail = head;
            Node<E> p = head.next;
            while (p != null) {
                if (o.equals(p.item)) {
                    removed = true;
                    break;
                }
                trail = p;
                p = p.next;
            }
            if (removed) {
                p.item = null;
                trail.next = p.next;
                if (count.getAndDecrement() == capacity)
                    notFull.signalAll();
            }
        } finally {
            fullyUnlock();
        }
        return removed;
    }

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

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

            int k = 0;
            for (Node p = head.next; p != null; p = p.next)
                a[k++] = (T)p.item;
            return a;
        } finally {
            fullyUnlock();
        }
    }

    public String toString() {
        fullyLock();
        try {
            return super.toString();
        } finally {
            fullyUnlock();
        }
    }

    public void clear() {
        fullyLock();
        try {
            head.next = null;
            if (count.getAndSet(0) == capacity)
                notFull.signalAll();
        } finally {
            fullyUnlock();
        }
    }

    public int drainTo(Collection<? super E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        Node first;
        fullyLock();
        try {
            first = head.next;
            head.next = null;
            if (count.getAndSet(0) == capacity)
                notFull.signalAll();
        } finally {
            fullyUnlock();
        }
        // Transfer the elements outside of locks
        int n = 0;
        for (Node<E> p = first; p != null; p = p.next) {
            c.add(p.item);
            p.item = null;
            ++n;
        }
        return n;
    }
        
    public int drainTo(Collection<? super E> c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        if (maxElements <= 0)
            return 0;
        fullyLock();
        try {
            int n = 0;
            Node<E> p = head.next;
            while (p != null && n < maxElements) {
                c.add(p.item);
                p.item = null;
                p = p.next;
                ++n;
            }
            if (n != 0) {
                head.next = p;
                if (count.getAndAdd(-n) == capacity)
                    notFull.signalAll();
            }
            return n;
        } finally {
            fullyUnlock();
        }
    }

    /**
     * Returns an iterator over the elements in this queue 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 queue in proper sequence.
     */
    public Iterator<E> iterator() {
      return new Itr();
    }

    private class Itr implements Iterator<E> {
        /*
         * Basic weak-consistent iterator.  At all times hold the next
         * item to hand out so that if hasNext() reports true, we will
         * still have it to return even if lost race with a take etc.
         */
        private Node<E> current;
        private Node<E> lastRet;
        private E currentElement;

        Itr() {
            final ReentrantLock putLock = LinkedBlockingQueue.this.putLock;
            final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock;
            putLock.lock();
            takeLock.lock();
            try {
                current = head.next;
                if (current != null)
                    currentElement = current.item;
            } finally {
                takeLock.unlock();
                putLock.unlock();
            }
        }

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

        public E next() {
            final ReentrantLock putLock = LinkedBlockingQueue.this.putLock;
            final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock;
            putLock.lock();
            takeLock.lock();
            try {
                if (current == null)
                    throw new NoSuchElementException();
                E x = currentElement;
                lastRet = current;
                current = current.next;
                if (current != null)
                    currentElement = current.item;
                return x;
            } finally {
                takeLock.unlock();
                putLock.unlock();
            }
        }

        public void remove() {
            if (lastRet == null)
                throw new IllegalStateException();
            final ReentrantLock putLock = LinkedBlockingQueue.this.putLock;
            final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock;
            putLock.lock();
            takeLock.lock();
            try {
                Node<E> node = lastRet;
                lastRet = null;
                Node<E> trail = head;
                Node<E> p = head.next;
                while (p != null && p != node) {
                    trail = p;
                    p = p.next;
                }
                if (p == node) {
                    p.item = null;
                    trail.next = p.next;
                    int c = count.getAndDecrement();
                    if (c == capacity)
                        notFull.signalAll();
                }
            } finally {
                takeLock.unlock();
                putLock.unlock();
            }
        }
    }

    /**
     * Save the state to a stream (that is, serialize it).
     *
     * @serialData The capacity is emitted (int), followed by all of
     * its 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 {

        fullyLock();
        try {
            // Write out any hidden stuff, plus capacity
            s.defaultWriteObject();

            // Write out all elements in the proper order.
            for (Node<E> p = head.next; p != null; p = p.next)
                s.writeObject(p.item);

            // Use trailing null as sentinel
            s.writeObject(null);
        } finally {
            fullyUnlock();
        }
    }

    /**
     * Reconstitute this queue instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in capacity, and any hidden stuff
        s.defaultReadObject();

        count.set(0);
        last = head = new Node<E>(null);

        // Read in all elements and place in queue
        for (;;) {
            E item = (E)s.readObject();
            if (item == null)
                break;
            add(item);
        }
    }
}
Revision:	1.32
Committed:	Sat Dec 27 17:19:03 2003 UTC (20 years, 5 months ago) by dl
Branch:	MAIN
Changes since 1.31:	+2 -2 lines
Log Message:	Adapt to AbstractQueuedSynchronizer
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain. Use, modify, and
4	* redistribute this code in any way without acknowledgement.
5	*/
6
7	package java.util.concurrent;
8	import java.util.concurrent.atomic.*;
9	import java.util.concurrent.locks.*;
10	import java.util.*;
11
12	/**
13	* An optionally-bounded {@linkplain BlockingQueue blocking queue} based on
14	* linked nodes.
15	* This queue orders elements FIFO (first-in-first-out).
16	* The <em>head</em> of the queue is that element that has been on the
17	* queue the longest time.
18	* The <em>tail</em> of the queue is that element that has been on the
19	* queue the shortest time. New elements
20	* are inserted at the tail of the queue, and the queue retrieval
21	* operations obtain elements at the head of the queue.
22	* Linked queues typically have higher throughput than array-based queues but
23	* less predictable performance in most concurrent applications.
24	*
25	* <p> The optional capacity bound constructor argument serves as a
26	* way to prevent excessive queue expansion. The capacity, if unspecified,
27	* is equal to {@link Integer#MAX_VALUE}. Linked nodes are
28	* dynamically created upon each insertion unless this would bring the
29	* queue above capacity.
30	*
31	* <p>This class implements all of the <em>optional</em> methods
32	* of the {@link Collection} and {@link Iterator} interfaces.
33	*
34	* @since 1.5
35	* @author Doug Lea
36	* @param <E> the type of elements held in this collection
37	*
38	**/
39	public class LinkedBlockingQueue<E> extends AbstractQueue<E>
40	implements BlockingQueue<E>, java.io.Serializable {
41	private static final long serialVersionUID = -6903933977591709194L;
42
43	/*
44	* A variant of the "two lock queue" algorithm. The putLock gates
45	* entry to put (and offer), and has an associated condition for
46	* waiting puts. Similarly for the takeLock. The "count" field
47	* that they both rely on is maintained as an atomic to avoid
48	* needing to get both locks in most cases. Also, to minimize need
49	* for puts to get takeLock and vice-versa, cascading notifies are
50	* used. When a put notices that it has enabled at least one take,
51	* it signals taker. That taker in turn signals others if more
52	* items have been entered since the signal. And symmetrically for
53	* takes signalling puts. Operations such as remove(Object) and
54	* iterators acquire both locks.
55	*/
56
57	/**
58	* Linked list node class
59	*/
60	static class Node<E> {
61	/** The item, volatile to ensure barrier separating write and read */
62	volatile E item;
63	Node<E> next;
64	Node(E x) { item = x; }
65	}
66
67	/** The capacity bound, or Integer.MAX_VALUE if none */
68	private final int capacity;
69
70	/** Current number of elements */
71	private final AtomicInteger count = new AtomicInteger(0);
72
73	/** Head of linked list */
74	private transient Node<E> head;
75
76	/** Tail of linked list */
77	private transient Node<E> last;
78
79	/** Lock held by take, poll, etc */
80	private final ReentrantLock takeLock = new ReentrantLock();
81
82	/** Wait queue for waiting takes */
83	private final Condition notEmpty = takeLock.newCondition();
84
85	/** Lock held by put, offer, etc */
86	private final ReentrantLock putLock = new ReentrantLock();
87
88	/** Wait queue for waiting puts */
89	private final Condition notFull = putLock.newCondition();
90
91	/**
92	* Signal a waiting take. Called only from put/offer (which do not
93	* otherwise ordinarily lock takeLock.)
94	*/
95	private void signalNotEmpty() {
96	final ReentrantLock takeLock = this.takeLock;
97	takeLock.lock();
98	try {
99	notEmpty.signal();
100	} finally {
101	takeLock.unlock();
102	}
103	}
104
105	/**
106	* Signal a waiting put. Called only from take/poll.
107	*/
108	private void signalNotFull() {
109	final ReentrantLock putLock = this.putLock;
110	putLock.lock();
111	try {
112	notFull.signal();
113	} finally {
114	putLock.unlock();
115	}
116	}
117
118	/**
119	* Create a node and link it at end of queue
120	* @param x the item
121	*/
122	private void insert(E x) {
123	last = last.next = new Node<E>(x);
124	}
125
126	/**
127	* Remove a node from head of queue,
128	* @return the node
129	*/
130	private E extract() {
131	Node<E> first = head.next;
132	head = first;
133	E x = first.item;
134	first.item = null;
135	return x;
136	}
137
138	/**
139	* Lock to prevent both puts and takes.
140	*/
141	private void fullyLock() {
142	putLock.lock();
143	takeLock.lock();
144	}
145
146	/**
147	* Unlock to allow both puts and takes.
148	*/
149	private void fullyUnlock() {
150	takeLock.unlock();
151	putLock.unlock();
152	}
153
154
155	/**
156	* Creates a <tt>LinkedBlockingQueue</tt> with a capacity of
157	* {@link Integer#MAX_VALUE}.
158	*/
159	public LinkedBlockingQueue() {
160	this(Integer.MAX_VALUE);
161	}
162
163	/**
164	* Creates a <tt>LinkedBlockingQueue</tt> with the given (fixed) capacity.
165	*
166	* @param capacity the capacity of this queue.
167	* @throws IllegalArgumentException if <tt>capacity</tt> is not greater
168	* than zero.
169	*/
170	public LinkedBlockingQueue(int capacity) {
171	if (capacity <= 0) throw new IllegalArgumentException();
172	this.capacity = capacity;
173	last = head = new Node<E>(null);
174	}
175
176	/**
177	* Creates a <tt>LinkedBlockingQueue</tt> with a capacity of
178	* {@link Integer#MAX_VALUE}, initially containing the elements of the
179	* given collection,
180	* added in traversal order of the collection's iterator.
181	* @param c the collection of elements to initially contain
182	* @throws NullPointerException if <tt>c</tt> or any element within it
183	* is <tt>null</tt>
184	*/
185	public LinkedBlockingQueue(Collection<? extends E> c) {
186	this(Integer.MAX_VALUE);
187	for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
188	add(it.next());
189	}
190
191
192	// this doc comment is overridden to remove the reference to collections
193	// greater in size than Integer.MAX_VALUE
194	/**
195	* Returns the number of elements in this queue.
196	*
197	* @return the number of elements in this queue.
198	*/
199	public int size() {
200	return count.get();
201	}
202
203	// this doc comment is a modified copy of the inherited doc comment,
204	// without the reference to unlimited queues.
205	/**
206	* Returns the number of elements that this queue can ideally (in
207	* the absence of memory or resource constraints) accept without
208	* blocking. This is always equal to the initial capacity of this queue
209	* less the current <tt>size</tt> of this queue.
210	* <p>Note that you <em>cannot</em> always tell if
211	* an attempt to <tt>add</tt> an element will succeed by
212	* inspecting <tt>remainingCapacity</tt> because it may be the
213	* case that a waiting consumer is ready to <tt>take</tt> an
214	* element out of an otherwise full queue.
215	*/
216	public int remainingCapacity() {
217	return capacity - count.get();
218	}
219
220	/**
221	* Adds the specified element to the tail of this queue, waiting if
222	* necessary for space to become available.
223	* @param o the element to add
224	* @throws InterruptedException if interrupted while waiting.
225	* @throws NullPointerException if the specified element is <tt>null</tt>.
226	*/
227	public void put(E o) throws InterruptedException {
228	if (o == null) throw new NullPointerException();
229	// Note: convention in all put/take/etc is to preset
230	// local var holding count negative to indicate failure unless set.
231	int c = -1;
232	final ReentrantLock putLock = this.putLock;
233	final AtomicInteger count = this.count;
234	putLock.lockInterruptibly();
235	try {
236	/*
237	* Note that count is used in wait guard even though it is
238	* not protected by lock. This works because count can
239	* only decrease at this point (all other puts are shut
240	* out by lock), and we (or some other waiting put) are
241	* signalled if it ever changes from
242	* capacity. Similarly for all other uses of count in
243	* other wait guards.
244	*/
245	try {
246	while (count.get() == capacity)
247	notFull.await();
248	} catch (InterruptedException ie) {
249	notFull.signal(); // propagate to a non-interrupted thread
250	throw ie;
251	}
252	insert(o);
253	c = count.getAndIncrement();
254	if (c + 1 < capacity)
255	notFull.signal();
256	} finally {
257	putLock.unlock();
258	}
259	if (c == 0)
260	signalNotEmpty();
261	}
262
263	/**
264	* Inserts the specified element at the tail of this queue, waiting if
265	* necessary up to the specified wait time for space to become available.
266	* @param o the element to add
267	* @param timeout how long to wait before giving up, in units of
268	* <tt>unit</tt>
269	* @param unit a <tt>TimeUnit</tt> determining how to interpret the
270	* <tt>timeout</tt> parameter
271	* @return <tt>true</tt> if successful, or <tt>false</tt> if
272	* the specified waiting time elapses before space is available.
273	* @throws InterruptedException if interrupted while waiting.
274	* @throws NullPointerException if the specified element is <tt>null</tt>.
275	*/
276	public boolean offer(E o, long timeout, TimeUnit unit)
277	throws InterruptedException {
278
279	if (o == null) throw new NullPointerException();
280	long nanos = unit.toNanos(timeout);
281	int c = -1;
282	final ReentrantLock putLock = this.putLock;
283	final AtomicInteger count = this.count;
284	putLock.lockInterruptibly();
285	try {
286	for (;;) {
287	if (count.get() < capacity) {
288	insert(o);
289	c = count.getAndIncrement();
290	if (c + 1 < capacity)
291	notFull.signal();
292	break;
293	}
294	if (nanos <= 0)
295	return false;
296	try {
297	nanos = notFull.awaitNanos(nanos);
298	} catch (InterruptedException ie) {
299	notFull.signal(); // propagate to a non-interrupted thread
300	throw ie;
301	}
302	}
303	} finally {
304	putLock.unlock();
305	}
306	if (c == 0)
307	signalNotEmpty();
308	return true;
309	}
310
311	/**
312	* Inserts the specified element at the tail of this queue if possible,
313	* returning immediately if this queue is full.
314	*
315	* @param o the element to add.
316	* @return <tt>true</tt> if it was possible to add the element to
317	* this queue, else <tt>false</tt>
318	* @throws NullPointerException if the specified element is <tt>null</tt>
319	*/
320	public boolean offer(E o) {
321	if (o == null) throw new NullPointerException();
322	final AtomicInteger count = this.count;
323	if (count.get() == capacity)
324	return false;
325	int c = -1;
326	final ReentrantLock putLock = this.putLock;
327	putLock.lock();
328	try {
329	if (count.get() < capacity) {
330	insert(o);
331	c = count.getAndIncrement();
332	if (c + 1 < capacity)
333	notFull.signal();
334	}
335	} finally {
336	putLock.unlock();
337	}
338	if (c == 0)
339	signalNotEmpty();
340	return c >= 0;
341	}
342
343
344	public E take() throws InterruptedException {
345	E x;
346	int c = -1;
347	final AtomicInteger count = this.count;
348	final ReentrantLock takeLock = this.takeLock;
349	takeLock.lockInterruptibly();
350	try {
351	try {
352	while (count.get() == 0)
353	notEmpty.await();
354	} catch (InterruptedException ie) {
355	notEmpty.signal(); // propagate to a non-interrupted thread
356	throw ie;
357	}
358
359	x = extract();
360	c = count.getAndDecrement();
361	if (c > 1)
362	notEmpty.signal();
363	} finally {
364	takeLock.unlock();
365	}
366	if (c == capacity)
367	signalNotFull();
368	return x;
369	}
370
371	public E poll(long timeout, TimeUnit unit) throws InterruptedException {
372	E x = null;
373	int c = -1;
374	long nanos = unit.toNanos(timeout);
375	final AtomicInteger count = this.count;
376	final ReentrantLock takeLock = this.takeLock;
377	takeLock.lockInterruptibly();
378	try {
379	for (;;) {
380	if (count.get() > 0) {
381	x = extract();
382	c = count.getAndDecrement();
383	if (c > 1)
384	notEmpty.signal();
385	break;
386	}
387	if (nanos <= 0)
388	return null;
389	try {
390	nanos = notEmpty.awaitNanos(nanos);
391	} catch (InterruptedException ie) {
392	notEmpty.signal(); // propagate to a non-interrupted thread
393	throw ie;
394	}
395	}
396	} finally {
397	takeLock.unlock();
398	}
399	if (c == capacity)
400	signalNotFull();
401	return x;
402	}
403
404	public E poll() {
405	final AtomicInteger count = this.count;
406	if (count.get() == 0)
407	return null;
408	E x = null;
409	int c = -1;
410	final ReentrantLock takeLock = this.takeLock;
411	takeLock.lock();
412	try {
413	if (count.get() > 0) {
414	x = extract();
415	c = count.getAndDecrement();
416	if (c > 1)
417	notEmpty.signal();
418	}
419	} finally {
420	takeLock.unlock();
421	}
422	if (c == capacity)
423	signalNotFull();
424	return x;
425	}
426
427
428	public E peek() {
429	if (count.get() == 0)
430	return null;
431	final ReentrantLock takeLock = this.takeLock;
432	takeLock.lock();
433	try {
434	Node<E> first = head.next;
435	if (first == null)
436	return null;
437	else
438	return first.item;
439	} finally {
440	takeLock.unlock();
441	}
442	}
443
444	public boolean remove(Object o) {
445	if (o == null) return false;
446	boolean removed = false;
447	fullyLock();
448	try {
449	Node<E> trail = head;
450	Node<E> p = head.next;
451	while (p != null) {
452	if (o.equals(p.item)) {
453	removed = true;
454	break;
455	}
456	trail = p;
457	p = p.next;
458	}
459	if (removed) {
460	p.item = null;
461	trail.next = p.next;
462	if (count.getAndDecrement() == capacity)
463	notFull.signalAll();
464	}
465	} finally {
466	fullyUnlock();
467	}
468	return removed;
469	}
470
471	public Object[] toArray() {
472	fullyLock();
473	try {
474	int size = count.get();
475	Object[] a = new Object[size];
476	int k = 0;
477	for (Node<E> p = head.next; p != null; p = p.next)
478	a[k++] = p.item;
479	return a;
480	} finally {
481	fullyUnlock();
482	}
483	}
484
485	public <T> T[] toArray(T[] a) {
486	fullyLock();
487	try {
488	int size = count.get();
489	if (a.length < size)
490	a = (T[])java.lang.reflect.Array.newInstance
491	(a.getClass().getComponentType(), size);
492
493	int k = 0;
494	for (Node p = head.next; p != null; p = p.next)
495	a[k++] = (T)p.item;
496	return a;
497	} finally {
498	fullyUnlock();
499	}
500	}
501
502	public String toString() {
503	fullyLock();
504	try {
505	return super.toString();
506	} finally {
507	fullyUnlock();
508	}
509	}
510
511	public void clear() {
512	fullyLock();
513	try {
514	head.next = null;
515	if (count.getAndSet(0) == capacity)
516	notFull.signalAll();
517	} finally {
518	fullyUnlock();
519	}
520	}
521
522	public int drainTo(Collection<? super E> c) {
523	if (c == null)
524	throw new NullPointerException();
525	if (c == this)
526	throw new IllegalArgumentException();
527	Node first;
528	fullyLock();
529	try {
530	first = head.next;
531	head.next = null;
532	if (count.getAndSet(0) == capacity)
533	notFull.signalAll();
534	} finally {
535	fullyUnlock();
536	}
537	// Transfer the elements outside of locks
538	int n = 0;
539	for (Node<E> p = first; p != null; p = p.next) {
540	c.add(p.item);
541	p.item = null;
542	++n;
543	}
544	return n;
545	}
546
547	public int drainTo(Collection<? super E> c, int maxElements) {
548	if (c == null)
549	throw new NullPointerException();
550	if (c == this)
551	throw new IllegalArgumentException();
552	if (maxElements <= 0)
553	return 0;
554	fullyLock();
555	try {
556	int n = 0;
557	Node<E> p = head.next;
558	while (p != null && n < maxElements) {
559	c.add(p.item);
560	p.item = null;
561	p = p.next;
562	++n;
563	}
564	if (n != 0) {
565	head.next = p;
566	if (count.getAndAdd(-n) == capacity)
567	notFull.signalAll();
568	}
569	return n;
570	} finally {
571	fullyUnlock();
572	}
573	}
574
575	/**
576	* Returns an iterator over the elements in this queue in proper sequence.
577	* The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
578	* will never throw {@link java.util.ConcurrentModificationException},
579	* and guarantees to traverse elements as they existed upon
580	* construction of the iterator, and may (but is not guaranteed to)
581	* reflect any modifications subsequent to construction.
582	*
583	* @return an iterator over the elements in this queue in proper sequence.
584	*/
585	public Iterator<E> iterator() {
586	return new Itr();
587	}
588
589	private class Itr implements Iterator<E> {
590	/*
591	* Basic weak-consistent iterator. At all times hold the next
592	* item to hand out so that if hasNext() reports true, we will
593	* still have it to return even if lost race with a take etc.
594	*/
595	private Node<E> current;
596	private Node<E> lastRet;
597	private E currentElement;
598
599	Itr() {
600	final ReentrantLock putLock = LinkedBlockingQueue.this.putLock;
601	final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock;
602	putLock.lock();
603	takeLock.lock();
604	try {
605	current = head.next;
606	if (current != null)
607	currentElement = current.item;
608	} finally {
609	takeLock.unlock();
610	putLock.unlock();
611	}
612	}
613
614	public boolean hasNext() {
615	return current != null;
616	}
617
618	public E next() {
619	final ReentrantLock putLock = LinkedBlockingQueue.this.putLock;
620	final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock;
621	putLock.lock();
622	takeLock.lock();
623	try {
624	if (current == null)
625	throw new NoSuchElementException();
626	E x = currentElement;
627	lastRet = current;
628	current = current.next;
629	if (current != null)
630	currentElement = current.item;
631	return x;
632	} finally {
633	takeLock.unlock();
634	putLock.unlock();
635	}
636	}
637
638	public void remove() {
639	if (lastRet == null)
640	throw new IllegalStateException();
641	final ReentrantLock putLock = LinkedBlockingQueue.this.putLock;
642	final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock;
643	putLock.lock();
644	takeLock.lock();
645	try {
646	Node<E> node = lastRet;
647	lastRet = null;
648	Node<E> trail = head;
649	Node<E> p = head.next;
650	while (p != null && p != node) {
651	trail = p;
652	p = p.next;
653	}
654	if (p == node) {
655	p.item = null;
656	trail.next = p.next;
657	int c = count.getAndDecrement();
658	if (c == capacity)
659	notFull.signalAll();
660	}
661	} finally {
662	takeLock.unlock();
663	putLock.unlock();
664	}
665	}
666	}
667
668	/**
669	* Save the state to a stream (that is, serialize it).
670	*
671	* @serialData The capacity is emitted (int), followed by all of
672	* its elements (each an <tt>Object</tt>) in the proper order,
673	* followed by a null
674	* @param s the stream
675	*/
676	private void writeObject(java.io.ObjectOutputStream s)
677	throws java.io.IOException {
678
679	fullyLock();
680	try {
681	// Write out any hidden stuff, plus capacity
682	s.defaultWriteObject();
683
684	// Write out all elements in the proper order.
685	for (Node<E> p = head.next; p != null; p = p.next)
686	s.writeObject(p.item);
687
688	// Use trailing null as sentinel
689	s.writeObject(null);
690	} finally {
691	fullyUnlock();
692	}
693	}
694
695	/**
696	* Reconstitute this queue instance from a stream (that is,
697	* deserialize it).
698	* @param s the stream
699	*/
700	private void readObject(java.io.ObjectInputStream s)
701	throws java.io.IOException, ClassNotFoundException {
702	// Read in capacity, and any hidden stuff
703	s.defaultReadObject();
704
705	count.set(0);
706	last = head = new Node<E>(null);
707
708	// Read in all elements and place in queue
709	for (;;) {
710	E item = (E)s.readObject();
711	if (item == null)
712	break;
713	add(item);
714	}
715	}
716	}