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