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 BlockingQueue blocking queue} based on 0N/A * This queue orders elements FIFO (first-in-first-out). 0N/A * The <em>head</em> of the queue is that element that has been on the 0N/A * queue the longest time. 0N/A * The <em>tail</em> of the queue is that element that has been on the 0N/A * queue the shortest time. New elements 0N/A * are inserted at the tail of the queue, and the queue retrieval 0N/A * operations obtain elements at the head of the queue. 0N/A * Linked queues typically have higher throughput than array-based queues but 0N/A * less predictable performance in most concurrent applications. 0N/A * <p> The optional capacity bound constructor argument serves as a 0N/A * way to prevent excessive queue 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 * queue above capacity. 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 * A variant of the "two lock queue" algorithm. The putLock gates 0N/A * entry to put (and offer), and has an associated condition for 0N/A * waiting puts. Similarly for the takeLock. The "count" field 0N/A * that they both rely on is maintained as an atomic to avoid 0N/A * needing to get both locks in most cases. Also, to minimize need 0N/A * for puts to get takeLock and vice-versa, cascading notifies are 0N/A * used. When a put notices that it has enabled at least one take, 0N/A * it signals taker. That taker in turn signals others if more 0N/A * items have been entered since the signal. And symmetrically for 0N/A * takes signalling puts. Operations such as remove(Object) and 0N/A * iterators acquire both locks. 1468N/A * Visibility between writers and readers is provided as follows: 1468N/A * Whenever an element is enqueued, the putLock is acquired and 1468N/A * count updated. A subsequent reader guarantees visibility to the 1468N/A * enqueued Node by either acquiring the putLock (via fullyLock) 1468N/A * or by acquiring the takeLock, and then reading n = count.get(); 1468N/A * this gives visibility to the first n items. 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 advance to head.next. 0N/A * Linked list node class 1468N/A * - the real successor Node 1468N/A * - this Node, meaning the successor is head.next 1468N/A * - null, meaning there is no successor (this is the last node) 0N/A /** The capacity bound, or Integer.MAX_VALUE if none */ 0N/A /** Current number of elements */ 1468N/A * Invariant: head.item == null 1468N/A * Invariant: last.next == null 0N/A /** Lock held by take, poll, etc */ 0N/A /** Wait queue for waiting takes */ 0N/A /** Lock held by put, offer, etc */ 0N/A /** Wait queue for waiting puts */ 0N/A * Signals a waiting take. Called only from put/offer (which do not 0N/A * otherwise ordinarily lock takeLock.) 3387N/A * Links node at end of queue. 1468N/A // assert putLock.isHeldByCurrentThread(); 1468N/A // assert last.next == null; 1468N/A * Removes a node from head of queue. 1468N/A // assert takeLock.isHeldByCurrentThread(); 1468N/A // assert head.item == null; 0N/A * Lock to prevent both puts and takes. 0N/A * Unlock to allow both puts and takes. 1468N/A// * Tells whether both locks are held by current thread. 1468N/A// boolean isFullyLocked() { 1468N/A// return (putLock.isHeldByCurrentThread() && 1468N/A// takeLock.isHeldByCurrentThread()); 1468N/A * Creates a {@code LinkedBlockingQueue} with a capacity of 0N/A * {@link Integer#MAX_VALUE}. 1468N/A * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity. 0N/A * @param capacity the capacity of this queue 1468N/A * @throws IllegalArgumentException if {@code capacity} is not greater 1468N/A * Creates a {@code LinkedBlockingQueue} with a capacity of 0N/A * {@link Integer#MAX_VALUE}, initially containing the elements of the 0N/A * added in traversal order of the 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 // this doc comment is overridden to remove the reference to collections 0N/A // greater in size than Integer.MAX_VALUE 0N/A * Returns the number of elements in this queue. 0N/A * @return the number of elements in this queue 0N/A // this doc comment is a modified copy of the inherited doc comment, 0N/A // without the reference to unlimited queues. 0N/A * Returns the number of additional elements that this queue 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 queue 1468N/A * less the current {@code size} of this queue. 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 * Inserts the specified element at the tail of this queue, waiting if 0N/A * necessary for space to become available. 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 1468N/A // holding count negative to indicate failure unless set. 0N/A * Note that count is used in wait guard even though it is 0N/A * not protected by lock. This works because count can 0N/A * only decrease at this point (all other puts are shut 0N/A * out by lock), and we (or some other waiting put) are 1468N/A * signalled if it ever changes from capacity. Similarly 1468N/A * for all other uses of count in other wait guards. 0N/A * Inserts the specified element at the tail of this queue, waiting if 0N/A * necessary up to the specified wait time for space to become available. 1468N/A * @return {@code true} if successful, or {@code false} if 0N/A * the specified waiting time elapses before space is available. 0N/A * @throws InterruptedException {@inheritDoc} 0N/A * @throws NullPointerException {@inheritDoc} 0N/A * Inserts the specified element at the tail of this queue if it is 0N/A * possible to do so immediately without exceeding the queue's capacity, 1468N/A * returning {@code true} upon success and {@code false} if this queue 0N/A * When using a capacity-restricted queue, this method is generally 0N/A * preferable to method {@link BlockingQueue#add add}, which can fail to 0N/A * insert an element only by throwing an exception. 0N/A * @throws NullPointerException if the specified element is null 1468N/A * Unlinks interior Node p with predecessor trail. 1468N/A // p.next is not changed, to allow iterators that are 1468N/A // traversing p to maintain their weak-consistency guarantee. 0N/A * Removes a single instance of the specified element from this queue, 1468N/A * if it is present. More formally, removes an element {@code e} such 1468N/A * that {@code o.equals(e)}, if this queue contains one or more such 1468N/A * Returns {@code true} if this queue contained the specified element 0N/A * (or equivalently, if this queue changed as a result of the call). 0N/A * @param o element to be removed from this queue, if present 1468N/A * @return {@code true} if this queue changed as a result of the call 3387N/A * Returns {@code true} if this queue contains the specified element. 3387N/A * More formally, returns {@code true} if and only if this queue contains 3387N/A * at least one element {@code e} such that {@code o.equals(e)}. 3387N/A * @param o object to be checked for containment in this queue 3387N/A * @return {@code true} if this queue contains the specified element 0N/A * Returns an array containing all of the elements in this queue, in 0N/A * <p>The returned array will be "safe" in that no references to it are 0N/A * maintained by this queue. (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 queue 0N/A * Returns an array containing all of the elements in this queue, in 0N/A * proper sequence; the runtime type of the returned array is that of 0N/A * the specified array. If the queue 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 queue. 0N/A * <p>If this queue fits in the specified array with room to spare 0N/A * (i.e., the array has more elements than this queue), the element in 0N/A * the array immediately following the end of the queue 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 queue known to contain only strings. 0N/A * The following code can be used to dump the queue 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 queue 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 queue 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 queue. 0N/A * The queue will be empty after this call returns. 1468N/A // assert head.item == null && head.next == null; 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 // count.get provides visibility to first n Nodes 1468N/A // Restore invariants even if c.add() threw 0N/A * Returns an iterator over the elements in this queue in proper sequence. 3387N/A * The elements will be returned in order from first (head) to last (tail). 3387N/A * <p>The returned iterator is a "weakly consistent" iterator that 1472N/A * will never throw {@link java.util.ConcurrentModificationException 3387N/A * ConcurrentModificationException}, and guarantees to traverse 3387N/A * elements as they existed upon construction of the iterator, and 3387N/A * may (but is not guaranteed to) reflect any modifications 3387N/A * subsequent to construction. 0N/A * @return an iterator over the elements in this queue in proper sequence 1468N/A * Basic weakly-consistent iterator. At all times hold the next 0N/A * item to hand out so that if hasNext() reports true, we will 0N/A * still have it to return even if lost race with a take etc. 1595N/A * Returns the next live successor of p, or null if no such. 1595N/A * Unlike other traversal methods, iterators need to handle both: 1468N/A * - dequeued nodes (p.next == p) 1595N/A * - (possibly multiple) interior removed nodes (p.item == null) 0N/A * Save the state to a stream (that is, serialize it). 0N/A * @serialData The capacity is emitted (int), followed by all of 1468N/A * its elements (each an {@code Object}) in the proper order, 0N/A * followed by a null 0N/A * @param s the stream 0N/A // Write out any hidden stuff, plus capacity 0N/A // Write out all elements in the proper order. 0N/A // Use trailing null as sentinel 0N/A * Reconstitute this queue instance from a stream (that is, 0N/A * @param s the stream 0N/A // Read in capacity, and any hidden stuff 0N/A // Read in all elements and place in queue