changeset 50813:6b29ef846c5c

8201386: Miscellaneous changes imported from jsr166 CVS 2018-05 Reviewed-by: martin, psandoz
author dl
date Tue, 22 May 2018 21:50:45 -0700
parents 45093fb73c6d
children cae567ae015d
files src/java.base/share/classes/java/util/PriorityQueue.java src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java test/jdk/java/util/ArrayList/IteratorMicroBenchmark.java test/jdk/java/util/Collection/IteratorMicroBenchmark.java test/jdk/java/util/Collection/RemoveMicroBenchmark.java test/jdk/java/util/WeakHashMap/GCDuringIteration.java test/jdk/java/util/concurrent/ArrayBlockingQueue/WhiteBox.java test/jdk/java/util/concurrent/ConcurrentQueues/GCRetention.java test/jdk/java/util/concurrent/PriorityBlockingQueue/WhiteBox.java test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java test/jdk/java/util/concurrent/locks/Lock/TimedAcquireLeak.java test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java test/jdk/java/util/concurrent/tck/PriorityBlockingQueueTest.java test/jdk/java/util/concurrent/tck/PriorityQueueTest.java test/jdk/java/util/concurrent/tck/VectorTest.java
diffstat 15 files changed, 836 insertions(+), 276 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/PriorityQueue.java	Tue May 22 21:46:51 2018 -0700
+++ b/src/java.base/share/classes/java/util/PriorityQueue.java	Tue May 22 21:50:45 2018 -0700
@@ -26,6 +26,7 @@
 package java.util;
 
 import java.util.function.Consumer;
+import java.util.function.Predicate;
 import jdk.internal.misc.SharedSecrets;
 
 /**
@@ -81,6 +82,7 @@
  * @author Josh Bloch, Doug Lea
  * @param <E> the type of elements held in this queue
  */
