util/concurrent/ArrayBlockingQueue.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.locks.*;
import java.util.*;

/**
 * A bounded {@linkplain BlockingQueue blocking queue} backed by an
 * array.  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.
 *
 * <p>This is a classic &quot;bounded buffer&quot;, in which a fixed-sized
 * array holds
 * elements inserted by producers and extracted by consumers.  Once
 * created, the capacity can not be increased.  Attempts to offer an
 * element to a full queue will result in the offer operation
 * blocking; attempts to retrieve an element from an empty queue will
 * similarly block.
 *
 * <p> This class supports an optional fairness policy for ordering
 * threads blocked on an insertion or removal.  By default, this
 * ordering is not guaranteed. However, an <tt>ArrayBlockingQueue</tt>
 * constructed with fairness set to <tt>true</tt> grants blocked
 * threads access in FIFO order. Fairness generally decreases
 * throughput but reduces variability and avoids starvation.
 *
 * <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 ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    /**
     * Seialization ID. This class relies on default serialzation even
     * for the items array is default-serialized, even if it is
     * empty. Otherwise it could not be declared final, which is
     * necessary here.
     */
    private static final long serialVersionUID = -817911632652898426L;

    /** The queued items  */
    private final E[] items;
    /** items index for next take, poll or remove */
    private transient int takeIndex;
    /** items index for next put, offer, or add. */
    private transient int putIndex;
    /** Number of items in the queue */
    private int count;

    /*
     * Concurrency control uses the classic two-condition algorithm
     * found in any textbook.
     */

    /** Main lock guarding all access */
    private final ReentrantLock lock;
    /** Condition for waiting takes */
    private final ReentrantLock.ConditionObject notEmpty;
    /** Condition for waiting puts */
    private final ReentrantLock.ConditionObject notFull;

    // Internal helper methods

    /**
     * Circularly increment i.
     */
    int inc(int i) {
        return (++i == items.length)? 0 : i;
    }

    /**
     * Insert element at current put position, advance, and signal.
     * Call only when holding lock.
     */
    private void insert(E x) {
        items[putIndex] = x;
        putIndex = inc(putIndex);
        ++count;
        notEmpty.signal();
    }

    /**
     * Extract element at current take position, advance, and signal.
     * Call only when holding lock.
     */
    private E extract() {
        final E[] items = this.items;
        E x = items[takeIndex];
        items[takeIndex] = null;
        takeIndex = inc(takeIndex);
        --count;
        notFull.signal();
        return x;
    }

    /**
     * Utility for remove and iterator.remove: Delete item at position i.
     * Call only when holding lock.
     */
    void removeAt(int i) {
        final E[] items = this.items;
        // if removing front item, just advance
        if (i == takeIndex) {
            items[takeIndex] = null;
            takeIndex = inc(takeIndex);
        } else {
            // slide over all others up through putIndex.
            for (;;) {
                int nexti = inc(i);
                if (nexti != putIndex) {
                    items[i] = items[nexti];
                    i = nexti;
                } else {
                    items[i] = null;
                    putIndex = i;
                    break;
                }
            }
        }
        --count;
        notFull.signal();
    }

    /**
     * Creates an <tt>ArrayBlockingQueue</tt> with the given (fixed)
     * capacity and default access policy.
     * @param capacity the capacity of this queue
     * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
     */
    public ArrayBlockingQueue(int capacity) {
        this(capacity, false);
    }

    /**
     * Creates an <tt>ArrayBlockingQueue</tt> with the given (fixed)
     * capacity and the specified access policy.
     * @param capacity the capacity of this queue
     * @param fair if <tt>true</tt> then queue accesses for threads blocked
     * on insertion or removal, are processed in FIFO order; if <tt>false</tt>
     * the access order is unspecified.
     * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
     */
    public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = (E[]) new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }

    /**
     * Creates an <tt>ArrayBlockingQueue</tt> with the given (fixed)
     * capacity, the specified access policy and initially containing the
     * elements of the given collection,
     * added in traversal order of the collection's iterator.
     * @param capacity the capacity of this queue
     * @param fair if <tt>true</tt> then queue accesses for threads blocked
     * on insertion or removal, are processed in FIFO order; if <tt>false</tt>
     * the access order is unspecified.
     * @param c the collection of elements to initially contain
     * @throws IllegalArgumentException if <tt>capacity</tt> is less than
     * <tt>c.size()</tt>, or less than 1.
     * @throws NullPointerException if <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    public ArrayBlockingQueue(int capacity, boolean fair,
                              Collection<? extends E> c) {
        this(capacity, fair);
        if (capacity < c.size())
            throw new IllegalArgumentException();

        for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
            add(it.next());
    }

    /**
     * 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 ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count == items.length)
                return false;
            else {
                insert(o);
                return true;
            }
        } finally {
            lock.unlock();
        }
    }

    /**
     * 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();
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            long nanos = unit.toNanos(timeout);
            for (;;) {
                if (count != items.length) {
                    insert(o);
                    return true;
                }
                if (nanos <= 0)
                    return false;
                try {
                    nanos = notFull.awaitNanos(nanos);
                } catch (InterruptedException ie) {
                    notFull.signal(); // propagate to non-interrupted thread
                    throw ie;
                }
            }
        } finally {
            lock.unlock();
        }
    }


    public E poll() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count == 0)
                return null;
            E x = extract();
            return x;
        } finally {
            lock.unlock();
        }
    }

    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            long nanos = unit.toNanos(timeout);
            for (;;) {
                if (count != 0) {
                    E x = extract();
                    return x;
                }
                if (nanos <= 0)
                    return null;
                try {
                    nanos = notEmpty.awaitNanos(nanos);
                } catch (InterruptedException ie) {
                    notEmpty.signal(); // propagate to non-interrupted thread
                    throw ie;
                }

            }
        } finally {
            lock.unlock();
        }
    }


    public boolean remove(Object o) {
        if (o == null) return false;
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = takeIndex;
            int k = 0;
            for (;;) {
                if (k++ >= count)
                    return false;
                if (o.equals(items[i])) {
                    removeAt(i);
                    return true;
                }
                i = inc(i);
            }

        } finally {
            lock.unlock();
        }
    }

    public E peek() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return (count == 0) ? null : items[takeIndex];
        } finally {
            lock.unlock();
        }
    }

    public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            try {
                while (count == 0)
                    notEmpty.await();
            } catch (InterruptedException ie) {
                notEmpty.signal(); // propagate to non-interrupted thread
                throw ie;
            }
            E x = extract();
            return x;
        } finally {
            lock.unlock();
        }
    }

    /**
     * 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();
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            try {
                while (count == items.length)
                    notFull.await();
            } catch (InterruptedException ie) {
                notFull.signal(); // propagate to non-interrupted thread
                throw ie;
            }
            insert(o);
        } finally {
            lock.unlock();
        }
    }

    // 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() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return count;
        } finally {
            lock.unlock();
        }
    }

    // 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() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return items.length - count;
        } finally {
            lock.unlock();
        }
    }


    public boolean contains(Object o) {
        if (o == null) return false;
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = takeIndex;
            int k = 0;
            while (k++ < count) {
                if (o.equals(items[i]))
                    return true;
                i = inc(i);
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public Object[] toArray() {
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] a = new Object[count];
            int k = 0;
            int i = takeIndex;
            while (k < count) {
                a[k++] = items[i];
                i = inc(i);
            }
            return a;
        } finally {
            lock.unlock();
        }
    }

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

            int k = 0;
            int i = takeIndex;
            while (k < count) {
                a[k++] = (T)items[i];
                i = inc(i);
            }
            if (a.length > count)
                a[count] = null;
            return a;
        } finally {
            lock.unlock();
        }
    }

    public String toString() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return super.toString();
        } finally {
            lock.unlock();
        }
    }


    public void clear() {
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = takeIndex;
            int k = count;
            while (k-- > 0) {
                items[i] = null;
                i = inc(i);
            }
            count = 0;
            putIndex = 0;
            takeIndex = 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();
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = takeIndex;
            int n = 0;
            int max = count;
            while (n < max) {
                c.add(items[i]);
                items[i] = null;
                i = inc(i);
                ++n;
            }
            if (n > 0) {
                count = 0;
                putIndex = 0;
                takeIndex = 0;
                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();
        if (maxElements <= 0)
            return 0;
        final E[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int i = takeIndex;
            int n = 0;
            int sz = count;
            int max = (maxElements < count)? maxElements : count;
            while (n < max) {
                c.add(items[i]);
                items[i] = null;
                i = inc(i);
                ++n;
            }
            if (n > 0) {
                count -= n;
                takeIndex = i;
                notFull.signalAll();
            }
            return n;
        } finally {
            lock.unlock();
        }
    }


    /**
     * 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() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return new Itr();
        } finally {
            lock.unlock();
        }
    }

    /**
     * Iterator for ArrayBlockingQueue
     */
    private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by next,
         * or a negative number if no such.
         */
        private int nextIndex;

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

        /**
         * Index of element returned by most recent call to next.
         * Reset to -1 if this element is deleted by a call to remove.
         */
        private int lastRet;

        Itr() {
            lastRet = -1;
            if (count == 0)
                nextIndex = -1;
            else {
                nextIndex = takeIndex;
                nextItem = items[takeIndex];
            }
        }

        public boolean hasNext() {
            /*
             * No sync. We can return true by mistake here
             * only if this iterator passed across threads,
             * which we don't support anyway.
             */
            return nextIndex >= 0;
        }

        /**
         * Check whether nextIndex is valid; if so setting nextItem.
         * Stops iterator when either hits putIndex or sees null item.
         */
        private void checkNext() {
            if (nextIndex == putIndex) {
                nextIndex = -1;
                nextItem = null;
            } else {
                nextItem = items[nextIndex];
                if (nextItem == null)
                    nextIndex = -1;
            }
        }

        public E next() {
            final ReentrantLock lock = ArrayBlockingQueue.this.lock;
            lock.lock();
            try {
                if (nextIndex < 0)
                    throw new NoSuchElementException();
                lastRet = nextIndex;
                E x = nextItem;
                nextIndex = inc(nextIndex);
                checkNext();
                return x;
            } finally {
                lock.unlock();
            }
        }

        public void remove() {
            final ReentrantLock lock = ArrayBlockingQueue.this.lock;
            lock.lock();
            try {
                int i = lastRet;
                if (i == -1)
                    throw new IllegalStateException();
                lastRet = -1;

                int ti = takeIndex;
                removeAt(i);
                // back up cursor (reset to front if was first element)
                nextIndex = (i == ti) ? takeIndex : i;
                checkNext();
            } finally {
                lock.unlock();
            }
        }
    }
}
Revision:	1.36
Committed:	Tue Dec 23 19:38:09 2003 UTC (20 years, 5 months ago) by dl
Branch:	MAIN
Changes since 1.35:	+49 -99 lines
Log Message:	cache finals across volatiles; avoid readResolve; doc improvments; timed invokeAll interleaves
#	User	Rev	Content
1	dl	1.2	/*
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	tim	1.1	package java.util.concurrent;
8	dl	1.11	import java.util.concurrent.locks.*;
9	tim	1.1	import java.util.*;
10
11			/**
12	dl	1.25	* A bounded {@linkplain BlockingQueue blocking queue} backed by an
13			* array. This queue orders elements FIFO (first-in-first-out). The
14			* <em>head</em> of the queue is that element that has been on the
15			* queue the longest time. The <em>tail</em> of the queue is that
16			* element that has been on the queue the shortest time. New elements
17			* are inserted at the tail of the queue, and the queue retrieval
18			* operations obtain elements at the head of the queue.
19	dholmes	1.13	*
20	tim	1.15	* <p>This is a classic "bounded buffer", in which a fixed-sized
21	dholmes	1.13	* array holds
22	dl	1.11	* elements inserted by producers and extracted by consumers. Once
23			* created, the capacity can not be increased. Attempts to offer an
24			* element to a full queue will result in the offer operation
25			* blocking; attempts to retrieve an element from an empty queue will
26	tim	1.12	* similarly block.
27	dl	1.11	*
28			* <p> This class supports an optional fairness policy for ordering
29			* threads blocked on an insertion or removal. By default, this
30			* ordering is not guaranteed. However, an <tt>ArrayBlockingQueue</tt>
31			* constructed with fairness set to <tt>true</tt> grants blocked
32	dl	1.25	* threads access in FIFO order. Fairness generally decreases
33	dl	1.29	* throughput but reduces variability and avoids starvation.
34	brian	1.7	*
35	dl	1.26	* <p>This class implements all of the <em>optional</em> methods
36			* of the {@link Collection} and {@link Iterator} interfaces.
37			*
38	dl	1.8	* @since 1.5
39			* @author Doug Lea
40	dl	1.33	* @param <E> the type of elements held in this collection
41	dl	1.8	*/
42	dl	1.5	public class ArrayBlockingQueue<E> extends AbstractQueue<E>
43	tim	1.1	implements BlockingQueue<E>, java.io.Serializable {
44
45	dl	1.36	/**
46			* Seialization ID. This class relies on default serialzation even
47			* for the items array is default-serialized, even if it is
48			* empty. Otherwise it could not be declared final, which is
49			* necessary here.
50			*/
51			private static final long serialVersionUID = -817911632652898426L;
52
53			/** The queued items */
54			private final E[] items;
55	dl	1.8	/** items index for next take, poll or remove */
56	tim	1.12	private transient int takeIndex;
57	dl	1.8	/** items index for next put, offer, or add. */
58	tim	1.12	private transient int putIndex;
59	dl	1.8	/** Number of items in the queue */
60	dl	1.5	private int count;
61	tim	1.12
62	dl	1.5	/*
63	dl	1.36	* Concurrency control uses the classic two-condition algorithm
64	dl	1.5	* found in any textbook.
65			*/
66
67	dl	1.11	/** Main lock guarding all access */
68			private final ReentrantLock lock;
69	dholmes	1.13	/** Condition for waiting takes */
70	dl	1.31	private final ReentrantLock.ConditionObject notEmpty;
71	dl	1.35	/** Condition for waiting puts */
72	dl	1.31	private final ReentrantLock.ConditionObject notFull;
73	dl	1.5
74			// Internal helper methods
75
76			/**
77			* Circularly increment i.
78			*/
79			int inc(int i) {
80			return (++i == items.length)? 0 : i;
81			}
82
83			/**
84	dl	1.9	* Insert element at current put position, advance, and signal.
85			* Call only when holding lock.
86	dl	1.5	*/
87			private void insert(E x) {
88			items[putIndex] = x;
89			putIndex = inc(putIndex);
90			++count;
91	dl	1.9	notEmpty.signal();
92	tim	1.1	}
93	tim	1.12
94	dl	1.5	/**
95	dl	1.9	* Extract element at current take position, advance, and signal.
96			* Call only when holding lock.
97	dl	1.5	*/
98	dholmes	1.13	private E extract() {
99	dl	1.36	final E[] items = this.items;
100	dl	1.5	E x = items[takeIndex];
101			items[takeIndex] = null;
102			takeIndex = inc(takeIndex);
103			--count;
104	dl	1.9	notFull.signal();
105	dl	1.5	return x;
106			}
107
108			/**
109	tim	1.12	* Utility for remove and iterator.remove: Delete item at position i.
110	dl	1.9	* Call only when holding lock.
111	dl	1.5	*/
112			void removeAt(int i) {
113	dl	1.36	final E[] items = this.items;
114	dl	1.9	// if removing front item, just advance
115			if (i == takeIndex) {
116			items[takeIndex] = null;
117			takeIndex = inc(takeIndex);
118	tim	1.23	} else {
119	dl	1.9	// slide over all others up through putIndex.
120			for (;;) {
121			int nexti = inc(i);
122			if (nexti != putIndex) {
123			items[i] = items[nexti];
124			i = nexti;
125	tim	1.23	} else {
126	dl	1.9	items[i] = null;
127			putIndex = i;
128			break;
129			}
130	dl	1.5	}
131			}
132	dl	1.9	--count;
133			notFull.signal();
134	tim	1.1	}
135
136			/**
137	dholmes	1.21	* Creates an <tt>ArrayBlockingQueue</tt> with the given (fixed)
138	dholmes	1.13	* capacity and default access policy.
139			* @param capacity the capacity of this queue
140	dholmes	1.16	* @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
141	dl	1.5	*/
142	dholmes	1.13	public ArrayBlockingQueue(int capacity) {
143	dl	1.36	this(capacity, false);
144	dl	1.5	}
145	dl	1.2
146	dl	1.5	/**
147	dholmes	1.21	* Creates an <tt>ArrayBlockingQueue</tt> with the given (fixed)
148	dholmes	1.13	* capacity and the specified access policy.
149			* @param capacity the capacity of this queue
150			* @param fair if <tt>true</tt> then queue accesses for threads blocked
151			* on insertion or removal, are processed in FIFO order; if <tt>false</tt>
152			* the access order is unspecified.
153	dholmes	1.16	* @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
154	dl	1.11	*/
155	dholmes	1.13	public ArrayBlockingQueue(int capacity, boolean fair) {
156	dl	1.36	if (capacity <= 0)
157			throw new IllegalArgumentException();
158			this.items = (E[]) new Object[capacity];
159			lock = new ReentrantLock(fair);
160			notEmpty = lock.newCondition();
161			notFull = lock.newCondition();
162	dl	1.5	}
163
164	dholmes	1.16	/**
165	dholmes	1.21	* Creates an <tt>ArrayBlockingQueue</tt> with the given (fixed)
166			* capacity, the specified access policy and initially containing the
167	tim	1.17	* elements of the given collection,
168	dholmes	1.16	* added in traversal order of the collection's iterator.
169			* @param capacity the capacity of this queue
170			* @param fair if <tt>true</tt> then queue accesses for threads blocked
171			* on insertion or removal, are processed in FIFO order; if <tt>false</tt>
172			* the access order is unspecified.
173			* @param c the collection of elements to initially contain
174			* @throws IllegalArgumentException if <tt>capacity</tt> is less than
175			* <tt>c.size()</tt>, or less than 1.
176			* @throws NullPointerException if <tt>c</tt> or any element within it
177			* is <tt>null</tt>
178			*/
179	tim	1.20	public ArrayBlockingQueue(int capacity, boolean fair,
180	dholmes	1.18	Collection<? extends E> c) {
181	dl	1.36	this(capacity, fair);
182	dholmes	1.16	if (capacity < c.size())
183			throw new IllegalArgumentException();
184
185	tim	1.20	for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
186			add(it.next());
187	dholmes	1.16	}
188	dl	1.2
189	dholmes	1.13	/**
190	dholmes	1.27	* Inserts the specified element at the tail of this queue if possible,
191			* returning immediately if this queue is full.
192	dl	1.25	*
193	dl	1.28	* @param o the element to add.
194			* @return <tt>true</tt> if it was possible to add the element to
195			* this queue, else <tt>false</tt>
196	dl	1.25	* @throws NullPointerException if the specified element is <tt>null</tt>
197	dholmes	1.13	*/
198	dholmes	1.21	public boolean offer(E o) {
199			if (o == null) throw new NullPointerException();
200	dl	1.36	final ReentrantLock lock = this.lock;
201	dl	1.5	lock.lock();
202			try {
203	tim	1.12	if (count == items.length)
204	dl	1.2	return false;
205	dl	1.5	else {
206	dholmes	1.21	insert(o);
207	dl	1.5	return true;
208			}
209	tim	1.23	} finally {
210	tim	1.12	lock.unlock();
211	dl	1.2	}
212	dl	1.5	}
213	dl	1.2
214	dholmes	1.13	/**
215	dholmes	1.27	* Inserts the specified element at the tail of this queue, waiting if
216	dholmes	1.13	* necessary up to the specified wait time for space to become available.
217	dl	1.28	* @param o the element to add
218			* @param timeout how long to wait before giving up, in units of
219			* <tt>unit</tt>
220			* @param unit a <tt>TimeUnit</tt> determining how to interpret the
221			* <tt>timeout</tt> parameter
222			* @return <tt>true</tt> if successful, or <tt>false</tt> if
223			* the specified waiting time elapses before space is available.
224			* @throws InterruptedException if interrupted while waiting.
225	dl	1.25	* @throws NullPointerException if the specified element is <tt>null</tt>.
226	brian	1.7	*/
227	dholmes	1.21	public boolean offer(E o, long timeout, TimeUnit unit)
228	dholmes	1.13	throws InterruptedException {
229	dl	1.2
230	dholmes	1.21	if (o == null) throw new NullPointerException();
231	dl	1.36	final ReentrantLock lock = this.lock;
232	dl	1.5	lock.lockInterruptibly();
233			try {
234	dholmes	1.13	long nanos = unit.toNanos(timeout);
235	dl	1.5	for (;;) {
236			if (count != items.length) {
237	dholmes	1.21	insert(o);
238	dl	1.5	return true;
239			}
240			if (nanos <= 0)
241			return false;
242			try {
243			nanos = notFull.awaitNanos(nanos);
244	tim	1.23	} catch (InterruptedException ie) {
245	dl	1.5	notFull.signal(); // propagate to non-interrupted thread
246			throw ie;
247			}
248			}
249	tim	1.23	} finally {
250	dl	1.5	lock.unlock();
251	dl	1.2	}
252	dl	1.5	}
253	dl	1.2
254	dholmes	1.13
255			public E poll() {
256	dl	1.36	final ReentrantLock lock = this.lock;
257	dholmes	1.13	lock.lock();
258			try {
259			if (count == 0)
260			return null;
261			E x = extract();
262			return x;
263	tim	1.23	} finally {
264	tim	1.15	lock.unlock();
265	dholmes	1.13	}
266			}
267
268	dl	1.5	public E poll(long timeout, TimeUnit unit) throws InterruptedException {
269	dl	1.36	final ReentrantLock lock = this.lock;
270	dl	1.5	lock.lockInterruptibly();
271			try {
272	dholmes	1.13	long nanos = unit.toNanos(timeout);
273	dl	1.2	for (;;) {
274	dl	1.5	if (count != 0) {
275			E x = extract();
276			return x;
277	dl	1.2	}
278	dl	1.5	if (nanos <= 0)
279			return null;
280			try {
281			nanos = notEmpty.awaitNanos(nanos);
282	tim	1.23	} catch (InterruptedException ie) {
283	dl	1.5	notEmpty.signal(); // propagate to non-interrupted thread
284			throw ie;
285			}
286
287	dl	1.2	}
288	tim	1.23	} finally {
289	dl	1.5	lock.unlock();
290			}
291			}
292	dl	1.2
293	brian	1.7
294	dholmes	1.21	public boolean remove(Object o) {
295			if (o == null) return false;
296	dl	1.36	final E[] items = this.items;
297			final ReentrantLock lock = this.lock;
298	dl	1.5	lock.lock();
299			try {
300			int i = takeIndex;
301			int k = 0;
302			for (;;) {
303			if (k++ >= count)
304			return false;
305	dholmes	1.21	if (o.equals(items[i])) {
306	dl	1.5	removeAt(i);
307			return true;
308			}
309	dl	1.2	i = inc(i);
310	dl	1.5	}
311	tim	1.12
312	tim	1.23	} finally {
313	dl	1.5	lock.unlock();
314			}
315			}
316	brian	1.7
317	dholmes	1.13	public E peek() {
318	dl	1.36	final ReentrantLock lock = this.lock;
319	dholmes	1.13	lock.lock();
320			try {
321			return (count == 0) ? null : items[takeIndex];
322	tim	1.23	} finally {
323	dholmes	1.13	lock.unlock();
324			}
325			}
326
327			public E take() throws InterruptedException {
328	dl	1.36	final ReentrantLock lock = this.lock;
329	dholmes	1.13	lock.lockInterruptibly();
330			try {
331			try {
332			while (count == 0)
333			notEmpty.await();
334	tim	1.23	} catch (InterruptedException ie) {
335	dholmes	1.13	notEmpty.signal(); // propagate to non-interrupted thread
336			throw ie;
337			}
338			E x = extract();
339			return x;
340	tim	1.23	} finally {
341	dholmes	1.13	lock.unlock();
342			}
343			}
344
345			/**
346	dholmes	1.21	* Adds the specified element to the tail of this queue, waiting if
347	dholmes	1.13	* necessary for space to become available.
348	dl	1.28	* @param o the element to add
349			* @throws InterruptedException if interrupted while waiting.
350	dl	1.25	* @throws NullPointerException if the specified element is <tt>null</tt>.
351	dholmes	1.13	*/
352	dholmes	1.21	public void put(E o) throws InterruptedException {
353			if (o == null) throw new NullPointerException();
354	dl	1.36	final E[] items = this.items;
355			final ReentrantLock lock = this.lock;
356	dholmes	1.13	lock.lockInterruptibly();
357			try {
358			try {
359			while (count == items.length)
360			notFull.await();
361	tim	1.23	} catch (InterruptedException ie) {
362	dholmes	1.13	notFull.signal(); // propagate to non-interrupted thread
363			throw ie;
364			}
365	dholmes	1.21	insert(o);
366	tim	1.23	} finally {
367	dholmes	1.13	lock.unlock();
368			}
369			}
370
371			// this doc comment is overridden to remove the reference to collections
372			// greater in size than Integer.MAX_VALUE
373	tim	1.15	/**
374	dl	1.25	* Returns the number of elements in this queue.
375			*
376			* @return the number of elements in this queue.
377	dholmes	1.13	*/
378			public int size() {
379	dl	1.36	final ReentrantLock lock = this.lock;
380	dholmes	1.13	lock.lock();
381			try {
382			return count;
383	tim	1.23	} finally {
384	dholmes	1.13	lock.unlock();
385			}
386			}
387
388			// this doc comment is a modified copy of the inherited doc comment,
389			// without the reference to unlimited queues.
390	tim	1.15	/**
391	dholmes	1.21	* Returns the number of elements that this queue can ideally (in
392	dholmes	1.13	* the absence of memory or resource constraints) accept without
393			* blocking. This is always equal to the initial capacity of this queue
394			* less the current <tt>size</tt> of this queue.
395			* <p>Note that you <em>cannot</em> always tell if
396			* an attempt to <tt>add</tt> an element will succeed by
397			* inspecting <tt>remainingCapacity</tt> because it may be the
398			* case that a waiting consumer is ready to <tt>take</tt> an
399			* element out of an otherwise full queue.
400			*/
401			public int remainingCapacity() {
402	dl	1.36	final ReentrantLock lock = this.lock;
403	dholmes	1.13	lock.lock();
404			try {
405			return items.length - count;
406	tim	1.23	} finally {
407	dholmes	1.13	lock.unlock();
408			}
409			}
410
411
412	dholmes	1.21	public boolean contains(Object o) {
413			if (o == null) return false;
414	dl	1.36	final E[] items = this.items;
415			final ReentrantLock lock = this.lock;
416	dl	1.5	lock.lock();
417			try {
418			int i = takeIndex;
419			int k = 0;
420			while (k++ < count) {
421	dholmes	1.21	if (o.equals(items[i]))
422	dl	1.2	return true;
423	dl	1.5	i = inc(i);
424			}
425	dl	1.2	return false;
426	tim	1.23	} finally {
427	dl	1.5	lock.unlock();
428			}
429			}
430	brian	1.7
431	dl	1.5	public Object[] toArray() {
432	dl	1.36	final E[] items = this.items;
433			final ReentrantLock lock = this.lock;
434	dl	1.5	lock.lock();
435			try {
436	dl	1.34	Object[] a = new Object[count];
437	dl	1.5	int k = 0;
438			int i = takeIndex;
439			while (k < count) {
440	dl	1.2	a[k++] = items[i];
441	dl	1.5	i = inc(i);
442			}
443	dl	1.2	return a;
444	tim	1.23	} finally {
445	dl	1.5	lock.unlock();
446			}
447			}
448	brian	1.7
449	dl	1.5	public <T> T[] toArray(T[] a) {
450	dl	1.36	final E[] items = this.items;
451			final ReentrantLock lock = this.lock;
452	dl	1.5	lock.lock();
453			try {
454			if (a.length < count)
455	dholmes	1.16	a = (T[])java.lang.reflect.Array.newInstance(
456	tim	1.17	a.getClass().getComponentType(),
457	dholmes	1.16	count
458			);
459	tim	1.12
460	dl	1.5	int k = 0;
461			int i = takeIndex;
462			while (k < count) {
463	dl	1.2	a[k++] = (T)items[i];
464	dl	1.5	i = inc(i);
465			}
466			if (a.length > count)
467			a[count] = null;
468	dl	1.2	return a;
469	tim	1.23	} finally {
470	dl	1.5	lock.unlock();
471			}
472			}
473	dl	1.6
474			public String toString() {
475	dl	1.36	final ReentrantLock lock = this.lock;
476	dl	1.6	lock.lock();
477			try {
478			return super.toString();
479	tim	1.23	} finally {
480	dl	1.6	lock.unlock();
481			}
482			}
483	tim	1.12
484	dl	1.30
485			public void clear() {
486	dl	1.36	final E[] items = this.items;
487			final ReentrantLock lock = this.lock;
488	dl	1.30	lock.lock();
489			try {
490			int i = takeIndex;
491			int k = count;
492			while (k-- > 0) {
493			items[i] = null;
494			i = inc(i);
495			}
496			count = 0;
497			putIndex = 0;
498			takeIndex = 0;
499			notFull.signalAll();
500			} finally {
501			lock.unlock();
502			}
503			}
504
505			public int drainTo(Collection<? super E> c) {
506			if (c == null)
507			throw new NullPointerException();
508			if (c == this)
509			throw new IllegalArgumentException();
510	dl	1.36	final E[] items = this.items;
511			final ReentrantLock lock = this.lock;
512	dl	1.30	lock.lock();
513			try {
514			int i = takeIndex;
515			int n = 0;
516			int max = count;
517			while (n < max) {
518			c.add(items[i]);
519			items[i] = null;
520			i = inc(i);
521			++n;
522			}
523			if (n > 0) {
524			count = 0;
525			putIndex = 0;
526			takeIndex = 0;
527			notFull.signalAll();
528			}
529			return n;
530			} finally {
531			lock.unlock();
532			}
533			}
534
535
536			public int drainTo(Collection<? super E> c, int maxElements) {
537			if (c == null)
538			throw new NullPointerException();
539			if (c == this)
540			throw new IllegalArgumentException();
541			if (maxElements <= 0)
542			return 0;
543	dl	1.36	final E[] items = this.items;
544			final ReentrantLock lock = this.lock;
545	dl	1.30	lock.lock();
546			try {
547			int i = takeIndex;
548			int n = 0;
549			int sz = count;
550			int max = (maxElements < count)? maxElements : count;
551			while (n < max) {
552			c.add(items[i]);
553			items[i] = null;
554			i = inc(i);
555			++n;
556			}
557			if (n > 0) {
558			count -= n;
559			takeIndex = i;
560			notFull.signalAll();
561			}
562			return n;
563			} finally {
564			lock.unlock();
565			}
566			}
567
568
569	brian	1.7	/**
570			* Returns an iterator over the elements in this queue in proper sequence.
571	dl	1.22	* The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
572			* will never throw {@link java.util.ConcurrentModificationException},
573			* and guarantees to traverse elements as they existed upon
574			* construction of the iterator, and may (but is not guaranteed to)
575			* reflect any modifications subsequent to construction.
576	brian	1.7	*
577			* @return an iterator over the elements in this queue in proper sequence.
578			*/
579	dl	1.5	public Iterator<E> iterator() {
580	dl	1.36	final ReentrantLock lock = this.lock;
581	dl	1.5	lock.lock();
582			try {
583	dl	1.2	return new Itr();
584	tim	1.23	} finally {
585	dl	1.5	lock.unlock();
586			}
587			}
588	dl	1.8
589			/**
590			* Iterator for ArrayBlockingQueue
591			*/
592	dl	1.5	private class Itr implements Iterator<E> {
593			/**
594			* Index of element to be returned by next,
595			* or a negative number if no such.
596			*/
597	dl	1.8	private int nextIndex;
598	dl	1.2
599	tim	1.12	/**
600	dl	1.5	* nextItem holds on to item fields because once we claim
601			* that an element exists in hasNext(), we must return it in
602			* the following next() call even if it was in the process of
603			* being removed when hasNext() was called.
604			**/
605	dl	1.8	private E nextItem;
606	dl	1.5
607			/**
608			* Index of element returned by most recent call to next.
609			* Reset to -1 if this element is deleted by a call to remove.
610			*/
611	dl	1.8	private int lastRet;
612	tim	1.12
613	dl	1.5	Itr() {
614			lastRet = -1;
615	tim	1.12	if (count == 0)
616	dl	1.5	nextIndex = -1;
617			else {
618			nextIndex = takeIndex;
619			nextItem = items[takeIndex];
620			}
621			}
622	tim	1.12
623	dl	1.5	public boolean hasNext() {
624			/*
625			* No sync. We can return true by mistake here
626			* only if this iterator passed across threads,
627			* which we don't support anyway.
628	dl	1.2	*/
629	dl	1.5	return nextIndex >= 0;
630			}
631
632			/**
633	dholmes	1.13	* Check whether nextIndex is valid; if so setting nextItem.
634	dl	1.5	* Stops iterator when either hits putIndex or sees null item.
635			*/
636			private void checkNext() {
637			if (nextIndex == putIndex) {
638			nextIndex = -1;
639			nextItem = null;
640	tim	1.23	} else {
641	dl	1.5	nextItem = items[nextIndex];
642			if (nextItem == null)
643			nextIndex = -1;
644	dl	1.2	}
645	dl	1.5	}
646	tim	1.12
647	dl	1.5	public E next() {
648	dl	1.36	final ReentrantLock lock = ArrayBlockingQueue.this.lock;
649	dl	1.5	lock.lock();
650			try {
651			if (nextIndex < 0)
652	dl	1.2	throw new NoSuchElementException();
653	dl	1.5	lastRet = nextIndex;
654			E x = nextItem;
655			nextIndex = inc(nextIndex);
656			checkNext();
657			return x;
658	tim	1.23	} finally {
659	tim	1.12	lock.unlock();
660	dl	1.2	}
661	dl	1.5	}
662	tim	1.12
663	dl	1.5	public void remove() {
664	dl	1.36	final ReentrantLock lock = ArrayBlockingQueue.this.lock;
665	dl	1.5	lock.lock();
666			try {
667	dl	1.2	int i = lastRet;
668			if (i == -1)
669			throw new IllegalStateException();
670			lastRet = -1;
671	tim	1.12
672	dl	1.9	int ti = takeIndex;
673	dl	1.2	removeAt(i);
674	dl	1.9	// back up cursor (reset to front if was first element)
675	tim	1.12	nextIndex = (i == ti) ? takeIndex : i;
676	dl	1.5	checkNext();
677	tim	1.23	} finally {
678	dl	1.5	lock.unlock();
679			}
680			}
681	tim	1.1	}
682			}