0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 0N/A * This file is available under and governed by the GNU General Public 0N/A * License version 2 only, as published by the Free Software Foundation. 0N/A * However, the following notice accompanied the original version of this 0N/A * Written by Doug Lea with assistance from members of JCP JSR-166 0N/A * Expert Group and released to the public domain, as explained at 0N/A * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on 0N/A * <p> The optional capacity bound constructor argument serves as a 0N/A * way to prevent excessive expansion. The capacity, if unspecified, 0N/A * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 0N/A * dynamically created upon each insertion unless this would bring the 0N/A * deque above capacity. 0N/A * <p>Most operations run in constant time (ignoring time spent 0N/A * blocking). Exceptions include {@link #remove(Object) remove}, 0N/A * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link 0N/A * #removeLastOccurrence removeLastOccurrence}, {@link #contains 0N/A * contains}, {@link #iterator iterator.remove()}, and the bulk 0N/A * operations, all of which run in linear time. 0N/A * <p>This class and its iterator implement all of the 0N/A * <em>optional</em> methods of the {@link Collection} and {@link 0N/A * Iterator} interfaces. 0N/A * <p>This class is a member of the 0N/A * Java Collections Framework</a>. 0N/A * @param <E> the type of elements held in this collection 0N/A * Implemented as a simple doubly-linked list protected by a 0N/A * single lock and using conditions to manage blocking. 1468N/A * To implement weakly consistent iterators, it appears we need to 1468N/A * keep all Nodes GC-reachable from a predecessor dequeued Node. 1468N/A * That would cause two problems: 1468N/A * - allow a rogue Iterator to cause unbounded memory retention 1468N/A * - cause cross-generational linking of old Nodes to new Nodes if 1468N/A * a Node was tenured while live, which generational GCs have a 1468N/A * hard time dealing with, causing repeated major collections. 1468N/A * However, only non-deleted Nodes need to be reachable from 1468N/A * dequeued Nodes, and reachability does not necessarily have to 1468N/A * be of the kind understood by the GC. We use the trick of 1468N/A * linking a Node that has just been dequeued to itself. Such a 1468N/A * self-link implicitly means to jump to "first" (for next links) 1468N/A * or "last" (for prev links). 0N/A * here, and that introduces ambiguities. Often we want the 0N/A * BlockingDeque javadoc combined with the AbstractQueue 0N/A * implementation, so a lot of method specs are duplicated here. 0N/A /** Doubly-linked list node class */ 1468N/A * The item, or null if this node has been removed. 1468N/A * - the real predecessor Node 1468N/A * - this Node, meaning the predecessor is tail 1468N/A * - null, meaning there is no predecessor 1468N/A * - the real successor Node 1468N/A * - this Node, meaning the successor is head 1468N/A * - null, meaning there is no successor 1468N/A * Invariant: (first == null && last == null) || 1468N/A * (first.prev == null && first.item != null) 1468N/A * Invariant: (first == null && last == null) || 1468N/A * (last.next == null && last.item != null) 0N/A /** Number of items in the deque */ 0N/A /** Maximum number of items in the deque */ 0N/A /** Main lock guarding all access */ 0N/A /** Condition for waiting takes */ 0N/A /** Condition for waiting puts */ 1468N/A * Creates a {@code LinkedBlockingDeque} with a capacity of 0N/A * {@link Integer#MAX_VALUE}. 1468N/A * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity. 0N/A * @param capacity the capacity of this deque 1468N/A * @throws IllegalArgumentException if {@code capacity} is less than 1 1468N/A * Creates a {@code LinkedBlockingDeque} with a capacity of 0N/A * {@link Integer#MAX_VALUE}, initially containing the elements of 0N/A * the given collection, added in traversal order of the 0N/A * collection's iterator. 0N/A * @param c the collection of elements to initially contain 0N/A * @throws NullPointerException if the specified collection or any 0N/A * of its elements are null 0N/A // Basic linking and unlinking operations, called only while holding lock 3059N/A * Links node as first element, or returns false if full. 1468N/A // assert lock.isHeldByCurrentThread(); 3059N/A * Links node as last element, or returns false if full. 1468N/A // assert lock.isHeldByCurrentThread(); 0N/A * Removes and returns first element, or null if empty. 1468N/A // assert lock.isHeldByCurrentThread(); 0N/A * Removes and returns last element, or null if empty. 1468N/A // assert lock.isHeldByCurrentThread(); 1468N/A // assert lock.isHeldByCurrentThread(); 1468N/A // Don't mess with x's links. They may still be in use by 0N/A // BlockingDeque methods 0N/A * @throws IllegalStateException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws IllegalStateException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NoSuchElementException {@inheritDoc} 0N/A * @throws NoSuchElementException {@inheritDoc} 0N/A * @throws NoSuchElementException {@inheritDoc} 0N/A * @throws NoSuchElementException {@inheritDoc} 0N/A // BlockingQueue methods 0N/A * Inserts the specified element at the end of this deque unless it would 0N/A * violate capacity restrictions. When using a capacity-restricted deque, 0N/A * it is generally preferable to use method {@link #offer(Object) offer}. 0N/A * <p>This method is equivalent to {@link #addLast}. 0N/A * @throws IllegalStateException if the element cannot be added at this 0N/A * time due to capacity restrictions 0N/A * @throws NullPointerException if the specified element is null 0N/A * @throws NullPointerException if the specified element is null 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * Retrieves and removes the head of the queue represented by this deque. 0N/A * This method differs from {@link #poll poll} only in that it throws an 0N/A * exception if this deque is empty. 0N/A * <p>This method is equivalent to {@link #removeFirst() removeFirst}. 0N/A * @return the head of the queue represented by this deque 0N/A * @throws NoSuchElementException if this deque is empty 0N/A * Retrieves, but does not remove, the head of the queue represented by 0N/A * this deque. This method differs from {@link #peek peek} only in that 0N/A * it throws an exception if this deque is empty. 0N/A * <p>This method is equivalent to {@link #getFirst() getFirst}. 0N/A * @return the head of the queue represented by this deque 0N/A * @throws NoSuchElementException if this deque is empty 0N/A * Returns the number of additional elements that this deque can ideally 0N/A * (in the absence of memory or resource constraints) accept without 0N/A * blocking. This is always equal to the initial capacity of this deque 1468N/A * less the current {@code size} of this deque. 0N/A * <p>Note that you <em>cannot</em> always tell if an attempt to insert 1468N/A * an element will succeed by inspecting {@code remainingCapacity} 0N/A * because it may be the case that another thread is about to 0N/A * insert or remove an element. 0N/A * @throws UnsupportedOperationException {@inheritDoc} 0N/A * @throws ClassCastException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws IllegalArgumentException {@inheritDoc} 0N/A * @throws UnsupportedOperationException {@inheritDoc} 0N/A * @throws ClassCastException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws IllegalArgumentException {@inheritDoc} 1468N/A for (
int i =
0; i < n; i++) {
0N/A * @throws IllegalStateException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * @throws NoSuchElementException {@inheritDoc} 0N/A // Collection methods 0N/A * Removes the first occurrence of the specified element from this deque. 0N/A * If the deque does not contain the element, it is unchanged. 1468N/A * More formally, removes the first element {@code e} such that 1468N/A * {@code o.equals(e)} (if such an element exists). 1468N/A * Returns {@code true} if this deque contained the specified element 0N/A * (or equivalently, if this deque changed as a result of the call). 0N/A * <p>This method is equivalent to 0N/A * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. 0N/A * @param o element to be removed from this deque, if present 1468N/A * @return {@code true} if this deque changed as a result of the call 0N/A * Returns the number of elements in this deque. 0N/A * @return the number of elements in this deque 1468N/A * Returns {@code true} if this deque contains the specified element. 1468N/A * More formally, returns {@code true} if and only if this deque contains 1468N/A * at least one element {@code e} such that {@code o.equals(e)}. 0N/A * @param o object to be checked for containment in this deque 1468N/A * @return {@code true} if this deque contains the specified element 1468N/A * TODO: Add support for more efficient bulk operations. 1468N/A * We don't want to acquire the lock for every iteration, but we 1468N/A * also want other threads a chance to interact with the 1468N/A * collection, especially when count is close to capacity. 1468N/A// * Adds all of the elements in the specified collection to this 1468N/A// * queue. Attempts to addAll of a queue to itself result in 1468N/A// * {@code IllegalArgumentException}. Further, the behavior of 1468N/A// * this operation is undefined if the specified collection is 1468N/A// * modified while the operation is in progress. 1468N/A// * @param c collection containing elements to be added to this queue 1468N/A// * @return {@code true} if this queue changed as a result of the call 1468N/A// * @throws ClassCastException {@inheritDoc} 1468N/A// * @throws NullPointerException {@inheritDoc} 1468N/A// * @throws IllegalArgumentException {@inheritDoc} 1468N/A// * @throws IllegalStateException {@inheritDoc} 1468N/A// public boolean addAll(Collection<? extends E> c) { 1468N/A// throw new NullPointerException(); 1468N/A// throw new IllegalArgumentException(); 1468N/A// final ReentrantLock lock = this.lock; 1468N/A// boolean modified = false; 0N/A * Returns an array containing all of the elements in this deque, in 0N/A * proper sequence (from first to last element). 0N/A * <p>The returned array will be "safe" in that no references to it are 0N/A * maintained by this deque. (In other words, this method must allocate 0N/A * a new array). The caller is thus free to modify the returned array. 0N/A * <p>This method acts as bridge between array-based and collection-based 0N/A * @return an array containing all of the elements in this deque 0N/A * Returns an array containing all of the elements in this deque, in 0N/A * proper sequence; the runtime type of the returned array is that of 0N/A * the specified array. If the deque fits in the specified array, it 0N/A * is returned therein. Otherwise, a new array is allocated with the 0N/A * runtime type of the specified array and the size of this deque. 0N/A * <p>If this deque fits in the specified array with room to spare 0N/A * (i.e., the array has more elements than this deque), the element in 0N/A * the array immediately following the end of the deque is set to 0N/A * <p>Like the {@link #toArray()} method, this method acts as bridge between 0N/A * array-based and collection-based APIs. Further, this method allows 0N/A * precise control over the runtime type of the output array, and may, 0N/A * under certain circumstances, be used to save allocation costs. 1468N/A * <p>Suppose {@code x} is a deque known to contain only strings. 0N/A * The following code can be used to dump the deque into a newly 1468N/A * allocated array of {@code String}: 0N/A * String[] y = x.toArray(new String[0]);</pre> 1468N/A * Note that {@code toArray(new Object[0])} is identical in function to 0N/A * @param a the array into which the elements of the deque are to 0N/A * be stored, if it is big enough; otherwise, a new array of the 0N/A * same runtime type is allocated for this purpose 0N/A * @return an array containing all of the elements in this deque 0N/A * @throws ArrayStoreException if the runtime type of the specified array 0N/A * is not a supertype of the runtime type of every element in 0N/A * @throws NullPointerException if the specified array is null 0N/A * Atomically removes all of the elements from this deque. 0N/A * The deque will be empty after this call returns. 0N/A * Returns an iterator over the elements in this deque in proper sequence. 0N/A * The elements will be returned in order from first (head) to last (tail). 3203N/A * <p>The returned iterator is a "weakly consistent" iterator that 1472N/A * will never throw {@link java.util.ConcurrentModificationException 3203N/A * ConcurrentModificationException}, and guarantees to traverse 3203N/A * elements as they existed upon construction of the iterator, and 3203N/A * may (but is not guaranteed to) reflect any modifications 3203N/A * subsequent to construction. 0N/A * @return an iterator over the elements in this deque in proper sequence 0N/A * Returns an iterator over the elements in this deque in reverse 0N/A * sequential order. The elements will be returned in order from 0N/A * last (tail) to first (head). 3203N/A * <p>The returned iterator is a "weakly consistent" iterator that 1472N/A * will never throw {@link java.util.ConcurrentModificationException 3203N/A * ConcurrentModificationException}, and guarantees to traverse 3203N/A * elements as they existed upon construction of the iterator, and 3203N/A * may (but is not guaranteed to) reflect any modifications 3203N/A * subsequent to construction. 3387N/A * @return an iterator over the elements in this deque in reverse order 0N/A * Base class for Iterators for LinkedBlockingDeque 1468N/A * The next node to return in next() 0N/A * nextItem holds on to item fields because once we claim that 0N/A * an element exists in hasNext(), we must return item read 0N/A * under lock (in advance()) even if it was in the process of 0N/A * being removed when hasNext() was called. 0N/A * Node returned by most recent call to next. Needed by remove. 0N/A * Reset to null if this element is deleted by a call to remove. 3059N/A * Returns the successor node of the given non-null, but 3059N/A * possibly previously deleted, node. 3059N/A // Chains of deleted nodes ending in null or self-links 3059N/A // are possible if multiple interior nodes are removed. 0N/A * Save the state of this deque to a stream (that is, serialize it). 0N/A * @serialData The capacity (int), followed by elements (each an 1468N/A * {@code Object}) in the proper order, followed by a null 0N/A * @param s the stream 0N/A // Write out capacity and any hidden stuff 0N/A // Write out all elements in the proper order. 0N/A // Use trailing null as sentinel 0N/A * Reconstitute this deque from a stream (that is, 0N/A * @param s the stream 0N/A // Read in all elements and place in queue