LinkedBlockingQueue.java revision 91770798d8b9280d48d30df2ed7f63b3ed9b036f
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 * 3491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <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 47bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class LinkedBlockingQueue<E> extends AbstractQueue<E> 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = -6903933977591709194L; 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * A variant of the "two lock queue" algorithm. The putLock gates 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * entry to put (and offer), and has an associated condition for 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting puts. Similarly for the takeLock. The "count" field 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * that they both rely on is maintained as an atomic to avoid 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * needing to get both locks in most cases. Also, to minimize need 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * for puts to get takeLock and vice-versa, cascading notifies are 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * used. When a put notices that it has enabled at least one take, 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * it signals taker. That taker in turn signals others if more 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * items have been entered since the signal. And symmetrically for 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * takes signalling puts. Operations such as remove(Object) and 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * iterators acquire both locks. 646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Visibility between writers and readers is provided as follows: 666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Whenever an element is enqueued, the putLock is acquired and 686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * count updated. A subsequent reader guarantees visibility to the 696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * enqueued Node by either acquiring the putLock (via fullyLock) 706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * or by acquiring the takeLock, and then reading n = count.get(); 716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this gives visibility to the first n items. 726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * To implement weakly consistent iterators, it appears we need to 746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * keep all Nodes GC-reachable from a predecessor dequeued Node. 756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * That would cause two problems: 766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a Node was tenured while live, which generational GCs have a 796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * hard time dealing with, causing repeated major collections. 806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * However, only non-deleted Nodes need to be reachable from 816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be of the kind understood by the GC. We use the trick of 836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linking a Node that has just been dequeued to itself. Such a 846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * self-link implicitly means to advance to head.next. 85bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Linked list node class 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static class Node<E> { 916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item; 926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real successor Node 966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the successor is head.next 976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no successor (this is the last node) 986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> next; 1006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node(E x) { item = x; } 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** The capacity bound, or Integer.MAX_VALUE if none */ 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final int capacity; 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Current number of elements */ 108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final AtomicInteger count = new AtomicInteger(); 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Head of linked list. 1126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: head.item == null 1136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson transient Node<E> head; 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Tail of linked list. 1186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: last.next == null 1196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient Node<E> last; 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Lock held by take, poll, etc */ 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReentrantLock takeLock = new ReentrantLock(); 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Wait queue for waiting takes */ 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notEmpty = takeLock.newCondition(); 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Lock held by put, offer, etc */ 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReentrantLock putLock = new ReentrantLock(); 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Wait queue for waiting puts */ 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notFull = putLock.newCondition(); 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 135bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Signals a waiting take. Called only from put/offer (which do not 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise ordinarily lock takeLock.) 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void signalNotEmpty() { 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 149bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Signals a waiting put. Called only from take/poll. 150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void signalNotFull() { 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node at end of queue. 1636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param node the node 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void enqueue(Node<E> node) { 1676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert putLock.isHeldByCurrentThread(); 1686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert last.next == null; 1698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = last.next = node; 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes a node from head of queue. 1746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the node 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E dequeue() { 1786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert takeLock.isHeldByCurrentThread(); 1796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert head.item == null; 180bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> h = head; 181bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> first = h.next; 1826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; // help GC 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project head = first; 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = first.item; 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project first.item = null; 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 19091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Locks to prevent both puts and takes. 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void fullyLock() { 193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 195adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 19891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Unlocks to allow both puts and takes. 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void fullyUnlock() { 201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// /** 2066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * Tells whether both locks are held by current thread. 2076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// */ 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// boolean isFullyLocked() { 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// return (putLock.isHeldByCurrentThread() && 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// takeLock.isHeldByCurrentThread()); 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with a capacity of 215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link Integer#MAX_VALUE}. 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue() { 218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(Integer.MAX_VALUE); 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity. 223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 224bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param capacity the capacity of this queue 2256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException if {@code capacity} is not greater 226bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than zero 227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue(int capacity) { 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (capacity <= 0) throw new IllegalArgumentException(); 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this.capacity = capacity; 231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = head = new Node<E>(null); 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingQueue} with a capacity of 236adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link Integer#MAX_VALUE}, initially containing the elements of the 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * given collection, 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 239bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 240adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 241bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 242bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public LinkedBlockingQueue(Collection<? extends E> c) { 245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(Integer.MAX_VALUE); 2466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock putLock = this.putLock; 2476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLock.lock(); // Never contended, but necessary for visibility 2486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 2496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = 0; 2506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (E e : c) { 2516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 2536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == capacity) 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Queue full"); 2558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(new Node<E>(e)); 2566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++n; 2576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count.set(n); 2596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 2606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLock.unlock(); 2616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is overridden to remove the reference to collections 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // greater in size than Integer.MAX_VALUE 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 269bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count.get(); 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is a modified copy of the inherited doc comment, 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // without the reference to unlimited queues. 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 278bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the number of additional elements that this queue can ideally 279bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (in the absence of memory or resource constraints) accept without 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking. This is always equal to the initial capacity of this queue 2816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * less the current {@code size} of this queue. 282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 283bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 2846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 285bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * because it may be the case that another thread is about to 286bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert or remove an element. 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return capacity - count.get(); 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 293bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting if 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary for space to become available. 295bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 296bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 297bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 299bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) throws InterruptedException { 300bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 3016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Note: convention in all put/take/etc is to preset local var 3026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // holding count negative to indicate failure unless set. 303adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 304a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> node = new Node<E>(e); 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lockInterruptibly(); 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Note that count is used in wait guard even though it is 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not protected by lock. This works because count can 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * only decrease at this point (all other puts are shut 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * out by lock), and we (or some other waiting put) are 3146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * signalled if it ever changes from capacity. Similarly 3156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * for all other uses of count in other wait guards. 316adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 3176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == capacity) { 3186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(node); 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndIncrement(); 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c + 1 < capacity) 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 329adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified element at the tail of this queue, waiting if 333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary up to the specified wait time for space to become available. 334bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 3356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if successful, or {@code false} if 33691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * the specified waiting time elapses before space is available 337bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 338bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 339adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 340bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 341adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 343bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lockInterruptibly(); 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == capacity) { 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanos <= 0) 352adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 3536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(new Node<E>(e)); 3566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c = count.getAndIncrement(); 3576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c + 1 < capacity) 3586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 359adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 360adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 368bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 369bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * returning {@code true} upon success and {@code false} if this queue 371bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is full. 372bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * When using a capacity-restricted queue, this method is generally 373bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * preferable to method {@link BlockingQueue#add add}, which can fail to 374bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert an element only by throwing an exception. 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 376bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 378bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 379bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (e == null) throw new NullPointerException(); 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == capacity) 382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 384a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> node = new Node<E>(e); 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock putLock = this.putLock; 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.lock(); 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() < capacity) { 3898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson enqueue(node); 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndIncrement(); 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c + 1 < capacity) 392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putLock.unlock(); 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == 0) 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotEmpty(); 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return c >= 0; 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E take() throws InterruptedException { 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x; 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lockInterruptibly(); 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 4096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == 0) { 4106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.await(); 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x = dequeue(); 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndDecrement(); 414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c > 1) 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == capacity) 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotFull(); 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll(long timeout, TimeUnit unit) throws InterruptedException { 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = null; 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lockInterruptibly(); 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 4326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (count.get() == 0) { 433adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanos <= 0) 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 4356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notEmpty.awaitNanos(nanos); 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x = dequeue(); 4386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c = count.getAndDecrement(); 4396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c > 1) 4406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.signal(); 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == capacity) 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotFull(); 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 447adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 448adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final AtomicInteger count = this.count; 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == 0) 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = null; 454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int c = -1; 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() > 0) { 4596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x = dequeue(); 460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project c = count.getAndDecrement(); 461adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c > 1) 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == capacity) 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signalNotFull(); 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.get() == 0) 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock takeLock = this.takeLock; 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.lock(); 477adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 478adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> first = head.next; 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (first == null) 480adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project else 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first.item; 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeLock.unlock(); 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 487adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 488bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 4896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlinks interior Node p with predecessor trail. 4906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void unlink(Node<E> p, Node<E> trail) { 4926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert isFullyLocked(); 4936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // p.next is not changed, to allow iterators that are 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // traversing p to maintain their weak-consistency guarantee. 4956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 4966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail.next = p.next; 4976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (last == p) 4986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = trail; 4996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count.getAndDecrement() == capacity) 5006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 5016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 504bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 5056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * if it is present. More formally, removes an element {@code e} such 5066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 507bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 5086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this queue contained the specified element 509bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 510bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 511bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 5126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this queue changed as a result of the call 513bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> trail = head, p = trail.next; 5196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p != null; 5206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail = p, p = p.next) { 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o.equals(p.item)) { 5226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p, trail); 5236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 530adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 532bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 5338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contains the specified element. 5348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * More formally, returns {@code true} if and only if this queue contains 5358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 5368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 5378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param o object to be checked for containment in this queue 5388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 5398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 5408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public boolean contains(Object o) { 5418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o == null) return false; 5428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson fullyLock(); 5438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 5448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> p = head.next; p != null; p = p.next) 5458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o.equals(p.item)) 5468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 5478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 5488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 5498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson fullyUnlock(); 5508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 554bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 555bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 556bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 557bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 558bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 559bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 563bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 565bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int size = count.get(); 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object[] a = new Object[size]; 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node<E> p = head.next; p != null; p = p.next) 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = p.item; 574adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 578adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 580bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 581bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 582bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 583bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 584bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 585bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 586bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 587bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 588bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 589bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 5906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code null}. 591bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 592bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 593bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 594bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 595bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 596bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 5976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 598bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 5996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * allocated array of {@code String}: 600bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 601a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 602bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 6036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 6046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code toArray()}. 605bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 606bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 607bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 608bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 609bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 610bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 611bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 612bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 613bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 614bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 6156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int size = count.get(); 620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (a.length < size) 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a = (T[])java.lang.reflect.Array.newInstance 622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (a.getClass().getComponentType(), size); 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 6256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = head.next; p != null; p = p.next) 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = (T)p.item; 627bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (a.length > k) 628bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson a[k] = null; 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 630adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> p = head.next; 6398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p == null) 6408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return "[]"; 6418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 6428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson StringBuilder sb = new StringBuilder(); 6438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append('['); 6448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 6458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E e = p.item; 6468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(e == this ? "(this Collection)" : e); 6478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = p.next; 6488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p == null) 6498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return sb.append(']').toString(); 6508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(',').append(' '); 6518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 657bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 658bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 659bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The queue will be empty after this call returns. 660bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p, h = head; (p = h.next) != null; h = p) { 6656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; 6666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 6676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson head = last; 6696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert head.item == null && head.next == null; 670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count.getAndSet(0) == capacity) 6716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 677bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 678bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 679bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 680bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 681bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 682bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c) { 6846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return drainTo(c, Integer.MAX_VALUE); 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 686bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 687bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 688bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 689bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 690bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 691bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 692bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 694adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == null) 695adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NullPointerException(); 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 698a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (maxElements <= 0) 699a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return 0; 7006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson boolean signalNotFull = false; 7016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock takeLock = this.takeLock; 7026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson takeLock.lock(); 703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 7046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = Math.min(maxElements, count.get()); 7056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // count.get provides visibility to first n Nodes 7066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> h = head; 7076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int i = 0; 7086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while (i < n) { 7106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = h.next; 7116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c.add(p.item); 7126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.item = null; 7136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.next = h; 7146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h = p; 7156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++i; 7166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return n; 7186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Restore invariants even if c.add() threw 7206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (i > 0) { 7216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert h.item == null; 7226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson head = h; 7236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson signalNotFull = (count.getAndAdd(-i) == capacity); 7246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 725adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson takeLock.unlock(); 7286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (signalNotFull) 7296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson signalNotFull(); 730adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 733adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 734adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 7358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 7368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 7378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 7386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 7398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 7408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements as they existed upon construction of the iterator, and 7418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * may (but is not guaranteed to) reflect any modifications 7428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * subsequent to construction. 743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 744bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 745adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 746adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 747a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return new Itr(); 748adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 749adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 750adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 7526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Basic weakly-consistent iterator. At all times hold the next 753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * item to hand out so that if hasNext() reports true, we will 754adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * still have it to return even if lost race with a take etc. 755adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 75691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle 757adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> current; 758adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> lastRet; 759adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E currentElement; 760adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 761adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 7626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 763adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 764adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project current = head.next; 765adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (current != null) 766adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project currentElement = current.item; 767adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 7686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 769adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 770adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 771adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 772adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 773adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return current != null; 774adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 775adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the next live successor of p, or null if no such. 7786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlike other traversal methods, iterators need to handle both: 7806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - dequeued nodes (p.next == p) 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - (possibly multiple) interior removed nodes (p.item == null) 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private Node<E> nextNode(Node<E> p) { 7846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (;;) { 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> s = p.next; 7866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (s == p) 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return head.next; 7886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (s == null || s.item != null) 7896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return s; 7906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p = s; 7916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 794adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 7956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 796adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 797adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (current == null) 798adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 799adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = currentElement; 800adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = current; 8016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson current = nextNode(current); 8026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson currentElement = (current == null) ? null : current.item; 803adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 804adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 8056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 806adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 807adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 808adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 809adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 810adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (lastRet == null) 811adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 8126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyLock(); 813adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 814adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> node = lastRet; 815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = null; 8166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> trail = head, p = trail.next; 8176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p != null; 8186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson trail = p, p = p.next) { 8196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == node) { 8206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p, trail); 8216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson break; 8226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 823adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 824adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 8256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson fullyUnlock(); 826adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 827adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 828adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 829adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 830adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 83191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Saves this queue to a stream (that is, serializes it). 832adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 833adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @serialData The capacity is emitted (int), followed by all of 8346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * its elements (each an {@code Object}) in the proper order, 835adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * followed by a null 836adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 837adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 838adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 839adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 840adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyLock(); 841adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 842adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out any hidden stuff, plus capacity 843adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 844adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 845adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out all elements in the proper order. 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node<E> p = head.next; p != null; p = p.next) 847adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(p.item); 848adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use trailing null as sentinel 850adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(null); 851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project fullyUnlock(); 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 854adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 855adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 856adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 857a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Reconstitutes this queue from a stream (that is, deserializes it). 858adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(java.io.ObjectInputStream s) 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException, ClassNotFoundException { 861adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Read in capacity, and any hidden stuff 862adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultReadObject(); 863adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 864adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project count.set(0); 865adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = head = new Node<E>(null); 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 867adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Read in all elements and place in queue 868adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 8696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 870adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E item = (E)s.readObject(); 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item == null) 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project add(item); 874adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 877