# HG changeset patch
# User dl
# Date 1482358973 28800
# Node ID 8b9cacdadb2df8147da36b7f2874c02896a94e18
# Parent  5ea771a2666532263f83960e76c536a08e77ffeb
8171051: LinkedBlockingQueue spliterator needs to support node self-linking
Reviewed-by: martin, smarks, psandoz

diff -r 5ea771a26665 -r 8b9cacdadb2d jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java
--- a/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java	Wed Dec 21 11:54:42 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java	Wed Dec 21 14:22:53 2016 -0800
@@ -39,6 +39,7 @@
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
+import java.util.Objects;
 import java.util.Spliterator;
 import java.util.Spliterators;
 import java.util.concurrent.locks.Condition;
@@ -740,8 +741,7 @@
      * @throws IllegalArgumentException      {@inheritDoc}
      */
     public int drainTo(Collection<? super E> c, int maxElements) {
-        if (c == null)
-            throw new NullPointerException();
+        Objects.requireNonNull(c);
         if (c == this)
             throw new IllegalArgumentException();
         if (maxElements <= 0)
@@ -986,6 +986,16 @@
     }
 
     /**
+     * Used for any element traversal that is not entirely under lock.
+     * Such traversals must handle both:
+     * - dequeued nodes (p.next == p)
+     * - (possibly multiple) interior removed nodes (p.item == null)
+     */
+    Node<E> succ(Node<E> p) {
+        return (p == (p = p.next)) ? first : p;
+    }
+
+    /**
      * Returns an iterator over the elements in this deque in proper sequence.
      * The elements will be returned in order from first (head) to last (tail).
      *
@@ -1024,8 +1034,8 @@
         /**
          * nextItem holds on to item fields because once we claim that
          * an element exists in hasNext(), we must return item read
-         * under lock (in advance()) even if it was in the process of
-         * being removed when hasNext() was called.
+         * under lock even if it was in the process of being removed
+         * when hasNext() was called.
          */
         E nextItem;
 
@@ -1038,48 +1048,17 @@
         abstract Node<E> firstNode();
         abstract Node<E> nextNode(Node<E> n);
 
+        private Node<E> succ(Node<E> p) {
+            return (p == (p = nextNode(p))) ? firstNode() : p;
+        }
+
         AbstractItr() {
             // set to initial position
             final ReentrantLock lock = LinkedBlockingDeque.this.lock;
             lock.lock();
             try {
-                next = firstNode();
-                nextItem = (next == null) ? null : next.item;
-            } finally {
-                lock.unlock();
-            }
-        }
-
-        /**
-         * Returns the successor node of the given non-null, but
-         * possibly previously deleted, node.
-         */
-        private Node<E> succ(Node<E> n) {
-            // Chains of deleted nodes ending in null or self-links
-            // are possible if multiple interior nodes are removed.
-            for (;;) {
-                Node<E> s = nextNode(n);
-                if (s == null)
-                    return null;
-                else if (s.item != null)
-                    return s;
-                else if (s == n)
-                    return firstNode();
-                else
-                    n = s;
-            }
-        }
-
-        /**
-         * Advances next.
-         */
-        void advance() {
-            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
-            lock.lock();
-            try {
-                // assert next != null;
-                next = succ(next);
-                nextItem = (next == null) ? null : next.item;
+                if ((next = firstNode()) != null)
+                    nextItem = next.item;
             } finally {
                 lock.unlock();
             }
@@ -1090,14 +1069,65 @@
         }
 
         public E next() {
-            if (next == null)
+            Node<E> p;
+            if ((p = next) == null)
                 throw new NoSuchElementException();
-            lastRet = next;
+            lastRet = p;
             E x = nextItem;
-            advance();
+            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+            lock.lock();
+            try {
+                E e = null;
+                for (p = nextNode(p); p != null && (e = p.item) == null; )
+                    p = succ(p);
+                next = p;
+                nextItem = e;
+            } finally {
+                lock.unlock();
+            }
             return x;
         }
 
