8171051: LinkedBlockingQueue spliterator needs to support node self-linking
Reviewed-by: martin, smarks, psandoz
--- 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);
--- 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);
}
/**
--- 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());
// }
--- /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));
+ }
+
+}
--- /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));
+ }
+
+}