8143577: optimize ArrayList.removeIf
8169679: ArrayList.subList().iterator().forEachRemaining() off-by-one-error
8167202: ArrayDeque improvements
8164793: new ArrayDeque(2**N) allocates backing array of size 2**(N+1)
8169739: LinkedBlockingDeque spliterator needs to support node self-linking
8169738: CopyOnWriteArrayList subList needs more synchronization
Reviewed-by: martin, smarks, psandoz, forax
--- a/jdk/src/java.base/share/classes/java/util/ArrayDeque.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/ArrayDeque.java Mon Nov 28 23:36:11 2016 -0800
@@ -36,6 +36,8 @@
import java.io.Serializable;
import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
/**
* Resizable-array implementation of the {@link Deque} interface. Array
@@ -87,81 +89,89 @@
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
+ /*
+ * VMs excel at optimizing simple array loops where indices are
+ * incrementing or decrementing over a valid slice, e.g.
+ *
+ * for (int i = start; i < end; i++) ... elements[i]
+ *
+ * Because in a circular array, elements are in general stored in
+ * two disjoint such slices, we help the VM by writing unusual
+ * nested loops for all traversals over the elements. Having only
+ * one hot inner loop body instead of two or three eases human
+ * maintenance and encourages VM loop inlining into the caller.
+ */
+
/**
* The array in which the elements of the deque are stored.
- * The capacity of the deque is the length of this array, which is
- * always a power of two. The array is never allowed to become
- * full, except transiently within an addX method where it is
- * resized (see doubleCapacity) immediately upon becoming full,
- * thus avoiding head and tail wrapping around to equal each
- * other. We also guarantee that all array cells not holding
- * deque elements are always null.
+ * All array cells not holding deque elements are always null.
+ * The array always has at least one null slot (at tail).
*/
- transient Object[] elements; // non-private to simplify nested class access
+ transient Object[] elements;
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
- * arbitrary number equal to tail if the deque is empty.
+ * arbitrary number 0 <= head < elements.length equal to tail if
+ * the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
- * of the deque (via addLast(E), add(E), or push(E)).
+ * of the deque (via addLast(E), add(E), or push(E));
+ * elements[tail] is always null.
*/
transient int tail;
/**
- * The minimum capacity that we'll use for a newly created deque.
- * Must be a power of 2.
+ * The maximum size of array to allocate.
+ * Some VMs reserve some header words in an array.
+ * Attempts to allocate larger arrays may result in
+ * OutOfMemoryError: Requested array size exceeds VM limit
*/
- private static final int MIN_INITIAL_CAPACITY = 8;
-
- // ****** Array allocation and resizing utilities ******
+ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
- * Allocates empty array to hold the given number of elements.
+ * Increases the capacity of this deque by at least the given amount.
*
- * @param numElements the number of elements to hold
+ * @param needed the required minimum extra capacity; must be positive
*/
- private void allocateElements(int numElements) {
- int initialCapacity = MIN_INITIAL_CAPACITY;
- // Find the best power of two to hold elements.
- // Tests "<=" because arrays aren't kept full.
- if (numElements >= initialCapacity) {
- initialCapacity = numElements;
- initialCapacity |= (initialCapacity >>> 1);
- initialCapacity |= (initialCapacity >>> 2);
- initialCapacity |= (initialCapacity >>> 4);
- initialCapacity |= (initialCapacity >>> 8);
- initialCapacity |= (initialCapacity >>> 16);
- initialCapacity++;
-
- if (initialCapacity < 0) // Too many elements, must back off
- initialCapacity >>>= 1; // Good luck allocating 2^30 elements
+ private void grow(int needed) {
+ // overflow-conscious code
+ final int oldCapacity = elements.length;
+ int newCapacity;
+ // Double capacity if small; else grow by 50%
+ int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
+ if (jump < needed
+ || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
+ newCapacity = newCapacity(needed, jump);
+ elements = Arrays.copyOf(elements, newCapacity);
+ // Exceptionally, here tail == head needs to be disambiguated
+ if (tail < head || (tail == head && elements[head] != null)) {
+ // wrap around; slide first leg forward to end of array
+ int newSpace = newCapacity - oldCapacity;
+ System.arraycopy(elements, head,
+ elements, head + newSpace,
+ oldCapacity - head);
+ Arrays.fill(elements, head, head + newSpace, null);
+ head += newSpace;
}
- elements = new Object[initialCapacity];
}
- /**
- * Doubles the capacity of this deque. Call only when full, i.e.,
- * when head and tail have wrapped around to become equal.
- */
- private void doubleCapacity() {
- assert head == tail;
- int p = head;
- int n = elements.length;
- int r = n - p; // number of elements to the right of p
- int newCapacity = n << 1;
- if (newCapacity < 0)
- throw new IllegalStateException("Sorry, deque too big");
- Object[] a = new Object[newCapacity];
- System.arraycopy(elements, p, a, 0, r);
- System.arraycopy(elements, 0, a, r, p);
- elements = a;
- head = 0;
- tail = n;
+ /** Capacity calculation for edge conditions, especially overflow. */
+ private int newCapacity(int needed, int jump) {
+ final int oldCapacity = elements.length, minCapacity;
+ if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
+ if (minCapacity < 0)
+ throw new IllegalStateException("Sorry, deque too big");
+ return Integer.MAX_VALUE;
+ }
+ if (needed > jump)
+ return minCapacity;
+ return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
+ ? oldCapacity + jump
+ : MAX_ARRAY_SIZE;
}
/**
@@ -176,10 +186,13 @@
* Constructs an empty array deque with an initial capacity
* sufficient to hold the specified number of elements.
*
- * @param numElements lower bound on initial capacity of the deque
+ * @param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
- allocateElements(numElements);
+ elements =
+ new Object[(numElements < 1) ? 1 :
+ (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
+ numElements + 1];
}
/**
@@ -193,10 +206,71 @@
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection<? extends E> c) {
- allocateElements(c.size());
+ this(c.size());
addAll(c);
}
+ /**
+ * Increments i, mod modulus.
+ * Precondition and postcondition: 0 <= i < modulus.
+ */
+ static final int inc(int i, int modulus) {
+ if (++i >= modulus) i = 0;
+ return i;
+ }
+
+ /**
+ * Decrements i, mod modulus.
+ * Precondition and postcondition: 0 <= i < modulus.
+ */
+ static final int dec(int i, int modulus) {
+ if (--i < 0) i = modulus - 1;
+ return i;
+ }
+
+ /**
+ * Circularly adds the given distance to index i, mod modulus.
+ * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
+ * @return index 0 <= i < modulus
+ */
+ static final int add(int i, int distance, int modulus) {
+ if ((i += distance) - modulus >= 0) i -= modulus;
+ return i;
+ }
+
+ /**
+ * Subtracts j from i, mod modulus.
+ * Index i must be logically ahead of index j.
+ * Precondition: 0 <= i < modulus, 0 <= j < modulus.
+ * @return the "circular distance" from j to i; corner case i == j
+ * is diambiguated to "empty", returning 0.
+ */
+ static final int sub(int i, int j, int modulus) {
+ if ((i -= j) < 0) i += modulus;
+ return i;
+ }
+
+ /**
+ * Returns element at array index i.
+ * This is a slight abuse of generics, accepted by javac.
+ */
+ @SuppressWarnings("unchecked")
+ static final <E> E elementAt(Object[] es, int i) {
+ return (E) es[i];
+ }
+
+ /**
+ * A version of elementAt that checks for null elements.
+ * This check doesn't catch all possible comodifications,
+ * but does catch ones that corrupt traversal.
+ */
+ static final <E> E nonNullElementAt(Object[] es, int i) {
+ @SuppressWarnings("unchecked") E e = (E) es[i];
+ if (e == null)
+ throw new ConcurrentModificationException();
+ return e;
+ }
+
// The main insertion and extraction methods are addFirst,
// addLast, pollFirst, pollLast. The other methods are defined in
// terms of these.
@@ -210,9 +284,10 @@
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
- elements[head = (head - 1) & (elements.length - 1)] = e;
+ final Object[] es = elements;
+ es[head = dec(head, es.length)] = e;
if (head == tail)
- doubleCapacity();
+ grow(1);
}
/**
@@ -226,9 +301,29 @@
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
- elements[tail] = e;
- if ( (tail = (tail + 1) & (elements.length - 1)) == head)
- doubleCapacity();
+ final Object[] es = elements;
+ es[tail] = e;
+ if (head == (tail = inc(tail, es.length)))
+ grow(1);
+ }
+
+ /**
+ * Adds all of the elements in the specified collection at the end
+ * of this deque, as if by calling {@link #addLast} on each one,
+ * in the order that they are returned by the collection's
+ * iterator.
+ *
+ * @param c the elements to be inserted into this deque
+ * @return {@code true} if this deque changed as a result of the call
+ * @throws NullPointerException if the specified collection or any
+ * of its elements are null
+ */
+ public boolean addAll(Collection<? extends E> c) {
+ final int s, needed;
+ if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
+ grow(needed);
+ c.forEach(this::addLast);
+ return size() > s;
}
/**
@@ -259,78 +354,70 @@
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
- E x = pollFirst();
- if (x == null)
+ E e = pollFirst();
+ if (e == null)
throw new NoSuchElementException();
- return x;
+ return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeLast() {
- E x = pollLast();
- if (x == null)
+ E e = pollLast();
+ if (e == null)
throw new NoSuchElementException();
- return x;
+ return e;
}
public E pollFirst() {
- final Object[] elements = this.elements;
- final int h = head;
- @SuppressWarnings("unchecked")
- E result = (E) elements[h];
- // Element is null if deque empty
- if (result != null) {
- elements[h] = null; // Must null out slot
- head = (h + 1) & (elements.length - 1);
+ final Object[] es;
+ final int h;
+ E e = elementAt(es = elements, h = head);
+ if (e != null) {
+ es[h] = null;
+ head = inc(h, es.length);
}
- return result;
+ return e;
}
public E pollLast() {
- final Object[] elements = this.elements;
- final int t = (tail - 1) & (elements.length - 1);
- @SuppressWarnings("unchecked")
- E result = (E) elements[t];
- if (result != null) {
- elements[t] = null;
- tail = t;
- }
- return result;
+ final Object[] es;
+ final int t;
+ E e = elementAt(es = elements, t = dec(tail, es.length));
+ if (e != null)
+ es[tail = t] = null;
+ return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getFirst() {
- @SuppressWarnings("unchecked")
- E result = (E) elements[head];
- if (result == null)
+ E e = elementAt(elements, head);
+ if (e == null)
throw new NoSuchElementException();
- return result;
+ return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
- @SuppressWarnings("unchecked")
- E result = (E) elements[(tail - 1) & (elements.length - 1)];
- if (result == null)
+ final Object[] es = elements;
+ E e = elementAt(es, dec(tail, es.length));
+ if (e == null)
throw new NoSuchElementException();
- return result;
+ return e;
}
- @SuppressWarnings("unchecked")
public E peekFirst() {
- // elements[head] is null if deque empty
- return (E) elements[head];
+ return elementAt(elements, head);
}
- @SuppressWarnings("unchecked")
public E peekLast() {
- return (E) elements[(tail - 1) & (elements.length - 1)];
+ final Object[] es;
+ return elementAt(es = elements, dec(tail, es.length));
}
/**
@@ -347,13 +434,15 @@
*/
public boolean removeFirstOccurrence(Object o) {
if (o != null) {
- int mask = elements.length - 1;
- int i = head;
- for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
- if (o.equals(x)) {
- delete(i);
- return true;
- }
+ final Object[] es = elements;
+ for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ if (o.equals(es[i])) {
+ delete(i);
+ return true;
+ }
+ if (to == end) break;
}
}
return false;
@@ -373,13 +462,15 @@
*/
public boolean removeLastOccurrence(Object o) {
if (o != null) {
- int mask = elements.length - 1;
- int i = (tail - 1) & mask;
- for (Object x; (x = elements[i]) != null; i = (i - 1) & mask) {
- if (o.equals(x)) {
- delete(i);
- return true;
- }
+ final Object[] es = elements;
+ for (int i = tail, end = head, to = (i >= end) ? end : 0;
+ ; i = es.length, to = end) {
+ for (i--; i > to - 1; i--)
+ if (o.equals(es[i])) {
+ delete(i);
+ return true;
+ }
+ if (to == end) break;
}
}
return false;
@@ -499,59 +590,47 @@
return removeFirst();
}
- private void checkInvariants() {
- assert elements[tail] == null;
- assert head == tail ? elements[head] == null :
- (elements[head] != null &&
- elements[(tail - 1) & (elements.length - 1)] != null);
- assert elements[(head - 1) & (elements.length - 1)] == null;
- }
-
/**
- * Removes the element at the specified position in the elements array,
- * adjusting head and tail as necessary. This can result in motion of
- * elements backwards or forwards in the array.
+ * Removes the element at the specified position in the elements array.
+ * This can result in forward or backwards motion of array elements.
+ * We optimize for least element motion.
*
* <p>This method is called delete rather than remove to emphasize
* that its semantics differ from those of {@link List#remove(int)}.
*
- * @return true if elements moved backwards
+ * @return true if elements near tail moved backwards
*/
boolean delete(int i) {
- checkInvariants();
- final Object[] elements = this.elements;
- final int mask = elements.length - 1;
- final int h = head;
- final int t = tail;
- final int front = (i - h) & mask;
- final int back = (t - i) & mask;
-
- // Invariant: head <= i < tail mod circularity
- if (front >= ((t - h) & mask))
- throw new ConcurrentModificationException();
-
- // Optimize for least element motion
+ final Object[] es = elements;
+ final int capacity = es.length;
+ final int h, t;
+ // number of elements before to-be-deleted elt
+ final int front = sub(i, h = head, capacity);
+ // number of elements after to-be-deleted elt
+ final int back = sub(t = tail, i, capacity) - 1;
if (front < back) {
+ // move front elements forwards
if (h <= i) {
- System.arraycopy(elements, h, elements, h + 1, front);
+ System.arraycopy(es, h, es, h + 1, front);
} else { // Wrap around
- System.arraycopy(elements, 0, elements, 1, i);
- elements[0] = elements[mask];
- System.arraycopy(elements, h, elements, h + 1, mask - h);
+ System.arraycopy(es, 0, es, 1, i);
+ es[0] = es[capacity - 1];
+ System.arraycopy(es, h, es, h + 1, front - (i + 1));
}
- elements[h] = null;
- head = (h + 1) & mask;
+ es[h] = null;
+ head = inc(h, capacity);
return false;
} else {
- if (i < t) { // Copy the null tail as well
- System.arraycopy(elements, i + 1, elements, i, back);
- tail = t - 1;
+ // move back elements backwards
+ tail = dec(t, capacity);
+ if (i <= tail) {
+ System.arraycopy(es, i + 1, es, i, back);
} else { // Wrap around
- System.arraycopy(elements, i + 1, elements, i, mask - i);
- elements[mask] = elements[0];
- System.arraycopy(elements, 1, elements, 0, t);
- tail = (t - 1) & mask;
+ System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
+ es[capacity - 1] = es[0];
+ System.arraycopy(es, 1, es, 0, t - 1);
}
+ es[tail] = null;
return true;
}
}
@@ -564,7 +643,7 @@
* @return the number of elements in this deque
*/
public int size() {
- return (tail - head) & (elements.length - 1);
+ return sub(tail, head, elements.length);
}
/**
@@ -593,101 +672,317 @@
}
private class DeqIterator implements Iterator<E> {
- /**
- * Index of element to be returned by subsequent call to next.
- */
- private int cursor = head;
+ /** Index of element to be returned by subsequent call to next. */
+ int cursor;
- /**
- * Tail recorded at construction (also in remove), to stop
- * iterator and also to check for comodification.
- */
- private int fence = tail;
+ /** Number of elements yet to be returned. */
+ int remaining = size();
/**
* Index of element returned by most recent call to next.
* Reset to -1 if element is deleted by a call to remove.
*/
- private int lastRet = -1;
+ int lastRet = -1;
- public boolean hasNext() {
- return cursor != fence;
+ DeqIterator() { cursor = head; }
+
+ public final boolean hasNext() {
+ return remaining > 0;
}
public E next() {
- if (cursor == fence)
+ if (remaining <= 0)
throw new NoSuchElementException();
- @SuppressWarnings("unchecked")
- E result = (E) elements[cursor];
- // This check doesn't catch all possible comodifications,
- // but does catch the ones that corrupt traversal
- if (tail != fence || result == null)
- throw new ConcurrentModificationException();
- lastRet = cursor;
- cursor = (cursor + 1) & (elements.length - 1);
- return result;
+ final Object[] es = elements;
+ E e = nonNullElementAt(es, cursor);
+ cursor = inc(lastRet = cursor, es.length);
+ remaining--;
+ return e;
}
- public void remove() {
+ void postDelete(boolean leftShifted) {
+ if (leftShifted)
+ cursor = dec(cursor, elements.length);
+ }
+
+ public final void remove() {
if (lastRet < 0)
throw new IllegalStateException();
- if (delete(lastRet)) { // if left-shifted, undo increment in next()
- cursor = (cursor - 1) & (elements.length - 1);
- fence = tail;
- }
+ postDelete(delete(lastRet));
lastRet = -1;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
- Object[] a = elements;
- int m = a.length - 1, f = fence, i = cursor;
- cursor = f;
- while (i != f) {
- @SuppressWarnings("unchecked") E e = (E)a[i];
- i = (i + 1) & m;
- if (e == null)
- throw new ConcurrentModificationException();
- action.accept(e);
+ int r;
+ if ((r = remaining) <= 0)
+ return;
+ remaining = 0;
+ final Object[] es = elements;
+ if (es[cursor] == null || sub(tail, cursor, es.length) != r)
+ throw new ConcurrentModificationException();
+ for (int i = cursor, end = tail, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ action.accept(elementAt(es, i));
+ if (to == end) {
+ if (end != tail)
+ throw new ConcurrentModificationException();
+ lastRet = dec(end, es.length);
+ break;
+ }
+ }
+ }
+ }
+
+ private class DescendingIterator extends DeqIterator {
+ DescendingIterator() { cursor = dec(tail, elements.length); }
+
+ public final E next() {
+ if (remaining <= 0)
+ throw new NoSuchElementException();
+ final Object[] es = elements;
+ E e = nonNullElementAt(es, cursor);
+ cursor = dec(lastRet = cursor, es.length);
+ remaining--;
+ return e;
+ }
+
+ void postDelete(boolean leftShifted) {
+ if (!leftShifted)
+ cursor = inc(cursor, elements.length);
+ }
+
+ public final void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ int r;
+ if ((r = remaining) <= 0)
+ return;
+ remaining = 0;
+ final Object[] es = elements;
+ if (es[cursor] == null || sub(cursor, head, es.length) + 1 != r)
+ throw new ConcurrentModificationException();
+ for (int i = cursor, end = head, to = (i >= end) ? end : 0;
+ ; i = es.length - 1, to = end) {
+ // hotspot generates faster code than for: i >= to !
+ for (; i > to - 1; i--)
+ action.accept(elementAt(es, i));
+ if (to == end) {
+ if (end != head)
+ throw new ConcurrentModificationException();
+ lastRet = end;
+ break;
+ }
}
}
}
/**
- * This class is nearly a mirror-image of DeqIterator, using tail
- * instead of head for initial cursor, and head instead of tail
- * for fence.
+ * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
+ * and <em>fail-fast</em> {@link Spliterator} over the elements in this
+ * deque.
+ *
+ * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
+ * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
+ * {@link Spliterator#NONNULL}. Overriding implementations should document
+ * the reporting of additional characteristic values.
+ *
+ * @return a {@code Spliterator} over the elements in this deque
+ * @since 1.8
*/
- private class DescendingIterator implements Iterator<E> {
- private int cursor = tail;
- private int fence = head;
- private int lastRet = -1;
+ public Spliterator<E> spliterator() {
+ return new DeqSpliterator();
+ }
+
+ final class DeqSpliterator implements Spliterator<E> {
+ private int fence; // -1 until first use
+ private int cursor; // current index, modified on traverse/split
+
+ /** Constructs late-binding spliterator over all elements. */
+ DeqSpliterator() {
+ this.fence = -1;
+ }
+
+ /** Constructs spliterator over the given range. */
+ DeqSpliterator(int origin, int fence) {
+ // assert 0 <= origin && origin < elements.length;
+ // assert 0 <= fence && fence < elements.length;
+ this.cursor = origin;
+ this.fence = fence;
+ }
+
+ /** Ensures late-binding initialization; then returns fence. */
+ private int getFence() { // force initialization
+ int t;
+ if ((t = fence) < 0) {
+ t = fence = tail;
+ cursor = head;
+ }
+ return t;
+ }
- public boolean hasNext() {
- return cursor != fence;
+ public DeqSpliterator trySplit() {
+ final Object[] es = elements;
+ final int i, n;
+ return ((n = sub(getFence(), i = cursor, es.length) >> 1) <= 0)
+ ? null
+ : new DeqSpliterator(i, cursor = add(i, n, es.length));
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ if (action == null)
+ throw new NullPointerException();
+ final int end = getFence(), cursor = this.cursor;
+ final Object[] es = elements;
+ if (cursor != end) {
+ this.cursor = end;
+ // null check at both ends of range is sufficient
+ if (es[cursor] == null || es[dec(end, es.length)] == null)
+ throw new ConcurrentModificationException();
+ for (int i = cursor, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ action.accept(elementAt(es, i));
+ if (to == end) break;
+ }
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ final Object[] es = elements;
+ if (fence < 0) { fence = tail; cursor = head; } // late-binding
+ final int i;
+ if ((i = cursor) == fence)
+ return false;
+ E e = nonNullElementAt(es, i);
+ cursor = inc(i, es.length);
+ action.accept(e);
+ return true;
+ }
+
+ public long estimateSize() {
+ return sub(getFence(), cursor, elements.length);
}
- public E next() {
- if (cursor == fence)
- throw new NoSuchElementException();
- cursor = (cursor - 1) & (elements.length - 1);
- @SuppressWarnings("unchecked")
- E result = (E) elements[cursor];
- if (head != fence || result == null)
- throw new ConcurrentModificationException();
- lastRet = cursor;
- return result;
+ public int characteristics() {
+ return Spliterator.NONNULL
+ | Spliterator.ORDERED
+ | Spliterator.SIZED
+ | Spliterator.SUBSIZED;
+ }
+ }
+
+ public void forEach(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ final Object[] es = elements;
+ for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ action.accept(elementAt(es, i));
+ if (to == end) {
+ if (end != tail) throw new ConcurrentModificationException();
+ break;
+ }
}
+ }
- public void remove() {
- if (lastRet < 0)
- throw new IllegalStateException();
- if (!delete(lastRet)) {
- cursor = (cursor + 1) & (elements.length - 1);
- fence = head;
+ /**
+ * @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));
+ }
+
+ /** Implementation of bulk remove methods. */
+ private boolean bulkRemove(Predicate<? super E> filter) {
+ final Object[] es = elements;
+ // Optimize for initial run of survivors
+ for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ if (filter.test(elementAt(es, i)))
+ return bulkRemoveModified(filter, i);
+ if (to == end) {
+ if (end != tail) throw new ConcurrentModificationException();
+ break;
}
- lastRet = -1;
}
+ return false;
+ }
+
+ // 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;
+ }
+
+ /**
+ * Helper for bulkRemove, in case of at least one deletion.
+ * 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.
+ *
+ * @param beg valid index of first element to be deleted
+ */
+ private boolean bulkRemoveModified(
+ Predicate<? super E> filter, final int beg) {
+ final Object[] es = elements;
+ final int capacity = es.length;
+ final int end = tail;
+ final long[] deathRow = nBits(sub(end, beg, capacity));
+ deathRow[0] = 1L; // set bit 0
+ for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+ ; i = 0, to = end, k -= capacity) {
+ for (; i < to; i++)
+ if (filter.test(elementAt(es, i)))
+ setBit(deathRow, i - k);
+ if (to == end) break;
+ }
+ // a two-finger traversal, with hare i reading, tortoise w writing
+ int w = beg;
+ for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+ ; w = 0) { // w rejoins i on second leg
+ // In this loop, i and w are on the same leg, with i > w
+ for (; i < to; i++)
+ if (isClear(deathRow, i - k))
+ es[w++] = es[i];
+ if (to == end) break;
+ // In this loop, w is on the first leg, i on the second
+ for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++)
+ if (isClear(deathRow, i - k))
+ es[w++] = es[i];
+ if (i >= to) {
+ if (w == capacity) w = 0; // "corner" case
+ break;
+ }
+ }
+ if (end != tail) throw new ConcurrentModificationException();
+ circularClear(es, tail = w, end);
+ return true;
}
/**
@@ -700,11 +995,13 @@
*/
public boolean contains(Object o) {
if (o != null) {
- int mask = elements.length - 1;
- int i = head;
- for (Object x; (x = elements[i]) != null; i = (i + 1) & mask) {
- if (o.equals(x))
- return true;
+ final Object[] es = elements;
+ for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ if (o.equals(es[i]))
+ return true;
+ if (to == end) break;
}
}
return false;
@@ -732,16 +1029,18 @@
* The deque will be empty after this call returns.
*/
public void clear() {
- int h = head;
- int t = tail;
- if (h != t) { // clear all cells
- head = tail = 0;
- int i = h;
- int mask = elements.length - 1;
- do {
- elements[i] = null;
- i = (i + 1) & mask;
- } while (i != t);
+ circularClear(elements, head, tail);
+ head = tail = 0;
+ }
+
+ /**
+ * Nulls out slots starting at array index i, upto index end.
+ */
+ private static void circularClear(Object[] es, int i, int end) {
+ for (int to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ Arrays.fill(es, i, to, null);
+ if (to == end) break;
}
}
@@ -759,13 +1058,23 @@
* @return an array containing all of the elements in this deque
*/
public Object[] toArray() {
- final int head = this.head;
- final int tail = this.tail;
- boolean wrap = (tail < head);
- int end = wrap ? tail + elements.length : tail;
- Object[] a = Arrays.copyOfRange(elements, head, end);
- if (wrap)
- System.arraycopy(elements, 0, a, elements.length - head, tail);
+ return toArray(Object[].class);
+ }
+
+ private <T> T[] toArray(Class<T[]> klazz) {
+ final Object[] es = elements;
+ final T[] a;
+ final int head = this.head, tail = this.tail, end;
+ if ((end = tail + ((head <= tail) ? 0 : es.length)) >= 0) {
+ // Uses null extension feature of copyOfRange
+ a = Arrays.copyOfRange(es, head, end, klazz);
+ } else {
+ // integer overflow!
+ a = Arrays.copyOfRange(es, 0, end - head, klazz);
+ System.arraycopy(es, head, a, 0, es.length - head);
+ }
+ if (end != tail)
+ System.arraycopy(es, 0, a, es.length - head, tail);
return a;
}
@@ -807,22 +1116,17 @@
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
- final int head = this.head;
- final int tail = this.tail;
- boolean wrap = (tail < head);
- int size = (tail - head) + (wrap ? elements.length : 0);
- int firstLeg = size - (wrap ? tail : 0);
- int len = a.length;
- if (size > len) {
- a = (T[]) Arrays.copyOfRange(elements, head, head + size,
- a.getClass());
- } else {
- System.arraycopy(elements, head, a, 0, firstLeg);
- if (size < len)
- a[size] = null;
+ final int size;
+ if ((size = size()) > a.length)
+ return toArray((Class<T[]>) a.getClass());
+ final Object[] es = elements;
+ for (int i = head, j = 0, len = Math.min(size, es.length - i);
+ ; i = 0, len = tail) {
+ System.arraycopy(es, i, a, j, len);
+ if ((j += len) == size) break;
}
- if (wrap)
- System.arraycopy(elements, 0, a, firstLeg, tail);
+ if (size < a.length)
+ a[size] = null;
return a;
}
@@ -863,9 +1167,13 @@
s.writeInt(size());
// Write out elements in order.
- int mask = elements.length - 1;
- for (int i = head; i != tail; i = (i + 1) & mask)
- s.writeObject(elements[i]);
+ final Object[] es = elements;
+ for (int i = head, end = tail, to = (i <= end) ? end : es.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ s.writeObject(es[i]);
+ if (to == end) break;
+ }
}
/**
@@ -881,106 +1189,33 @@
// Read in size and allocate array
int size = s.readInt();
- allocateElements(size);
- head = 0;
- tail = size;
+ elements = new Object[size + 1];
+ this.tail = size;
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
elements[i] = s.readObject();
}
- /**
- * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
- * and <em>fail-fast</em> {@link Spliterator} over the elements in this
- * deque.
- *
- * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
- * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
- * {@link Spliterator#NONNULL}. Overriding implementations should document
- * the reporting of additional characteristic values.
- *
- * @return a {@code Spliterator} over the elements in this deque
- * @since 1.8
- */
- public Spliterator<E> spliterator() {
- return new DeqSpliterator<>(this, -1, -1);
- }
-
- static final class DeqSpliterator<E> implements Spliterator<E> {
- private final ArrayDeque<E> deq;
- private int fence; // -1 until first use
- private int index; // current index, modified on traverse/split
-
- /** Creates new spliterator covering the given array and range. */
- DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
- this.deq = deq;
- this.index = origin;
- this.fence = fence;
- }
-
- private int getFence() { // force initialization
- int t;
- if ((t = fence) < 0) {
- t = fence = deq.tail;
- index = deq.head;
- }
- return t;
- }
-
- public DeqSpliterator<E> trySplit() {
- int t = getFence(), h = index, n = deq.elements.length;
- if (h != t && ((h + 1) & (n - 1)) != t) {
- if (h > t)
- t += n;
- int m = ((h + t) >>> 1) & (n - 1);
- return new DeqSpliterator<E>(deq, h, index = m);
- }
- return null;
- }
-
- public void forEachRemaining(Consumer<? super E> consumer) {
- if (consumer == null)
- throw new NullPointerException();
- Object[] a = deq.elements;
- int m = a.length - 1, f = getFence(), i = index;
- index = f;
- while (i != f) {
- @SuppressWarnings("unchecked") E e = (E)a[i];
- i = (i + 1) & m;
- if (e == null)
- throw new ConcurrentModificationException();
- consumer.accept(e);
- }
- }
-
- public boolean tryAdvance(Consumer<? super E> consumer) {
- if (consumer == null)
- throw new NullPointerException();
- Object[] a = deq.elements;
- int m = a.length - 1, f = getFence(), i = index;
- if (i != f) {
- @SuppressWarnings("unchecked") E e = (E)a[i];
- index = (i + 1) & m;
- if (e == null)
- throw new ConcurrentModificationException();
- consumer.accept(e);
- return true;
- }
- return false;
- }
-
- public long estimateSize() {
- int n = getFence() - index;
- if (n < 0)
- n += deq.elements.length;
- return (long) n;
- }
-
- @Override
- public int characteristics() {
- return Spliterator.ORDERED | Spliterator.SIZED |
- Spliterator.NONNULL | Spliterator.SUBSIZED;
+ /** debugging */
+ void checkInvariants() {
+ // Use head and tail fields with empty slot at tail strategy.
+ // head == tail disambiguates to "empty".
+ try {
+ int capacity = elements.length;
+ // assert 0 <= head && head < capacity;
+ // assert 0 <= tail && tail < capacity;
+ // assert capacity > 0;
+ // assert size() < capacity;
+ // assert head == tail || elements[head] != null;
+ // assert elements[tail] == null;
+ // assert head == tail || elements[dec(tail, capacity)] != null;
+ } catch (Throwable t) {
+ System.err.printf("head=%d tail=%d capacity=%d%n",
+ head, tail, elements.length);
+ System.err.printf("elements=%s%n",
+ Arrays.toString(elements));
+ throw t;
}
}
--- a/jdk/src/java.base/share/classes/java/util/ArrayList.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/ArrayList.java Mon Nov 28 23:36:11 2016 -0800
@@ -104,7 +104,6 @@
* @see Vector
* @since 1.2
*/
-
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
@@ -424,6 +423,11 @@
return (E) elementData[index];
}
+ @SuppressWarnings("unchecked")
+ static <E> E elementAt(Object[] es, int index) {
+ return (E) es[index];
+ }
+
/**
* Returns the element at the specified position in this list.
*
@@ -553,7 +557,7 @@
return false;
}
- /*
+ /**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
@@ -572,11 +576,7 @@
*/
public void clear() {
modCount++;
-
- // clear to let GC do its work
- for (int i = 0; i < size; i++)
- elementData[i] = null;
-
+ Arrays.fill(elementData, 0, size, null);
size = 0;
}
@@ -665,16 +665,10 @@
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
- int numMoved = size - toIndex;
- System.arraycopy(elementData, toIndex, elementData, fromIndex,
- numMoved);
-
- // clear to let GC do its work
- int newSize = size - (toIndex-fromIndex);
- for (int i = newSize; i < size; i++) {
- elementData[i] = null;
- }
- size = newSize;
+ final Object[] es = elementData;
+ final int oldSize = size;
+ System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
+ Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null);
}
/**
@@ -717,8 +711,7 @@
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
- Objects.requireNonNull(c);
- return batchRemove(c, false);
+ return batchRemove(c, false, 0, size);
}
/**
@@ -738,34 +731,35 @@
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {
- Objects.requireNonNull(c);
- return batchRemove(c, true);
+ return batchRemove(c, true, 0, size);
}
- private boolean batchRemove(Collection<?> c, boolean complement) {
- final Object[] elementData = this.elementData;
- int r = 0, w = 0;
- boolean modified = false;
- try {
- for (; r < size; r++)
- if (c.contains(elementData[r]) == complement)
- elementData[w++] = elementData[r];
- } finally {
- // Preserve behavioral compatibility with AbstractCollection,
- // even if c.contains() throws.
- if (r != size) {
- System.arraycopy(elementData, r,
- elementData, w,
- size - r);
- w += size - r;
- }
- if (w != size) {
- // clear to let GC do its work
- for (int i = w; i < size; i++)
- elementData[i] = null;
- modCount += size - w;
- size = w;
- modified = true;
+ boolean batchRemove(Collection<?> c, boolean complement,
+ final int from, final int end) {
+ Objects.requireNonNull(c);
+ final Object[] es = elementData;
+ final boolean modified;
+ int r;
+ // Optimize for initial run of survivors
+ for (r = from; r < end && c.contains(es[r]) == complement; r++)
+ ;
+ if (modified = (r < end)) {
+ int w = r++;
+ try {
+ for (Object e; r < end; r++)
+ if (c.contains(e = es[r]) == complement)
+ es[w++] = e;
+ } catch (Throwable ex) {
+ // Preserve behavioral compatibility with AbstractCollection,
+ // even if c.contains() throws.
+ System.arraycopy(es, r, es, w, end - r);
+ w += end - r;
+ throw ex;
+ } finally {
+ final int oldSize = size, deleted = end - w;
+ modCount += deleted;
+ System.arraycopy(es, end, es, w, oldSize - end);
+ Arrays.fill(es, size -= deleted, oldSize, null);
}
}
return modified;
@@ -912,25 +906,21 @@
}
@Override
- @SuppressWarnings("unchecked")
- public void forEachRemaining(Consumer<? super E> consumer) {
- Objects.requireNonNull(consumer);
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
final int size = ArrayList.this.size;
int i = cursor;
- if (i >= size) {
- return;
- }
- final Object[] elementData = ArrayList.this.elementData;
- if (i >= elementData.length) {
- throw new ConcurrentModificationException();
+ if (i < size) {
+ final Object[] es = elementData;
+ if (i >= es.length)
+ throw new ConcurrentModificationException();
+ for (; i < size && modCount == expectedModCount; i++)
+ action.accept(elementAt(es, i));
+ // update once at end to reduce heap write traffic
+ cursor = i;
+ lastRet = i - 1;
+ checkForComodification();
}
- while (i != size && modCount == expectedModCount) {
- consumer.accept((E) elementData[i++]);
- }
- // update once at end of iteration to reduce heap write traffic
- cursor = i;
- lastRet = i - 1;
- checkForComodification();
}
final void checkForComodification() {
@@ -1117,6 +1107,33 @@
return true;
}
+ public boolean removeAll(Collection<?> c) {
+ return batchRemove(c, false);
+ }
+
+ public boolean retainAll(Collection<?> c) {
+ return batchRemove(c, true);
+ }
+
+ private boolean batchRemove(Collection<?> c, boolean complement) {
+ checkForComodification();
+ int oldSize = root.size;
+ boolean modified =
+ root.batchRemove(c, complement, offset, offset + size);
+ if (modified)
+ updateSizeAndModCount(root.size - oldSize);
+ return modified;
+ }
+
+ public boolean removeIf(Predicate<? super E> filter) {
+ checkForComodification();
+ int oldSize = root.size;
+ boolean modified = root.removeIf(filter, offset, offset + size);
+ if (modified)
+ updateSizeAndModCount(root.size - oldSize);
+ return modified;
+ }
+
public Iterator<E> iterator() {
return listIterator();
}
@@ -1164,24 +1181,21 @@
return (E) elementData[offset + (lastRet = i)];
}
- @SuppressWarnings("unchecked")
- public void forEachRemaining(Consumer<? super E> consumer) {
- Objects.requireNonNull(consumer);
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
final int size = SubList.this.size;
int i = cursor;
- if (i >= size) {
- return;
- }
- final Object[] elementData = root.elementData;
- if (offset + i >= elementData.length) {
- throw new ConcurrentModificationException();
+ if (i < size) {
+ final Object[] es = root.elementData;
+ if (offset + i >= es.length)
+ throw new ConcurrentModificationException();
+ for (; i < size && modCount == expectedModCount; i++)
+ action.accept(elementAt(es, offset + i));
+ // update once at end to reduce heap write traffic
+ cursor = i;
+ lastRet = i - 1;
+ checkForComodification();
}
- while (i != size && modCount == expectedModCount) {
- consumer.accept((E) elementData[offset + (i++)]);
- }
- // update once at end of iteration to reduce heap write traffic
- lastRet = cursor = i;
- checkForComodification();
}
public int nextIndex() {
@@ -1348,15 +1362,12 @@
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
- @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) this.elementData;
+ final Object[] es = elementData;
final int size = this.size;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- action.accept(elementData[i]);
- }
- if (modCount != expectedModCount) {
+ for (int i = 0; modCount == expectedModCount && i < size; i++)
+ action.accept(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
}
/**
@@ -1417,7 +1428,7 @@
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
- /** Create new spliterator covering the given range */
+ /** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
@@ -1495,61 +1506,73 @@
}
}
- @Override
- public boolean removeIf(Predicate<? super E> filter) {
- Objects.requireNonNull(filter);
- // figure out which elements are to be removed
- // any exception thrown from the filter predicate at this stage
- // will leave the collection unmodified
- int removeCount = 0;
- final BitSet removeSet = new BitSet(size);
- final int expectedModCount = modCount;
- final int size = this.size;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- @SuppressWarnings("unchecked")
- final E element = (E) elementData[i];
- if (filter.test(element)) {
- removeSet.set(i);
- removeCount++;
- }
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
+ // A tiny bit set implementation
- // shift surviving elements left over the spaces left by removed elements
- final boolean anyToRemove = removeCount > 0;
- if (anyToRemove) {
- final int newSize = size - removeCount;
- for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
- i = removeSet.nextClearBit(i);
- elementData[j] = elementData[i];
- }
- for (int k=newSize; k < size; k++) {
- elementData[k] = null; // Let gc do its work
- }
- this.size = newSize;
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- modCount++;
- }
-
- return anyToRemove;
+ 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;
}
@Override
- @SuppressWarnings("unchecked")
+ public boolean removeIf(Predicate<? super E> filter) {
+ return removeIf(filter, 0, size);
+ }
+
+ /**
+ * Removes all elements satisfying the given predicate, from index
+ * i (inclusive) to index end (exclusive).
+ */
+ boolean removeIf(Predicate<? super E> filter, int i, final int end) {
+ Objects.requireNonNull(filter);
+ int expectedModCount = modCount;
+ final Object[] es = elementData;
+ // Optimize for initial run of survivors
+ for (; i < end && !filter.test(elementAt(es, i)); i++)
+ ;
+ // 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.
+ if (i < end) {
+ 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(elementAt(es, i)))
+ setBit(deathRow, i - beg);
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ expectedModCount++;
+ modCount++;
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ es[w++] = es[i];
+ final int oldSize = size;
+ System.arraycopy(es, end, es, w, oldSize - end);
+ Arrays.fill(es, size -= (end - w), oldSize, null);
+ return true;
+ } else {
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return false;
+ }
+ }
+
+ @Override
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
+ final Object[] es = elementData;
final int size = this.size;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- elementData[i] = operator.apply((E) elementData[i]);
- }
- if (modCount != expectedModCount) {
+ for (int i = 0; modCount == expectedModCount && i < size; i++)
+ es[i] = operator.apply(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
modCount++;
}
@@ -1558,9 +1581,13 @@
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
- if (modCount != expectedModCount) {
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
modCount++;
}
+
+ void checkInvariants() {
+ // assert size >= 0;
+ // assert size == elementData.length || elementData[size] == null;
+ }
}
--- a/jdk/src/java.base/share/classes/java/util/Vector.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/Vector.java Mon Nov 28 23:36:11 2016 -0800
@@ -513,7 +513,7 @@
* Returns the last component of the vector.
*
* @return the last component of the vector, i.e., the component at index
- * <code>size() - 1</code>.
+ * {@code size() - 1}
* @throws NoSuchElementException if this vector is empty
*/
public synchronized E lastElement() {
@@ -675,10 +675,7 @@
* method (which is part of the {@link List} interface).
*/
public synchronized void removeAllElements() {
- // Let gc do its work
- for (int i = 0; i < elementCount; i++)
- elementData[i] = null;
-
+ Arrays.fill(elementData, 0, elementCount, null);
modCount++;
elementCount = 0;
}
@@ -693,7 +690,7 @@
public synchronized Object clone() {
try {
@SuppressWarnings("unchecked")
- Vector<E> v = (Vector<E>) super.clone();
+ Vector<E> v = (Vector<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, elementCount);
v.modCount = 0;
return v;
@@ -759,6 +756,11 @@
return (E) elementData[index];
}
+ @SuppressWarnings("unchecked")
+ static <E> E elementAt(Object[] es, int index) {
+ return (E) es[index];
+ }
+
/**
* Returns the element at the specified position in this Vector.
*
@@ -855,10 +857,10 @@
* Shifts any subsequent elements to the left (subtracts one from their
* indices). Returns the element that was removed from the Vector.
*
+ * @param index the index of the element to be removed
+ * @return element that was removed
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
- * @param index the index of the element to be removed
- * @return element that was removed
* @since 1.2
*/
public synchronized E remove(int index) {
@@ -949,8 +951,9 @@
* or if the specified collection is null
* @since 1.2
*/
- public synchronized boolean removeAll(Collection<?> c) {
- return super.removeAll(c);
+ public boolean removeAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
}
/**
@@ -972,8 +975,62 @@
* or if the specified collection is null
* @since 1.2
*/
- public synchronized boolean retainAll(Collection<?> c) {
- return super.retainAll(c);
+ public boolean retainAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
+ }
+
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ // 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;
+ }
+
+ private synchronized boolean bulkRemove(Predicate<? super E> filter) {
+ int expectedModCount = modCount;
+ final Object[] es = elementData;
+ final int end = elementCount;
+ int i;
+ // Optimize for initial run of survivors
+ for (i = 0; i < end && !filter.test(elementAt(es, i)); i++)
+ ;
+ // 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.
+ if (i < end) {
+ 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(elementAt(es, i)))
+ setBit(deathRow, i - beg);
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ expectedModCount++;
+ modCount++;
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ es[w++] = es[i];
+ Arrays.fill(es, elementCount = w, end, null);
+ return true;
+ } else {
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return false;
+ }
}
/**
@@ -1095,15 +1152,12 @@
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*/
protected synchronized void removeRange(int fromIndex, int toIndex) {
- int numMoved = elementCount - toIndex;
- System.arraycopy(elementData, toIndex, elementData, fromIndex,
- numMoved);
+ final Object[] es = elementData;
+ final int oldSize = elementCount;
+ System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
- // Let gc do its work
modCount++;
- int newElementCount = elementCount - (toIndex-fromIndex);
- while (elementCount != newElementCount)
- elementData[--elementCount] = null;
+ Arrays.fill(es, elementCount -= (toIndex - fromIndex), oldSize, null);
}
/**
@@ -1212,14 +1266,11 @@
if (i >= size) {
return;
}
- @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) Vector.this.elementData;
- if (i >= elementData.length) {
+ final Object[] es = elementData;
+ if (i >= es.length)
throw new ConcurrentModificationException();
- }
- while (i != size && modCount == expectedModCount) {
- action.accept(elementData[i++]);
- }
+ while (i < size && modCount == expectedModCount)
+ action.accept(elementAt(es, i++));
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
@@ -1290,73 +1341,24 @@
public synchronized void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
- @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) this.elementData;
- final int elementCount = this.elementCount;
- for (int i=0; modCount == expectedModCount && i < elementCount; i++) {
- action.accept(elementData[i]);
- }
- if (modCount != expectedModCount) {
+ final Object[] es = elementData;
+ final int size = elementCount;
+ for (int i = 0; modCount == expectedModCount && i < size; i++)
+ action.accept(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
}
@Override
- @SuppressWarnings("unchecked")
- public synchronized boolean removeIf(Predicate<? super E> filter) {
- Objects.requireNonNull(filter);
- // figure out which elements are to be removed
- // any exception thrown from the filter predicate at this stage
- // will leave the collection unmodified
- int removeCount = 0;
- final int size = elementCount;
- final BitSet removeSet = new BitSet(size);
- final int expectedModCount = modCount;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- @SuppressWarnings("unchecked")
- final E element = (E) elementData[i];
- if (filter.test(element)) {
- removeSet.set(i);
- removeCount++;
- }
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
-
- // shift surviving elements left over the spaces left by removed elements
- final boolean anyToRemove = removeCount > 0;
- if (anyToRemove) {
- final int newSize = size - removeCount;
- for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
- i = removeSet.nextClearBit(i);
- elementData[j] = elementData[i];
- }
- for (int k=newSize; k < size; k++) {
- elementData[k] = null; // Let gc do its work
- }
- elementCount = newSize;
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- modCount++;
- }
-
- return anyToRemove;
- }
-
- @Override
- @SuppressWarnings("unchecked")
public synchronized void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
+ final Object[] es = elementData;
final int size = elementCount;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- elementData[i] = operator.apply((E) elementData[i]);
- }
- if (modCount != expectedModCount) {
+ for (int i = 0; modCount == expectedModCount && i < size; i++)
+ es[i] = operator.apply(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
modCount++;
}
@@ -1365,9 +1367,8 @@
public synchronized void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, elementCount, c);
- if (modCount != expectedModCount) {
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
modCount++;
}
@@ -1397,7 +1398,7 @@
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
- /** Create new spliterator covering the given range */
+ /** Create new spliterator covering the given range */
VectorSpliterator(Vector<E> list, Object[] array, int origin, int fence,
int expectedModCount) {
this.list = list;
@@ -1410,7 +1411,7 @@
private int getFence() { // initialize on first use
int hi;
if ((hi = fence) < 0) {
- synchronized(list) {
+ synchronized (list) {
array = list.elementData;
expectedModCount = list.modCount;
hi = fence = list.elementCount;
@@ -1449,7 +1450,7 @@
throw new NullPointerException();
if ((lst = list) != null) {
if ((hi = fence) < 0) {
- synchronized(lst) {
+ synchronized (lst) {
expectedModCount = lst.modCount;
a = array = lst.elementData;
hi = fence = lst.elementCount;
@@ -1475,4 +1476,9 @@
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
+
+ void checkInvariants() {
+ // assert elementCount >= 0;
+ // assert elementCount == elementData.length || elementData[elementCount] == null;
+ }
}
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java Mon Nov 28 23:36:11 2016 -0800
@@ -46,6 +46,8 @@
import java.util.Spliterators;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
/**
* A bounded {@linkplain BlockingQueue blocking queue} backed by an
@@ -85,6 +87,11 @@
public class ArrayBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
+ /*
+ * Much of the implementation mechanics, especially the unusual
+ * nested loops, are shared and co-maintained with ArrayDeque.
+ */
+
/**
* Serialization ID. This class relies on default serialization
* even for the items array, which is default-serialized, even if
@@ -129,10 +136,21 @@
// Internal helper methods
/**
- * Circularly decrements array index i.
+ * Increments i, mod modulus.
+ * Precondition and postcondition: 0 <= i < modulus.
*/
- final int dec(int i) {
- return ((i == 0) ? items.length : i) - 1;
+ static final int inc(int i, int modulus) {
+ if (++i >= modulus) i = 0;
+ return i;
+ }
+
+ /**
+ * Decrements i, mod modulus.
+ * Precondition and postcondition: 0 <= i < modulus.
+ */
+ static final int dec(int i, int modulus) {
+ if (--i < 0) i = modulus - 1;
+ return i;
}
/**
@@ -144,14 +162,24 @@
}
/**
+ * Returns element at array index i.
+ * This is a slight abuse of generics, accepted by javac.
+ */
+ @SuppressWarnings("unchecked")
+ static <E> E itemAt(Object[] items, int i) {
+ return (E) items[i];
+ }
+
+ /**
* Inserts element at current put position, advances, and signals.
* Call only when holding lock.
*/
- private void enqueue(E x) {
+ private void enqueue(E e) {
+ // assert lock.isHeldByCurrentThread();
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
- items[putIndex] = x;
+ items[putIndex] = e;
if (++putIndex == items.length) putIndex = 0;
count++;
notEmpty.signal();
@@ -162,18 +190,19 @@
* Call only when holding lock.
*/
private E dequeue() {
+ // assert lock.isHeldByCurrentThread();
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
- E x = (E) items[takeIndex];
+ E e = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length) takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
- return x;
+ return e;
}
/**
@@ -182,6 +211,7 @@
* Call only when holding lock.
*/
void removeAt(final int removeIndex) {
+ // assert lock.isHeldByCurrentThread();
// assert lock.getHoldCount() == 1;
// assert items[removeIndex] != null;
// assert removeIndex >= 0 && removeIndex < items.length;
@@ -267,6 +297,7 @@
final ReentrantLock lock = this.lock;
lock.lock(); // Lock only for visibility, not mutual exclusion
try {
+ final Object[] items = this.items;
int i = 0;
try {
for (E e : c)
@@ -481,15 +512,16 @@
try {
if (count > 0) {
final Object[] items = this.items;
- final int putIndex = this.putIndex;
- int i = takeIndex;
- do {
- if (o.equals(items[i])) {
- removeAt(i);
- return true;
- }
- if (++i == items.length) i = 0;
- } while (i != putIndex);
+ for (int i = takeIndex, end = putIndex,
+ to = (i < end) ? end : items.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ if (o.equals(items[i])) {
+ removeAt(i);
+ return true;
+ }
+ if (to == end) break;
+ }
}
return false;
} finally {
@@ -512,13 +544,14 @@
try {
if (count > 0) {
final Object[] items = this.items;
- final int putIndex = this.putIndex;
- int i = takeIndex;
- do {
- if (o.equals(items[i]))
- return true;
- if (++i == items.length) i = 0;
- } while (i != putIndex);
+ for (int i = takeIndex, end = putIndex,
+ to = (i < end) ? end : items.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ if (o.equals(items[i]))
+ return true;
+ if (to == end) break;
+ }
}
return false;
} finally {
@@ -625,15 +658,9 @@
final ReentrantLock lock = this.lock;
lock.lock();
try {
- int k = count;
- if (k > 0) {
- final Object[] items = this.items;
- final int putIndex = this.putIndex;
- int i = takeIndex;
- do {
- items[i] = null;
- if (++i == items.length) i = 0;
- } while (i != putIndex);
+ int k;
+ if ((k = count) > 0) {
+ circularClear(items, takeIndex, putIndex);
takeIndex = putIndex;
count = 0;
if (itrs != null)
@@ -647,6 +674,18 @@
}
/**
+ * Nulls out slots starting at array index i, upto index end.
+ * If i == end, the entire array is cleared!
+ */
+ private static void circularClear(Object[] items, int i, int end) {
+ for (int to = (i < end) ? end : items.length;
+ ; i = 0, to = end) {
+ Arrays.fill(items, i, to, null);
+ if (to == end) break;
+ }
+ }
+
+ /**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
@@ -678,8 +717,8 @@
try {
while (i < n) {
@SuppressWarnings("unchecked")
- E x = (E) items[take];
- c.add(x);
+ E e = (E) items[take];
+ c.add(e);
items[take] = null;
if (++take == items.length) take = 0;
i++;
@@ -808,7 +847,7 @@
* there is known to be at least one iterator to collect
*/
void doSomeSweeping(boolean tryHarder) {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
// assert head != null;
int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;
Node o, p;
@@ -864,7 +903,7 @@
* Adds a new iterator to the linked list of tracked iterators.
*/
void register(Itr itr) {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
head = new Node(itr, head);
}
@@ -874,7 +913,7 @@
* Notifies all iterators, and expunges any that are now stale.
*/
void takeIndexWrapped() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
cycles++;
for (Node o = null, p = head; p != null;) {
final Itr it = p.get();
@@ -931,7 +970,7 @@
* clears all weak refs, and unlinks the itrs datastructure.
*/
void queueIsEmpty() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
for (Node p = head; p != null; p = p.next) {
Itr it = p.get();
if (it != null) {
@@ -947,7 +986,7 @@
* Called whenever an element has been dequeued (at takeIndex).
*/
void elementDequeued() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
if (count == 0)
queueIsEmpty();
else if (takeIndex == 0)
@@ -1008,7 +1047,6 @@
private static final int DETACHED = -3;
Itr() {
- // assert lock.getHoldCount() == 0;
lastRet = NONE;
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
@@ -1041,12 +1079,12 @@
}
boolean isDetached() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
return prevTakeIndex < 0;
}
private int incCursor(int index) {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
if (++index == items.length) index = 0;
if (index == putIndex) index = NONE;
return index;
@@ -1071,7 +1109,7 @@
* operation on this iterator. Call only from iterating thread.
*/
private void incorporateDequeues() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
// assert itrs != null;
// assert !isDetached();
// assert count > 0;
@@ -1114,7 +1152,7 @@
*/
private void detach() {
// Switch to detached mode
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
// assert cursor == NONE;
// assert nextIndex < 0;
// assert lastRet < 0 || nextItem == null;
@@ -1134,7 +1172,6 @@
* triggered by queue modifications.
*/
public boolean hasNext() {
- // assert lock.getHoldCount() == 0;
if (nextItem != null)
return true;
noNext();
@@ -1164,9 +1201,8 @@
}
public E next() {
- // assert lock.getHoldCount() == 0;
- final E x = nextItem;
- if (x == null)
+ final E e = nextItem;
+ if (e == null)
throw new NoSuchElementException();
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
@@ -1188,13 +1224,43 @@
} finally {
lock.unlock();
}
- return x;
+ return e;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ final ReentrantLock lock = ArrayBlockingQueue.this.lock;
+ lock.lock();
+ try {
+ final E e = nextItem;
+ if (e == null) return;
+ if (!isDetached())
+ incorporateDequeues();
+ action.accept(e);
+ if (isDetached() || cursor < 0) return;
+ final Object[] items = ArrayBlockingQueue.this.items;
+ for (int i = cursor, end = putIndex,
+ to = (i < end) ? end : items.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ action.accept(itemAt(items, i));
+ if (to == end) break;
+ }
+ } finally {
+ // Calling forEachRemaining is a strong hint that this
+ // iteration is surely over; supporting remove() after
+ // forEachRemaining() is more trouble than it's worth
+ cursor = nextIndex = lastRet = NONE;
+ nextItem = lastItem = null;
+ detach();
+ lock.unlock();
+ }
}
public void remove() {
- // assert lock.getHoldCount() == 0;
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
+ // assert lock.getHoldCount() == 1;
try {
if (!isDetached())
incorporateDequeues(); // might update lastRet or detach
@@ -1232,7 +1298,7 @@
* from next(), as promised by returning true from hasNext().
*/
void shutdown() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
cursor = NONE;
if (nextIndex >= 0)
nextIndex = REMOVED;
@@ -1260,7 +1326,7 @@
* @return true if this iterator should be unlinked from itrs
*/
boolean removedAt(int removedIndex) {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
if (isDetached())
return true;
@@ -1285,7 +1351,7 @@
}
else if (x > removedDistance) {
// assert cursor != prevTakeIndex;
- this.cursor = cursor = dec(cursor);
+ this.cursor = cursor = dec(cursor, len);
}
}
int lastRet = this.lastRet;
@@ -1294,7 +1360,7 @@
if (x == removedDistance)
this.lastRet = lastRet = REMOVED;
else if (x > removedDistance)
- this.lastRet = lastRet = dec(lastRet);
+ this.lastRet = lastRet = dec(lastRet, len);
}
int nextIndex = this.nextIndex;
if (nextIndex >= 0) {
@@ -1302,7 +1368,7 @@
if (x == removedDistance)
this.nextIndex = nextIndex = REMOVED;
else if (x > removedDistance)
- this.nextIndex = nextIndex = dec(nextIndex);
+ this.nextIndex = nextIndex = dec(nextIndex, len);
}
if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
this.prevTakeIndex = DETACHED;
@@ -1317,7 +1383,7 @@
* @return true if this iterator should be unlinked from itrs
*/
boolean takeIndexWrapped() {
- // assert lock.getHoldCount() == 1;
+ // assert lock.isHeldByCurrentThread();
if (isDetached())
return true;
if (itrs.cycles - prevCycles > 1) {
@@ -1366,4 +1432,170 @@
Spliterator.CONCURRENT));
}
+ public void forEach(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ if (count > 0) {
+ final Object[] items = this.items;
+ for (int i = takeIndex, end = putIndex,
+ to = (i < end) ? end : items.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ action.accept(itemAt(items, i));
+ if (to == end) break;
+ }
+ }
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ /**
+ * @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));
+ }
+
+ /** Implementation of bulk remove methods. */
+ private boolean bulkRemove(Predicate<? super E> filter) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ if (itrs == null) { // check for active iterators
+ if (count > 0) {
+ final Object[] items = this.items;
+ // Optimize for initial run of survivors
+ for (int i = takeIndex, end = putIndex,
+ to = (i < end) ? end : items.length;
+ ; i = 0, to = end) {
+ for (; i < to; i++)
+ if (filter.test(itemAt(items, i)))
+ return bulkRemoveModified(filter, i);
+ if (to == end) break;
+ }
+ }
+ return false;
+ }
+ } finally {
+ lock.unlock();
+ }
+ // Active iterators are too hairy!
+ // Punting (for now) to the slow n^2 algorithm ...
+ return super.removeIf(filter);
+ }
+
+ // 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;
+ }
+
+ /**
+ * Returns circular distance from i to j, disambiguating i == j to
+ * items.length; never returns 0.
+ */
+ private int distanceNonEmpty(int i, int j) {
+ if ((j -= i) <= 0) j += items.length;
+ return j;
+ }
+
+ /**
+ * Helper for bulkRemove, in case of at least one deletion.
+ * Tolerate predicates that reentrantly access the collection for
+ * read (but not write), so traverse once to find elements to
+ * delete, a second pass to physically expunge.
+ *
+ * @param beg valid index of first element to be deleted
+ */
+ private boolean bulkRemoveModified(
+ Predicate<? super E> filter, final int beg) {
+ final Object[] es = items;
+ final int capacity = items.length;
+ final int end = putIndex;
+ final long[] deathRow = nBits(distanceNonEmpty(beg, putIndex));
+ deathRow[0] = 1L; // set bit 0
+ for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+ ; i = 0, to = end, k -= capacity) {
+ for (; i < to; i++)
+ if (filter.test(itemAt(es, i)))
+ setBit(deathRow, i - k);
+ if (to == end) break;
+ }
+ // a two-finger traversal, with hare i reading, tortoise w writing
+ int w = beg;
+ for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+ ; w = 0) { // w rejoins i on second leg
+ // In this loop, i and w are on the same leg, with i > w
+ for (; i < to; i++)
+ if (isClear(deathRow, i - k))
+ es[w++] = es[i];
+ if (to == end) break;
+ // In this loop, w is on the first leg, i on the second
+ for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++)
+ if (isClear(deathRow, i - k))
+ es[w++] = es[i];
+ if (i >= to) {
+ if (w == capacity) w = 0; // "corner" case
+ break;
+ }
+ }
+ count -= distanceNonEmpty(w, end);
+ circularClear(es, putIndex = w, end);
+ return true;
+ }
+
+ /** debugging */
+ void checkInvariants() {
+ // meta-assertions
+ // assert lock.isHeldByCurrentThread();
+ try {
+ // Unlike ArrayDeque, we have a count field but no spare slot.
+ // We prefer ArrayDeque's strategy (and the names of its fields!),
+ // but our field layout is baked into the serial form, and so is
+ // too annoying to change.
+ //
+ // putIndex == takeIndex must be disambiguated by checking count.
+ int capacity = items.length;
+ // assert capacity > 0;
+ // assert takeIndex >= 0 && takeIndex < capacity;
+ // assert putIndex >= 0 && putIndex < capacity;
+ // assert count <= capacity;
+ // assert takeIndex == putIndex || items[takeIndex] != null;
+ // assert count == capacity || items[putIndex] == null;
+ // assert takeIndex == putIndex || items[dec(putIndex, capacity)] != null;
+ } catch (Throwable t) {
+ System.err.printf("takeIndex=%d putIndex=%d count=%d capacity=%d%n",
+ takeIndex, putIndex, count, items.length);
+ System.err.printf("items=%s%n",
+ Arrays.toString(items));
+ throw t;
+ }
+ }
+
}
--- a/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Mon Nov 28 23:36:11 2016 -0800
@@ -380,7 +380,7 @@
// Positional Access Operations
@SuppressWarnings("unchecked")
- private E get(Object[] a, int index) {
+ static <E> E elementAt(Object[] a, int index) {
return (E) a[index];
}
@@ -394,7 +394,7 @@
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
- return get(getArray(), index);
+ return elementAt(getArray(), index);
}
/**
@@ -406,7 +406,7 @@
public E set(int index, E element) {
synchronized (lock) {
Object[] elements = getArray();
- E oldValue = get(elements, index);
+ E oldValue = elementAt(elements, index);
if (oldValue != element) {
int len = elements.length;
@@ -477,7 +477,7 @@
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
- E oldValue = get(elements, index);
+ E oldValue = elementAt(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
@@ -644,34 +644,16 @@
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
- * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>)
+ * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
- * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
+ * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see #remove(Object)
*/
public boolean removeAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- if (len != 0) {
- // temp array holds those elements we know we want to keep
- int newlen = 0;
- Object[] temp = new Object[len];
- for (int i = 0; i < len; ++i) {
- Object element = elements[i];
- if (!c.contains(element))
- temp[newlen++] = element;
- }
- if (newlen != len) {
- setArray(Arrays.copyOf(temp, newlen));
- return true;
- }
- }
- return false;
- }
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
}
/**
@@ -683,34 +665,16 @@
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
- * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>)
+ * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
- * (<a href="{@docRoot}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
+ * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see #remove(Object)
*/
public boolean retainAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- if (len != 0) {
- // temp array holds those elements we know we want to keep
- int newlen = 0;
- Object[] temp = new Object[len];
- for (int i = 0; i < len; ++i) {
- Object element = elements[i];
- if (c.contains(element))
- temp[newlen++] = element;
- }
- if (newlen != len) {
- setArray(Arrays.copyOf(temp, newlen));
- return true;
- }
- }
- return false;
- }
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
}
/**
@@ -839,55 +803,90 @@
public boolean removeIf(Predicate<? super E> filter) {
if (filter == null) throw new NullPointerException();
+ return bulkRemove(filter);
+ }
+
+ // 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;
+ }
+
+ private boolean bulkRemove(Predicate<? super E> filter) {
synchronized (lock) {
- final Object[] elements = getArray();
- final int len = elements.length;
- int i;
- for (i = 0; i < len; i++) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- if (filter.test(e)) {
- int newlen = i;
- final Object[] newElements = new Object[len - 1];
- System.arraycopy(elements, 0, newElements, 0, newlen);
- for (i++; i < len; i++) {
- @SuppressWarnings("unchecked") E x = (E) elements[i];
- if (!filter.test(x))
- newElements[newlen++] = x;
- }
- setArray((newlen == len - 1)
- ? newElements // one match => one copy
- : Arrays.copyOf(newElements, newlen));
- return true;
+ return bulkRemove(filter, 0, getArray().length);
+ }
+ }
+
+ boolean bulkRemove(Predicate<? super E> filter, int i, int end) {
+ // assert Thread.holdsLock(lock);
+ final Object[] es = getArray();
+ // Optimize for initial run of survivors
+ for (; i < end && !filter.test(elementAt(es, i)); i++)
+ ;
+ if (i < end) {
+ final int beg = i;
+ final long[] deathRow = nBits(end - beg);
+ int deleted = 1;
+ deathRow[0] = 1L; // set bit 0
+ for (i = beg + 1; i < end; i++)
+ if (filter.test(elementAt(es, i))) {
+ setBit(deathRow, i - beg);
+ deleted++;
}
- }
- return false; // zero matches => zero copies
+ // Did filter reentrantly modify the list?
+ if (es != getArray())
+ throw new ConcurrentModificationException();
+ final Object[] newElts = Arrays.copyOf(es, es.length - deleted);
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ newElts[w++] = es[i];
+ System.arraycopy(es, i, newElts, w, es.length - i);
+ setArray(newElts);
+ return true;
+ } else {
+ if (es != getArray())
+ throw new ConcurrentModificationException();
+ return false;
}
}
public void replaceAll(UnaryOperator<E> operator) {
if (operator == null) throw new NullPointerException();
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- Object[] newElements = Arrays.copyOf(elements, len);
- for (int i = 0; i < len; ++i) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- newElements[i] = operator.apply(e);
- }
- setArray(newElements);
+ replaceAll(operator, 0, getArray().length);
}
}
+ void replaceAll(UnaryOperator<E> operator, int i, int end) {
+ // assert Thread.holdsLock(lock);
+ final Object[] es = getArray().clone();
+ for (; i < end; i++)
+ es[i] = operator.apply(elementAt(es, i));
+ setArray(es);
+ }
+
public void sort(Comparator<? super E> c) {
synchronized (lock) {
- Object[] elements = getArray();
- Object[] newElements = Arrays.copyOf(elements, elements.length);
- @SuppressWarnings("unchecked") E[] es = (E[])newElements;
- Arrays.sort(es, c);
- setArray(newElements);
+ sort(c, 0, getArray().length);
}
}
+ @SuppressWarnings("unchecked")
+ void sort(Comparator<? super E> c, int i, int end) {
+ // assert Thread.holdsLock(lock);
+ final Object[] es = getArray().clone();
+ Arrays.sort(es, i, end, (Comparator<Object>)c);
+ setArray(es);
+ }
+
/**
* Saves this list to a stream (that is, serializes it).
*
@@ -1167,18 +1166,6 @@
/**
* Sublist for CopyOnWriteArrayList.
- * This class extends AbstractList merely for convenience, to
- * avoid having to define addAll, etc. This doesn't hurt, but
- * is wasteful. This class does not need or use modCount
- * mechanics in AbstractList, but does need to check for
- * concurrent modification using similar mechanics. On each
- * operation, the array that we expect the backing list to use
- * is checked and updated. Since we do this for all of the
- * base operations invoked by those defined in AbstractList,
- * all is well. While inefficient, this is not worth
- * improving. The kinds of list operations inherited from
- * AbstractList are already so slow on COW sublists that
- * adding a bit more space/time doesn't seem even noticeable.
*/
private static class COWSubList<E>
extends AbstractList<E>
@@ -1206,6 +1193,14 @@
throw new ConcurrentModificationException();
}
+ private Object[] getArrayChecked() {
+ // assert Thread.holdsLock(l.lock);
+ Object[] a = l.getArray();
+ if (a != expectedArray)
+ throw new ConcurrentModificationException();
+ return a;
+ }
+
// only call this holding l's lock
private void rangeCheck(int index) {
// assert Thread.holdsLock(l.lock);
@@ -1217,7 +1212,7 @@
synchronized (l.lock) {
rangeCheck(index);
checkForComodification();
- E x = l.set(index+offset, element);
+ E x = l.set(offset + index, element);
expectedArray = l.getArray();
return x;
}
@@ -1227,7 +1222,7 @@
synchronized (l.lock) {
rangeCheck(index);
checkForComodification();
- return l.get(index+offset);
+ return l.get(offset + index);
}
}
@@ -1238,22 +1233,41 @@
}
}
+ public boolean add(E element) {
+ synchronized (l.lock) {
+ checkForComodification();
+ l.add(offset + size, element);
+ expectedArray = l.getArray();
+ size++;
+ }
+ return true;
+ }
+
public void add(int index, E element) {
synchronized (l.lock) {
checkForComodification();
if (index < 0 || index > size)
throw new IndexOutOfBoundsException
(outOfBounds(index, size));
- l.add(index+offset, element);
+ l.add(offset + index, element);
expectedArray = l.getArray();
size++;
}
}
+ public boolean addAll(Collection<? extends E> c) {
+ synchronized (l.lock) {
+ final Object[] oldArray = getArrayChecked();
+ boolean modified = l.addAll(offset + size, c);
+ size += (expectedArray = l.getArray()).length - oldArray.length;
+ return modified;
+ }
+ }
+
public void clear() {
synchronized (l.lock) {
checkForComodification();
- l.removeRange(offset, offset+size);
+ l.removeRange(offset, offset + size);
expectedArray = l.getArray();
size = 0;
}
@@ -1263,7 +1277,7 @@
synchronized (l.lock) {
rangeCheck(index);
checkForComodification();
- E result = l.remove(index+offset);
+ E result = l.remove(offset + index);
expectedArray = l.getArray();
size--;
return result;
@@ -1271,11 +1285,14 @@
}
public boolean remove(Object o) {
- int index = indexOf(o);
- if (index == -1)
- return false;
- remove(index);
- return true;
+ synchronized (l.lock) {
+ checkForComodification();
+ int index = indexOf(o);
+ if (index == -1)
+ return false;
+ remove(index);
+ return true;
+ }
}
public Iterator<E> iterator() {
@@ -1307,174 +1324,63 @@
public void forEach(Consumer<? super E> action) {
if (action == null) throw new NullPointerException();
- int lo = offset;
- int hi = offset + size;
- Object[] a = expectedArray;
- if (l.getArray() != a)
- throw new ConcurrentModificationException();
- if (lo < 0 || hi > a.length)
- throw new IndexOutOfBoundsException();
- for (int i = lo; i < hi; ++i) {
- @SuppressWarnings("unchecked") E e = (E) a[i];
- action.accept(e);
+ int i, end; final Object[] es;
+ synchronized (l.lock) {
+ es = getArrayChecked();
+ i = offset;
+ end = i + size;
}
+ for (; i < end; i++)
+ action.accept(elementAt(es, i));
}
public void replaceAll(UnaryOperator<E> operator) {
if (operator == null) throw new NullPointerException();
synchronized (l.lock) {
- int lo = offset;
- int hi = offset + size;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- Object[] newElements = Arrays.copyOf(elements, len);
- for (int i = lo; i < hi; ++i) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- newElements[i] = operator.apply(e);
- }
- l.setArray(expectedArray = newElements);
+ checkForComodification();
+ l.replaceAll(operator, offset, offset + size);
+ expectedArray = l.getArray();
}
}
public void sort(Comparator<? super E> c) {
synchronized (l.lock) {
- int lo = offset;
- int hi = offset + size;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- Object[] newElements = Arrays.copyOf(elements, len);
- @SuppressWarnings("unchecked") E[] es = (E[])newElements;
- Arrays.sort(es, lo, hi, c);
- l.setArray(expectedArray = newElements);
+ checkForComodification();
+ l.sort(c, offset, offset + size);
+ expectedArray = l.getArray();
}
}
public boolean removeAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- boolean removed = false;
- synchronized (l.lock) {
- int n = size;
- if (n > 0) {
- int lo = offset;
- int hi = offset + n;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- int newSize = 0;
- Object[] temp = new Object[n];
- for (int i = lo; i < hi; ++i) {
- Object element = elements[i];
- if (!c.contains(element))
- temp[newSize++] = element;
- }
- if (newSize != n) {
- Object[] newElements = new Object[len - n + newSize];
- System.arraycopy(elements, 0, newElements, 0, lo);
- System.arraycopy(temp, 0, newElements, lo, newSize);
- System.arraycopy(elements, hi, newElements,
- lo + newSize, len - hi);
- size = newSize;
- removed = true;
- l.setArray(expectedArray = newElements);
- }
- }
- }
- return removed;
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
}
public boolean retainAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- boolean removed = false;
- synchronized (l.lock) {
- int n = size;
- if (n > 0) {
- int lo = offset;
- int hi = offset + n;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- int newSize = 0;
- Object[] temp = new Object[n];
- for (int i = lo; i < hi; ++i) {
- Object element = elements[i];
- if (c.contains(element))
- temp[newSize++] = element;
- }
- if (newSize != n) {
- Object[] newElements = new Object[len - n + newSize];
- System.arraycopy(elements, 0, newElements, 0, lo);
- System.arraycopy(temp, 0, newElements, lo, newSize);
- System.arraycopy(elements, hi, newElements,
- lo + newSize, len - hi);
- size = newSize;
- removed = true;
- l.setArray(expectedArray = newElements);
- }
- }
- }
- return removed;
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
}
public boolean removeIf(Predicate<? super E> filter) {
- if (filter == null) throw new NullPointerException();
- boolean removed = false;
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ private boolean bulkRemove(Predicate<? super E> filter) {
synchronized (l.lock) {
- int n = size;
- if (n > 0) {
- int lo = offset;
- int hi = offset + n;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- int newSize = 0;
- Object[] temp = new Object[n];
- for (int i = lo; i < hi; ++i) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- if (!filter.test(e))
- temp[newSize++] = e;
- }
- if (newSize != n) {
- Object[] newElements = new Object[len - n + newSize];
- System.arraycopy(elements, 0, newElements, 0, lo);
- System.arraycopy(temp, 0, newElements, lo, newSize);
- System.arraycopy(elements, hi, newElements,
- lo + newSize, len - hi);
- size = newSize;
- removed = true;
- l.setArray(expectedArray = newElements);
- }
- }
+ final Object[] oldArray = getArrayChecked();
+ boolean modified = l.bulkRemove(filter, offset, offset + size);
+ size += (expectedArray = l.getArray()).length - oldArray.length;
+ return modified;
}
- return removed;
}
public Spliterator<E> spliterator() {
- int lo = offset;
- int hi = offset + size;
- Object[] a = expectedArray;
- if (l.getArray() != a)
- throw new ConcurrentModificationException();
- if (lo < 0 || hi > a.length)
- throw new IndexOutOfBoundsException();
- return Spliterators.spliterator
- (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED);
+ synchronized (l.lock) {
+ return Spliterators.spliterator(
+ getArrayChecked(), offset, offset + size,
+ Spliterator.IMMUTABLE | Spliterator.ORDERED);
+ }
}
}
--- a/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java Mon Nov 28 23:36:11 2016 -0800
@@ -1127,40 +1127,35 @@
}
/** A customized variant of Spliterators.IteratorSpliterator */
- static final class LBDSpliterator<E> implements Spliterator<E> {
+ private final class LBDSpliterator implements Spliterator<E> {
static final int MAX_BATCH = 1 << 25; // max batch array size;
- final LinkedBlockingDeque<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
- LBDSpliterator(LinkedBlockingDeque<E> queue) {
- this.queue = queue;
- this.est = queue.size();
- }
+
+ LBDSpliterator() { est = size(); }
public long estimateSize() { return est; }
public Spliterator<E> trySplit() {
Node<E> h;
- final LinkedBlockingDeque<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.first) != null) &&
- h.next != null) {
+ (((h = current) != null && h != h.next)
+ || (h = first) != null)
+ && h.next != null) {
Object[] a = new Object[n];
- final ReentrantLock lock = q.lock;
+ final ReentrantLock lock = LinkedBlockingDeque.this.lock;
int i = 0;
Node<E> p = current;
lock.lock();
try {
- if (p != null || (p = q.first) != null) {
- do {
- if ((a[i] = p.item) != null)
- ++i;
- } while ((p = p.next) != null && i < n);
- }
+ if (((p != null && p != p.next) || (p = first) != null)
+ && p.item != null)
+ for (; p != null && i < n; p = p.next)
+ a[i++] = p.item;
} finally {
lock.unlock();
}
@@ -1183,64 +1178,55 @@
public void forEachRemaining(Consumer<? super E> action) {
if (action == null) throw new NullPointerException();
- final LinkedBlockingDeque<E> q = this.queue;
- final ReentrantLock lock = q.lock;
- if (!exhausted) {
- exhausted = true;
- Node<E> p = current;
- do {
- E e = null;
- lock.lock();
- try {
- if (p == null)
- p = q.first;
- while (p != null) {
- e = p.item;
- p = p.next;
- if (e != null)
- break;
- }
- } finally {
- lock.unlock();
+ if (exhausted)
+ return;
+ exhausted = true;
+ final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+ Node<E> p = current;
+ current = null;
+ do {
+ E e = null;
+ lock.lock();
+ try {
+ if ((p != null && p != p.next) || (p = first) != null) {
+ e = p.item;
+ p = p.next;
}
- if (e != null)
- action.accept(e);
- } while (p != null);
- }
+ } finally {
+ lock.unlock();
+ }
+ if (e != null)
+ action.accept(e);
+ } while (p != null);
}
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null) throw new NullPointerException();
- final LinkedBlockingDeque<E> q = this.queue;
- final ReentrantLock lock = q.lock;
- if (!exhausted) {
- E e = null;
- lock.lock();
- try {
- if (current == null)
- current = q.first;
- while (current != null) {
- e = current.item;
- current = current.next;
- if (e != null)
- break;
- }
- } finally {
- lock.unlock();
+ 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;
}
- if (current == null)
- exhausted = true;
- if (e != null) {
- action.accept(e);
- return true;
- }
+ } finally {
+ lock.unlock();
}
- return false;
+ exhausted = ((current = p) == null);
+ if (e == null)
+ return false;
+ action.accept(e);
+ return true;
}
public int characteristics() {
- return Spliterator.ORDERED | Spliterator.NONNULL |
- Spliterator.CONCURRENT;
+ return (Spliterator.ORDERED |
+ Spliterator.NONNULL |
+ Spliterator.CONCURRENT);
}
}
@@ -1261,7 +1247,7 @@
* @since 1.8
*/
public Spliterator<E> spliterator() {
- return new LBDSpliterator<E>(this);
+ return new LBDSpliterator();
}
/**
@@ -1312,4 +1298,14 @@
}
}
+ void checkInvariants() {
+ // assert lock.isHeldByCurrentThread();
+ // Nodes may get self-linked or lose their item, but only
+ // after being unlinked and becoming unreachable from first.
+ for (Node<E> p = first; p != null; p = p.next) {
+ // assert p.next != p;
+ // assert p.item != null;
+ }
+ }
+
}
--- a/jdk/test/java/util/ArrayList/IteratorMicroBenchmark.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/ArrayList/IteratorMicroBenchmark.java Mon Nov 28 23:36:11 2016 -0800
@@ -22,21 +22,36 @@
*/
/*
- * This is not a regression test, but a micro-benchmark.
- * Be patient; this runs for half an hour!
+ * @test
+ * @summary micro-benchmark correctness mode
+ * @run main IteratorMicroBenchmark iterations=1 size=8 warmup=0
+ */
+
+import java.lang.ref.WeakReference;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Enumeration;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.Spliterator;
+import java.util.Vector;
+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;
+
+/**
+ * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
*
- * I have run this as follows:
- *
- * for f in -client -server; do mergeBench dolphin . jr -dsa -da $f IteratorMicroBenchmark.java; done
- *
+ * To run this in micro-benchmark mode, simply run as a normal java program.
+ * Be patient; this program runs for a very long time.
+ * For faster runs, restrict execution using command line args.
*
* @author Martin Buchholz
*/
-
-import java.util.*;
-import java.util.concurrent.*;
-import java.util.regex.Pattern;
-
public class IteratorMicroBenchmark {
abstract static class Job {
private final String name;
@@ -45,17 +60,28 @@
public abstract void work() throws Throwable;
}
- private static void collectAllGarbage() {
- final java.util.concurrent.CountDownLatch drained
- = new java.util.concurrent.CountDownLatch(1);
+ static double warmupSeconds;
+ static long warmupNanos;
+
+ // --------------- GC finalization infrastructure ---------------
+
+ /** 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(); }});
try {
- System.gc(); // enqueue finalizable objects
- new Object() { protected void finalize() {
- drained.countDown(); }};
- System.gc(); // enqueue detector
- drained.await(); // wait for finalizer queue to drain
- System.gc(); // cleanup finalized objects
- } catch (InterruptedException e) { throw new Error(e); }
+ for (int i = 0; i < 10; i++) {
+ System.gc();
+ if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+ System.runFinalization(); // try to pick up stragglers
+ return;
+ }
+ }
+ } catch (InterruptedException unexpected) {
+ throw new AssertionError("unexpected InterruptedException");
+ }
+ throw new AssertionError("failed to do a \"full\" gc");
}
/**
@@ -65,23 +91,22 @@
* Returns array of average times per job per run.
*/
private static long[] time0(Job ... jobs) throws Throwable {
- final long warmupNanos = 10L * 1000L * 1000L * 1000L;
long[] nanoss = new long[jobs.length];
for (int i = 0; i < jobs.length; i++) {
- collectAllGarbage();
- long t0 = System.nanoTime();
- long t;
- int j = 0;
- do { jobs[i].work(); j++; }
- while ((t = System.nanoTime() - t0) < warmupNanos);
- nanoss[i] = t/j;
+ if (warmupNanos > 0) forceFullGc();
+ Job job = jobs[i];
+ long totalTime;
+ int runs = 0;
+ long startTime = System.nanoTime();
+ do { job.work(); runs++; }
+ while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
+ nanoss[i] = totalTime/runs;
}
return nanoss;
}
private static void time(Job ... jobs) throws Throwable {
-
- long[] warmup = time0(jobs); // Warm up run
+ if (warmupSeconds > 0.0) time0(jobs); // Warm up run
long[] nanoss = time0(jobs); // Real timing run
long[] milliss = new long[jobs.length];
double[] ratios = new double[jobs.length];
@@ -126,12 +151,17 @@
private static int intArg(String[] args, String keyword, int defaultValue) {
String val = keywordValue(args, keyword);
- return val == null ? defaultValue : Integer.parseInt(val);
+ return (val == null) ? defaultValue : Integer.parseInt(val);
+ }
+
+ private static double doubleArg(String[] args, String keyword, double defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Double.parseDouble(val);
}
private static Pattern patternArg(String[] args, String keyword) {
String val = keywordValue(args, keyword);
- return val == null ? null : Pattern.compile(val);
+ return (val == null) ? null : Pattern.compile(val);
}
private static Job[] filter(Pattern filter, Job[] jobs) {
@@ -166,26 +196,33 @@
public void remove() { it.remove(); }};}};
}
- /**
- * Usage: [iterations=N] [size=N] [filter=REGEXP]
- */
public static void main(String[] args) throws Throwable {
- final int iterations = intArg(args, "iterations", 100000);
+ final int iterations = intArg(args, "iterations", 100_000);
final int size = intArg(args, "size", 1000);
+ warmupSeconds = doubleArg(args, "warmup", 7.0);
final Pattern filter = patternArg(args, "filter");
+ warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+
+// System.out.printf(
+// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
+// iterations, size, warmupSeconds, filter);
+
final ConcurrentSkipListMap<Integer,Integer> m
= new ConcurrentSkipListMap<Integer,Integer>();
- final Vector<Integer> v = new Vector<Integer>(size);
final ArrayList<Integer> al = new ArrayList<Integer>(size);
// Populate collections with random data
- final Random rnd = new Random();
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
for (int i = 0; i < size; i++) {
m.put(rnd.nextInt(size), rnd.nextInt(size));
- v.add(rnd.nextInt(size));
+ al.add(rnd.nextInt(size));
}
- al.addAll(v);
+ final Vector<Integer> v = new Vector<Integer>(al);
+ final ArrayDeque<Integer> ad = new ArrayDeque<Integer>(al);
+ // shuffle ArrayDeque elements so they wrap
+ for (int i = 0, n = rnd.nextInt(size); i < n; i++)
+ ad.addLast(ad.removeFirst());
// Also test "short" collections
final int shortSize = 5;
@@ -222,6 +259,15 @@
for (int j = 0; j < size; ++j)
sum += a[j];
check.sum(sum);}}},
+ new Job("descending array loop") {
+ public void work() throws Throwable {
+ Integer[] a = al.toArray(new Integer[0]);
+ for (int i = 0; i < iterations; i++) {
+ int sum = 0;
+ int size = a.length;
+ for (int j = size - 1; j >= 0; j--)
+ sum += a[j];
+ check.sum(sum);}}},
new Job("Vector get loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
@@ -334,6 +380,13 @@
for (Integer n : al)
sum += n;
check.sum(sum);}}},
+ new Job("ArrayDeque iterate for loop") {
+ public void work() throws Throwable {
+ for (int i = 0; i < iterations; i++) {
+ int sum = 0;
+ for (Integer n : ad)
+ sum += n;
+ check.sum(sum);}}},
new Job("ArrayList descending listIterator loop") {
public void work() throws Throwable {
for (int i = 0; i < iterations; i++) {
@@ -350,6 +403,137 @@
while (it.hasNext())
sum += it.next();
check.sum(sum);}}},
+ new Job("ArrayDeque.descendingIterator() loop") {
+ public void work() throws Throwable {
+ for (int i = 0; i < iterations; i++) {
+ int sum = 0;
+ Iterator<Integer> it = ad.descendingIterator();
+ while (it.hasNext())
+ sum += it.next();
+ check.sum(sum);}}},
+ new Job("ArrayList.forEach") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ al.forEach(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.forEach") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ ad.forEach(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("Vector.forEach") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ v.forEach(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayList.iterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ al.iterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.descendingIterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ ad.descendingIterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.iterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ ad.iterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("Vector.iterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ v.iterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayList.spliterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ al.spliterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.spliterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ ad.spliterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("Vector.spliterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ v.spliterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job("ArrayList.spliterator().tryAdvance()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ Spliterator<Integer> spliterator = al.spliterator();
+ do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.spliterator().tryAdvance()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ Spliterator<Integer> spliterator = ad.spliterator();
+ do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+ check.sum(sum[0]);}}},
+ new Job("Vector.spliterator().tryAdvance()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ Spliterator<Integer> spliterator = v.spliterator();
+ do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+ check.sum(sum[0]);}}},
+ new Job("ArrayList.removeIf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ al.removeIf(n -> { sum[0] += n; return false; });
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.removeIf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ ad.removeIf(n -> { sum[0] += n; return false; });
+ check.sum(sum[0]);}}},
+ new Job("Vector.removeIf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ v.removeIf(n -> { sum[0] += n; return false; });
+ check.sum(sum[0]);}}},
+ new Job("ArrayList subList .removeIf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ List<Integer> sl = asSubList(al);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ sl.removeIf(n -> { sum[0] += n; return false; });
+ check.sum(sum[0]);}}},
new Job("ArrayList subList get loop") {
public void work() throws Throwable {
List<Integer> sl = asSubList(al);
@@ -442,7 +626,61 @@
int sum = 0;
for (Map.Entry<Integer,Integer> e : m.entrySet())
sum += e.getKey();
- deoptimize(sum);}}}
+ deoptimize(sum);}}},
+ new Job("ArrayList.toArray()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ for (Object o : al.toArray())
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job("ArrayList.toArray(a)") {
+ public void work() throws Throwable {
+ Integer[] a = new Integer[size];
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ al.toArray(a);
+ for (Object o : a)
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.toArray()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ for (Object o : ad.toArray())
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job("ArrayDeque.toArray(a)") {
+ public void work() throws Throwable {
+ Integer[] a = new Integer[size];
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ ad.toArray(a);
+ for (Object o : a)
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job("Vector.toArray()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ for (Object o : v.toArray())
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job("Vector.toArray(a)") {
+ public void work() throws Throwable {
+ Integer[] a = new Integer[size];
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ v.toArray(a);
+ for (Object o : a)
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
};
time(filter(filter, jobs));
--- a/jdk/test/java/util/Collection/CollectionDefaults.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/Collection/CollectionDefaults.java Mon Nov 28 23:36:11 2016 -0800
@@ -60,9 +60,19 @@
public static final Predicate<Integer> pEven = x -> 0 == x % 2;
public static final Predicate<Integer> pOdd = x -> 1 == x % 2;
+ private static final int SIZE = 100;
+
private static final List<Function<Collection<Integer>, Collection<Integer>>> TEST_SUPPLIERS = Arrays.asList(
// Collection
ExtendsAbstractCollection<Integer>::new,
+ java.util.ArrayDeque<Integer>::new,
+ java.util.concurrent.ConcurrentLinkedDeque<Integer>::new,
+ java.util.concurrent.ConcurrentLinkedQueue<Integer>::new,
+ java.util.concurrent.LinkedBlockingDeque<Integer>::new,
+ java.util.concurrent.LinkedBlockingQueue<Integer>::new,
+ java.util.concurrent.LinkedTransferQueue<Integer>::new,
+ (coll) -> new java.util.concurrent.ArrayBlockingQueue<Integer>(
+ 3 * SIZE, false, coll),
// Lists
java.util.ArrayList<Integer>::new,
@@ -80,8 +90,6 @@
ExtendsAbstractSet<Integer>::new
);
- private static final int SIZE = 100;
-
@DataProvider(name="setProvider", parallel=true)
public static Iterator<Object[]> setCases() {
final List<Object[]> cases = new LinkedList<>();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Collection/IteratorMicroBenchmark.java Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,404 @@
+/*
+ * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved.
+ * 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.
+ */
+
+/*
+ * @test
+ * @summary micro-benchmark correctness mode
+ * @run main IteratorMicroBenchmark iterations=1 size=8 warmup=0
+ */
+
+import static java.util.stream.Collectors.summingInt;
+
+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;
+import java.util.Deque;
+import java.util.Enumeration;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Spliterator;
+import java.util.Vector;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.LinkedBlockingDeque;
+import java.util.concurrent.LinkedBlockingQueue;
+import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.PriorityBlockingQueue;
+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;
+
+/**
+ * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
+ *
+ * To run this in micro-benchmark mode, simply run as a normal java program.
+ * Be patient; this program runs for a very long time.
+ * For faster runs, restrict execution using command line args.
+ *
+ * This is an interface based version of ArrayList/IteratorMicroBenchmark
+ *
+ * @author Martin Buchholz
+ */
+public class IteratorMicroBenchmark {
+ abstract static class Job {
+ private final String name;
+ public Job(String name) { this.name = name; }
+ public String name() { return name; }
+ public abstract void work() throws Throwable;
+ }
+
+ final int iterations;
+ final int size; // number of elements in collections
+ final double warmupSeconds;
+ final long warmupNanos;
+ final Pattern filter; // select subset of Jobs to run
+ final boolean reverse; // reverse order of Jobs
+ final boolean shuffle; // randomize order of Jobs
+
+ IteratorMicroBenchmark(String[] args) {
+ iterations = intArg(args, "iterations", 10_000);
+ size = intArg(args, "size", 1000);
+ warmupSeconds = doubleArg(args, "warmup", 7.0);
+ filter = patternArg(args, "filter");
+ reverse = booleanArg(args, "reverse");
+ shuffle = booleanArg(args, "shuffle");
+
+ warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+ }
+
+ // --------------- GC finalization infrastructure ---------------
+
+ /** 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(); }});
+ try {
+ for (int i = 0; i < 10; i++) {
+ System.gc();
+ if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+ System.runFinalization(); // try to pick up stragglers
+ return;
+ }
+ }
+ } catch (InterruptedException unexpected) {
+ throw new AssertionError("unexpected InterruptedException");
+ }
+ throw new AssertionError("failed to do a \"full\" gc");
+ }
+
+ /**
+ * Runs each job for long enough that all the runtime compilers
+ * have had plenty of time to warm up, i.e. get around to
+ * compiling everything worth compiling.
+ * Returns array of average times per job per run.
+ */
+ long[] time0(List<Job> jobs) throws Throwable {
+ final int size = jobs.size();
+ long[] nanoss = new long[size];
+ for (int i = 0; i < size; i++) {
+ if (warmupNanos > 0) forceFullGc();
+ Job job = jobs.get(i);
+ long totalTime;
+ int runs = 0;
+ long startTime = System.nanoTime();
+ do { job.work(); runs++; }
+ while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
+ nanoss[i] = totalTime/runs;
+ }
+ return nanoss;
+ }
+
+ void time(List<Job> jobs) throws Throwable {
+ if (warmupNanos > 0) time0(jobs); // Warm up run
+ final int size = jobs.size();
+ final long[] nanoss = time0(jobs); // Real timing run
+ final long[] milliss = new long[size];
+ final double[] ratios = new double[size];
+
+ final String nameHeader = "Method";
+ final String millisHeader = "Millis";
+ final String ratioHeader = "Ratio";
+
+ int nameWidth = nameHeader.length();
+ int millisWidth = millisHeader.length();
+ int ratioWidth = ratioHeader.length();
+
+ for (int i = 0; i < size; i++) {
+ nameWidth = Math.max(nameWidth, jobs.get(i).name().length());
+
+ milliss[i] = nanoss[i]/(1000L * 1000L);
+ millisWidth = Math.max(millisWidth,
+ String.format("%d", milliss[i]).length());
+
+ ratios[i] = (double) nanoss[i] / (double) nanoss[0];
+ ratioWidth = Math.max(ratioWidth,
+ String.format("%.3f", ratios[i]).length());
+ }
+
+ String format = String.format("%%-%ds %%%dd %%%d.3f%%n",
+ nameWidth, millisWidth, ratioWidth);
+ String headerFormat = String.format("%%-%ds %%%ds %%%ds%%n",
+ nameWidth, millisWidth, ratioWidth);
+ System.out.printf(headerFormat, "Method", "Millis", "Ratio");
+
+ // Print out absolute and relative times, calibrated against first job
+ for (int i = 0; i < size; i++)
+ System.out.printf(format, jobs.get(i).name(), milliss[i], ratios[i]);
+ }
+
+ private static String keywordValue(String[] args, String keyword) {
+ for (String arg : args)
+ if (arg.startsWith(keyword))
+ return arg.substring(keyword.length() + 1);
+ return null;
+ }
+
+ private static int intArg(String[] args, String keyword, int defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Integer.parseInt(val);
+ }
+
+ private static double doubleArg(String[] args, String keyword, double defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Double.parseDouble(val);
+ }
+
+ private static Pattern patternArg(String[] args, String keyword) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? null : Pattern.compile(val);
+ }
+
+ private static boolean booleanArg(String[] args, String keyword) {
+ String val = keywordValue(args, keyword);
+ if (val == null || val.equals("false")) return false;
+ if (val.equals("true")) return true;
+ throw new IllegalArgumentException(val);
+ }
+
+ private static List<Job> filter(Pattern filter, List<Job> jobs) {
+ if (filter == null) return jobs;
+ ArrayList<Job> newJobs = new ArrayList<>();
+ for (Job job : jobs)
+ if (filter.matcher(job.name()).find())
+ newJobs.add(job);
+ return newJobs;
+ }
+
+ private static void deoptimize(int sum) {
+ if (sum == 42)
+ System.out.println("the answer");
+ }
+
+ private static <T> List<T> asSubList(List<T> list) {
+ return list.subList(0, list.size());
+ }
+
+ private static <T> Iterable<T> backwards(final List<T> list) {
+ return new Iterable<T>() {
+ public Iterator<T> iterator() {
+ return new Iterator<T>() {
+ final ListIterator<T> it = list.listIterator(list.size());
+ public boolean hasNext() { return it.hasPrevious(); }
+ public T next() { return it.previous(); }
+ public void remove() { it.remove(); }};}};
+ }
+
+ // Checks for correctness *and* prevents loop optimizations
+ class Check {
+ private int sum;
+ public void sum(int sum) {
+ if (this.sum == 0)
+ this.sum = sum;
+ if (this.sum != sum)
+ throw new AssertionError("Sum mismatch");
+ }
+ }
+ volatile Check check = new Check();
+
+ public static void main(String[] args) throws Throwable {
+ new IteratorMicroBenchmark(args).run();
+ }
+
+ void run() throws Throwable {
+// System.out.printf(
+// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
+// iterations, size, warmupSeconds, filter);
+
+ final ArrayList<Integer> al = new ArrayList<Integer>(size);
+
+ // Populate collections with random data
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ for (int i = 0; i < size; i++)
+ al.add(rnd.nextInt(size));
+
+ final ArrayDeque<Integer> ad = new ArrayDeque<>(al);
+ final ArrayBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(al.size());
+ abq.addAll(al);
+
+ // shuffle circular array elements so they wrap
+ for (int i = 0, n = rnd.nextInt(size); i < n; i++) {
+ ad.addLast(ad.removeFirst());
+ abq.add(abq.remove());
+ }
+
+ ArrayList<Job> jobs = new ArrayList<>(Arrays.asList());
+
+ List.of(al, ad, abq,
+ new LinkedList<>(al),
+ new PriorityQueue<>(al),
+ new Vector<>(al),
+ new ConcurrentLinkedQueue<>(al),
+ new ConcurrentLinkedDeque<>(al),
+ new LinkedBlockingQueue<>(al),
+ new LinkedBlockingDeque<>(al),
+ new LinkedTransferQueue<>(al),
+ new PriorityBlockingQueue<>(al))
+ .stream()
+ .forEach(x -> {
+ jobs.addAll(collectionJobs(x));
+ if (x instanceof Deque)
+ jobs.addAll(dequeJobs((Deque<Integer>)x));
+ });
+
+ if (reverse) Collections.reverse(jobs);
+ if (shuffle) Collections.shuffle(jobs);
+
+ time(filter(filter, jobs));
+ }
+
+ List<Job> collectionJobs(Collection<Integer> x) {
+ String klazz = x.getClass().getSimpleName();
+ return List.of(
+ new Job(klazz + " iterate for loop") {
+ public void work() throws Throwable {
+ for (int i = 0; i < iterations; i++) {
+ int sum = 0;
+ for (Integer n : x)
+ sum += n;
+ check.sum(sum);}}},
+ new Job(klazz + " .iterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.iterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .spliterator().tryAdvance()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ Spliterator<Integer> spliterator = x.spliterator();
+ do {} while (spliterator.tryAdvance(n -> sum[0] += n));
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .spliterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.spliterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .removeIf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.removeIf(n -> { sum[0] += n; return false; });
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .forEach") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.forEach(n -> sum[0] += n);
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .toArray()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ for (Object o : x.toArray())
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .toArray(a)") {
+ public void work() throws Throwable {
+ Integer[] a = new Integer[x.size()];
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.toArray(a);
+ for (Object o : a)
+ sum[0] += (Integer) o;
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .toArray(empty)") {
+ public void work() throws Throwable {
+ Integer[] empty = new Integer[0];
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ for (Integer o : x.toArray(empty))
+ sum[0] += o;
+ check.sum(sum[0]);}}},
+ new Job(klazz + " .stream().collect") {
+ public void work() throws Throwable {
+ for (int i = 0; i < iterations; i++) {
+ check.sum(x.stream()
+ .collect(summingInt(e -> e)));}}},
+ new Job(klazz + " .parallelStream().collect") {
+ public void work() throws Throwable {
+ for (int i = 0; i < iterations; i++) {
+ check.sum(x.parallelStream()
+ .collect(summingInt(e -> e)));}}});
+ }
+
+ List<Job> dequeJobs(Deque<Integer> x) {
+ String klazz = x.getClass().getSimpleName();
+ return List.of(
+ new Job(klazz + " .descendingIterator() loop") {
+ public void work() throws Throwable {
+ for (int i = 0; i < iterations; i++) {
+ int sum = 0;
+ Iterator<Integer> it = x.descendingIterator();
+ while (it.hasNext())
+ sum += it.next();
+ check.sum(sum);}}},
+ new Job(klazz + " .descendingIterator().forEachRemaining()") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.descendingIterator().forEachRemaining(n -> sum[0] += n);
+ check.sum(sum[0]);}}});
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Collection/RemoveMicroBenchmark.java Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,504 @@
+/*
+ * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved.
+ * 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.
+ */
+
+/*
+ * @test
+ * @summary micro-benchmark correctness mode
+ * @run main RemoveMicroBenchmark iterations=1 size=8 warmup=0
+ */
+
+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;
+import java.util.Deque;
+import java.util.Enumeration;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.Spliterator;
+import java.util.Vector;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.BlockingDeque;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.LinkedBlockingDeque;
+import java.util.concurrent.LinkedBlockingQueue;
+import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.PriorityBlockingQueue;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.regex.Pattern;
+import java.util.function.Supplier;
+
+/**
+ * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
+ *
+ * To run this in micro-benchmark mode, simply run as a normal java program.
+ * Be patient; this program runs for a very long time.
+ * For faster runs, restrict execution using command line args.
+ *
+ * @author Martin Buchholz
+ */
+public class RemoveMicroBenchmark {
+ abstract static class Job {
+ private final String name;
+ public Job(String name) { this.name = name; }
+ public String name() { return name; }
+ public abstract void work() throws Throwable;
+ }
+
+ final int iterations;
+ final int size; // number of elements in collections
+ final double warmupSeconds;
+ final long warmupNanos;
+ final Pattern filter; // select subset of Jobs to run
+ final boolean reverse; // reverse order of Jobs
+ final boolean shuffle; // randomize order of Jobs
+
+ RemoveMicroBenchmark(String[] args) {
+ iterations = intArg(args, "iterations", 10_000);
+ size = intArg(args, "size", 1000);
+ warmupSeconds = doubleArg(args, "warmup", 7.0);
+ filter = patternArg(args, "filter");
+ reverse = booleanArg(args, "reverse");
+ shuffle = booleanArg(args, "shuffle");
+
+ warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+ }
+
+ // --------------- GC finalization infrastructure ---------------
+
+ /** 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(); }});
+ try {
+ for (int i = 0; i < 10; i++) {
+ System.gc();
+ if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
+ System.runFinalization(); // try to pick up stragglers
+ return;
+ }
+ }
+ } catch (InterruptedException unexpected) {
+ throw new AssertionError("unexpected InterruptedException");
+ }
+ throw new AssertionError("failed to do a \"full\" gc");
+ }
+
+ /**
+ * Runs each job for long enough that all the runtime compilers
+ * have had plenty of time to warm up, i.e. get around to
+ * compiling everything worth compiling.
+ * Returns array of average times per job per run.
+ */
+ long[] time0(List<Job> jobs) throws Throwable {
+ final int size = jobs.size();
+ long[] nanoss = new long[size];
+ for (int i = 0; i < size; i++) {
+ if (warmupNanos > 0) forceFullGc();
+ Job job = jobs.get(i);
+ long totalTime;
+ int runs = 0;
+ long startTime = System.nanoTime();
+ do { job.work(); runs++; }
+ while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
+ nanoss[i] = totalTime/runs;
+ }
+ return nanoss;
+ }
+
+ void time(List<Job> jobs) throws Throwable {
+ if (warmupNanos > 0) time0(jobs); // Warm up run
+ final int size = jobs.size();
+ final long[] nanoss = time0(jobs); // Real timing run
+ final long[] milliss = new long[size];
+ final double[] ratios = new double[size];
+
+ final String nameHeader = "Method";
+ final String millisHeader = "Millis";
+ final String ratioHeader = "Ratio";
+
+ int nameWidth = nameHeader.length();
+ int millisWidth = millisHeader.length();
+ int ratioWidth = ratioHeader.length();
+
+ for (int i = 0; i < size; i++) {
+ nameWidth = Math.max(nameWidth, jobs.get(i).name().length());
+
+ milliss[i] = nanoss[i]/(1000L * 1000L);
+ millisWidth = Math.max(millisWidth,
+ String.format("%d", milliss[i]).length());
+
+ ratios[i] = (double) nanoss[i] / (double) nanoss[0];
+ ratioWidth = Math.max(ratioWidth,
+ String.format("%.3f", ratios[i]).length());
+ }
+
+ String format = String.format("%%-%ds %%%dd %%%d.3f%%n",
+ nameWidth, millisWidth, ratioWidth);
+ String headerFormat = String.format("%%-%ds %%%ds %%%ds%%n",
+ nameWidth, millisWidth, ratioWidth);
+ System.out.printf(headerFormat, "Method", "Millis", "Ratio");
+
+ // Print out absolute and relative times, calibrated against first job
+ for (int i = 0; i < size; i++)
+ System.out.printf(format, jobs.get(i).name(), milliss[i], ratios[i]);
+ }
+
+ private static String keywordValue(String[] args, String keyword) {
+ for (String arg : args)
+ if (arg.startsWith(keyword))
+ return arg.substring(keyword.length() + 1);
+ return null;
+ }
+
+ private static int intArg(String[] args, String keyword, int defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Integer.parseInt(val);
+ }
+
+ private static double doubleArg(String[] args, String keyword, double defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Double.parseDouble(val);
+ }
+
+ private static Pattern patternArg(String[] args, String keyword) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? null : Pattern.compile(val);
+ }
+
+ private static boolean booleanArg(String[] args, String keyword) {
+ String val = keywordValue(args, keyword);
+ if (val == null || val.equals("false")) return false;
+ if (val.equals("true")) return true;
+ throw new IllegalArgumentException(val);
+ }
+
+ private static List<Job> filter(Pattern filter, List<Job> jobs) {
+ if (filter == null) return jobs;
+ ArrayList<Job> newJobs = new ArrayList<>();
+ for (Job job : jobs)
+ if (filter.matcher(job.name()).find())
+ newJobs.add(job);
+ return newJobs;
+ }
+
+ private static void deoptimize(int sum) {
+ if (sum == 42)
+ System.out.println("the answer");
+ }
+
+ private static <T> List<T> asSubList(List<T> list) {
+ return list.subList(0, list.size());
+ }
+
+ private static <T> Iterable<T> backwards(final List<T> list) {
+ return new Iterable<T>() {
+ public Iterator<T> iterator() {
+ return new Iterator<T>() {
+ final ListIterator<T> it = list.listIterator(list.size());
+ public boolean hasNext() { return it.hasPrevious(); }
+ public T next() { return it.previous(); }
+ public void remove() { it.remove(); }};}};
+ }
+
+ // Checks for correctness *and* prevents loop optimizations
+ class Check {
+ private int sum;
+ public void sum(int sum) {
+ if (this.sum == 0)
+ this.sum = sum;
+ if (this.sum != sum)
+ throw new AssertionError("Sum mismatch");
+ }
+ }
+ volatile Check check = new Check();
+
+ public static void main(String[] args) throws Throwable {
+ new RemoveMicroBenchmark(args).run();
+ }
+
+ void run() throws Throwable {
+// System.out.printf(
+// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
+// iterations, size, warmupSeconds, filter);
+
+ final ArrayList<Integer> al = new ArrayList<Integer>(size);
+
+ // Populate collections with random data
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ for (int i = 0; i < size; i++)
+ al.add(rnd.nextInt(size));
+
+ ArrayList<Job> jobs = new ArrayList<>();
+
+ List.<Collection<Integer>>of(
+ new ArrayList<>(),
+ new LinkedList<>(),
+ new Vector<>(),
+ new ArrayDeque<>(),
+ new PriorityQueue<>(),
+ new ArrayBlockingQueue<>(al.size()),
+ new ConcurrentLinkedQueue<>(),
+ new ConcurrentLinkedDeque<>(),
+ new LinkedBlockingQueue<>(),
+ new LinkedBlockingDeque<>(),
+ new LinkedTransferQueue<>(),
+ new PriorityBlockingQueue<>())
+ .stream().forEach(
+ x -> {
+ String klazz = x.getClass().getSimpleName();
+ jobs.addAll(collectionJobs(klazz, () -> x, al));
+ if (x instanceof Queue) {
+ Queue<Integer> queue = (Queue<Integer>) x;
+ jobs.addAll(queueJobs(klazz, () -> queue, al));
+ }
+ if (x instanceof Deque) {
+ Deque<Integer> deque = (Deque<Integer>) x;
+ jobs.addAll(dequeJobs(klazz, () -> deque, al));
+ }
+ if (x instanceof BlockingQueue) {
+ BlockingQueue<Integer> q = (BlockingQueue<Integer>) x;
+ jobs.addAll(blockingQueueJobs(klazz, () -> q, al));
+ }
+ if (x instanceof BlockingDeque) {
+ BlockingDeque<Integer> q = (BlockingDeque<Integer>) x;
+ jobs.addAll(blockingDequeJobs(klazz, () -> q, al));
+ }
+ if (x instanceof List) {
+ List<Integer> list = (List<Integer>) x;
+ jobs.addAll(
+ collectionJobs(
+ klazz + " subList",
+ () -> list.subList(0, x.size()),
+ al));
+ }
+ });
+
+ if (reverse) Collections.reverse(jobs);
+ if (shuffle) Collections.shuffle(jobs);
+
+ time(filter(filter, jobs));
+ }
+
+ Collection<Integer> universeRecorder(int[] sum) {
+ return new ArrayList<>() {
+ public boolean contains(Object x) {
+ sum[0] += (Integer) x;
+ return true;
+ }};
+ }
+
+ Collection<Integer> emptyRecorder(int[] sum) {
+ return new ArrayList<>() {
+ public boolean contains(Object x) {
+ sum[0] += (Integer) x;
+ return false;
+ }};
+ }
+
+ List<Job> collectionJobs(
+ String description,
+ Supplier<Collection<Integer>> supplier,
+ ArrayList<Integer> al) {
+ return List.of(
+ new Job(description + " .removeIf") {
+ public void work() throws Throwable {
+ Collection<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ x.removeIf(n -> { sum[0] += n; return true; });
+ check.sum(sum[0]);}}},
+ new Job(description + " .removeAll") {
+ public void work() throws Throwable {
+ Collection<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ Collection<Integer> universe = universeRecorder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ x.removeAll(universe);
+ check.sum(sum[0]);}}},
+ new Job(description + " .retainAll") {
+ public void work() throws Throwable {
+ Collection<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ Collection<Integer> empty = emptyRecorder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ x.retainAll(empty);
+ check.sum(sum[0]);}}},
+ new Job(description + " Iterator.remove") {
+ public void work() throws Throwable {
+ Collection<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ Iterator<Integer> it = x.iterator();
+ while (it.hasNext()) {
+ sum[0] += it.next();
+ it.remove();
+ }
+ check.sum(sum[0]);}}},
+ new Job(description + " clear") {
+ public void work() throws Throwable {
+ Collection<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ x.forEach(e -> sum[0] += e);
+ x.clear();
+ check.sum(sum[0]);}}});
+ }
+
+ List<Job> queueJobs(
+ String description,
+ Supplier<Queue<Integer>> supplier,
+ ArrayList<Integer> al) {
+ return List.of(
+ new Job(description + " poll()") {
+ public void work() throws Throwable {
+ Queue<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ for (Integer e; (e = x.poll()) != null; )
+ sum[0] += e;
+ check.sum(sum[0]);}}});
+ }
+
+ List<Job> dequeJobs(
+ String description,
+ Supplier<Deque<Integer>> supplier,
+ ArrayList<Integer> al) {
+ return List.of(
+ new Job(description + " descendingIterator().remove") {
+ public void work() throws Throwable {
+ Deque<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ Iterator<Integer> it = x.descendingIterator();
+ while (it.hasNext()) {
+ sum[0] += it.next();
+ it.remove();
+ }
+ check.sum(sum[0]);}}},
+ new Job(description + " pollFirst()") {
+ public void work() throws Throwable {
+ Deque<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ for (Integer e; (e = x.pollFirst()) != null; )
+ sum[0] += e;
+ check.sum(sum[0]);}}},
+ new Job(description + " pollLast()") {
+ public void work() throws Throwable {
+ Deque<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ for (Integer e; (e = x.pollLast()) != null; )
+ sum[0] += e;
+ check.sum(sum[0]);}}});
+ }
+
+ List<Job> blockingQueueJobs(
+ String description,
+ Supplier<BlockingQueue<Integer>> supplier,
+ ArrayList<Integer> al) {
+ return List.of(
+ new Job(description + " drainTo(sink)") {
+ public void work() throws Throwable {
+ BlockingQueue<Integer> x = supplier.get();
+ ArrayList<Integer> sink = new ArrayList<>();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ sink.clear();
+ x.addAll(al);
+ x.drainTo(sink);
+ sink.forEach(e -> sum[0] += e);
+ check.sum(sum[0]);}}},
+ new Job(description + " drainTo(sink, n)") {
+ public void work() throws Throwable {
+ BlockingQueue<Integer> x = supplier.get();
+ ArrayList<Integer> sink = new ArrayList<>();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ sink.clear();
+ x.addAll(al);
+ x.drainTo(sink, al.size());
+ sink.forEach(e -> sum[0] += e);
+ check.sum(sum[0]);}}});
+ }
+
+ List<Job> blockingDequeJobs(
+ String description,
+ Supplier<BlockingDeque<Integer>> supplier,
+ ArrayList<Integer> al) {
+ return List.of(
+ new Job(description + " timed pollFirst()") {
+ public void work() throws Throwable {
+ BlockingDeque<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ for (Integer e; (e = x.pollFirst(0L, TimeUnit.DAYS)) != null; )
+ sum[0] += e;
+ check.sum(sum[0]);}}},
+ new Job(description + " timed pollLast()") {
+ public void work() throws Throwable {
+ BlockingDeque<Integer> x = supplier.get();
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(al);
+ for (Integer e; (e = x.pollLast(0L, TimeUnit.DAYS)) != null; )
+ sum[0] += e;
+ check.sum(sum[0]);}}});
+ }
+}
--- a/jdk/test/java/util/Vector/LastIndexOf.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/Vector/LastIndexOf.java Mon Nov 28 23:36:11 2016 -0800
@@ -22,10 +22,10 @@
*/
/*
- @test
- @bug 4271588
- @summary Vector.lastIndex(Object, int) used to let you look outside the
- valid range in the backing array
+ * @test
+ * @bug 4271588
+ * @summary Vector.lastIndex(Object, int) used to let you look outside the
+ * valid range in the backing array
*/
import java.util.*;
--- a/jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/ArrayBlockingQueue/IteratorConsistency.java Mon Nov 28 23:36:11 2016 -0800
@@ -42,9 +42,9 @@
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
-import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ThreadLocalRandom;
/*
* @test
@@ -53,12 +53,12 @@
*/
/**
- * Highly coupled to the implementation of ArrayBlockingQueue.
+ * Tightly coupled to the implementation of ArrayBlockingQueue.
* Uses reflection to inspect queue and iterator state.
*/
@SuppressWarnings({"unchecked", "rawtypes"})
public class IteratorConsistency {
- final Random rnd = new Random();
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
final int CAPACITY = 20;
Field itrsField;
Field itemsField;
@@ -144,6 +144,10 @@
check(!it.hasNext());
check(isDetached(it));
}
+ if (rnd.nextBoolean()) {
+ it.forEachRemaining(e -> { throw new AssertionError(); });
+ checkDetached(it);
+ }
if (rnd.nextBoolean())
try { it.next(); fail("should throw"); }
catch (NoSuchElementException success) {}
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java Mon Nov 28 23:36:11 2016 -0800
@@ -44,7 +44,6 @@
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
-import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ConcurrentLinkedDeque;
@@ -52,10 +51,11 @@
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.ThreadLocalRandom;
@SuppressWarnings({"unchecked", "rawtypes"})
public class IteratorWeakConsistency {
- final Random rnd = new Random();
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
void test(String[] args) throws Throwable {
test(new LinkedBlockingQueue());
@@ -72,6 +72,9 @@
if (rnd.nextBoolean()) {
check(!it.hasNext());
}
+ if (rnd.nextBoolean()) {
+ it.forEachRemaining(e -> { throw new AssertionError(); });
+ }
if (rnd.nextBoolean())
try { it.next(); fail("should throw"); }
catch (NoSuchElementException success) {}
--- a/jdk/test/java/util/concurrent/tck/ArrayBlockingQueueTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/ArrayBlockingQueueTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -38,6 +38,7 @@
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
+import java.util.Collections;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
@@ -46,45 +47,78 @@
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;
+import java.util.concurrent.ThreadLocalRandom;
import junit.framework.Test;
public class ArrayBlockingQueueTest extends JSR166TestCase {
- public static class Fair extends BlockingQueueTest {
- protected BlockingQueue emptyCollection() {
- return new ArrayBlockingQueue(SIZE, true);
- }
- }
-
- public static class NonFair extends BlockingQueueTest {
- protected BlockingQueue emptyCollection() {
- return new ArrayBlockingQueue(SIZE, false);
- }
- }
-
public static void main(String[] args) {
main(suite(), args);
}
public static Test suite() {
- return newTestSuite(ArrayBlockingQueueTest.class,
- new Fair().testSuite(),
- new NonFair().testSuite());
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return ArrayBlockingQueue.class; }
+ public Collection emptyCollection() {
+ boolean fair = ThreadLocalRandom.current().nextBoolean();
+ return populatedQueue(0, SIZE, 2 * SIZE, fair);
+ }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return true; }
+ public boolean permitsNulls() { return false; }
+ }
+
+ return newTestSuite(
+ ArrayBlockingQueueTest.class,
+ new Fair().testSuite(),
+ new NonFair().testSuite(),
+ CollectionTest.testSuite(new Implementation()));
+ }
+
+ public static class Fair extends BlockingQueueTest {
+ protected BlockingQueue emptyCollection() {
+ return populatedQueue(0, SIZE, 2 * SIZE, true);
+ }
+ }
+
+ public static class NonFair extends BlockingQueueTest {
+ protected BlockingQueue emptyCollection() {
+ return populatedQueue(0, SIZE, 2 * SIZE, false);
+ }
}
/**
* Returns a new queue of given size containing consecutive
- * Integers 0 ... n.
+ * Integers 0 ... n - 1.
*/
- private ArrayBlockingQueue<Integer> populatedQueue(int n) {
- ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<Integer>(n);
+ static ArrayBlockingQueue<Integer> populatedQueue(int n) {
+ return populatedQueue(n, n, n, false);
+ }
+
+ /**
+ * Returns a new queue of given size containing consecutive
+ * Integers 0 ... n - 1, with given capacity range and fairness.
+ */
+ static ArrayBlockingQueue<Integer> populatedQueue(
+ int size, int minCapacity, int maxCapacity, boolean fair) {
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ int capacity = rnd.nextInt(minCapacity, maxCapacity + 1);
+ ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);
assertTrue(q.isEmpty());
- for (int i = 0; i < n; i++)
- assertTrue(q.offer(new Integer(i)));
- assertFalse(q.isEmpty());
- assertEquals(0, q.remainingCapacity());
- assertEquals(n, q.size());
+ // shuffle circular array elements so they wrap
+ {
+ int n = rnd.nextInt(capacity);
+ for (int i = 0; i < n; i++) q.add(42);
+ for (int i = 0; i < n; i++) q.remove();
+ }
+ for (int i = 0; i < size; i++)
+ assertTrue(q.offer((Integer) i));
+ assertEquals(size == 0, q.isEmpty());
+ assertEquals(capacity - size, q.remainingCapacity());
+ assertEquals(size, q.size());
+ if (size > 0)
+ assertEquals((Integer) 0, q.peek());
return q;
}
@@ -98,17 +132,25 @@
/**
* Constructor throws IAE if capacity argument nonpositive
*/
- public void testConstructor2() {
- try {
- new ArrayBlockingQueue(0);
- shouldThrow();
- } catch (IllegalArgumentException success) {}
+ public void testConstructor_nonPositiveCapacity() {
+ for (int i : new int[] { 0, -1, Integer.MIN_VALUE }) {
+ try {
+ new ArrayBlockingQueue(i);
+ shouldThrow();
+ } catch (IllegalArgumentException success) {}
+ for (boolean fair : new boolean[] { true, false }) {
+ try {
+ new ArrayBlockingQueue(i, fair);
+ shouldThrow();
+ } catch (IllegalArgumentException success) {}
+ }
+ }
}
/**
* Initializing from null Collection throws NPE
*/
- public void testConstructor3() {
+ public void testConstructor_nullCollection() {
try {
new ArrayBlockingQueue(1, true, null);
shouldThrow();
@@ -143,13 +185,13 @@
/**
* Initializing from too large collection throws IAE
*/
- public void testConstructor6() {
- Integer[] ints = new Integer[SIZE];
- for (int i = 0; i < SIZE; ++i)
- ints[i] = i;
- Collection<Integer> elements = Arrays.asList(ints);
+ public void testConstructor_collectionTooLarge() {
+ // just barely fits - succeeds
+ new ArrayBlockingQueue(SIZE, false,
+ Collections.nCopies(SIZE, ""));
try {
- new ArrayBlockingQueue(SIZE - 1, false, elements);
+ new ArrayBlockingQueue(SIZE - 1, false,
+ Collections.nCopies(SIZE, ""));
shouldThrow();
} catch (IllegalArgumentException success) {}
}
@@ -171,12 +213,12 @@
* Queue transitions from empty to full when elements added
*/
public void testEmptyFull() {
- ArrayBlockingQueue q = new ArrayBlockingQueue(2);
+ BlockingQueue q = populatedQueue(0, 2, 2, false);
assertTrue(q.isEmpty());
assertEquals(2, q.remainingCapacity());
q.add(one);
assertFalse(q.isEmpty());
- q.add(two);
+ assertTrue(q.offer(two));
assertFalse(q.isEmpty());
assertEquals(0, q.remainingCapacity());
assertFalse(q.offer(three));
@@ -186,15 +228,18 @@
* remainingCapacity decreases on add, increases on remove
*/
public void testRemainingCapacity() {
- BlockingQueue q = populatedQueue(SIZE);
- for (int i = 0; i < SIZE; ++i) {
- assertEquals(i, q.remainingCapacity());
- assertEquals(SIZE, q.size() + q.remainingCapacity());
+ int size = ThreadLocalRandom.current().nextInt(1, SIZE);
+ BlockingQueue q = populatedQueue(size, size, 2 * size, false);
+ int spare = q.remainingCapacity();
+ int capacity = spare + size;
+ for (int i = 0; i < size; i++) {
+ assertEquals(spare + i, q.remainingCapacity());
+ assertEquals(capacity, q.size() + q.remainingCapacity());
assertEquals(i, q.remove());
}
- for (int i = 0; i < SIZE; ++i) {
- assertEquals(SIZE - i, q.remainingCapacity());
- assertEquals(SIZE, q.size() + q.remainingCapacity());
+ for (int i = 0; i < size; i++) {
+ assertEquals(capacity - i, q.remainingCapacity());
+ assertEquals(capacity, q.size() + q.remainingCapacity());
assertTrue(q.add(i));
}
}
@@ -213,12 +258,10 @@
*/
public void testAdd() {
ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);
- for (int i = 0; i < SIZE; ++i) {
- assertTrue(q.add(new Integer(i)));
- }
+ for (int i = 0; i < SIZE; i++) assertTrue(q.add((Integer) i));
assertEquals(0, q.remainingCapacity());
try {
- q.add(new Integer(SIZE));
+ q.add((Integer) SIZE);
shouldThrow();
} catch (IllegalStateException success) {}
}
@@ -252,13 +295,17 @@
/**
* addAll throws ISE if not enough room
*/
- public void testAddAll4() {
- ArrayBlockingQueue q = new ArrayBlockingQueue(1);
- Integer[] ints = new Integer[SIZE];
- for (int i = 0; i < SIZE; ++i)
- ints[i] = new Integer(i);
+ public void testAddAll_insufficientSpace() {
+ int size = ThreadLocalRandom.current().nextInt(1, SIZE);
+ ArrayBlockingQueue q = populatedQueue(0, size, size, false);
+ // Just fits:
+ q.addAll(populatedQueue(size, size, 2 * size, false));
+ assertEquals(0, q.remainingCapacity());
+ assertEquals(size, q.size());
+ assertEquals(0, q.peek());
try {
- q.addAll(Arrays.asList(ints));
+ q = populatedQueue(0, size, size, false);
+ q.addAll(Collections.nCopies(size + 1, 42));
shouldThrow();
} catch (IllegalStateException success) {}
}
@@ -545,8 +592,10 @@
* contains(x) reports true when elements added but not yet removed
*/
public void testContains() {
- ArrayBlockingQueue q = populatedQueue(SIZE);
- for (int i = 0; i < SIZE; ++i) {
+ int size = ThreadLocalRandom.current().nextInt(1, SIZE);
+ ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);
+ assertFalse(q.contains(null));
+ for (int i = 0; i < size; ++i) {
assertTrue(q.contains(new Integer(i)));
assertEquals(i, q.poll());
assertFalse(q.contains(new Integer(i)));
@@ -557,11 +606,13 @@
* clear removes all elements
*/
public void testClear() {
- ArrayBlockingQueue q = populatedQueue(SIZE);
+ int size = ThreadLocalRandom.current().nextInt(1, 5);
+ ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);
+ int capacity = size + q.remainingCapacity();
q.clear();
assertTrue(q.isEmpty());
assertEquals(0, q.size());
- assertEquals(SIZE, q.remainingCapacity());
+ assertEquals(capacity, q.remainingCapacity());
q.add(one);
assertFalse(q.isEmpty());
assertTrue(q.contains(one));
@@ -618,103 +669,75 @@
}
}
- void checkToArray(ArrayBlockingQueue q) {
+ void checkToArray(ArrayBlockingQueue<Integer> q) {
int size = q.size();
- Object[] o = q.toArray();
- assertEquals(size, o.length);
+ Object[] a1 = q.toArray();
+ assertEquals(size, a1.length);
+ Integer[] a2 = q.toArray(new Integer[0]);
+ assertEquals(size, a2.length);
+ Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]);
+ assertEquals(size, a3.length);
+ Integer[] a4 = new Integer[size];
+ assertSame(a4, q.toArray(a4));
+ Integer[] a5 = new Integer[size + 1];
+ Arrays.fill(a5, 42);
+ assertSame(a5, q.toArray(a5));
+ Integer[] a6 = new Integer[size + 2];
+ Arrays.fill(a6, 42);
+ assertSame(a6, q.toArray(a6));
+ Object[][] as = { a1, a2, a3, a4, a5, a6 };
+ for (Object[] a : as) {
+ if (a.length > size) assertNull(a[size]);
+ if (a.length > size + 1) assertEquals(42, a[size + 1]);
+ }
Iterator it = q.iterator();
+ Integer s = q.peek();
for (int i = 0; i < size; i++) {
Integer x = (Integer) it.next();
- assertEquals((Integer)o[0] + i, (int) x);
- assertSame(o[i], x);
+ assertEquals(s + i, (int) x);
+ for (Object[] a : as)
+ assertSame(a1[i], x);
}
}
/**
- * toArray() contains all elements in FIFO order
+ * toArray() and toArray(a) contain all elements in FIFO order
*/
public void testToArray() {
- ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);
- for (int i = 0; i < SIZE; i++) {
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ final int size = rnd.nextInt(6);
+ final int capacity = Math.max(1, size + rnd.nextInt(size + 1));
+ ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);
+ for (int i = 0; i < size; i++) {
checkToArray(q);
q.add(i);
}
// Provoke wraparound
- for (int i = 0; i < SIZE; i++) {
- checkToArray(q);
- assertEquals(i, q.poll());
+ int added = size * 2;
+ for (int i = 0; i < added; i++) {
checkToArray(q);
- q.add(SIZE + i);
- }
- for (int i = 0; i < SIZE; i++) {
- checkToArray(q);
- assertEquals(SIZE + i, q.poll());
+ assertEquals((Integer) i, q.poll());
+ q.add(size + i);
}
- }
-
- void checkToArray2(ArrayBlockingQueue q) {
- int size = q.size();
- Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
- Integer[] a2 = new Integer[size];
- Integer[] a3 = new Integer[size + 2];
- if (size > 0) Arrays.fill(a1, 42);
- Arrays.fill(a2, 42);
- Arrays.fill(a3, 42);
- Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
- Integer[] b2 = (Integer[]) q.toArray(a2);
- Integer[] b3 = (Integer[]) q.toArray(a3);
- assertSame(a2, b2);
- assertSame(a3, b3);
- Iterator it = q.iterator();
for (int i = 0; i < size; i++) {
- Integer x = (Integer) it.next();
- assertSame(b1[i], x);
- assertEquals(b1[0] + i, (int) x);
- assertSame(b2[i], x);
- assertSame(b3[i], x);
- }
- assertNull(a3[size]);
- assertEquals(42, (int) a3[size + 1]);
- if (size > 0) {
- assertNotSame(a1, b1);
- assertEquals(size, b1.length);
- for (int i = 0; i < a1.length; i++) {
- assertEquals(42, (int) a1[i]);
- }
- }
- }
-
- /**
- * toArray(a) contains all elements in FIFO order
- */
- public void testToArray2() {
- ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);
- for (int i = 0; i < SIZE; i++) {
- checkToArray2(q);
- q.add(i);
- }
- // Provoke wraparound
- for (int i = 0; i < SIZE; i++) {
- checkToArray2(q);
- assertEquals(i, q.poll());
- checkToArray2(q);
- q.add(SIZE + i);
- }
- for (int i = 0; i < SIZE; i++) {
- checkToArray2(q);
- assertEquals(SIZE + i, q.poll());
+ checkToArray(q);
+ assertEquals((Integer) (added + i), q.poll());
}
}
/**
* toArray(incompatible array type) throws ArrayStoreException
*/
- public void testToArray1_BadArg() {
+ public void testToArray_incompatibleArrayType() {
ArrayBlockingQueue q = populatedQueue(SIZE);
try {
q.toArray(new String[10]);
shouldThrow();
} catch (ArrayStoreException success) {}
+ try {
+ q.toArray(new String[0]);
+ shouldThrow();
+ } catch (ArrayStoreException success) {}
}
/**
@@ -943,8 +966,8 @@
*/
public void testNeverContainsNull() {
Collection<?>[] qs = {
- new ArrayBlockingQueue<Object>(10),
- populatedQueue(2),
+ populatedQueue(0, 1, 10, false),
+ populatedQueue(2, 2, 10, true),
};
for (Collection<?> q : qs) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/ArrayDeque8Test.java Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,125 @@
+/*
+ * 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.ArrayDeque;
+import java.util.Collections;
+import java.util.Spliterator;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class ArrayDeque8Test extends JSR166TestCase {
+ public static void main(String[] args) {
+ main(suite(), args);
+ }
+
+ public static Test suite() {
+ return newTestSuite(ArrayDeque8Test.class);
+ }
+
+ /**
+ * Spliterator.getComparator always throws IllegalStateException
+ */
+ public void testSpliterator_getComparator() {
+ assertThrows(IllegalStateException.class,
+ () -> new ArrayDeque().spliterator().getComparator());
+ }
+
+ /**
+ * Spliterator characteristics are as advertised
+ */
+ public void testSpliterator_characteristics() {
+ ArrayDeque q = new ArrayDeque();
+ Spliterator s = q.spliterator();
+ int characteristics = s.characteristics();
+ int required = Spliterator.NONNULL
+ | Spliterator.ORDERED
+ | Spliterator.SIZED
+ | Spliterator.SUBSIZED;
+ assertEquals(required, characteristics & required);
+ assertTrue(s.hasCharacteristics(required));
+ assertEquals(0, characteristics
+ & (Spliterator.CONCURRENT
+ | Spliterator.DISTINCT
+ | Spliterator.IMMUTABLE
+ | Spliterator.SORTED));
+ }
+
+ /**
+ * Handle capacities near Integer.MAX_VALUE.
+ * ant -Dvmoptions='-Xms28g -Xmx28g' -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ArrayDeque8Test -Djsr166.methodFilter=testHugeCapacity tck
+ */
+ public void testHugeCapacity() {
+ if (! (testImplementationDetails
+ && expensiveTests
+ && Runtime.getRuntime().maxMemory() > 24L * (1 << 30)))
+ return;
+
+ final Integer e = 42;
+ final int maxArraySize = Integer.MAX_VALUE - 8;
+
+ assertThrows(OutOfMemoryError.class,
+ () -> new ArrayDeque(Integer.MAX_VALUE));
+
+ {
+ ArrayDeque q = new ArrayDeque(maxArraySize - 1);
+ assertEquals(0, q.size());
+ assertTrue(q.isEmpty());
+ q = null;
+ }
+
+ {
+ ArrayDeque q = new ArrayDeque();
+ assertTrue(q.addAll(Collections.nCopies(maxArraySize - 3, e)));
+ assertEquals(e, q.peekFirst());
+ assertEquals(e, q.peekLast());
+ assertEquals(maxArraySize - 3, q.size());
+ q.addFirst((Integer) 0);
+ q.addLast((Integer) 1);
+ assertEquals((Integer) 0, q.peekFirst());
+ assertEquals((Integer) 1, q.peekLast());
+ assertEquals(maxArraySize - 1, q.size());
+
+ ArrayDeque qq = q;
+ ArrayDeque smallish = new ArrayDeque(
+ Collections.nCopies(Integer.MAX_VALUE - q.size() + 1, e));
+ assertThrows(
+ IllegalStateException.class,
+ () -> qq.addAll(qq),
+ () -> qq.addAll(smallish),
+ () -> smallish.addAll(qq));
+ }
+ }
+
+}
--- a/jdk/test/java/util/concurrent/tck/ArrayDequeTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/ArrayDequeTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -26,19 +26,22 @@
* However, the following notice accompanied the original version of this
* file:
*
- * Written by Doug Lea with assistance from members of JCP JSR-166
- * Expert Group and released to the public domain, as explained at
+ * 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.ArrayDeque;
import java.util.Arrays;
import java.util.Collection;
+import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
import junit.framework.Test;
import junit.framework.TestSuite;
@@ -49,20 +52,60 @@
}
public static Test suite() {
- return new TestSuite(ArrayDequeTest.class);
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return ArrayDeque.class; }
+ public Collection emptyCollection() { return populatedDeque(0); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return false; }
+ public boolean permitsNulls() { return false; }
+ }
+ return newTestSuite(ArrayDequeTest.class,
+ CollectionTest.testSuite(new Implementation()));
}
/**
* Returns a new deque of given size containing consecutive
- * Integers 0 ... n.
+ * Integers 0 ... n - 1.
*/
- private ArrayDeque<Integer> populatedDeque(int n) {
- ArrayDeque<Integer> q = new ArrayDeque<Integer>();
+ private static ArrayDeque<Integer> populatedDeque(int n) {
+ // Randomize various aspects of memory layout, including
+ // capacity slop and wraparound.
+ final ArrayDeque<Integer> q;
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ switch (rnd.nextInt(6)) {
+ case 0: q = new ArrayDeque<Integer>(); break;
+ case 1: q = new ArrayDeque<Integer>(0); break;
+ case 2: q = new ArrayDeque<Integer>(1); break;
+ case 3: q = new ArrayDeque<Integer>(Math.max(0, n - 1)); break;
+ case 4: q = new ArrayDeque<Integer>(n); break;
+ case 5: q = new ArrayDeque<Integer>(n + 1); break;
+ default: throw new AssertionError();
+ }
+ switch (rnd.nextInt(3)) {
+ case 0:
+ q.addFirst(42);
+ assertEquals((Integer) 42, q.removeLast());
+ break;
+ case 1:
+ q.addLast(42);
+ assertEquals((Integer) 42, q.removeFirst());
+ break;
+ case 2: /* do nothing */ break;
+ default: throw new AssertionError();
+ }
assertTrue(q.isEmpty());
- for (int i = 0; i < n; ++i)
- assertTrue(q.offerLast(new Integer(i)));
- assertFalse(q.isEmpty());
+ if (rnd.nextBoolean())
+ for (int i = 0; i < n; i++)
+ assertTrue(q.offerLast((Integer) i));
+ else
+ for (int i = n; --i >= 0; )
+ q.addFirst((Integer) i);
assertEquals(n, q.size());
+ if (n > 0) {
+ assertFalse(q.isEmpty());
+ assertEquals((Integer) 0, q.peekFirst());
+ assertEquals((Integer) (n - 1), q.peekLast());
+ }
return q;
}
@@ -556,30 +599,48 @@
* removeFirstOccurrence(x) removes x and returns true if present
*/
public void testRemoveFirstOccurrence() {
- ArrayDeque q = populatedDeque(SIZE);
+ Deque<Integer> q = populatedDeque(SIZE);
+ assertFalse(q.removeFirstOccurrence(null));
for (int i = 1; i < SIZE; i += 2) {
- assertTrue(q.removeFirstOccurrence(new Integer(i)));
+ assertTrue(q.removeFirstOccurrence(i));
+ assertFalse(q.contains(i));
}
for (int i = 0; i < SIZE; i += 2) {
- assertTrue(q.removeFirstOccurrence(new Integer(i)));
- assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
+ assertTrue(q.removeFirstOccurrence(i));
+ assertFalse(q.removeFirstOccurrence(i + 1));
+ assertFalse(q.contains(i));
+ assertFalse(q.contains(i + 1));
}
assertTrue(q.isEmpty());
+ assertFalse(q.removeFirstOccurrence(null));
+ assertFalse(q.removeFirstOccurrence(42));
+ q = new ArrayDeque();
+ assertFalse(q.removeFirstOccurrence(null));
+ assertFalse(q.removeFirstOccurrence(42));
}
/**
* removeLastOccurrence(x) removes x and returns true if present
*/
public void testRemoveLastOccurrence() {
- ArrayDeque q = populatedDeque(SIZE);
+ Deque<Integer> q = populatedDeque(SIZE);
+ assertFalse(q.removeLastOccurrence(null));
for (int i = 1; i < SIZE; i += 2) {
- assertTrue(q.removeLastOccurrence(new Integer(i)));
+ assertTrue(q.removeLastOccurrence(i));
+ assertFalse(q.contains(i));
}
for (int i = 0; i < SIZE; i += 2) {
- assertTrue(q.removeLastOccurrence(new Integer(i)));
- assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
+ assertTrue(q.removeLastOccurrence(i));
+ assertFalse(q.removeLastOccurrence(i + 1));
+ assertFalse(q.contains(i));
+ assertFalse(q.contains(i + 1));
}
assertTrue(q.isEmpty());
+ assertFalse(q.removeLastOccurrence(null));
+ assertFalse(q.removeLastOccurrence(42));
+ q = new ArrayDeque();
+ assertFalse(q.removeLastOccurrence(null));
+ assertFalse(q.removeLastOccurrence(42));
}
/**
@@ -652,89 +713,57 @@
}
}
- void checkToArray(ArrayDeque q) {
+ void checkToArray(ArrayDeque<Integer> q) {
int size = q.size();
- Object[] o = q.toArray();
- assertEquals(size, o.length);
+ Object[] a1 = q.toArray();
+ assertEquals(size, a1.length);
+ Integer[] a2 = q.toArray(new Integer[0]);
+ assertEquals(size, a2.length);
+ Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]);
+ assertEquals(size, a3.length);
+ Integer[] a4 = new Integer[size];
+ assertSame(a4, q.toArray(a4));
+ Integer[] a5 = new Integer[size + 1];
+ Arrays.fill(a5, 42);
+ assertSame(a5, q.toArray(a5));
+ Integer[] a6 = new Integer[size + 2];
+ Arrays.fill(a6, 42);
+ assertSame(a6, q.toArray(a6));
+ Object[][] as = { a1, a2, a3, a4, a5, a6 };
+ for (Object[] a : as) {
+ if (a.length > size) assertNull(a[size]);
+ if (a.length > size + 1) assertEquals(42, a[size + 1]);
+ }
Iterator it = q.iterator();
+ Integer s = q.peekFirst();
for (int i = 0; i < size; i++) {
Integer x = (Integer) it.next();
- assertEquals((Integer)o[0] + i, (int) x);
- assertSame(o[i], x);
+ assertEquals(s + i, (int) x);
+ for (Object[] a : as)
+ assertSame(a1[i], x);
}
}
/**
- * toArray() contains all elements in FIFO order
+ * toArray() and toArray(a) contain all elements in FIFO order
*/
public void testToArray() {
- ArrayDeque q = new ArrayDeque();
- for (int i = 0; i < SIZE; i++) {
+ final int size = ThreadLocalRandom.current().nextInt(10);
+ ArrayDeque<Integer> q = new ArrayDeque<>(size);
+ for (int i = 0; i < size; i++) {
checkToArray(q);
q.addLast(i);
}
// Provoke wraparound
- for (int i = 0; i < SIZE; i++) {
+ int added = size * 2;
+ for (int i = 0; i < added; i++) {
checkToArray(q);
- assertEquals(i, q.poll());
- q.addLast(SIZE + i);
- }
- for (int i = 0; i < SIZE; i++) {
- checkToArray(q);
- assertEquals(SIZE + i, q.poll());
+ assertEquals((Integer) i, q.poll());
+ q.addLast(size + i);
}
- }
-
- void checkToArray2(ArrayDeque q) {
- int size = q.size();
- Integer[] a1 = (size == 0) ? null : new Integer[size - 1];
- Integer[] a2 = new Integer[size];
- Integer[] a3 = new Integer[size + 2];
- if (size > 0) Arrays.fill(a1, 42);
- Arrays.fill(a2, 42);
- Arrays.fill(a3, 42);
- Integer[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1);
- Integer[] b2 = (Integer[]) q.toArray(a2);
- Integer[] b3 = (Integer[]) q.toArray(a3);
- assertSame(a2, b2);
- assertSame(a3, b3);
- Iterator it = q.iterator();
for (int i = 0; i < size; i++) {
- Integer x = (Integer) it.next();
- assertSame(b1[i], x);
- assertEquals(b1[0] + i, (int) x);
- assertSame(b2[i], x);
- assertSame(b3[i], x);
- }
- assertNull(a3[size]);
- assertEquals(42, (int) a3[size + 1]);
- if (size > 0) {
- assertNotSame(a1, b1);
- assertEquals(size, b1.length);
- for (int i = 0; i < a1.length; i++) {
- assertEquals(42, (int) a1[i]);
- }
- }
- }
-
- /**
- * toArray(a) contains all elements in FIFO order
- */
- public void testToArray2() {
- ArrayDeque q = new ArrayDeque();
- for (int i = 0; i < SIZE; i++) {
- checkToArray2(q);
- q.addLast(i);
- }
- // Provoke wraparound
- for (int i = 0; i < SIZE; i++) {
- checkToArray2(q);
- assertEquals(i, q.poll());
- q.addLast(SIZE + i);
- }
- for (int i = 0; i < SIZE; i++) {
- checkToArray2(q);
- assertEquals(SIZE + i, q.poll());
+ checkToArray(q);
+ assertEquals((Integer) (added + i), q.poll());
}
}
@@ -753,13 +782,17 @@
/**
* toArray(incompatible array type) throws ArrayStoreException
*/
- public void testToArray1_BadArg() {
+ public void testToArray_incompatibleArrayType() {
ArrayDeque l = new ArrayDeque();
l.add(new Integer(5));
try {
l.toArray(new String[10]);
shouldThrow();
} catch (ArrayStoreException success) {}
+ try {
+ l.toArray(new String[0]);
+ shouldThrow();
+ } catch (ArrayStoreException success) {}
}
/**
@@ -917,6 +950,25 @@
assertNotSame(y, x);
assertEquals(x.size(), y.size());
assertEquals(x.toString(), y.toString());
+ assertEquals(Arrays.toString(x.toArray()), Arrays.toString(y.toArray()));
+ assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+ while (!x.isEmpty()) {
+ assertFalse(y.isEmpty());
+ assertEquals(x.remove(), y.remove());
+ }
+ assertTrue(y.isEmpty());
+ }
+
+ /**
+ * A cloned deque has same elements in same order
+ */
+ public void testClone() throws Exception {
+ ArrayDeque<Integer> x = populatedDeque(SIZE);
+ ArrayDeque<Integer> y = x.clone();
+
+ assertNotSame(y, x);
+ assertEquals(x.size(), y.size());
+ assertEquals(x.toString(), y.toString());
assertTrue(Arrays.equals(x.toArray(), y.toArray()));
while (!x.isEmpty()) {
assertFalse(y.isEmpty());
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/ArrayListTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,66 @@
+/*
+ * 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.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class ArrayListTest extends JSR166TestCase {
+ public static void main(String[] args) {
+ main(suite(), args);
+ }
+
+ public static Test suite() {
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return ArrayList.class; }
+ public List emptyCollection() { return new ArrayList(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return false; }
+ public boolean permitsNulls() { return true; }
+ }
+ class SubListImplementation extends Implementation {
+ public List emptyCollection() {
+ return super.emptyCollection().subList(0, 0);
+ }
+ }
+ return newTestSuite(
+ // ArrayListTest.class,
+ CollectionTest.testSuite(new Implementation()),
+ CollectionTest.testSuite(new SubListImplementation()));
+ }
+
+}
--- a/jdk/test/java/util/concurrent/tck/Collection8Test.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/Collection8Test.java Mon Nov 28 23:36:11 2016 -0800
@@ -32,18 +32,35 @@
* http://creativecommons.org/publicdomain/zero/1.0/
*/
+import static java.util.concurrent.TimeUnit.HOURS;
import static java.util.concurrent.TimeUnit.MILLISECONDS;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+import java.util.Spliterator;
+import java.util.concurrent.BlockingDeque;
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
+import java.util.concurrent.Phaser;
+import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
import junit.framework.Test;
@@ -66,16 +83,422 @@
impl);
}
+ Object bomb() {
+ return new Object() {
+ public boolean equals(Object x) { throw new AssertionError(); }
+ public int hashCode() { throw new AssertionError(); }
+ };
+ }
+
+ /** Checks properties of empty collections. */
+ public void testEmptyMeansEmpty() throws Throwable {
+ Collection c = impl.emptyCollection();
+ emptyMeansEmpty(c);
+
+ if (c instanceof java.io.Serializable) {
+ try {
+ emptyMeansEmpty(serialClonePossiblyFailing(c));
+ } catch (java.io.NotSerializableException ex) {
+ // excusable when we have a serializable wrapper around
+ // a non-serializable collection, as can happen with:
+ // Vector.subList() => wrapped AbstractList$RandomAccessSubList
+ if (testImplementationDetails
+ && (! c.getClass().getName().matches(
+ "java.util.Collections.*")))
+ throw ex;
+ }
+ }
+
+ Collection clone = cloneableClone(c);
+ if (clone != null)
+ emptyMeansEmpty(clone);
+ }
+
+ void emptyMeansEmpty(Collection c) throws InterruptedException {
+ assertTrue(c.isEmpty());
+ assertEquals(0, c.size());
+ assertEquals("[]", c.toString());
+ {
+ Object[] a = c.toArray();
+ assertEquals(0, a.length);
+ assertSame(Object[].class, a.getClass());
+ }
+ {
+ Object[] a = new Object[0];
+ assertSame(a, c.toArray(a));
+ }
+ {
+ Integer[] a = new Integer[0];
+ assertSame(a, c.toArray(a));
+ }
+ {
+ Integer[] a = { 1, 2, 3};
+ assertSame(a, c.toArray(a));
+ assertNull(a[0]);
+ assertSame(2, a[1]);
+ assertSame(3, a[2]);
+ }
+ assertIteratorExhausted(c.iterator());
+ Consumer alwaysThrows = e -> { throw new AssertionError(); };
+ c.forEach(alwaysThrows);
+ c.iterator().forEachRemaining(alwaysThrows);
+ c.spliterator().forEachRemaining(alwaysThrows);
+ assertFalse(c.spliterator().tryAdvance(alwaysThrows));
+ if (c.spliterator().hasCharacteristics(Spliterator.SIZED))
+ assertEquals(0, c.spliterator().estimateSize());
+ assertFalse(c.contains(bomb()));
+ assertFalse(c.remove(bomb()));
+ if (c instanceof Queue) {
+ Queue q = (Queue) c;
+ assertNull(q.peek());
+ assertNull(q.poll());
+ }
+ if (c instanceof Deque) {
+ Deque d = (Deque) c;
+ assertNull(d.peekFirst());
+ assertNull(d.peekLast());
+ assertNull(d.pollFirst());
+ assertNull(d.pollLast());
+ assertIteratorExhausted(d.descendingIterator());
+ d.descendingIterator().forEachRemaining(alwaysThrows);
+ assertFalse(d.removeFirstOccurrence(bomb()));
+ assertFalse(d.removeLastOccurrence(bomb()));
+ }
+ if (c instanceof BlockingQueue) {
+ BlockingQueue q = (BlockingQueue) c;
+ assertNull(q.poll(0L, MILLISECONDS));
+ }
+ if (c instanceof BlockingDeque) {
+ BlockingDeque q = (BlockingDeque) c;
+ assertNull(q.pollFirst(0L, MILLISECONDS));
+ assertNull(q.pollLast(0L, MILLISECONDS));
+ }
+ }
+
+ public void testNullPointerExceptions() throws InterruptedException {
+ Collection c = impl.emptyCollection();
+ assertThrows(
+ NullPointerException.class,
+ () -> c.addAll(null),
+ () -> c.containsAll(null),
+ () -> c.retainAll(null),
+ () -> c.removeAll(null),
+ () -> c.removeIf(null),
+ () -> c.forEach(null),
+ () -> c.iterator().forEachRemaining(null),
+ () -> c.spliterator().forEachRemaining(null),
+ () -> c.spliterator().tryAdvance(null),
+ () -> c.toArray(null));
+
+ if (!impl.permitsNulls()) {
+ assertThrows(
+ NullPointerException.class,
+ () -> c.add(null));
+ }
+ if (!impl.permitsNulls() && c instanceof Queue) {
+ Queue q = (Queue) c;
+ assertThrows(
+ NullPointerException.class,
+ () -> q.offer(null));
+ }
+ if (!impl.permitsNulls() && c instanceof Deque) {
+ Deque d = (Deque) c;
+ assertThrows(
+ NullPointerException.class,
+ () -> d.addFirst(null),
+ () -> d.addLast(null),
+ () -> d.offerFirst(null),
+ () -> d.offerLast(null),
+ () -> d.push(null),
+ () -> d.descendingIterator().forEachRemaining(null));
+ }
+ if (c instanceof BlockingQueue) {
+ BlockingQueue q = (BlockingQueue) c;
+ assertThrows(
+ NullPointerException.class,
+ () -> {
+ try { q.offer(null, 1L, HOURS); }
+ catch (InterruptedException ex) {
+ throw new AssertionError(ex);
+ }},
+ () -> {
+ try { q.put(null); }
+ catch (InterruptedException ex) {
+ throw new AssertionError(ex);
+ }});
+ }
+ if (c instanceof BlockingDeque) {
+ BlockingDeque q = (BlockingDeque) c;
+ assertThrows(
+ NullPointerException.class,
+ () -> {
+ try { q.offerFirst(null, 1L, HOURS); }
+ catch (InterruptedException ex) {
+ throw new AssertionError(ex);
+ }},
+ () -> {
+ try { q.offerLast(null, 1L, HOURS); }
+ catch (InterruptedException ex) {
+ throw new AssertionError(ex);
+ }},
+ () -> {
+ try { q.putFirst(null); }
+ catch (InterruptedException ex) {
+ throw new AssertionError(ex);
+ }},
+ () -> {
+ try { q.putLast(null); }
+ catch (InterruptedException ex) {
+ throw new AssertionError(ex);
+ }});
+ }
+ }
+
+ public void testNoSuchElementExceptions() {
+ Collection c = impl.emptyCollection();
+ assertThrows(
+ NoSuchElementException.class,
+ () -> c.iterator().next());
+
+ if (c instanceof Queue) {
+ Queue q = (Queue) c;
+ assertThrows(
+ NoSuchElementException.class,
+ () -> q.element(),
+ () -> q.remove());
+ }
+ if (c instanceof Deque) {
+ Deque d = (Deque) c;
+ assertThrows(
+ NoSuchElementException.class,
+ () -> d.getFirst(),
+ () -> d.getLast(),
+ () -> d.removeFirst(),
+ () -> d.removeLast(),
+ () -> d.pop(),
+ () -> d.descendingIterator().next());
+ }
+ }
+
+ public void testRemoveIf() {
+ Collection c = impl.emptyCollection();
+ boolean ordered =
+ c.spliterator().hasCharacteristics(Spliterator.ORDERED);
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ int n = rnd.nextInt(6);
+ for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+ AtomicReference threwAt = new AtomicReference(null);
+ List orig = rnd.nextBoolean()
+ ? new ArrayList(c)
+ : Arrays.asList(c.toArray());
+
+ // Merely creating an iterator can change ArrayBlockingQueue behavior
+ Iterator it = rnd.nextBoolean() ? c.iterator() : null;
+
+ ArrayList survivors = new ArrayList();
+ ArrayList accepts = new ArrayList();
+ ArrayList rejects = new ArrayList();
+
+ Predicate randomPredicate = e -> {
+ assertNull(threwAt.get());
+ switch (rnd.nextInt(3)) {
+ case 0: accepts.add(e); return true;
+ case 1: rejects.add(e); return false;
+ case 2: threwAt.set(e); throw new ArithmeticException();
+ default: throw new AssertionError();
+ }
+ };
+ try {
+ try {
+ boolean modified = c.removeIf(randomPredicate);
+ assertNull(threwAt.get());
+ assertEquals(modified, accepts.size() > 0);
+ assertEquals(modified, rejects.size() != n);
+ assertEquals(accepts.size() + rejects.size(), n);
+ if (ordered) {
+ assertEquals(rejects,
+ Arrays.asList(c.toArray()));
+ } else {
+ assertEquals(new HashSet(rejects),
+ new HashSet(Arrays.asList(c.toArray())));
+ }
+ } catch (ArithmeticException ok) {
+ assertNotNull(threwAt.get());
+ assertTrue(c.contains(threwAt.get()));
+ }
+ if (it != null && impl.isConcurrent())
+ // check for weakly consistent iterator
+ while (it.hasNext()) assertTrue(orig.contains(it.next()));
+ switch (rnd.nextInt(4)) {
+ case 0: survivors.addAll(c); break;
+ case 1: survivors.addAll(Arrays.asList(c.toArray())); break;
+ case 2: c.forEach(survivors::add); break;
+ case 3: for (Object e : c) survivors.add(e); break;
+ }
+ assertTrue(orig.containsAll(accepts));
+ assertTrue(orig.containsAll(rejects));
+ assertTrue(orig.containsAll(survivors));
+ assertTrue(orig.containsAll(c));
+ assertTrue(c.containsAll(rejects));
+ assertTrue(c.containsAll(survivors));
+ assertTrue(survivors.containsAll(rejects));
+ if (threwAt.get() == null) {
+ assertEquals(n - accepts.size(), c.size());
+ for (Object x : accepts) assertFalse(c.contains(x));
+ } else {
+ // Two acceptable behaviors: entire removeIf call is one
+ // transaction, or each element processed is one transaction.
+ assertTrue(n == c.size() || n == c.size() + accepts.size());
+ int k = 0;
+ for (Object x : accepts) if (c.contains(x)) k++;
+ assertTrue(k == accepts.size() || k == 0);
+ }
+ } catch (Throwable ex) {
+ System.err.println(impl.klazz());
+ // c is at risk of corruption if we got here, so be lenient
+ try { System.err.printf("c=%s%n", c); }
+ catch (Throwable t) { t.printStackTrace(); }
+ System.err.printf("n=%d%n", n);
+ System.err.printf("orig=%s%n", orig);
+ System.err.printf("accepts=%s%n", accepts);
+ System.err.printf("rejects=%s%n", rejects);
+ System.err.printf("survivors=%s%n", survivors);
+ System.err.printf("threwAt=%s%n", threwAt.get());
+ throw ex;
+ }
+ }
+
+ /**
+ * Various ways of traversing a collection yield same elements
+ */
+ public void testIteratorEquivalence() {
+ Collection c = impl.emptyCollection();
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ int n = rnd.nextInt(6);
+ for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+ ArrayList iterated = new ArrayList();
+ ArrayList iteratedForEachRemaining = new ArrayList();
+ ArrayList tryAdvanced = new ArrayList();
+ ArrayList spliterated = new ArrayList();
+ ArrayList splitonced = new ArrayList();
+ ArrayList forEached = new ArrayList();
+ ArrayList streamForEached = new ArrayList();
+ ConcurrentLinkedQueue parallelStreamForEached = new ConcurrentLinkedQueue();
+ ArrayList removeIfed = new ArrayList();
+ for (Object x : c) iterated.add(x);
+ c.iterator().forEachRemaining(iteratedForEachRemaining::add);
+ for (Spliterator s = c.spliterator();
+ s.tryAdvance(tryAdvanced::add); ) {}
+ c.spliterator().forEachRemaining(spliterated::add);
+ { // trySplit returns "strict prefix"
+ Spliterator s1 = c.spliterator(), s2 = s1.trySplit();
+ if (s2 != null) s2.forEachRemaining(splitonced::add);
+ s1.forEachRemaining(splitonced::add);
+ }
+ c.forEach(forEached::add);
+ c.stream().forEach(streamForEached::add);
+ c.parallelStream().forEach(parallelStreamForEached::add);
+ c.removeIf(e -> { removeIfed.add(e); return false; });
+ boolean ordered =
+ c.spliterator().hasCharacteristics(Spliterator.ORDERED);
+ if (c instanceof List || c instanceof Deque)
+ assertTrue(ordered);
+ HashSet cset = new HashSet(c);
+ assertEquals(cset, new HashSet(parallelStreamForEached));
+ if (ordered) {
+ assertEquals(iterated, iteratedForEachRemaining);
+ assertEquals(iterated, tryAdvanced);
+ assertEquals(iterated, spliterated);
+ assertEquals(iterated, splitonced);
+ assertEquals(iterated, forEached);
+ assertEquals(iterated, streamForEached);
+ assertEquals(iterated, removeIfed);
+ } else {
+ assertEquals(cset, new HashSet(iterated));
+ assertEquals(cset, new HashSet(iteratedForEachRemaining));
+ assertEquals(cset, new HashSet(tryAdvanced));
+ assertEquals(cset, new HashSet(spliterated));
+ assertEquals(cset, new HashSet(splitonced));
+ assertEquals(cset, new HashSet(forEached));
+ assertEquals(cset, new HashSet(streamForEached));
+ assertEquals(cset, new HashSet(removeIfed));
+ }
+ if (c instanceof Deque) {
+ Deque d = (Deque) c;
+ ArrayList descending = new ArrayList();
+ ArrayList descendingForEachRemaining = new ArrayList();
+ for (Iterator it = d.descendingIterator(); it.hasNext(); )
+ descending.add(it.next());
+ d.descendingIterator().forEachRemaining(
+ e -> descendingForEachRemaining.add(e));
+ Collections.reverse(descending);
+ Collections.reverse(descendingForEachRemaining);
+ assertEquals(iterated, descending);
+ assertEquals(iterated, descendingForEachRemaining);
+ }
+ }
+
+ /**
+ * Calling Iterator#remove() after Iterator#forEachRemaining
+ * should (maybe) remove last element
+ */
+ public void testRemoveAfterForEachRemaining() {
+ Collection c = impl.emptyCollection();
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ testCollection: {
+ int n = 3 + rnd.nextInt(2);
+ for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+ Iterator it = c.iterator();
+ assertTrue(it.hasNext());
+ assertEquals(impl.makeElement(0), it.next());
+ assertTrue(it.hasNext());
+ assertEquals(impl.makeElement(1), it.next());
+ it.forEachRemaining(e -> assertTrue(c.contains(e)));
+ if (testImplementationDetails) {
+ if (c instanceof java.util.concurrent.ArrayBlockingQueue) {
+ assertIteratorExhausted(it);
+ } else {
+ try { it.remove(); }
+ catch (UnsupportedOperationException ok) {
+ break testCollection;
+ }
+ assertEquals(n - 1, c.size());
+ for (int i = 0; i < n - 1; i++)
+ assertTrue(c.contains(impl.makeElement(i)));
+ assertFalse(c.contains(impl.makeElement(n - 1)));
+ }
+ }
+ }
+ if (c instanceof Deque) {
+ Deque d = (Deque) impl.emptyCollection();
+ int n = 3 + rnd.nextInt(2);
+ for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
+ Iterator it = d.descendingIterator();
+ assertTrue(it.hasNext());
+ assertEquals(impl.makeElement(n - 1), it.next());
+ assertTrue(it.hasNext());
+ assertEquals(impl.makeElement(n - 2), it.next());
+ it.forEachRemaining(e -> assertTrue(c.contains(e)));
+ if (testImplementationDetails) {
+ it.remove();
+ assertEquals(n - 1, d.size());
+ for (int i = 1; i < n; i++)
+ assertTrue(d.contains(impl.makeElement(i)));
+ assertFalse(d.contains(impl.makeElement(0)));
+ }
+ }
+ }
+
/**
* stream().forEach returns elements in the collection
*/
- public void testForEach() throws Throwable {
+ public void testStreamForEach() throws Throwable {
final Collection c = impl.emptyCollection();
final AtomicLong count = new AtomicLong(0L);
final Object x = impl.makeElement(1);
final Object y = impl.makeElement(2);
final ArrayList found = new ArrayList();
- Consumer<Object> spy = (o) -> { found.add(o); };
+ Consumer<Object> spy = o -> found.add(o);
c.stream().forEach(spy);
assertTrue(found.isEmpty());
@@ -96,7 +519,7 @@
assertTrue(found.isEmpty());
}
- public void testForEachConcurrentStressTest() throws Throwable {
+ public void testStreamForEachConcurrentStressTest() throws Throwable {
if (!impl.isConcurrent()) return;
final Collection c = impl.emptyCollection();
final long testDurationMillis = timeoutMillis();
@@ -109,7 +532,7 @@
Runnable checkElt = () -> {
threadsStarted.countDown();
while (!done.get())
- c.stream().forEach((x) -> { assertSame(x, elt); }); };
+ c.stream().forEach(x -> assertSame(x, elt)); };
Runnable addRemove = () -> {
threadsStarted.countDown();
while (!done.get()) {
@@ -124,5 +547,144 @@
assertNull(f2.get(0L, MILLISECONDS));
}
- // public void testCollection8DebugFail() { fail(); }
+ /**
+ * collection.forEach returns elements in the collection
+ */
+ public void testForEach() throws Throwable {
+ final Collection c = impl.emptyCollection();
+ final AtomicLong count = new AtomicLong(0L);
+ final Object x = impl.makeElement(1);
+ final Object y = impl.makeElement(2);
+ final ArrayList found = new ArrayList();
+ Consumer<Object> spy = o -> found.add(o);
+ c.forEach(spy);
+ assertTrue(found.isEmpty());
+
+ assertTrue(c.add(x));
+ c.forEach(spy);
+ assertEquals(Collections.singletonList(x), found);
+ found.clear();
+
+ assertTrue(c.add(y));
+ c.forEach(spy);
+ assertEquals(2, found.size());
+ assertTrue(found.contains(x));
+ assertTrue(found.contains(y));
+ found.clear();
+
+ c.clear();
+ c.forEach(spy);
+ assertTrue(found.isEmpty());
+ }
+
+ /**
+ * Motley crew of threads concurrently randomly hammer the collection.
+ */
+ public void testDetectRaces() throws Throwable {
+ if (!impl.isConcurrent()) return;
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ final Collection c = impl.emptyCollection();
+ final long testDurationMillis
+ = expensiveTests ? LONG_DELAY_MS : timeoutMillis();
+ final AtomicBoolean done = new AtomicBoolean(false);
+ final Object one = impl.makeElement(1);
+ final Object two = impl.makeElement(2);
+ final Consumer checkSanity = x -> assertTrue(x == one || x == two);
+ final Consumer<Object[]> checkArraySanity = array -> {
+ // assertTrue(array.length <= 2); // duplicates are permitted
+ for (Object x : array) assertTrue(x == one || x == two);
+ };
+ final Object[] emptyArray =
+ (Object[]) java.lang.reflect.Array.newInstance(one.getClass(), 0);
+ final List<Future<?>> futures;
+ final Phaser threadsStarted = new Phaser(1); // register this thread
+ final Runnable[] frobbers = {
+ () -> c.forEach(checkSanity),
+ () -> c.stream().forEach(checkSanity),
+ () -> c.parallelStream().forEach(checkSanity),
+ () -> c.spliterator().trySplit(),
+ () -> {
+ Spliterator s = c.spliterator();
+ s.tryAdvance(checkSanity);
+ s.trySplit();
+ },
+ () -> {
+ Spliterator s = c.spliterator();
+ do {} while (s.tryAdvance(checkSanity));
+ },
+ () -> { for (Object x : c) checkSanity.accept(x); },
+ () -> 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));
+ },
+ };
+ final List<Runnable> tasks =
+ Arrays.stream(frobbers)
+ .filter(task -> rnd.nextBoolean()) // random subset
+ .map(task -> (Runnable) () -> {
+ threadsStarted.arriveAndAwaitAdvance();
+ while (!done.get())
+ task.run();
+ })
+ .collect(Collectors.toList());
+ final ExecutorService pool = Executors.newCachedThreadPool();
+ try (PoolCleaner cleaner = cleaner(pool, done)) {
+ threadsStarted.bulkRegister(tasks.size());
+ futures = tasks.stream()
+ .map(pool::submit)
+ .collect(Collectors.toList());
+ threadsStarted.arriveAndDeregister();
+ Thread.sleep(testDurationMillis);
+ }
+ for (Future future : futures)
+ assertNull(future.get(0L, MILLISECONDS));
+ }
+
+ /**
+ * Spliterators are either IMMUTABLE or truly late-binding or, if
+ * concurrent, use the same "late-binding style" of returning
+ * elements added between creation and first use.
+ */
+ public void testLateBindingStyle() {
+ if (!testImplementationDetails) return;
+ if (impl.klazz() == ArrayList.class) return; // for jdk8
+ // Immutable (snapshot) spliterators are exempt
+ if (impl.emptyCollection().spliterator()
+ .hasCharacteristics(Spliterator.IMMUTABLE))
+ return;
+ final Object one = impl.makeElement(1);
+ {
+ final Collection c = impl.emptyCollection();
+ final Spliterator split = c.spliterator();
+ c.add(one);
+ assertTrue(split.tryAdvance(e -> { assertSame(e, one); }));
+ assertFalse(split.tryAdvance(e -> { throw new AssertionError(); }));
+ assertTrue(c.contains(one));
+ }
+ {
+ final AtomicLong count = new AtomicLong(0);
+ final Collection c = impl.emptyCollection();
+ final Spliterator split = c.spliterator();
+ c.add(one);
+ split.forEachRemaining(
+ e -> { assertSame(e, one); count.getAndIncrement(); });
+ assertEquals(1L, count.get());
+ assertFalse(split.tryAdvance(e -> { throw new AssertionError(); }));
+ assertTrue(c.contains(one));
+ }
+ }
+
+// public void testCollection8DebugFail() {
+// fail(impl.klazz().getSimpleName());
+// }
}
--- a/jdk/test/java/util/concurrent/tck/CollectionTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/CollectionTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -32,8 +32,6 @@
* http://creativecommons.org/publicdomain/zero/1.0/
*/
-import java.util.Collection;
-
import junit.framework.Test;
/**
@@ -58,11 +56,7 @@
impl));
}
- /** A test of the CollectionImplementation implementation ! */
- public void testEmptyMeansEmpty() {
- assertTrue(impl.emptyCollection().isEmpty());
- assertEquals(0, impl.emptyCollection().size());
- }
-
- // public void testCollectionDebugFail() { fail(); }
+// public void testCollectionDebugFail() {
+// fail(impl.klazz().getSimpleName());
+// }
}
--- a/jdk/test/java/util/concurrent/tck/CopyOnWriteArrayListTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/CopyOnWriteArrayListTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -53,7 +53,22 @@
}
public static Test suite() {
- return new TestSuite(CopyOnWriteArrayListTest.class);
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return ArrayList.class; }
+ public List emptyCollection() { return new CopyOnWriteArrayList(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return true; }
+ public boolean permitsNulls() { return true; }
+ }
+ class SubListImplementation extends Implementation {
+ public List emptyCollection() {
+ return super.emptyCollection().subList(0, 0);
+ }
+ }
+ return newTestSuite(
+ CopyOnWriteArrayListTest.class,
+ CollectionTest.testSuite(new Implementation()),
+ CollectionTest.testSuite(new SubListImplementation()));
}
static CopyOnWriteArrayList<Integer> populatedArray(int n) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/CountedCompleter8Test.java Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,168 @@
+/*
+ * 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 static java.util.concurrent.TimeUnit.MILLISECONDS;
+import static java.util.concurrent.TimeUnit.SECONDS;
+
+import java.util.concurrent.CountedCompleter;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class CountedCompleter8Test extends JSR166TestCase {
+
+ public static void main(String[] args) {
+ main(suite(), args);
+ }
+
+ public static Test suite() {
+ return new TestSuite(CountedCompleter8Test.class);
+ }
+
+ /** CountedCompleter class javadoc code sample, version 1. */
+ public static <E> void forEach1(E[] array, Consumer<E> action) {
+ class Task extends CountedCompleter<Void> {
+ final int lo, hi;
+ Task(Task parent, int lo, int hi) {
+ super(parent); this.lo = lo; this.hi = hi;
+ }
+
+ public void compute() {
+ if (hi - lo >= 2) {
+ int mid = (lo + hi) >>> 1;
+ // must set pending count before fork
+ setPendingCount(2);
+ new Task(this, mid, hi).fork(); // right child
+ new Task(this, lo, mid).fork(); // left child
+ }
+ else if (hi > lo)
+ action.accept(array[lo]);
+ tryComplete();
+ }
+ }
+ new Task(null, 0, array.length).invoke();
+ }
+
+ /** CountedCompleter class javadoc code sample, version 2. */
+ public static <E> void forEach2(E[] array, Consumer<E> action) {
+ class Task extends CountedCompleter<Void> {
+ final int lo, hi;
+ Task(Task parent, int lo, int hi) {
+ super(parent); this.lo = lo; this.hi = hi;
+ }
+
+ public void compute() {
+ if (hi - lo >= 2) {
+ int mid = (lo + hi) >>> 1;
+ setPendingCount(1); // looks off by one, but correct!
+ new Task(this, mid, hi).fork(); // right child
+ new Task(this, lo, mid).compute(); // direct invoke
+ } else {
+ if (hi > lo)
+ action.accept(array[lo]);
+ tryComplete();
+ }
+ }
+ }
+ new Task(null, 0, array.length).invoke();
+ }
+
+ /** CountedCompleter class javadoc code sample, version 3. */
+ public static <E> void forEach3(E[] array, Consumer<E> action) {
+ class Task extends CountedCompleter<Void> {
+ final int lo, hi;
+ Task(Task parent, int lo, int hi) {
+ super(parent); this.lo = lo; this.hi = hi;
+ }
+
+ public void compute() {
+ int n = hi - lo;
+ for (; n >= 2; n /= 2) {
+ addToPendingCount(1);
+ new Task(this, lo + n/2, lo + n).fork();
+ }
+ if (n > 0)
+ action.accept(array[lo]);
+ propagateCompletion();
+ }
+ }
+ new Task(null, 0, array.length).invoke();
+ }
+
+ /** CountedCompleter class javadoc code sample, version 4. */
+ public static <E> void forEach4(E[] array, Consumer<E> action) {
+ class Task extends CountedCompleter<Void> {
+ final int lo, hi;
+ Task(Task parent, int lo, int hi) {
+ super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo));
+ this.lo = lo; this.hi = hi;
+ }
+
+ public void compute() {
+ for (int n = hi - lo; n >= 2; n /= 2)
+ new Task(this, lo + n/2, lo + n).fork();
+ action.accept(array[lo]);
+ propagateCompletion();
+ }
+ }
+ if (array.length > 0)
+ new Task(null, 0, array.length).invoke();
+ }
+
+ void testRecursiveDecomposition(
+ BiConsumer<Integer[], Consumer<Integer>> action) {
+ int n = ThreadLocalRandom.current().nextInt(8);
+ Integer[] a = new Integer[n];
+ for (int i = 0; i < n; i++) a[i] = i + 1;
+ AtomicInteger ai = new AtomicInteger(0);
+ action.accept(a, ai::addAndGet);
+ assertEquals(n * (n + 1) / 2, ai.get());
+ }
+
+ /**
+ * Variants of divide-by-two recursive decomposition into leaf tasks,
+ * as described in the CountedCompleter class javadoc code samples
+ */
+ public void testRecursiveDecomposition() {
+ testRecursiveDecomposition(CountedCompleter8Test::forEach1);
+ testRecursiveDecomposition(CountedCompleter8Test::forEach2);
+ testRecursiveDecomposition(CountedCompleter8Test::forEach3);
+ testRecursiveDecomposition(CountedCompleter8Test::forEach4);
+ }
+
+}
--- a/jdk/test/java/util/concurrent/tck/CountedCompleterTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/CountedCompleterTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -44,8 +44,6 @@
import java.util.concurrent.TimeoutException;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
import junit.framework.Test;
import junit.framework.TestSuite;
@@ -1872,115 +1870,4 @@
testInvokeOnPool(singletonPool(), a);
}
- /** CountedCompleter class javadoc code sample, version 1. */
- public static <E> void forEach1(E[] array, Consumer<E> action) {
- class Task extends CountedCompleter<Void> {
- final int lo, hi;
- Task(Task parent, int lo, int hi) {
- super(parent); this.lo = lo; this.hi = hi;
- }
-
- public void compute() {
- if (hi - lo >= 2) {
- int mid = (lo + hi) >>> 1;
- // must set pending count before fork
- setPendingCount(2);
- new Task(this, mid, hi).fork(); // right child
- new Task(this, lo, mid).fork(); // left child
- }
- else if (hi > lo)
- action.accept(array[lo]);
- tryComplete();
- }
- }
- new Task(null, 0, array.length).invoke();
- }
-
- /** CountedCompleter class javadoc code sample, version 2. */
- public static <E> void forEach2(E[] array, Consumer<E> action) {
- class Task extends CountedCompleter<Void> {
- final int lo, hi;
- Task(Task parent, int lo, int hi) {
- super(parent); this.lo = lo; this.hi = hi;
- }
-
- public void compute() {
- if (hi - lo >= 2) {
- int mid = (lo + hi) >>> 1;
- setPendingCount(1); // looks off by one, but correct!
- new Task(this, mid, hi).fork(); // right child
- new Task(this, lo, mid).compute(); // direct invoke
- } else {
- if (hi > lo)
- action.accept(array[lo]);
- tryComplete();
- }
- }
- }
- new Task(null, 0, array.length).invoke();
- }
-
- /** CountedCompleter class javadoc code sample, version 3. */
- public static <E> void forEach3(E[] array, Consumer<E> action) {
- class Task extends CountedCompleter<Void> {
- final int lo, hi;
- Task(Task parent, int lo, int hi) {
- super(parent); this.lo = lo; this.hi = hi;
- }
-
- public void compute() {
- int n = hi - lo;
- for (; n >= 2; n /= 2) {
- addToPendingCount(1);
- new Task(this, lo + n/2, lo + n).fork();
- }
- if (n > 0)
- action.accept(array[lo]);
- propagateCompletion();
- }
- }
- new Task(null, 0, array.length).invoke();
- }
-
- /** CountedCompleter class javadoc code sample, version 4. */
- public static <E> void forEach4(E[] array, Consumer<E> action) {
- class Task extends CountedCompleter<Void> {
- final int lo, hi;
- Task(Task parent, int lo, int hi) {
- super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo));
- this.lo = lo; this.hi = hi;
- }
-
- public void compute() {
- for (int n = hi - lo; n >= 2; n /= 2)
- new Task(this, lo + n/2, lo + n).fork();
- action.accept(array[lo]);
- propagateCompletion();
- }
- }
- if (array.length > 0)
- new Task(null, 0, array.length).invoke();
- }
-
- void testRecursiveDecomposition(
- BiConsumer<Integer[], Consumer<Integer>> action) {
- int n = ThreadLocalRandom.current().nextInt(8);
- Integer[] a = new Integer[n];
- for (int i = 0; i < n; i++) a[i] = i + 1;
- AtomicInteger ai = new AtomicInteger(0);
- action.accept(a, (x) -> ai.addAndGet(x));
- assertEquals(n * (n + 1) / 2, ai.get());
- }
-
- /**
- * Variants of divide-by-two recursive decomposition into leaf tasks,
- * as described in the CountedCompleter class javadoc code samples
- */
- public void testRecursiveDecomposition() {
- testRecursiveDecomposition(CountedCompleterTest::forEach1);
- testRecursiveDecomposition(CountedCompleterTest::forEach2);
- testRecursiveDecomposition(CountedCompleterTest::forEach3);
- testRecursiveDecomposition(CountedCompleterTest::forEach4);
- }
-
}
--- a/jdk/test/java/util/concurrent/tck/DelayQueueTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/DelayQueueTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -66,8 +66,16 @@
}
public static Test suite() {
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return DelayQueue.class; }
+ public Collection emptyCollection() { return new DelayQueue(); }
+ public Object makeElement(int i) { return new PDelay(i); }
+ public boolean isConcurrent() { return true; }
+ public boolean permitsNulls() { return false; }
+ }
return newTestSuite(DelayQueueTest.class,
- new Generic().testSuite());
+ new Generic().testSuite(),
+ CollectionTest.testSuite(new Implementation()));
}
/**
@@ -144,7 +152,7 @@
/**
* Returns a new queue of given size containing consecutive
- * PDelays 0 ... n.
+ * PDelays 0 ... n - 1.
*/
private DelayQueue<PDelay> populatedQueue(int n) {
DelayQueue<PDelay> q = new DelayQueue<PDelay>();
@@ -156,6 +164,7 @@
assertFalse(q.isEmpty());
assertEquals(Integer.MAX_VALUE, q.remainingCapacity());
assertEquals(n, q.size());
+ assertEquals(new PDelay(0), q.peek());
return q;
}
--- a/jdk/test/java/util/concurrent/tck/JSR166TestCase.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/JSR166TestCase.java Mon Nov 28 23:36:11 2016 -0800
@@ -68,6 +68,7 @@
import java.security.SecurityPermission;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
import java.util.Date;
import java.util.Enumeration;
@@ -474,6 +475,7 @@
AbstractQueuedLongSynchronizerTest.suite(),
ArrayBlockingQueueTest.suite(),
ArrayDequeTest.suite(),
+ ArrayListTest.suite(),
AtomicBooleanTest.suite(),
AtomicIntegerArrayTest.suite(),
AtomicIntegerFieldUpdaterTest.suite(),
@@ -496,6 +498,7 @@
CopyOnWriteArrayListTest.suite(),
CopyOnWriteArraySetTest.suite(),
CountDownLatchTest.suite(),
+ CountedCompleterTest.suite(),
CyclicBarrierTest.suite(),
DelayQueueTest.suite(),
EntryTest.suite(),
@@ -524,15 +527,17 @@
TreeMapTest.suite(),
TreeSetTest.suite(),
TreeSubMapTest.suite(),
- TreeSubSetTest.suite());
+ TreeSubSetTest.suite(),
+ VectorTest.suite());
// Java8+ test classes
if (atLeastJava8()) {
String[] java8TestClassNames = {
+ "ArrayDeque8Test",
"Atomic8Test",
"CompletableFutureTest",
"ConcurrentHashMap8Test",
- "CountedCompleterTest",
+ "CountedCompleter8Test",
"DoubleAccumulatorTest",
"DoubleAdderTest",
"ForkJoinPool8Test",
@@ -1850,12 +1855,22 @@
}
}
+ void assertImmutable(final Object o) {
+ if (o instanceof Collection) {
+ assertThrows(
+ UnsupportedOperationException.class,
+ new Runnable() { public void run() {
+ ((Collection) o).add(null);}});
+ }
+ }
+
@SuppressWarnings("unchecked")
<T> T serialClone(T o) {
try {
ObjectInputStream ois = new ObjectInputStream
(new ByteArrayInputStream(serialBytes(o)));
T clone = (T) ois.readObject();
+ if (o == clone) assertImmutable(o);
assertSame(o.getClass(), clone.getClass());
return clone;
} catch (Throwable fail) {
@@ -1864,6 +1879,46 @@
}
}
+ /**
+ * A version of serialClone that leaves error handling (for
+ * e.g. NotSerializableException) up to the caller.
+ */
+ @SuppressWarnings("unchecked")
+ <T> T serialClonePossiblyFailing(T o)
+ throws ReflectiveOperationException, java.io.IOException {
+ ByteArrayOutputStream bos = new ByteArrayOutputStream();
+ ObjectOutputStream oos = new ObjectOutputStream(bos);
+ oos.writeObject(o);
+ oos.flush();
+ oos.close();
+ ObjectInputStream ois = new ObjectInputStream
+ (new ByteArrayInputStream(bos.toByteArray()));
+ T clone = (T) ois.readObject();
+ if (o == clone) assertImmutable(o);
+ assertSame(o.getClass(), clone.getClass());
+ return clone;
+ }
+
+ /**
+ * If o implements Cloneable and has a public clone method,
+ * returns a clone of o, else null.
+ */
+ @SuppressWarnings("unchecked")
+ <T> T cloneableClone(T o) {
+ if (!(o instanceof Cloneable)) return null;
+ final T clone;
+ try {
+ clone = (T) o.getClass().getMethod("clone").invoke(o);
+ } catch (NoSuchMethodException ok) {
+ return null;
+ } catch (ReflectiveOperationException unexpected) {
+ throw new Error(unexpected);
+ }
+ assertNotSame(o, clone); // not 100% guaranteed by spec
+ assertSame(o.getClass(), clone.getClass());
+ return clone;
+ }
+
public void assertThrows(Class<? extends Throwable> expectedExceptionClass,
Runnable... throwingActions) {
for (Runnable throwingAction : throwingActions) {
--- a/jdk/test/java/util/concurrent/tck/LinkedBlockingDequeTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/LinkedBlockingDequeTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -68,14 +68,22 @@
}
public static Test suite() {
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return LinkedBlockingDeque.class; }
+ public Collection emptyCollection() { return new LinkedBlockingDeque(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return true; }
+ public boolean permitsNulls() { return false; }
+ }
return newTestSuite(LinkedBlockingDequeTest.class,
new Unbounded().testSuite(),
- new Bounded().testSuite());
+ new Bounded().testSuite(),
+ CollectionTest.testSuite(new Implementation()));
}
/**
* Returns a new deque of given size containing consecutive
- * Integers 0 ... n.
+ * Integers 0 ... n - 1.
*/
private LinkedBlockingDeque<Integer> populatedDeque(int n) {
LinkedBlockingDeque<Integer> q =
@@ -86,6 +94,8 @@
assertFalse(q.isEmpty());
assertEquals(0, q.remainingCapacity());
assertEquals(n, q.size());
+ assertEquals((Integer) 0, q.peekFirst());
+ assertEquals((Integer) (n - 1), q.peekLast());
return q;
}
--- a/jdk/test/java/util/concurrent/tck/LinkedBlockingQueueTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/LinkedBlockingQueueTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -68,14 +68,22 @@
}
public static Test suite() {
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return LinkedBlockingQueue.class; }
+ public Collection emptyCollection() { return new LinkedBlockingQueue(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return true; }
+ public boolean permitsNulls() { return false; }
+ }
return newTestSuite(LinkedBlockingQueueTest.class,
new Unbounded().testSuite(),
- new Bounded().testSuite());
+ new Bounded().testSuite(),
+ CollectionTest.testSuite(new Implementation()));
}
/**
* Returns a new queue of given size containing consecutive
- * Integers 0 ... n.
+ * Integers 0 ... n - 1.
*/
private LinkedBlockingQueue<Integer> populatedQueue(int n) {
LinkedBlockingQueue<Integer> q =
@@ -86,6 +94,7 @@
assertFalse(q.isEmpty());
assertEquals(0, q.remainingCapacity());
assertEquals(n, q.size());
+ assertEquals((Integer) 0, q.peek());
return q;
}
--- a/jdk/test/java/util/concurrent/tck/LinkedListTest.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/LinkedListTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -48,12 +48,27 @@
}
public static Test suite() {
- return new TestSuite(LinkedListTest.class);
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return LinkedList.class; }
+ public Collection emptyCollection() { return new LinkedList(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return false; }
+ public boolean permitsNulls() { return true; }
+ }
+ class SubListImplementation extends Implementation {
+ public Collection emptyCollection() {
+ return new LinkedList().subList(0, 0);
+ }
+ }
+ return newTestSuite(
+ LinkedListTest.class,
+ CollectionTest.testSuite(new Implementation()),
+ CollectionTest.testSuite(new SubListImplementation()));
}
/**
* Returns a new queue of given size containing consecutive
- * Integers 0 ... n.
+ * Integers 0 ... n - 1.
*/
private LinkedList<Integer> populatedQueue(int n) {
LinkedList<Integer> q = new LinkedList<Integer>();
@@ -62,6 +77,8 @@
assertTrue(q.offer(new Integer(i)));
assertFalse(q.isEmpty());
assertEquals(n, q.size());
+ assertEquals((Integer) 0, q.peekFirst());
+ assertEquals((Integer) (n - 1), q.peekLast());
return q;
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/tck/VectorTest.java Mon Nov 28 23:36:11 2016 -0800
@@ -0,0 +1,66 @@
+/*
+ * 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.Vector;
+import java.util.Collection;
+import java.util.List;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
+
+public class VectorTest extends JSR166TestCase {
+ public static void main(String[] args) {
+ main(suite(), args);
+ }
+
+ public static Test suite() {
+ class Implementation implements CollectionImplementation {
+ public Class<?> klazz() { return Vector.class; }
+ public List emptyCollection() { return new Vector(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return false; }
+ public boolean permitsNulls() { return true; }
+ }
+ class SubListImplementation extends Implementation {
+ public List emptyCollection() {
+ return super.emptyCollection().subList(0, 0);
+ }
+ }
+ return newTestSuite(
+ // VectorTest.class,
+ CollectionTest.testSuite(new Implementation()),
+ CollectionTest.testSuite(new SubListImplementation()));
+ }
+
+}