1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is free software; you can redistribute it and/or modify it 529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * published by the Free Software Foundation. Oracle designates this 729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * particular file as subject to the "Classpath" exception as provided 829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 1129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 1429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * accompanied this code). 1529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * You should have received a copy of the GNU General Public License version 1729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 1829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * or visit www.oracle.com if you need additional information or have any 2229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * questions. 2329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer */ 2429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer 2529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer/* 2629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This file is available under and governed by the GNU General Public 2729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 2829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * However, the following notice accompanied the original version of this 2929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * file: 3029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 33a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent; 37edf43d27e240d82106f39ae91404963c23987234Narayan Kamath 38edf43d27e240d82106f39ae91404963c23987234Narayan Kamathimport java.lang.ref.WeakReference; 39ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniakimport java.util.AbstractQueue; 40b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Arrays; 41a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Collection; 42a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Iterator; 43a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.NoSuchElementException; 44b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Objects; 45b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Spliterator; 46b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Spliterators; 47edf43d27e240d82106f39ae91404963c23987234Narayan Kamathimport java.util.concurrent.locks.Condition; 48edf43d27e240d82106f39ae91404963c23987234Narayan Kamathimport java.util.concurrent.locks.ReentrantLock; 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// BEGIN android-note 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// removed link to collections framework docs 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// END android-note 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * A bounded {@linkplain BlockingQueue blocking queue} backed by an 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * array. This queue orders elements FIFO (first-in-first-out). The 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>head</em> of the queue is that element that has been on the 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the longest time. The <em>tail</em> of the queue is that 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * element that has been on the queue the shortest time. New elements 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * are inserted at the tail of the queue, and the queue retrieval 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operations obtain elements at the head of the queue. 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This is a classic "bounded buffer", in which a 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * fixed-sized array holds elements inserted by producers and 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * extracted by consumers. Once created, the capacity cannot be 668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * changed. Attempts to {@code put} an element into a full queue 678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * will result in the operation blocking; attempts to {@code take} an 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * element from an empty queue will similarly block. 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>This class supports an optional fairness policy for ordering 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting producer and consumer threads. By default, this ordering 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is not guaranteed. However, a queue constructed with fairness set 738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * to {@code true} grants threads access in FIFO order. Fairness 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * generally decreases throughput but reduces variability and avoids 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * starvation. 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 77bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class and its iterator implement all of the 78bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 79bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Iterator} interfaces. 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 83edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * @param <E> the type of elements held in this queue 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class ArrayBlockingQueue<E> extends AbstractQueue<E> 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Serialization ID. This class relies on default serialization 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * even for the items array, which is default-serialized, even if 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * it is empty. Otherwise it could not be declared final, which is 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * necessary here. 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = -817911632652898426L; 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** The queued items */ 978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items; 988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** items index for next take, poll, peek or remove */ 1008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int takeIndex; 1018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** items index for next put, offer, or add */ 1038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int putIndex; 1048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** Number of elements in the queue */ 1068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int count; 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Concurrency control uses the classic two-condition algorithm 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * found in any textbook. 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Main lock guarding all access */ 1148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock; 115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Condition for waiting takes */ 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notEmpty; 118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Condition for waiting puts */ 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final Condition notFull; 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 122a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Shared state for currently active iterators, or null if there 124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * are known not to be any. Allows queue operations to update 125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * iterator state. 126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 127b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak transient Itrs itrs; 128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Internal helper methods 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 132edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * Circularly decrements array index i. 1338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final int dec(int i) { 1358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return ((i == 0) ? items.length : i) - 1; 1368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns item at index i. 1408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 14191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 1428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final E itemAt(int i) { 14391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle return (E) items[i]; 1448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 147bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts element at current put position, advances, and signals. 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Call only when holding lock. 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void enqueue(E x) { 151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert items[putIndex] == null; 153edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final Object[] items = this.items; 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[putIndex] = x; 155edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++putIndex == items.length) putIndex = 0; 156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count++; 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 161bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Extracts element at current take position, advances, and signals. 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Call only when holding lock. 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E dequeue() { 165a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert items[takeIndex] != null; 1678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 16891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 16991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle E x = (E) items[takeIndex]; 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[takeIndex] = null; 171edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++takeIndex == items.length) takeIndex = 0; 172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count--; 173a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.elementDequeued(); 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Deletes item at array index removeIndex. 181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Utility for remove(Object) and iterator.remove. 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Call only when holding lock. 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void removeAt(final int removeIndex) { 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert items[removeIndex] != null; 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert removeIndex >= 0 && removeIndex < items.length; 1888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (removeIndex == takeIndex) { 190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // removing front item; just advance 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project items[takeIndex] = null; 192edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++takeIndex == items.length) takeIndex = 0; 193a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count--; 194a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.elementDequeued(); 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 197a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // an "interior" remove 198a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // slide over all others up through putIndex. 200edf43d27e240d82106f39ae91404963c23987234Narayan Kamath for (int i = removeIndex, putIndex = this.putIndex;;) { 201edf43d27e240d82106f39ae91404963c23987234Narayan Kamath int pred = i; 202edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++i == items.length) i = 0; 203edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (i == putIndex) { 204edf43d27e240d82106f39ae91404963c23987234Narayan Kamath items[pred] = null; 205edf43d27e240d82106f39ae91404963c23987234Narayan Kamath this.putIndex = pred; 206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 208edf43d27e240d82106f39ae91404963c23987234Narayan Kamath items[pred] = items[i]; 209adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 210a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count--; 211a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 212a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.removedAt(removeIndex); 213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull.signal(); 215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates an {@code ArrayBlockingQueue} with the given (fixed) 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity and default access policy. 220bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity the capacity of this queue 2228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code capacity < 1} 223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayBlockingQueue(int capacity) { 225adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(capacity, false); 226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates an {@code ArrayBlockingQueue} with the given (fixed) 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity and the specified access policy. 231bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity the capacity of this queue 2338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param fair if {@code true} then queue accesses for threads blocked 234bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * on insertion or removal, are processed in FIFO order; 2358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if {@code false} the access order is unspecified. 2368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code capacity < 1} 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayBlockingQueue(int capacity, boolean fair) { 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (capacity <= 0) 240adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 2418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.items = new Object[capacity]; 242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock = new ReentrantLock(fair); 243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty = lock.newCondition(); 244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notFull = lock.newCondition(); 245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates an {@code ArrayBlockingQueue} with the given (fixed) 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity, the specified access policy and initially containing the 250adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * elements of the given collection, 251adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 252bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity the capacity of this queue 2548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param fair if {@code true} then queue accesses for threads blocked 255bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * on insertion or removal, are processed in FIFO order; 2568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if {@code false} the access order is unspecified. 257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 2588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code capacity} is less than 2598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code c.size()}, or less than 1. 260bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 261bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ArrayBlockingQueue(int capacity, boolean fair, 264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Collection<? extends E> c) { 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(capacity, fair); 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock = this.lock; 2688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); // Lock only for visibility, not mutual exclusion 2698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 2708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int i = 0; 2718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 272b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (E e : c) 273b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak items[i++] = Objects.requireNonNull(e); 2748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } catch (ArrayIndexOutOfBoundsException ex) { 2758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new IllegalArgumentException(); 2768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson count = i; 2788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson putIndex = (i == capacity) ? 0 : i; 2798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 2808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); 2818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 285bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 286bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 2878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * returning {@code true} upon success and throwing an 2888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code IllegalStateException} if this queue is full. 289bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 290bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 2918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 292bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalStateException if this queue is full 293bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 294bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 295bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean add(E e) { 296bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return super.add(e); 297bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 298bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 299bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 300bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue if it is 301bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * possible to do so immediately without exceeding the queue's capacity, 3028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * returning {@code true} upon success and {@code false} if this queue 303bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is full. This method is generally preferable to method {@link #add}, 304bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * which can fail to insert an element only by throwing an exception. 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 306bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 308bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 309b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Objects.requireNonNull(e); 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (count == items.length) 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project else { 316a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson enqueue(e); 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 318adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 320adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 325bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting 326bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * for space to become available if the queue is full. 327bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 328bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 329bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 330bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 331bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) throws InterruptedException { 332b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Objects.requireNonNull(e); 333bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 334bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lockInterruptibly(); 335bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 3368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == items.length) 3378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson notFull.await(); 338a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson enqueue(e); 339bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 340bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 341bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 342bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 343bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 344bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 345bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue, waiting 346bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * up to the specified wait time for space to become available if 347bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the queue is full. 348bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 349bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws InterruptedException {@inheritDoc} 350bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 352bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 355b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Objects.requireNonNull(e); 356bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson long nanos = unit.toNanos(timeout); 357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 358adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 359adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == items.length) { 361b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (nanos <= 0L) 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 3638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nanos = notFull.awaitNanos(nanos); 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 365a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson enqueue(e); 3668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 372adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 376a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (count == 0) ? null : dequeue(); 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 382bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public E take() throws InterruptedException { 383bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 384bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lockInterruptibly(); 385bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 3868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == 0) 3878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson notEmpty.await(); 388a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeue(); 389bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 390bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 391bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 392bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 393bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll(long timeout, TimeUnit unit) throws InterruptedException { 395bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson long nanos = unit.toNanos(timeout); 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 3998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (count == 0) { 400b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (nanos <= 0L) 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 4028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nanos = notEmpty.awaitNanos(nanos); 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 404a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeue(); 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 41491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle return itemAt(takeIndex); // null when queue is empty 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is overridden to remove the reference to collections 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // greater in size than Integer.MAX_VALUE 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 425bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count; 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 433adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // this doc comment is a modified copy of the inherited doc comment, 438adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // without the reference to unlimited queues. 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 440bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the number of additional elements that this queue can ideally 441bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (in the absence of memory or resource constraints) accept without 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking. This is always equal to the initial capacity of this queue 4438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * less the current {@code size} of this queue. 444bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 445bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 4468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 447bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * because it may be the case that another thread is about to 448bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insert or remove an element. 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return items.length - count; 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 460bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 461bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 4628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if it is present. More formally, removes an element {@code e} such 4638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 464bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 4658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contained the specified element 466bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 467bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 4688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Removal of interior elements in circular array based queues 4698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * is an intrinsically slow and disruptive operation, so should 4708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * be undertaken only in exceptional circumstances, ideally 4718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * only when the queue is known not to be accessible by other 4728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * threads. 4738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 474bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 4758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue changed as a result of the call 476bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 477bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean remove(Object o) { 478bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (o == null) return false; 479bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 480bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lock(); 481bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 482a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count > 0) { 483edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final Object[] items = this.items; 484a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 485a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = takeIndex; 486a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson do { 487a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o.equals(items[i])) { 488a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(i); 489a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 490a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 491edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++i == items.length) i = 0; 492edf43d27e240d82106f39ae91404963c23987234Narayan Kamath } while (i != putIndex); 493bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 4948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 495bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 496bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 497bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 498bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 500bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 5018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns {@code true} if this queue contains the specified element. 5028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * More formally, returns {@code true} if and only if this queue contains 5038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 504bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 505bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o object to be checked for containment in this queue 5068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 507bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 508adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object o) { 509adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 513a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count > 0) { 514edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final Object[] items = this.items; 515a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 516a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = takeIndex; 517a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson do { 518a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o.equals(items[i])) 519a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 520edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++i == items.length) i = 0; 521edf43d27e240d82106f39ae91404963c23987234Narayan Kamath } while (i != putIndex); 522a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 523adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 529bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 530bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 531bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 532bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 533bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 534bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 535bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 536bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 537bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 538bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 539bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 540bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 541bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 542adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 543adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 546edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final Object[] items = this.items; 547edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final int end = takeIndex + count; 548edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final Object[] a = Arrays.copyOfRange(items, takeIndex, end); 549edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (end != putIndex) 550edf43d27e240d82106f39ae91404963c23987234Narayan Kamath System.arraycopy(items, 0, a, items.length - takeIndex, putIndex); 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 553adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 557bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 558bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 559bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 563bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 565bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 566bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 5678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code null}. 568bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 569bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 570bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 571bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 572bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 573bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 5748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 575bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 5768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * allocated array of {@code String}: 577bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 578edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 579bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 5808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 5818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code toArray()}. 582bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 583bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 584bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 585bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 586bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 587bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 588bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 589bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 590bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 591bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 5928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson @SuppressWarnings("unchecked") 593adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 594adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 595adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 596adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 597edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final Object[] items = this.items; 5988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final int count = this.count; 599edf43d27e240d82106f39ae91404963c23987234Narayan Kamath final int firstLeg = Math.min(items.length - takeIndex, count); 600edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (a.length < count) { 601edf43d27e240d82106f39ae91404963c23987234Narayan Kamath a = (T[]) Arrays.copyOfRange(items, takeIndex, takeIndex + count, 602edf43d27e240d82106f39ae91404963c23987234Narayan Kamath a.getClass()); 603edf43d27e240d82106f39ae91404963c23987234Narayan Kamath } else { 604edf43d27e240d82106f39ae91404963c23987234Narayan Kamath System.arraycopy(items, takeIndex, a, 0, firstLeg); 605edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (a.length > count) 606edf43d27e240d82106f39ae91404963c23987234Narayan Kamath a[count] = null; 60791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle } 608edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (firstLeg < count) 609edf43d27e240d82106f39ae91404963c23987234Narayan Kamath System.arraycopy(items, 0, a, firstLeg, putIndex); 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 612adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 614adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 617b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return Helpers.collectionToString(this); 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 620bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 621bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 622bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The queue will be empty after this call returns. 623bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 628a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int k = count; 629a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (k > 0) { 630b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final Object[] items = this.items; 631a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int putIndex = this.putIndex; 632a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = takeIndex; 633a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson do { 634a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson items[i] = null; 635edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++i == items.length) i = 0; 636edf43d27e240d82106f39ae91404963c23987234Narayan Kamath } while (i != putIndex); 637a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson takeIndex = putIndex; 638a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count = 0; 639a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) 640a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.queueIsEmpty(); 641a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (; k > 0 && lock.hasWaiters(notFull); k--) 642a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson notFull.signal(); 643a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 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) { 656a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return drainTo(c, Integer.MAX_VALUE); 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 659bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 660bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 661bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 662bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 663bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 664bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 666b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Objects.requireNonNull(c); 667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (maxElements <= 0) 670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return 0; 6718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Object[] items = this.items; 672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 675a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int n = Math.min(maxElements, count); 676a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int take = takeIndex; 677a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int i = 0; 678a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 679a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while (i < n) { 68091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 68191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle E x = (E) items[take]; 682a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson c.add(x); 683a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson items[take] = null; 684edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++take == items.length) take = 0; 685a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson i++; 686a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 687a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return n; 688a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } finally { 689a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Restore invariants even if c.add() threw 690a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (i > 0) { 691a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson count -= i; 692a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson takeIndex = take; 693a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs != null) { 694a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count == 0) 695a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.queueIsEmpty(); 696a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (i > take) 697a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.takeIndexWrapped(); 698a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 699a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (; i > 0 && lock.hasWaiters(notFull); i--) 700a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson notFull.signal(); 701a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 7108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 7118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 712edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * <p>The returned iterator is 713edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 715bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 716adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 7188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return new Itr(); 719adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 720adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 722a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Shared data between iterators and their queue, allowing queue 723a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * modifications to update iterators when elements are removed. 724a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 725a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * This adds a lot of complexity for the sake of correctly 726a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * handling some uncommon operations, but the combination of 727a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * circular-arrays and supporting interior removes (i.e., those 728a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * not at head) would cause iterators to sometimes lose their 729a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * places and/or (re)report elements they shouldn't. To avoid 730a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this, when a queue has one or more iterators, it keeps iterator 731a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * state consistent by: 732a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 733a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (1) keeping track of the number of "cycles", that is, the 734a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number of times takeIndex has wrapped around to 0. 735a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (2) notifying all iterators via the callback removedAt whenever 736a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * an interior element is removed (and thus other elements may 737a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * be shifted). 738a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 739a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * These suffice to eliminate iterator inconsistencies, but 740a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unfortunately add the secondary responsibility of maintaining 741a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the list of iterators. We track all active iterators in a 742a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * simple linked list (accessed only when the queue's lock is 743a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * held) of weak references to Itr. The list is cleaned up using 744a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 3 different mechanisms: 745a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 746a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (1) Whenever a new iterator is created, do some O(1) checking for 747a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * stale list elements. 748a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 749a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (2) Whenever takeIndex wraps around to 0, check for iterators 750a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that have been unused for more than one wrap-around cycle. 751a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 752a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (3) Whenever the queue becomes empty, all iterators are notified 753a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and this entire data structure is discarded. 754a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 755a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * So in addition to the removedAt callback that is necessary for 756a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * correctness, iterators have the shutdown and takeIndexWrapped 757a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * callbacks that help remove stale iterators from the list. 758a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 759a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Whenever a list element is examined, it is expunged if either 760a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the GC has determined that the iterator is discarded, or if the 761a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * iterator reports that it is "detached" (does not need any 762a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * further state updates). Overhead is maximal when takeIndex 763a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * never advances, iterators are discarded before they are 764a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * exhausted, and all removals are interior removes, in which case 765a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * all stale iterators are discovered by the GC. But even in this 766a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * case we don't increase the amortized complexity. 767a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 768a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Care must be taken to keep list sweeping methods from 769a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * reentrantly invoking another such method, causing subtle 770a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * corruption bugs. 771a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 772a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson class Itrs { 773a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 774a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 775a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Node in a linked list of weak iterator references. 776a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 777a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private class Node extends WeakReference<Itr> { 778a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node next; 779a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 780a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node(Itr iterator, Node next) { 781a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson super(iterator); 782a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.next = next; 783a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 784a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 785a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 786a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Incremented whenever takeIndex wraps around to 0 */ 787edf43d27e240d82106f39ae91404963c23987234Narayan Kamath int cycles; 788a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 789a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Linked list of weak iterator references */ 790a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node head; 791a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 792a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Used to expunge stale iterators */ 793edf43d27e240d82106f39ae91404963c23987234Narayan Kamath private Node sweeper; 794a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 795a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int SHORT_SWEEP_PROBES = 4; 796a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int LONG_SWEEP_PROBES = 16; 797a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 798a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Itrs(Itr initial) { 799a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson register(initial); 800a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 801a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 802a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 803a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Sweeps itrs, looking for and expunging stale iterators. 804a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * If at least one was found, tries harder to find more. 805a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called only from iterating thread. 806a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 807a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param tryHarder whether to start in try-harder mode, because 808a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * there is known to be at least one iterator to collect 809a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 810a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void doSomeSweeping(boolean tryHarder) { 811a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 812a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert head != null; 813a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES; 814a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node o, p; 815a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node sweeper = this.sweeper; 816a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean passedGo; // to limit search to one full sweep 817a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 818a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (sweeper == null) { 819a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = null; 820a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = head; 821a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson passedGo = true; 822a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 823a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = sweeper; 824a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = o.next; 825a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson passedGo = false; 826a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 827a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 828a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (; probes > 0; probes--) { 829a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == null) { 830a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (passedGo) 831a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 832a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = null; 833a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = head; 834a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson passedGo = true; 835a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 836a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Itr it = p.get(); 837a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node next = p.next; 838a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it == null || it.isDetached()) { 839a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // found a discarded/exhausted iterator 840a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson probes = LONG_SWEEP_PROBES; // "try harder" 841a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // unlink p 842a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 843a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.next = null; 844a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o == null) { 845a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = next; 846a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (next == null) { 847a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // We've run out of iterators to track; retire 848a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 849a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return; 850a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 851a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 852a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 853a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o.next = next; 854a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 855a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = p; 856a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 857a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = next; 858a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 859a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 860a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.sweeper = (p == null) ? null : o; 861a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 862a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 863a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 864a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Adds a new iterator to the linked list of tracked iterators. 865a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 866a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void register(Itr itr) { 867a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 868a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = new Node(itr, head); 869a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 870a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 871a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 872a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever takeIndex wraps around to 0. 873a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 874a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Notifies all iterators, and expunges any that are now stale. 875a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 876a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void takeIndexWrapped() { 877a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 878a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cycles++; 879a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node o = null, p = head; p != null;) { 880a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Itr it = p.get(); 881a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node next = p.next; 882a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it == null || it.takeIndexWrapped()) { 883a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // unlink p 884a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert it == null || it.isDetached(); 885a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 886a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.next = null; 887a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o == null) 888a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = next; 889a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 890a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o.next = next; 891a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 892a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = p; 893a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 894a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = next; 895a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 896a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head == null) // no more iterators to track 897a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 898a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 899a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 900a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 901edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * Called whenever an interior remove (not at takeIndex) occurred. 902a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 903a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Notifies all iterators, and expunges any that are now stale. 904a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 905a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void removedAt(int removedIndex) { 906a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node o = null, p = head; p != null;) { 907a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Itr it = p.get(); 908a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node next = p.next; 909a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it == null || it.removedAt(removedIndex)) { 910a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // unlink p 911a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert it == null || it.isDetached(); 912a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 913a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.next = null; 914a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (o == null) 915a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = next; 916a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 917a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o.next = next; 918a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 919a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson o = p; 920a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 921a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = next; 922a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 923a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head == null) // no more iterators to track 924a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 925a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 926a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 927a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 928a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever the queue becomes empty. 929a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 930a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Notifies all active iterators that the queue is empty, 931a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * clears all weak refs, and unlinks the itrs datastructure. 932a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 933a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void queueIsEmpty() { 934a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 935a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node p = head; p != null; p = p.next) { 936a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Itr it = p.get(); 937a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (it != null) { 938a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.clear(); 939a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson it.shutdown(); 940a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 941a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 942a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson head = null; 943a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = null; 944a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 945a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 946a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 947a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever an element has been dequeued (at takeIndex). 948a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 949a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void elementDequeued() { 950a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 951a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count == 0) 952a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson queueIsEmpty(); 953a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (takeIndex == 0) 954a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson takeIndexWrapped(); 955a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 956a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 957a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 958a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 959a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Iterator for ArrayBlockingQueue. 960a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 961a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * To maintain weak consistency with respect to puts and takes, we 962a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * read ahead one slot, so as to not report hasNext true but then 963a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * not have an element to return. 964a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 965a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We switch into "detached" mode (allowing prompt unlinking from 966a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * itrs without help from the GC) when all indices are negative, or 967a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * when hasNext returns false for the first time. This allows the 968a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * iterator to track concurrent updates completely accurately, 969a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * except for the corner case of the user calling Iterator.remove() 970a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * after hasNext() returned false. Even in this case, we ensure 971a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that we don't remove the wrong element by keeping track of the 972a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * expected element to remove, in lastItem. Yes, we may fail to 973a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * remove lastItem from the queue if it moved due to an interleaved 974a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * interior remove while in detached mode. 975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 976adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 977a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Index to look for new nextItem; NONE at end */ 978a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int cursor; 979a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 980a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Element to be returned by next call to next(); null if none */ 981a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E nextItem; 982a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 983a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Index of nextItem; NONE if none, REMOVED if removed elsewhere */ 984a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int nextIndex; 985a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 986a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Last element returned; null if none or not detached. */ 987a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E lastItem; 988a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 989a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Index of lastItem, NONE if none, REMOVED if removed elsewhere */ 990a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int lastRet; 991a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 992a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Previous value of takeIndex, or DETACHED when detached */ 993a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int prevTakeIndex; 994a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 995a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Previous value of iters.cycles */ 996a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int prevCycles; 997a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 998a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Special index value indicating "not available" or "undefined" */ 999a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int NONE = -1; 1000a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1001a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1002a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Special index value indicating "removed elsewhere", that is, 1003a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * removed by some operation other than a call to this.remove(). 1004a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1005a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int REMOVED = -2; 1006a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1007a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** Special value for prevTakeIndex indicating "detached mode" */ 1008a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int DETACHED = -3; 1009adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1010adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 1011a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1012a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastRet = NONE; 10138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock = ArrayBlockingQueue.this.lock; 10148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); 10158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 1016a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (count == 0) { 1017a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert itrs == null; 1018a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = NONE; 1019a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = NONE; 1020a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = DETACHED; 1021a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 1022a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int takeIndex = ArrayBlockingQueue.this.takeIndex; 1023a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = takeIndex; 10248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nextItem = itemAt(nextIndex = takeIndex); 1025a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = incCursor(takeIndex); 1026a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs == null) { 1027a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs = new Itrs(this); 1028a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 1029a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.register(this); // in this order 1030a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.doSomeSweeping(false); 1031a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1032a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevCycles = itrs.cycles; 1033a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert takeIndex >= 0; 1034a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert prevTakeIndex == takeIndex; 1035a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex >= 0; 1036a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextItem != null; 1037a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 10388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 10398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); 1040adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1041adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1042adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1043a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean isDetached() { 1044a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1045a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return prevTakeIndex < 0; 1046a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1047a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1048a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int incCursor(int index) { 1049a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1050edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (++index == items.length) index = 0; 1051edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (index == putIndex) index = NONE; 1052a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return index; 1053a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1054a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1055a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1056a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns true if index is invalidated by the given number of 1057a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * dequeues, starting from prevTakeIndex. 1058a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1059a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private boolean invalidated(int index, int prevTakeIndex, 1060a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long dequeues, int length) { 1061a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (index < 0) 1062a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1063a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int distance = index - prevTakeIndex; 1064a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (distance < 0) 1065a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson distance += length; 1066a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeues > distance; 1067a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1068a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1069a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1070a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Adjusts indices to incorporate all dequeues since the last 1071a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * operation on this iterator. Call only from iterating thread. 1072a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1073a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void incorporateDequeues() { 1074a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1075a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert itrs != null; 1076a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert !isDetached(); 1077a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert count > 0; 1078a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1079a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int cycles = itrs.cycles; 1080a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int takeIndex = ArrayBlockingQueue.this.takeIndex; 1081a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevCycles = this.prevCycles; 1082a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevTakeIndex = this.prevTakeIndex; 1083a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1084a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cycles != prevCycles || takeIndex != prevTakeIndex) { 1085a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int len = items.length; 1086a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // how far takeIndex has advanced since the previous 1087a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // operation of this iterator 1088a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long dequeues = (cycles - prevCycles) * len 1089a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson + (takeIndex - prevTakeIndex); 1090a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1091a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Check indices for invalidation 1092a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (invalidated(lastRet, prevTakeIndex, dequeues, len)) 1093a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastRet = REMOVED; 1094a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (invalidated(nextIndex, prevTakeIndex, dequeues, len)) 1095a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = REMOVED; 1096a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (invalidated(cursor, prevTakeIndex, dequeues, len)) 1097a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = takeIndex; 1098a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1099a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor < 0 && nextIndex < 0 && lastRet < 0) 1100a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson detach(); 1101a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 1102a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.prevCycles = cycles; 1103a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.prevTakeIndex = takeIndex; 1104a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1105a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1106a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1107a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called when itrs should stop tracking this iterator, either 1110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * because there are no more indices to update (cursor < 0 && 1111a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nextIndex < 0 && lastRet < 0) or as a special exception, when 1112a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * lastRet >= 0, because hasNext() is about to return false for the 1113a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * first time. Call only from iterating thread. 1114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void detach() { 1116a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Switch to detached mode 1117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cursor == NONE; 1119a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex < 0; 1120a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet < 0 || nextItem == null; 1121a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet < 0 ^ lastItem != null; 1122a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (prevTakeIndex >= 0) { 1123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert itrs != null; 1124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = DETACHED; 1125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // try to unlink from itrs (but not too hard) 1126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itrs.doSomeSweeping(true); 1127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1129a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1130a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1131a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * For performance reasons, we would like not to acquire a lock in 1132a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * hasNext in the common case. To allow for this, we only access 1133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * fields (i.e. nextItem) that are not modified by update operations 1134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * triggered by queue modifications. 1135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 1137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (nextItem != null) 1139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1140a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson noNext(); 1141a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1143a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1144a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void noNext() { 1145a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final ReentrantLock lock = ArrayBlockingQueue.this.lock; 1146a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lock.lock(); 1147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 1148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cursor == NONE; 1149a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex == NONE; 1150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) { 1151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet >= 0; 1152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson incorporateDequeues(); // might update lastRet 1153a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastItem = itemAt(lastRet); 1155a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem != null; 1156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson detach(); 1157a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1158a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1159a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert isDetached(); 1160a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet < 0 ^ lastItem != null; 1161a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } finally { 1162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lock.unlock(); 1163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 1167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final E x = nextItem; 1169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == null) 1170a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new NoSuchElementException(); 1171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = ArrayBlockingQueue.this.lock; 1172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 1173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) 1175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson incorporateDequeues(); 1176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextIndex != NONE; 1177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem == null; 1178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = nextIndex; 1179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int cursor = this.cursor; 1180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor >= 0) { 1181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextItem = itemAt(nextIndex = cursor); 1182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert nextItem != null; 1183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.cursor = incCursor(cursor); 1184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else { 1185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = NONE; 1186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextItem = null; 11878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 1189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 1190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1191a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return x; 1192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 1195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 0; 1196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = ArrayBlockingQueue.this.lock; 1197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 1198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1199a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) 1200a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson incorporateDequeues(); // might update lastRet or detach 1201a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int lastRet = this.lastRet; 1202a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = NONE; 1203a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1204a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!isDetached()) 1205a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(lastRet); 1206a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 1207a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final E lastItem = this.lastItem; 1208a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem != null; 1209a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastItem = null; 1210a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itemAt(lastRet) == lastItem) 1211a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(lastRet); 1212a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1213a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } else if (lastRet == NONE) 1214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 1215a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // else lastRet == REMOVED and the last returned element was 1216a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // previously asynchronously removed via an operation other 1217a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // than this.remove(), so nothing to do. 1218a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1219a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor < 0 && nextIndex < 0) 1220a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson detach(); 1221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 1222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 1223a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastRet == NONE; 1224a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lastItem == null; 1225adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 12278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1228a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1229a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called to notify the iterator that the queue is empty, or that it 1230a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * has fallen hopelessly behind, so that it should abandon any 1231a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * further iteration, except possibly to return one more element 1232a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * from next(), as promised by returning true from hasNext(). 1233a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1234a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void shutdown() { 1235a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1236a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson cursor = NONE; 1237a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (nextIndex >= 0) 1238a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextIndex = REMOVED; 1239a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1240a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastRet = REMOVED; 1241a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastItem = null; 1242a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1243a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson prevTakeIndex = DETACHED; 1244a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Don't set nextItem to null because we must continue to be 1245a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // able to return it on next(). 1246a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // 1247a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Caller will unlink from itrs when convenient. 1248a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1249a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1250a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int distance(int index, int prevTakeIndex, int length) { 1251a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int distance = index - prevTakeIndex; 1252a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (distance < 0) 1253a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson distance += length; 1254a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return distance; 1255a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1256a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1257a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1258edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * Called whenever an interior remove (not at takeIndex) occurred. 1259a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1260a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return true if this iterator should be unlinked from itrs 1261a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1262a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean removedAt(int removedIndex) { 1263a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (isDetached()) 1265a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1266a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1267a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int takeIndex = ArrayBlockingQueue.this.takeIndex; 1268a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int prevTakeIndex = this.prevTakeIndex; 1269a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int len = items.length; 1270edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // distance from prevTakeIndex to removedIndex 1271a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int removedDistance = 1272edf43d27e240d82106f39ae91404963c23987234Narayan Kamath len * (itrs.cycles - this.prevCycles 1273edf43d27e240d82106f39ae91404963c23987234Narayan Kamath + ((removedIndex < takeIndex) ? 1 : 0)) 1274edf43d27e240d82106f39ae91404963c23987234Narayan Kamath + (removedIndex - prevTakeIndex); 1275edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // assert itrs.cycles - this.prevCycles >= 0; 1276edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // assert itrs.cycles - this.prevCycles <= 1; 1277edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // assert removedDistance > 0; 1278edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // assert removedIndex != takeIndex; 1279a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int cursor = this.cursor; 1280a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor >= 0) { 1281a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int x = distance(cursor, prevTakeIndex, len); 1282a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == removedDistance) { 1283a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (cursor == putIndex) 1284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.cursor = cursor = NONE; 1285a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1286a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (x > removedDistance) { 1287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cursor != prevTakeIndex; 1288a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.cursor = cursor = dec(cursor); 1289a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1290a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1291a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int lastRet = this.lastRet; 1292a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet >= 0) { 1293a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int x = distance(lastRet, prevTakeIndex, len); 1294a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == removedDistance) 1295a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = lastRet = REMOVED; 1296a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (x > removedDistance) 1297a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = lastRet = dec(lastRet); 1298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1299a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int nextIndex = this.nextIndex; 1300a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (nextIndex >= 0) { 1301a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int x = distance(nextIndex, prevTakeIndex, len); 1302a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x == removedDistance) 1303a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.nextIndex = nextIndex = REMOVED; 1304a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (x > removedDistance) 1305a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.nextIndex = nextIndex = dec(nextIndex); 1306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1307edf43d27e240d82106f39ae91404963c23987234Narayan Kamath if (cursor < 0 && nextIndex < 0 && lastRet < 0) { 1308a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.prevTakeIndex = DETACHED; 1309a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1310a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1311a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1312a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1313a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1314a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1315a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Called whenever takeIndex wraps around to zero. 1316a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1317a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return true if this iterator should be unlinked from itrs 1318a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1319a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean takeIndexWrapped() { 1320a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert lock.getHoldCount() == 1; 1321a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (isDetached()) 1322a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1323a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (itrs.cycles - prevCycles > 1) { 1324a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // All the elements that existed at the time of the last 1325a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // operation are gone, so abandon further iteration. 1326a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson shutdown(); 1327a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1328a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1329a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1330a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1331a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1332a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// /** Uncomment for debugging. */ 1333a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// public String toString() { 1334a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// return ("cursor=" + cursor + " " + 1335a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "nextIndex=" + nextIndex + " " + 1336a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "lastRet=" + lastRet + " " + 1337a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "nextItem=" + nextItem + " " + 1338a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "lastItem=" + lastItem + " " + 1339a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "prevCycles=" + prevCycles + " " + 1340a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "prevTakeIndex=" + prevTakeIndex + " " + 1341a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "size()=" + size() + " " + 1342a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// "remainingCapacity()=" + remainingCapacity()); 1343a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// } 1344a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1345edf43d27e240d82106f39ae91404963c23987234Narayan Kamath 1346b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 1347b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Returns a {@link Spliterator} over the elements in this queue. 1348b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1349b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>The returned spliterator is 1350b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1351b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1352b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 1353b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. 1354b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1355b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @implNote 1356b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The {@code Spliterator} implements {@code trySplit} to permit limited 1357b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * parallelism. 1358b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1359b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return a {@code Spliterator} over the elements in this queue 1360b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @since 1.8 1361b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 1362b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public Spliterator<E> spliterator() { 1363b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return Spliterators.spliterator 1364b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (this, (Spliterator.ORDERED | 1365b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Spliterator.NONNULL | 1366b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Spliterator.CONCURRENT)); 1367b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1368b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1370