ArrayBlockingQueue.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; 8a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.concurrent.locks.Condition; 9a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.concurrent.locks.ReentrantLock; 10a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.AbstractQueue; 11a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Collection; 12a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Iterator; 13a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.NoSuchElementException; 14a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.lang.ref.WeakReference; 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// BEGIN android-note 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// removed link to collections framework docs 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// END android-note 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 21adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * A bounded {@linkplain BlockingQueue blocking queue} backed by an 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * array. This queue orders elements FIFO (first-in-first-out). The 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>head</em> of the queue is that element that has been on the 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the longest time. The <em>tail</em> of the queue is that 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * element that has been on the queue the shortest time. New elements 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * are inserted at the tail of the queue, and the queue retrieval 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operations obtain elements at the head of the queue. 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 29adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This is a classic "bounded buffer", in which a 30adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * fixed-sized array holds elements inserted by producers and 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * extracted by consumers. Once created, the capacity cannot be 328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * changed. Attempts to {@code put} an element into a full queue 338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * will result in the operation blocking; attempts to {@code take} an 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * element from an empty queue will similarly block. 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>This class supports an optional fairness policy for ordering 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting producer and consumer threads. By default, this ordering 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is not guaranteed. However, a queue constructed with fairness set 398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * to {@code true} grants threads access in FIFO order. Fairness 40adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * generally decreases throughput but reduces variability and avoids 41adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * starvation. 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 43bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class and its iterator implement all of the 44bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 45bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Iterator} interfaces. 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param <E> the type of elements held in this collection 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class ArrayBlockingQueue<E> extends AbstractQueue<E> 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Serialization ID. This class relies on default serialization 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * even for the items array, which is default-serialized, even if 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * it is empty. Otherwise it could not be declared final, which is 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary here. 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = -817911632652898426L; 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** The queued items */ 638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items; 648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** items index for next take, poll, peek or remove */ 668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int takeIndex; 678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** items index for next put, offer, or add */ 698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int putIndex; 708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** Number of elements in the queue */ 728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int count; 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Concurrency control uses the classic two-condition algorithm 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * found in any textbook. 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Main lock guarding all access */ 808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock; 81a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Condition for waiting takes */ 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notEmpty; 84a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Condition for waiting puts */ 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notFull; 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 88a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 89a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Shared state for currently active iterators, or null if there 90a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * are known not to be any. Allows queue operations to update 91a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * iterator state. 92a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 93a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson transient Itrs itrs = null; 94a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Internal helper methods 96adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 97adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Circularly increment i. 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final int inc(int i) { 1018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return (++i == items.length) ? 0 : i; 1028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Circularly decrement i. 1068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final int dec(int i) { 1088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return ((i == 0) ? items.length : i) - 1; 1098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns item at index i. 1138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 11491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 1158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final E itemAt(int i) { 11691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle return (E) items[i]; 1178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Throws NullPointerException if argument is null. 1218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 1228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param v the element 1238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static void checkNotNull(Object v) { 1258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (v == null) 1268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 130bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts element at current put position, advances, and signals. 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Call only when holding lock. 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void enqueue(E x) { 134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert items[putIndex] == null; 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[putIndex] = x; 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putIndex = inc(putIndex); 138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count++; 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 143bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Extracts element at current take position, advances, and signals. 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Call only when holding lock. 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 146a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E dequeue() { 147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert items[takeIndex] != null; 1498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 15091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 15191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle E x = (E) items[takeIndex]; 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[takeIndex] = null; 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeIndex = inc(takeIndex); 154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count--; 155a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.elementDequeued(); 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Deletes item at array index removeIndex. 163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Utility for remove(Object) and iterator.remove. 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Call only when holding lock. 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void removeAt(final int removeIndex) { 167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert items[removeIndex] != null; 169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert removeIndex >= 0 && removeIndex < items.length; 1708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 171a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (removeIndex == takeIndex) { 172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // removing front item; just advance 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[takeIndex] = null; 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project takeIndex = inc(takeIndex); 175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count--; 176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.elementDequeued(); 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // an "interior" remove 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 181adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // slide over all others up through putIndex. 182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (int i = removeIndex;;) { 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int next = inc(i); 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (next != putIndex) { 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson items[i] = items[next]; 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson i = next; 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[i] = null; 190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.putIndex = i; 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 194a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count--; 195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 196a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.removedAt(removeIndex); 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates an {@code ArrayBlockingQueue} with the given (fixed) 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity and default access policy. 204bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity the capacity of this queue 2068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code capacity < 1} 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 208adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayBlockingQueue(int capacity) { 209adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(capacity, false); 210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates an {@code ArrayBlockingQueue} with the given (fixed) 214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity and the specified access policy. 215bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity the capacity of this queue 2178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param fair if {@code true} then queue accesses for threads blocked 218bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * on insertion or removal, are processed in FIFO order; 2198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if {@code false} the access order is unspecified. 2208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code capacity < 1} 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayBlockingQueue(int capacity, boolean fair) { 223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (capacity <= 0) 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 2258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.items = new Object[capacity]; 226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock = new ReentrantLock(fair); 227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty = lock.newCondition(); 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull = lock.newCondition(); 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates an {@code ArrayBlockingQueue} with the given (fixed) 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity, the specified access policy and initially containing the 234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements of the given collection, 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 236bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity the capacity of this queue 2388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param fair if {@code true} then queue accesses for threads blocked 239bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * on insertion or removal, are processed in FIFO order; 2408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if {@code false} the access order is unspecified. 241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 2428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code capacity} is less than 2438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code c.size()}, or less than 1. 244bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 245bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayBlockingQueue(int capacity, boolean fair, 248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Collection<? extends E> c) { 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(capacity, fair); 250adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock = this.lock; 2528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); // Lock only for visibility, not mutual exclusion 2538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 2548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int i = 0; 2558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 2568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (E e : c) { 2578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 2588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson items[i++] = e; 2598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } catch (ArrayIndexOutOfBoundsException ex) { 2618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new IllegalArgumentException(); 2628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson count = i; 2648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson putIndex = (i == capacity) ? 0 : i; 2658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 2668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); 2678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 271bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 272bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 2738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * returning {@code true} upon success and throwing an 2748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code IllegalStateException} if this queue is full. 275bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 276bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 2778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 278bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalStateException if this queue is full 279bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 280bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean add(E e) { 282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return super.add(e); 283bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 284bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 285bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 286bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 287bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 2888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * returning {@code true} upon success and {@code false} if this queue 289bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is full. This method is generally preferable to method {@link #add}, 290bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * which can fail to insert an element only by throwing an exception. 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 292bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 294bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 2958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 297adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 299adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count == items.length) 300adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 301adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project else { 302a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson enqueue(e); 303adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 311bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting 312bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * for space to become available if the queue is full. 313bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 314bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 315bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 316bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 317bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) throws InterruptedException { 3188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 319bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 320bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lockInterruptibly(); 321bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 3228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == items.length) 3238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson notFull.await(); 324a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson enqueue(e); 325bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 326bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 327bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 328bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 329bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 330bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 331bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting 332bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * up to the specified wait time for space to become available if 333bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the queue is full. 334bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 335bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 336bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 338bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 339adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 340adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 3418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 342bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson long nanos = unit.toNanos(timeout); 343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == items.length) { 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanos <= 0) 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 3498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nanos = notFull.awaitNanos(nanos); 350adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 351a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson enqueue(e); 3528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 355adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 358adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 359adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 360adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 362a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (count == 0) ? null : dequeue(); 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 368bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public E take() throws InterruptedException { 369bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 370bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lockInterruptibly(); 371bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 3728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == 0) 3738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson notEmpty.await(); 374a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeue(); 375bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 376bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 377bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 378bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 379bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll(long timeout, TimeUnit unit) throws InterruptedException { 381bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson long nanos = unit.toNanos(timeout); 382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == 0) { 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanos <= 0) 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 3888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nanos = notEmpty.awaitNanos(nanos); 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 390a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeue(); 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 40091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle return itemAt(takeIndex); // null when queue is empty 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is overridden to remove the reference to collections 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // greater in size than Integer.MAX_VALUE 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 411bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count; 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is a modified copy of the inherited doc comment, 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // without the reference to unlimited queues. 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 426bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the number of additional elements that this queue can ideally 427bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (in the absence of memory or resource constraints) accept without 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking. This is always equal to the initial capacity of this queue 4298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * less the current {@code size} of this queue. 430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 431bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 4328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 433bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * because it may be the case that another thread is about to 434bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert or remove an element. 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 438adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 440adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return items.length - count; 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 446bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 447bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 4488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if it is present. More formally, removes an element {@code e} such 4498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 450bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 4518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contained the specified element 452bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 453bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 4548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Removal of interior elements in circular array based queues 4558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * is an intrinsically slow and disruptive operation, so should 4568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * be undertaken only in exceptional circumstances, ideally 4578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * only when the queue is known not to be accessible by other 4588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * threads. 4598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 460bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 4618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue changed as a result of the call 462bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 463bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean remove(Object o) { 464bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (o == null) return false; 4658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 466bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 467bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lock(); 468bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 469a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count > 0) { 470a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 471a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = takeIndex; 472a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson do { 473a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o.equals(items[i])) { 474a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(i); 475a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 476a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 477a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } while ((i = inc(i)) != putIndex); 478bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 4798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 480bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 481bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 482bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 483bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 485bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 4868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contains the specified element. 4878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * More formally, returns {@code true} if and only if this queue contains 4888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 489bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 490bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o object to be checked for containment in this queue 4918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 492bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object o) { 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 4958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 496adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 497adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 499a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count > 0) { 500a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 501a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = takeIndex; 502a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson do { 503a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o.equals(items[i])) 504a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 505a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } while ((i = inc(i)) != putIndex); 506a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 508adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 509adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 513bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 514bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 515bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 516bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 517bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 518bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 519bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 520bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 521bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 522bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 523bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 524bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 525bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 5278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 530adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final int count = this.count; 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object[] a = new Object[count]; 53391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int n = items.length - takeIndex; 53491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (count <= n) { 53591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle System.arraycopy(items, takeIndex, a, 0, count); 53691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle } else { 53791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle System.arraycopy(items, takeIndex, a, 0, n); 53891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle System.arraycopy(items, 0, a, n, count - n); 53991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle } 540adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 541adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 542adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 543adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 546bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 547bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 548bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 549bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 550bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 551bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 552bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 553bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 554bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 555bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 5568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code null}. 557bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 558bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 559bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 5638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 5658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * allocated array of {@code String}: 566bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 567a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 568bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 5698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 5708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code toArray()}. 571bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 572bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 573bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 574bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 575bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 576bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 577bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 578bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 579bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 580bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 5818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson @SuppressWarnings("unchecked") 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 5838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 584adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 586adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final int count = this.count; 5888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final int len = a.length; 5898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (len < count) 590adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a = (T[])java.lang.reflect.Array.newInstance( 5918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson a.getClass().getComponentType(), count); 59291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int n = items.length - takeIndex; 59391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (count <= n) 59491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle System.arraycopy(items, takeIndex, a, 0, count); 59591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle else { 59691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle System.arraycopy(items, takeIndex, a, 0, n); 59791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle System.arraycopy(items, 0, a, n, count - n); 59891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle } 5998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (len > count) 600adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[count] = null; 601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 603adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int k = count; 6128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (k == 0) 6138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return "[]"; 6148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 6158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson StringBuilder sb = new StringBuilder(); 6168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append('['); 6178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = takeIndex; ; i = inc(i)) { 6188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object e = items[i]; 6198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(e == this ? "(this Collection)" : e); 6208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (--k == 0) 6218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return sb.append(']').toString(); 6228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(',').append(' '); 6238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 628adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 629bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 630bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 631bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The queue will be empty after this call returns. 632bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 6348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 638a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int k = count; 639a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (k > 0) { 640a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 641a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = takeIndex; 642a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson do { 643a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson items[i] = null; 644a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } while ((i = inc(i)) != putIndex); 645a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson takeIndex = putIndex; 646a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count = 0; 647a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 648a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.queueIsEmpty(); 649a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (; k > 0 && lock.hasWaiters(notFull); k--) 650a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson notFull.signal(); 651a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 657bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 658bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 659bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 660bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 661bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 662bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c) { 664a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return drainTo(c, Integer.MAX_VALUE); 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 667bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 668bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 669bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 670bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 671bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 672bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 6748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(c); 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (maxElements <= 0) 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return 0; 6798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 683a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int n = Math.min(maxElements, count); 684a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int take = takeIndex; 685a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = 0; 686a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 687a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while (i < n) { 68891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 68991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle E x = (E) items[take]; 690a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson c.add(x); 691a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson items[take] = null; 692a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson take = inc(take); 693a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson i++; 694a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 695a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return n; 696a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } finally { 697a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Restore invariants even if c.add() threw 698a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (i > 0) { 699a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count -= i; 700a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson takeIndex = take; 701a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) { 702a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count == 0) 703a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.queueIsEmpty(); 704a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (i > take) 705a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.takeIndexWrapped(); 706a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 707a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (; i > 0 && lock.hasWaiters(notFull); i--) 708a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson notFull.signal(); 709a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 712adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 713adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 716adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 7188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 7198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 720a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 7218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 722a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ConcurrentModificationException}, and guarantees to traverse 723a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * elements as they existed upon construction of the iterator, and 724a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may (but is not guaranteed to) reflect any modifications 725a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * subsequent to construction. 726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 727bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 7308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return new Itr(); 731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 733adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 734a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Shared data between iterators and their queue, allowing queue 735a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * modifications to update iterators when elements are removed. 736a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 737a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * This adds a lot of complexity for the sake of correctly 738a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * handling some uncommon operations, but the combination of 739a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * circular-arrays and supporting interior removes (i.e., those 740a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * not at head) would cause iterators to sometimes lose their 741a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * places and/or (re)report elements they shouldn't. To avoid 742a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this, when a queue has one or more iterators, it keeps iterator 743a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * state consistent by: 744a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 745a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (1) keeping track of the number of "cycles", that is, the 746a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number of times takeIndex has wrapped around to 0. 747a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (2) notifying all iterators via the callback removedAt whenever 748a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * an interior element is removed (and thus other elements may 749a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * be shifted). 750a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 751a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * These suffice to eliminate iterator inconsistencies, but 752a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unfortunately add the secondary responsibility of maintaining 753a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the list of iterators. We track all active iterators in a 754a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * simple linked list (accessed only when the queue's lock is 755a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * held) of weak references to Itr. The list is cleaned up using 756a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 3 different mechanisms: 757a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 758a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (1) Whenever a new iterator is created, do some O(1) checking for 759a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * stale list elements. 760a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 761a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (2) Whenever takeIndex wraps around to 0, check for iterators 762a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that have been unused for more than one wrap-around cycle. 763a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 764a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (3) Whenever the queue becomes empty, all iterators are notified 765a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and this entire data structure is discarded. 766a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 767a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * So in addition to the removedAt callback that is necessary for 768a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * correctness, iterators have the shutdown and takeIndexWrapped 769a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * callbacks that help remove stale iterators from the list. 770a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 771a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Whenever a list element is examined, it is expunged if either 772a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the GC has determined that the iterator is discarded, or if the 773a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * iterator reports that it is "detached" (does not need any 774a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * further state updates). Overhead is maximal when takeIndex 775a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * never advances, iterators are discarded before they are 776a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * exhausted, and all removals are interior removes, in which case 777a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * all stale iterators are discovered by the GC. But even in this 778a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * case we don't increase the amortized complexity. 779a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 780a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Care must be taken to keep list sweeping methods from 781a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * reentrantly invoking another such method, causing subtle 782a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * corruption bugs. 783a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 784a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson class Itrs { 785a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 786a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 787a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Node in a linked list of weak iterator references. 788a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 789a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private class Node extends WeakReference<Itr> { 790a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node next; 791a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 792a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node(Itr iterator, Node next) { 793a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson super(iterator); 794a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.next = next; 795a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 796a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 797a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 798a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Incremented whenever takeIndex wraps around to 0 */ 799a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int cycles = 0; 800a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 801a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Linked list of weak iterator references */ 802a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node head; 803a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 804a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Used to expunge stale iterators */ 805a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node sweeper = null; 806a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 807a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int SHORT_SWEEP_PROBES = 4; 808a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int LONG_SWEEP_PROBES = 16; 809a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 810a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Itrs(Itr initial) { 811a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson register(initial); 812a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 813a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 814a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 815a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Sweeps itrs, looking for and expunging stale iterators. 816a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * If at least one was found, tries harder to find more. 817a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called only from iterating thread. 818a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 819a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param tryHarder whether to start in try-harder mode, because 820a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * there is known to be at least one iterator to collect 821a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 822a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void doSomeSweeping(boolean tryHarder) { 823a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 824a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert head != null; 825a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES; 826a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node o, p; 827a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node sweeper = this.sweeper; 828a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean passedGo; // to limit search to one full sweep 829a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 830a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (sweeper == null) { 831a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = null; 832a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = head; 833a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson passedGo = true; 834a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 835a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = sweeper; 836a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = o.next; 837a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson passedGo = false; 838a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 839a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 840a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (; probes > 0; probes--) { 841a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == null) { 842a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (passedGo) 843a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 844a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = null; 845a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = head; 846a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson passedGo = true; 847a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 848a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Itr it = p.get(); 849a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node next = p.next; 850a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it == null || it.isDetached()) { 851a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // found a discarded/exhausted iterator 852a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson probes = LONG_SWEEP_PROBES; // "try harder" 853a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // unlink p 854a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 855a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.next = null; 856a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o == null) { 857a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = next; 858a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (next == null) { 859a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // We've run out of iterators to track; retire 860a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 861a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return; 862a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 863a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 864a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 865a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o.next = next; 866a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 867a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = p; 868a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 869a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = next; 870a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 871a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 872a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.sweeper = (p == null) ? null : o; 873a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 874a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 875a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 876a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Adds a new iterator to the linked list of tracked iterators. 877a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 878a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void register(Itr itr) { 879a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 880a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = new Node(itr, head); 881a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 882a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 883a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 884a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever takeIndex wraps around to 0. 885a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 886a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Notifies all iterators, and expunges any that are now stale. 887a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 888a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void takeIndexWrapped() { 889a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 890a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cycles++; 891a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node o = null, p = head; p != null;) { 892a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Itr it = p.get(); 893a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node next = p.next; 894a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it == null || it.takeIndexWrapped()) { 895a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // unlink p 896a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert it == null || it.isDetached(); 897a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 898a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.next = null; 899a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o == null) 900a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = next; 901a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 902a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o.next = next; 903a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 904a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = p; 905a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 906a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = next; 907a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 908a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head == null) // no more iterators to track 909a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 910a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 911a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 912a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 913a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever an interior remove (not at takeIndex) occured. 914a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 915a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Notifies all iterators, and expunges any that are now stale. 916a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 917a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void removedAt(int removedIndex) { 918a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node o = null, p = head; p != null;) { 919a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Itr it = p.get(); 920a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node next = p.next; 921a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it == null || it.removedAt(removedIndex)) { 922a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // unlink p 923a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert it == null || it.isDetached(); 924a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 925a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.next = null; 926a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o == null) 927a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = next; 928a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 929a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o.next = next; 930a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 931a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = p; 932a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 933a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = next; 934a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 935a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head == null) // no more iterators to track 936a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 937a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 938a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 939a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 940a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever the queue becomes empty. 941a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 942a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Notifies all active iterators that the queue is empty, 943a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * clears all weak refs, and unlinks the itrs datastructure. 944a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 945a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void queueIsEmpty() { 946a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 947a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node p = head; p != null; p = p.next) { 948a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Itr it = p.get(); 949a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it != null) { 950a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 951a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson it.shutdown(); 952a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 953a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 954a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = null; 955a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 956a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 957a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 958a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 959a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever an element has been dequeued (at takeIndex). 960a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 961a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void elementDequeued() { 962a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 963a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count == 0) 964a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson queueIsEmpty(); 965a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (takeIndex == 0) 966a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson takeIndexWrapped(); 967a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 968a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 969a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 970a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 971a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Iterator for ArrayBlockingQueue. 972a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 973a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * To maintain weak consistency with respect to puts and takes, we 974a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * read ahead one slot, so as to not report hasNext true but then 975a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * not have an element to return. 976a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 977a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We switch into "detached" mode (allowing prompt unlinking from 978a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * itrs without help from the GC) when all indices are negative, or 979a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * when hasNext returns false for the first time. This allows the 980a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * iterator to track concurrent updates completely accurately, 981a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * except for the corner case of the user calling Iterator.remove() 982a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * after hasNext() returned false. Even in this case, we ensure 983a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that we don't remove the wrong element by keeping track of the 984a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * expected element to remove, in lastItem. Yes, we may fail to 985a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * remove lastItem from the queue if it moved due to an interleaved 986a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * interior remove while in detached mode. 987adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 988adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 989a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Index to look for new nextItem; NONE at end */ 990a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int cursor; 991a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 992a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Element to be returned by next call to next(); null if none */ 993a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E nextItem; 994a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 995a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Index of nextItem; NONE if none, REMOVED if removed elsewhere */ 996a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int nextIndex; 997a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 998a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Last element returned; null if none or not detached. */ 999a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E lastItem; 1000a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1001a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Index of lastItem, NONE if none, REMOVED if removed elsewhere */ 1002a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int lastRet; 1003a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1004a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Previous value of takeIndex, or DETACHED when detached */ 1005a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int prevTakeIndex; 1006a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1007a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Previous value of iters.cycles */ 1008a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int prevCycles; 1009a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1010a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Special index value indicating "not available" or "undefined" */ 1011a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int NONE = -1; 1012a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1013a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1014a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Special index value indicating "removed elsewhere", that is, 1015a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * removed by some operation other than a call to this.remove(). 1016a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1017a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int REMOVED = -2; 1018a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1019a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Special value for prevTakeIndex indicating "detached mode" */ 1020a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int DETACHED = -3; 1021adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1022adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 1023a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1024a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastRet = NONE; 10258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock = ArrayBlockingQueue.this.lock; 10268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); 10278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 1028a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count == 0) { 1029a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert itrs == null; 1030a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = NONE; 1031a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = NONE; 1032a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = DETACHED; 1033a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 1034a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int takeIndex = ArrayBlockingQueue.this.takeIndex; 1035a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = takeIndex; 10368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nextItem = itemAt(nextIndex = takeIndex); 1037a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = incCursor(takeIndex); 1038a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs == null) { 1039a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = new Itrs(this); 1040a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 1041a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.register(this); // in this order 1042a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.doSomeSweeping(false); 1043a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1044a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevCycles = itrs.cycles; 1045a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert takeIndex >= 0; 1046a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert prevTakeIndex == takeIndex; 1047a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex >= 0; 1048a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextItem != null; 1049a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 10508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 10518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); 1052adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1053adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1054adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1055a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean isDetached() { 1056a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1057a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return prevTakeIndex < 0; 1058a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1059a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1060a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int incCursor(int index) { 1061a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1062a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson index = inc(index); 1063a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (index == putIndex) 1064a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson index = NONE; 1065a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return index; 1066a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1067a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1068a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1069a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns true if index is invalidated by the given number of 1070a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * dequeues, starting from prevTakeIndex. 1071a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1072a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private boolean invalidated(int index, int prevTakeIndex, 1073a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long dequeues, int length) { 1074a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (index < 0) 1075a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1076a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int distance = index - prevTakeIndex; 1077a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (distance < 0) 1078a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson distance += length; 1079a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeues > distance; 1080a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1081a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1082a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1083a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Adjusts indices to incorporate all dequeues since the last 1084a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * operation on this iterator. Call only from iterating thread. 1085a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1086a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void incorporateDequeues() { 1087a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1088a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert itrs != null; 1089a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert !isDetached(); 1090a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert count > 0; 1091a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1092a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int cycles = itrs.cycles; 1093a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int takeIndex = ArrayBlockingQueue.this.takeIndex; 1094a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevCycles = this.prevCycles; 1095a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevTakeIndex = this.prevTakeIndex; 1096a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1097a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cycles != prevCycles || takeIndex != prevTakeIndex) { 1098a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int len = items.length; 1099a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // how far takeIndex has advanced since the previous 1100a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // operation of this iterator 1101a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long dequeues = (cycles - prevCycles) * len 1102a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson + (takeIndex - prevTakeIndex); 1103a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1104a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Check indices for invalidation 1105a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (invalidated(lastRet, prevTakeIndex, dequeues, len)) 1106a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastRet = REMOVED; 1107a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (invalidated(nextIndex, prevTakeIndex, dequeues, len)) 1108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = REMOVED; 1109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (invalidated(cursor, prevTakeIndex, dequeues, len)) 1110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = takeIndex; 1111a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1112a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor < 0 && nextIndex < 0 && lastRet < 0) 1113a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson detach(); 1114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 1115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.prevCycles = cycles; 1116a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.prevTakeIndex = takeIndex; 1117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1119a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1120a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1121a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1122a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called when itrs should stop tracking this iterator, either 1123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * because there are no more indices to update (cursor < 0 && 1124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nextIndex < 0 && lastRet < 0) or as a special exception, when 1125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * lastRet >= 0, because hasNext() is about to return false for the 1126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * first time. Call only from iterating thread. 1127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void detach() { 1129a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Switch to detached mode 1130a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1131a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cursor == NONE; 1132a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex < 0; 1133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet < 0 || nextItem == null; 1134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet < 0 ^ lastItem != null; 1135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (prevTakeIndex >= 0) { 1136a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert itrs != null; 1137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = DETACHED; 1138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // try to unlink from itrs (but not too hard) 1139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.doSomeSweeping(true); 1140a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1141a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1143a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1144a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * For performance reasons, we would like not to acquire a lock in 1145a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * hasNext in the common case. To allow for this, we only access 1146a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * fields (i.e. nextItem) that are not modified by update operations 1147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * triggered by queue modifications. 1148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 1150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (nextItem != null) 1152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1153a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson noNext(); 1154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1155a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1157a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void noNext() { 1158a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final ReentrantLock lock = ArrayBlockingQueue.this.lock; 1159a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lock.lock(); 1160a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 1161a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cursor == NONE; 1162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex == NONE; 1163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) { 1164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet >= 0; 1165a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson incorporateDequeues(); // might update lastRet 1166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastItem = itemAt(lastRet); 1168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem != null; 1169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson detach(); 1170a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1171a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert isDetached(); 1173a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet < 0 ^ lastItem != null; 1174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } finally { 1175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lock.unlock(); 1176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 1180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final E x = nextItem; 1182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == null) 1183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new NoSuchElementException(); 1184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = ArrayBlockingQueue.this.lock; 1185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 1186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) 1188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson incorporateDequeues(); 1189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex != NONE; 1190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem == null; 1191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = nextIndex; 1192a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int cursor = this.cursor; 1193a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor >= 0) { 1194a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextItem = itemAt(nextIndex = cursor); 1195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextItem != null; 1196a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.cursor = incCursor(cursor); 1197a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 1198a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = NONE; 1199a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextItem = null; 12008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 1202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 1203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1204a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return x; 1205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 1208a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1209adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = ArrayBlockingQueue.this.lock; 1210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 1211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1212a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) 1213a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson incorporateDequeues(); // might update lastRet or detach 1214a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int lastRet = this.lastRet; 1215a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = NONE; 1216a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1217a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) 1218a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(lastRet); 1219a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 1220a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final E lastItem = this.lastItem; 1221a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem != null; 1222a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastItem = null; 1223a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itemAt(lastRet) == lastItem) 1224a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(lastRet); 1225a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1226a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else if (lastRet == NONE) 1227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 1228a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // else lastRet == REMOVED and the last returned element was 1229a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // previously asynchronously removed via an operation other 1230a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // than this.remove(), so nothing to do. 1231a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1232a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor < 0 && nextIndex < 0) 1233a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson detach(); 1234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 1235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 1236a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet == NONE; 1237a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem == null; 1238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 12408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1241a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1242a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called to notify the iterator that the queue is empty, or that it 1243a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * has fallen hopelessly behind, so that it should abandon any 1244a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * further iteration, except possibly to return one more element 1245a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * from next(), as promised by returning true from hasNext(). 1246a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1247a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void shutdown() { 1248a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1249a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = NONE; 1250a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (nextIndex >= 0) 1251a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = REMOVED; 1252a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1253a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastRet = REMOVED; 1254a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastItem = null; 1255a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1256a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = DETACHED; 1257a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Don't set nextItem to null because we must continue to be 1258a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // able to return it on next(). 1259a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // 1260a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Caller will unlink from itrs when convenient. 1261a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1262a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1263a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int distance(int index, int prevTakeIndex, int length) { 1264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int distance = index - prevTakeIndex; 1265a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (distance < 0) 1266a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson distance += length; 1267a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return distance; 1268a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1269a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1270a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1271a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever an interior remove (not at takeIndex) occured. 1272a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1273a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return true if this iterator should be unlinked from itrs 1274a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1275a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean removedAt(int removedIndex) { 1276a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1277a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (isDetached()) 1278a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1279a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1280a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int cycles = itrs.cycles; 1281a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int takeIndex = ArrayBlockingQueue.this.takeIndex; 1282a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevCycles = this.prevCycles; 1283a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevTakeIndex = this.prevTakeIndex; 1284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int len = items.length; 1285a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int cycleDiff = cycles - prevCycles; 1286a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (removedIndex < takeIndex) 1287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cycleDiff++; 1288a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int removedDistance = 1289a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (cycleDiff * len) + (removedIndex - prevTakeIndex); 1290a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert removedDistance >= 0; 1291a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int cursor = this.cursor; 1292a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor >= 0) { 1293a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int x = distance(cursor, prevTakeIndex, len); 1294a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == removedDistance) { 1295a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor == putIndex) 1296a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.cursor = cursor = NONE; 1297a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (x > removedDistance) { 1299a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cursor != prevTakeIndex; 1300a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.cursor = cursor = dec(cursor); 1301a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1302a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1303a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int lastRet = this.lastRet; 1304a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1305a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int x = distance(lastRet, prevTakeIndex, len); 1306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == removedDistance) 1307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = lastRet = REMOVED; 1308a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (x > removedDistance) 1309a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = lastRet = dec(lastRet); 1310a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1311a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int nextIndex = this.nextIndex; 1312a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (nextIndex >= 0) { 1313a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int x = distance(nextIndex, prevTakeIndex, len); 1314a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == removedDistance) 1315a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.nextIndex = nextIndex = REMOVED; 1316a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (x > removedDistance) 1317a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.nextIndex = nextIndex = dec(nextIndex); 1318a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1319a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (cursor < 0 && nextIndex < 0 && lastRet < 0) { 1320a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.prevTakeIndex = DETACHED; 1321a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1322a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1323a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1324a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1325a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1326a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1327a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever takeIndex wraps around to zero. 1328a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1329a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return true if this iterator should be unlinked from itrs 1330a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1331a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean takeIndexWrapped() { 1332a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1333a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (isDetached()) 1334a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1335a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs.cycles - prevCycles > 1) { 1336a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // All the elements that existed at the time of the last 1337a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // operation are gone, so abandon further iteration. 1338a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson shutdown(); 1339a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1340a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1341a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1342a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1343a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1344a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// /** Uncomment for debugging. */ 1345a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// public String toString() { 1346a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// return ("cursor=" + cursor + " " + 1347a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "nextIndex=" + nextIndex + " " + 1348a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "lastRet=" + lastRet + " " + 1349a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "nextItem=" + nextItem + " " + 1350a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "lastItem=" + lastItem + " " + 1351a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "prevCycles=" + prevCycles + " " + 1352a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "prevTakeIndex=" + prevTakeIndex + " " + 1353a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "size()=" + size() + " " + 1354a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "remainingCapacity()=" + remainingCapacity()); 1355a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// } 1356a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1358