1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent; 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 96232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.AbstractQueue; 106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Collection; 116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Iterator; 126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.NoSuchElementException; 13e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Spliterator; 14e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Spliterators; 15e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.concurrent.atomic.AtomicInteger; 16e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.concurrent.locks.Condition; 17e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.concurrent.locks.ReentrantLock; 18e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.function.Consumer; 198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson// BEGIN android-note 218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson// removed link to collections framework docs 228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson// END android-note 236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An optionally-bounded {@linkplain BlockingQueue blocking queue} based on 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * linked nodes. 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This queue orders elements FIFO (first-in-first-out). 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The <em>head</em> of the queue is that element that has been on the 29adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the longest time. 30adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The <em>tail</em> of the queue is that element that has been on the 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the shortest time. New elements 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * are inserted at the tail of the queue, and the queue retrieval 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operations obtain elements at the head of the queue. 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Linked queues typically have higher throughput than array-based queues but 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * less predictable performance in most concurrent applications. 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 3791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p>The optional capacity bound constructor argument serves as a 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * way to prevent excessive queue expansion. The capacity, if unspecified, 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 40adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * dynamically created upon each insertion unless this would bring the 41adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue above capacity. 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 43bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class and its iterator implement all of the 44bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 45bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Iterator} interfaces. 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 49e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param <E> the type of elements held in this queue 50bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class LinkedBlockingQueue<E> extends AbstractQueue<E> 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = -6903933977591709194L; 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * A variant of the "two lock queue" algorithm. The putLock gates 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * entry to put (and offer), and has an associated condition for 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting puts. Similarly for the takeLock. The "count" field 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * that they both rely on is maintained as an atomic to avoid 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * needing to get both locks in most cases. Also, to minimize need 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * for puts to get takeLock and vice-versa, cascading notifies are 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * used. When a put notices that it has enabled at least one take, 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * it signals taker. That taker in turn signals others if more 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * items have been entered since the signal. And symmetrically for 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * takes signalling puts. Operations such as remove(Object) and 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * iterators acquire both locks. 676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Visibility between writers and readers is provided as follows: 696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Whenever an element is enqueued, the putLock is acquired and 716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * count updated. A subsequent reader guarantees visibility to the 726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * enqueued Node by either acquiring the putLock (via fullyLock) 736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * or by acquiring the takeLock, and then reading n = count.get(); 746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this gives visibility to the first n items. 756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * To implement weakly consistent iterators, it appears we need to 776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * keep all Nodes GC-reachable from a predecessor dequeued Node. 786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * That would cause two problems: 796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a Node was tenured while live, which generational GCs have a 826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * hard time dealing with, causing repeated major collections. 836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * However, only non-deleted Nodes need to be reachable from 846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be of the kind understood by the GC. We use the trick of 866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linking a Node that has just been dequeued to itself. Such a 876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * self-link implicitly means to advance to head.next. 88bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 91e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Linked list node class. 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static class Node<E> { 946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item; 956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real successor Node 996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the successor is head.next 1006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no successor (this is the last node) 1016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> next; 1036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node(E x) { item = x; } 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** The capacity bound, or Integer.MAX_VALUE if none */ 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final int capacity; 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Current number of elements */ 111a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final AtomicInteger count = new AtomicInteger(); 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Head of linked list. 1156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: head.item == null 1166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson transient Node<E> head; 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Tail of linked list. 1216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: last.next == null 1226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient Node<E> last; 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Lock held by take, poll, etc */ 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReentrantLock takeLock = new ReentrantLock(); 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Wait queue for waiting takes */ 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notEmpty = takeLock.newCondition(); 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Lock held by put, offer, etc */ 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReentrantLock putLock = new ReentrantLock(); 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Wait queue for waiting puts */ 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notFull = putLock.newCondition(); 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 138bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Signals a waiting take. Called only from put/offer (which do not 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise ordinarily lock takeLock.) 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void signalNotEmpty() { 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 152bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Signals a waiting put. Called only from take/poll. 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void signalNotFull() { 155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node at end of queue. 1666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param node the node 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void enqueue(Node<E> node) { 1706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert putLock.isHeldByCurrentThread(); 1716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert last.next == null; 1728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = last.next = node; 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes a node from head of queue. 1776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the node 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E dequeue() { 1816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert takeLock.isHeldByCurrentThread(); 1826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert head.item == null; 183bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> h = head; 184bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> first = h.next; 1856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; // help GC 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project head = first; 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = first.item; 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project first.item = null; 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 19391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Locks to prevent both puts and takes. 194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void fullyLock() { 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 20191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Unlocks to allow both puts and takes. 202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void fullyUnlock() { 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// /** 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * Tells whether both locks are held by current thread. 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// */ 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// boolean isFullyLocked() { 2126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// return (putLock.isHeldByCurrentThread() && 2136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// takeLock.isHeldByCurrentThread()); 2146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with a capacity of 218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link Integer#MAX_VALUE}. 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue() { 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(Integer.MAX_VALUE); 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity. 226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 227bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param capacity the capacity of this queue 2286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException if {@code capacity} is not greater 229bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than zero 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue(int capacity) { 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (capacity <= 0) throw new IllegalArgumentException(); 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this.capacity = capacity; 234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = head = new Node<E>(null); 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 236adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with a capacity of 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link Integer#MAX_VALUE}, initially containing the elements of the 240adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * given collection, 241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 242bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 244bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 245bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue(Collection<? extends E> c) { 248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(Integer.MAX_VALUE); 2496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock putLock = this.putLock; 2506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLock.lock(); // Never contended, but necessary for visibility 2516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = 0; 2536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (E e : c) { 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) 2556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 2566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == capacity) 2576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Queue full"); 2588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(new Node<E>(e)); 2596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++n; 2606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count.set(n); 2626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 2636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLock.unlock(); 2646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is overridden to remove the reference to collections 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // greater in size than Integer.MAX_VALUE 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. 271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 272bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count.get(); 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is a modified copy of the inherited doc comment, 279adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // without the reference to unlimited queues. 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the number of additional elements that this queue can ideally 282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (in the absence of memory or resource constraints) accept without 283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking. This is always equal to the initial capacity of this queue 2846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * less the current {@code size} of this queue. 285bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 286bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 2876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 288bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * because it may be the case that another thread is about to 289bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert or remove an element. 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return capacity - count.get(); 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 296bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting if 297adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary for space to become available. 298bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 299bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 300bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 301adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 302bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) throws InterruptedException { 303bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 3046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Note: convention in all put/take/etc is to preset local var 3056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // holding count negative to indicate failure unless set. 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> node = new Node<E>(e); 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lockInterruptibly(); 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Note that count is used in wait guard even though it is 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not protected by lock. This works because count can 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * only decrease at this point (all other puts are shut 316adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * out by lock), and we (or some other waiting put) are 3176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * signalled if it ever changes from capacity. Similarly 3186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * for all other uses of count in other wait guards. 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 3206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == capacity) { 3216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(node); 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndIncrement(); 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c + 1 < capacity) 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 329adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 334adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified element at the tail of this queue, waiting if 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary up to the specified wait time for space to become available. 337bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 3386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if successful, or {@code false} if 33991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * the specified waiting time elapses before space is available 340bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 341bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 343bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 346bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 350adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lockInterruptibly(); 352adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == capacity) { 354e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 355adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 3566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(new Node<E>(e)); 3596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c = count.getAndIncrement(); 3606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c + 1 < capacity) 3616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 371bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 372bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 3736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * returning {@code true} upon success and {@code false} if this queue 374bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is full. 375bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * When using a capacity-restricted queue, this method is generally 376bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * preferable to method {@link BlockingQueue#add add}, which can fail to 377bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert an element only by throwing an exception. 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 379bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 381bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 382bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == capacity) 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 387a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> node = new Node<E>(e); 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() < capacity) { 3928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(node); 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndIncrement(); 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c + 1 < capacity) 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return c >= 0; 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E take() throws InterruptedException { 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x; 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lockInterruptibly(); 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 4126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == 0) { 4136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.await(); 414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x = dequeue(); 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndDecrement(); 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c > 1) 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == capacity) 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotFull(); 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll(long timeout, TimeUnit unit) throws InterruptedException { 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = null; 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 433adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lockInterruptibly(); 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 4356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == 0) { 436e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 4386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notEmpty.awaitNanos(nanos); 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x = dequeue(); 4416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c = count.getAndDecrement(); 4426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c > 1) 4436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.signal(); 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 447adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == capacity) 448adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotFull(); 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == 0) 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = null; 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 461adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() > 0) { 4626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x = dequeue(); 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndDecrement(); 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c > 1) 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == capacity) 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotFull(); 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == 0) 477adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 478adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 480adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 481e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (count.get() > 0) ? head.next.item : null; 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 487bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 4886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlinks interior Node p with predecessor trail. 4896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void unlink(Node<E> p, Node<E> trail) { 4916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert isFullyLocked(); 4926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // p.next is not changed, to allow iterators that are 4936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // traversing p to maintain their weak-consistency guarantee. 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 4956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail.next = p.next; 4966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (last == p) 4976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = trail; 4986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count.getAndDecrement() == capacity) 4996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 5006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 503bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 5046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * if it is present. More formally, removes an element {@code e} such 5056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 506bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 5076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this queue contained the specified element 508bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 509bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 510bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 5116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this queue changed as a result of the call 512bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> trail = head, p = trail.next; 5186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p != null; 5196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail = p, p = p.next) { 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o.equals(p.item)) { 5216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p, trail); 5226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 523adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 530adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 531bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 5328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contains the specified element. 5338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * More formally, returns {@code true} if and only if this queue contains 5348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 5358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 5368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param o object to be checked for containment in this queue 5378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 5388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 5398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public boolean contains(Object o) { 5408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o == null) return false; 5418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson fullyLock(); 5428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 5438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> p = head.next; p != null; p = p.next) 5448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o.equals(p.item)) 5458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 5468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 5478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 5488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson fullyUnlock(); 5498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 553bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 554bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 555bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 556bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 557bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 558bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 559bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 563bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int size = count.get(); 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object[] a = new Object[size]; 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node<E> p = head.next; p != null; p = p.next) 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = p.item; 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 574adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 578adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 579bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 580bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 581bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 582bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 583bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 584bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 585bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 586bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 587bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 588bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 5896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code null}. 590bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 591bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 592bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 593bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 594bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 595bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 5966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 597bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 5986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * allocated array of {@code String}: 599bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 600e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 601bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 6026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 6036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code toArray()}. 604bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 605bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 606bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 607bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 608bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 609bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 610bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 611bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 612bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 613bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 6146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int size = count.get(); 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (a.length < size) 620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a = (T[])java.lang.reflect.Array.newInstance 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (a.getClass().getComponentType(), size); 622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 6246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = head.next; p != null; p = p.next) 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = (T)p.item; 626bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (a.length > k) 627bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson a[k] = null; 628adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 630adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 635e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Helpers.collectionToString(this); 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 638bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 639bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 640bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The queue will be empty after this call returns. 641bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p, h = head; (p = h.next) != null; h = p) { 6466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; 6476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 6486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson head = last; 6506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert head.item == null && head.next == null; 651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.getAndSet(0) == capacity) 6526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 658bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 659bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 660bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 661bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 662bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 663bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c) { 6656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return drainTo(c, Integer.MAX_VALUE); 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 667bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 668bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 669bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 670bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 671bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 672bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 673bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == null) 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NullPointerException(); 677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 679a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (maxElements <= 0) 680a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return 0; 6816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson boolean signalNotFull = false; 6826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock takeLock = this.takeLock; 6836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson takeLock.lock(); 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = Math.min(maxElements, count.get()); 6866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // count.get provides visibility to first n Nodes 6876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> h = head; 6886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int i = 0; 6896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 6906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (i < n) { 6916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = h.next; 6926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c.add(p.item); 6936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 6946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; 6956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h = p; 6966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++i; 6976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return n; 6996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Restore invariants even if c.add() threw 7016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (i > 0) { 7026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert h.item == null; 7036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson head = h; 7046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson signalNotFull = (count.getAndAdd(-i) == capacity); 7056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson takeLock.unlock(); 7096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (signalNotFull) 7106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson signalNotFull(); 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 712adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 713adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 7168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 7178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 718e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned iterator is 719e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 720adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 721bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 722adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 723adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 724a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return new Itr(); 725adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 727adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 7296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Basic weakly-consistent iterator. At all times hold the next 730adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * item to hand out so that if hasNext() reports true, we will 731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * still have it to return even if lost race with a take etc. 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 73391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle 734adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> current; 735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> lastRet; 736adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E currentElement; 737adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 7396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 741adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project current = head.next; 742adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (current != null) 743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project currentElement = current.item; 744adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 746adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 747adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 748adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 749adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 750adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return current != null; 751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 752adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 7546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 755adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 756adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (current == null) 757adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 758adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = current; 759e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E item = null; 760e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Unlike other traversal methods, iterators must handle both: 761e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // - dequeued nodes (p.next == p) 762e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // - (possibly multiple) interior removed nodes (p.item == null) 763e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (Node<E> p = current, q;; p = q) { 764e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((q = p.next) == p) 765e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q = head.next; 766e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (q == null || (item = q.item) != null) { 767e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak current = q; 768e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E x = currentElement; 769e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak currentElement = item; 770e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return x; 771e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 772e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 773adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 775adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 776adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 777adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 778adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 779adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (lastRet == null) 780adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 782adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 783adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> node = lastRet; 784adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = null; 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> trail = head, p = trail.next; 7866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p != null; 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail = p, p = p.next) { 7886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == node) { 7896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p, trail); 7906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson break; 7916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 792adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 793adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 795adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 796adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 797adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 798adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 799e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** A customized variant of Spliterators.IteratorSpliterator */ 800e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static final class LBQSpliterator<E> implements Spliterator<E> { 801e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static final int MAX_BATCH = 1 << 25; // max batch array size; 802e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingQueue<E> queue; 803e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> current; // current node; null until initialized 804e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int batch; // batch size for splits 805e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak boolean exhausted; // true when no more nodes 806e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long est; // size estimate 807e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak LBQSpliterator(LinkedBlockingQueue<E> queue) { 808e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.queue = queue; 809e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.est = queue.size(); 810e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 811e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 812e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long estimateSize() { return est; } 813e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 814e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Spliterator<E> trySplit() { 815e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> h; 816e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingQueue<E> q = this.queue; 817e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int b = batch; 818e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; 819e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!exhausted && 820e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ((h = current) != null || (h = q.head.next) != null) && 821e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak h.next != null) { 822e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Object[] a = new Object[n]; 823e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int i = 0; 824e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> p = current; 825e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q.fullyLock(); 826e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 827e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p != null || (p = q.head.next) != null) { 828e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak do { 829e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((a[i] = p.item) != null) 830e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ++i; 831e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } while ((p = p.next) != null && i < n); 832e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 833e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 834e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q.fullyUnlock(); 835e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 836e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((current = p) == null) { 837e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak est = 0L; 838e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak exhausted = true; 839e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 840e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((est -= i) < 0L) 841e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak est = 0L; 842e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (i > 0) { 843e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak batch = i; 844e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Spliterators.spliterator 845e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (a, 0, i, (Spliterator.ORDERED | 846e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Spliterator.NONNULL | 847e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Spliterator.CONCURRENT)); 848e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 849e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 850e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return null; 851e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 852e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 853e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void forEachRemaining(Consumer<? super E> action) { 854e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (action == null) throw new NullPointerException(); 855e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingQueue<E> q = this.queue; 856e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!exhausted) { 857e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak exhausted = true; 858e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> p = current; 859e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak do { 860e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E e = null; 861e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q.fullyLock(); 862e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 863e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p == null) 864e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p = q.head.next; 865e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (p != null) { 866e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak e = p.item; 867e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p = p.next; 868e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) 869e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 870e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 871e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 872e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q.fullyUnlock(); 873e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 874e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) 875e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak action.accept(e); 876e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } while (p != null); 877e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 878e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 879e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 880e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryAdvance(Consumer<? super E> action) { 881e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (action == null) throw new NullPointerException(); 882e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingQueue<E> q = this.queue; 883e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!exhausted) { 884e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E e = null; 885e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q.fullyLock(); 886e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 887e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (current == null) 888e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak current = q.head.next; 889e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (current != null) { 890e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak e = current.item; 891e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak current = current.next; 892e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) 893e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 894e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 895e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 896e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q.fullyUnlock(); 897e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 898e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (current == null) 899e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak exhausted = true; 900e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) { 901e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak action.accept(e); 902e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return true; 903e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 904e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 905e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return false; 906e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 907e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 908e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public int characteristics() { 909e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Spliterator.ORDERED | Spliterator.NONNULL | 910e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Spliterator.CONCURRENT; 911e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 912e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 913e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 914e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 915e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a {@link Spliterator} over the elements in this queue. 916e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 917e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned spliterator is 918e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 919e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 920e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 921e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. 922e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 923e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @implNote 924e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The {@code Spliterator} implements {@code trySplit} to permit limited 925e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * parallelism. 926e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 927e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a {@code Spliterator} over the elements in this queue 928e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @since 1.8 929e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 930e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Spliterator<E> spliterator() { 931e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return new LBQSpliterator<E>(this); 932e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 933e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 934adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 93591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Saves this queue to a stream (that is, serializes it). 936adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 937e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s the stream 938e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 939adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @serialData The capacity is emitted (int), followed by all of 9406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * its elements (each an {@code Object}) in the proper order, 941adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * followed by a null 942adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 943adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 944adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 945adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 946adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 947adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 948adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out any hidden stuff, plus capacity 949adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 950adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 951adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out all elements in the proper order. 952adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node<E> p = head.next; p != null; p = p.next) 953adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(p.item); 954adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 955adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use trailing null as sentinel 956adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(null); 957adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 958adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 959adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 960adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 961adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 962adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 963a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Reconstitutes this queue from a stream (that is, deserializes it). 964e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s the stream 965e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws ClassNotFoundException if the class of a serialized object 966e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * could not be found 967e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 968adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 969adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(java.io.ObjectInputStream s) 970adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException, ClassNotFoundException { 971adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Read in capacity, and any hidden stuff 972adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultReadObject(); 973adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 974adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project count.set(0); 975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = head = new Node<E>(null); 976adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 977adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Read in all elements and place in queue 978adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 9796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 980adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E item = (E)s.readObject(); 981adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item == null) 982adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 983adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project add(item); 984adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 985adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 986adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 987