1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/PriorityBlockingQueue.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,978 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea with assistance from members of JCP JSR-166
1.35 + * Expert Group and released to the public domain, as explained at
1.36 + * http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util.concurrent;
1.40 +
1.41 +import java.util.concurrent.locks.*;
1.42 +import java.util.*;
1.43 +
1.44 +/**
1.45 + * An unbounded {@linkplain BlockingQueue blocking queue} that uses
1.46 + * the same ordering rules as class {@link PriorityQueue} and supplies
1.47 + * blocking retrieval operations. While this queue is logically
1.48 + * unbounded, attempted additions may fail due to resource exhaustion
1.49 + * (causing {@code OutOfMemoryError}). This class does not permit
1.50 + * {@code null} elements. A priority queue relying on {@linkplain
1.51 + * Comparable natural ordering} also does not permit insertion of
1.52 + * non-comparable objects (doing so results in
1.53 + * {@code ClassCastException}).
1.54 + *
1.55 + * <p>This class and its iterator implement all of the
1.56 + * <em>optional</em> methods of the {@link Collection} and {@link
1.57 + * Iterator} interfaces. The Iterator provided in method {@link
1.58 + * #iterator()} is <em>not</em> guaranteed to traverse the elements of
1.59 + * the PriorityBlockingQueue in any particular order. If you need
1.60 + * ordered traversal, consider using
1.61 + * {@code Arrays.sort(pq.toArray())}. Also, method {@code drainTo}
1.62 + * can be used to <em>remove</em> some or all elements in priority
1.63 + * order and place them in another collection.
1.64 + *
1.65 + * <p>Operations on this class make no guarantees about the ordering
1.66 + * of elements with equal priority. If you need to enforce an
1.67 + * ordering, you can define custom classes or comparators that use a
1.68 + * secondary key to break ties in primary priority values. For
1.69 + * example, here is a class that applies first-in-first-out
1.70 + * tie-breaking to comparable elements. To use it, you would insert a
1.71 + * {@code new FIFOEntry(anEntry)} instead of a plain entry object.
1.72 + *
1.73 + * <pre> {@code
1.74 + * class FIFOEntry<E extends Comparable<? super E>>
1.75 + * implements Comparable<FIFOEntry<E>> {
1.76 + * static final AtomicLong seq = new AtomicLong(0);
1.77 + * final long seqNum;
1.78 + * final E entry;
1.79 + * public FIFOEntry(E entry) {
1.80 + * seqNum = seq.getAndIncrement();
1.81 + * this.entry = entry;
1.82 + * }
1.83 + * public E getEntry() { return entry; }
1.84 + * public int compareTo(FIFOEntry<E> other) {
1.85 + * int res = entry.compareTo(other.entry);
1.86 + * if (res == 0 && other.entry != this.entry)
1.87 + * res = (seqNum < other.seqNum ? -1 : 1);
1.88 + * return res;
1.89 + * }
1.90 + * }}</pre>
1.91 + *
1.92 + * <p>This class is a member of the
1.93 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.94 + * Java Collections Framework</a>.
1.95 + *
1.96 + * @since 1.5
1.97 + * @author Doug Lea
1.98 + * @param <E> the type of elements held in this collection
1.99 + */
1.100 +public class PriorityBlockingQueue<E> extends AbstractQueue<E>
1.101 + implements BlockingQueue<E>, java.io.Serializable {
1.102 + private static final long serialVersionUID = 5595510919245408276L;
1.103 +
1.104 + /*
1.105 + * The implementation uses an array-based binary heap, with public
1.106 + * operations protected with a single lock. However, allocation
1.107 + * during resizing uses a simple spinlock (used only while not
1.108 + * holding main lock) in order to allow takes to operate
1.109 + * concurrently with allocation. This avoids repeated
1.110 + * postponement of waiting consumers and consequent element
1.111 + * build-up. The need to back away from lock during allocation
1.112 + * makes it impossible to simply wrap delegated
1.113 + * java.util.PriorityQueue operations within a lock, as was done
1.114 + * in a previous version of this class. To maintain
1.115 + * interoperability, a plain PriorityQueue is still used during
1.116 + * serialization, which maintains compatibility at the espense of
1.117 + * transiently doubling overhead.
1.118 + */
1.119 +
1.120 + /**
1.121 + * Default array capacity.
1.122 + */
1.123 + private static final int DEFAULT_INITIAL_CAPACITY = 11;
1.124 +
1.125 + /**
1.126 + * The maximum size of array to allocate.
1.127 + * Some VMs reserve some header words in an array.
1.128 + * Attempts to allocate larger arrays may result in
1.129 + * OutOfMemoryError: Requested array size exceeds VM limit
1.130 + */
1.131 + private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1.132 +
1.133 + /**
1.134 + * Priority queue represented as a balanced binary heap: the two
1.135 + * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
1.136 + * priority queue is ordered by comparator, or by the elements'
1.137 + * natural ordering, if comparator is null: For each node n in the
1.138 + * heap and each descendant d of n, n <= d. The element with the
1.139 + * lowest value is in queue[0], assuming the queue is nonempty.
1.140 + */
1.141 + private transient Object[] queue;
1.142 +
1.143 + /**
1.144 + * The number of elements in the priority queue.
1.145 + */
1.146 + private transient int size;
1.147 +
1.148 + /**
1.149 + * The comparator, or null if priority queue uses elements'
1.150 + * natural ordering.
1.151 + */
1.152 + private transient Comparator<? super E> comparator;
1.153 +
1.154 + /**
1.155 + * Lock used for all public operations
1.156 + */
1.157 + private final ReentrantLock lock;
1.158 +
1.159 + /**
1.160 + * Condition for blocking when empty
1.161 + */
1.162 + private final Condition notEmpty;
1.163 +
1.164 + /**
1.165 + * Spinlock for allocation, acquired via CAS.
1.166 + */
1.167 + private transient volatile int allocationSpinLock;
1.168 +
1.169 + /**
1.170 + * A plain PriorityQueue used only for serialization,
1.171 + * to maintain compatibility with previous versions
1.172 + * of this class. Non-null only during serialization/deserialization.
1.173 + */
1.174 + private PriorityQueue q;
1.175 +
1.176 + /**
1.177 + * Creates a {@code PriorityBlockingQueue} with the default
1.178 + * initial capacity (11) that orders its elements according to
1.179 + * their {@linkplain Comparable natural ordering}.
1.180 + */
1.181 + public PriorityBlockingQueue() {
1.182 + this(DEFAULT_INITIAL_CAPACITY, null);
1.183 + }
1.184 +
1.185 + /**
1.186 + * Creates a {@code PriorityBlockingQueue} with the specified
1.187 + * initial capacity that orders its elements according to their
1.188 + * {@linkplain Comparable natural ordering}.
1.189 + *
1.190 + * @param initialCapacity the initial capacity for this priority queue
1.191 + * @throws IllegalArgumentException if {@code initialCapacity} is less
1.192 + * than 1
1.193 + */
1.194 + public PriorityBlockingQueue(int initialCapacity) {
1.195 + this(initialCapacity, null);
1.196 + }
1.197 +
1.198 + /**
1.199 + * Creates a {@code PriorityBlockingQueue} with the specified initial
1.200 + * capacity that orders its elements according to the specified
1.201 + * comparator.
1.202 + *
1.203 + * @param initialCapacity the initial capacity for this priority queue
1.204 + * @param comparator the comparator that will be used to order this
1.205 + * priority queue. If {@code null}, the {@linkplain Comparable
1.206 + * natural ordering} of the elements will be used.
1.207 + * @throws IllegalArgumentException if {@code initialCapacity} is less
1.208 + * than 1
1.209 + */
1.210 + public PriorityBlockingQueue(int initialCapacity,
1.211 + Comparator<? super E> comparator) {
1.212 + if (initialCapacity < 1)
1.213 + throw new IllegalArgumentException();
1.214 + this.lock = new ReentrantLock();
1.215 + this.notEmpty = lock.newCondition();
1.216 + this.comparator = comparator;
1.217 + this.queue = new Object[initialCapacity];
1.218 + }
1.219 +
1.220 + /**
1.221 + * Creates a {@code PriorityBlockingQueue} containing the elements
1.222 + * in the specified collection. If the specified collection is a
1.223 + * {@link SortedSet} or a {@link PriorityQueue}, this
1.224 + * priority queue will be ordered according to the same ordering.
1.225 + * Otherwise, this priority queue will be ordered according to the
1.226 + * {@linkplain Comparable natural ordering} of its elements.
1.227 + *
1.228 + * @param c the collection whose elements are to be placed
1.229 + * into this priority queue
1.230 + * @throws ClassCastException if elements of the specified collection
1.231 + * cannot be compared to one another according to the priority
1.232 + * queue's ordering
1.233 + * @throws NullPointerException if the specified collection or any
1.234 + * of its elements are null
1.235 + */
1.236 + public PriorityBlockingQueue(Collection<? extends E> c) {
1.237 + this.lock = new ReentrantLock();
1.238 + this.notEmpty = lock.newCondition();
1.239 + boolean heapify = true; // true if not known to be in heap order
1.240 + boolean screen = true; // true if must screen for nulls
1.241 + if (c instanceof SortedSet<?>) {
1.242 + SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
1.243 + this.comparator = (Comparator<? super E>) ss.comparator();
1.244 + heapify = false;
1.245 + }
1.246 + else if (c instanceof PriorityBlockingQueue<?>) {
1.247 + PriorityBlockingQueue<? extends E> pq =
1.248 + (PriorityBlockingQueue<? extends E>) c;
1.249 + this.comparator = (Comparator<? super E>) pq.comparator();
1.250 + screen = false;
1.251 + if (pq.getClass() == PriorityBlockingQueue.class) // exact match
1.252 + heapify = false;
1.253 + }
1.254 + Object[] a = c.toArray();
1.255 + int n = a.length;
1.256 + // If c.toArray incorrectly doesn't return Object[], copy it.
1.257 + if (a.getClass() != Object[].class)
1.258 + a = Arrays.copyOf(a, n, Object[].class);
1.259 + if (screen && (n == 1 || this.comparator != null)) {
1.260 + for (int i = 0; i < n; ++i)
1.261 + if (a[i] == null)
1.262 + throw new NullPointerException();
1.263 + }
1.264 + this.queue = a;
1.265 + this.size = n;
1.266 + if (heapify)
1.267 + heapify();
1.268 + }
1.269 +
1.270 + /**
1.271 + * Tries to grow array to accommodate at least one more element
1.272 + * (but normally expand by about 50%), giving up (allowing retry)
1.273 + * on contention (which we expect to be rare). Call only while
1.274 + * holding lock.
1.275 + *
1.276 + * @param array the heap array
1.277 + * @param oldCap the length of the array
1.278 + */
1.279 + private void tryGrow(Object[] array, int oldCap) {
1.280 + lock.unlock(); // must release and then re-acquire main lock
1.281 + Object[] newArray = null;
1.282 + if (allocationSpinLock == 0 &&
1.283 + UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,
1.284 + 0, 1)) {
1.285 + try {
1.286 + int newCap = oldCap + ((oldCap < 64) ?
1.287 + (oldCap + 2) : // grow faster if small
1.288 + (oldCap >> 1));
1.289 + if (newCap - MAX_ARRAY_SIZE > 0) { // possible overflow
1.290 + int minCap = oldCap + 1;
1.291 + if (minCap < 0 || minCap > MAX_ARRAY_SIZE)
1.292 + throw new OutOfMemoryError();
1.293 + newCap = MAX_ARRAY_SIZE;
1.294 + }
1.295 + if (newCap > oldCap && queue == array)
1.296 + newArray = new Object[newCap];
1.297 + } finally {
1.298 + allocationSpinLock = 0;
1.299 + }
1.300 + }
1.301 + if (newArray == null) // back off if another thread is allocating
1.302 + Thread.yield();
1.303 + lock.lock();
1.304 + if (newArray != null && queue == array) {
1.305 + queue = newArray;
1.306 + System.arraycopy(array, 0, newArray, 0, oldCap);
1.307 + }
1.308 + }
1.309 +
1.310 + /**
1.311 + * Mechanics for poll(). Call only while holding lock.
1.312 + */
1.313 + private E extract() {
1.314 + E result;
1.315 + int n = size - 1;
1.316 + if (n < 0)
1.317 + result = null;
1.318 + else {
1.319 + Object[] array = queue;
1.320 + result = (E) array[0];
1.321 + E x = (E) array[n];
1.322 + array[n] = null;
1.323 + Comparator<? super E> cmp = comparator;
1.324 + if (cmp == null)
1.325 + siftDownComparable(0, x, array, n);
1.326 + else
1.327 + siftDownUsingComparator(0, x, array, n, cmp);
1.328 + size = n;
1.329 + }
1.330 + return result;
1.331 + }
1.332 +
1.333 + /**
1.334 + * Inserts item x at position k, maintaining heap invariant by
1.335 + * promoting x up the tree until it is greater than or equal to
1.336 + * its parent, or is the root.
1.337 + *
1.338 + * To simplify and speed up coercions and comparisons. the
1.339 + * Comparable and Comparator versions are separated into different
1.340 + * methods that are otherwise identical. (Similarly for siftDown.)
1.341 + * These methods are static, with heap state as arguments, to
1.342 + * simplify use in light of possible comparator exceptions.
1.343 + *
1.344 + * @param k the position to fill
1.345 + * @param x the item to insert
1.346 + * @param array the heap array
1.347 + * @param n heap size
1.348 + */
1.349 + private static <T> void siftUpComparable(int k, T x, Object[] array) {
1.350 + Comparable<? super T> key = (Comparable<? super T>) x;
1.351 + while (k > 0) {
1.352 + int parent = (k - 1) >>> 1;
1.353 + Object e = array[parent];
1.354 + if (key.compareTo((T) e) >= 0)
1.355 + break;
1.356 + array[k] = e;
1.357 + k = parent;
1.358 + }
1.359 + array[k] = key;
1.360 + }
1.361 +
1.362 + private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
1.363 + Comparator<? super T> cmp) {
1.364 + while (k > 0) {
1.365 + int parent = (k - 1) >>> 1;
1.366 + Object e = array[parent];
1.367 + if (cmp.compare(x, (T) e) >= 0)
1.368 + break;
1.369 + array[k] = e;
1.370 + k = parent;
1.371 + }
1.372 + array[k] = x;
1.373 + }
1.374 +
1.375 + /**
1.376 + * Inserts item x at position k, maintaining heap invariant by
1.377 + * demoting x down the tree repeatedly until it is less than or
1.378 + * equal to its children or is a leaf.
1.379 + *
1.380 + * @param k the position to fill
1.381 + * @param x the item to insert
1.382 + * @param array the heap array
1.383 + * @param n heap size
1.384 + */
1.385 + private static <T> void siftDownComparable(int k, T x, Object[] array,
1.386 + int n) {
1.387 + Comparable<? super T> key = (Comparable<? super T>)x;
1.388 + int half = n >>> 1; // loop while a non-leaf
1.389 + while (k < half) {
1.390 + int child = (k << 1) + 1; // assume left child is least
1.391 + Object c = array[child];
1.392 + int right = child + 1;
1.393 + if (right < n &&
1.394 + ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
1.395 + c = array[child = right];
1.396 + if (key.compareTo((T) c) <= 0)
1.397 + break;
1.398 + array[k] = c;
1.399 + k = child;
1.400 + }
1.401 + array[k] = key;
1.402 + }
1.403 +
1.404 + private static <T> void siftDownUsingComparator(int k, T x, Object[] array,
1.405 + int n,
1.406 + Comparator<? super T> cmp) {
1.407 + int half = n >>> 1;
1.408 + while (k < half) {
1.409 + int child = (k << 1) + 1;
1.410 + Object c = array[child];
1.411 + int right = child + 1;
1.412 + if (right < n && cmp.compare((T) c, (T) array[right]) > 0)
1.413 + c = array[child = right];
1.414 + if (cmp.compare(x, (T) c) <= 0)
1.415 + break;
1.416 + array[k] = c;
1.417 + k = child;
1.418 + }
1.419 + array[k] = x;
1.420 + }
1.421 +
1.422 + /**
1.423 + * Establishes the heap invariant (described above) in the entire tree,
1.424 + * assuming nothing about the order of the elements prior to the call.
1.425 + */
1.426 + private void heapify() {
1.427 + Object[] array = queue;
1.428 + int n = size;
1.429 + int half = (n >>> 1) - 1;
1.430 + Comparator<? super E> cmp = comparator;
1.431 + if (cmp == null) {
1.432 + for (int i = half; i >= 0; i--)
1.433 + siftDownComparable(i, (E) array[i], array, n);
1.434 + }
1.435 + else {
1.436 + for (int i = half; i >= 0; i--)
1.437 + siftDownUsingComparator(i, (E) array[i], array, n, cmp);
1.438 + }
1.439 + }
1.440 +
1.441 + /**
1.442 + * Inserts the specified element into this priority queue.
1.443 + *
1.444 + * @param e the element to add
1.445 + * @return {@code true} (as specified by {@link Collection#add})
1.446 + * @throws ClassCastException if the specified element cannot be compared
1.447 + * with elements currently in the priority queue according to the
1.448 + * priority queue's ordering
1.449 + * @throws NullPointerException if the specified element is null
1.450 + */
1.451 + public boolean add(E e) {
1.452 + return offer(e);
1.453 + }
1.454 +
1.455 + /**
1.456 + * Inserts the specified element into this priority queue.
1.457 + * As the queue is unbounded, this method will never return {@code false}.
1.458 + *
1.459 + * @param e the element to add
1.460 + * @return {@code true} (as specified by {@link Queue#offer})
1.461 + * @throws ClassCastException if the specified element cannot be compared
1.462 + * with elements currently in the priority queue according to the
1.463 + * priority queue's ordering
1.464 + * @throws NullPointerException if the specified element is null
1.465 + */
1.466 + public boolean offer(E e) {
1.467 + if (e == null)
1.468 + throw new NullPointerException();
1.469 + final ReentrantLock lock = this.lock;
1.470 + lock.lock();
1.471 + int n, cap;
1.472 + Object[] array;
1.473 + while ((n = size) >= (cap = (array = queue).length))
1.474 + tryGrow(array, cap);
1.475 + try {
1.476 + Comparator<? super E> cmp = comparator;
1.477 + if (cmp == null)
1.478 + siftUpComparable(n, e, array);
1.479 + else
1.480 + siftUpUsingComparator(n, e, array, cmp);
1.481 + size = n + 1;
1.482 + notEmpty.signal();
1.483 + } finally {
1.484 + lock.unlock();
1.485 + }
1.486 + return true;
1.487 + }
1.488 +
1.489 + /**
1.490 + * Inserts the specified element into this priority queue.
1.491 + * As the queue is unbounded, this method will never block.
1.492 + *
1.493 + * @param e the element to add
1.494 + * @throws ClassCastException if the specified element cannot be compared
1.495 + * with elements currently in the priority queue according to the
1.496 + * priority queue's ordering
1.497 + * @throws NullPointerException if the specified element is null
1.498 + */
1.499 + public void put(E e) {
1.500 + offer(e); // never need to block
1.501 + }
1.502 +
1.503 + /**
1.504 + * Inserts the specified element into this priority queue.
1.505 + * As the queue is unbounded, this method will never block or
1.506 + * return {@code false}.
1.507 + *
1.508 + * @param e the element to add
1.509 + * @param timeout This parameter is ignored as the method never blocks
1.510 + * @param unit This parameter is ignored as the method never blocks
1.511 + * @return {@code true} (as specified by
1.512 + * {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer})
1.513 + * @throws ClassCastException if the specified element cannot be compared
1.514 + * with elements currently in the priority queue according to the
1.515 + * priority queue's ordering
1.516 + * @throws NullPointerException if the specified element is null
1.517 + */
1.518 + public boolean offer(E e, long timeout, TimeUnit unit) {
1.519 + return offer(e); // never need to block
1.520 + }
1.521 +
1.522 + public E poll() {
1.523 + final ReentrantLock lock = this.lock;
1.524 + lock.lock();
1.525 + E result;
1.526 + try {
1.527 + result = extract();
1.528 + } finally {
1.529 + lock.unlock();
1.530 + }
1.531 + return result;
1.532 + }
1.533 +
1.534 + public E take() throws InterruptedException {
1.535 + final ReentrantLock lock = this.lock;
1.536 + lock.lockInterruptibly();
1.537 + E result;
1.538 + try {
1.539 + while ( (result = extract()) == null)
1.540 + notEmpty.await();
1.541 + } finally {
1.542 + lock.unlock();
1.543 + }
1.544 + return result;
1.545 + }
1.546 +
1.547 + public E poll(long timeout, TimeUnit unit) throws InterruptedException {
1.548 + long nanos = unit.toNanos(timeout);
1.549 + final ReentrantLock lock = this.lock;
1.550 + lock.lockInterruptibly();
1.551 + E result;
1.552 + try {
1.553 + while ( (result = extract()) == null && nanos > 0)
1.554 + nanos = notEmpty.awaitNanos(nanos);
1.555 + } finally {
1.556 + lock.unlock();
1.557 + }
1.558 + return result;
1.559 + }
1.560 +
1.561 + public E peek() {
1.562 + final ReentrantLock lock = this.lock;
1.563 + lock.lock();
1.564 + E result;
1.565 + try {
1.566 + result = size > 0 ? (E) queue[0] : null;
1.567 + } finally {
1.568 + lock.unlock();
1.569 + }
1.570 + return result;
1.571 + }
1.572 +
1.573 + /**
1.574 + * Returns the comparator used to order the elements in this queue,
1.575 + * or {@code null} if this queue uses the {@linkplain Comparable
1.576 + * natural ordering} of its elements.
1.577 + *
1.578 + * @return the comparator used to order the elements in this queue,
1.579 + * or {@code null} if this queue uses the natural
1.580 + * ordering of its elements
1.581 + */
1.582 + public Comparator<? super E> comparator() {
1.583 + return comparator;
1.584 + }
1.585 +
1.586 + public int size() {
1.587 + final ReentrantLock lock = this.lock;
1.588 + lock.lock();
1.589 + try {
1.590 + return size;
1.591 + } finally {
1.592 + lock.unlock();
1.593 + }
1.594 + }
1.595 +
1.596 + /**
1.597 + * Always returns {@code Integer.MAX_VALUE} because
1.598 + * a {@code PriorityBlockingQueue} is not capacity constrained.
1.599 + * @return {@code Integer.MAX_VALUE} always
1.600 + */
1.601 + public int remainingCapacity() {
1.602 + return Integer.MAX_VALUE;
1.603 + }
1.604 +
1.605 + private int indexOf(Object o) {
1.606 + if (o != null) {
1.607 + Object[] array = queue;
1.608 + int n = size;
1.609 + for (int i = 0; i < n; i++)
1.610 + if (o.equals(array[i]))
1.611 + return i;
1.612 + }
1.613 + return -1;
1.614 + }
1.615 +
1.616 + /**
1.617 + * Removes the ith element from queue.
1.618 + */
1.619 + private void removeAt(int i) {
1.620 + Object[] array = queue;
1.621 + int n = size - 1;
1.622 + if (n == i) // removed last element
1.623 + array[i] = null;
1.624 + else {
1.625 + E moved = (E) array[n];
1.626 + array[n] = null;
1.627 + Comparator<? super E> cmp = comparator;
1.628 + if (cmp == null)
1.629 + siftDownComparable(i, moved, array, n);
1.630 + else
1.631 + siftDownUsingComparator(i, moved, array, n, cmp);
1.632 + if (array[i] == moved) {
1.633 + if (cmp == null)
1.634 + siftUpComparable(i, moved, array);
1.635 + else
1.636 + siftUpUsingComparator(i, moved, array, cmp);
1.637 + }
1.638 + }
1.639 + size = n;
1.640 + }
1.641 +
1.642 + /**
1.643 + * Removes a single instance of the specified element from this queue,
1.644 + * if it is present. More formally, removes an element {@code e} such
1.645 + * that {@code o.equals(e)}, if this queue contains one or more such
1.646 + * elements. Returns {@code true} if and only if this queue contained
1.647 + * the specified element (or equivalently, if this queue changed as a
1.648 + * result of the call).
1.649 + *
1.650 + * @param o element to be removed from this queue, if present
1.651 + * @return {@code true} if this queue changed as a result of the call
1.652 + */
1.653 + public boolean remove(Object o) {
1.654 + boolean removed = false;
1.655 + final ReentrantLock lock = this.lock;
1.656 + lock.lock();
1.657 + try {
1.658 + int i = indexOf(o);
1.659 + if (i != -1) {
1.660 + removeAt(i);
1.661 + removed = true;
1.662 + }
1.663 + } finally {
1.664 + lock.unlock();
1.665 + }
1.666 + return removed;
1.667 + }
1.668 +
1.669 +
1.670 + /**
1.671 + * Identity-based version for use in Itr.remove
1.672 + */
1.673 + private void removeEQ(Object o) {
1.674 + final ReentrantLock lock = this.lock;
1.675 + lock.lock();
1.676 + try {
1.677 + Object[] array = queue;
1.678 + int n = size;
1.679 + for (int i = 0; i < n; i++) {
1.680 + if (o == array[i]) {
1.681 + removeAt(i);
1.682 + break;
1.683 + }
1.684 + }
1.685 + } finally {
1.686 + lock.unlock();
1.687 + }
1.688 + }
1.689 +
1.690 + /**
1.691 + * Returns {@code true} if this queue contains the specified element.
1.692 + * More formally, returns {@code true} if and only if this queue contains
1.693 + * at least one element {@code e} such that {@code o.equals(e)}.
1.694 + *
1.695 + * @param o object to be checked for containment in this queue
1.696 + * @return {@code true} if this queue contains the specified element
1.697 + */
1.698 + public boolean contains(Object o) {
1.699 + int index;
1.700 + final ReentrantLock lock = this.lock;
1.701 + lock.lock();
1.702 + try {
1.703 + index = indexOf(o);
1.704 + } finally {
1.705 + lock.unlock();
1.706 + }
1.707 + return index != -1;
1.708 + }
1.709 +
1.710 + /**
1.711 + * Returns an array containing all of the elements in this queue.
1.712 + * The returned array elements are in no particular order.
1.713 + *
1.714 + * <p>The returned array will be "safe" in that no references to it are
1.715 + * maintained by this queue. (In other words, this method must allocate
1.716 + * a new array). The caller is thus free to modify the returned array.
1.717 + *
1.718 + * <p>This method acts as bridge between array-based and collection-based
1.719 + * APIs.
1.720 + *
1.721 + * @return an array containing all of the elements in this queue
1.722 + */
1.723 + public Object[] toArray() {
1.724 + final ReentrantLock lock = this.lock;
1.725 + lock.lock();
1.726 + try {
1.727 + return Arrays.copyOf(queue, size);
1.728 + } finally {
1.729 + lock.unlock();
1.730 + }
1.731 + }
1.732 +
1.733 +
1.734 + public String toString() {
1.735 + final ReentrantLock lock = this.lock;
1.736 + lock.lock();
1.737 + try {
1.738 + int n = size;
1.739 + if (n == 0)
1.740 + return "[]";
1.741 + StringBuilder sb = new StringBuilder();
1.742 + sb.append('[');
1.743 + for (int i = 0; i < n; ++i) {
1.744 + E e = (E)queue[i];
1.745 + sb.append(e == this ? "(this Collection)" : e);
1.746 + if (i != n - 1)
1.747 + sb.append(',').append(' ');
1.748 + }
1.749 + return sb.append(']').toString();
1.750 + } finally {
1.751 + lock.unlock();
1.752 + }
1.753 + }
1.754 +
1.755 + /**
1.756 + * @throws UnsupportedOperationException {@inheritDoc}
1.757 + * @throws ClassCastException {@inheritDoc}
1.758 + * @throws NullPointerException {@inheritDoc}
1.759 + * @throws IllegalArgumentException {@inheritDoc}
1.760 + */
1.761 + public int drainTo(Collection<? super E> c) {
1.762 + if (c == null)
1.763 + throw new NullPointerException();
1.764 + if (c == this)
1.765 + throw new IllegalArgumentException();
1.766 + final ReentrantLock lock = this.lock;
1.767 + lock.lock();
1.768 + try {
1.769 + int n = 0;
1.770 + E e;
1.771 + while ( (e = extract()) != null) {
1.772 + c.add(e);
1.773 + ++n;
1.774 + }
1.775 + return n;
1.776 + } finally {
1.777 + lock.unlock();
1.778 + }
1.779 + }
1.780 +
1.781 + /**
1.782 + * @throws UnsupportedOperationException {@inheritDoc}
1.783 + * @throws ClassCastException {@inheritDoc}
1.784 + * @throws NullPointerException {@inheritDoc}
1.785 + * @throws IllegalArgumentException {@inheritDoc}
1.786 + */
1.787 + public int drainTo(Collection<? super E> c, int maxElements) {
1.788 + if (c == null)
1.789 + throw new NullPointerException();
1.790 + if (c == this)
1.791 + throw new IllegalArgumentException();
1.792 + if (maxElements <= 0)
1.793 + return 0;
1.794 + final ReentrantLock lock = this.lock;
1.795 + lock.lock();
1.796 + try {
1.797 + int n = 0;
1.798 + E e;
1.799 + while (n < maxElements && (e = extract()) != null) {
1.800 + c.add(e);
1.801 + ++n;
1.802 + }
1.803 + return n;
1.804 + } finally {
1.805 + lock.unlock();
1.806 + }
1.807 + }
1.808 +
1.809 + /**
1.810 + * Atomically removes all of the elements from this queue.
1.811 + * The queue will be empty after this call returns.
1.812 + */
1.813 + public void clear() {
1.814 + final ReentrantLock lock = this.lock;
1.815 + lock.lock();
1.816 + try {
1.817 + Object[] array = queue;
1.818 + int n = size;
1.819 + size = 0;
1.820 + for (int i = 0; i < n; i++)
1.821 + array[i] = null;
1.822 + } finally {
1.823 + lock.unlock();
1.824 + }
1.825 + }
1.826 +
1.827 + /**
1.828 + * Returns an array containing all of the elements in this queue; the
1.829 + * runtime type of the returned array is that of the specified array.
1.830 + * The returned array elements are in no particular order.
1.831 + * If the queue fits in the specified array, it is returned therein.
1.832 + * Otherwise, a new array is allocated with the runtime type of the
1.833 + * specified array and the size of this queue.
1.834 + *
1.835 + * <p>If this queue fits in the specified array with room to spare
1.836 + * (i.e., the array has more elements than this queue), the element in
1.837 + * the array immediately following the end of the queue is set to
1.838 + * {@code null}.
1.839 + *
1.840 + * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.841 + * array-based and collection-based APIs. Further, this method allows
1.842 + * precise control over the runtime type of the output array, and may,
1.843 + * under certain circumstances, be used to save allocation costs.
1.844 + *
1.845 + * <p>Suppose {@code x} is a queue known to contain only strings.
1.846 + * The following code can be used to dump the queue into a newly
1.847 + * allocated array of {@code String}:
1.848 + *
1.849 + * <pre>
1.850 + * String[] y = x.toArray(new String[0]);</pre>
1.851 + *
1.852 + * Note that {@code toArray(new Object[0])} is identical in function to
1.853 + * {@code toArray()}.
1.854 + *
1.855 + * @param a the array into which the elements of the queue are to
1.856 + * be stored, if it is big enough; otherwise, a new array of the
1.857 + * same runtime type is allocated for this purpose
1.858 + * @return an array containing all of the elements in this queue
1.859 + * @throws ArrayStoreException if the runtime type of the specified array
1.860 + * is not a supertype of the runtime type of every element in
1.861 + * this queue
1.862 + * @throws NullPointerException if the specified array is null
1.863 + */
1.864 + public <T> T[] toArray(T[] a) {
1.865 + final ReentrantLock lock = this.lock;
1.866 + lock.lock();
1.867 + try {
1.868 + int n = size;
1.869 + if (a.length < n)
1.870 + // Make a new array of a's runtime type, but my contents:
1.871 + return (T[]) Arrays.copyOf(queue, size, a.getClass());
1.872 + System.arraycopy(queue, 0, a, 0, n);
1.873 + if (a.length > n)
1.874 + a[n] = null;
1.875 + return a;
1.876 + } finally {
1.877 + lock.unlock();
1.878 + }
1.879 + }
1.880 +
1.881 + /**
1.882 + * Returns an iterator over the elements in this queue. The
1.883 + * iterator does not return the elements in any particular order.
1.884 + *
1.885 + * <p>The returned iterator is a "weakly consistent" iterator that
1.886 + * will never throw {@link java.util.ConcurrentModificationException
1.887 + * ConcurrentModificationException}, and guarantees to traverse
1.888 + * elements as they existed upon construction of the iterator, and
1.889 + * may (but is not guaranteed to) reflect any modifications
1.890 + * subsequent to construction.
1.891 + *
1.892 + * @return an iterator over the elements in this queue
1.893 + */
1.894 + public Iterator<E> iterator() {
1.895 + return new Itr(toArray());
1.896 + }
1.897 +
1.898 + /**
1.899 + * Snapshot iterator that works off copy of underlying q array.
1.900 + */
1.901 + final class Itr implements Iterator<E> {
1.902 + final Object[] array; // Array of all elements
1.903 + int cursor; // index of next element to return;
1.904 + int lastRet; // index of last element, or -1 if no such
1.905 +
1.906 + Itr(Object[] array) {
1.907 + lastRet = -1;
1.908 + this.array = array;
1.909 + }
1.910 +
1.911 + public boolean hasNext() {
1.912 + return cursor < array.length;
1.913 + }
1.914 +
1.915 + public E next() {
1.916 + if (cursor >= array.length)
1.917 + throw new NoSuchElementException();
1.918 + lastRet = cursor;
1.919 + return (E)array[cursor++];
1.920 + }
1.921 +
1.922 + public void remove() {
1.923 + if (lastRet < 0)
1.924 + throw new IllegalStateException();
1.925 + removeEQ(array[lastRet]);
1.926 + lastRet = -1;
1.927 + }
1.928 + }
1.929 +
1.930 + /**
1.931 + * Saves the state to a stream (that is, serializes it). For
1.932 + * compatibility with previous version of this class,
1.933 + * elements are first copied to a java.util.PriorityQueue,
1.934 + * which is then serialized.
1.935 + */
1.936 + private void writeObject(java.io.ObjectOutputStream s)
1.937 + throws java.io.IOException {
1.938 + lock.lock();
1.939 + try {
1.940 + int n = size; // avoid zero capacity argument
1.941 + q = new PriorityQueue<E>(n == 0 ? 1 : n, comparator);
1.942 + q.addAll(this);
1.943 + s.defaultWriteObject();
1.944 + } finally {
1.945 + q = null;
1.946 + lock.unlock();
1.947 + }
1.948 + }
1.949 +
1.950 + /**
1.951 + * Reconstitutes the {@code PriorityBlockingQueue} instance from a stream
1.952 + * (that is, deserializes it).
1.953 + *
1.954 + * @param s the stream
1.955 + */
1.956 + private void readObject(java.io.ObjectInputStream s)
1.957 + throws java.io.IOException, ClassNotFoundException {
1.958 + try {
1.959 + s.defaultReadObject();
1.960 + this.queue = new Object[q.size()];
1.961 + comparator = q.comparator();
1.962 + addAll(q);
1.963 + } finally {
1.964 + q = null;
1.965 + }
1.966 + }
1.967 +
1.968 + // Unsafe mechanics
1.969 + private static final sun.misc.Unsafe UNSAFE;
1.970 + private static final long allocationSpinLockOffset;
1.971 + static {
1.972 + try {
1.973 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.974 + Class k = PriorityBlockingQueue.class;
1.975 + allocationSpinLockOffset = UNSAFE.objectFieldOffset
1.976 + (k.getDeclaredField("allocationSpinLock"));
1.977 + } catch (Exception e) {
1.978 + throw new Error(e);
1.979 + }
1.980 + }
1.981 +}