diff --git a/src/java.base/share/classes/java/util/ArrayDeque.java b/src/java.base/share/classes/java/util/ArrayDeque.java
--- a/src/java.base/share/classes/java/util/ArrayDeque.java
+++ b/src/java.base/share/classes/java/util/ArrayDeque.java
@@ -208,7 +208,7 @@
*/
public ArrayDeque(Collection extends E> c) {
this(c.size());
- addAll(c);
+ copyElements(c);
}
/**
@@ -322,8 +322,12 @@
final int s, needed;
if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
grow(needed);
+ copyElements(c);
+ return size() > s;
+ }
+
+ private void copyElements(Collection extends E> c) {
c.forEach(this::addLast);
- return size() > s;
}
/**
diff --git a/src/java.base/share/classes/java/util/Deque.java b/src/java.base/share/classes/java/util/Deque.java
--- a/src/java.base/share/classes/java/util/Deque.java
+++ b/src/java.base/share/classes/java/util/Deque.java
@@ -141,8 +141,8 @@
*
Deques can also be used as LIFO (Last-In-First-Out) stacks. This
* interface should be used in preference to the legacy {@link Stack} class.
* When a deque is used as a stack, elements are pushed and popped from the
- * beginning of the deque. Stack methods are precisely equivalent to
- * {@code Deque} methods as indicated in the table below:
+ * beginning of the deque. Stack methods are equivalent to {@code Deque}
+ * methods as indicated in the table below:
*
*
* Comparison of Stack and Deque methods
@@ -163,7 +163,7 @@
*
*
* {@link #peek() peek()}
- * {@link #peekFirst() peekFirst()}
+ * {@link #getFirst() getFirst()}
*
*
*
diff --git a/src/java.base/share/classes/java/util/concurrent/CompletableFuture.java b/src/java.base/share/classes/java/util/concurrent/CompletableFuture.java
--- a/src/java.base/share/classes/java/util/concurrent/CompletableFuture.java
+++ b/src/java.base/share/classes/java/util/concurrent/CompletableFuture.java
@@ -2883,7 +2883,7 @@
STACK = l.findVarHandle(CompletableFuture.class, "stack", Completion.class);
NEXT = l.findVarHandle(Completion.class, "next", Completion.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java
@@ -6383,7 +6383,7 @@
ABASE = U.arrayBaseOffset(Node[].class);
int scale = U.arrayIndexScale(Node[].class);
if ((scale & (scale - 1)) != 0)
- throw new Error("array index scale not a power of two");
+ throw new ExceptionInInitializerError("array index scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java b/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
@@ -1671,7 +1671,7 @@
NEXT = l.findVarHandle(Node.class, "next", Node.class);
ITEM = l.findVarHandle(Node.class, "item", Object.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java b/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java
@@ -1069,7 +1069,7 @@
ITEM = l.findVarHandle(Node.class, "item", Object.class);
NEXT = l.findVarHandle(Node.class, "next", Node.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java b/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
@@ -3412,7 +3412,7 @@
VAL = l.findVarHandle(Node.class, "val", Object.class);
RIGHT = l.findVarHandle(Index.class, "right", Index.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
- }
- }
-}
+ throw new ExceptionInInitializerError(e);
+ }
+ }
+}
diff --git a/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java b/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java
--- a/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java
+++ b/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java
@@ -35,7 +35,6 @@
package java.util.concurrent;
import java.lang.reflect.Field;
-import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
@@ -134,17 +133,17 @@
* @throws NullPointerException if the specified collection is null
*/
public CopyOnWriteArrayList(Collection extends E> c) {
- Object[] elements;
+ Object[] es;
if (c.getClass() == CopyOnWriteArrayList.class)
- elements = ((CopyOnWriteArrayList>)c).getArray();
+ es = ((CopyOnWriteArrayList>)c).getArray();
else {
- elements = c.toArray();
+ es = c.toArray();
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
- if (elements.getClass() != Object[].class)
- elements = Arrays.copyOf(elements, elements.length, Object[].class);
+ if (es.getClass() != Object[].class)
+ es = Arrays.copyOf(es, es.length, Object[].class);
}
- setArray(elements);
+ setArray(es);
}
/**
@@ -180,20 +179,19 @@
* static version of indexOf, to allow repeated calls without
* needing to re-acquire array each time.
* @param o element to search for
- * @param elements the array
- * @param index first index to search
- * @param fence one past last index to search
+ * @param es the array
+ * @param from first index to search
+ * @param to one past last index to search
* @return index of element, or -1 if absent
*/
- private static int indexOf(Object o, Object[] elements,
- int index, int fence) {
+ private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
- for (int i = index; i < fence; i++)
- if (elements[i] == null)
+ for (int i = from; i < to; i++)
+ if (es[i] == null)
return i;
} else {
- for (int i = index; i < fence; i++)
- if (o.equals(elements[i]))
+ for (int i = from; i < to; i++)
+ if (o.equals(es[i]))
return i;
}
return -1;
@@ -202,18 +200,19 @@
/**
* static version of lastIndexOf.
* @param o element to search for
- * @param elements the array
- * @param index first index to search
+ * @param es the array
+ * @param from index of first element of range, last element to search
+ * @param to one past last element of range, first element to search
* @return index of element, or -1 if absent
*/
- private static int lastIndexOf(Object o, Object[] elements, int index) {
+ private static int lastIndexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
- for (int i = index; i >= 0; i--)
- if (elements[i] == null)
+ for (int i = to - 1; i >= from; i--)
+ if (es[i] == null)
return i;
} else {
- for (int i = index; i >= 0; i--)
- if (o.equals(elements[i]))
+ for (int i = to - 1; i >= from; i--)
+ if (o.equals(es[i]))
return i;
}
return -1;
@@ -228,16 +227,15 @@
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
- Object[] elements = getArray();
- return indexOf(o, elements, 0, elements.length) >= 0;
+ return indexOf(o) >= 0;
}
/**
* {@inheritDoc}
*/
public int indexOf(Object o) {
- Object[] elements = getArray();
- return indexOf(o, elements, 0, elements.length);
+ Object[] es = getArray();
+ return indexOfRange(o, es, 0, es.length);
}
/**
@@ -256,16 +254,16 @@
* @throws IndexOutOfBoundsException if the specified index is negative
*/
public int indexOf(E e, int index) {
- Object[] elements = getArray();
- return indexOf(e, elements, index, elements.length);
+ Object[] es = getArray();
+ return indexOfRange(e, es, index, es.length);
}
/**
* {@inheritDoc}
*/
public int lastIndexOf(Object o) {
- Object[] elements = getArray();
- return lastIndexOf(o, elements, elements.length - 1);
+ Object[] es = getArray();
+ return lastIndexOfRange(o, es, 0, es.length);
}
/**
@@ -285,8 +283,8 @@
* than or equal to the current size of this list
*/
public int lastIndexOf(E e, int index) {
- Object[] elements = getArray();
- return lastIndexOf(e, elements, index);
+ Object[] es = getArray();
+ return lastIndexOfRange(e, es, 0, index + 1);
}
/**
@@ -322,8 +320,7 @@
* @return an array containing all the elements in this list
*/
public Object[] toArray() {
- Object[] elements = getArray();
- return Arrays.copyOf(elements, elements.length);
+ return getArray().clone();
}
/**
@@ -366,12 +363,12 @@
*/
@SuppressWarnings("unchecked")
public T[] toArray(T[] a) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
if (a.length < len)
- return (T[]) Arrays.copyOf(elements, len, a.getClass());
+ return (T[]) Arrays.copyOf(es, len, a.getClass());
else {
- System.arraycopy(elements, 0, a, 0, len);
+ System.arraycopy(es, 0, a, 0, len);
if (a.length > len)
a[len] = null;
return a;
@@ -406,17 +403,13 @@
*/
public E set(int index, E element) {
synchronized (lock) {
- Object[] elements = getArray();
- E oldValue = elementAt(elements, index);
+ Object[] es = getArray();
+ E oldValue = elementAt(es, index);
if (oldValue != element) {
- int len = elements.length;
- Object[] newElements = Arrays.copyOf(elements, len);
- newElements[index] = element;
- setArray(newElements);
- } else {
- // Not quite a no-op; ensures volatile write semantics
- setArray(elements);
+ es = es.clone();
+ es[index] = element;
+ setArray(es);
}
return oldValue;
}
@@ -430,11 +423,11 @@
*/
public boolean add(E e) {
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- Object[] newElements = Arrays.copyOf(elements, len + 1);
- newElements[len] = e;
- setArray(newElements);
+ Object[] es = getArray();
+ int len = es.length;
+ es = Arrays.copyOf(es, len + 1);
+ es[len] = e;
+ setArray(es);
return true;
}
}
@@ -448,18 +441,18 @@
*/
public void add(int index, E element) {
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
- newElements = Arrays.copyOf(elements, len + 1);
+ newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
- System.arraycopy(elements, 0, newElements, 0, index);
- System.arraycopy(elements, index, newElements, index + 1,
+ System.arraycopy(es, 0, newElements, 0, index);
+ System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
@@ -476,19 +469,20 @@
*/
public E remove(int index) {
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- E oldValue = elementAt(elements, index);
+ Object[] es = getArray();
+ int len = es.length;
+ E oldValue = elementAt(es, index);
int numMoved = len - index - 1;
+ Object[] newElements;
if (numMoved == 0)
- setArray(Arrays.copyOf(elements, len - 1));
+ newElements = Arrays.copyOf(es, len - 1);
else {
- Object[] newElements = new Object[len - 1];
- System.arraycopy(elements, 0, newElements, 0, index);
- System.arraycopy(elements, index + 1, newElements, index,
+ newElements = new Object[len - 1];
+ System.arraycopy(es, 0, newElements, 0, index);
+ System.arraycopy(es, index + 1, newElements, index,
numMoved);
+ }
setArray(newElements);
- }
return oldValue;
}
}
@@ -507,7 +501,7 @@
*/
public boolean remove(Object o) {
Object[] snapshot = getArray();
- int index = indexOf(o, snapshot, 0, snapshot.length);
+ int index = indexOfRange(o, snapshot, 0, snapshot.length);
return index >= 0 && remove(o, snapshot, index);
}
@@ -532,7 +526,7 @@
return false;
if (current[index] == o)
break findIndex;
- index = indexOf(o, current, index, len);
+ index = indexOfRange(o, current, index, len);
if (index < 0)
return false;
}
@@ -560,19 +554,19 @@
*/
void removeRange(int fromIndex, int toIndex) {
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
throw new IndexOutOfBoundsException();
int newlen = len - (toIndex - fromIndex);
int numMoved = len - toIndex;
if (numMoved == 0)
- setArray(Arrays.copyOf(elements, newlen));
+ setArray(Arrays.copyOf(es, newlen));
else {
Object[] newElements = new Object[newlen];
- System.arraycopy(elements, 0, newElements, 0, fromIndex);
- System.arraycopy(elements, toIndex, newElements,
+ System.arraycopy(es, 0, newElements, 0, fromIndex);
+ System.arraycopy(es, toIndex, newElements,
fromIndex, numMoved);
setArray(newElements);
}
@@ -587,7 +581,7 @@
*/
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
- return indexOf(e, snapshot, 0, snapshot.length) < 0
+ return indexOfRange(e, snapshot, 0, snapshot.length) < 0
&& addIfAbsent(e, snapshot);
}
@@ -606,7 +600,7 @@
if (current[i] != snapshot[i]
&& Objects.equals(e, current[i]))
return false;
- if (indexOf(e, current, common, len) >= 0)
+ if (indexOfRange(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
@@ -627,10 +621,10 @@
* @see #contains(Object)
*/
public boolean containsAll(Collection> c) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
for (Object e : c) {
- if (indexOf(e, elements, 0, len) < 0)
+ if (indexOfRange(e, es, 0, len) < 0)
return false;
}
return true;
@@ -694,18 +688,18 @@
if (cs.length == 0)
return 0;
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
int added = 0;
// uniquify and compact elements in cs
for (int i = 0; i < cs.length; ++i) {
Object e = cs[i];
- if (indexOf(e, elements, 0, len) < 0 &&
- indexOf(e, cs, 0, added) < 0)
+ if (indexOfRange(e, es, 0, len) < 0 &&
+ indexOfRange(e, cs, 0, added) < 0)
cs[added++] = e;
}
if (added > 0) {
- Object[] newElements = Arrays.copyOf(elements, len + added);
+ Object[] newElements = Arrays.copyOf(es, len + added);
System.arraycopy(cs, 0, newElements, len, added);
setArray(newElements);
}
@@ -739,15 +733,16 @@
if (cs.length == 0)
return false;
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
+ Object[] newElements;
if (len == 0 && cs.getClass() == Object[].class)
- setArray(cs);
+ newElements = cs;
else {
- Object[] newElements = Arrays.copyOf(elements, len + cs.length);
+ newElements = Arrays.copyOf(es, len + cs.length);
System.arraycopy(cs, 0, newElements, len, cs.length);
+ }
setArray(newElements);
- }
return true;
}
}
@@ -771,8 +766,8 @@
public boolean addAll(int index, Collection extends E> c) {
Object[] cs = c.toArray();
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
if (cs.length == 0)
@@ -780,11 +775,11 @@
int numMoved = len - index;
Object[] newElements;
if (numMoved == 0)
- newElements = Arrays.copyOf(elements, len + cs.length);
+ newElements = Arrays.copyOf(es, len + cs.length);
else {
newElements = new Object[len + cs.length];
- System.arraycopy(elements, 0, newElements, 0, index);
- System.arraycopy(elements, index,
+ System.arraycopy(es, 0, newElements, 0, index);
+ System.arraycopy(es, index,
newElements, index + cs.length,
numMoved);
}
@@ -866,14 +861,14 @@
}
public void replaceAll(UnaryOperator operator) {
- Objects.requireNonNull(operator);
synchronized (lock) {
- replaceAll(operator, 0, getArray().length);
+ replaceAllRange(operator, 0, getArray().length);
}
}
- void replaceAll(UnaryOperator operator, int i, int end) {
+ void replaceAllRange(UnaryOperator operator, int i, int end) {
// assert Thread.holdsLock(lock);
+ Objects.requireNonNull(operator);
final Object[] es = getArray().clone();
for (; i < end; i++)
es[i] = operator.apply(elementAt(es, i));
@@ -882,12 +877,12 @@
public void sort(Comparator super E> c) {
synchronized (lock) {
- sort(c, 0, getArray().length);
+ sortRange(c, 0, getArray().length);
}
}
@SuppressWarnings("unchecked")
- void sort(Comparator super E> c, int i, int end) {
+ void sortRange(Comparator super E> c, int i, int end) {
// assert Thread.holdsLock(lock);
final Object[] es = getArray().clone();
Arrays.sort(es, i, end, (Comparator)c);
@@ -908,12 +903,12 @@
s.defaultWriteObject();
- Object[] elements = getArray();
+ Object[] es = getArray();
// Write out array length
- s.writeInt(elements.length);
+ s.writeInt(es.length);
// Write out all elements in the proper order.
- for (Object element : elements)
+ for (Object element : es)
s.writeObject(element);
}
@@ -935,12 +930,12 @@
// Read in array length and allocate array
int len = s.readInt();
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len);
- Object[] elements = new Object[len];
+ Object[] es = new Object[len];
// Read in all elements in the proper order.
for (int i = 0; i < len; i++)
- elements[i] = s.readObject();
- setArray(elements);
+ es[i] = s.readObject();
+ setArray(es);
}
/**
@@ -986,6 +981,15 @@
return !it.hasNext();
}
+ private static int hashCodeOfRange(Object[] es, int from, int to) {
+ int hashCode = 1;
+ for (int i = from; i < to; i++) {
+ Object x = es[i];
+ hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
+ }
+ return hashCode;
+ }
+
/**
* Returns the hash code value for this list.
*
@@ -994,10 +998,8 @@
* @return the hash code value for this list
*/
public int hashCode() {
- int hashCode = 1;
- for (Object x : getArray())
- hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
- return hashCode;
+ Object[] es = getArray();
+ return hashCodeOfRange(es, 0, es.length);
}
/**
@@ -1037,12 +1039,12 @@
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ListIterator listIterator(int index) {
- Object[] elements = getArray();
- int len = elements.length;
+ Object[] es = getArray();
+ int len = es.length;
if (index < 0 || index > len)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
- return new COWIterator(elements, index);
+ return new COWIterator(es, index);
}
/**
@@ -1070,9 +1072,9 @@
/** Index of element to be returned by subsequent call to next. */
private int cursor;
- COWIterator(Object[] elements, int initialCursor) {
+ COWIterator(Object[] es, int initialCursor) {
cursor = initialCursor;
- snapshot = elements;
+ snapshot = es;
}
public boolean hasNext() {
@@ -1133,14 +1135,13 @@
}
@Override
- @SuppressWarnings("unchecked")
public void forEachRemaining(Consumer super E> action) {
Objects.requireNonNull(action);
final int size = snapshot.length;
- for (int i = cursor; i < size; i++) {
- action.accept((E) snapshot[i]);
- }
+ int i = cursor;
cursor = size;
+ for (; i < size; i++)
+ action.accept(elementAt(snapshot, i));
}
}
@@ -1161,136 +1162,264 @@
*/
public List subList(int fromIndex, int toIndex) {
synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
+ Object[] es = getArray();
+ int len = es.length;
+ int size = toIndex - fromIndex;
+ if (fromIndex < 0 || toIndex > len || size < 0)
throw new IndexOutOfBoundsException();
- return new COWSubList(this, fromIndex, toIndex);
+ return new COWSubList(es, fromIndex, size);
}
}
/**
* Sublist for CopyOnWriteArrayList.
*/
- private static class COWSubList
- extends AbstractList
- implements RandomAccess
- {
- private final CopyOnWriteArrayList l;
+ private class COWSubList implements List, RandomAccess {
private final int offset;
private int size;
private Object[] expectedArray;
- // only call this holding l's lock
- COWSubList(CopyOnWriteArrayList list,
- int fromIndex, int toIndex) {
- // assert Thread.holdsLock(list.lock);
- l = list;
- expectedArray = l.getArray();
- offset = fromIndex;
- size = toIndex - fromIndex;
+ COWSubList(Object[] es, int offset, int size) {
+ // assert Thread.holdsLock(lock);
+ expectedArray = es;
+ this.offset = offset;
+ this.size = size;
}
- // only call this holding l's lock
private void checkForComodification() {
- // assert Thread.holdsLock(l.lock);
- if (l.getArray() != expectedArray)
+ // assert Thread.holdsLock(lock);
+ if (getArray() != expectedArray)
throw new ConcurrentModificationException();
}
private Object[] getArrayChecked() {
- // assert Thread.holdsLock(l.lock);
- Object[] a = l.getArray();
+ // assert Thread.holdsLock(lock);
+ Object[] a = 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);
+ // assert Thread.holdsLock(lock);
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBounds(index, size));
}
+ private void rangeCheckForAdd(int index) {
+ // assert Thread.holdsLock(lock);
+ if (index < 0 || index > size)
+ throw new IndexOutOfBoundsException(outOfBounds(index, size));
+ }
+
+ public Object[] toArray() {
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+ return Arrays.copyOfRange(es, offset, offset + size);
+ }
+
+ @SuppressWarnings("unchecked")
+ public T[] toArray(T[] a) {
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+ if (a.length < size)
+ return (T[]) Arrays.copyOfRange(
+ es, offset, offset + size, a.getClass());
+ else {
+ System.arraycopy(es, offset, a, 0, size);
+ if (a.length > size)
+ a[size] = null;
+ return a;
+ }
+ }
+
+ public int indexOf(Object o) {
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+ int i = indexOfRange(o, es, offset, offset + size);
+ return (i == -1) ? -1 : i - offset;
+ }
+
+ public int lastIndexOf(Object o) {
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+ int i = lastIndexOfRange(o, es, offset, offset + size);
+ return (i == -1) ? -1 : i - offset;
+ }
+
+ public boolean contains(Object o) {
+ return indexOf(o) >= 0;
+ }
+
+ public boolean containsAll(Collection> c) {
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+ for (Object o : c)
+ if (indexOfRange(o, es, offset, offset + size) < 0)
+ return false;
+ return true;
+ }
+
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
+ public String toString() {
+ return Arrays.toString(toArray());
+ }
+
+ public int hashCode() {
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+ return hashCodeOfRange(es, offset, offset + size);
+ }
+
+ public boolean equals(Object o) {
+ if (o == this)
+ return true;
+ if (!(o instanceof List))
+ return false;
+ Iterator> it = ((List>)o).iterator();
+
+ final Object[] es;
+ final int offset;
+ final int size;
+ synchronized (lock) {
+ es = getArrayChecked();
+ offset = this.offset;
+ size = this.size;
+ }
+
+ for (int i = offset, end = offset + size; i < end; i++)
+ if (!it.hasNext() || !Objects.equals(es[i], it.next()))
+ return false;
+ return !it.hasNext();
+ }
+
public E set(int index, E element) {
- synchronized (l.lock) {
+ synchronized (lock) {
rangeCheck(index);
checkForComodification();
- E x = l.set(offset + index, element);
- expectedArray = l.getArray();
+ E x = CopyOnWriteArrayList.this.set(offset + index, element);
+ expectedArray = getArray();
return x;
}
}
public E get(int index) {
- synchronized (l.lock) {
+ synchronized (lock) {
rangeCheck(index);
checkForComodification();
- return l.get(offset + index);
+ return CopyOnWriteArrayList.this.get(offset + index);
}
}
public int size() {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
return size;
}
}
public boolean add(E element) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- l.add(offset + size, element);
- expectedArray = l.getArray();
+ CopyOnWriteArrayList.this.add(offset + size, element);
+ expectedArray = getArray();
size++;
}
return true;
}
public void add(int index, E element) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException
- (outOfBounds(index, size));
- l.add(offset + index, element);
- expectedArray = l.getArray();
+ rangeCheckForAdd(index);
+ CopyOnWriteArrayList.this.add(offset + index, element);
+ expectedArray = getArray();
size++;
}
}
public boolean addAll(Collection extends E> c) {
- synchronized (l.lock) {
+ synchronized (lock) {
final Object[] oldArray = getArrayChecked();
- boolean modified = l.addAll(offset + size, c);
- size += (expectedArray = l.getArray()).length - oldArray.length;
+ boolean modified =
+ CopyOnWriteArrayList.this.addAll(offset + size, c);
+ size += (expectedArray = getArray()).length - oldArray.length;
+ return modified;
+ }
+ }
+
+ public boolean addAll(int index, Collection extends E> c) {
+ synchronized (lock) {
+ rangeCheckForAdd(index);
+ final Object[] oldArray = getArrayChecked();
+ boolean modified =
+ CopyOnWriteArrayList.this.addAll(offset + index, c);
+ size += (expectedArray = getArray()).length - oldArray.length;
return modified;
}
}
public void clear() {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- l.removeRange(offset, offset + size);
- expectedArray = l.getArray();
+ removeRange(offset, offset + size);
+ expectedArray = getArray();
size = 0;
}
}
public E remove(int index) {
- synchronized (l.lock) {
+ synchronized (lock) {
rangeCheck(index);
checkForComodification();
- E result = l.remove(offset + index);
- expectedArray = l.getArray();
+ E result = CopyOnWriteArrayList.this.remove(offset + index);
+ expectedArray = getArray();
size--;
return result;
}
}
public boolean remove(Object o) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
int index = indexOf(o);
if (index == -1)
@@ -1301,36 +1430,35 @@
}
public Iterator iterator() {
- synchronized (l.lock) {
- checkForComodification();
- return new COWSubListIterator(l, 0, offset, size);
+ return listIterator(0);
}
+
+ public ListIterator listIterator() {
+ return listIterator(0);
}
public ListIterator listIterator(int index) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException
- (outOfBounds(index, size));
- return new COWSubListIterator(l, index, offset, size);
+ rangeCheckForAdd(index);
+ return new COWSubListIterator(
+ CopyOnWriteArrayList.this, index, offset, size);
}
}
public List subList(int fromIndex, int toIndex) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
throw new IndexOutOfBoundsException();
- return new COWSubList(l, fromIndex + offset,
- toIndex + offset);
+ return new COWSubList(expectedArray, fromIndex + offset, toIndex - fromIndex);
}
}
public void forEach(Consumer super E> action) {
Objects.requireNonNull(action);
int i, end; final Object[] es;
- synchronized (l.lock) {
+ synchronized (lock) {
es = getArrayChecked();
i = offset;
end = i + size;
@@ -1340,19 +1468,18 @@
}
public void replaceAll(UnaryOperator operator) {
- Objects.requireNonNull(operator);
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- l.replaceAll(operator, offset, offset + size);
- expectedArray = l.getArray();
+ replaceAllRange(operator, offset, offset + size);
+ expectedArray = getArray();
}
}
public void sort(Comparator super E> c) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- l.sort(c, offset, offset + size);
- expectedArray = l.getArray();
+ sortRange(c, offset, offset + size);
+ expectedArray = getArray();
}
}
@@ -1372,16 +1499,17 @@
}
private boolean bulkRemove(Predicate super E> filter) {
- synchronized (l.lock) {
+ synchronized (lock) {
final Object[] oldArray = getArrayChecked();
- boolean modified = l.bulkRemove(filter, offset, offset + size);
- size += (expectedArray = l.getArray()).length - oldArray.length;
+ boolean modified = CopyOnWriteArrayList.this.bulkRemove(
+ filter, offset, offset + size);
+ size += (expectedArray = getArray()).length - oldArray.length;
return modified;
}
}
public Spliterator spliterator() {
- synchronized (l.lock) {
+ synchronized (lock) {
return Spliterators.spliterator(
getArrayChecked(), offset, offset + size,
Spliterator.IMMUTABLE | Spliterator.ORDERED);
@@ -1447,7 +1575,7 @@
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer super E> action) {
Objects.requireNonNull(action);
- while (nextIndex() < size) {
+ while (hasNext()) {
action.accept(it.next());
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/CountedCompleter.java b/src/java.base/share/classes/java/util/concurrent/CountedCompleter.java
--- a/src/java.base/share/classes/java/util/concurrent/CountedCompleter.java
+++ b/src/java.base/share/classes/java/util/concurrent/CountedCompleter.java
@@ -775,7 +775,7 @@
PENDING = l.findVarHandle(CountedCompleter.class, "pending", int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/Exchanger.java b/src/java.base/share/classes/java/util/concurrent/Exchanger.java
--- a/src/java.base/share/classes/java/util/concurrent/Exchanger.java
+++ b/src/java.base/share/classes/java/util/concurrent/Exchanger.java
@@ -641,7 +641,7 @@
MATCH = l.findVarHandle(Node.class, "match", Object.class);
AA = MethodHandles.arrayElementVarHandle(Node[].class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java b/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java
--- a/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java
+++ b/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java
@@ -184,17 +184,22 @@
* functionality and control for a set of worker threads:
* Submissions from non-FJ threads enter into submission queues.
* Workers take these tasks and typically split them into subtasks
- * that may be stolen by other workers. Preference rules give
- * first priority to processing tasks from their own queues (LIFO
- * or FIFO, depending on mode), then to randomized FIFO steals of
- * tasks in other queues. This framework began as vehicle for
- * supporting tree-structured parallelism using work-stealing.
- * Over time, its scalability advantages led to extensions and
- * changes to better support more diverse usage contexts. Because
- * most internal methods and nested classes are interrelated,
- * their main rationale and descriptions are presented here;
- * individual methods and nested classes contain only brief
- * comments about details.
+ * that may be stolen by other workers. Work-stealing based on
+ * randomized scans generally leads to better throughput than
+ * "work dealing" in which producers assign tasks to idle threads,
+ * in part because threads that have finished other tasks before
+ * the signalled thread wakes up (which can be a long time) can
+ * take the task instead. Preference rules give first priority to
+ * processing tasks from their own queues (LIFO or FIFO, depending
+ * on mode), then to randomized FIFO steals of tasks in other
+ * queues. This framework began as vehicle for supporting
+ * tree-structured parallelism using work-stealing. Over time,
+ * its scalability advantages led to extensions and changes to
+ * better support more diverse usage contexts. Because most
+ * internal methods and nested classes are interrelated, their
+ * main rationale and descriptions are presented here; individual
+ * methods and nested classes contain only brief comments about
+ * details.
*
* WorkQueues
* ==========
@@ -227,9 +232,10 @@
*
* (The actual code needs to null-check and size-check the array,
* uses masking, not mod, for indexing a power-of-two-sized array,
- * properly fences accesses, and possibly signals waiting workers
- * to start scanning -- see below.) Both a successful pop and
- * poll mainly entail a CAS of a slot from non-null to null.
+ * adds a release fence for publication, and possibly signals
+ * waiting workers to start scanning -- see below.) Both a
+ * successful pop and poll mainly entail a CAS of a slot from
+ * non-null to null.
*
* The pop operation (always performed by owner) is:
* if ((the task at top slot is not null) and
@@ -241,9 +247,14 @@
* (CAS slot to null))
* increment base and return task;
*
- * There are several variants of each of these. In particular,
- * almost all uses of poll occur within scan operations that also
- * interleave contention tracking (with associated code sprawl.)
+ * There are several variants of each of these. Most uses occur
+ * within operations that also interleave contention or emptiness
+ * tracking or inspection of elements before extracting them, so
+ * must interleave these with the above code. When performed by
+ * owner, getAndSet is used instead of CAS (see for example method
+ * nextLocalTask) which is usually more efficient, and possible
+ * because the top index cannot independently change during the
+ * operation.
*
* Memory ordering. See "Correct and Efficient Work-Stealing for
* Weak Memory Models" by Le, Pop, Cohen, and Nardelli, PPoPP 2013
@@ -252,30 +263,37 @@
* algorithms similar to (but different than) the one used here.
* Extracting tasks in array slots via (fully fenced) CAS provides
* primary synchronization. The base and top indices imprecisely
- * guide where to extract from. We do not always require strict
- * orderings of array and index updates, so sometimes let them be
- * subject to compiler and processor reorderings. However, the
- * volatile "base" index also serves as a basis for memory
- * ordering: Slot accesses are preceded by a read of base,
- * ensuring happens-before ordering with respect to stealers (so
- * the slots themselves can be read via plain array reads.) The
- * only other memory orderings relied on are maintained in the
- * course of signalling and activation (see below). A check that
- * base == top indicates (momentary) emptiness, but otherwise may
- * err on the side of possibly making the queue appear nonempty
- * when a push, pop, or poll have not fully committed, or making
- * it appear empty when an update of top has not yet been visibly
- * written. (Method isEmpty() checks the case of a partially
- * completed removal of the last element.) Because of this, the
- * poll operation, considered individually, is not wait-free. One
- * thief cannot successfully continue until another in-progress
- * one (or, if previously empty, a push) visibly completes.
- * However, in the aggregate, we ensure at least probabilistic
+ * guide where to extract from. We do not usually require strict
+ * orderings of array and index updates. Many index accesses use
+ * plain mode, with ordering constrained by surrounding context
+ * (usually with respect to element CASes or the two WorkQueue
+ * volatile fields source and phase). When not otherwise already
+ * constrained, reads of "base" by queue owners use acquire-mode,
+ * and some externally callable methods preface accesses with
+ * acquire fences. Additionally, to ensure that index update
+ * writes are not coalesced or postponed in loops etc, "opaque"
+ * mode is used in a few cases where timely writes are not
+ * otherwise ensured. The "locked" versions of push- and pop-
+ * based methods for shared queues differ from owned versions
+ * because locking already forces some of the ordering.
+ *
+ * Because indices and slot contents cannot always be consistent,
+ * a check that base == top indicates (momentary) emptiness, but
+ * otherwise may err on the side of possibly making the queue
+ * appear nonempty when a push, pop, or poll have not fully
+ * committed, or making it appear empty when an update of top has
+ * not yet been visibly written. (Method isEmpty() checks the
+ * case of a partially completed removal of the last element.)
+ * Because of this, the poll operation, considered individually,
+ * is not wait-free. One thief cannot successfully continue until
+ * another in-progress one (or, if previously empty, a push)
+ * visibly completes. This can stall threads when required to
+ * consume from a given queue (see method poll()). However, in
+ * the aggregate, we ensure at least probabilistic
* non-blockingness. If an attempted steal fails, a scanning
* thief chooses a different random victim target to try next. So,
* in order for one thief to progress, it suffices for any
- * in-progress poll or new push on any empty queue to
- * complete.
+ * in-progress poll or new push on any empty queue to complete.
*
* This approach also enables support of a user mode in which
* local task processing is in FIFO, not LIFO order, simply by
@@ -296,7 +314,7 @@
* different position to use or create other queues -- they block
* only when creating and registering new queues. Because it is
* used only as a spinlock, unlocking requires only a "releasing"
- * store (using setRelease).
+ * store (using setRelease) unless otherwise signalling.
*
* Management
* ==========
@@ -317,10 +335,10 @@
*
* Field "ctl" contains 64 bits holding information needed to
* atomically decide to add, enqueue (on an event queue), and
- * dequeue (and release)-activate workers. To enable this
- * packing, we restrict maximum parallelism to (1<<15)-1 (which is
- * far in excess of normal operating range) to allow ids, counts,
- * and their negations (used for thresholding) to fit into 16bit
+ * dequeue and release workers. To enable this packing, we
+ * restrict maximum parallelism to (1<<15)-1 (which is far in
+ * excess of normal operating range) to allow ids, counts, and
+ * their negations (used for thresholding) to fit into 16bit
* subfields.
*
* Field "mode" holds configuration parameters as well as lifetime
@@ -332,13 +350,14 @@
* lock (using field workerNamePrefix as lock), but is otherwise
* concurrently readable, and accessed directly. We also ensure
* that uses of the array reference itself never become too stale
- * in case of resizing. To simplify index-based operations, the
- * array size is always a power of two, and all readers must
- * tolerate null slots. Worker queues are at odd indices. Shared
- * (submission) queues are at even indices, up to a maximum of 64
- * slots, to limit growth even if array needs to expand to add
- * more workers. Grouping them together in this way simplifies and
- * speeds up task scanning.
+ * in case of resizing, by arranging that (re-)reads are separated
+ * by at least one acquiring read access. To simplify index-based
+ * operations, the array size is always a power of two, and all
+ * readers must tolerate null slots. Worker queues are at odd
+ * indices. Shared (submission) queues are at even indices, up to
+ * a maximum of 64 slots, to limit growth even if the array needs
+ * to expand to add more workers. Grouping them together in this
+ * way simplifies and speeds up task scanning.
*
* All worker thread creation is on-demand, triggered by task
* submissions, replacement of terminated workers, and/or
@@ -416,8 +435,8 @@
* releases so usage requires care -- seeing a negative phase does
* not guarantee that the worker is available. When queued, the
* lower 16 bits of scanState must hold its pool index. So we
- * place the index there upon initialization (see registerWorker)
- * and otherwise keep it there or restore it when necessary.
+ * place the index there upon initialization and otherwise keep it
+ * there or restore it when necessary.
*
* The ctl field also serves as the basis for memory
* synchronization surrounding activation. This uses a more
@@ -425,48 +444,56 @@
* consumers sync with each other by both writing/CASing ctl (even
* if to its current value). This would be extremely costly. So
* we relax it in several ways: (1) Producers only signal when
- * their queue is empty. Other workers propagate this signal (in
- * method scan) when they find tasks; to further reduce flailing,
- * each worker signals only one other per activation. (2) Workers
- * only enqueue after scanning (see below) and not finding any
- * tasks. (3) Rather than CASing ctl to its current value in the
- * common case where no action is required, we reduce write
+ * their queue is possibly empty at some point during a push
+ * operation (which requires conservatively checking size zero or
+ * one to cover races). (2) Other workers propagate this signal
+ * when they find tasks in a queue with size greater than one. (3)
+ * Workers only enqueue after scanning (see below) and not finding
+ * any tasks. (4) Rather than CASing ctl to its current value in
+ * the common case where no action is required, we reduce write
* contention by equivalently prefacing signalWork when called by
* an external task producer using a memory access with
* full-volatile semantics or a "fullFence".
*
- * Almost always, too many signals are issued. A task producer
- * cannot in general tell if some existing worker is in the midst
- * of finishing one task (or already scanning) and ready to take
- * another without being signalled. So the producer might instead
- * activate a different worker that does not find any work, and
- * then inactivates. This scarcely matters in steady-state
- * computations involving all workers, but can create contention
- * and bookkeeping bottlenecks during ramp-up, ramp-down, and small
- * computations involving only a few workers.
+ * Almost always, too many signals are issued, in part because a
+ * task producer cannot tell if some existing worker is in the
+ * midst of finishing one task (or already scanning) and ready to
+ * take another without being signalled. So the producer might
+ * instead activate a different worker that does not find any
+ * work, and then inactivates. This scarcely matters in
+ * steady-state computations involving all workers, but can create
+ * contention and bookkeeping bottlenecks during ramp-up,
+ * ramp-down, and small computations involving only a few workers.
*
- * Scanning. Method runWorker performs top-level scanning for
- * tasks. Each scan traverses and tries to poll from each queue
- * starting at a random index and circularly stepping. Scans are
- * not performed in ideal random permutation order, to reduce
- * cacheline contention. The pseudorandom generator need not have
+ * Scanning. Method scan (from runWorker) performs top-level
+ * scanning for tasks. (Similar scans appear in helpQuiesce and
+ * pollScan.) Each scan traverses and tries to poll from each
+ * queue starting at a random index. Scans are not performed in
+ * ideal random permutation order, to reduce cacheline
+ * contention. The pseudorandom generator need not have
* high-quality statistical properties in the long term, but just
* within computations; We use Marsaglia XorShifts (often via
* ThreadLocalRandom.nextSecondarySeed), which are cheap and
- * suffice. Scanning also employs contention reduction: When
+ * suffice. Scanning also includes contention reduction: When
* scanning workers fail to extract an apparently existing task,
- * they soon restart at a different pseudorandom index. This
- * improves throughput when many threads are trying to take tasks
- * from few queues, which can be common in some usages. Scans do
- * not otherwise explicitly take into account core affinities,
- * loads, cache localities, etc, However, they do exploit temporal
- * locality (which usually approximates these) by preferring to
- * re-poll (at most #workers times) from the same queue after a
- * successful poll before trying others.
+ * they soon restart at a different pseudorandom index. This form
+ * of backoff improves throughput when many threads are trying to
+ * take tasks from few queues, which can be common in some usages.
+ * Scans do not otherwise explicitly take into account core
+ * affinities, loads, cache localities, etc, However, they do
+ * exploit temporal locality (which usually approximates these) by
+ * preferring to re-poll from the same queue after a successful
+ * poll before trying others (see method topLevelExec). However
+ * this preference is bounded (see TOP_BOUND_SHIFT) as a safeguard
+ * against infinitely unfair looping under unbounded user task
+ * recursion, and also to reduce long-term contention when many
+ * threads poll few queues holding many small tasks. The bound is
+ * high enough to avoid much impact on locality and scheduling
+ * overhead.
*
* Trimming workers. To release resources after periods of lack of
* use, a worker starting to wait when the pool is quiescent will
- * time out and terminate (see method scan) if the pool has
+ * time out and terminate (see method runWorker) if the pool has
* remained quiescent for period given by field keepAlive.
*
* Shutdown and Termination. A call to shutdownNow invokes
@@ -534,13 +561,14 @@
* time. Some previous versions of this class employed immediate
* compensations for any blocked join. However, in practice, the
* vast majority of blockages are transient byproducts of GC and
- * other JVM or OS activities that are made worse by replacement.
- * Rather than impose arbitrary policies, we allow users to
- * override the default of only adding threads upon apparent
- * starvation. The compensation mechanism may also be bounded.
- * Bounds for the commonPool (see COMMON_MAX_SPARES) better enable
- * JVMs to cope with programming errors and abuse before running
- * out of resources to do so.
+ * other JVM or OS activities that are made worse by replacement
+ * when they cause longer-term oversubscription. Rather than
+ * impose arbitrary policies, we allow users to override the
+ * default of only adding threads upon apparent starvation. The
+ * compensation mechanism may also be bounded. Bounds for the
+ * commonPool (see COMMON_MAX_SPARES) better enable JVMs to cope
+ * with programming errors and abuse before running out of
+ * resources to do so.
*
* Common Pool
* ===========
@@ -573,6 +601,18 @@
* in ForkJoinWorkerThread) may be JVM-dependent and must access
* particular Thread class fields to achieve this effect.
*
+ * Memory placement
+ * ================
+ *
+ * Performance can be very sensitive to placement of instances of
+ * ForkJoinPool and WorkQueues and their queue arrays. To reduce
+ * false-sharing impact, the @Contended annotation isolates
+ * adjacent WorkQueue instances, as well as the ForkJoinPool.ctl
+ * field. WorkQueue arrays are allocated (by their threads) with
+ * larger initial sizes than most ever need, mostly to reduce
+ * false sharing with current garbage collectors that use cardmark
+ * tables.
+ *
* Style notes
* ===========
*
@@ -580,13 +620,15 @@
* awkward and ugly, but also reflects the need to control
* outcomes across the unusual cases that arise in very racy code
* with very few invariants. All fields are read into locals
- * before use, and null-checked if they are references. This is
- * usually done in a "C"-like style of listing declarations at the
- * heads of methods or blocks, and using inline assignments on
- * first encounter. Nearly all explicit checks lead to
- * bypass/return, not exception throws, because they may
- * legitimately arise due to cancellation/revocation during
- * shutdown.
+ * before use, and null-checked if they are references. Array
+ * accesses using masked indices include checks (that are always
+ * true) that the array length is non-zero to avoid compilers
+ * inserting more expensive traps. This is usually done in a
+ * "C"-like style of listing declarations at the heads of methods
+ * or blocks, and using inline assignments on first encounter.
+ * Nearly all explicit checks lead to bypass/return, not exception
+ * throws, because they may legitimately arise due to
+ * cancellation/revocation during shutdown.
*
* There is a lot of representation-level coupling among classes
* ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask. The
@@ -596,10 +638,11 @@
* representations will need to be accompanied by algorithmic
* changes anyway. Several methods intrinsically sprawl because
* they must accumulate sets of consistent reads of fields held in
- * local variables. There are also other coding oddities
- * (including several unnecessary-looking hoisted null checks)
- * that help some methods perform reasonably even when interpreted
- * (not compiled).
+ * local variables. Some others are artificially broken up to
+ * reduce producer/consumer imbalances due to dynamic compilation.
+ * There are also other coding oddities (including several
+ * unnecessary-looking hoisted null checks) that help some methods
+ * perform reasonably even when interpreted (not compiled).
*
* The order of declarations in this file is (with a few exceptions):
* (1) Static utility functions
@@ -703,54 +746,43 @@
static final int DORMANT = QUIET | UNSIGNALLED;
/**
- * The maximum number of local polls from the same queue before
- * checking others. This is a safeguard against infinitely unfair
- * looping under unbounded user task recursion, and must be larger
- * than plausible cases of intentional bounded task recursion.
+ * Initial capacity of work-stealing queue array.
+ * Must be a power of two, at least 2.
*/
- static final int POLL_LIMIT = 1 << 10;
+ static final int INITIAL_QUEUE_CAPACITY = 1 << 13;
+
+ /**
+ * Maximum capacity for queue arrays. Must be a power of two less
+ * than or equal to 1 << (31 - width of array entry) to ensure
+ * lack of wraparound of index calculations, but defined to a
+ * value a bit less than this to help users trap runaway programs
+ * before saturating systems.
+ */
+ static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M
+
+ /**
+ * The maximum number of top-level polls per worker before
+ * checking other queues, expressed as a bit shift to, in effect,
+ * multiply by pool size, and then use as random value mask, so
+ * average bound is about poolSize*(1<[] array; // the elements (initially unallocated)
+ ForkJoinTask>[] array; // the queued tasks; power of 2 size
final ForkJoinPool pool; // the containing pool (may be null)
final ForkJoinWorkerThread owner; // owning thread or null if shared
@@ -762,6 +794,17 @@
}
/**
+ * Tries to lock shared queue by CASing phase field.
+ */
+ final boolean tryLockPhase() {
+ return PHASE.compareAndSet(this, 0, 1);
+ }
+
+ final void releasePhaseLock() {
+ PHASE.setRelease(this, 0);
+ }
+
+ /**
* Returns an exportable index (used by ForkJoinWorkerThread).
*/
final int getPoolIndex() {
@@ -772,7 +815,7 @@
* Returns the approximate number of tasks in the queue.
*/
final int queueSize() {
- int n = base - top; // read base first
+ int n = (int)BASE.getAcquire(this) - top;
return (n >= 0) ? 0 : -n; // ignore transient negative
}
@@ -782,11 +825,12 @@
* near-empty queue has at least one unclaimed task.
*/
final boolean isEmpty() {
- ForkJoinTask>[] a; int n, al, b;
+ ForkJoinTask>[] a; int n, cap, b;
+ VarHandle.acquireFence(); // needed by external callers
return ((n = (b = base) - top) >= 0 || // possibly one task
(n == -1 && ((a = array) == null ||
- (al = a.length) == 0 ||
- a[(al - 1) & b] == null)));
+ (cap = a.length) == 0 ||
+ a[(cap - 1) & b] == null)));
}
@@ -797,94 +841,99 @@
* @throws RejectedExecutionException if array cannot be resized
*/
final void push(ForkJoinTask> task) {
- int s = top; ForkJoinTask>[] a; int al, d;
- if ((a = array) != null && (al = a.length) > 0) {
- int index = (al - 1) & s;
+ ForkJoinTask>[] a;
+ int s = top, d, cap, m;
ForkJoinPool p = pool;
+ if ((a = array) != null && (cap = a.length) > 0) {
+ QA.setRelease(a, (m = cap - 1) & s, task);
top = s + 1;
- QA.setRelease(a, index, task);
- if ((d = base - s) == 0 && p != null) {
+ if (((d = s - (int)BASE.getAcquire(this)) & ~1) == 0 &&
+ p != null) { // size 0 or 1
VarHandle.fullFence();
p.signalWork();
}
- else if (d + al == 1)
- growArray();
+ else if (d == m)
+ growArray(false);
}
}
/**
- * Initializes or doubles the capacity of array. Call either
- * by owner or with lock held -- it is OK for base, but not
- * top, to move while resizings are in progress.
+ * Version of push for shared queues. Call only with phase lock held.
+ * @return true if should signal work
*/
- final ForkJoinTask>[] growArray() {
- ForkJoinTask>[] oldA = array;
- int oldSize = oldA != null ? oldA.length : 0;
- int size = oldSize > 0 ? oldSize << 1 : INITIAL_QUEUE_CAPACITY;
- if (size < INITIAL_QUEUE_CAPACITY || size > MAXIMUM_QUEUE_CAPACITY)
- throw new RejectedExecutionException("Queue capacity exceeded");
- int oldMask, t, b;
- ForkJoinTask>[] a = array = new ForkJoinTask>[size];
- if (oldA != null && (oldMask = oldSize - 1) > 0 &&
- (t = top) - (b = base) > 0) {
- int mask = size - 1;
- do { // emulate poll from old array, push to new array
- int index = b & oldMask;
- ForkJoinTask> x = (ForkJoinTask>)
- QA.getAcquire(oldA, index);
- if (x != null &&
- QA.compareAndSet(oldA, index, x, null))
- a[b & mask] = x;
- } while (++b != t);
- VarHandle.releaseFence();
+ final boolean lockedPush(ForkJoinTask> task) {
+ ForkJoinTask>[] a;
+ boolean signal = false;
+ int s = top, b = base, cap, d;
+ if ((a = array) != null && (cap = a.length) > 0) {
+ a[(cap - 1) & s] = task;
+ top = s + 1;
+ if (b - s + cap - 1 == 0)
+ growArray(true);
+ else {
+ phase = 0; // full volatile unlock
+ if (((s - base) & ~1) == 0) // size 0 or 1
+ signal = true;
}
- return a;
+ }
+ return signal;
}
/**
- * Takes next task, if one exists, in LIFO order. Call only
- * by owner in unshared queues.
+ * Doubles the capacity of array. Call either by owner or with
+ * lock held -- it is OK for base, but not top, to move while
+ * resizings are in progress.
*/
- final ForkJoinTask> pop() {
- int b = base, s = top, al, i; ForkJoinTask>[] a;
- if ((a = array) != null && b != s && (al = a.length) > 0) {
- int index = (al - 1) & --s;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.get(a, index);
- if (t != null &&
- QA.compareAndSet(a, index, t, null)) {
- top = s;
+ final void growArray(boolean locked) {
+ ForkJoinTask>[] newA = null;
+ try {
+ ForkJoinTask>[] oldA; int oldSize, newSize;
+ if ((oldA = array) != null && (oldSize = oldA.length) > 0 &&
+ (newSize = oldSize << 1) <= MAXIMUM_QUEUE_CAPACITY &&
+ newSize > 0) {
+ try {
+ newA = new ForkJoinTask>[newSize];
+ } catch (OutOfMemoryError ex) {
+ }
+ if (newA != null) { // poll from old array, push to new
+ int oldMask = oldSize - 1, newMask = newSize - 1;
+ for (int s = top - 1, k = oldMask; k >= 0; --k) {
+ ForkJoinTask> x = (ForkJoinTask>)
+ QA.getAndSet(oldA, s & oldMask, null);
+ if (x != null)
+ newA[s-- & newMask] = x;
+ else
+ break;
+ }
+ array = newA;
VarHandle.releaseFence();
- return t;
}
}
- return null;
+ } finally {
+ if (locked)
+ phase = 0;
+ }
+ if (newA == null)
+ throw new RejectedExecutionException("Queue capacity exceeded");
}
/**
* Takes next task, if one exists, in FIFO order.
*/
final ForkJoinTask> poll() {
- for (;;) {
- int b = base, s = top, d, al; ForkJoinTask>[] a;
- if ((a = array) != null && (d = b - s) < 0 &&
- (al = a.length) > 0) {
- int index = (al - 1) & b;
+ int b, k, cap; ForkJoinTask>[] a;
+ while ((a = array) != null && (cap = a.length) > 0 &&
+ top - (b = base) > 0) {
ForkJoinTask> t = (ForkJoinTask>)
- QA.getAcquire(a, index);
- if (b++ == base) {
- if (t != null) {
- if (QA.compareAndSet(a, index, t, null)) {
- base = b;
+ QA.getAcquire(a, k = (cap - 1) & b);
+ if (base == b++) {
+ if (t == null)
+ Thread.yield(); // await index advance
+ else if (QA.compareAndSet(a, k, t, null)) {
+ BASE.setOpaque(this, b);
return t;
}
}
- else if (d == -1)
- break; // now empty
- }
- }
- else
- break;
}
return null;
}
@@ -893,33 +942,61 @@
* Takes next task, if one exists, in order specified by mode.
*/
final ForkJoinTask> nextLocalTask() {
- return ((id & FIFO) != 0) ? poll() : pop();
+ ForkJoinTask> t = null;
+ int md = id, b, s, d, cap; ForkJoinTask>[] a;
+ if ((a = array) != null && (cap = a.length) > 0 &&
+ (d = (s = top) - (b = base)) > 0) {
+ if ((md & FIFO) == 0 || d == 1) {
+ if ((t = (ForkJoinTask>)
+ QA.getAndSet(a, (cap - 1) & --s, null)) != null)
+ TOP.setOpaque(this, s);
+ }
+ else if ((t = (ForkJoinTask>)
+ QA.getAndSet(a, (cap - 1) & b++, null)) != null) {
+ BASE.setOpaque(this, b);
+ }
+ else // on contention in FIFO mode, use regular poll
+ t = poll();
+ }
+ return t;
}
/**
* Returns next task, if one exists, in order specified by mode.
*/
final ForkJoinTask> peek() {
- int al; ForkJoinTask>[] a;
- return ((a = array) != null && (al = a.length) > 0) ?
- a[(al - 1) &
- ((id & FIFO) != 0 ? base : top - 1)] : null;
+ int cap; ForkJoinTask>[] a;
+ return ((a = array) != null && (cap = a.length) > 0) ?
+ a[(cap - 1) & ((id & FIFO) != 0 ? base : top - 1)] : null;
}
/**
* Pops the given task only if it is at the current top.
*/
final boolean tryUnpush(ForkJoinTask> task) {
- int b = base, s = top, al; ForkJoinTask>[] a;
- if ((a = array) != null && b != s && (al = a.length) > 0) {
- int index = (al - 1) & --s;
- if (QA.compareAndSet(a, index, task, null)) {
+ boolean popped = false;
+ int s, cap; ForkJoinTask>[] a;
+ if ((a = array) != null && (cap = a.length) > 0 &&
+ (s = top) != base &&
+ (popped = QA.compareAndSet(a, (cap - 1) & --s, task, null)))
+ TOP.setOpaque(this, s);
+ return popped;
+ }
+
+ /**
+ * Shared version of tryUnpush.
+ */
+ final boolean tryLockedUnpush(ForkJoinTask> task) {
+ boolean popped = false;
+ int s = top - 1, k, cap; ForkJoinTask>[] a;
+ if ((a = array) != null && (cap = a.length) > 0 &&
+ a[k = (cap - 1) & s] == task && tryLockPhase()) {
+ if (top == s + 1 && array == a &&
+ (popped = QA.compareAndSet(a, k, task, null)))
top = s;
- VarHandle.releaseFence();
- return true;
+ releasePhaseLock();
}
- }
- return false;
+ return popped;
}
/**
@@ -933,58 +1010,29 @@
// Specialized execution methods
/**
- * Pops and executes up to limit consecutive tasks or until empty.
- *
- * @param limit max runs, or zero for no limit
+ * Runs the given (stolen) task if nonnull, as well as
+ * remaining local tasks and others available from the given
+ * queue, up to bound n (to avoid infinite unfairness).
*/
- final void localPopAndExec(int limit) {
+ final void topLevelExec(ForkJoinTask> t, WorkQueue q, int n) {
+ if (t != null && q != null) { // hoist checks
+ int nstolen = 1;
for (;;) {
- int b = base, s = top, al; ForkJoinTask>[] a;
- if ((a = array) != null && b != s && (al = a.length) > 0) {
- int index = (al - 1) & --s;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.getAndSet(a, index, null);
- if (t != null) {
- top = s;
- VarHandle.releaseFence();
t.doExec();
- if (limit != 0 && --limit == 0)
+ if (n-- < 0)
break;
- }
+ else if ((t = nextLocalTask()) == null) {
+ if ((t = q.poll()) == null)
+ break;
else
- break;
- }
- else
- break;
+ ++nstolen;
}
}
-
- /**
- * Polls and executes up to limit consecutive tasks or until empty.
- *
- * @param limit, or zero for no limit
- */
- final void localPollAndExec(int limit) {
- for (int polls = 0;;) {
- int b = base, s = top, d, al; ForkJoinTask>[] a;
- if ((a = array) != null && (d = b - s) < 0 &&
- (al = a.length) > 0) {
- int index = (al - 1) & b++;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.getAndSet(a, index, null);
- if (t != null) {
- base = b;
- t.doExec();
- if (limit != 0 && ++polls == limit)
- break;
- }
- else if (d == -1)
- break; // now empty
- else
- polls = 0; // stolen; reset
- }
- else
- break;
+ ForkJoinWorkerThread thread = owner;
+ nsteals += nstolen;
+ source = 0;
+ if (thread != null)
+ thread.afterTopLevelExec();
}
}
@@ -992,25 +1040,24 @@
* If present, removes task from queue and executes it.
*/
final void tryRemoveAndExec(ForkJoinTask> task) {
- ForkJoinTask>[] wa; int s, wal;
- if (base - (s = top) < 0 && // traverse from top
- (wa = array) != null && (wal = wa.length) > 0) {
- for (int m = wal - 1, ns = s - 1, i = ns; ; --i) {
+ ForkJoinTask>[] a; int s, cap;
+ if ((a = array) != null && (cap = a.length) > 0 &&
+ (s = top) - base > 0) { // traverse from top
+ for (int m = cap - 1, ns = s - 1, i = ns; ; --i) {
int index = i & m;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.get(wa, index);
+ ForkJoinTask> t = (ForkJoinTask>)QA.get(a, index);
if (t == null)
break;
else if (t == task) {
- if (QA.compareAndSet(wa, index, t, null)) {
+ if (QA.compareAndSet(a, index, t, null)) {
top = ns; // safely shift down
for (int j = i; j != ns; ++j) {
ForkJoinTask> f;
int pindex = (j + 1) & m;
- f = (ForkJoinTask>)QA.get(wa, pindex);
- QA.setVolatile(wa, pindex, null);
+ f = (ForkJoinTask>)QA.get(a, pindex);
+ QA.setVolatile(a, pindex, null);
int jindex = j & m;
- QA.setRelease(wa, jindex, f);
+ QA.setRelease(a, jindex, f);
}
VarHandle.releaseFence();
t.doExec();
@@ -1022,43 +1069,52 @@
}
/**
- * Tries to steal and run tasks within the target's
- * computation until done, not found, or limit exceeded.
+ * Tries to pop and run tasks within the target's computation
+ * until done, not found, or limit exceeded.
*
* @param task root of CountedCompleter computation
* @param limit max runs, or zero for no limit
+ * @param shared true if must lock to extract task
* @return task status on exit
*/
- final int localHelpCC(CountedCompleter> task, int limit) {
+ final int helpCC(CountedCompleter> task, int limit, boolean shared) {
int status = 0;
if (task != null && (status = task.status) >= 0) {
- for (;;) {
- boolean help = false;
- int b = base, s = top, al; ForkJoinTask>[] a;
- if ((a = array) != null && b != s && (al = a.length) > 0) {
- int index = (al - 1) & (s - 1);
- ForkJoinTask> o = (ForkJoinTask>)
- QA.get(a, index);
+ int s, k, cap; ForkJoinTask>[] a;
+ while ((a = array) != null && (cap = a.length) > 0 &&
+ (s = top) - base > 0) {
+ CountedCompleter> v = null;
+ ForkJoinTask> o = a[k = (cap - 1) & (s - 1)];
if (o instanceof CountedCompleter) {
CountedCompleter> t = (CountedCompleter>)o;
for (CountedCompleter> f = t;;) {
if (f != task) {
- if ((f = f.completer) == null) // try parent
+ if ((f = f.completer) == null)
+ break;
+ }
+ else if (shared) {
+ if (tryLockPhase()) {
+ if (top == s && array == a &&
+ QA.compareAndSet(a, k, t, null)) {
+ top = s - 1;
+ v = t;
+ }
+ releasePhaseLock();
+ }
break;
}
else {
- if (QA.compareAndSet(a, index, t, null)) {
+ if (QA.compareAndSet(a, k, t, null)) {
top = s - 1;
- VarHandle.releaseFence();
- t.doExec();
- help = true;
+ v = t;
}
break;
}
}
}
- }
- if ((status = task.status) < 0 || !help ||
+ if (v != null)
+ v.doExec();
+ if ((status = task.status) < 0 || v == null ||
(limit != 0 && --limit == 0))
break;
}
@@ -1066,79 +1122,31 @@
return status;
}
- // Operations on shared queues
-
/**
- * Tries to lock shared queue by CASing phase field.
- */
- final boolean tryLockSharedQueue() {
- return PHASE.compareAndSet(this, 0, QLOCK);
- }
-
- /**
- * Shared version of tryUnpush.
+ * Tries to poll and run AsynchronousCompletionTasks until
+ * none found or blocker is released
+ *
+ * @param blocker the blocker
*/
- final boolean trySharedUnpush(ForkJoinTask> task) {
- boolean popped = false;
- int s = top - 1, al; ForkJoinTask>[] a;
- if ((a = array) != null && (al = a.length) > 0) {
- int index = (al - 1) & s;
- ForkJoinTask> t = (ForkJoinTask>) QA.get(a, index);
- if (t == task &&
- PHASE.compareAndSet(this, 0, QLOCK)) {
- if (top == s + 1 && array == a &&
- QA.compareAndSet(a, index, task, null)) {
- popped = true;
- top = s;
- }
- PHASE.setRelease(this, 0);
- }
- }
- return popped;
- }
-
- /**
- * Shared version of localHelpCC.
- */
- final int sharedHelpCC(CountedCompleter> task, int limit) {
- int status = 0;
- if (task != null && (status = task.status) >= 0) {
- for (;;) {
- boolean help = false;
- int b = base, s = top, al; ForkJoinTask>[] a;
- if ((a = array) != null && b != s && (al = a.length) > 0) {
- int index = (al - 1) & (s - 1);
- ForkJoinTask> o = (ForkJoinTask>)
- QA.get(a, index);
- if (o instanceof CountedCompleter) {
- CountedCompleter> t = (CountedCompleter>)o;
- for (CountedCompleter> f = t;;) {
- if (f != task) {
- if ((f = f.completer) == null)
+ final void helpAsyncBlocker(ManagedBlocker blocker) {
+ if (blocker != null) {
+ int b, k, cap; ForkJoinTask>[] a; ForkJoinTask> t;
+ while ((a = array) != null && (cap = a.length) > 0 &&
+ top - (b = base) > 0) {
+ t = (ForkJoinTask>)QA.getAcquire(a, k = (cap - 1) & b);
+ if (blocker.isReleasable())
break;
- }
- else {
- if (PHASE.compareAndSet(this, 0, QLOCK)) {
- if (top == s && array == a &&
- QA.compareAndSet(a, index, t, null)) {
- help = true;
- top = s - 1;
- }
- PHASE.setRelease(this, 0);
- if (help)
+ else if (base == b++ && t != null) {
+ if (!(t instanceof CompletableFuture.
+ AsynchronousCompletionTask))
+ break;
+ else if (QA.compareAndSet(a, k, t, null)) {
+ BASE.setOpaque(this, b);
t.doExec();
}
- break;
- }
}
}
}
- if ((status = task.status) < 0 || !help ||
- (limit != 0 && --limit == 0))
- break;
- }
- }
- return status;
}
/**
@@ -1153,13 +1161,17 @@
}
// VarHandle mechanics.
- private static final VarHandle PHASE;
+ static final VarHandle PHASE;
+ static final VarHandle BASE;
+ static final VarHandle TOP;
static {
try {
MethodHandles.Lookup l = MethodHandles.lookup();
PHASE = l.findVarHandle(WorkQueue.class, "phase", int.class);
+ BASE = l.findVarHandle(WorkQueue.class, "base", int.class);
+ TOP = l.findVarHandle(WorkQueue.class, "top", int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
@@ -1356,39 +1368,37 @@
wt.setDaemon(true); // configure thread
if ((handler = ueh) != null)
wt.setUncaughtExceptionHandler(handler);
- WorkQueue w = new WorkQueue(this, wt);
int tid = 0; // for thread name
- int fifo = mode & FIFO;
+ int idbits = mode & FIFO;
String prefix = workerNamePrefix;
+ WorkQueue w = new WorkQueue(this, wt);
if (prefix != null) {
synchronized (prefix) {
WorkQueue[] ws = workQueues; int n;
int s = indexSeed += SEED_INCREMENT;
+ idbits |= (s & ~(SMASK | FIFO | DORMANT));
if (ws != null && (n = ws.length) > 1) {
int m = n - 1;
- tid = s & m;
- int i = m & ((s << 1) | 1); // odd-numbered indices
+ tid = m & ((s << 1) | 1); // odd-numbered indices
for (int probes = n >>> 1;;) { // find empty slot
WorkQueue q;
- if ((q = ws[i]) == null || q.phase == QUIET)
+ if ((q = ws[tid]) == null || q.phase == QUIET)
break;
else if (--probes == 0) {
- i = n | 1; // resize below
+ tid = n | 1; // resize below
break;
}
else
- i = (i + 2) & m;
+ tid = (tid + 2) & m;
}
+ w.phase = w.id = tid | idbits; // now publishable
- int id = i | fifo | (s & ~(SMASK | FIFO | DORMANT));
- w.phase = w.id = id; // now publishable
-
- if (i < n)
- ws[i] = w;
+ if (tid < n)
+ ws[tid] = w;
else { // expand array
int an = n << 1;
WorkQueue[] as = new WorkQueue[an];
- as[i] = w;
+ as[tid] = w;
int am = an - 1;
for (int j = 0; j < n; ++j) {
WorkQueue v; // copy external queue
@@ -1421,14 +1431,14 @@
int phase = 0;
if (wt != null && (w = wt.workQueue) != null) {
Object lock = workerNamePrefix;
+ int wid = w.id;
long ns = (long)w.nsteals & 0xffffffffL;
- int idx = w.id & SMASK;
if (lock != null) {
- WorkQueue[] ws; // remove index from array
synchronized (lock) {
- if ((ws = workQueues) != null && ws.length > idx &&
- ws[idx] == w)
- ws[idx] = null;
+ WorkQueue[] ws; int n, i; // remove index from array
+ if ((ws = workQueues) != null && (n = ws.length) > 0 &&
+ ws[i = wid & (n - 1)] == w)
+ ws[i] = null;
stealCount += ns;
}
}
@@ -1480,7 +1490,7 @@
Thread vt = v.owner;
if (sp == vp && CTL.compareAndSet(this, c, nc)) {
v.phase = np;
- if (v.source < 0)
+ if (vt != null && v.source < 0)
LockSupport.unpark(vt);
break;
}
@@ -1521,7 +1531,7 @@
long nc = ((long)v.stackPred & SP_MASK) | uc;
if (vp == sp && CTL.compareAndSet(this, c, nc)) {
v.phase = np;
- if (v.source < 0)
+ if (vt != null && v.source < 0)
LockSupport.unpark(vt);
return (wp < 0) ? -1 : 1;
}
@@ -1578,98 +1588,85 @@
* See above for explanation.
*/
final void runWorker(WorkQueue w) {
- WorkQueue[] ws;
- w.growArray(); // allocate queue
- int r = w.id ^ ThreadLocalRandom.nextSecondarySeed();
- if (r == 0) // initial nonzero seed
- r = 1;
- int lastSignalId = 0; // avoid unneeded signals
- while ((ws = workQueues) != null) {
- boolean nonempty = false; // scan
- for (int n = ws.length, j = n, m = n - 1; j > 0; --j) {
- WorkQueue q; int i, b, al; ForkJoinTask>[] a;
- if ((i = r & m) >= 0 && i < n && // always true
- (q = ws[i]) != null && (b = q.base) - q.top < 0 &&
- (a = q.array) != null && (al = a.length) > 0) {
- int qid = q.id; // (never zero)
- int index = (al - 1) & b;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.getAcquire(a, index);
- if (t != null && b++ == q.base &&
- QA.compareAndSet(a, index, t, null)) {
- if ((q.base = b) - q.top < 0 && qid != lastSignalId)
- signalWork(); // propagate signal
- w.source = lastSignalId = qid;
- t.doExec();
- if ((w.id & FIFO) != 0) // run remaining locals
- w.localPollAndExec(POLL_LIMIT);
- else
- w.localPopAndExec(POLL_LIMIT);
- ForkJoinWorkerThread thread = w.owner;
- ++w.nsteals;
- w.source = 0; // now idle
- if (thread != null)
- thread.afterTopLevelExec();
+ int r = (w.id ^ ThreadLocalRandom.nextSecondarySeed()) | FIFO; // rng
+ w.array = new ForkJoinTask>[INITIAL_QUEUE_CAPACITY]; // initialize
+ for (;;) {
+ int phase;
+ if (scan(w, r)) { // scan until apparently empty
+ r ^= r << 13; r ^= r >>> 17; r ^= r << 5; // move (xorshift)
}
- nonempty = true;
- }
- else if (nonempty)
- break;
- else
- ++r;
- }
-
- if (nonempty) { // move (xorshift)
- r ^= r << 13; r ^= r >>> 17; r ^= r << 5;
- }
- else {
- int phase;
- lastSignalId = 0; // clear for next scan
- if ((phase = w.phase) >= 0) { // enqueue
- int np = w.phase = (phase + SS_SEQ) | UNSIGNALLED;
+ else if ((phase = w.phase) >= 0) { // enqueue, then rescan
+ long np = (w.phase = (phase + SS_SEQ) | UNSIGNALLED) & SP_MASK;
long c, nc;
do {
w.stackPred = (int)(c = ctl);
- nc = ((c - RC_UNIT) & UC_MASK) | (SP_MASK & np);
+ nc = ((c - RC_UNIT) & UC_MASK) | np;
} while (!CTL.weakCompareAndSet(this, c, nc));
}
else { // already queued
int pred = w.stackPred;
+ Thread.interrupted(); // clear before park
w.source = DORMANT; // enable signal
- for (int steps = 0;;) {
- int md, rc; long c;
- if (w.phase >= 0) {
- w.source = 0;
+ long c = ctl;
+ int md = mode, rc = (md & SMASK) + (int)(c >> RC_SHIFT);
+ if (md < 0) // terminating
+ break;
+ else if (rc <= 0 && (md & SHUTDOWN) != 0 &&
+ tryTerminate(false, false))
+ break; // quiescent shutdown
+ else if (rc <= 0 && pred != 0 && phase == (int)c) {
+ long nc = (UC_MASK & (c - TC_UNIT)) | (SP_MASK & pred);
+ long d = keepAlive + System.currentTimeMillis();
+ LockSupport.parkUntil(this, d);
+ if (ctl == c && // drop on timeout if all idle
+ d - System.currentTimeMillis() <= TIMEOUT_SLOP &&
+ CTL.compareAndSet(this, c, nc)) {
+ w.phase = QUIET;
break;
}
- else if ((md = mode) < 0) // shutting down
- return;
- else if ((rc = ((md & SMASK) + // possibly quiescent
- (int)((c = ctl) >> RC_SHIFT))) <= 0 &&
- (md & SHUTDOWN) != 0 &&
- tryTerminate(false, false))
- return; // help terminate
- else if ((++steps & 1) == 0)
- Thread.interrupted(); // clear between parks
- else if (rc <= 0 && pred != 0 && phase == (int)c) {
- long d = keepAlive + System.currentTimeMillis();
- LockSupport.parkUntil(this, d);
- if (ctl == c &&
- d - System.currentTimeMillis() <= TIMEOUT_SLOP) {
- long nc = ((UC_MASK & (c - TC_UNIT)) |
- (SP_MASK & pred));
- if (CTL.compareAndSet(this, c, nc)) {
- w.phase = QUIET;
- return; // drop on timeout
+ }
+ else if (w.phase < 0)
+ LockSupport.park(this); // OK if spuriously woken
+ w.source = 0; // disable signal
}
}
}
- else
- LockSupport.park(this);
+
+ /**
+ * Scans for and if found executes one or more top-level tasks from a queue.
+ *
+ * @return true if found an apparently non-empty queue, and
+ * possibly ran task(s).
+ */
+ private boolean scan(WorkQueue w, int r) {
+ WorkQueue[] ws; int n;
+ if ((ws = workQueues) != null && (n = ws.length) > 0 && w != null) {
+ for (int m = n - 1, j = r & m;;) {
+ WorkQueue q; int b;
+ if ((q = ws[j]) != null && q.top != (b = q.base)) {
+ int qid = q.id;
+ ForkJoinTask>[] a; int cap, k; ForkJoinTask> t;
+ if ((a = q.array) != null && (cap = a.length) > 0) {
+ t = (ForkJoinTask>)QA.getAcquire(a, k = (cap - 1) & b);
+ if (q.base == b++ && t != null &&
+ QA.compareAndSet(a, k, t, null)) {
+ q.base = b;
+ w.source = qid;
+ if (q.top - b > 0)
+ signalWork();
+ w.topLevelExec(t, q, // random fairness bound
+ r & ((n << TOP_BOUND_SHIFT) - 1));
}
}
+ return true;
+ }
+ else if (--n > 0)
+ j = (j + 1) & m;
+ else
+ break;
}
}
+ return false;
}
/**
@@ -1685,42 +1682,44 @@
*/
final int awaitJoin(WorkQueue w, ForkJoinTask> task, long deadline) {
int s = 0;
+ int seed = ThreadLocalRandom.nextSecondarySeed();
if (w != null && task != null &&
(!(task instanceof CountedCompleter) ||
- (s = w.localHelpCC((CountedCompleter>)task, 0)) >= 0)) {
+ (s = w.helpCC((CountedCompleter>)task, 0, false)) >= 0)) {
w.tryRemoveAndExec(task);
int src = w.source, id = w.id;
+ int r = (seed >>> 16) | 1, step = (seed & ~1) | 2;
s = task.status;
while (s >= 0) {
WorkQueue[] ws;
- boolean nonempty = false;
- int r = ThreadLocalRandom.nextSecondarySeed() | 1; // odd indices
- if ((ws = workQueues) != null) { // scan for matching id
- for (int n = ws.length, m = n - 1, j = -n; j < n; j += 2) {
- WorkQueue q; int i, b, al; ForkJoinTask>[] a;
- if ((i = (r + j) & m) >= 0 && i < n &&
- (q = ws[i]) != null && q.source == id &&
- (b = q.base) - q.top < 0 &&
- (a = q.array) != null && (al = a.length) > 0) {
+ int n = (ws = workQueues) == null ? 0 : ws.length, m = n - 1;
+ while (n > 0) {
+ WorkQueue q; int b;
+ if ((q = ws[r & m]) != null && q.source == id &&
+ q.top != (b = q.base)) {
+ ForkJoinTask>[] a; int cap, k;
int qid = q.id;
- int index = (al - 1) & b;
+ if ((a = q.array) != null && (cap = a.length) > 0) {
ForkJoinTask> t = (ForkJoinTask>)
- QA.getAcquire(a, index);
- if (t != null && b++ == q.base && id == q.source &&
- QA.compareAndSet(a, index, t, null)) {
+ QA.getAcquire(a, k = (cap - 1) & b);
+ if (q.source == id && q.base == b++ &&
+ t != null && QA.compareAndSet(a, k, t, null)) {
q.base = b;
w.source = qid;
t.doExec();
w.source = src;
}
- nonempty = true;
+ }
break;
}
+ else {
+ r += step;
+ --n;
}
}
if ((s = task.status) < 0)
break;
- else if (!nonempty) {
+ else if (n == 0) { // empty scan
long ms, ns; int block;
if (deadline == 0L)
ms = 0L; // untimed
@@ -1745,46 +1744,46 @@
* find tasks either.
*/
final void helpQuiescePool(WorkQueue w) {
- int prevSrc = w.source, fifo = w.id & FIFO;
+ int prevSrc = w.source;
+ int seed = ThreadLocalRandom.nextSecondarySeed();
+ int r = seed >>> 16, step = r | 1;
for (int source = prevSrc, released = -1;;) { // -1 until known
- WorkQueue[] ws;
- if (fifo != 0)
- w.localPollAndExec(0);
- else
- w.localPopAndExec(0);
- if (released == -1 && w.phase >= 0)
+ ForkJoinTask> localTask; WorkQueue[] ws;
+ while ((localTask = w.nextLocalTask()) != null)
+ localTask.doExec();
+ if (w.phase >= 0 && released == -1)
released = 1;
boolean quiet = true, empty = true;
- int r = ThreadLocalRandom.nextSecondarySeed();
- if ((ws = workQueues) != null) {
- for (int n = ws.length, j = n, m = n - 1; j > 0; --j) {
- WorkQueue q; int i, b, al; ForkJoinTask>[] a;
- if ((i = (r - j) & m) >= 0 && i < n && (q = ws[i]) != null) {
- if ((b = q.base) - q.top < 0 &&
- (a = q.array) != null && (al = a.length) > 0) {
+ int n = (ws = workQueues) == null ? 0 : ws.length;
+ for (int m = n - 1; n > 0; r += step, --n) {
+ WorkQueue q; int b;
+ if ((q = ws[r & m]) != null) {
+ int qs = q.source;
+ if (q.top != (b = q.base)) {
+ quiet = empty = false;
+ ForkJoinTask>[] a; int cap, k;
int qid = q.id;
+ if ((a = q.array) != null && (cap = a.length) > 0) {
if (released == 0) { // increment
released = 1;
CTL.getAndAdd(this, RC_UNIT);
}
- int index = (al - 1) & b;
ForkJoinTask> t = (ForkJoinTask>)
- QA.getAcquire(a, index);
- if (t != null && b++ == q.base &&
- QA.compareAndSet(a, index, t, null)) {
+ QA.getAcquire(a, k = (cap - 1) & b);
+ if (q.base == b++ && t != null &&
+ QA.compareAndSet(a, k, t, null)) {
q.base = b;
- w.source = source = q.id;
+ w.source = qid;
t.doExec();
w.source = source = prevSrc;
}
- quiet = empty = false;
+ }
break;
}
- else if ((q.source & QUIET) == 0)
+ else if ((qs & QUIET) == 0)
quiet = false;
}
}
- }
if (quiet) {
if (released == 0)
CTL.getAndAdd(this, RC_UNIT);
@@ -1824,28 +1823,24 @@
origin = r & m;
step = h | 1;
}
- for (int k = origin, oldSum = 0, checkSum = 0;;) {
- WorkQueue q; int b, al; ForkJoinTask>[] a;
- if ((q = ws[k]) != null) {
- checkSum += b = q.base;
- if (b - q.top < 0 &&
- (a = q.array) != null && (al = a.length) > 0) {
- int index = (al - 1) & b;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.getAcquire(a, index);
- if (t != null && b++ == q.base &&
- QA.compareAndSet(a, index, t, null)) {
- q.base = b;
+ boolean nonempty = false;
+ for (int i = origin, oldSum = 0, checkSum = 0;;) {
+ WorkQueue q;
+ if ((q = ws[i]) != null) {
+ int b; ForkJoinTask> t;
+ if (q.top - (b = q.base) > 0) {
+ nonempty = true;
+ if ((t = q.poll()) != null)
return t;
}
else
- break; // restart
+ checkSum += b + q.id;
}
- }
- if ((k = (k + step) & m) == origin) {
- if (oldSum == (oldSum = checkSum))
+ if ((i = (i + step) & m) == origin) {
+ if (!nonempty && oldSum == (oldSum = checkSum))
break rescan;
checkSum = 0;
+ nonempty = false;
}
}
}
@@ -1859,11 +1854,9 @@
*/
final ForkJoinTask> nextTaskFor(WorkQueue w) {
ForkJoinTask> t;
- if (w != null &&
- (t = (w.id & FIFO) != 0 ? w.poll() : w.pop()) != null)
+ if (w == null || (t = w.nextLocalTask()) == null)
+ t = pollScan(false);
return t;
- else
- return pollScan(false);
}
// External operations
@@ -1881,64 +1874,35 @@
r = ThreadLocalRandom.getProbe();
}
for (;;) {
+ WorkQueue q;
int md = mode, n;
WorkQueue[] ws = workQueues;
if ((md & SHUTDOWN) != 0 || ws == null || (n = ws.length) <= 0)
throw new RejectedExecutionException();
- else {
- WorkQueue q;
- boolean push = false, grow = false;
- if ((q = ws[(n - 1) & r & SQMASK]) == null) {
+ else if ((q = ws[(n - 1) & r & SQMASK]) == null) { // add queue
+ int qid = (r | QUIET) & ~(FIFO | OWNED);
Object lock = workerNamePrefix;
- int qid = (r | QUIET) & ~(FIFO | OWNED);
+ ForkJoinTask>[] qa =
+ new ForkJoinTask>[INITIAL_QUEUE_CAPACITY];
q = new WorkQueue(this, null);
+ q.array = qa;
q.id = qid;
q.source = QUIET;
- q.phase = QLOCK; // lock queue
- if (lock != null) {
- synchronized (lock) { // lock pool to install
- int i;
- if ((ws = workQueues) != null &&
- (n = ws.length) > 0 &&
- ws[i = qid & (n - 1) & SQMASK] == null) {
- ws[i] = q;
- push = grow = true;
- }
+ if (lock != null) { // unless disabled, lock pool to install
+ synchronized (lock) {
+ WorkQueue[] vs; int i, vn;
+ if ((vs = workQueues) != null && (vn = vs.length) > 0 &&
+ vs[i = qid & (vn - 1) & SQMASK] == null)
+ vs[i] = q; // else another thread already installed
}
}
}
- else if (q.tryLockSharedQueue()) {
- int b = q.base, s = q.top, al, d; ForkJoinTask>[] a;
- if ((a = q.array) != null && (al = a.length) > 0 &&
- al - 1 + (d = b - s) > 0) {
- a[(al - 1) & s] = task;
- q.top = s + 1; // relaxed writes OK here
- q.phase = 0;
- if (d < 0 && q.base - s < -1)
- break; // no signal needed
- }
- else
- grow = true;
- push = true;
- }
- if (push) {
- if (grow) {
- try {
- q.growArray();
- int s = q.top, al; ForkJoinTask>[] a;
- if ((a = q.array) != null && (al = a.length) > 0) {
- a[(al - 1) & s] = task;
- q.top = s + 1;
- }
- } finally {
- q.phase = 0;
- }
- }
+ else if (!q.tryLockPhase()) // move if busy
+ r = ThreadLocalRandom.advanceProbe(r);
+ else {
+ if (q.lockedPush(task))
signalWork();
- break;
- }
- else // move if busy
- r = ThreadLocalRandom.advanceProbe(r);
+ return;
}
}
}
@@ -1980,7 +1944,7 @@
return ((ws = workQueues) != null &&
(n = ws.length) > 0 &&
(w = ws[(n - 1) & r & SQMASK]) != null &&
- w.trySharedUnpush(task));
+ w.tryLockedUnpush(task));
}
/**
@@ -1991,7 +1955,7 @@
WorkQueue[] ws; WorkQueue w; int n;
return ((ws = workQueues) != null && (n = ws.length) > 0 &&
(w = ws[(n - 1) & r & SQMASK]) != null) ?
- w.sharedHelpCC(task, maxTasks) : 0;
+ w.helpCC(task, maxTasks, true) : 0;
}
/**
@@ -2006,7 +1970,7 @@
*/
final int helpComplete(WorkQueue w, CountedCompleter> task,
int maxTasks) {
- return (w == null) ? 0 : w.localHelpCC(task, maxTasks);
+ return (w == null) ? 0 : w.helpCC(task, maxTasks, false);
}
/**
@@ -2097,15 +2061,18 @@
if ((md & SMASK) + (int)(checkSum >> RC_SHIFT) > 0)
running = true;
else if (ws != null) {
- WorkQueue w; int b;
+ WorkQueue w;
for (int i = 0; i < ws.length; ++i) {
if ((w = ws[i]) != null) {
- checkSum += (b = w.base) + w.id;
+ int s = w.source, p = w.phase;
+ int d = w.id, b = w.base;
if (b != w.top ||
- ((i & 1) == 1 && w.source >= 0)) {
+ ((d & 1) == 1 && (s >= 0 || p >= 0))) {
running = true;
- break;
+ break; // working, scanning, or have work
}
+ checkSum += (((long)s << 48) + ((long)p << 32) +
+ ((long)b << 16) + (long)d);
}
}
}
@@ -2136,7 +2103,7 @@
} catch (Throwable ignore) {
}
}
- checkSum += w.base + w.id;
+ checkSum += ((long)w.phase << 32) + w.base;
}
}
}
@@ -2629,8 +2596,9 @@
* @return the number of worker threads
*/
public int getRunningThreadCount() {
+ WorkQueue[] ws; WorkQueue w;
+ VarHandle.acquireFence();
int rc = 0;
- WorkQueue[] ws; WorkQueue w;
if ((ws = workQueues) != null) {
for (int i = 1; i < ws.length; i += 2) {
if ((w = ws[i]) != null && w.isApparentlyUnblocked())
@@ -2678,7 +2646,7 @@
if ((ws = workQueues) != null) {
for (int i = 1; i < ws.length; i += 2) {
if ((v = ws[i]) != null) {
- if ((v.source & QUIET) == 0)
+ if (v.source > 0)
return false;
--tc;
}
@@ -2724,8 +2692,9 @@
* @return the number of queued tasks
*/
public long getQueuedTaskCount() {
- long count = 0;
WorkQueue[] ws; WorkQueue w;
+ VarHandle.acquireFence();
+ int count = 0;
if ((ws = workQueues) != null) {
for (int i = 1; i < ws.length; i += 2) {
if ((w = ws[i]) != null)
@@ -2743,8 +2712,9 @@
* @return the number of queued submissions
*/
public int getQueuedSubmissionCount() {
+ WorkQueue[] ws; WorkQueue w;
+ VarHandle.acquireFence();
int count = 0;
- WorkQueue[] ws; WorkQueue w;
if ((ws = workQueues) != null) {
for (int i = 0; i < ws.length; i += 2) {
if ((w = ws[i]) != null)
@@ -2762,6 +2732,7 @@
*/
public boolean hasQueuedSubmissions() {
WorkQueue[] ws; WorkQueue w;
+ VarHandle.acquireFence();
if ((ws = workQueues) != null) {
for (int i = 0; i < ws.length; i += 2) {
if ((w = ws[i]) != null && !w.isEmpty())
@@ -2800,8 +2771,9 @@
* @return the number of elements transferred
*/
protected int drainTasksTo(Collection super ForkJoinTask>> c) {
+ WorkQueue[] ws; WorkQueue w; ForkJoinTask> t;
+ VarHandle.acquireFence();
int count = 0;
- WorkQueue[] ws; WorkQueue w; ForkJoinTask> t;
if ((ws = workQueues) != null) {
for (int i = 0; i < ws.length; ++i) {
if ((w = ws[i]) != null) {
@@ -2824,8 +2796,10 @@
*/
public String toString() {
// Use a single pass through workQueues to collect counts
+ int md = mode; // read volatile fields first
+ long c = ctl;
+ long st = stealCount;
long qt = 0L, qs = 0L; int rc = 0;
- long st = stealCount;
WorkQueue[] ws; WorkQueue w;
if ((ws = workQueues) != null) {
for (int i = 0; i < ws.length; ++i) {
@@ -2843,9 +2817,7 @@
}
}
- int md = mode;
int pc = (md & SMASK);
- long c = ctl;
int tc = pc + (short)(c >>> TC_SHIFT);
int ac = pc + (int)(c >> RC_SHIFT);
if (ac < 0) // ignore transient negative
@@ -3131,6 +3103,7 @@
*/
public static void managedBlock(ManagedBlocker blocker)
throws InterruptedException {
+ if (blocker == null) throw new NullPointerException();
ForkJoinPool p;
ForkJoinWorkerThread wt;
WorkQueue w;
@@ -3163,7 +3136,7 @@
* available or blocker is released.
*/
static void helpAsyncBlocker(Executor e, ManagedBlocker blocker) {
- if (blocker != null && (e instanceof ForkJoinPool)) {
+ if (e instanceof ForkJoinPool) {
WorkQueue w; ForkJoinWorkerThread wt; WorkQueue[] ws; int r, n;
ForkJoinPool p = (ForkJoinPool)e;
Thread thread = Thread.currentThread();
@@ -3175,34 +3148,8 @@
w = ws[(n - 1) & r & SQMASK];
else
w = null;
- if (w != null) {
- for (;;) {
- int b = w.base, s = w.top, d, al; ForkJoinTask>[] a;
- if ((a = w.array) != null && (d = b - s) < 0 &&
- (al = a.length) > 0) {
- int index = (al - 1) & b;
- ForkJoinTask> t = (ForkJoinTask>)
- QA.getAcquire(a, index);
- if (blocker.isReleasable())
- break;
- else if (b++ == w.base) {
- if (t == null) {
- if (d == -1)
- break;
- }
- else if (!(t instanceof CompletableFuture.
- AsynchronousCompletionTask))
- break;
- else if (QA.compareAndSet(a, index, t, null)) {
- w.base = b;
- t.doExec();
- }
- }
- }
- else
- break;
- }
- }
+ if (w != null)
+ w.helpAsyncBlocker(blocker);
}
}
@@ -3221,7 +3168,7 @@
// VarHandle mechanics
private static final VarHandle CTL;
private static final VarHandle MODE;
- private static final VarHandle QA;
+ static final VarHandle QA;
static {
try {
@@ -3230,7 +3177,7 @@
MODE = l.findVarHandle(ForkJoinPool.class, "mode", int.class);
QA = MethodHandles.arrayElementVarHandle(ForkJoinTask[].class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/ForkJoinTask.java b/src/java.base/share/classes/java/util/concurrent/ForkJoinTask.java
--- a/src/java.base/share/classes/java/util/concurrent/ForkJoinTask.java
+++ b/src/java.base/share/classes/java/util/concurrent/ForkJoinTask.java
@@ -1540,7 +1540,7 @@
MethodHandles.Lookup l = MethodHandles.lookup();
STATUS = l.findVarHandle(ForkJoinTask.class, "status", int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/FutureTask.java b/src/java.base/share/classes/java/util/concurrent/FutureTask.java
--- a/src/java.base/share/classes/java/util/concurrent/FutureTask.java
+++ b/src/java.base/share/classes/java/util/concurrent/FutureTask.java
@@ -526,7 +526,7 @@
RUNNER = l.findVarHandle(FutureTask.class, "runner", Thread.class);
WAITERS = l.findVarHandle(FutureTask.class, "waiters", WaitNode.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/LinkedTransferQueue.java b/src/java.base/share/classes/java/util/concurrent/LinkedTransferQueue.java
--- a/src/java.base/share/classes/java/util/concurrent/LinkedTransferQueue.java
+++ b/src/java.base/share/classes/java/util/concurrent/LinkedTransferQueue.java
@@ -1739,7 +1739,7 @@
NEXT = l.findVarHandle(Node.class, "next", Node.class);
WAITER = l.findVarHandle(Node.class, "waiter", Thread.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/Phaser.java b/src/java.base/share/classes/java/util/concurrent/Phaser.java
--- a/src/java.base/share/classes/java/util/concurrent/Phaser.java
+++ b/src/java.base/share/classes/java/util/concurrent/Phaser.java
@@ -1137,7 +1137,7 @@
MethodHandles.Lookup l = MethodHandles.lookup();
STATE = l.findVarHandle(Phaser.class, "state", long.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java b/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java
--- a/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java
+++ b/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java
@@ -1014,7 +1014,7 @@
"allocationSpinLock",
int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java b/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java
--- a/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java
+++ b/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java
@@ -1096,7 +1096,7 @@
if (cap > 0) {
boolean added;
if (n >= cap && cap < maxCapacity) // resize
- added = growAndoffer(item, a, t);
+ added = growAndOffer(item, a, t);
else if (n >= cap || unowned) // need volatile CAS
added = QA.compareAndSet(a, i, null, item);
else { // can use release mode
@@ -1115,7 +1115,7 @@
* Tries to expand buffer and add item, returning true on
* success. Currently fails only if out of memory.
*/
- final boolean growAndoffer(T item, Object[] a, int t) {
+ final boolean growAndOffer(T item, Object[] a, int t) {
int cap = 0, newCap = 0;
Object[] newArray = null;
if (a != null && (cap = a.length) > 0 && (newCap = cap << 1) > 0) {
@@ -1466,7 +1466,7 @@
long.class);
QA = MethodHandles.arrayElementVarHandle(Object[].class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/SynchronousQueue.java b/src/java.base/share/classes/java/util/concurrent/SynchronousQueue.java
--- a/src/java.base/share/classes/java/util/concurrent/SynchronousQueue.java
+++ b/src/java.base/share/classes/java/util/concurrent/SynchronousQueue.java
@@ -293,7 +293,7 @@
SMATCH = l.findVarHandle(SNode.class, "match", SNode.class);
SNEXT = l.findVarHandle(SNode.class, "next", SNode.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
@@ -516,7 +516,7 @@
MethodHandles.Lookup l = MethodHandles.lookup();
SHEAD = l.findVarHandle(TransferStack.class, "head", SNode.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
@@ -583,7 +583,7 @@
QITEM = l.findVarHandle(QNode.class, "item", Object.class);
QNEXT = l.findVarHandle(QNode.class, "next", QNode.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
@@ -830,7 +830,7 @@
QCLEANME = l.findVarHandle(TransferQueue.class, "cleanMe",
QNode.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicBoolean.java b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicBoolean.java
--- a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicBoolean.java
+++ b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicBoolean.java
@@ -56,7 +56,7 @@
MethodHandles.Lookup l = MethodHandles.lookup();
VALUE = l.findVarHandle(AtomicBoolean.class, "value", int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicMarkableReference.java b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicMarkableReference.java
--- a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicMarkableReference.java
+++ b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicMarkableReference.java
@@ -199,7 +199,7 @@
PAIR = l.findVarHandle(AtomicMarkableReference.class, "pair",
Pair.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicReference.java b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicReference.java
--- a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicReference.java
+++ b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicReference.java
@@ -56,7 +56,7 @@
MethodHandles.Lookup l = MethodHandles.lookup();
VALUE = l.findVarHandle(AtomicReference.class, "value", Object.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicStampedReference.java b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicStampedReference.java
--- a/src/java.base/share/classes/java/util/concurrent/atomic/AtomicStampedReference.java
+++ b/src/java.base/share/classes/java/util/concurrent/atomic/AtomicStampedReference.java
@@ -199,7 +199,7 @@
PAIR = l.findVarHandle(AtomicStampedReference.class, "pair",
Pair.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/atomic/Striped64.java b/src/java.base/share/classes/java/util/concurrent/atomic/Striped64.java
--- a/src/java.base/share/classes/java/util/concurrent/atomic/Striped64.java
+++ b/src/java.base/share/classes/java/util/concurrent/atomic/Striped64.java
@@ -144,7 +144,7 @@
MethodHandles.Lookup l = MethodHandles.lookup();
VALUE = l.findVarHandle(Cell.class, "value", long.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
@@ -396,13 +396,13 @@
try {
return MethodHandles.privateLookupIn(Thread.class, MethodHandles.lookup());
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}});
THREAD_PROBE = l.findVarHandle(Thread.class,
"threadLocalRandomProbe", int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
diff --git a/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java b/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
--- a/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
+++ b/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
@@ -1830,7 +1830,7 @@
HEAD = l.findVarHandle(AbstractQueuedLongSynchronizer.class, "head", Node.class);
TAIL = l.findVarHandle(AbstractQueuedLongSynchronizer.class, "tail", Node.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedSynchronizer.java b/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedSynchronizer.java
--- a/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedSynchronizer.java
+++ b/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedSynchronizer.java
@@ -555,7 +555,7 @@
THREAD = l.findVarHandle(Node.class, "thread", Thread.class);
WAITSTATUS = l.findVarHandle(Node.class, "waitStatus", int.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
@@ -2308,7 +2308,7 @@
HEAD = l.findVarHandle(AbstractQueuedSynchronizer.class, "head", Node.class);
TAIL = l.findVarHandle(AbstractQueuedSynchronizer.class, "tail", Node.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
// Reduce the risk of rare disastrous classloading in first call to
diff --git a/src/java.base/share/classes/java/util/concurrent/locks/StampedLock.java b/src/java.base/share/classes/java/util/concurrent/locks/StampedLock.java
--- a/src/java.base/share/classes/java/util/concurrent/locks/StampedLock.java
+++ b/src/java.base/share/classes/java/util/concurrent/locks/StampedLock.java
@@ -1614,7 +1614,7 @@
WNEXT = l.findVarHandle(WNode.class, "next", WNode.class);
WCOWAIT = l.findVarHandle(WNode.class, "cowait", WNode.class);
} catch (ReflectiveOperationException e) {
- throw new Error(e);
+ throw new ExceptionInInitializerError(e);
}
}
}
diff --git a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java
--- a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java
+++ b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java
@@ -36,6 +36,7 @@
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
@@ -55,6 +56,7 @@
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.LongAdder;
+import java.util.function.UnaryOperator;
import java.util.regex.Pattern;
import java.util.stream.Stream;
@@ -75,6 +77,13 @@
public Job(String name) { this.name = name; }
public String name() { return name; }
public abstract void work() throws Throwable;
+ public void run() {
+ try { work(); }
+ catch (Throwable ex) {
+ // current job cannot always be deduced from stacktrace.
+ throw new RuntimeException("Job failed: " + name(), ex);
+ }
+ }
}
final int iterations;
@@ -102,6 +111,7 @@
static void forceFullGc() {
CountDownLatch finalizeDone = new CountDownLatch(1);
WeakReference> ref = new WeakReference(new Object() {
+ @SuppressWarnings("deprecation")
protected void finalize() { finalizeDone.countDown(); }});
try {
for (int i = 0; i < 10; i++) {
@@ -123,7 +133,7 @@
* compiling everything worth compiling.
* Returns array of average times per job per run.
*/
- long[] time0(List jobs) throws Throwable {
+ long[] time0(List jobs) {
final int size = jobs.size();
long[] nanoss = new long[size];
for (int i = 0; i < size; i++) {
@@ -132,7 +142,7 @@
long totalTime;
int runs = 0;
long startTime = System.nanoTime();
- do { job.work(); runs++; }
+ do { job.run(); runs++; }
while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
nanoss[i] = totalTime/runs;
}
@@ -211,10 +221,6 @@
System.out.println("the answer");
}
- private static List asSubList(List list) {
- return list.subList(0, list.size());
- }
-
private static Iterable backwards(final List list) {
return new Iterable() {
public Iterator iterator() {
@@ -241,11 +247,32 @@
new IteratorMicroBenchmark(args).run();
}
+ HashMap, String> goodClassName = new HashMap<>();
+
+ String goodClassName(Class> klazz) {
+ return goodClassName.computeIfAbsent(
+ klazz,
+ k -> {
+ String simple = k.getSimpleName();
+ return (simple.equals("SubList")) // too simple!
+ ? k.getName().replaceFirst(".*\\.", "")
+ : simple;
+ });
+ }
+
+ static List makeSubList(List list) {
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ int size = list.size();
+ if (size <= 2) return list.subList(0, size);
+ List subList = list.subList(rnd.nextInt(0, 2),
+ size - rnd.nextInt(0, 2));
+ List copy = new ArrayList<>(list);
+ subList.clear();
+ subList.addAll(copy);
+ return subList;
+ }
+
void run() throws Throwable {
-// System.out.printf(
-// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
-// iterations, size, warmupSeconds, nameFilter);
-
final ArrayList al = new ArrayList<>(size);
// Populate collections with random data
@@ -265,10 +292,14 @@
ArrayList jobs = Stream.>of(
al, ad, abq,
+ makeSubList(new ArrayList<>(al)),
new LinkedList<>(al),
+ makeSubList(new LinkedList<>(al)),
new PriorityQueue<>(al),
new Vector<>(al),
+ makeSubList(new Vector<>(al)),
new CopyOnWriteArrayList<>(al),
+ makeSubList(new CopyOnWriteArrayList<>(al)),
new ConcurrentLinkedQueue<>(al),
new ConcurrentLinkedDeque<>(al),
new LinkedBlockingQueue<>(al),
@@ -302,8 +333,15 @@
: Stream.empty());
}
+ Object sneakyAdder(int[] sneakySum) {
+ return new Object() {
+ public int hashCode() { throw new AssertionError(); }
+ public boolean equals(Object z) {
+ sneakySum[0] += (int) z; return false; }};
+ }
+
Stream collectionJobs(Collection x) {
- String klazz = x.getClass().getSimpleName();
+ final String klazz = goodClassName(x.getClass());
return Stream.of(
new Job(klazz + " iterate for loop") {
public void work() throws Throwable {
@@ -345,22 +383,28 @@
new Job(klazz + " contains") {
public void work() throws Throwable {
int[] sum = new int[1];
- Object y = new Object() {
- public boolean equals(Object z) {
- sum[0] += (int) z; return false; }};
+ Object sneakyAdder = sneakyAdder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- if (x.contains(y)) throw new AssertionError();
+ if (x.contains(sneakyAdder)) throw new AssertionError();
+ check.sum(sum[0]);}}},
+ new Job(klazz + " containsAll") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ Collection sneakyAdderCollection =
+ Collections.singleton(sneakyAdder(sum));
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ if (x.containsAll(sneakyAdderCollection))
+ throw new AssertionError();
check.sum(sum[0]);}}},
new Job(klazz + " remove(Object)") {
public void work() throws Throwable {
int[] sum = new int[1];
- Object y = new Object() {
- public boolean equals(Object z) {
- sum[0] += (int) z; return false; }};
+ Object sneakyAdder = sneakyAdder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- if (x.remove(y)) throw new AssertionError();
+ if (x.remove(sneakyAdder)) throw new AssertionError();
check.sum(sum[0]);}}},
new Job(klazz + " forEach") {
public void work() throws Throwable {
@@ -446,7 +490,7 @@
}
Stream dequeJobs(Deque x) {
- String klazz = x.getClass().getSimpleName();
+ String klazz = goodClassName(x.getClass());
return Stream.of(
new Job(klazz + " descendingIterator() loop") {
public void work() throws Throwable {
@@ -466,48 +510,50 @@
}
Stream listJobs(List x) {
- String klazz = x.getClass().getSimpleName();
+ final String klazz = goodClassName(x.getClass());
return Stream.of(
- new Job(klazz + " subList toArray()") {
+ new Job(klazz + " listIterator forward loop") {
public void work() throws Throwable {
- int size = x.size();
- for (int i = 0; i < iterations; i++) {
- int total = Stream.of(x.subList(0, size / 2),
- x.subList(size / 2, size))
- .mapToInt(subList -> {
- int sum = 0;
- for (Object o : subList.toArray())
- sum += (Integer) o;
- return sum; })
- .sum();
- check.sum(total);}}},
- new Job(klazz + " subList toArray(a)") {
- public void work() throws Throwable {
- int size = x.size();
for (int i = 0; i < iterations; i++) {
- int total = Stream.of(x.subList(0, size / 2),
- x.subList(size / 2, size))
- .mapToInt(subList -> {
int sum = 0;
- Integer[] a = new Integer[subList.size()];
- for (Object o : subList.toArray(a))
- sum += (Integer) o;
- return sum; })
- .sum();
- check.sum(total);}}},
- new Job(klazz + " subList toArray(empty)") {
+ ListIterator it = x.listIterator();
+ while (it.hasNext())
+ sum += it.next();
+ check.sum(sum);}}},
+ new Job(klazz + " listIterator backward loop") {
public void work() throws Throwable {
- int size = x.size();
- Integer[] empty = new Integer[0];
for (int i = 0; i < iterations; i++) {
- int total = Stream.of(x.subList(0, size / 2),
- x.subList(size / 2, size))
- .mapToInt(subList -> {
int sum = 0;
- for (Object o : subList.toArray(empty))
- sum += (Integer) o;
- return sum; })
- .sum();
- check.sum(total);}}});
+ ListIterator it = x.listIterator(x.size());
+ while (it.hasPrevious())
+ sum += it.previous();
+ check.sum(sum);}}},
+ new Job(klazz + " indexOf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ Object sneakyAdder = sneakyAdder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ if (x.indexOf(sneakyAdder) != -1)
+ throw new AssertionError();
+ check.sum(sum[0]);}}},
+ new Job(klazz + " lastIndexOf") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ Object sneakyAdder = sneakyAdder(sum);
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ if (x.lastIndexOf(sneakyAdder) != -1)
+ throw new AssertionError();
+ check.sum(sum[0]);}}},
+ new Job(klazz + " replaceAll") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ UnaryOperator sneakyAdder =
+ x -> { sum[0] += x; return x; };
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.replaceAll(sneakyAdder);
+ check.sum(sum[0]);}}});
}
}
diff --git a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java
--- a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java
+++ b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java
@@ -27,7 +27,7 @@
* @run main RemoveMicroBenchmark iterations=1 size=8 warmup=0
*/
-import static java.util.stream.Collectors.toList;
+import static java.util.stream.Collectors.toCollection;
import java.lang.ref.WeakReference;
import java.util.ArrayDeque;
@@ -35,6 +35,7 @@
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
@@ -47,6 +48,7 @@
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
@@ -55,7 +57,7 @@
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.regex.Pattern;
-import java.util.function.Supplier;
+import java.util.stream.Stream;
/**
* Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
@@ -72,25 +74,38 @@
public Job(String name) { this.name = name; }
public String name() { return name; }
public abstract void work() throws Throwable;
+ public void run() {
+ try { work(); }
+ catch (Throwable ex) {
+ // current job cannot always be deduced from stacktrace.
+ throw new RuntimeException("Job failed: " + name(), ex);
+ }
+ }
}
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 Pattern nameFilter; // select subset of Jobs to run
final boolean reverse; // reverse order of Jobs
final boolean shuffle; // randomize order of Jobs
+ final ArrayList elements; // contains size random Integers
+
RemoveMicroBenchmark(String[] args) {
iterations = intArg(args, "iterations", 10_000);
size = intArg(args, "size", 1000);
warmupSeconds = doubleArg(args, "warmup", 7.0);
- filter = patternArg(args, "filter");
+ nameFilter = patternArg(args, "filter");
reverse = booleanArg(args, "reverse");
shuffle = booleanArg(args, "shuffle");
warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+
+ elements = ThreadLocalRandom.current().ints(size)
+ .mapToObj(x -> x)
+ .collect(toCollection(ArrayList::new));
}
// --------------- GC finalization infrastructure ---------------
@@ -99,6 +114,7 @@
static void forceFullGc() {
CountDownLatch finalizeDone = new CountDownLatch(1);
WeakReference> ref = new WeakReference(new Object() {
+ @SuppressWarnings("deprecation")
protected void finalize() { finalizeDone.countDown(); }});
try {
for (int i = 0; i < 10; i++) {
@@ -120,7 +136,7 @@
* compiling everything worth compiling.
* Returns array of average times per job per run.
*/
- long[] time0(List jobs) throws Throwable {
+ long[] time0(List jobs) {
final int size = jobs.size();
long[] nanoss = new long[size];
for (int i = 0; i < size; i++) {
@@ -129,7 +145,7 @@
long totalTime;
int runs = 0;
long startTime = System.nanoTime();
- do { job.work(); runs++; }
+ do { job.run(); runs++; }
while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
nanoss[i] = totalTime/runs;
}
@@ -203,22 +219,11 @@
throw new IllegalArgumentException(val);
}
- private static List filter(Pattern filter, List jobs) {
- return (filter == null) ? jobs
- : jobs.stream()
- .filter(job -> filter.matcher(job.name()).find())
- .collect(toList());
- }
-
private static void deoptimize(int sum) {
if (sum == 42)
System.out.println("the answer");
}
- private static List asSubList(List list) {
- return list.subList(0, list.size());
- }
-
private static Iterable backwards(final List list) {
return new Iterable() {
public Iterator iterator() {
@@ -245,66 +250,99 @@
new RemoveMicroBenchmark(args).run();
}
- void run() throws Throwable {
-// System.out.printf(
-// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
-// iterations, size, warmupSeconds, filter);
+ HashMap, String> goodClassName = new HashMap<>();
- final ArrayList al = new ArrayList<>(size);
+ String goodClassName(Class> klazz) {
+ return goodClassName.computeIfAbsent(
+ klazz,
+ k -> {
+ String simple = k.getSimpleName();
+ return (simple.equals("SubList")) // too simple!
+ ? k.getName().replaceFirst(".*\\.", "")
+ : simple;
+ });
+ }
- // Populate collections with random data
+ static List makeSubList(List list) {
final ThreadLocalRandom rnd = ThreadLocalRandom.current();
- for (int i = 0; i < size; i++)
- al.add(rnd.nextInt(size));
+ int size = rnd.nextInt(4);
+ for (int i = size; i--> 0; )
+ list.add(rnd.nextInt());
+ int index = rnd.nextInt(size + 1);
+ return list.subList(index, index);
+ }
- ArrayList jobs = new ArrayList<>();
+ private static List asSubList(List list) {
+ return list.subList(0, list.size());
+ }
- List.>of(
+ @SafeVarargs @SuppressWarnings("varargs")
+ private Stream concatStreams(Stream ... streams) {
+ return Stream.of(streams).flatMap(s -> s);
+ }
+
+ Class> topLevelClass(Object x) {
+ for (Class> k = x.getClass();; ) {
+ Class> enclosing = k.getEnclosingClass();
+ if (enclosing == null)
+ return k;
+ k = enclosing;
+ }
+ }
+
+ void run() throws Throwable {
+ ArrayList jobs = Stream.>of(
new ArrayList<>(),
+ makeSubList(new ArrayList<>()),
new LinkedList<>(),
+ makeSubList(new LinkedList<>()),
new Vector<>(),
+ makeSubList(new Vector<>()),
+ new CopyOnWriteArrayList<>(),
+ makeSubList(new CopyOnWriteArrayList<>()),
new ArrayDeque<>(),
new PriorityQueue<>(),
- new ArrayBlockingQueue<>(al.size()),
+ new ArrayBlockingQueue<>(elements.size()),
new ConcurrentLinkedQueue<>(),
new ConcurrentLinkedDeque<>(),
new LinkedBlockingQueue<>(),
new LinkedBlockingDeque<>(),
new LinkedTransferQueue<>(),
- new PriorityBlockingQueue<>()).forEach(
- x -> {
- String klazz = x.getClass().getSimpleName();
- jobs.addAll(collectionJobs(klazz, () -> x, al));
- if (x instanceof Queue) {
- Queue queue = (Queue) x;
- jobs.addAll(queueJobs(klazz, () -> queue, al));
- }
- if (x instanceof Deque) {
- Deque deque = (Deque) x;
- jobs.addAll(dequeJobs(klazz, () -> deque, al));
- }
- if (x instanceof BlockingQueue) {
- BlockingQueue q = (BlockingQueue) x;
- jobs.addAll(blockingQueueJobs(klazz, () -> q, al));
- }
- if (x instanceof BlockingDeque) {
- BlockingDeque q = (BlockingDeque) x;
- jobs.addAll(blockingDequeJobs(klazz, () -> q, al));
- }
- if (x instanceof List) {
- List list = (List) x;
- jobs.addAll(
- collectionJobs(
- klazz + " subList",
- () -> list.subList(0, x.size()),
- al));
- }
- });
+ new PriorityBlockingQueue<>())
+ .flatMap(x -> jobs(x))
+ .filter(job ->
+ nameFilter == null || nameFilter.matcher(job.name()).find())
+ .collect(toCollection(ArrayList::new));
if (reverse) Collections.reverse(jobs);
if (shuffle) Collections.shuffle(jobs);
- time(filter(filter, jobs));
+ time(jobs);
+ }
+
+ Stream jobs(Collection x) {
+ return concatStreams(
+ collectionJobs(x),
+
+ (CopyOnWriteArrayList.class.isAssignableFrom(topLevelClass(x)))
+ ? Stream.empty()
+ : iteratorRemoveJobs(x),
+
+ (x instanceof Queue)
+ ? queueJobs((Queue)x)
+ : Stream.empty(),
+
+ (x instanceof Deque)
+ ? dequeJobs((Deque)x)
+ : Stream.empty(),
+
+ (x instanceof BlockingQueue)
+ ? blockingQueueJobs((BlockingQueue)x)
+ : Stream.empty(),
+
+ (x instanceof BlockingDeque)
+ ? blockingDequeJobs((BlockingDeque)x)
+ : Stream.empty());
}
Collection universeRecorder(int[] sum) {
@@ -323,75 +361,81 @@
}};
}
- List collectionJobs(
- String description,
- Supplier> supplier,
- ArrayList al) {
- return List.of(
- new Job(description + " removeIf") {
+ Stream collectionJobs(Collection x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " removeIf") {
public void work() throws Throwable {
- Collection x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
x.removeIf(n -> { sum[0] += n; return true; });
check.sum(sum[0]);}}},
- new Job(description + " removeIf rnd-two-pass") {
+ new Job(klazz + " removeIf rnd-two-pass") {
public void work() throws Throwable {
ThreadLocalRandom rnd = ThreadLocalRandom.current();
- Collection x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
x.removeIf(n -> {
boolean b = rnd.nextBoolean();
if (b) sum[0] += n;
return b; });
x.removeIf(n -> { sum[0] += n; return true; });
check.sum(sum[0]);}}},
- new Job(description + " removeAll") {
+ new Job(klazz + " removeAll") {
public void work() throws Throwable {
- Collection x = supplier.get();
int[] sum = new int[1];
Collection universe = universeRecorder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
x.removeAll(universe);
check.sum(sum[0]);}}},
- new Job(description + " retainAll") {
+ new Job(klazz + " retainAll") {
public void work() throws Throwable {
- Collection x = supplier.get();
int[] sum = new int[1];
Collection empty = emptyRecorder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
x.retainAll(empty);
check.sum(sum[0]);}}},
- new Job(description + " Iterator.remove") {
+ new Job(klazz + " clear") {
public void work() throws Throwable {
- Collection x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
+ x.forEach(e -> sum[0] += e);
+ x.clear();
+ check.sum(sum[0]);}}});
+ }
+
+ Stream iteratorRemoveJobs(Collection x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " Iterator.remove") {
+ public void work() throws Throwable {
+ int[] sum = new int[1];
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.addAll(elements);
Iterator it = x.iterator();
while (it.hasNext()) {
sum[0] += it.next();
it.remove();
}
check.sum(sum[0]);}}},
- new Job(description + " Iterator.remove-rnd-two-pass") {
+ new Job(klazz + " Iterator.remove-rnd-two-pass") {
public void work() throws Throwable {
ThreadLocalRandom rnd = ThreadLocalRandom.current();
- Collection x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Iterator it = x.iterator();
it.hasNext(); ) {
Integer e = it.next();
@@ -405,129 +449,103 @@
sum[0] += it.next();
it.remove();
}
- check.sum(sum[0]);}}},
- new Job(description + " clear") {
+ check.sum(sum[0]);}}});
+ }
+
+ Stream queueJobs(Queue x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " poll()") {
public void work() throws Throwable {
- Collection 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 queueJobs(
- String description,
- Supplier> supplier,
- ArrayList al) {
- return List.of(
- new Job(description + " poll()") {
- public void work() throws Throwable {
- Queue x = supplier.get();
- int[] sum = new int[1];
- for (int i = 0; i < iterations; i++) {
- sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Integer e; (e = x.poll()) != null; )
sum[0] += e;
check.sum(sum[0]);}}});
}
- List dequeJobs(
- String description,
- Supplier> supplier,
- ArrayList al) {
- return List.of(
- new Job(description + " descendingIterator().remove") {
+ Stream dequeJobs(Deque x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " descendingIterator().remove") {
public void work() throws Throwable {
- Deque x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
Iterator it = x.descendingIterator();
while (it.hasNext()) {
sum[0] += it.next();
it.remove();
}
check.sum(sum[0]);}}},
- new Job(description + " pollFirst()") {
+ new Job(klazz + " pollFirst()") {
public void work() throws Throwable {
- Deque x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Integer e; (e = x.pollFirst()) != null; )
sum[0] += e;
check.sum(sum[0]);}}},
- new Job(description + " pollLast()") {
+ new Job(klazz + " pollLast()") {
public void work() throws Throwable {
- Deque x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Integer e; (e = x.pollLast()) != null; )
sum[0] += e;
check.sum(sum[0]);}}});
}
- List blockingQueueJobs(
- String description,
- Supplier> supplier,
- ArrayList al) {
- return List.of(
- new Job(description + " drainTo(sink)") {
+ Stream blockingQueueJobs(BlockingQueue x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " drainTo(sink)") {
public void work() throws Throwable {
- BlockingQueue x = supplier.get();
ArrayList sink = new ArrayList<>();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
sink.clear();
- x.addAll(al);
+ x.addAll(elements);
x.drainTo(sink);
sink.forEach(e -> sum[0] += e);
check.sum(sum[0]);}}},
- new Job(description + " drainTo(sink, n)") {
+ new Job(klazz + " drainTo(sink, n)") {
public void work() throws Throwable {
- BlockingQueue x = supplier.get();
ArrayList 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());
+ x.addAll(elements);
+ x.drainTo(sink, elements.size());
sink.forEach(e -> sum[0] += e);
check.sum(sum[0]);}}});
}
- List blockingDequeJobs(
- String description,
- Supplier> supplier,
- ArrayList al) {
- return List.of(
- new Job(description + " timed pollFirst()") {
+ Stream blockingDequeJobs(BlockingDeque x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " timed pollFirst()") {
public void work() throws Throwable {
- BlockingDeque x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Integer e; (e = x.pollFirst(0L, TimeUnit.DAYS)) != null; )
sum[0] += e;
check.sum(sum[0]);}}},
- new Job(description + " timed pollLast()") {
+ new Job(klazz + " timed pollLast()") {
public void work() throws Throwable {
- BlockingDeque x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Integer e; (e = x.pollLast(0L, TimeUnit.DAYS)) != null; )
sum[0] += e;
check.sum(sum[0]);}}});
diff --git a/test/jdk/java/util/concurrent/ConcurrentHashMap/WhiteBox.java b/test/jdk/java/util/concurrent/ConcurrentHashMap/WhiteBox.java
new file mode 100644
--- /dev/null
+++ b/test/jdk/java/util/concurrent/ConcurrentHashMap/WhiteBox.java
@@ -0,0 +1,155 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Martin Buchholz with assistance from members of JCP
+ * JSR-166 Expert Group and released to the public domain, as
+ * explained at http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+/*
+ * @test
+ * @modules java.base/java.util.concurrent:open
+ * @run testng WhiteBox
+ * @summary White box tests of implementation details
+ */
+
+import static org.testng.Assert.*;
+import org.testng.annotations.Test;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ThreadLocalRandom;
+
+@Test
+public class WhiteBox {
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ final VarHandle TABLE, NEXTTABLE, SIZECTL;
+
+ WhiteBox() throws ReflectiveOperationException {
+ Class> mClass = ConcurrentHashMap.class;
+ String nodeClassName = mClass.getName() + "$Node";
+ Class> nodeClass = Class.forName(nodeClassName);
+ Class> nodeArrayClass = Class.forName("[L" + nodeClassName + ";");
+ MethodHandles.Lookup lookup
+ = MethodHandles.privateLookupIn(mClass, MethodHandles.lookup());
+ TABLE = lookup.findVarHandle(mClass, "table", nodeArrayClass);
+ NEXTTABLE = lookup.findVarHandle(mClass, "nextTable", nodeArrayClass);
+ SIZECTL = lookup.findVarHandle(mClass, "sizeCtl", int.class);
+ }
+
+ Object[] table(ConcurrentHashMap m) { return (Object[]) TABLE.getVolatile(m); }
+ Object[] nextTable(ConcurrentHashMap m) { return (Object[]) NEXTTABLE.getVolatile(m); }
+ int sizeCtl(ConcurrentHashMap m) { return (int) SIZECTL.getVolatile(m); }
+
+ @Test
+ public void defaultConstructor() {
+ ConcurrentHashMap m = new ConcurrentHashMap();
+ assertNull(table(m));
+ assertEquals(sizeCtl(m), 0);
+ assertResizeNotInProgress(m);
+ }
+
+ @Test
+ public void shouldNotResizeWhenInitialCapacityProvided() {
+ int initialCapacity = rnd.nextInt(1, 100);
+ Object[] initialTable = null;
+ ConcurrentHashMap m = new ConcurrentHashMap(initialCapacity);
+
+ // table is lazily initialized
+ assertNull(table(m));
+ int expectedInitialTableLength = sizeCtl(m);
+
+ assertInvariants(m);
+ for (int i = 0; i < initialCapacity; i++) {
+ m.put(i * 100 + rnd.nextInt(100), i);
+ if (i == 0)
+ initialTable = table(m);
+ else
+ assertSame(table(m), initialTable);
+ assertInvariants(m);
+ }
+ assertEquals(initialTable.length, expectedInitialTableLength);
+ }
+
+ byte[] serialBytes(Object o) {
+ try {
+ ByteArrayOutputStream bos = new ByteArrayOutputStream();
+ ObjectOutputStream oos = new ObjectOutputStream(bos);
+ oos.writeObject(o);
+ oos.flush();
+ oos.close();
+ return bos.toByteArray();
+ } catch (Exception fail) {
+ throw new AssertionError(fail);
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ T serialClone(T o) {
+ try {
+ ObjectInputStream ois = new ObjectInputStream
+ (new ByteArrayInputStream(serialBytes(o)));
+ T clone = (T) ois.readObject();
+ assertNotSame(o, clone);
+ assertSame(o.getClass(), clone.getClass());
+ return clone;
+ } catch (Exception fail) {
+ throw new AssertionError(fail);
+ }
+ }
+
+ @Test
+ public void testSerialization() {
+ assertInvariants(serialClone(new ConcurrentHashMap()));
+
+ ConcurrentHashMap m = new ConcurrentHashMap(rnd.nextInt(100));
+ m.put(1, 1);
+ ConcurrentHashMap clone = serialClone(m);
+ assertInvariants(clone);
+ assertNotSame(table(m), table(clone));
+ assertEquals(m, clone);
+ assertResizeNotInProgress(m);
+ assertResizeNotInProgress(clone);
+ }
+
+ /** Checks conditions which should always be true. */
+ void assertInvariants(ConcurrentHashMap m) {
+ if (!m.isEmpty())
+ assertNotNull(table(m));
+ }
+
+ void assertResizeNotInProgress(ConcurrentHashMap m) {
+ assertTrue(sizeCtl(m) >= 0);
+ assertNull(nextTable(m));
+ }
+}
diff --git a/test/jdk/java/util/concurrent/ConcurrentLinkedQueue/WhiteBox.java b/test/jdk/java/util/concurrent/ConcurrentLinkedQueue/WhiteBox.java
--- a/test/jdk/java/util/concurrent/ConcurrentLinkedQueue/WhiteBox.java
+++ b/test/jdk/java/util/concurrent/ConcurrentLinkedQueue/WhiteBox.java
@@ -338,6 +338,7 @@
}
}
+ @Test
public void testSerialization() {
ConcurrentLinkedQueue q = serialClone(new ConcurrentLinkedQueue());
assertInvariants(q);
diff --git a/test/jdk/java/util/concurrent/Executors/PrivilegedCallables.java b/test/jdk/java/util/concurrent/Executors/PrivilegedCallables.java
--- a/test/jdk/java/util/concurrent/Executors/PrivilegedCallables.java
+++ b/test/jdk/java/util/concurrent/Executors/PrivilegedCallables.java
@@ -101,8 +101,7 @@
final Policy policy = new Policy();
Policy.setPolicy(policy);
policy.setPermissions(new RuntimePermission("getClassLoader"),
- new RuntimePermission("setContextClassLoader"),
- new RuntimePermission("stopThread"));
+ new RuntimePermission("setContextClassLoader"));
System.setSecurityManager(new SecurityManager());
testPrivileged();
diff --git a/test/jdk/java/util/concurrent/LinkedTransferQueue/WhiteBox.java b/test/jdk/java/util/concurrent/LinkedTransferQueue/WhiteBox.java
--- a/test/jdk/java/util/concurrent/LinkedTransferQueue/WhiteBox.java
+++ b/test/jdk/java/util/concurrent/LinkedTransferQueue/WhiteBox.java
@@ -361,6 +361,7 @@
}
}
+ @Test
public void testSerialization() {
LinkedTransferQueue q = serialClone(new LinkedTransferQueue());
assertInvariants(q);
diff --git a/test/jdk/java/util/concurrent/tck/Collection8Test.java b/test/jdk/java/util/concurrent/tck/Collection8Test.java
--- a/test/jdk/java/util/concurrent/tck/Collection8Test.java
+++ b/test/jdk/java/util/concurrent/tck/Collection8Test.java
@@ -35,6 +35,7 @@
import static java.util.concurrent.TimeUnit.HOURS;
import static java.util.concurrent.TimeUnit.MILLISECONDS;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
@@ -46,6 +47,7 @@
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
+import java.util.Set;
import java.util.Spliterator;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.BlockingQueue;
@@ -86,8 +88,9 @@
Object bomb() {
return new Object() {
- public boolean equals(Object x) { throw new AssertionError(); }
- public int hashCode() { throw new AssertionError(); }
+ @Override public boolean equals(Object x) { throw new AssertionError(); }
+ @Override public int hashCode() { throw new AssertionError(); }
+ @Override public String toString() { throw new AssertionError(); }
};
}
@@ -119,6 +122,23 @@
assertTrue(c.isEmpty());
assertEquals(0, c.size());
assertEquals("[]", c.toString());
+ if (c instanceof List>) {
+ List x = (List) c;
+ assertEquals(1, x.hashCode());
+ assertEquals(x, Collections.emptyList());
+ assertEquals(Collections.emptyList(), x);
+ assertEquals(-1, x.indexOf(impl.makeElement(86)));
+ assertEquals(-1, x.lastIndexOf(impl.makeElement(99)));
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> x.get(0),
+ () -> x.set(0, impl.makeElement(42)));
+ }
+ else if (c instanceof Set>) {
+ assertEquals(0, c.hashCode());
+ assertEquals(c, Collections.emptySet());
+ assertEquals(Collections.emptySet(), c);
+ }
{
Object[] a = c.toArray();
assertEquals(0, a.length);
@@ -279,6 +299,16 @@
() -> d.pop(),
() -> d.descendingIterator().next());
}
+ if (c instanceof List) {
+ List x = (List) c;
+ assertThrows(
+ NoSuchElementException.class,
+ () -> x.iterator().next(),
+ () -> x.listIterator().next(),
+ () -> x.listIterator(0).next(),
+ () -> x.listIterator().previous(),
+ () -> x.listIterator(0).previous());
+ }
}
public void testRemoveIf() {
@@ -904,6 +934,31 @@
}
}
+ public void testCollectionCopies() throws Exception {
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ Collection c = impl.emptyCollection();
+ for (int n = rnd.nextInt(4); n--> 0; )
+ c.add(impl.makeElement(rnd.nextInt()));
+ assertEquals(c, c);
+ if (c instanceof List)
+ assertCollectionsEquals(c, new ArrayList(c));
+ else if (c instanceof Set)
+ assertCollectionsEquals(c, new HashSet(c));
+ else if (c instanceof Deque)
+ assertCollectionsEquivalent(c, new ArrayDeque(c));
+
+ Collection clone = cloneableClone(c);
+ if (clone != null) {
+ assertSame(c.getClass(), clone.getClass());
+ assertCollectionsEquivalent(c, clone);
+ }
+ try {
+ Collection serialClone = serialClonePossiblyFailing(c);
+ assertSame(c.getClass(), serialClone.getClass());
+ assertCollectionsEquivalent(c, serialClone);
+ } catch (java.io.NotSerializableException acceptable) {}
+ }
+
// public void testCollection8DebugFail() {
// fail(impl.klazz().getSimpleName());
// }
diff --git a/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java b/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java
@@ -36,12 +36,13 @@
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
+import java.util.Collections;
import java.util.Iterator;
-import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.concurrent.CopyOnWriteArrayList;
+import java.util.concurrent.ThreadLocalRandom;
import junit.framework.Test;
@@ -61,7 +62,12 @@
}
class SubListImplementation extends Implementation {
public List emptyCollection() {
- return super.emptyCollection().subList(0, 0);
+ List list = super.emptyCollection();
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ if (rnd.nextBoolean())
+ list.add(makeElement(rnd.nextInt()));
+ int i = rnd.nextInt(list.size() + 1);
+ return list.subList(i, i);
}
}
return newTestSuite(
@@ -70,67 +76,67 @@
CollectionTest.testSuite(new SubListImplementation()));
}
- static CopyOnWriteArrayList populatedArray(int n) {
- CopyOnWriteArrayList a = new CopyOnWriteArrayList<>();
- assertTrue(a.isEmpty());
+ static CopyOnWriteArrayList populatedList(int n) {
+ CopyOnWriteArrayList list = new CopyOnWriteArrayList<>();
+ assertTrue(list.isEmpty());
for (int i = 0; i < n; i++)
- a.add(i);
- assertFalse(a.isEmpty());
- assertEquals(n, a.size());
- return a;
+ list.add(i);
+ assertEquals(n <= 0, list.isEmpty());
+ assertEquals(n, list.size());
+ return list;
}
- static CopyOnWriteArrayList populatedArray(Integer[] elements) {
- CopyOnWriteArrayList a = new CopyOnWriteArrayList<>();
- assertTrue(a.isEmpty());
+ static CopyOnWriteArrayList populatedList(Integer[] elements) {
+ CopyOnWriteArrayList list = new CopyOnWriteArrayList<>();
+ assertTrue(list.isEmpty());
for (Integer element : elements)
- a.add(element);
- assertFalse(a.isEmpty());
- assertEquals(elements.length, a.size());
- return a;
+ list.add(element);
+ assertFalse(list.isEmpty());
+ assertEquals(elements.length, list.size());
+ return list;
}
/**
* a new list is empty
*/
public void testConstructor() {
- CopyOnWriteArrayList a = new CopyOnWriteArrayList();
- assertTrue(a.isEmpty());
+ List list = new CopyOnWriteArrayList();
+ assertTrue(list.isEmpty());
}
/**
* new list contains all elements of initializing array
*/
public void testConstructor2() {
- Integer[] ints = new Integer[SIZE];
+ Integer[] elts = new Integer[SIZE];
for (int i = 0; i < SIZE - 1; ++i)
- ints[i] = new Integer(i);
- CopyOnWriteArrayList a = new CopyOnWriteArrayList(ints);
+ elts[i] = i;
+ List list = new CopyOnWriteArrayList(elts);
for (int i = 0; i < SIZE; ++i)
- assertEquals(ints[i], a.get(i));
+ assertEquals(elts[i], list.get(i));
}
/**
* new list contains all elements of initializing collection
*/
public void testConstructor3() {
- Integer[] ints = new Integer[SIZE];
+ Integer[] elts = new Integer[SIZE];
for (int i = 0; i < SIZE - 1; ++i)
- ints[i] = new Integer(i);
- CopyOnWriteArrayList a = new CopyOnWriteArrayList(Arrays.asList(ints));
+ elts[i] = i;
+ List list = new CopyOnWriteArrayList(Arrays.asList(elts));
for (int i = 0; i < SIZE; ++i)
- assertEquals(ints[i], a.get(i));
+ assertEquals(elts[i], list.get(i));
}
/**
* addAll adds each element from the given collection, including duplicates
*/
public void testAddAll() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertTrue(full.addAll(Arrays.asList(three, four, five)));
- assertEquals(6, full.size());
- assertTrue(full.addAll(Arrays.asList(three, four, five)));
- assertEquals(9, full.size());
+ List list = populatedList(3);
+ assertTrue(list.addAll(Arrays.asList(three, four, five)));
+ assertEquals(6, list.size());
+ assertTrue(list.addAll(Arrays.asList(three, four, five)));
+ assertEquals(9, list.size());
}
/**
@@ -138,46 +144,46 @@
* already exist in the List
*/
public void testAddAllAbsent() {
- CopyOnWriteArrayList full = populatedArray(3);
+ CopyOnWriteArrayList list = populatedList(3);
// "one" is duplicate and will not be added
- assertEquals(2, full.addAllAbsent(Arrays.asList(three, four, one)));
- assertEquals(5, full.size());
- assertEquals(0, full.addAllAbsent(Arrays.asList(three, four, one)));
- assertEquals(5, full.size());
+ assertEquals(2, list.addAllAbsent(Arrays.asList(three, four, one)));
+ assertEquals(5, list.size());
+ assertEquals(0, list.addAllAbsent(Arrays.asList(three, four, one)));
+ assertEquals(5, list.size());
}
/**
* addIfAbsent will not add the element if it already exists in the list
*/
public void testAddIfAbsent() {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- full.addIfAbsent(one);
- assertEquals(SIZE, full.size());
+ CopyOnWriteArrayList list = populatedList(SIZE);
+ list.addIfAbsent(one);
+ assertEquals(SIZE, list.size());
}
/**
* addIfAbsent adds the element when it does not exist in the list
*/
public void testAddIfAbsent2() {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- full.addIfAbsent(three);
- assertTrue(full.contains(three));
+ CopyOnWriteArrayList list = populatedList(SIZE);
+ list.addIfAbsent(three);
+ assertTrue(list.contains(three));
}
/**
* clear removes all elements from the list
*/
public void testClear() {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- full.clear();
- assertEquals(0, full.size());
+ List list = populatedList(SIZE);
+ list.clear();
+ assertEquals(0, list.size());
}
/**
* Cloned list is equal
*/
public void testClone() {
- CopyOnWriteArrayList l1 = populatedArray(SIZE);
+ CopyOnWriteArrayList l1 = populatedList(SIZE);
CopyOnWriteArrayList l2 = (CopyOnWriteArrayList)(l1.clone());
assertEquals(l1, l2);
l1.clear();
@@ -188,33 +194,33 @@
* contains is true for added elements
*/
public void testContains() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertTrue(full.contains(one));
- assertFalse(full.contains(five));
+ List list = populatedList(3);
+ assertTrue(list.contains(one));
+ assertFalse(list.contains(five));
}
/**
* adding at an index places it in the indicated index
*/
public void testAddIndex() {
- CopyOnWriteArrayList full = populatedArray(3);
- full.add(0, m1);
- assertEquals(4, full.size());
- assertEquals(m1, full.get(0));
- assertEquals(zero, full.get(1));
+ List list = populatedList(3);
+ list.add(0, m1);
+ assertEquals(4, list.size());
+ assertEquals(m1, list.get(0));
+ assertEquals(zero, list.get(1));
- full.add(2, m2);
- assertEquals(5, full.size());
- assertEquals(m2, full.get(2));
- assertEquals(two, full.get(4));
+ list.add(2, m2);
+ assertEquals(5, list.size());
+ assertEquals(m2, list.get(2));
+ assertEquals(two, list.get(4));
}
/**
* lists with same elements are equal and have same hashCode
*/
public void testEquals() {
- CopyOnWriteArrayList a = populatedArray(3);
- CopyOnWriteArrayList b = populatedArray(3);
+ List a = populatedList(3);
+ List b = populatedList(3);
assertTrue(a.equals(b));
assertTrue(b.equals(a));
assertTrue(a.containsAll(b));
@@ -239,15 +245,15 @@
* containsAll returns true for collections with subset of elements
*/
public void testContainsAll() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertTrue(full.containsAll(Arrays.asList()));
- assertTrue(full.containsAll(Arrays.asList(one)));
- assertTrue(full.containsAll(Arrays.asList(one, two)));
- assertFalse(full.containsAll(Arrays.asList(one, two, six)));
- assertFalse(full.containsAll(Arrays.asList(six)));
+ List list = populatedList(3);
+ assertTrue(list.containsAll(Arrays.asList()));
+ assertTrue(list.containsAll(Arrays.asList(one)));
+ assertTrue(list.containsAll(Arrays.asList(one, two)));
+ assertFalse(list.containsAll(Arrays.asList(one, two, six)));
+ assertFalse(list.containsAll(Arrays.asList(six)));
try {
- full.containsAll(null);
+ list.containsAll(null);
shouldThrow();
} catch (NullPointerException success) {}
}
@@ -256,37 +262,81 @@
* get returns the value at the given index
*/
public void testGet() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertEquals(0, full.get(0));
+ List list = populatedList(3);
+ assertEquals(0, list.get(0));
}
/**
- * indexOf gives the index for the given object
+ * indexOf(Object) returns the index of the first occurrence of the
+ * specified element in this list, or -1 if this list does not
+ * contain the element
*/
public void testIndexOf() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertEquals(1, full.indexOf(one));
- assertEquals(-1, full.indexOf("puppies"));
+ List list = populatedList(3);
+ assertEquals(-1, list.indexOf(-42));
+ int size = list.size();
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.indexOf(i));
+ assertEquals(i, list.subList(0, size).indexOf(i));
+ assertEquals(i, list.subList(0, i + 1).indexOf(i));
+ assertEquals(-1, list.subList(0, i).indexOf(i));
+ assertEquals(0, list.subList(i, size).indexOf(i));
+ assertEquals(-1, list.subList(i + 1, size).indexOf(i));
+ }
+
+ list.add(1);
+ assertEquals(1, list.indexOf(1));
+ assertEquals(1, list.subList(0, size + 1).indexOf(1));
+ assertEquals(0, list.subList(1, size + 1).indexOf(1));
+ assertEquals(size - 2, list.subList(2, size + 1).indexOf(1));
+ assertEquals(0, list.subList(size, size + 1).indexOf(1));
+ assertEquals(-1, list.subList(size + 1, size + 1).indexOf(1));
}
/**
- * indexOf gives the index based on the given index
- * at which to start searching
+ * indexOf(E, int) returns the index of the first occurrence of the
+ * specified element in this list, searching forwards from index,
+ * or returns -1 if the element is not found
*/
public void testIndexOf2() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertEquals(1, full.indexOf(one, 0));
- assertEquals(-1, full.indexOf(one, 2));
+ CopyOnWriteArrayList list = populatedList(3);
+ int size = list.size();
+ assertEquals(-1, list.indexOf(-42, 0));
+
+ // we might expect IOOBE, but spec says otherwise
+ assertEquals(-1, list.indexOf(0, size));
+ assertEquals(-1, list.indexOf(0, Integer.MAX_VALUE));
+
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> list.indexOf(0, -1),
+ () -> list.indexOf(0, Integer.MIN_VALUE));
+
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.indexOf(i, 0));
+ assertEquals(i, list.indexOf(i, i));
+ assertEquals(-1, list.indexOf(i, i + 1));
+ }
+
+ list.add(1);
+ assertEquals(1, list.indexOf(1, 0));
+ assertEquals(1, list.indexOf(1, 1));
+ assertEquals(size, list.indexOf(1, 2));
+ assertEquals(size, list.indexOf(1, size));
}
/**
* isEmpty returns true when empty, else false
*/
public void testIsEmpty() {
- CopyOnWriteArrayList empty = new CopyOnWriteArrayList();
- CopyOnWriteArrayList full = populatedArray(SIZE);
+ List empty = new CopyOnWriteArrayList();
assertTrue(empty.isEmpty());
+ assertTrue(empty.subList(0, 0).isEmpty());
+
+ List full = populatedList(SIZE);
assertFalse(full.isEmpty());
+ assertTrue(full.subList(0, 0).isEmpty());
+ assertTrue(full.subList(SIZE, SIZE).isEmpty());
}
/**
@@ -305,7 +355,7 @@
for (int i = 0; i < SIZE; i++)
elements[i] = i;
shuffle(elements);
- Collection full = populatedArray(elements);
+ Collection full = populatedList(elements);
Iterator it = full.iterator();
for (int j = 0; j < SIZE; j++) {
@@ -327,8 +377,8 @@
* iterator.remove throws UnsupportedOperationException
*/
public void testIteratorRemove() {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- Iterator it = full.iterator();
+ CopyOnWriteArrayList list = populatedList(SIZE);
+ Iterator it = list.iterator();
it.next();
try {
it.remove();
@@ -341,42 +391,78 @@
*/
public void testToString() {
assertEquals("[]", new CopyOnWriteArrayList().toString());
- CopyOnWriteArrayList full = populatedArray(3);
- String s = full.toString();
+ List list = populatedList(3);
+ String s = list.toString();
for (int i = 0; i < 3; ++i)
assertTrue(s.contains(String.valueOf(i)));
- assertEquals(new ArrayList(full).toString(),
- full.toString());
+ assertEquals(new ArrayList(list).toString(),
+ list.toString());
}
/**
- * lastIndexOf returns the index for the given object
+ * lastIndexOf(Object) returns the index of the last occurrence of
+ * the specified element in this list, or -1 if this list does not
+ * contain the element
*/
public void testLastIndexOf1() {
- CopyOnWriteArrayList full = populatedArray(3);
- full.add(one);
- full.add(three);
- assertEquals(3, full.lastIndexOf(one));
- assertEquals(-1, full.lastIndexOf(six));
+ List list = populatedList(3);
+ assertEquals(-1, list.lastIndexOf(-42));
+ int size = list.size();
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.lastIndexOf(i));
+ assertEquals(i, list.subList(0, size).lastIndexOf(i));
+ assertEquals(i, list.subList(0, i + 1).lastIndexOf(i));
+ assertEquals(-1, list.subList(0, i).lastIndexOf(i));
+ assertEquals(0, list.subList(i, size).lastIndexOf(i));
+ assertEquals(-1, list.subList(i + 1, size).lastIndexOf(i));
+ }
+
+ list.add(1);
+ assertEquals(size, list.lastIndexOf(1));
+ assertEquals(size, list.subList(0, size + 1).lastIndexOf(1));
+ assertEquals(1, list.subList(0, size).lastIndexOf(1));
+ assertEquals(0, list.subList(1, 2).lastIndexOf(1));
+ assertEquals(-1, list.subList(0, 1).indexOf(1));
}
/**
- * lastIndexOf returns the index from the given starting point
+ * lastIndexOf(E, int) returns the index of the last occurrence of the
+ * specified element in this list, searching backwards from index, or
+ * returns -1 if the element is not found
*/
public void testLastIndexOf2() {
- CopyOnWriteArrayList full = populatedArray(3);
- full.add(one);
- full.add(three);
- assertEquals(3, full.lastIndexOf(one, 4));
- assertEquals(-1, full.lastIndexOf(three, 3));
+ CopyOnWriteArrayList list = populatedList(3);
+
+ // we might expect IOOBE, but spec says otherwise
+ assertEquals(-1, list.lastIndexOf(0, -1));
+
+ int size = list.size();
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> list.lastIndexOf(0, size),
+ () -> list.lastIndexOf(0, Integer.MAX_VALUE));
+
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.lastIndexOf(i, i));
+ assertEquals(list.indexOf(i), list.lastIndexOf(i, i));
+ if (i > 0)
+ assertEquals(-1, list.lastIndexOf(i, i - 1));
+ }
+ list.add(one);
+ list.add(three);
+ assertEquals(1, list.lastIndexOf(one, 1));
+ assertEquals(1, list.lastIndexOf(one, 2));
+ assertEquals(3, list.lastIndexOf(one, 3));
+ assertEquals(3, list.lastIndexOf(one, 4));
+ assertEquals(-1, list.lastIndexOf(three, 3));
}
/**
* listIterator traverses all elements
*/
public void testListIterator1() {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- ListIterator i = full.listIterator();
+ List list = populatedList(SIZE);
+ ListIterator i = list.listIterator();
int j;
for (j = 0; i.hasNext(); j++)
assertEquals(j, i.next());
@@ -387,8 +473,8 @@
* listIterator only returns those elements after the given index
*/
public void testListIterator2() {
- CopyOnWriteArrayList full = populatedArray(3);
- ListIterator i = full.listIterator(1);
+ List list = populatedList(3);
+ ListIterator i = list.listIterator(1);
int j;
for (j = 0; i.hasNext(); j++)
assertEquals(j + 1, i.next());
@@ -401,10 +487,10 @@
public void testRemove_int() {
int SIZE = 3;
for (int i = 0; i < SIZE; i++) {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- assertEquals(i, full.remove(i));
- assertEquals(SIZE - 1, full.size());
- assertFalse(full.contains(new Integer(i)));
+ List list = populatedList(SIZE);
+ assertEquals(i, list.remove(i));
+ assertEquals(SIZE - 1, list.size());
+ assertFalse(list.contains(new Integer(i)));
}
}
@@ -414,11 +500,11 @@
public void testRemove_Object() {
int SIZE = 3;
for (int i = 0; i < SIZE; i++) {
- CopyOnWriteArrayList full = populatedArray(SIZE);
- assertFalse(full.remove(new Integer(-42)));
- assertTrue(full.remove(new Integer(i)));
- assertEquals(SIZE - 1, full.size());
- assertFalse(full.contains(new Integer(i)));
+ List list = populatedList(SIZE);
+ assertFalse(list.remove(new Integer(-42)));
+ assertTrue(list.remove(new Integer(i)));
+ assertEquals(SIZE - 1, list.size());
+ assertFalse(list.contains(new Integer(i)));
}
CopyOnWriteArrayList x = new CopyOnWriteArrayList(Arrays.asList(4, 5, 6));
assertTrue(x.remove(new Integer(6)));
@@ -434,30 +520,34 @@
* removeAll removes all elements from the given collection
*/
public void testRemoveAll() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertTrue(full.removeAll(Arrays.asList(one, two)));
- assertEquals(1, full.size());
- assertFalse(full.removeAll(Arrays.asList(one, two)));
- assertEquals(1, full.size());
+ List list = populatedList(3);
+ assertTrue(list.removeAll(Arrays.asList(one, two)));
+ assertEquals(1, list.size());
+ assertFalse(list.removeAll(Arrays.asList(one, two)));
+ assertEquals(1, list.size());
}
/**
* set changes the element at the given index
*/
public void testSet() {
- CopyOnWriteArrayList full = populatedArray(3);
- assertEquals(2, full.set(2, four));
- assertEquals(4, full.get(2));
+ List list = populatedList(3);
+ assertEquals(2, list.set(2, four));
+ assertEquals(4, list.get(2));
}
/**
* size returns the number of elements
*/
public void testSize() {
- CopyOnWriteArrayList empty = new CopyOnWriteArrayList();
- CopyOnWriteArrayList full = populatedArray(SIZE);
+ List empty = new CopyOnWriteArrayList();
+ assertEquals(0, empty.size());
+ assertEquals(0, empty.subList(0, 0).size());
+
+ List full = populatedList(SIZE);
assertEquals(SIZE, full.size());
- assertEquals(0, empty.size());
+ assertEquals(0, full.subList(0, 0).size());
+ assertEquals(0, full.subList(SIZE, SIZE).size());
}
/**
@@ -473,7 +563,7 @@
for (int i = 0; i < SIZE; i++)
elements[i] = i;
shuffle(elements);
- Collection full = populatedArray(elements);
+ Collection full = populatedList(elements);
assertTrue(Arrays.equals(elements, full.toArray()));
assertSame(Object[].class, full.toArray().getClass());
@@ -501,7 +591,7 @@
for (int i = 0; i < SIZE; i++)
elements[i] = i;
shuffle(elements);
- Collection full = populatedArray(elements);
+ Collection full = populatedList(elements);
Arrays.fill(a, 42);
assertTrue(Arrays.equals(elements, full.toArray(a)));
@@ -527,7 +617,7 @@
* sublists contains elements at indexes offset from their base
*/
public void testSubList() {
- CopyOnWriteArrayList a = populatedArray(10);
+ List a = populatedList(10);
assertTrue(a.subList(1,1).isEmpty());
for (int j = 0; j < 9; ++j) {
for (int i = j ; i < 10; ++i) {
@@ -544,6 +634,11 @@
assertEquals(a.get(4), m1);
s.clear();
assertEquals(7, a.size());
+
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> s.get(0),
+ () -> s.set(0, 42));
}
// Exception tests
@@ -553,231 +648,72 @@
* can not store the objects inside the list
*/
public void testToArray_ArrayStoreException() {
- CopyOnWriteArrayList c = new CopyOnWriteArrayList();
- c.add("zfasdfsdf");
- c.add("asdadasd");
- try {
- c.toArray(new Long[5]);
- shouldThrow();
- } catch (ArrayStoreException success) {}
- }
-
- /**
- * get throws an IndexOutOfBoundsException on a negative index
- */
- public void testGet1_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.get(-1);
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * get throws an IndexOutOfBoundsException on a too high index
- */
- public void testGet2_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.get(list.size());
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * set throws an IndexOutOfBoundsException on a negative index
- */
- public void testSet1_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.set(-1, "qwerty");
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
+ List list = new CopyOnWriteArrayList();
+ // Integers are not auto-converted to Longs
+ list.add(86);
+ list.add(99);
+ assertThrows(
+ ArrayStoreException.class,
+ () -> list.toArray(new Long[0]),
+ () -> list.toArray(new Long[5]));
}
- /**
- * set throws an IndexOutOfBoundsException on a too high index
- */
- public void testSet2() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.set(list.size(), "qwerty");
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
+ void testIndexOutOfBoundsException(List list) {
+ int size = list.size();
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> list.get(-1),
+ () -> list.get(size),
+ () -> list.set(-1, "qwerty"),
+ () -> list.set(size, "qwerty"),
+ () -> list.add(-1, "qwerty"),
+ () -> list.add(size + 1, "qwerty"),
+ () -> list.remove(-1),
+ () -> list.remove(size),
+ () -> list.addAll(-1, Collections.emptyList()),
+ () -> list.addAll(size + 1, Collections.emptyList()),
+ () -> list.listIterator(-1),
+ () -> list.listIterator(size + 1),
+ () -> list.subList(-1, size),
+ () -> list.subList(0, size + 1));
- /**
- * add throws an IndexOutOfBoundsException on a negative index
- */
- public void testAdd1_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.add(-1, "qwerty");
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * add throws an IndexOutOfBoundsException on a too high index
- */
- public void testAdd2_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.add(list.size() + 1, "qwerty");
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * remove throws an IndexOutOfBoundsException on a negative index
- */
- public void testRemove1_IndexOutOfBounds() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.remove(-1);
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
+ // Conversely, operations that must not throw
+ list.addAll(0, Collections.emptyList());
+ list.addAll(size, Collections.emptyList());
+ list.add(0, "qwerty");
+ list.add(list.size(), "qwerty");
+ list.get(0);
+ list.get(list.size() - 1);
+ list.set(0, "azerty");
+ list.set(list.size() - 1, "azerty");
+ list.listIterator(0);
+ list.listIterator(list.size());
+ list.subList(0, list.size());
+ list.remove(list.size() - 1);
}
/**
- * remove throws an IndexOutOfBoundsException on a too high index
- */
- public void testRemove2_IndexOutOfBounds() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.remove(list.size());
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * addAll throws an IndexOutOfBoundsException on a negative index
+ * IndexOutOfBoundsException is thrown when specified
*/
- public void testAddAll1_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.addAll(-1, new LinkedList());
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * addAll throws an IndexOutOfBoundsException on a too high index
- */
- public void testAddAll2_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.addAll(list.size() + 1, new LinkedList());
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * listIterator throws an IndexOutOfBoundsException on a negative index
- */
- public void testListIterator1_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.listIterator(-1);
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
+ public void testIndexOutOfBoundsException() {
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ List x = populatedList(rnd.nextInt(5));
+ testIndexOutOfBoundsException(x);
- /**
- * listIterator throws an IndexOutOfBoundsException on a too high index
- */
- public void testListIterator2_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.listIterator(list.size() + 1);
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * subList throws an IndexOutOfBoundsException on a negative index
- */
- public void testSubList1_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.subList(-1, list.size());
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * subList throws an IndexOutOfBoundsException on a too high index
- */
- public void testSubList2_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.subList(0, list.size() + 1);
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
- }
-
- /**
- * subList throws IndexOutOfBoundsException when the second index
- * is lower then the first
- */
- public void testSubList3_IndexOutOfBoundsException() {
- CopyOnWriteArrayList c = populatedArray(5);
- List[] lists = { c, c.subList(1, c.size() - 1) };
- for (List list : lists) {
- try {
- list.subList(list.size() - 1, 1);
- shouldThrow();
- } catch (IndexOutOfBoundsException success) {}
- }
+ int start = rnd.nextInt(x.size() + 1);
+ int end = rnd.nextInt(start, x.size() + 1);
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> x.subList(start, start - 1));
+ List subList = x.subList(start, end);
+ testIndexOutOfBoundsException(x);
}
/**
* a deserialized/reserialized list equals original
*/
public void testSerialization() throws Exception {
- List x = populatedArray(SIZE);
+ List x = populatedList(SIZE);
List y = serialClone(x);
assertNotSame(x, y);
diff --git a/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java b/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java
@@ -49,7 +49,16 @@
main(suite(), args);
}
public static Test suite() {
- return new TestSuite(CopyOnWriteArraySetTest.class);
+ class Implementation implements CollectionImplementation {
+ public Class> klazz() { return CopyOnWriteArraySet.class; }
+ public Set emptyCollection() { return new CopyOnWriteArraySet(); }
+ public Object makeElement(int i) { return i; }
+ public boolean isConcurrent() { return true; }
+ public boolean permitsNulls() { return true; }
+ }
+ return newTestSuite(
+ CopyOnWriteArraySetTest.class,
+ CollectionTest.testSuite(new Implementation()));
}
static CopyOnWriteArraySet populatedSet(int n) {
diff --git a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java
--- a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java
+++ b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java
@@ -93,11 +93,14 @@
import java.util.Collection;
import java.util.Collections;
import java.util.Date;
+import java.util.Deque;
import java.util.Enumeration;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PropertyPermission;
+import java.util.Set;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.Callable;
import java.util.concurrent.CountDownLatch;
@@ -475,6 +478,7 @@
public static boolean atLeastJava8() { return JAVA_CLASS_VERSION >= 52.0; }
public static boolean atLeastJava9() { return JAVA_CLASS_VERSION >= 53.0; }
public static boolean atLeastJava10() { return JAVA_CLASS_VERSION >= 54.0; }
+ public static boolean atLeastJava11() { return JAVA_CLASS_VERSION >= 55.0; }
/**
* Collects all JSR166 unit tests as one suite.
@@ -1473,26 +1477,6 @@
}
}
- public abstract class RunnableShouldThrow implements Runnable {
- protected abstract void realRun() throws Throwable;
-
- final Class> exceptionClass;
-
- RunnableShouldThrow(Class exceptionClass) {
- this.exceptionClass = exceptionClass;
- }
-
- public final void run() {
- try {
- realRun();
- threadShouldThrow(exceptionClass.getSimpleName());
- } catch (Throwable t) {
- if (! exceptionClass.isInstance(t))
- threadUnexpectedException(t);
- }
- }
- }
-
public abstract class ThreadShouldThrow extends Thread {
protected abstract void realRun() throws Throwable;
@@ -2098,4 +2082,42 @@
assertEquals(savedCompletedTaskCount, p.getCompletedTaskCount());
assertEquals(savedQueueSize, p.getQueue().size());
}
+
+ void assertCollectionsEquals(Collection> x, Collection> y) {
+ assertEquals(x, y);
+ assertEquals(y, x);
+ assertEquals(x.isEmpty(), y.isEmpty());
+ assertEquals(x.size(), y.size());
+ if (x instanceof List) {
+ assertEquals(x.toString(), y.toString());
}
+ if (x instanceof List || x instanceof Set) {
+ assertEquals(x.hashCode(), y.hashCode());
+ }
+ if (x instanceof List || x instanceof Deque) {
+ assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+ assertTrue(Arrays.equals(x.toArray(new Object[0]),
+ y.toArray(new Object[0])));
+ }
+ }
+
+ /**
+ * A weaker form of assertCollectionsEquals which does not insist
+ * that the two collections satisfy Object#equals(Object), since
+ * they may use identity semantics as Deques do.
+ */
+ void assertCollectionsEquivalent(Collection> x, Collection> y) {
+ if (x instanceof List || x instanceof Set)
+ assertCollectionsEquals(x, y);
+ else {
+ assertEquals(x.isEmpty(), y.isEmpty());
+ assertEquals(x.size(), y.size());
+ assertEquals(new HashSet(x), new HashSet(y));
+ if (x instanceof Deque) {
+ assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+ assertTrue(Arrays.equals(x.toArray(new Object[0]),
+ y.toArray(new Object[0])));
+ }
+ }
+ }
+}
diff --git a/test/jdk/java/util/concurrent/tck/LinkedListTest.java b/test/jdk/java/util/concurrent/tck/LinkedListTest.java
--- a/test/jdk/java/util/concurrent/tck/LinkedListTest.java
+++ b/test/jdk/java/util/concurrent/tck/LinkedListTest.java
@@ -37,7 +37,9 @@
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
+import java.util.List;
import java.util.NoSuchElementException;
+import java.util.concurrent.ThreadLocalRandom;
import junit.framework.Test;
@@ -49,14 +51,19 @@
public static Test suite() {
class Implementation implements CollectionImplementation {
public Class> klazz() { return LinkedList.class; }
- public Collection emptyCollection() { return new LinkedList(); }
+ public List 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);
+ public List emptyCollection() {
+ List list = super.emptyCollection();
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ if (rnd.nextBoolean())
+ list.add(makeElement(rnd.nextInt()));
+ int i = rnd.nextInt(list.size() + 1);
+ return list.subList(i, i);
}
}
return newTestSuite(
diff --git a/test/jdk/java/util/concurrent/tck/VectorTest.java b/test/jdk/java/util/concurrent/tck/VectorTest.java
--- a/test/jdk/java/util/concurrent/tck/VectorTest.java
+++ b/test/jdk/java/util/concurrent/tck/VectorTest.java
@@ -32,8 +32,13 @@
* http://creativecommons.org/publicdomain/zero/1.0/
*/
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
import java.util.Vector;
-import java.util.List;
+import java.util.concurrent.ThreadLocalRandom;
import junit.framework.Test;
@@ -52,7 +57,12 @@
}
class SubListImplementation extends Implementation {
public List emptyCollection() {
- return super.emptyCollection().subList(0, 0);
+ List list = super.emptyCollection();
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ if (rnd.nextBoolean())
+ list.add(makeElement(rnd.nextInt()));
+ int i = rnd.nextInt(list.size() + 1);
+ return list.subList(i, i);
}
}
return newTestSuite(
@@ -61,6 +71,393 @@
CollectionTest.testSuite(new SubListImplementation()));
}
+ static Vector populatedList(int n) {
+ Vector list = new Vector<>();
+ assertTrue(list.isEmpty());
+ for (int i = 0; i < n; i++)
+ list.add(i);
+ assertEquals(n <= 0, list.isEmpty());
+ assertEquals(n, list.size());
+ return list;
+ }
+
+ /**
+ * addAll adds each element from the given collection, including duplicates
+ */
+ public void testAddAll() {
+ List list = populatedList(3);
+ assertTrue(list.addAll(Arrays.asList(three, four, five)));
+ assertEquals(6, list.size());
+ assertTrue(list.addAll(Arrays.asList(three, four, five)));
+ assertEquals(9, list.size());
+ }
+
+ /**
+ * clear removes all elements from the list
+ */
+ public void testClear() {
+ List list = populatedList(SIZE);
+ list.clear();
+ assertEquals(0, list.size());
+ }
+
+ /**
+ * Cloned list is equal
+ */
+ public void testClone() {
+ Vector l1 = populatedList(SIZE);
+ Vector l2 = (Vector)(l1.clone());
+ assertEquals(l1, l2);
+ l1.clear();
+ assertFalse(l1.equals(l2));
+ }
+
+ /**
+ * contains is true for added elements
+ */
+ public void testContains() {
+ List list = populatedList(3);
+ assertTrue(list.contains(one));
+ assertFalse(list.contains(five));
+ }
+
+ /**
+ * adding at an index places it in the indicated index
+ */
+ public void testAddIndex() {
+ List list = populatedList(3);
+ list.add(0, m1);
+ assertEquals(4, list.size());
+ assertEquals(m1, list.get(0));
+ assertEquals(zero, list.get(1));
+
+ list.add(2, m2);
+ assertEquals(5, list.size());
+ assertEquals(m2, list.get(2));
+ assertEquals(two, list.get(4));
+ }
+
+ /**
+ * lists with same elements are equal and have same hashCode
+ */
+ public void testEquals() {
+ List a = populatedList(3);
+ List b = populatedList(3);
+ assertTrue(a.equals(b));
+ assertTrue(b.equals(a));
+ assertTrue(a.containsAll(b));
+ assertTrue(b.containsAll(a));
+ assertEquals(a.hashCode(), b.hashCode());
+ a.add(m1);
+ assertFalse(a.equals(b));
+ assertFalse(b.equals(a));
+ assertTrue(a.containsAll(b));
+ assertFalse(b.containsAll(a));
+ b.add(m1);
+ assertTrue(a.equals(b));
+ assertTrue(b.equals(a));
+ assertTrue(a.containsAll(b));
+ assertTrue(b.containsAll(a));
+ assertEquals(a.hashCode(), b.hashCode());
+
+ assertFalse(a.equals(null));
+ }
+
+ /**
+ * containsAll returns true for collections with subset of elements
+ */
+ public void testContainsAll() {
+ List list = populatedList(3);
+ assertTrue(list.containsAll(Arrays.asList()));
+ assertTrue(list.containsAll(Arrays.asList(one)));
+ assertTrue(list.containsAll(Arrays.asList(one, two)));
+ assertFalse(list.containsAll(Arrays.asList(one, two, six)));
+ assertFalse(list.containsAll(Arrays.asList(six)));
+
+ try {
+ list.containsAll(null);
+ shouldThrow();
+ } catch (NullPointerException success) {}
+ }
+
+ /**
+ * get returns the value at the given index
+ */
+ public void testGet() {
+ List list = populatedList(3);
+ assertEquals(0, list.get(0));
+ }
+
+ /**
+ * indexOf(Object) returns the index of the first occurrence of the
+ * specified element in this list, or -1 if this list does not
+ * contain the element
+ */
+ public void testIndexOf() {
+ List list = populatedList(3);
+ assertEquals(-1, list.indexOf(-42));
+ int size = list.size();
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.indexOf(i));
+ assertEquals(i, list.subList(0, size).indexOf(i));
+ assertEquals(i, list.subList(0, i + 1).indexOf(i));
+ assertEquals(-1, list.subList(0, i).indexOf(i));
+ assertEquals(0, list.subList(i, size).indexOf(i));
+ assertEquals(-1, list.subList(i + 1, size).indexOf(i));
+ }
+
+ list.add(1);
+ assertEquals(1, list.indexOf(1));
+ assertEquals(1, list.subList(0, size + 1).indexOf(1));
+ assertEquals(0, list.subList(1, size + 1).indexOf(1));
+ assertEquals(size - 2, list.subList(2, size + 1).indexOf(1));
+ assertEquals(0, list.subList(size, size + 1).indexOf(1));
+ assertEquals(-1, list.subList(size + 1, size + 1).indexOf(1));
+ }
+
+ /**
+ * indexOf(E, int) returns the index of the first occurrence of the
+ * specified element in this list, searching forwards from index,
+ * or returns -1 if the element is not found
+ */
+ public void testIndexOf2() {
+ Vector list = populatedList(3);
+ int size = list.size();
+ assertEquals(-1, list.indexOf(-42, 0));
+
+ // we might expect IOOBE, but spec says otherwise
+ assertEquals(-1, list.indexOf(0, size));
+ assertEquals(-1, list.indexOf(0, Integer.MAX_VALUE));
+
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> list.indexOf(0, -1),
+ () -> list.indexOf(0, Integer.MIN_VALUE));
+
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.indexOf(i, 0));
+ assertEquals(i, list.indexOf(i, i));
+ assertEquals(-1, list.indexOf(i, i + 1));
+ }
+
+ list.add(1);
+ assertEquals(1, list.indexOf(1, 0));
+ assertEquals(1, list.indexOf(1, 1));
+ assertEquals(size, list.indexOf(1, 2));
+ assertEquals(size, list.indexOf(1, size));
+ }
+
+ /**
+ * isEmpty returns true when empty, else false
+ */
+ public void testIsEmpty() {
+ List empty = new Vector();
+ assertTrue(empty.isEmpty());
+ assertTrue(empty.subList(0, 0).isEmpty());
+
+ List full = populatedList(SIZE);
+ assertFalse(full.isEmpty());
+ assertTrue(full.subList(0, 0).isEmpty());
+ assertTrue(full.subList(SIZE, SIZE).isEmpty());
+ }
+
+ /**
+ * iterator of empty collection has no elements
+ */
+ public void testEmptyIterator() {
+ Collection c = new Vector();
+ assertIteratorExhausted(c.iterator());
+ }
+
+ /**
+ * lastIndexOf(Object) returns the index of the last occurrence of
+ * the specified element in this list, or -1 if this list does not
+ * contain the element
+ */
+ public void testLastIndexOf1() {
+ List list = populatedList(3);
+ assertEquals(-1, list.lastIndexOf(-42));
+ int size = list.size();
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.lastIndexOf(i));
+ assertEquals(i, list.subList(0, size).lastIndexOf(i));
+ assertEquals(i, list.subList(0, i + 1).lastIndexOf(i));
+ assertEquals(-1, list.subList(0, i).lastIndexOf(i));
+ assertEquals(0, list.subList(i, size).lastIndexOf(i));
+ assertEquals(-1, list.subList(i + 1, size).lastIndexOf(i));
+ }
+
+ list.add(1);
+ assertEquals(size, list.lastIndexOf(1));
+ assertEquals(size, list.subList(0, size + 1).lastIndexOf(1));
+ assertEquals(1, list.subList(0, size).lastIndexOf(1));
+ assertEquals(0, list.subList(1, 2).lastIndexOf(1));
+ assertEquals(-1, list.subList(0, 1).indexOf(1));
+ }
+
+ /**
+ * lastIndexOf(E, int) returns the index of the last occurrence of the
+ * specified element in this list, searching backwards from index, or
+ * returns -1 if the element is not found
+ */
+ public void testLastIndexOf2() {
+ Vector list = populatedList(3);
+
+ // we might expect IOOBE, but spec says otherwise
+ assertEquals(-1, list.lastIndexOf(0, -1));
+
+ int size = list.size();
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> list.lastIndexOf(0, size),
+ () -> list.lastIndexOf(0, Integer.MAX_VALUE));
+
+ for (int i = 0; i < size; i++) {
+ assertEquals(i, list.lastIndexOf(i, i));
+ assertEquals(list.indexOf(i), list.lastIndexOf(i, i));
+ if (i > 0)
+ assertEquals(-1, list.lastIndexOf(i, i - 1));
+ }
+ list.add(one);
+ list.add(three);
+ assertEquals(1, list.lastIndexOf(one, 1));
+ assertEquals(1, list.lastIndexOf(one, 2));
+ assertEquals(3, list.lastIndexOf(one, 3));
+ assertEquals(3, list.lastIndexOf(one, 4));
+ assertEquals(-1, list.lastIndexOf(three, 3));
+ }
+
+ /**
+ * size returns the number of elements
+ */
+ public void testSize() {
+ List empty = new Vector();
+ assertEquals(0, empty.size());
+ assertEquals(0, empty.subList(0, 0).size());
+
+ List full = populatedList(SIZE);
+ assertEquals(SIZE, full.size());
+ assertEquals(0, full.subList(0, 0).size());
+ assertEquals(0, full.subList(SIZE, SIZE).size());
+ }
+
+ /**
+ * sublists contains elements at indexes offset from their base
+ */
+ public void testSubList() {
+ List a = populatedList(10);
+ assertTrue(a.subList(1,1).isEmpty());
+ for (int j = 0; j < 9; ++j) {
+ for (int i = j ; i < 10; ++i) {
+ List b = a.subList(j,i);
+ for (int k = j; k < i; ++k) {
+ assertEquals(new Integer(k), b.get(k-j));
+ }
+ }
+ }
+
+ List s = a.subList(2, 5);
+ assertEquals(3, s.size());
+ s.set(2, m1);
+ assertEquals(a.get(4), m1);
+ s.clear();
+ assertEquals(7, a.size());
+
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> s.get(0),
+ () -> s.set(0, 42));
+ }
+
+ /**
+ * toArray throws an ArrayStoreException when the given array
+ * can not store the objects inside the list
+ */
+ public void testToArray_ArrayStoreException() {
+ List list = new Vector();
+ // Integers are not auto-converted to Longs
+ list.add(86);
+ list.add(99);
+ assertThrows(
+ ArrayStoreException.class,
+ () -> list.toArray(new Long[0]),
+ () -> list.toArray(new Long[5]));
+ }
+
+ void testIndexOutOfBoundsException(List list) {
+ int size = list.size();
+ assertThrows(
+ IndexOutOfBoundsException.class,
+ () -> list.get(-1),
+ () -> list.get(size),
+ () -> list.set(-1, "qwerty"),
+ () -> list.set(size, "qwerty"),
+ () -> list.add(-1, "qwerty"),
+ () -> list.add(size + 1, "qwerty"),
+ () -> list.remove(-1),
+ () -> list.remove(size),
+ () -> list.addAll(-1, Collections.emptyList()),
+ () -> list.addAll(size + 1, Collections.emptyList()),
+ () -> list.listIterator(-1),
+ () -> list.listIterator(size + 1),
+ () -> list.subList(-1, size),
+ () -> list.subList(0, size + 1));
+
+ // Conversely, operations that must not throw
+ list.addAll(0, Collections.emptyList());
+ list.addAll(size, Collections.emptyList());
+ list.add(0, "qwerty");
+ list.add(list.size(), "qwerty");
+ list.get(0);
+ list.get(list.size() - 1);
+ list.set(0, "azerty");
+ list.set(list.size() - 1, "azerty");
+ list.listIterator(0);
+ list.listIterator(list.size());
+ list.subList(0, list.size());
+ list.remove(list.size() - 1);
+ }
+
+ /**
+ * IndexOutOfBoundsException is thrown when specified
+ */
+ public void testIndexOutOfBoundsException() {
+ ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ List x = populatedList(rnd.nextInt(5));
+ testIndexOutOfBoundsException(x);
+
+ int start = rnd.nextInt(x.size() + 1);
+ int end = rnd.nextInt(start, x.size() + 1);
+
+ // Vector#subList spec deviates slightly from List#subList spec
+ assertThrows(
+ IllegalArgumentException.class,
+ () -> x.subList(start, start - 1));
+
+ List subList = x.subList(start, end);
+ testIndexOutOfBoundsException(x);
+ }
+
+ /**
+ * a deserialized/reserialized list equals original
+ */
+ public void testSerialization() throws Exception {
+ List x = populatedList(SIZE);
+ List y = serialClone(x);
+
+ assertNotSame(x, y);
+ assertEquals(x.size(), y.size());
+ assertEquals(x.toString(), y.toString());
+ assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+ assertEquals(x, y);
+ assertEquals(y, x);
+ while (!x.isEmpty()) {
+ assertFalse(y.isEmpty());
+ assertEquals(x.remove(0), y.remove(0));
+ }
+ assertTrue(y.isEmpty());
+ }
+
/**
* tests for setSize()
*/