LinkedBlockingQueue.java revision a807b4d808d2591894daf13aab179b2e9c46a2f5
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 98eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonimport java.util.concurrent.atomic.AtomicInteger; 108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonimport java.util.concurrent.locks.Condition; 118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonimport java.util.concurrent.locks.ReentrantLock; 126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.AbstractQueue; 136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Collection; 146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Iterator; 156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.NoSuchElementException; 168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson// BEGIN android-note 188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson// removed link to collections framework docs 198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson// END android-note 206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 21adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An optionally-bounded {@linkplain BlockingQueue blocking queue} based on 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * linked nodes. 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This queue orders elements FIFO (first-in-first-out). 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The <em>head</em> of the queue is that element that has been on the 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the longest time. 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The <em>tail</em> of the queue is that element that has been on the 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the shortest time. New elements 29adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * are inserted at the tail of the queue, and the queue retrieval 30adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operations obtain elements at the head of the queue. 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Linked queues typically have higher throughput than array-based queues but 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * less predictable performance in most concurrent applications. 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p> The optional capacity bound constructor argument serves as a 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * way to prevent excessive queue expansion. The capacity, if unspecified, 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * dynamically created upon each insertion unless this would bring the 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue above capacity. 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 40bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class and its iterator implement all of the 41bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 42bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Iterator} interfaces. 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param <E> the type of elements held in this collection 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 48bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class LinkedBlockingQueue<E> extends AbstractQueue<E> 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = -6903933977591709194L; 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * A variant of the "two lock queue" algorithm. The putLock gates 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * entry to put (and offer), and has an associated condition for 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting puts. Similarly for the takeLock. The "count" field 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * that they both rely on is maintained as an atomic to avoid 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * needing to get both locks in most cases. Also, to minimize need 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * for puts to get takeLock and vice-versa, cascading notifies are 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * used. When a put notices that it has enabled at least one take, 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * it signals taker. That taker in turn signals others if more 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * items have been entered since the signal. And symmetrically for 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * takes signalling puts. Operations such as remove(Object) and 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * iterators acquire both locks. 656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Visibility between writers and readers is provided as follows: 676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Whenever an element is enqueued, the putLock is acquired and 696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * count updated. A subsequent reader guarantees visibility to the 706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * enqueued Node by either acquiring the putLock (via fullyLock) 716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * or by acquiring the takeLock, and then reading n = count.get(); 726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this gives visibility to the first n items. 736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * To implement weakly consistent iterators, it appears we need to 756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * keep all Nodes GC-reachable from a predecessor dequeued Node. 766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * That would cause two problems: 776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a Node was tenured while live, which generational GCs have a 806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * hard time dealing with, causing repeated major collections. 816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * However, only non-deleted Nodes need to be reachable from 826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be of the kind understood by the GC. We use the trick of 846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linking a Node that has just been dequeued to itself. Such a 856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * self-link implicitly means to advance to head.next. 86bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Linked list node class 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static class Node<E> { 926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item; 936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real successor Node 976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the successor is head.next 986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no successor (this is the last node) 996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> next; 1016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node(E x) { item = x; } 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** The capacity bound, or Integer.MAX_VALUE if none */ 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final int capacity; 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Current number of elements */ 109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final AtomicInteger count = new AtomicInteger(); 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Head of linked list. 1136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: head.item == null 1146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson transient Node<E> head; 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Tail of linked list. 1196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: last.next == null 1206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient Node<E> last; 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Lock held by take, poll, etc */ 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReentrantLock takeLock = new ReentrantLock(); 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Wait queue for waiting takes */ 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notEmpty = takeLock.newCondition(); 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Lock held by put, offer, etc */ 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReentrantLock putLock = new ReentrantLock(); 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Wait queue for waiting puts */ 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notFull = putLock.newCondition(); 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 136bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Signals a waiting take. Called only from put/offer (which do not 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise ordinarily lock takeLock.) 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void signalNotEmpty() { 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 150bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Signals a waiting put. Called only from take/poll. 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void signalNotFull() { 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node at end of queue. 1646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param node the node 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void enqueue(Node<E> node) { 1686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert putLock.isHeldByCurrentThread(); 1696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert last.next == null; 1708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = last.next = node; 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes a node from head of queue. 1756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the node 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E dequeue() { 1796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert takeLock.isHeldByCurrentThread(); 1806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert head.item == null; 181bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> h = head; 182bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> first = h.next; 1836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; // help GC 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project head = first; 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = first.item; 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project first.item = null; 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Lock to prevent both puts and takes. 192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void fullyLock() { 194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 195adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unlock to allow both puts and takes. 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void fullyUnlock() { 202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// /** 2076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * Tells whether both locks are held by current thread. 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// */ 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// boolean isFullyLocked() { 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// return (putLock.isHeldByCurrentThread() && 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// takeLock.isHeldByCurrentThread()); 2126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with a capacity of 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link Integer#MAX_VALUE}. 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue() { 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(Integer.MAX_VALUE); 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity. 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 225bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param capacity the capacity of this queue 2266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException if {@code capacity} is not greater 227bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than zero 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue(int capacity) { 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (capacity <= 0) throw new IllegalArgumentException(); 231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this.capacity = capacity; 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = head = new Node<E>(null); 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with a capacity of 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link Integer#MAX_VALUE}, initially containing the elements of the 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * given collection, 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 240bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 242bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 243bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue(Collection<? extends E> c) { 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(Integer.MAX_VALUE); 2476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock putLock = this.putLock; 2486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLock.lock(); // Never contended, but necessary for visibility 2496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 2506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = 0; 2516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (E e : c) { 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) 2536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == capacity) 2556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Queue full"); 2568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(new Node<E>(e)); 2576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++n; 2586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count.set(n); 2606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 2616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLock.unlock(); 2626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is overridden to remove the reference to collections 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // greater in size than Integer.MAX_VALUE 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 271bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count.get(); 275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is a modified copy of the inherited doc comment, 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // without the reference to unlimited queues. 279adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 280bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the number of additional elements that this queue can ideally 281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (in the absence of memory or resource constraints) accept without 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking. This is always equal to the initial capacity of this queue 2836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * less the current {@code size} of this queue. 284bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 285bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 2866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 287bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * because it may be the case that another thread is about to 288bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert or remove an element. 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return capacity - count.get(); 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 295bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting if 296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary for space to become available. 297bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 298bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 299bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 300adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 301bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) throws InterruptedException { 302bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 3036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Note: convention in all put/take/etc is to preset local var 3046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // holding count negative to indicate failure unless set. 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> node = new Node<E>(e); 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lockInterruptibly(); 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Note that count is used in wait guard even though it is 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not protected by lock. This works because count can 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * only decrease at this point (all other puts are shut 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * out by lock), and we (or some other waiting put) are 3166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * signalled if it ever changes from capacity. Similarly 3176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * for all other uses of count in other wait guards. 318adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 3196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == capacity) { 3206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(node); 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndIncrement(); 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c + 1 < capacity) 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 329adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 334adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified element at the tail of this queue, waiting if 335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary up to the specified wait time for space to become available. 336bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 3376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if successful, or {@code false} if 338bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified waiting time elapses before space is available. 339bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 340bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 341adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 342bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 345bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 350adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lockInterruptibly(); 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == capacity) { 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanos <= 0) 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 3556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(new Node<E>(e)); 3586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c = count.getAndIncrement(); 3596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c + 1 < capacity) 3606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 370bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 371bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 3726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * returning {@code true} upon success and {@code false} if this queue 373bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is full. 374bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * When using a capacity-restricted queue, this method is generally 375bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * preferable to method {@link BlockingQueue#add add}, which can fail to 376bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert an element only by throwing an exception. 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 378bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 380bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 381bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == capacity) 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 386a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> node = new Node<E>(e); 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() < capacity) { 3918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(node); 392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndIncrement(); 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c + 1 < capacity) 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return c >= 0; 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 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) { 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanos <= 0) 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 { 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> first = head.next; 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (first == null) 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project else 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first.item; 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 487adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 488adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 489adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 490adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 491bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 4926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlinks interior Node p with predecessor trail. 4936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void unlink(Node<E> p, Node<E> trail) { 4956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert isFullyLocked(); 4966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // p.next is not changed, to allow iterators that are 4976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // traversing p to maintain their weak-consistency guarantee. 4986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 4996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail.next = p.next; 5006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (last == p) 5016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = trail; 5026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count.getAndDecrement() == capacity) 5036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 5046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 507bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 5086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * if it is present. More formally, removes an element {@code e} such 5096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 510bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 5116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this queue contained the specified element 512bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 513bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 514bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 5156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this queue changed as a result of the call 516bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 518adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 519adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> trail = head, p = trail.next; 5226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p != null; 5236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail = p, p = p.next) { 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o.equals(p.item)) { 5256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p, trail); 5266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 530adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 533adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 535bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 5368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contains the specified element. 5378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * More formally, returns {@code true} if and only if this queue contains 5388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 5398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 5408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param o object to be checked for containment in this queue 5418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 5428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 5438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public boolean contains(Object o) { 5448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o == null) return false; 5458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson fullyLock(); 5468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 5478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> p = head.next; p != null; p = p.next) 5488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o.equals(p.item)) 5498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 5508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 5518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 5528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson fullyUnlock(); 5538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 557bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 558bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 559bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 563bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 565bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 566bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 567bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 568bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int size = count.get(); 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object[] a = new Object[size]; 574adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node<E> p = head.next; p != null; p = p.next) 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = p.item; 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 578adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 583bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 584bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 585bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 586bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 587bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 588bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 589bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 590bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 591bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 592bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 5936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code null}. 594bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 595bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 596bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 597bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 598bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 599bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 6006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 601bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 6026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * allocated array of {@code String}: 603bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 604a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 605bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 6066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 6076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code toArray()}. 608bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 609bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 610bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 611bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 612bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 613bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 614bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 615bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 616bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 617bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 6186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int size = count.get(); 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (a.length < size) 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a = (T[])java.lang.reflect.Array.newInstance 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (a.getClass().getComponentType(), size); 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 6286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = head.next; p != null; p = p.next) 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = (T)p.item; 630bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (a.length > k) 631bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson a[k] = null; 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 639adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> p = head.next; 6428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p == null) 6438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return "[]"; 6448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 6458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson StringBuilder sb = new StringBuilder(); 6468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append('['); 6478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 6488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E e = p.item; 6498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(e == this ? "(this Collection)" : e); 6508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = p.next; 6518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p == null) 6528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return sb.append(']').toString(); 6538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(',').append(' '); 6548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 660bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 661bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 662bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The queue will be empty after this call returns. 663bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p, h = head; (p = h.next) != null; h = p) { 6686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; 6696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 6706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson head = last; 6726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert head.item == null && head.next == null; 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.getAndSet(0) == capacity) 6746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 679adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 680bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 681bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 682bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 683bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 684bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 685bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c) { 6876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return drainTo(c, Integer.MAX_VALUE); 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 689bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 690bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 691bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 692bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 693bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 694bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 695bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == null) 698adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NullPointerException(); 699adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 701a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (maxElements <= 0) 702a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return 0; 7036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson boolean signalNotFull = false; 7046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock takeLock = this.takeLock; 7056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson takeLock.lock(); 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 7076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = Math.min(maxElements, count.get()); 7086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // count.get provides visibility to first n Nodes 7096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> h = head; 7106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int i = 0; 7116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (i < n) { 7136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = h.next; 7146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c.add(p.item); 7156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 7166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; 7176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h = p; 7186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++i; 7196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return n; 7216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Restore invariants even if c.add() threw 7236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (i > 0) { 7246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert h.item == null; 7256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson head = h; 7266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson signalNotFull = (count.getAndAdd(-i) == capacity); 7276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson takeLock.unlock(); 7316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (signalNotFull) 7326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson signalNotFull(); 733adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 734adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 736adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 737adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 7388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 7398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 7408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 7416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 7428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 7438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements as they existed upon construction of the iterator, and 7448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * may (but is not guaranteed to) reflect any modifications 7458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * subsequent to construction. 746adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 747bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 748adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 749adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 750a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return new Itr(); 751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 752adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 754adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 7556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Basic weakly-consistent iterator. At all times hold the next 756adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * item to hand out so that if hasNext() reports true, we will 757adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * still have it to return even if lost race with a take etc. 758adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 759adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> current; 760adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> lastRet; 761adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E currentElement; 762adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 763adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 7646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 765adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 766adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project current = head.next; 767adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (current != null) 768adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project currentElement = current.item; 769adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 771adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 772adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 773adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 774adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 775adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return current != null; 776adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 777adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the next live successor of p, or null if no such. 7806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlike other traversal methods, iterators need to handle both: 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - dequeued nodes (p.next == p) 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - (possibly multiple) interior removed nodes (p.item == null) 7846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private Node<E> nextNode(Node<E> p) { 7866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (;;) { 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> s = p.next; 7886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (s == p) 7896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return head.next; 7906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (s == null || s.item != null) 7916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return s; 7926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p = s; 7936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 796adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 7976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 798adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 799adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (current == null) 800adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 801adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = currentElement; 802adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = current; 8036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson current = nextNode(current); 8046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson currentElement = (current == null) ? null : current.item; 805adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 806adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 8076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 808adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 809adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 810adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 811adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 812adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (lastRet == null) 813adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 8146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> node = lastRet; 817adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = null; 8186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> trail = head, p = trail.next; 8196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p != null; 8206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail = p, p = p.next) { 8216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == node) { 8226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p, trail); 8236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson break; 8246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 825adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 826adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 8276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 828adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 829adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 830adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 831adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 832adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 833a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Saves the state to a stream (that is, serializes it). 834adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 835adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @serialData The capacity is emitted (int), followed by all of 8366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * its elements (each an {@code Object}) in the proper order, 837adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * followed by a null 838adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param s the stream 839adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 840adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 841adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 842adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 843adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 844adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 845adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out any hidden stuff, plus capacity 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 847adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 848adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out all elements in the proper order. 849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node<E> p = head.next; p != null; p = p.next) 850adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(p.item); 851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use trailing null as sentinel 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(null); 854adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 855adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 856adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 857adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 858adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 860a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Reconstitutes this queue from a stream (that is, deserializes it). 8616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 862adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param s the stream 863adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 864adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(java.io.ObjectInputStream s) 865adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException, ClassNotFoundException { 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Read in capacity, and any hidden stuff 867adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultReadObject(); 868adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 869adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project count.set(0); 870adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = head = new Node<E>(null); 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Read in all elements and place in queue 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 8746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E item = (E)s.readObject(); 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item == null) 877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 878adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project add(item); 879adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 880adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 882