1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent; 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 98eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonimport java.util.concurrent.locks.*; 108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonimport java.util.*; 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// BEGIN android-note 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// removed link to collections framework docs 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// END android-note 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An unbounded {@linkplain BlockingQueue blocking queue} that uses 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the same ordering rules as class {@link PriorityQueue} and supplies 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking retrieval operations. While this queue is logically 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * unbounded, attempted additions may fail due to resource exhaustion 218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (causing {@code OutOfMemoryError}). This class does not permit 228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code null} elements. A priority queue relying on {@linkplain 23bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Comparable natural ordering} also does not permit insertion of 24bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * non-comparable objects (doing so results in 258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code ClassCastException}). 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 27bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class and its iterator implement all of the 28bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 29bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Iterator} interfaces. The Iterator provided in method {@link 30bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * #iterator()} is <em>not</em> guaranteed to traverse the elements of 31bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the PriorityBlockingQueue in any particular order. If you need 32bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ordered traversal, consider using 338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code Arrays.sort(pq.toArray())}. Also, method {@code drainTo} 34bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * can be used to <em>remove</em> some or all elements in priority 35bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * order and place them in another collection. 36bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 37bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Operations on this class make no guarantees about the ordering 38bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of elements with equal priority. If you need to enforce an 39bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ordering, you can define custom classes or comparators that use a 40bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * secondary key to break ties in primary priority values. For 41bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * example, here is a class that applies first-in-first-out 42bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * tie-breaking to comparable elements. To use it, you would insert a 438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code new FIFOEntry(anEntry)} instead of a plain entry object. 44bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <pre> {@code 468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * class FIFOEntry<E extends Comparable<? super E>> 478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * implements Comparable<FIFOEntry<E>> { 488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * static final AtomicLong seq = new AtomicLong(0); 49bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * final long seqNum; 50bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * final E entry; 51bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public FIFOEntry(E entry) { 52bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * seqNum = seq.getAndIncrement(); 53bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this.entry = entry; 54bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 55bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public E getEntry() { return entry; } 568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * public int compareTo(FIFOEntry<E> other) { 57bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * int res = entry.compareTo(other.entry); 588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if (res == 0 && other.entry != this.entry) 598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * res = (seqNum < other.seqNum ? -1 : 1); 60bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return res; 61bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * }}</pre> 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param <E> the type of elements held in this collection 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class PriorityBlockingQueue<E> extends AbstractQueue<E> 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 5595510919245408276L; 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /* 738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The implementation uses an array-based binary heap, with public 748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * operations protected with a single lock. However, allocation 758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * during resizing uses a simple spinlock (used only while not 768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * holding main lock) in order to allow takes to operate 778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * concurrently with allocation. This avoids repeated 788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * postponement of waiting consumers and consequent element 798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * build-up. The need to back away from lock during allocation 808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * makes it impossible to simply wrap delegated 818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * java.util.PriorityQueue operations within a lock, as was done 828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * in a previous version of this class. To maintain 838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * interoperability, a plain PriorityQueue is still used during 84a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * serialization, which maintains compatibility at the expense of 858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * transiently doubling overhead. 868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Default array capacity. 908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static final int DEFAULT_INITIAL_CAPACITY = 11; 928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The maximum size of array to allocate. 958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Some VMs reserve some header words in an array. 968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Attempts to allocate larger arrays may result in 978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * OutOfMemoryError: Requested array size exceeds VM limit 988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 1008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Priority queue represented as a balanced binary heap: the two 1038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The 1048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * priority queue is ordered by comparator, or by the elements' 1058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * natural ordering, if comparator is null: For each node n in the 1068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * heap and each descendant d of n, n <= d. The element with the 1078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * lowest value is in queue[0], assuming the queue is nonempty. 1088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient Object[] queue; 1108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The number of elements in the priority queue. 1138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient int size; 1158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The comparator, or null if priority queue uses elements' 1188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * natural ordering. 1198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient Comparator<? super E> comparator; 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Lock used for all public operations 1248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private final ReentrantLock lock; 1268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Condition for blocking when empty 1298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private final Condition notEmpty; 1318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Spinlock for allocation, acquired via CAS. 1348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient volatile int allocationSpinLock; 1368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * A plain PriorityQueue used only for serialization, 1398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * to maintain compatibility with previous versions 1408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of this class. Non-null only during serialization/deserialization. 1418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private PriorityQueue<E> q; 1438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} with the default 146bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * initial capacity (11) that orders its elements according to 147bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * their {@linkplain Comparable natural ordering}. 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue() { 1508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this(DEFAULT_INITIAL_CAPACITY, null); 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} with the specified 155bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * initial capacity that orders its elements according to their 156bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@linkplain Comparable natural ordering}. 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 158bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param initialCapacity the initial capacity for this priority queue 1598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code initialCapacity} is less 160bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than 1 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue(int initialCapacity) { 1638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this(initialCapacity, null); 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} with the specified initial 168bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * capacity that orders its elements according to the specified 169bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * comparator. 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 171bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param initialCapacity the initial capacity for this priority queue 172bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param comparator the comparator that will be used to order this 173bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue. If {@code null}, the {@linkplain Comparable 174bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * natural ordering} of the elements will be used. 1758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code initialCapacity} is less 176bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than 1 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue(int initialCapacity, 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Comparator<? super E> comparator) { 1808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (initialCapacity < 1) 1818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new IllegalArgumentException(); 1828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.lock = new ReentrantLock(); 1838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.notEmpty = lock.newCondition(); 1848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.comparator = comparator; 1858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.queue = new Object[initialCapacity]; 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} containing the elements 190bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * in the specified collection. If the specified collection is a 191bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link SortedSet} or a {@link PriorityQueue}, this 192bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue will be ordered according to the same ordering. 193bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Otherwise, this priority queue will be ordered according to the 194bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@linkplain Comparable natural ordering} of its elements. 195adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 196bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param c the collection whose elements are to be placed 197bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * into this priority queue 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException if elements of the specified collection 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cannot be compared to one another according to the priority 200bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * queue's ordering 201bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 202bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue(Collection<? extends E> c) { 2058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.lock = new ReentrantLock(); 2068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.notEmpty = lock.newCondition(); 2078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson boolean heapify = true; // true if not known to be in heap order 2088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson boolean screen = true; // true if must screen for nulls 2098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (c instanceof SortedSet<?>) { 2108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson SortedSet<? extends E> ss = (SortedSet<? extends E>) c; 2118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.comparator = (Comparator<? super E>) ss.comparator(); 2128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson heapify = false; 2138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (c instanceof PriorityBlockingQueue<?>) { 2158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson PriorityBlockingQueue<? extends E> pq = 2168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (PriorityBlockingQueue<? extends E>) c; 2178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.comparator = (Comparator<? super E>) pq.comparator(); 2188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson screen = false; 2198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (pq.getClass() == PriorityBlockingQueue.class) // exact match 2208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson heapify = false; 2218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] a = c.toArray(); 2238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = a.length; 2248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // If c.toArray incorrectly doesn't return Object[], copy it. 2258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a.getClass() != Object[].class) 2268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson a = Arrays.copyOf(a, n, Object[].class); 2278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (screen && (n == 1 || this.comparator != null)) { 2288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; ++i) 2298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a[i] == null) 2308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 2318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.queue = a; 2338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.size = n; 2348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (heapify) 2358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson heapify(); 2368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 2388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 2398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Tries to grow array to accommodate at least one more element 2408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (but normally expand by about 50%), giving up (allowing retry) 2418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * on contention (which we expect to be rare). Call only while 2428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * holding lock. 2438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 2448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param array the heap array 2458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param oldCap the length of the array 2468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 2478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void tryGrow(Object[] array, int oldCap) { 2488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); // must release and then re-acquire main lock 2498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] newArray = null; 2508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (allocationSpinLock == 0 && 2518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset, 2528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 0, 1)) { 2538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 2548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int newCap = oldCap + ((oldCap < 64) ? 2558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (oldCap + 2) : // grow faster if small 2568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (oldCap >> 1)); 2578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newCap - MAX_ARRAY_SIZE > 0) { // possible overflow 2588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int minCap = oldCap + 1; 2598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (minCap < 0 || minCap > MAX_ARRAY_SIZE) 2608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new OutOfMemoryError(); 2618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson newCap = MAX_ARRAY_SIZE; 2628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newCap > oldCap && queue == array) 2648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson newArray = new Object[newCap]; 2658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 2668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson allocationSpinLock = 0; 2678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newArray == null) // back off if another thread is allocating 2708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Thread.yield(); 2718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); 2728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newArray != null && queue == array) { 2738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson queue = newArray; 2748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson System.arraycopy(array, 0, newArray, 0, oldCap); 2758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 2788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 2798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Mechanics for poll(). Call only while holding lock. 2808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 281a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E dequeue() { 2828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size - 1; 2838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (n < 0) 284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return null; 2858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 2868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E result = (E) array[0]; 2888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E x = (E) array[n]; 2898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[n] = null; 2908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 2918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 2928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownComparable(0, x, array, n); 2938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 2948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownUsingComparator(0, x, array, n, cmp); 2958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = n; 296a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return result; 2978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 3018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts item x at position k, maintaining heap invariant by 3028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * promoting x up the tree until it is greater than or equal to 3038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * its parent, or is the root. 3048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 3058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * To simplify and speed up coercions and comparisons. the 3068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Comparable and Comparator versions are separated into different 3078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * methods that are otherwise identical. (Similarly for siftDown.) 3088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * These methods are static, with heap state as arguments, to 3098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * simplify use in light of possible comparator exceptions. 3108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 3118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param k the position to fill 3128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param x the item to insert 3138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param array the heap array 314a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param n heap size 3158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 3168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftUpComparable(int k, T x, Object[] array) { 3178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparable<? super T> key = (Comparable<? super T>) x; 3188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (k > 0) { 3198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int parent = (k - 1) >>> 1; 3208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object e = array[parent]; 3218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (key.compareTo((T) e) >= 0) 3228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 3238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = e; 3248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson k = parent; 3258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = key; 3278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftUpUsingComparator(int k, T x, Object[] array, 3308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super T> cmp) { 3318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (k > 0) { 3328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int parent = (k - 1) >>> 1; 3338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object e = array[parent]; 3348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp.compare(x, (T) e) >= 0) 3358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 3368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = e; 3378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson k = parent; 3388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = x; 3408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 3438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts item x at position k, maintaining heap invariant by 3448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * demoting x down the tree repeatedly until it is less than or 3458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * equal to its children or is a leaf. 3468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 3478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param k the position to fill 3488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param x the item to insert 3498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param array the heap array 3508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param n heap size 3518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 3528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftDownComparable(int k, T x, Object[] array, 3538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n) { 3548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparable<? super T> key = (Comparable<? super T>)x; 3558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int half = n >>> 1; // loop while a non-leaf 3568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (k < half) { 3578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int child = (k << 1) + 1; // assume left child is least 3588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object c = array[child]; 3598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int right = child + 1; 3608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (right < n && 3618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) 3628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson c = array[child = right]; 3638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (key.compareTo((T) c) <= 0) 3648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 3658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = c; 3668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson k = child; 3678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = key; 3698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftDownUsingComparator(int k, T x, Object[] array, 3728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n, 3738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super T> cmp) { 3748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int half = n >>> 1; 3758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (k < half) { 3768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int child = (k << 1) + 1; 3778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object c = array[child]; 3788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int right = child + 1; 3798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (right < n && cmp.compare((T) c, (T) array[right]) > 0) 3808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson c = array[child = right]; 3818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp.compare(x, (T) c) <= 0) 3828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 3838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = c; 3848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson k = child; 3858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = x; 3878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 3908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Establishes the heap invariant (described above) in the entire tree, 3918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * assuming nothing about the order of the elements prior to the call. 3928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 3938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void heapify() { 3948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 3958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 3968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int half = (n >>> 1) - 1; 3978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 3988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) { 3998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = half; i >= 0; i--) 4008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownComparable(i, (E) array[i], array, n); 4018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 4028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 4038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = half; i >= 0; i--) 4048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownUsingComparator(i, (E) array[i], array, n, cmp); 4058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 409bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element into this priority queue. 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 411bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 4128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException if the specified element cannot be compared 414bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 415bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 416bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 418bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean add(E e) { 419bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return offer(e); 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified element into this priority queue. 4248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never return {@code false}. 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 426bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 4278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by {@link Queue#offer}) 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException if the specified element cannot be compared 429bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 431bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 433bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 4348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (e == null) 4358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 4388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n, cap; 4398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array; 4408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while ((n = size) >= (cap = (array = queue).length)) 4418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson tryGrow(array, cap); 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 4438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 4448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 4458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpComparable(n, e, array); 4468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 4478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpUsingComparator(n, e, array, cmp); 4488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = n + 1; 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 4578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts the specified element into this priority queue. 4588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never block. 459bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 460bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 461bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException if the specified element cannot be compared 462bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 463bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 464bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 466bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) { 467bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson offer(e); // never need to block 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 4718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts the specified element into this priority queue. 4728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never block or 4738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * return {@code false}. 474bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 475bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param timeout This parameter is ignored as the method never blocks 477adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param unit This parameter is ignored as the method never blocks 4788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by 479a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer}) 480bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException if the specified element cannot be compared 481bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 482bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 483bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 485bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) { 486bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return offer(e); // never need to block 487bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 488bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 489bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public E poll() { 490bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 491bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lock(); 492bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 493a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeue(); 494bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 495bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 496bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 497adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E take() throws InterruptedException { 500adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 501adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 5028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E result; 503adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 504a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ( (result = dequeue()) == null) 5058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson notEmpty.await(); 506adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 508adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return result; 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll(long timeout, TimeUnit unit) throws InterruptedException { 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 5168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E result; 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 518a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ( (result = dequeue()) == null && nanos > 0) 5198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nanos = notEmpty.awaitNanos(nanos); 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 522adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return result; 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 530a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (size == 0) ? null : (E) queue[0]; 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 533adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 536bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 537bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the comparator used to order the elements in this queue, 5388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * or {@code null} if this queue uses the {@linkplain Comparable 539bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * natural ordering} of its elements. 540bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 541bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the comparator used to order the elements in this queue, 5428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * or {@code null} if this queue uses the natural 543bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ordering of its elements 544bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 545bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public Comparator<? super E> comparator() { 5468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return comparator; 547bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 548bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return size; 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 5608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Always returns {@code Integer.MAX_VALUE} because 5618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * a {@code PriorityBlockingQueue} is not capacity constrained. 5628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code Integer.MAX_VALUE} always 563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return Integer.MAX_VALUE; 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 5688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private int indexOf(Object o) { 5698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o != null) { 5708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 5718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 5728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; i++) 5738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o.equals(array[i])) 5748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return i; 5758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return -1; 5778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 5808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Removes the ith element from queue. 5818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 5828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void removeAt(int i) { 5838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 5848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size - 1; 5858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (n == i) // removed last element 5868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[i] = null; 5878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 5888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E moved = (E) array[n]; 5898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[n] = null; 5908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 5918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 5928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownComparable(i, moved, array, n); 5938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 5948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownUsingComparator(i, moved, array, n, cmp); 5958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (array[i] == moved) { 5968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 5978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpComparable(i, moved, array); 5988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 5998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpUsingComparator(i, moved, array, cmp); 6008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = n; 6038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 605bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 606bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 607bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if it is present. More formally, removes an element {@code e} such 608bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 609bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. Returns {@code true} if and only if this queue contained 610bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified element (or equivalently, if this queue changed as a 611bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * result of the call). 612bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 613bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 6148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue changed as a result of the call 615bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int i = indexOf(o); 621a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (i == -1) 622a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 623a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(i); 624a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 6258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 6268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); 6278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 6308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 6318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Identity-based version for use in Itr.remove 6328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 633a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void removeEQ(Object o) { 6348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock = this.lock; 6358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); 6368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 6378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 638a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (int i = 0, n = size; i < n; i++) { 6398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o == array[i]) { 6408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson removeAt(i); 6418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 6428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6438eb35c835be1345d3873a82cc9e42f944d698afdJesse 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 * Returns {@code true} if this queue contains the specified element. 651bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * More formally, returns {@code true} if and only if this queue contains 652bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 653bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 654bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o object to be checked for containment in this queue 6558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 656bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object o) { 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 661a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return indexOf(o) != -1; 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 667bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 668bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue. 669bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The returned array elements are in no particular order. 670bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 671bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 672bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 673bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 674bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 675bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 676bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 677bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 678bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 679bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return Arrays.copyOf(queue, size); 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 6958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (n == 0) 6968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return "[]"; 6978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson StringBuilder sb = new StringBuilder(); 6988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append('['); 6998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; ++i) { 700a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object e = queue[i]; 7018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(e == this ? "(this Collection)" : e); 7028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (i != n - 1) 7038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(',').append(' '); 7048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 7058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return sb.append(']').toString(); 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 711bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 712bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 713bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 714bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 715bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 716bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c) { 718a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return drainTo(c, Integer.MAX_VALUE); 719adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 720adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 721bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 722bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 723bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 724bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 725bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 726bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 727adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == null) 729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NullPointerException(); 730adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (maxElements <= 0) 733adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return 0; 734adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 736adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 737a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int n = Math.min(size, maxElements); 738a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (int i = 0; i < n; i++) { 739a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson c.add((E) queue[0]); // In this order, in case add() throws. 740a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson dequeue(); 741adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 742adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return n; 743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 744adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 745adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 746adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 747adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 748adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 749bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 750adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The queue will be empty after this call returns. 751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 752adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 754adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 755adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 7568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 7578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 7588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = 0; 7598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; i++) 7608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[i] = null; 761adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 762adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 763adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 764adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 765adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 766bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 767bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue; the 768bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the returned array is that of the specified array. 769bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The returned array elements are in no particular order. 770bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * If the queue fits in the specified array, it is returned therein. 771bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Otherwise, a new array is allocated with the runtime type of the 772bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * specified array and the size of this queue. 773bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 774bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 775bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 776bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 7778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code null}. 778bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 779bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 780bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 781bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 782bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 783bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 7848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 785bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 7868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * allocated array of {@code String}: 787bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 788a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 789bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 7908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 7918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code toArray()}. 792bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 793bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 794bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 795bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 796bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 797bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 798bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 799bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 800bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 801bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 802adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 803adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 804adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 805adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 8068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 8078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a.length < n) 8088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Make a new array of a's runtime type, but my contents: 8098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return (T[]) Arrays.copyOf(queue, size, a.getClass()); 8108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson System.arraycopy(queue, 0, a, 0, n); 8118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a.length > n) 8128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson a[n] = null; 8138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return a; 814adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 817adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 818adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 819adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 820adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue. The 821adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * iterator does not return the elements in any particular order. 8228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 8238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 8248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 825bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 826bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements as they existed upon construction of the iterator, and 827bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * may (but is not guaranteed to) reflect any modifications 828bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * subsequent to construction. 829adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 830bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue 831adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 832adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 833bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return new Itr(toArray()); 834adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 835adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 836bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 837bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Snapshot iterator that works off copy of underlying q array. 838bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 8398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final class Itr implements Iterator<E> { 840bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final Object[] array; // Array of all elements 841a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int cursor; // index of next element to return 842bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int lastRet; // index of last element, or -1 if no such 843bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 844bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Itr(Object[] array) { 845bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastRet = -1; 846bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson this.array = array; 847adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 848adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 850bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return cursor < array.length; 851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 854bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (cursor >= array.length) 855bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new NoSuchElementException(); 856bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastRet = cursor; 857bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return (E)array[cursor++]; 858adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 861bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (lastRet < 0) 862bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new IllegalStateException(); 8638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson removeEQ(array[lastRet]); 864bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastRet = -1; 865adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 867adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 868adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 8698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Saves the state to a stream (that is, serializes it). For 8708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * compatibility with previous version of this class, 8718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements are first copied to a java.util.PriorityQueue, 8728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * which is then serialized. 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 874adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 878a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // avoid zero capacity argument 879a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson q = new PriorityQueue<E>(Math.max(size, 1), comparator); 8808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson q.addAll(this); 881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 882adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 8838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson q = null; 884adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 885adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 886adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 887adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 8888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 8898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Reconstitutes the {@code PriorityBlockingQueue} instance from a stream 8908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (that is, deserializes it). 8918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 8928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param s the stream 8938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 8948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void readObject(java.io.ObjectInputStream s) 8958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws java.io.IOException, ClassNotFoundException { 8968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 8978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson s.defaultReadObject(); 8988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.queue = new Object[q.size()]; 8998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson comparator = q.comparator(); 9008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson addAll(q); 9018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 9028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson q = null; 9038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 9068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Unsafe mechanics 907a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final sun.misc.Unsafe UNSAFE; 908a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long allocationSpinLockOffset; 909a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 9108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 911a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson UNSAFE = sun.misc.Unsafe.getUnsafe(); 912a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Class<?> k = PriorityBlockingQueue.class; 913a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson allocationSpinLockOffset = UNSAFE.objectFieldOffset 914a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("allocationSpinLock")); 915a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } catch (Exception e) { 916a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 9178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 919adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 920