+@SuppressWarnings("unchecked")
 public class PriorityQueue<E> extends AbstractQueue<E>
     implements java.io.Serializable {
 
@@ -187,7 +189,6 @@
      * @throws NullPointerException if the specified collection or any
      *         of its elements are null
      */
-    @SuppressWarnings("unchecked")
     public PriorityQueue(Collection<? extends E> c) {
         if (c instanceof SortedSet<?>) {
             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
@@ -219,7 +220,6 @@
      * @throws NullPointerException if the specified priority queue or any
      *         of its elements are null
      */
-    @SuppressWarnings("unchecked")
     public PriorityQueue(PriorityQueue<? extends E> c) {
         this.comparator = (Comparator<? super E>) c.comparator();
         initFromPriorityQueue(c);
@@ -238,15 +238,19 @@
      * @throws NullPointerException if the specified sorted set or any
      *         of its elements are null
      */
-    @SuppressWarnings("unchecked")
     public PriorityQueue(SortedSet<? extends E> c) {
         this.comparator = (Comparator<? super E>) c.comparator();
         initElementsFromCollection(c);
     }
 
+    /** Ensures that queue[0] exists, helping peek() and poll(). */
+    private static Object[] ensureNonEmpty(Object[] es) {
+        return (es.length > 0) ? es : new Object[1];
+    }
+
     private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
         if (c.getClass() == PriorityQueue.class) {
-            this.queue = c.toArray();
+            this.queue = ensureNonEmpty(c.toArray());
             this.size = c.size();
         } else {
             initFromCollection(c);
@@ -254,17 +258,17 @@
     }
 
     private void initElementsFromCollection(Collection<? extends E> c) {
-        Object[] a = c.toArray();
+        Object[] es = c.toArray();
+        int len = es.length;
         // If c.toArray incorrectly doesn't return Object[], copy it.
-        if (a.getClass() != Object[].class)
-            a = Arrays.copyOf(a, a.length, Object[].class);
-        int len = a.length;
+        if (es.getClass() != Object[].class)
+            es = Arrays.copyOf(es, len, Object[].class);
         if (len == 1 || this.comparator != null)
-            for (Object e : a)
+            for (Object e : es)
                 if (e == null)
                     throw new NullPointerException();
-        this.queue = a;
-        this.size = a.length;
+        this.queue = ensureNonEmpty(es);
+        this.size = len;
     }
 
     /**
@@ -344,15 +348,15 @@
         return true;
     }
 
-    @SuppressWarnings("unchecked")
     public E peek() {
-        return (size == 0) ? null : (E) queue[0];
+        return (E) queue[0];
     }
 
     private int indexOf(Object o) {
         if (o != null) {
-            for (int i = 0; i < size; i++)
-                if (o.equals(queue[i]))
+            final Object[] es = queue;
+            for (int i = 0, n = size; i < n; i++)
+                if (o.equals(es[i]))
                     return i;
         }
         return -1;
@@ -380,20 +384,18 @@
     }
 
     /**
-     * Version of remove using reference equality, not equals.
-     * Needed by iterator.remove.
+     * Identity-based version for use in Itr.remove.
      *
      * @param o element to be removed from this queue, if present
-     * @return {@code true} if removed
      */
-    boolean removeEq(Object o) {
-        for (int i = 0; i < size; i++) {
-            if (o == queue[i]) {
+    void removeEq(Object o) {
+        final Object[] es = queue;
+        for (int i = 0, n = size; i < n; i++) {
+            if (o == es[i]) {
                 removeAt(i);
-                return true;
+                break;
             }
         }
-        return false;
     }
 
     /**
@@ -461,7 +463,6 @@
      *         this queue
      * @throws NullPointerException if the specified array is null
      */
-    @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
         final int size = this.size;
         if (a.length < size)
@@ -530,7 +531,6 @@
                 (forgetMeNot != null && !forgetMeNot.isEmpty());
         }
 
-        @SuppressWarnings("unchecked")
         public E next() {
             if (expectedModCount != modCount)
                 throw new ConcurrentModificationException();
@@ -578,22 +578,29 @@
      */
     public void clear() {
         modCount++;
-        for (int i = 0; i < size; i++)
-            queue[i] = null;
+        final Object[] es = queue;
+        for (int i = 0, n = size; i < n; i++)
+            es[i] = null;
         size = 0;
     }
 
-    @SuppressWarnings("unchecked")
     public E poll() {
-        if (size == 0)
-            return null;
-        int s = --size;
-        modCount++;
-        E result = (E) queue[0];
-        E x = (E) queue[s];
-        queue[s] = null;
-        if (s != 0)
-            siftDown(0, x);
+        final Object[] es;
+        final E result;
+
+        if ((result = (E) ((es = queue)[0])) != null) {
+            modCount++;
+            final int n;
+            final E x = (E) es[(n = --size)];
+            es[n] = null;
+            if (n > 0) {
+                final Comparator<? super E> cmp;
+                if ((cmp = comparator) == null)
+                    siftDownComparable(0, x, es, n);
+                else
+                    siftDownUsingComparator(0, x, es, n, cmp);
+            }
+        }
         return result;
     }
 
@@ -609,20 +616,20 @@
      * position before i. This fact is used by iterator.remove so as to
      * avoid missing traversing elements.
      */
-    @SuppressWarnings("unchecked")
     E removeAt(int i) {
         // assert i >= 0 && i < size;
+        final Object[] es = queue;
         modCount++;
         int s = --size;
         if (s == i) // removed last element
-            queue[i] = null;
+            es[i] = null;
         else {
-            E moved = (E) queue[s];
-            queue[s] = null;
+            E moved = (E) es[s];
+            es[s] = null;
             siftDown(i, moved);
-            if (queue[i] == moved) {
+            if (es[i] == moved) {
                 siftUp(i, moved);
-                if (queue[i] != moved)
+                if (es[i] != moved)
                     return moved;
             }
         }
@@ -643,36 +650,35 @@
      */
     private void siftUp(int k, E x) {
         if (comparator != null)
-            siftUpUsingComparator(k, x);
+            siftUpUsingComparator(k, x, queue, comparator);
         else
-            siftUpComparable(k, x);
+            siftUpComparable(k, x, queue);
     }
 
-    @SuppressWarnings("unchecked")
-    private void siftUpComparable(int k, E x) {
-        Comparable<? super E> key = (Comparable<? super E>) x;
+    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 = queue[parent];
-            if (key.compareTo((E) e) >= 0)
+            Object e = es[parent];
+            if (key.compareTo((T) e) >= 0)
                 break;
-            queue[k] = e;
+            es[k] = e;
             k = parent;
         }
-        queue[k] = key;
+        es[k] = key;
     }
 
-    @SuppressWarnings("unchecked")
-    private void siftUpUsingComparator(int k, E x) {
+    private static <T> void siftUpUsingComparator(
+        int k, T x, Object[] es, Comparator<? super T> cmp) {
         while (k > 0) {
             int parent = (k - 1) >>> 1;
-            Object e = queue[parent];
-            if (comparator.compare(x, (E) e) >= 0)
+            Object e = es[parent];
+            if (cmp.compare(x, (T) e) >= 0)
                 break;
-            queue[k] = e;
+            es[k] = e;
             k = parent;
         }
-        queue[k] = x;
+        es[k] = x;
     }
 
     /**
@@ -685,46 +691,46 @@
      */
     private void siftDown(int k, E x) {
         if (comparator != null)
-            siftDownUsingComparator(k, x);
+            siftDownUsingComparator(k, x, queue, size, comparator);
         else
-            siftDownComparable(k, x);
+            siftDownComparable(k, x, queue, size);
     }
 
-    @SuppressWarnings("unchecked")
-    private void siftDownComparable(int k, E x) {
-        Comparable<? super E> key = (Comparable<? super E>)x;
-        int half = size >>> 1;        // loop while a non-leaf
+    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
+        // assert n > 0;
+        Comparable<? super T> key = (Comparable<? super T>)x;
+        int half = n >>> 1;           // loop while a non-leaf
         while (k < half) {
             int child = (k << 1) + 1; // assume left child is least
-            Object c = queue[child];
+            Object c = es[child];
             int right = child + 1;
-            if (right < size &&
-                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
-                c = queue[child = right];
-            if (key.compareTo((E) c) <= 0)
+            if (right < n &&
+                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
+                c = es[child = right];
+            if (key.compareTo((T) c) <= 0)
                 break;
-            queue[k] = c;
+            es[k] = c;
             k = child;
         }
-        queue[k] = key;
+        es[k] = key;
     }
 
-    @SuppressWarnings("unchecked")
-    private void siftDownUsingComparator(int k, E x) {
-        int half = size >>> 1;
+    private static <T> void siftDownUsingComparator(
+        int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
+        // assert n > 0;
+        int half = n >>> 1;
         while (k < half) {
             int child = (k << 1) + 1;
-            Object c = queue[child];
+            Object c = es[child];
             int right = child + 1;
-            if (right < size &&
-                comparator.compare((E) c, (E) queue[right]) > 0)
-                c = queue[child = right];
-            if (comparator.compare(x, (E) c) <= 0)
+            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
+                c = es[child = right];
+            if (cmp.compare(x, (T) c) <= 0)
                 break;
-            queue[k] = c;
+            es[k] = c;
             k = child;
         }
-        queue[k] = x;
+        es[k] = x;
     }
 
     /**
@@ -732,16 +738,16 @@
      * 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).
      */
-    @SuppressWarnings("unchecked")
     private void heapify() {
         final Object[] es = queue;
-        int i = (size >>> 1) - 1;
-        if (comparator == null)
+        int n = size, i = (n >>> 1) - 1;
+        final Comparator<? super E> cmp;
+        if ((cmp = comparator) == null)
             for (; i >= 0; i--)
-                siftDownComparable(i, (E) es[i]);
+                siftDownComparable(i, (E) es[i], es, n);
         else
             for (; i >= 0; i--)
-                siftDownUsingComparator(i, (E) es[i]);
+                siftDownUsingComparator(i, (E) es[i], es, n, cmp);
     }
 
     /**
@@ -775,8 +781,9 @@
         s.writeInt(Math.max(2, size + 1));
 
         // Write out all elements in the "proper order".
-        for (int i = 0; i < size; i++)
-            s.writeObject(queue[i]);
+        final Object[] es = queue;
+        for (int i = 0, n = size; i < n; i++)
+            s.writeObject(es[i]);
     }
 
     /**
@@ -797,11 +804,11 @@
         s.readInt();
 
         SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
-        queue = new Object[size];
+        final Object[] es = queue = new Object[Math.max(size, 1)];
 
         // Read in all elements.
-        for (int i = 0; i < size; i++)
-            queue[i] = s.readObject();
+        for (int i = 0, n = size; i < n; i++)
+            es[i] = s.readObject();
 
         // Elements are guaranteed to be in "proper order", but the
         // spec has never explained what that might be.
@@ -853,15 +860,14 @@
                 new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
         }
 
-        @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super E> action) {
             if (action == null)
                 throw new NullPointerException();
             if (fence < 0) { fence = size; expectedModCount = modCount; }
-            final Object[] a = queue;
+            final Object[] es = queue;
             int i, hi; E e;
             for (i = index, index = hi = fence; i < hi; i++) {
-                if ((e = (E) a[i]) == null)
+                if ((e = (E) es[i]) == null)
                     break;      // must be CME
                 action.accept(e);
             }
@@ -869,7 +875,6 @@
                 throw new ConcurrentModificationException();
         }
 
-        @SuppressWarnings("unchecked")
         public boolean tryAdvance(Consumer<? super E> action) {
             if (action == null)
                 throw new NullPointerException();
@@ -895,4 +900,88 @@
             return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
         }
     }
+
+    /**
+     * @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 int expectedModCount = ++modCount;
+        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) {
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return false;
+        }
+        // Tolerate predicates that reentrantly access the collection for
+        // read (but writers still get CME), 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);
+        if (modCount != expectedModCount)
+            throw new ConcurrentModificationException();
+        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;
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        final int expectedModCount = modCount;
+        final Object[] es = queue;
+        for (int i = 0, n = size; i < n; i++)
+            action.accept((E) es[i]);
+        if (expectedModCount != modCount)
+            throw new ConcurrentModificationException();
+    }
 }
--- a/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java	Tue May 22 21:46:51 2018 -0700
+++ b/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java	Tue May 22 21:50:45 2018 -0700
@@ -51,6 +51,7 @@
 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;
 
 /**
@@ -167,12 +168,12 @@
     /**
      * 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.
@@ -224,10 +225,8 @@
                                  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)];
     }
 
     /**
@@ -247,8 +246,6 @@
      *         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<?>) {
@@ -264,22 +261,27 @@
             if (pq.getClass() == PriorityBlockingQueue.class) // exact match
                 heapify = false;
         }
-        Object[] a = c.toArray();
-        int n = a.length;
+        Object[] es = c.toArray();
+        int n = es.length;
         // If c.toArray incorrectly doesn't return Object[], copy it.
-        if (a.getClass() != Object[].class)
-            a = Arrays.copyOf(a, n, Object[].class);
+        if (es.getClass() != Object[].class)
+            es = Arrays.copyOf(es, n, Object[].class);
         if (screen && (n == 1 || this.comparator != null)) {
-            for (Object elt : a)
-                if (elt == null)
+            for (Object e : es)
+                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)
@@ -323,22 +325,23 @@
      * Mechanics for poll().  Call only while holding lock.
      */
     private E dequeue() {
-        int n = size - 1;
-        if (n < 0)
-            return null;
-        else {
-            Object[] array = queue;
-            E result = (E) array[0];
-            E x = (E) array[n];
-            array[n] = null;
-            Comparator<? super E> cmp = comparator;
-            if (cmp == null)
-                siftDownComparable(0, x, array, n);
-            else
-                siftDownUsingComparator(0, x, array, n, cmp);
-            size = n;
-            return result;
+        // assert lock.isHeldByCurrentThread();
+        final Object[] es;
+        final E result;
+
+        if ((result = (E) ((es = queue)[0])) != null) {
+            final int n;
+            final E x = (E) es[(n = --size)];
+            es[n] = null;
+            if (n > 0) {
+                final Comparator<? super E> cmp;
+                if ((cmp = comparator) == null)
+                    siftDownComparable(0, x, es, n);
+                else
+                    siftDownUsingComparator(0, x, es, n, cmp);
+            }
         }
+        return result;
     }
 
     /**
@@ -352,32 +355,32 @@
      *
      * @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,
-                                       Comparator<? super T> cmp) {
+    private static <T> void siftUpUsingComparator(
+        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;
     }
 
     /**
@@ -387,48 +390,44 @@
      *
      * @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,
-                                               int n) {
-        if (n > 0) {
-            Comparable<? super T> key = (Comparable<? super T>)x;
-            int half = n >>> 1;           // loop while a non-leaf
-            while (k < half) {
-                int child = (k << 1) + 1; // assume left child is least
-                Object c = array[child];
-                int right = child + 1;
-                if (right < n &&
-                    ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
-                    c = array[child = right];
-                if (key.compareTo((T) c) <= 0)
-                    break;
-                array[k] = c;
-                k = child;
-            }
-            array[k] = key;
+    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
+        // assert n > 0;
+        Comparable<? super T> key = (Comparable<? super T>)x;
+        int half = n >>> 1;           // loop while a non-leaf
+        while (k < half) {
+            int child = (k << 1) + 1; // assume left child is least
+            Object c = es[child];
+            int right = child + 1;
+            if (right < n &&
+                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
+                c = es[child = right];
+            if (key.compareTo((T) c) <= 0)
+                break;
+            es[k] = c;
+            k = child;
         }
+        es[k] = key;
     }
 
-    private static <T> void siftDownUsingComparator(int k, T x, Object[] array,
-                                                    int n,
-                                                    Comparator<? super T> cmp) {
-        if (n > 0) {
-            int half = n >>> 1;
-            while (k < half) {
-                int child = (k << 1) + 1;
-                Object c = array[child];
-                int right = child + 1;
-                if (right < n && cmp.compare((T) c, (T) array[right]) > 0)
-                    c = array[child = right];
-                if (cmp.compare(x, (T) c) <= 0)
-                    break;
-                array[k] = c;
-                k = child;
-            }
-            array[k] = x;
+    private static <T> void siftDownUsingComparator(
+        int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
+        // assert n > 0;
+        int half = n >>> 1;
+        while (k < half) {
+            int child = (k << 1) + 1;
+            Object c = es[child];
+            int right = child + 1;
+            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
+                c = es[child = right];
+            if (cmp.compare(x, (T) c) <= 0)
+                break;
+            es[k] = c;
+            k = child;
         }
+        es[k] = x;
     }
 
     /**
@@ -437,17 +436,15 @@
      * 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;
-        if (cmp == null) {
+        final Comparator<? super E> cmp;
+        if ((cmp = comparator) == null)
             for (; i >= 0; i--)
-                siftDownComparable(i, (E) array[i], array, n);
-        }
-        else {
+                siftDownComparable(i, (E) es[i], es, n);
+        else
             for (; i >= 0; i--)
-                siftDownUsingComparator(i, (E) array[i], array, n, cmp);
-        }
+                siftDownUsingComparator(i, (E) es[i], es, n, cmp);
     }
 
     /**
@@ -481,15 +478,15 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         int n, cap;
-        Object[] array;
-        while ((n = size) >= (cap = (array = queue).length))
-            tryGrow(array, cap);
+        Object[] es;
+        while ((n = size) >= (cap = (es = queue).length))
+            tryGrow(es, cap);
         try {
-            Comparator<? super E> cmp = comparator;
-            if (cmp == null)
-                siftUpComparable(n, e, array);
+            final Comparator<? super E> cmp;
+            if ((cmp = comparator) == null)
+                siftUpComparable(n, e, es);
             else
-                siftUpUsingComparator(n, e, array, cmp);
+                siftUpUsingComparator(n, e, es, cmp);
             size = n + 1;
             notEmpty.signal();
         } finally {
@@ -572,7 +569,7 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return (size == 0) ? null : (E) queue[0];
+            return (E) queue[0];
         } finally {
             lock.unlock();
         }
@@ -612,10 +609,9 @@
 
     private int indexOf(Object o) {
         if (o != null) {
-            Object[] array = queue;
-            int n = size;
-            for (int i = 0; i < n; i++)
-                if (o.equals(array[i]))
+            final Object[] es = queue;
+            for (int i = 0, n = size; i < n; i++)
+                if (o.equals(es[i]))
                     return i;
         }
         return -1;
@@ -625,23 +621,23 @@
      * Removes the ith element from queue.
      */
     private void removeAt(int i) {
-        Object[] array = queue;
-        int n = size - 1;
+        final Object[] es = queue;
+        final int n = size - 1;
         if (n == i) // removed last element
-            array[i] = null;
+            es[i] = null;
         else {
-            E moved = (E) array[n];
-            array[n] = null;
-            Comparator<? super E> cmp = comparator;
-            if (cmp == null)
-                siftDownComparable(i, moved, array, n);
+            E moved = (E) es[n];
+            es[n] = null;
+            final Comparator<? super E> cmp;
+            if ((cmp = comparator) == null)
+                siftDownComparable(i, moved, es, n);
             else
-                siftDownUsingComparator(i, moved, array, n, cmp);
-            if (array[i] == moved) {
+                siftDownUsingComparator(i, moved, es, n, cmp);
+            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;
@@ -674,14 +670,16 @@
 
     /**
      * Identity-based version for use in Itr.remove.
+     *
+     * @param o element to be removed from this queue, if present
      */
-    void removeEQ(Object o) {
+    void removeEq(Object o) {
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            Object[] array = queue;
+            final Object[] es = queue;
             for (int i = 0, n = size; i < n; i++) {
-                if (o == array[i]) {
+                if (o == es[i]) {
                     removeAt(i);
                     break;
                 }
@@ -757,11 +755,10 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            Object[] array = queue;
-            int n = size;
+            final Object[] es = queue;
+            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();
         }
@@ -862,10 +859,9 @@
     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;
         }
 
@@ -882,9 +878,22 @@
         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;
+            }
+        }
     }
 
     /**
@@ -924,7 +933,7 @@
             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 {
@@ -963,10 +972,10 @@
         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) {
@@ -1008,6 +1017,93 @@
         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 {
--- a/test/jdk/java/util/ArrayList/IteratorMicroBenchmark.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/ArrayList/IteratorMicroBenchmark.java	Tue May 22 21:50:45 2018 -0700
@@ -27,8 +27,10 @@
  * @run main IteratorMicroBenchmark iterations=1 size=8 warmup=0
  */
 
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 import static java.util.stream.Collectors.toList;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
@@ -43,7 +45,6 @@
 import java.util.concurrent.ConcurrentSkipListMap;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.ThreadLocalRandom;
-import java.util.concurrent.TimeUnit;
 import java.util.regex.Pattern;
 
 /**
@@ -70,16 +71,22 @@
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
--- a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java	Tue May 22 21:50:45 2018 -0700
@@ -27,11 +27,14 @@
  * @run main IteratorMicroBenchmark iterations=1 size=8 warmup=0
  */
 
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 import static java.util.stream.Collectors.summingInt;
 import static java.util.stream.Collectors.toCollection;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.util.ArrayDeque;
+import java.util.Arrays;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
@@ -54,7 +57,6 @@
 import java.util.concurrent.PriorityBlockingQueue;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.ThreadLocalRandom;
-import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.LongAdder;
 import java.util.function.UnaryOperator;
 import java.util.regex.Pattern;
@@ -109,17 +111,22 @@
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            @SuppressWarnings("deprecation")
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
@@ -556,6 +563,18 @@
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
                         x.replaceAll(sneakyAdder);
-                        check.sum(sum[0]);}}});
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " equals") {
+                public void work() throws Throwable {
+                    ArrayList<Integer> copy = new ArrayList<>(x);
+                    for (int i = 0; i < iterations; i++) {
+                        if (!x.equals(copy))
+                            throw new AssertionError();}}},
+            new Job(klazz + " hashCode") {
+                public void work() throws Throwable {
+                    int hashCode = Arrays.hashCode(x.toArray());
+                    for (int i = 0; i < iterations; i++) {
+                        if (x.hashCode() != hashCode)
+                            throw new AssertionError();}}});
     }
 }
--- a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java	Tue May 22 21:50:45 2018 -0700
@@ -27,8 +27,10 @@
  * @run main RemoveMicroBenchmark iterations=1 size=8 warmup=0
  */
 
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 import static java.util.stream.Collectors.toCollection;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
@@ -112,17 +114,22 @@
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            @SuppressWarnings("deprecation")
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
@@ -504,6 +511,15 @@
     Stream<Job> blockingQueueJobs(BlockingQueue<Integer> x) {
         final String klazz = goodClassName(x.getClass());
         return Stream.of(
+            new Job(klazz + " timed poll()") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(elements);
+                        for (Integer e; (e = x.poll(0L, TimeUnit.DAYS)) != null; )
+                            sum[0] += e;
+                        check.sum(sum[0]);}}},
             new Job(klazz + " drainTo(sink)") {
                 public void work() throws Throwable {
                     ArrayList<Integer> sink = new ArrayList<>();
--- a/test/jdk/java/util/WeakHashMap/GCDuringIteration.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/WeakHashMap/GCDuringIteration.java	Tue May 22 21:50:45 2018 -0700
@@ -34,6 +34,7 @@
 
 import jdk.test.lib.RandomFactory;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.util.Arrays;
 import java.util.Iterator;
@@ -44,22 +45,28 @@
 import java.util.concurrent.CountDownLatch;
 import java.util.function.BooleanSupplier;
 
-import static java.util.concurrent.TimeUnit.SECONDS;
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 
 public class GCDuringIteration {
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
--- a/test/jdk/java/util/concurrent/ArrayBlockingQueue/WhiteBox.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/ArrayBlockingQueue/WhiteBox.java	Tue May 22 21:50:45 2018 -0700
@@ -38,10 +38,12 @@
  * @summary White box tests of implementation details
  */
 
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 import static org.testng.Assert.*;
 
 import org.testng.annotations.Test;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.lang.invoke.MethodHandles;
 import java.lang.invoke.VarHandle;
@@ -202,16 +204,22 @@
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
--- a/test/jdk/java/util/concurrent/ConcurrentQueues/GCRetention.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/ConcurrentQueues/GCRetention.java	Tue May 22 21:50:45 2018 -0700
@@ -38,8 +38,9 @@
  * @run main GCRetention just-testing
  */
 
-import static java.util.concurrent.TimeUnit.SECONDS;
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.ConcurrentHashMap;
@@ -65,16 +66,22 @@
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/jdk/java/util/concurrent/PriorityBlockingQueue/WhiteBox.java	Tue May 22 21:50:45 2018 -0700
@@ -0,0 +1,270 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Martin Buchholz with assistance from members of JCP
+ * JSR-166 Expert Group and released to the public domain, as
+ * explained at http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+/*
+ * @test
+ * @modules java.base/java.util.concurrent:open
+ *          java.base/java.util:open
+ * @run testng WhiteBox
+ * @summary White box tests of implementation details
+ */
+
+import static org.testng.Assert.*;
+import org.testng.annotations.Test;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.Set;
+import java.util.concurrent.PriorityBlockingQueue;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+
+@Test
+public class WhiteBox {
+    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+    final VarHandle PQ_QUEUE = queueVarHandle(PriorityQueue.class);
+    final VarHandle PBQ_QUEUE = queueVarHandle(PriorityBlockingQueue.class);
+
+    VarHandle queueVarHandle(Class klazz) {
+        return findVarHandle(klazz, "queue", Object[].class);
+    }
+
+    VarHandle findVarHandle(Class klazz, String fieldName, Class type) {
+        try {
+            return MethodHandles.privateLookupIn(klazz, MethodHandles.lookup())
+                .findVarHandle(klazz, fieldName, type);
+        } catch (ReflectiveOperationException ex) { throw new Error(ex); }
+    }
+
+    Object[] queue(PriorityQueue q) {
+        return (Object[]) PQ_QUEUE.getOpaque(q);
+    }
+
+    Object[] queue(PriorityBlockingQueue q) {
+        return (Object[]) PBQ_QUEUE.getOpaque(q);
+    }
+
+    /** PriorityQueue and PriorityBlockingQueue have identical heap management. */
+    @Test
+    public void randomLockstep() {
+        PriorityBlockingQueue pbq = new PriorityBlockingQueue();
+        PriorityQueue pq = new PriorityQueue();
+        List<Consumer<Queue>> frobbers = List.of(
+            q -> q.add(42),
+            q -> assertTrue(q.offer(86)),
+            q -> q.poll(),
+            q -> q.peek(),
+            q -> {
+                Iterator it = q.iterator();
+                if (it.hasNext()) {
+                    it.next();
+                    it.remove();
+                }});
+        for (int i = 0; i < 100; i++) {
+            Consumer<Queue> frobber = frobbers.get(rnd.nextInt(frobbers.size()));
+            frobber.accept(pq);
+            frobber.accept(pbq);
+            assertInvariants(pbq);
+            assertInvariants(pq);
+            assertTrue(Arrays.equals(pq.toArray(), pbq.toArray()));
+        }
+    }
+
+    @Test
+    public void forgetMeNot_PriorityQueue() {
+        forgetMeNot(() -> new PriorityQueue());
+        forgetMeNot(() -> new PriorityQueue(rnd.nextInt(1, 100)));
+        forgetMeNot(() -> new PriorityQueue(rnd.nextInt(1, 100), Collections.reverseOrder()));
+    }
+
+    @Test
+    public void forgetMeNot_PriorityBlockingQueue() {
+        forgetMeNot(() -> new PriorityBlockingQueue());
+        forgetMeNot(() -> new PriorityBlockingQueue(rnd.nextInt(1, 100)));
+        forgetMeNot(() -> new PriorityBlockingQueue(rnd.nextInt(1, 100), Collections.reverseOrder()));
+    }
+
+    void forgetMeNot(Supplier<Queue> qMaker) {
+        Queue q = qMaker.get();
+        Set replay = Collections.newSetFromMap(new IdentityHashMap());
+        int size = rnd.nextInt(64);
+        for (int i = 0; i < size; i++) {
+            Object e = new Integer(rnd.nextInt());
+            q.add(e);
+            replay.add(e);
+        }
+        Iterator it = q.iterator();
+        while (it.hasNext()) {
+            Object e = it.next();
+            assertTrue(replay.contains(e));
+            if (rnd.nextBoolean()) {
+                it.remove();
+                if (rnd.nextBoolean())
+                    assertThrows(IllegalStateException.class,
+                                 () -> it.remove());
+                assertTrue(replay.remove(e));
+            }
+            assertInvariants(q);
+        }
+        for (Object e; (e = q.poll()) != null; )
+            assertTrue(replay.remove(e));
+        assertTrue(replay.isEmpty());
+    }
+
+    @Test
+    public void testRemoveIf_PriorityQueue() {
+        testRemoveIf(() -> new PriorityQueue());
+        testRemoveIf(() -> new PriorityQueue(rnd.nextInt(1, 100)));
+        testRemoveIf(() -> new PriorityQueue(rnd.nextInt(1, 100), Collections.reverseOrder()));
+    }
+
+    @Test
+    public void testRemoveIf_PriorityBlockingQueue() {
+        testRemoveIf(() -> new PriorityBlockingQueue());
+        testRemoveIf(() -> new PriorityBlockingQueue(rnd.nextInt(1, 100)));
+        testRemoveIf(() -> new PriorityBlockingQueue(rnd.nextInt(1, 100), Collections.reverseOrder()));
+    }
+
+    void testRemoveIf(Supplier<Queue> qMaker) {
+        Queue q = qMaker.get();
+        Set replay = Collections.newSetFromMap(new IdentityHashMap());
+        int size = rnd.nextInt(64);
+        for (int i = 0; i < size; i++) {
+            Object e = new Integer(rnd.nextInt());
+            q.add(e);
+            replay.add(e);
+        }
+        q.removeIf(
+            e -> {
+                if (rnd.nextBoolean())
+                    return false;
+                assertTrue(replay.remove(e));
+                return true;
+            });
+        assertInvariants(q);
+        for (Object e; (e = q.poll()) != null; )
+            assertTrue(replay.remove(e));
+        assertTrue(replay.isEmpty());
+    }
+
+    byte[] serialBytes(Object o) {
+        try {
+            ByteArrayOutputStream bos = new ByteArrayOutputStream();
+            ObjectOutputStream oos = new ObjectOutputStream(bos);
+            oos.writeObject(o);
+            oos.flush();
+            oos.close();
+            return bos.toByteArray();
+        } catch (Exception fail) {
+            throw new AssertionError(fail);
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    <T> T serialClone(T o) {
+        try {
+            ObjectInputStream ois = new ObjectInputStream
+                (new ByteArrayInputStream(serialBytes(o)));
+            T clone = (T) ois.readObject();
+            assertNotSame(o, clone);
+            assertSame(o.getClass(), clone.getClass());
+            return clone;
+        } catch (Exception fail) {
+            throw new AssertionError(fail);
+        }
+    }
+
+    @Test
+    public void testSerialization() {
+        assertInvariants(serialClone(new PriorityQueue()));
+        assertInvariants(serialClone(new PriorityQueue(1)));
+        assertInvariants(serialClone(new PriorityQueue(new ArrayList())));
+        assertInvariants(serialClone(new PriorityBlockingQueue()));
+        assertInvariants(serialClone(new PriorityBlockingQueue(1)));
+        assertInvariants(serialClone(new PriorityBlockingQueue(new ArrayList())));
+    }
+
+    void assertInvariants(Queue q) {
+        if (q instanceof PriorityQueue)
+            assertInvariants((PriorityQueue) q);
+        else
+            assertInvariants((PriorityBlockingQueue) q);
+    }
+
+    void assertInvariants(PriorityBlockingQueue q) {
+        assertHeap(queue(q), q.size(), q.comparator());
+    }
+
+    void assertInvariants(PriorityQueue q) {
+        assertHeap(queue(q), q.size(), q.comparator());
+    }
+
+    void assertHeap(Object[] es, int size, Comparator cmp) {
+        assertTrue(es.length > 0);
+        assertTrue(size >= 0 && size <= es.length);
+        if (size < es.length)
+            assertNull(es[size]);
+        if (size > 0)
+            assertNotNull(es[size - 1]);
+        for (int i = 0; i <= size / 2; i++) {
+            int leftChild = 2 * i + 1;
+            int rightChild = leftChild + 1;
+            if (leftChild < size)
+                assertTrue(cmp(es[i], es[leftChild], cmp) <= 0);
+            if (rightChild < size)
+                assertTrue(cmp(es[i], es[rightChild], cmp) <= 0);
+        }
+    }
+
+    int cmp(Object x, Object y, Comparator cmp) {
+        return (cmp == null)
+            ? ((Comparable) x).compareTo(y)
+            : cmp.compare(x, y);
+    }
+
+}
--- a/test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/forkjoin/FJExceptionTableLeak.java	Tue May 22 21:50:45 2018 -0700
@@ -40,8 +40,9 @@
  * This whitebox test is sensitive to forkjoin implementation details.
  */
 
-import static java.util.concurrent.TimeUnit.SECONDS;
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.lang.reflect.Field;
 import java.util.ArrayList;
@@ -115,16 +116,22 @@
 
     /** No guarantees, but effective in practice. */
     static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
--- a/test/jdk/java/util/concurrent/locks/Lock/TimedAcquireLeak.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/locks/Lock/TimedAcquireLeak.java	Tue May 22 21:50:45 2018 -0700
@@ -31,7 +31,6 @@
 
 import static java.util.concurrent.TimeUnit.MILLISECONDS;
 import static java.util.concurrent.TimeUnit.NANOSECONDS;
-import static java.util.concurrent.TimeUnit.SECONDS;
 
 import java.io.File;
 import java.io.FileOutputStream;
@@ -41,6 +40,7 @@
 import java.io.OutputStream;
 import java.io.PrintStream;
 import java.io.Reader;
+import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
 import java.util.concurrent.BlockingQueue;
 import java.util.concurrent.Callable;
@@ -125,16 +125,22 @@
 
     /** No guarantees, but effective in practice. */
     private static void forceFullGc() {
-        CountDownLatch finalizeDone = new CountDownLatch(1);
-        WeakReference<?> ref = new WeakReference<Object>(new Object() {
-            protected void finalize() { finalizeDone.countDown(); }});
+        long timeoutMillis = 1000L;
+        CountDownLatch finalized = new CountDownLatch(1);
+        ReferenceQueue<Object> queue = new ReferenceQueue<>();
+        WeakReference<Object> ref = new WeakReference<>(
+            new Object() { protected void finalize() { finalized.countDown(); }},
+            queue);
         try {
-            for (int i = 0; i < 10; i++) {
+            for (int tries = 3; tries--> 0; ) {
                 System.gc();
-                if (finalizeDone.await(1L, SECONDS) && ref.get() == null) {
+                if (finalized.await(timeoutMillis, MILLISECONDS)
+                    && queue.remove(timeoutMillis) != null
+                    && ref.get() == null) {
                     System.runFinalization(); // try to pick up stragglers
                     return;
                 }
+                timeoutMillis *= 4;
             }
         } catch (InterruptedException unexpected) {
             throw new AssertionError("unexpected InterruptedException");
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java	Tue May 22 21:50:45 2018 -0700
@@ -42,7 +42,6 @@
 import java.util.concurrent.CopyOnWriteArraySet;
 
 import junit.framework.Test;
-import junit.framework.TestSuite;
 
 public class CopyOnWriteArraySetTest extends JSR166TestCase {
     public static void main(String[] args) {
--- a/test/jdk/java/util/concurrent/tck/PriorityBlockingQueueTest.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/PriorityBlockingQueueTest.java	Tue May 22 21:50:45 2018 -0700
@@ -47,6 +47,7 @@
 import java.util.concurrent.Executors;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.PriorityBlockingQueue;
+import java.util.concurrent.ThreadLocalRandom;
 
 import junit.framework.Test;
 
@@ -60,7 +61,9 @@
 
     public static class InitialCapacity extends BlockingQueueTest {
         protected BlockingQueue emptyCollection() {
-            return new PriorityBlockingQueue(SIZE);
+            ThreadLocalRandom rnd = ThreadLocalRandom.current();
+            int initialCapacity = rnd.nextInt(1, SIZE);
+            return new PriorityBlockingQueue(initialCapacity);
         }
     }
 
@@ -71,19 +74,35 @@
     public static Test suite() {
         class Implementation implements CollectionImplementation {
             public Class<?> klazz() { return PriorityBlockingQueue.class; }
-            public Collection emptyCollection() { return new PriorityBlockingQueue(); }
+            public Collection emptyCollection() {
+                return new PriorityBlockingQueue();
+            }
             public Object makeElement(int i) { return i; }
             public boolean isConcurrent() { return true; }
             public boolean permitsNulls() { return false; }
         }
-        return newTestSuite(PriorityBlockingQueueTest.class,
-                            new Generic().testSuite(),
-                            new InitialCapacity().testSuite(),
-                            CollectionTest.testSuite(new Implementation()));
+        class ComparatorImplementation implements CollectionImplementation {
+            public Class<?> klazz() { return PriorityBlockingQueue.class; }
+            public Collection emptyCollection() {
+                ThreadLocalRandom rnd = ThreadLocalRandom.current();
+                int initialCapacity = rnd.nextInt(1, 10);
+                return new PriorityBlockingQueue(
+                    initialCapacity, new MyReverseComparator());
+            }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return false; }
+        }
+        return newTestSuite(
+            PriorityBlockingQueueTest.class,
+            new Generic().testSuite(),
+            new InitialCapacity().testSuite(),
+            CollectionTest.testSuite(new Implementation()),
+            CollectionTest.testSuite(new ComparatorImplementation()));
     }
 
     /** Sample Comparator */
-    static class MyReverseComparator implements Comparator {
+    static class MyReverseComparator implements Comparator, java.io.Serializable {
         public int compare(Object x, Object y) {
             return ((Comparable)y).compareTo(x);
         }
--- a/test/jdk/java/util/concurrent/tck/PriorityQueueTest.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/PriorityQueueTest.java	Tue May 22 21:50:45 2018 -0700
@@ -55,11 +55,22 @@
             public boolean isConcurrent() { return false; }
             public boolean permitsNulls() { return false; }
         }
-        return newTestSuite(PriorityQueueTest.class,
-                            CollectionTest.testSuite(new Implementation()));
+        class ComparatorImplementation implements CollectionImplementation {
+            public Class<?> klazz() { return PriorityQueue.class; }
+            public Collection emptyCollection() {
+                return new PriorityQueue(new MyReverseComparator());
+            }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNulls() { return false; }
+        }
+        return newTestSuite(
+            PriorityQueueTest.class,
+            CollectionTest.testSuite(new Implementation()),
+            CollectionTest.testSuite(new ComparatorImplementation()));
     }
 
-    static class MyReverseComparator implements Comparator {
+    static class MyReverseComparator implements Comparator, java.io.Serializable {
         public int compare(Object x, Object y) {
             return ((Comparable)y).compareTo(x);
         }
--- a/test/jdk/java/util/concurrent/tck/VectorTest.java	Tue May 22 21:46:51 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/VectorTest.java	Tue May 22 21:50:45 2018 -0700
@@ -32,7 +32,6 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
-import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;