jdk-sandbox: comparison src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java

equal deleted inserted replaced

-:45093fb73c6d
+:6b29ef846c5c
 import java.util.SortedSet;
 import java.util.Spliterator;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
 import java.util.function.Consumer;
+import java.util.function.Predicate;
 import jdk.internal.misc.SharedSecrets;
 /**
 * An unbounded {@linkplain BlockingQueue blocking queue} that uses
 * the same ordering rules as class {@link PriorityQueue} and supplies
 private transient Comparator<? super E> comparator;
 /**
 * Lock used for all public operations.
 */
-private final ReentrantLock lock;
+private final ReentrantLock lock = new ReentrantLock();
 /**
 * Condition for blocking when empty.
 */
-private final Condition notEmpty;
+private final Condition notEmpty = lock.newCondition();
 /**
 * Spinlock for allocation, acquired via CAS.
 */
 private transient volatile int allocationSpinLock;
 */
 public PriorityBlockingQueue(int initialCapacity,
 Comparator<? super E> comparator) {
 if (initialCapacity < 1)
 throw new IllegalArgumentException();
-this.lock = new ReentrantLock();
-this.notEmpty = lock.newCondition();
 this.comparator = comparator;
-this.queue = new Object[initialCapacity];
+this.queue = new Object[Math.max(1, initialCapacity)];
 }
 /**
 * Creates a {@code PriorityBlockingQueue} containing the elements
 * in the specified collection.  If the specified collection is a
 *         queue's ordering
 * @throws NullPointerException if the specified collection or any
 *         of its elements are null
 */
 public PriorityBlockingQueue(Collection<? extends E> c) {
-this.lock = new ReentrantLock();
-this.notEmpty = lock.newCondition();
 boolean heapify = true; // true if not known to be in heap order
 boolean screen = true;  // true if must screen for nulls
 if (c instanceof SortedSet<?>) {
 SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
 this.comparator = (Comparator<? super E>) ss.comparator();
 this.comparator = (Comparator<? super E>) pq.comparator();
 screen = false;
 if (pq.getClass() == PriorityBlockingQueue.class) // exact match
 heapify = false;
 }
-Object[] a = c.toArray();
+Object[] es = c.toArray();
-int n = a.length;
+int n = es.length;
 // If c.toArray incorrectly doesn't return Object[], copy it.
-if (a.getClass() != Object[].class)
+if (es.getClass() != Object[].class)
-a = Arrays.copyOf(a, n, Object[].class);
+es = Arrays.copyOf(es, n, Object[].class);
 if (screen && (n == 1 || this.comparator != null)) {
-for (Object elt : a)
+for (Object e : es)
-if (elt == null)
+if (e == null)
 throw new NullPointerException();
 }
-this.queue = a;
+this.queue = ensureNonEmpty(es);
 this.size = n;
 if (heapify)
 heapify();
+}
+/** Ensures that queue[0] exists, helping peek() and poll(). */
+private static Object[] ensureNonEmpty(Object[] es) {
+return (es.length > 0) ? es : new Object[1];
 }
 /**
 * Tries to grow array to accommodate at least one more element
 * (but normally expand by about 50%), giving up (allowing retry)
 /**
 * Mechanics for poll().  Call only while holding lock.
 */
 private E dequeue() {
-int n = size - 1;
+// assert lock.isHeldByCurrentThread();
-if (n < 0)
+final Object[] es;
-return null;
+final E result;
-else {
-Object[] array = queue;
+if ((result = (E) ((es = queue)[0])) != null) {
-E result = (E) array[0];
+final int n;
-E x = (E) array[n];
+final E x = (E) es[(n = --size)];
-array[n] = null;
+es[n] = null;
-Comparator<? super E> cmp = comparator;
+if (n > 0) {
-if (cmp == null)
+final Comparator<? super E> cmp;
-siftDownComparable(0, x, array, n);
+if ((cmp = comparator) == null)
-else
+siftDownComparable(0, x, es, n);
-siftDownUsingComparator(0, x, array, n, cmp);
+else
-size = n;
+siftDownUsingComparator(0, x, es, n, cmp);
-return result;
+}
 }
+return result;
 }
 /**
 * Inserts item x at position k, maintaining heap invariant by
 * promoting x up the tree until it is greater than or equal to
 * Comparable and Comparator versions are separated into different
 * methods that are otherwise identical. (Similarly for siftDown.)
 *
 * @param k the position to fill
 * @param x the item to insert
-* @param array the heap array
+* @param es the heap array
 */
-private static <T> void siftUpComparable(int k, T x, Object[] array) {
+private static <T> void siftUpComparable(int k, T x, Object[] es) {
 Comparable<? super T> key = (Comparable<? super T>) x;
 while (k > 0) {
 int parent = (k - 1) >>> 1;
-Object e = array[parent];
+Object e = es[parent];
 if (key.compareTo((T) e) >= 0)
 break;
-array[k] = e;
+es[k] = e;
 k = parent;
 }
-array[k] = key;
+es[k] = key;
 }
-private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
+private static <T> void siftUpUsingComparator(
-Comparator<? super T> cmp) {
+int k, T x, Object[] es, Comparator<? super T> cmp) {
 while (k > 0) {
 int parent = (k - 1) >>> 1;
-Object e = array[parent];
+Object e = es[parent];
 if (cmp.compare(x, (T) e) >= 0)
 break;
-array[k] = e;
+es[k] = e;
 k = parent;
 }
-array[k] = x;
+es[k] = x;
 }
 /**
 * Inserts item x at position k, maintaining heap invariant by
 * demoting x down the tree repeatedly until it is less than or
 * equal to its children or is a leaf.
 *
 * @param k the position to fill
 * @param x the item to insert
-* @param array the heap array
+* @param es the heap array
 * @param n heap size
 */
-private static <T> void siftDownComparable(int k, T x, Object[] array,
+private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
-int n) {
+// assert n > 0;
-if (n > 0) {
+Comparable<? super T> key = (Comparable<? super T>)x;
-Comparable<? super T> key = (Comparable<? super T>)x;
+int half = n >>> 1;           // loop while a non-leaf
-int half = n >>> 1;           // loop while a non-leaf
+while (k < half) {
-while (k < half) {
+int child = (k << 1) + 1; // assume left child is least
-int child = (k << 1) + 1; // assume left child is least
+Object c = es[child];
-Object c = array[child];
+int right = child + 1;
-int right = child + 1;
+if (right < n &&
-if (right < n &&
+((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
-((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
+c = es[child = right];
-c = array[child = right];
+if (key.compareTo((T) c) <= 0)
-if (key.compareTo((T) c) <= 0)
+break;
-break;
+es[k] = c;
-array[k] = c;
+k = child;
-k = child;
+}
-}
+es[k] = key;
-array[k] = key;
+}
-}
-}
+private static <T> void siftDownUsingComparator(
+int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
-private static <T> void siftDownUsingComparator(int k, T x, Object[] array,
+// assert n > 0;
-int n,
+int half = n >>> 1;
-Comparator<? super T> cmp) {
+while (k < half) {
-if (n > 0) {
+int child = (k << 1) + 1;
-int half = n >>> 1;
+Object c = es[child];
-while (k < half) {
+int right = child + 1;
-int child = (k << 1) + 1;
+if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
-Object c = array[child];
+c = es[child = right];
-int right = child + 1;
+if (cmp.compare(x, (T) c) <= 0)
-if (right < n && cmp.compare((T) c, (T) array[right]) > 0)
+break;
-c = array[child = right];
+es[k] = c;
-if (cmp.compare(x, (T) c) <= 0)
+k = child;
-break;
+}
-array[k] = c;
+es[k] = x;
-k = child;
-}
-array[k] = x;
-}
 }
 /**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 * This classic algorithm due to Floyd (1964) is known to be O(size).
 */
 private void heapify() {
-Object[] array = queue;
+final Object[] es = queue;
 int n = size, i = (n >>> 1) - 1;
-Comparator<? super E> cmp = comparator;
+final Comparator<? super E> cmp;
-if (cmp == null) {
+if ((cmp = comparator) == null)
 for (; i >= 0; i--)
-siftDownComparable(i, (E) array[i], array, n);
+siftDownComparable(i, (E) es[i], es, n);
-}
+else
-else {
 for (; i >= 0; i--)
-siftDownUsingComparator(i, (E) array[i], array, n, cmp);
+siftDownUsingComparator(i, (E) es[i], es, n, cmp);
-}
 }
 /**
 * Inserts the specified element into this priority queue.
 *
 if (e == null)
 throw new NullPointerException();
 final ReentrantLock lock = this.lock;
 lock.lock();
 int n, cap;
-Object[] array;
+Object[] es;
-while ((n = size) >= (cap = (array = queue).length))
+while ((n = size) >= (cap = (es = queue).length))
-tryGrow(array, cap);
+tryGrow(es, cap);
 try {
-Comparator<? super E> cmp = comparator;
+final Comparator<? super E> cmp;
-if (cmp == null)
+if ((cmp = comparator) == null)
-siftUpComparable(n, e, array);
+siftUpComparable(n, e, es);
 else
-siftUpUsingComparator(n, e, array, cmp);
+siftUpUsingComparator(n, e, es, cmp);
 size = n + 1;
 notEmpty.signal();
 } finally {
 lock.unlock();
 }
 public E peek() {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
-return (size == 0) ? null : (E) queue[0];
+return (E) queue[0];
 } finally {
 lock.unlock();
 }
 }
 return Integer.MAX_VALUE;
 }
 private int indexOf(Object o) {
 if (o != null) {
-Object[] array = queue;
+final Object[] es = queue;
-int n = size;
+for (int i = 0, n = size; i < n; i++)
-for (int i = 0; i < n; i++)
+if (o.equals(es[i]))
-if (o.equals(array[i]))
 return i;
 }
 return -1;
 }
 /**
 * Removes the ith element from queue.
 */
 private void removeAt(int i) {
-Object[] array = queue;
+final Object[] es = queue;
-int n = size - 1;
+final int n = size - 1;
 if (n == i) // removed last element
-array[i] = null;
+es[i] = null;
 else {
-E moved = (E) array[n];
+E moved = (E) es[n];
-array[n] = null;
+es[n] = null;
-Comparator<? super E> cmp = comparator;
+final Comparator<? super E> cmp;
-if (cmp == null)
+if ((cmp = comparator) == null)
-siftDownComparable(i, moved, array, n);
+siftDownComparable(i, moved, es, n);
 else
-siftDownUsingComparator(i, moved, array, n, cmp);
+siftDownUsingComparator(i, moved, es, n, cmp);
-if (array[i] == moved) {
+if (es[i] == moved) {
 if (cmp == null)
-siftUpComparable(i, moved, array);
+siftUpComparable(i, moved, es);
 else
-siftUpUsingComparator(i, moved, array, cmp);
+siftUpUsingComparator(i, moved, es, cmp);
 }
 }
 size = n;
 }
 }
 }
 /**
 * Identity-based version for use in Itr.remove.
-*/
+*
-void removeEQ(Object o) {
+* @param o element to be removed from this queue, if present
-final ReentrantLock lock = this.lock;
+*/
-lock.lock();
+void removeEq(Object o) {
-try {
+final ReentrantLock lock = this.lock;
-Object[] array = queue;
+lock.lock();
+try {
+final Object[] es = queue;
 for (int i = 0, n = size; i < n; i++) {
-if (o == array[i]) {
+if (o == es[i]) {
 removeAt(i);
 break;
 }
 }
 } finally {
 */
 public void clear() {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
-Object[] array = queue;
+final Object[] es = queue;
-int n = size;
+for (int i = 0, n = size; i < n; i++)
+es[i] = null;
 size = 0;
-for (int i = 0; i < n; i++)
-array[i] = null;
 } finally {
 lock.unlock();
 }
 }
 * Snapshot iterator that works off copy of underlying q array.
 */
 final class Itr implements Iterator<E> {
 final Object[] array; // Array of all elements
 int cursor;           // index of next element to return
-int lastRet;          // index of last element, or -1 if no such
+int lastRet = -1;     // index of last element, or -1 if no such
 Itr(Object[] array) {
-lastRet = -1;
 this.array = array;
 }
 public boolean hasNext() {
 return cursor < array.length;
 }
 public void remove() {
 if (lastRet < 0)
 throw new IllegalStateException();
-removeEQ(array[lastRet]);
+removeEq(array[lastRet]);
 lastRet = -1;
+}
+public void forEachRemaining(Consumer<? super E> action) {
+Objects.requireNonNull(action);
+final Object[] es = array;
+int i;
+if ((i = cursor) < es.length) {
+lastRet = -1;
+cursor = es.length;
+for (; i < es.length; i++)
+action.accept((E) es[i]);
+lastRet = es.length - 1;
+}
 }
 }
 /**
 * Saves this queue to a stream (that is, serializes it).
 throws java.io.IOException, ClassNotFoundException {
 try {
 s.defaultReadObject();
 int sz = q.size();
 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, sz);
-this.queue = new Object[sz];
+this.queue = new Object[Math.max(1, sz)];
 comparator = q.comparator();
 addAll(q);
 } finally {
 q = null;
 }
 }
 public void forEachRemaining(Consumer<? super E> action) {
 Objects.requireNonNull(action);
 final int hi = getFence(), lo = index;
-final Object[] a = array;
+final Object[] es = array;
 index = hi;                 // ensure exhaustion
 for (int i = lo; i < hi; i++)
-action.accept((E) a[i]);
+action.accept((E) es[i]);
 }
 public boolean tryAdvance(Consumer<? super E> action) {
 Objects.requireNonNull(action);
 if (getFence() > index && index >= 0) {
 */
 public Spliterator<E> spliterator() {
 return new PBQSpliterator();
 }
+/**
+* @throws NullPointerException {@inheritDoc}
+*/
+public boolean removeIf(Predicate<? super E> filter) {
+Objects.requireNonNull(filter);
+return bulkRemove(filter);
+}
+/**
+* @throws NullPointerException {@inheritDoc}
+*/
+public boolean removeAll(Collection<?> c) {
+Objects.requireNonNull(c);
+return bulkRemove(e -> c.contains(e));
+}
+/**
+* @throws NullPointerException {@inheritDoc}
+*/
+public boolean retainAll(Collection<?> c) {
+Objects.requireNonNull(c);
+return bulkRemove(e -> !c.contains(e));
+}
+// A tiny bit set implementation
+private static long[] nBits(int n) {
+return new long[((n - 1) >> 6) + 1];
+}
+private static void setBit(long[] bits, int i) {
+bits[i >> 6] |= 1L << i;
+}
+private static boolean isClear(long[] bits, int i) {
+return (bits[i >> 6] & (1L << i)) == 0;
+}
+/** Implementation of bulk remove methods. */
+private boolean bulkRemove(Predicate<? super E> filter) {
+final ReentrantLock lock = this.lock;
+lock.lock();
+try {
+final Object[] es = queue;
+final int end = size;
+int i;
+// Optimize for initial run of survivors
+for (i = 0; i < end && !filter.test((E) es[i]); i++)
+;
+if (i >= end)
+return false;
+// Tolerate predicates that reentrantly access the
+// collection for read, so traverse once to find elements
+// to delete, a second pass to physically expunge.
+final int beg = i;
+final long[] deathRow = nBits(end - beg);
+deathRow[0] = 1L;   // set bit 0
+for (i = beg + 1; i < end; i++)
+if (filter.test((E) es[i]))
+setBit(deathRow, i - beg);
+int w = beg;
+for (i = beg; i < end; i++)
+if (isClear(deathRow, i - beg))
+es[w++] = es[i];
+for (i = size = w; i < end; i++)
+es[i] = null;
+heapify();
+return true;
+} finally {
+lock.unlock();
+}
+}
+/**
+* @throws NullPointerException {@inheritDoc}
+*/
+public void forEach(Consumer<? super E> action) {
+Objects.requireNonNull(action);
+final ReentrantLock lock = this.lock;
+lock.lock();
+try {
+final Object[] es = queue;
+for (int i = 0, n = size; i < n; i++)
+action.accept((E) es[i]);
+} finally {
+lock.unlock();
+}
+}
 // VarHandle mechanics
 private static final VarHandle ALLOCATIONSPINLOCK;
 static {
 try {
 MethodHandles.Lookup l = MethodHandles.lookup();

changeset 50229	6b29ef846c5c
parent 49792	cfdce76e0449
child 52427	3c6aa484536c