+        public void forEachRemaining(Consumer<? super E> action) {
+            // A variant of forEachFrom
+            Objects.requireNonNull(action);
+            Node<E> p;
+            if ((p = next) == null) return;
+            lastRet = p;
+            next = null;
+            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+            final int batchSize = 32;
+            Object[] es = null;
+            int n, len = 1;
+            do {
+                lock.lock();
+                try {
+                    if (es == null) {
+                        p = nextNode(p);
+                        for (Node<E> q = p; q != null; q = succ(q))
+                            if (q.item != null && ++len == batchSize)
+                                break;
+                        es = new Object[len];
+                        es[0] = nextItem;
+                        nextItem = null;
+                        n = 1;
+                    } else
+                        n = 0;
+                    for (; p != null && n < len; p = succ(p))
+                        if ((es[n] = p.item) != null) {
+                            lastRet = p;
+                            n++;
+                        }
+                } finally {
+                    lock.unlock();
+                }
+                for (int i = 0; i < n; i++) {
+                    @SuppressWarnings("unchecked") E e = (E) es[i];
+                    action.accept(e);
+                }
+            } while (n > 0 && p != null);
+        }
+
         public void remove() {
             Node<E> n = lastRet;
             if (n == null)
@@ -1116,25 +1146,30 @@
 
     /** Forward iterator */
     private class Itr extends AbstractItr {
+        Itr() {}                        // prevent access constructor creation
         Node<E> firstNode() { return first; }
         Node<E> nextNode(Node<E> n) { return n.next; }
     }
 
     /** Descending iterator */
     private class DescendingItr extends AbstractItr {
+        DescendingItr() {}              // prevent access constructor creation
         Node<E> firstNode() { return last; }
         Node<E> nextNode(Node<E> n) { return n.prev; }
     }
 
-    /** A customized variant of Spliterators.IteratorSpliterator */
+    /**
+     * A customized variant of Spliterators.IteratorSpliterator.
+     * Keep this class in sync with (very similar) LBQSpliterator.
+     */
     private final class LBDSpliterator implements Spliterator<E> {
         static final int MAX_BATCH = 1 << 25;  // max batch array size;
         Node<E> current;    // current node; null until initialized
         int batch;          // batch size for splits
         boolean exhausted;  // true when no more nodes
-        long est;           // size estimate
+        long est = size();  // size estimate
 
-        LBDSpliterator() { est = size(); }
+        LBDSpliterator() {}
 
         public long estimateSize() { return est; }
 
@@ -1143,8 +1178,7 @@
             int b = batch;
             int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
             if (!exhausted &&
-                (((h = current) != null && h != h.next)
-                 || (h = first) != null)
+                ((h = current) != null || (h = first) != null)
                 && h.next != null) {
                 Object[] a = new Object[n];
                 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
@@ -1152,10 +1186,10 @@
                 Node<E> p = current;
                 lock.lock();
                 try {
-                    if (((p != null && p != p.next) || (p = first) != null)
-                        && p.item != null)
-                        for (; p != null && i < n; p = p.next)
-                            a[i++] = p.item;
+                    if (p != null || (p = first) != null)
+                        for (; p != null && i < n; p = succ(p))
+                            if ((a[i] = p.item) != null)
+                                i++;
                 } finally {
                     lock.unlock();
                 }
@@ -1176,51 +1210,39 @@
             return null;
         }
 
-        public void forEachRemaining(Consumer<? super E> action) {
-            if (action == null) throw new NullPointerException();
-            if (exhausted)
-                return;
-            exhausted = true;
-            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
-            Node<E> p = current;
-            current = null;
-            do {
+        public boolean tryAdvance(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            if (!exhausted) {
                 E e = null;
+                final ReentrantLock lock = LinkedBlockingDeque.this.lock;
                 lock.lock();
                 try {
-                    if ((p != null && p != p.next) || (p = first) != null) {
-                        e = p.item;
-                        p = p.next;
-                    }
+                    Node<E> p;
+                    if ((p = current) != null || (p = first) != null)
+                        do {
+                            e = p.item;
+                            p = succ(p);
+                        } while (e == null && p != null);
+                    exhausted = ((current = p) == null);
                 } finally {
                     lock.unlock();
                 }
-                if (e != null)
+                if (e != null) {
                     action.accept(e);
-            } while (p != null);
+                    return true;
+                }
+            }
+            return false;
         }
 
-        public boolean tryAdvance(Consumer<? super E> action) {
-            if (action == null) throw new NullPointerException();
-            if (exhausted)
-                return false;
-            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
-            Node<E> p = current;
-            E e = null;
-            lock.lock();
-            try {
-                if ((p != null && p != p.next) || (p = first) != null) {
-                    e = p.item;
-                    p = p.next;
-                }
-            } finally {
-                lock.unlock();
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            if (!exhausted) {
+                exhausted = true;
+                Node<E> p = current;
+                current = null;
+                forEachFrom(action, p);
             }
-            exhausted = ((current = p) == null);
-            if (e == null)
-                return false;
-            action.accept(e);
-            return true;
         }
 
         public int characteristics() {
@@ -1251,6 +1273,48 @@
     }
 
     /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        forEachFrom(action, null);
+    }
+
+    /**
+     * Runs action on each element found during a traversal starting at p.
+     * If p is null, traversal starts at head.
+     */
+    void forEachFrom(Consumer<? super E> action, Node<E> p) {
+        // Extract batches of elements while holding the lock; then
+        // run the action on the elements while not
+        final ReentrantLock lock = this.lock;
+        final int batchSize = 32;       // max number of elements per batch
+        Object[] es = null;             // container for batch of elements
+        int n, len = 0;
+        do {
+            lock.lock();
+            try {
+                if (es == null) {
+                    if (p == null) p = first;
+                    for (Node<E> q = p; q != null; q = succ(q))
+                        if (q.item != null && ++len == batchSize)
+                            break;
+                    es = new Object[len];
+                }
+                for (n = 0; p != null && n < len; p = succ(p))
+                    if ((es[n] = p.item) != null)
+                        n++;
+            } finally {
+                lock.unlock();
+            }
+            for (int i = 0; i < n; i++) {
+                @SuppressWarnings("unchecked") E e = (E) es[i];
+                action.accept(e);
+            }
+        } while (n > 0 && p != null);
+    }
+
+    /**
      * Saves this deque to a stream (that is, serializes it).
      *
      * @param s the stream
@@ -1290,8 +1354,7 @@
         last = null;
         // Read in all elements and place in queue
         for (;;) {
-            @SuppressWarnings("unchecked")
-            E item = (E)s.readObject();
+            @SuppressWarnings("unchecked") E item = (E)s.readObject();
             if (item == null)
                 break;
             add(item);
diff -r 5ea771a26665 -r 8b9cacdadb2d jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingQueue.java
--- a/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingQueue.java	Wed Dec 21 11:54:42 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingQueue.java	Wed Dec 21 14:22:53 2016 -0800
@@ -39,6 +39,7 @@
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
+import java.util.Objects;
 import java.util.Spliterator;
 import java.util.Spliterators;
 import java.util.concurrent.atomic.AtomicInteger;
@@ -234,14 +235,6 @@
         putLock.unlock();
     }
 
-//     /**
-//      * Tells whether both locks are held by current thread.
-//      */
-//     boolean isFullyLocked() {
-//         return (putLock.isHeldByCurrentThread() &&
-//                 takeLock.isHeldByCurrentThread());
-//     }
-
     /**
      * Creates a {@code LinkedBlockingQueue} with a capacity of
      * {@link Integer#MAX_VALUE}.
@@ -517,7 +510,8 @@
      * Unlinks interior Node p with predecessor trail.
      */
     void unlink(Node<E> p, Node<E> trail) {
-        // assert isFullyLocked();
+        // assert putLock.isHeldByCurrentThread();
+        // assert takeLock.isHeldByCurrentThread();
         // p.next is not changed, to allow iterators that are
         // traversing p to maintain their weak-consistency guarantee.
         p.item = null;
@@ -701,8 +695,7 @@
      * @throws IllegalArgumentException      {@inheritDoc}
      */
     public int drainTo(Collection<? super E> c, int maxElements) {
-        if (c == null)
-            throw new NullPointerException();
+        Objects.requireNonNull(c);
         if (c == this)
             throw new IllegalArgumentException();
         if (maxElements <= 0)
@@ -741,6 +734,16 @@
     }
 
     /**
+     * Used for any element traversal that is not entirely under lock.
+     * Such traversals must handle both:
+     * - dequeued nodes (p.next == p)
+     * - (possibly multiple) interior removed nodes (p.item == null)
+     */
+    Node<E> succ(Node<E> p) {
+        return (p == (p = p.next)) ? head.next : p;
+    }
+
+    /**
      * Returns an iterator over the elements in this queue in proper sequence.
      * The elements will be returned in order from first (head) to last (tail).
      *
@@ -760,48 +763,80 @@
          * still have it to return even if lost race with a take etc.
          */
 
-        private Node<E> current;
+        private Node<E> next;
+        private E nextItem;
         private Node<E> lastRet;
-        private E currentElement;
 
         Itr() {
             fullyLock();
             try {
-                current = head.next;
-                if (current != null)
-                    currentElement = current.item;
+                if ((next = head.next) != null)
+                    nextItem = next.item;
             } finally {
                 fullyUnlock();
             }
         }
 
         public boolean hasNext() {
-            return current != null;
+            return next != null;
         }
 
         public E next() {
+            Node<E> p;
+            if ((p = next) == null)
+                throw new NoSuchElementException();
+            lastRet = p;
+            E x = nextItem;
             fullyLock();
             try {
-                if (current == null)
-                    throw new NoSuchElementException();
-                lastRet = current;
-                E item = null;
-                // Unlike other traversal methods, iterators must handle both:
-                // - dequeued nodes (p.next == p)
-                // - (possibly multiple) interior removed nodes (p.item == null)
-                for (Node<E> p = current, q;; p = q) {
-                    if ((q = p.next) == p)
-                        q = head.next;
-                    if (q == null || (item = q.item) != null) {
-                        current = q;
-                        E x = currentElement;
-                        currentElement = item;
-                        return x;
-                    }
-                }
+                E e = null;
+                for (p = p.next; p != null && (e = p.item) == null; )
+                    p = succ(p);
+                next = p;
+                nextItem = e;
             } finally {
                 fullyUnlock();
             }
+            return x;
+        }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            // A variant of forEachFrom
+            Objects.requireNonNull(action);
+            Node<E> p;
+            if ((p = next) == null) return;
+            lastRet = p;
+            next = null;
+            final int batchSize = 32;
+            Object[] es = null;
+            int n, len = 1;
+            do {
+                fullyLock();
+                try {
+                    if (es == null) {
+                        p = p.next;
+                        for (Node<E> q = p; q != null; q = succ(q))
+                            if (q.item != null && ++len == batchSize)
+                                break;
+                        es = new Object[len];
+                        es[0] = nextItem;
+                        nextItem = null;
+                        n = 1;
+                    } else
+                        n = 0;
+                    for (; p != null && n < len; p = succ(p))
+                        if ((es[n] = p.item) != null) {
+                            lastRet = p;
+                            n++;
+                        }
+                } finally {
+                    fullyUnlock();
+                }
+                for (int i = 0; i < n; i++) {
+                    @SuppressWarnings("unchecked") E e = (E) es[i];
+                    action.accept(e);
+                }
+            } while (n > 0 && p != null);
         }
 
         public void remove() {
@@ -825,42 +860,39 @@
         }
     }
 
-    /** A customized variant of Spliterators.IteratorSpliterator */
-    static final class LBQSpliterator<E> implements Spliterator<E> {
+    /**
+     * A customized variant of Spliterators.IteratorSpliterator.
+     * Keep this class in sync with (very similar) LBDSpliterator.
+     */
+    private final class LBQSpliterator implements Spliterator<E> {
         static final int MAX_BATCH = 1 << 25;  // max batch array size;
-        final LinkedBlockingQueue<E> queue;
         Node<E> current;    // current node; null until initialized
         int batch;          // batch size for splits
         boolean exhausted;  // true when no more nodes
-        long est;           // size estimate
-        LBQSpliterator(LinkedBlockingQueue<E> queue) {
-            this.queue = queue;
-            this.est = queue.size();
-        }
+        long est = size();  // size estimate
+
+        LBQSpliterator() {}
 
         public long estimateSize() { return est; }
 
         public Spliterator<E> trySplit() {
             Node<E> h;
-            final LinkedBlockingQueue<E> q = this.queue;
             int b = batch;
             int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
             if (!exhausted &&
-                ((h = current) != null || (h = q.head.next) != null) &&
-                h.next != null) {
+                ((h = current) != null || (h = head.next) != null)
+                && h.next != null) {
                 Object[] a = new Object[n];
                 int i = 0;
                 Node<E> p = current;
-                q.fullyLock();
+                fullyLock();
                 try {
-                    if (p != null || (p = q.head.next) != null) {
-                        do {
+                    if (p != null || (p = head.next) != null)
+                        for (; p != null && i < n; p = succ(p))
                             if ((a[i] = p.item) != null)
-                                ++i;
-                        } while ((p = p.next) != null && i < n);
-                    }
+                                i++;
                 } finally {
-                    q.fullyUnlock();
+                    fullyUnlock();
                 }
                 if ((current = p) == null) {
                     est = 0L;
@@ -879,53 +911,22 @@
             return null;
         }
 
-        public void forEachRemaining(Consumer<? super E> action) {
-            if (action == null) throw new NullPointerException();
-            final LinkedBlockingQueue<E> q = this.queue;
-            if (!exhausted) {
-                exhausted = true;
-                Node<E> p = current;
-                do {
-                    E e = null;
-                    q.fullyLock();
-                    try {
-                        if (p == null)
-                            p = q.head.next;
-                        while (p != null) {
-                            e = p.item;
-                            p = p.next;
-                            if (e != null)
-                                break;
-                        }
-                    } finally {
-                        q.fullyUnlock();
-                    }
-                    if (e != null)
-                        action.accept(e);
-                } while (p != null);
-            }
-        }
-
         public boolean tryAdvance(Consumer<? super E> action) {
-            if (action == null) throw new NullPointerException();
-            final LinkedBlockingQueue<E> q = this.queue;
+            Objects.requireNonNull(action);
             if (!exhausted) {
                 E e = null;
-                q.fullyLock();
+                fullyLock();
                 try {
-                    if (current == null)
-                        current = q.head.next;
-                    while (current != null) {
-                        e = current.item;
-                        current = current.next;
-                        if (e != null)
-                            break;
-                    }
+                    Node<E> p;
+                    if ((p = current) != null || (p = head.next) != null)
+                        do {
+                            e = p.item;
+                            p = succ(p);
+                        } while (e == null && p != null);
+                    exhausted = ((current = p) == null);
                 } finally {
-                    q.fullyUnlock();
+                    fullyUnlock();
                 }
-                if (current == null)
-                    exhausted = true;
                 if (e != null) {
                     action.accept(e);
                     return true;
@@ -934,9 +935,20 @@
             return false;
         }
 
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            if (!exhausted) {
+                exhausted = true;
+                Node<E> p = current;
+                current = null;
+                forEachFrom(action, p);
+            }
+        }
+
         public int characteristics() {
-            return Spliterator.ORDERED | Spliterator.NONNULL |
-                Spliterator.CONCURRENT;
+            return (Spliterator.ORDERED |
+                    Spliterator.NONNULL |
+                    Spliterator.CONCURRENT);
         }
     }
 
@@ -957,7 +969,48 @@
      * @since 1.8
      */
     public Spliterator<E> spliterator() {
-        return new LBQSpliterator<E>(this);
+        return new LBQSpliterator();
+    }
+
+    /**
+     * @throws NullPointerException {@inheritDoc}
+     */
+    public void forEach(Consumer<? super E> action) {
+        Objects.requireNonNull(action);
+        forEachFrom(action, null);
+    }
+
+    /**
+     * Runs action on each element found during a traversal starting at p.
+     * If p is null, traversal starts at head.
+     */
+    void forEachFrom(Consumer<? super E> action, Node<E> p) {
+        // Extract batches of elements while holding the lock; then
+        // run the action on the elements while not
+        final int batchSize = 32;       // max number of elements per batch
+        Object[] es = null;             // container for batch of elements
+        int n, len = 0;
+        do {
+            fullyLock();
+            try {
+                if (es == null) {
+                    if (p == null) p = head.next;
+                    for (Node<E> q = p; q != null; q = succ(q))
+                        if (q.item != null && ++len == batchSize)
+                            break;
+                    es = new Object[len];
+                }
+                for (n = 0; p != null && n < len; p = succ(p))
+                    if ((es[n] = p.item) != null)
+                        n++;
+            } finally {
+                fullyUnlock();
+            }
+            for (int i = 0; i < n; i++) {
+                @SuppressWarnings("unchecked") E e = (E) es[i];
+                action.accept(e);
+            }
+        } while (n > 0 && p != null);
     }
 
     /**
diff -r 5ea771a26665 -r 8b9cacdadb2d jdk/test/java/util/concurrent/tck/Collection8Test.java
--- a/jdk/test/java/util/concurrent/tck/Collection8Test.java	Wed Dec 21 11:54:42 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/Collection8Test.java	Wed Dec 21 14:22:53 2016 -0800
@@ -39,6 +39,7 @@
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.ConcurrentModificationException;
 import java.util.Deque;
 import java.util.HashSet;
 import java.util.Iterator;
@@ -369,9 +370,112 @@
     }
 
     /**
+     * All elements removed in the middle of CONCURRENT traversal.
+     */
+    public void testElementRemovalDuringTraversal() {
+        Collection c = impl.emptyCollection();
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int n = rnd.nextInt(6);
+        ArrayList copy = new ArrayList();
+        for (int i = 0; i < n; i++) {
+            Object x = impl.makeElement(i);
+            copy.add(x);
+            c.add(x);
+        }
+        ArrayList iterated = new ArrayList();
+        ArrayList spliterated = new ArrayList();
+        Spliterator s = c.spliterator();
+        Iterator it = c.iterator();
+        for (int i = rnd.nextInt(n + 1); --i >= 0; ) {
+            assertTrue(s.tryAdvance(spliterated::add));
+            if (rnd.nextBoolean()) assertTrue(it.hasNext());
+            iterated.add(it.next());
+        }
+        Consumer alwaysThrows = e -> { throw new AssertionError(); };
+        if (s.hasCharacteristics(Spliterator.CONCURRENT)) {
+            c.clear();          // TODO: many more removal methods
+            if (testImplementationDetails
+                && !(c instanceof java.util.concurrent.ArrayBlockingQueue)) {
+                if (rnd.nextBoolean())
+                    assertFalse(s.tryAdvance(alwaysThrows));
+                else
+                    s.forEachRemaining(alwaysThrows);
+            }
+            if (it.hasNext()) iterated.add(it.next());
+            if (rnd.nextBoolean()) assertIteratorExhausted(it);
+        }
+        assertTrue(copy.containsAll(iterated));
+        assertTrue(copy.containsAll(spliterated));
+    }
+
+    /**
+     * Some elements randomly disappear in the middle of traversal.
+     */
+    public void testRandomElementRemovalDuringTraversal() {
+        Collection c = impl.emptyCollection();
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int n = rnd.nextInt(6);
+        ArrayList copy = new ArrayList();
+        for (int i = 0; i < n; i++) {
+            Object x = impl.makeElement(i);
+            copy.add(x);
+            c.add(x);
+        }
+        ArrayList iterated = new ArrayList();
+        ArrayList spliterated = new ArrayList();
+        ArrayList removed = new ArrayList();
+        Spliterator s = c.spliterator();
+        Iterator it = c.iterator();
+        if (! (s.hasCharacteristics(Spliterator.CONCURRENT) ||
+               s.hasCharacteristics(Spliterator.IMMUTABLE)))
+            return;
+        for (int i = rnd.nextInt(n + 1); --i >= 0; ) {
+            assertTrue(s.tryAdvance(e -> {}));
+            if (rnd.nextBoolean()) assertTrue(it.hasNext());
+            it.next();
+        }
+        Consumer alwaysThrows = e -> { throw new AssertionError(); };
+        // TODO: many more removal methods
+        if (rnd.nextBoolean()) {
+            for (Iterator z = c.iterator(); z.hasNext(); ) {
+                Object e = z.next();
+                if (rnd.nextBoolean()) {
+                    try {
+                        z.remove();
+                    } catch (UnsupportedOperationException ok) { return; }
+                    removed.add(e);
+                }
+            }
+        } else {
+            Predicate randomlyRemove = e -> {
+                if (rnd.nextBoolean()) { removed.add(e); return true; }
+                else return false;
+            };
+            c.removeIf(randomlyRemove);
+        }
+        s.forEachRemaining(spliterated::add);
+        while (it.hasNext())
+            iterated.add(it.next());
+        assertTrue(copy.containsAll(iterated));
+        assertTrue(copy.containsAll(spliterated));
+        assertTrue(copy.containsAll(removed));
+        if (s.hasCharacteristics(Spliterator.CONCURRENT)) {
+            ArrayList iteratedAndRemoved = new ArrayList(iterated);
+            ArrayList spliteratedAndRemoved = new ArrayList(spliterated);
+            iteratedAndRemoved.retainAll(removed);
+            spliteratedAndRemoved.retainAll(removed);
+            assertTrue(iteratedAndRemoved.size() <= 1);
+            assertTrue(spliteratedAndRemoved.size() <= 1);
+            if (testImplementationDetails
+                && !(c instanceof java.util.concurrent.ArrayBlockingQueue))
+                assertTrue(spliteratedAndRemoved.isEmpty());
+        }
+    }
+
+    /**
      * Various ways of traversing a collection yield same elements
      */
-    public void testIteratorEquivalence() {
+    public void testTraversalEquivalence() {
         Collection c = impl.emptyCollection();
         ThreadLocalRandom rnd = ThreadLocalRandom.current();
         int n = rnd.nextInt(6);
@@ -439,6 +543,43 @@
     }
 
     /**
+     * Iterator.forEachRemaining has same behavior as Iterator's
+     * default implementation.
+     */
+    public void testForEachRemainingConsistentWithDefaultImplementation() {
+        Collection c = impl.emptyCollection();
+        if (!testImplementationDetails
+            || c.getClass() == java.util.LinkedList.class)
+            return;
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int n = 1 + rnd.nextInt(3);
+        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+        ArrayList iterated = new ArrayList();
+        ArrayList iteratedForEachRemaining = new ArrayList();
+        Iterator it1 = c.iterator();
+        Iterator it2 = c.iterator();
+        assertTrue(it1.hasNext());
+        assertTrue(it2.hasNext());
+        c.clear();
+        Object r1, r2;
+        try {
+            while (it1.hasNext()) iterated.add(it1.next());
+            r1 = iterated;
+        } catch (ConcurrentModificationException ex) {
+            r1 = ConcurrentModificationException.class;
+            assertFalse(impl.isConcurrent());
+        }
+        try {
+            it2.forEachRemaining(iteratedForEachRemaining::add);
+            r2 = iteratedForEachRemaining;
+        } catch (ConcurrentModificationException ex) {
+            r2 = ConcurrentModificationException.class;
+            assertFalse(impl.isConcurrent());
+        }
+        assertEquals(r1, r2);
+    }
+
+    /**
      * Calling Iterator#remove() after Iterator#forEachRemaining
      * should (maybe) remove last element
      */
@@ -577,6 +718,41 @@
         assertTrue(found.isEmpty());
     }
 
+    /** TODO: promote to a common utility */
+    static <T> T chooseOne(T ... ts) {
+        return ts[ThreadLocalRandom.current().nextInt(ts.length)];
+    }
+
+    /** TODO: more random adders and removers */
+    static <E> Runnable adderRemover(Collection<E> c, E e) {
+        return chooseOne(
+            () -> {
+                assertTrue(c.add(e));
+                assertTrue(c.contains(e));
+                assertTrue(c.remove(e));
+                assertFalse(c.contains(e));
+            },
+            () -> {
+                assertTrue(c.add(e));
+                assertTrue(c.contains(e));
+                assertTrue(c.removeIf(x -> x == e));
+                assertFalse(c.contains(e));
+            },
+            () -> {
+                assertTrue(c.add(e));
+                assertTrue(c.contains(e));
+                for (Iterator it = c.iterator();; )
+                    if (it.next() == e) {
+                        try { it.remove(); }
+                        catch (UnsupportedOperationException ok) {
+                            c.remove(e);
+                        }
+                        break;
+                    }
+                assertFalse(c.contains(e));
+            });
+    }
+
     /**
      * Motley crew of threads concurrently randomly hammer the collection.
      */
@@ -616,17 +792,20 @@
             () -> checkArraySanity.accept(c.toArray()),
             () -> checkArraySanity.accept(c.toArray(emptyArray)),
             () -> {
-                assertTrue(c.add(one));
-                assertTrue(c.contains(one));
-                assertTrue(c.remove(one));
-                assertFalse(c.contains(one));
-            },
-            () -> {
-                assertTrue(c.add(two));
-                assertTrue(c.contains(two));
-                assertTrue(c.remove(two));
-                assertFalse(c.contains(two));
-            },
+                Object[] a = new Object[5];
+                Object three = impl.makeElement(3);
+                Arrays.fill(a, 0, a.length, three);
+                Object[] x = c.toArray(a);
+                if (x == a)
+                    for (int i = 0; i < a.length && a[i] != null; i++)
+                        checkSanity.accept(a[i]);
+                    // A careful reading of the spec does not support:
+                    // for (i++; i < a.length; i++) assertSame(three, a[i]);
+                else
+                    checkArraySanity.accept(x);
+                },
+            adderRemover(c, one),
+            adderRemover(c, two),
         };
         final List<Runnable> tasks =
             Arrays.stream(frobbers)
@@ -684,6 +863,22 @@
         }
     }
 
+    /**
+     * Spliterator.getComparator throws IllegalStateException iff the
+     * spliterator does not report SORTED.
+     */
+    public void testGetComparator_IllegalStateException() {
+        Collection c = impl.emptyCollection();
+        Spliterator s = c.spliterator();
+        boolean reportsSorted = s.hasCharacteristics(Spliterator.SORTED);
+        try {
+            s.getComparator();
+            assertTrue(reportsSorted);
+        } catch (IllegalStateException ex) {
+            assertFalse(reportsSorted);
+        }
+    }
+
 //     public void testCollection8DebugFail() {
 //         fail(impl.klazz().getSimpleName());
 //     }
diff -r 5ea771a26665 -r 8b9cacdadb2d jdk/test/java/util/concurrent/tck/LinkedBlockingDeque8Test.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/LinkedBlockingDeque8Test.java	Wed Dec 21 14:22:53 2016 -0800
@@ -0,0 +1,76 @@
+/*
+ * 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 Doug Lea and 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/
+ */
+
+import java.util.concurrent.LinkedBlockingDeque;
+import java.util.Spliterator;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class LinkedBlockingDeque8Test extends JSR166TestCase {
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        return newTestSuite(LinkedBlockingDeque8Test.class);
+    }
+
+    /**
+     * Spliterator.getComparator always throws IllegalStateException
+     */
+    public void testSpliterator_getComparator() {
+        assertThrows(IllegalStateException.class,
+                     () -> new LinkedBlockingDeque().spliterator().getComparator());
+    }
+
+    /**
+     * Spliterator characteristics are as advertised
+     */
+    public void testSpliterator_characteristics() {
+        LinkedBlockingDeque q = new LinkedBlockingDeque();
+        Spliterator s = q.spliterator();
+        int characteristics = s.characteristics();
+        int required = Spliterator.CONCURRENT
+            | Spliterator.NONNULL
+            | Spliterator.ORDERED;
+        assertEquals(required, characteristics & required);
+        assertTrue(s.hasCharacteristics(required));
+        assertEquals(0, characteristics
+                     & (Spliterator.DISTINCT
+                        | Spliterator.IMMUTABLE
+                        | Spliterator.SORTED));
+    }
+
+}
diff -r 5ea771a26665 -r 8b9cacdadb2d jdk/test/java/util/concurrent/tck/LinkedBlockingQueue8Test.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/LinkedBlockingQueue8Test.java	Wed Dec 21 14:22:53 2016 -0800
@@ -0,0 +1,76 @@
+/*
+ * 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 Doug Lea and 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/
+ */
+
+import java.util.concurrent.LinkedBlockingQueue;
+import java.util.Spliterator;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class LinkedBlockingQueue8Test extends JSR166TestCase {
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        return newTestSuite(LinkedBlockingQueue8Test.class);
+    }
+
+    /**
+     * Spliterator.getComparator always throws IllegalStateException
+     */
+    public void testSpliterator_getComparator() {
+        assertThrows(IllegalStateException.class,
+                     () -> new LinkedBlockingQueue().spliterator().getComparator());
+    }
+
+    /**
+     * Spliterator characteristics are as advertised
+     */
+    public void testSpliterator_characteristics() {
+        LinkedBlockingQueue q = new LinkedBlockingQueue();
+        Spliterator s = q.spliterator();
+        int characteristics = s.characteristics();
+        int required = Spliterator.CONCURRENT
+            | Spliterator.NONNULL
+            | Spliterator.ORDERED;
+        assertEquals(required, characteristics & required);
+        assertTrue(s.hasCharacteristics(required));
+        assertEquals(0, characteristics
+                     & (Spliterator.DISTINCT
+                        | Spliterator.IMMUTABLE
+                        | Spliterator.SORTED));
+    }
+
+}