8200258: Improve CopyOnWriteArrayList subList code
Reviewed-by: martin, psandoz, smarks
--- a/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Tue Apr 10 11:29:37 2018 -0700
+++ b/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Tue Apr 10 11:33:29 2018 -0700
@@ -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> 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);
}
+ 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);
}
+ 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<E> operator) {
- Objects.requireNonNull(operator);
synchronized (lock) {
- replaceAll(operator, 0, getArray().length);
+ replaceAllRange(operator, 0, getArray().length);
}
}
- void replaceAll(UnaryOperator<E> operator, int i, int end) {
+ void replaceAllRange(UnaryOperator<E> 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<Object>)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<E> 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<E>(elements, index);
+ return new COWIterator<E>(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() {
@@ -1102,7 +1104,7 @@
}
public int previousIndex() {
- return cursor-1;
+ return cursor - 1;
}
/**
@@ -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<E> 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<E>(this, fromIndex, toIndex);
+ return new COWSubList(es, fromIndex, size);
}
}
/**
* Sublist for CopyOnWriteArrayList.
*/
- private static class COWSubList<E>
- extends AbstractList<E>
- implements RandomAccess
- {
- private final CopyOnWriteArrayList<E> l;
+ private class COWSubList implements List<E>, RandomAccess {
private final int offset;
private int size;
private Object[] expectedArray;
- // only call this holding l's lock
- COWSubList(CopyOnWriteArrayList<E> 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> 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<E> iterator() {
- synchronized (l.lock) {
- checkForComodification();
- return new COWSubListIterator<E>(l, 0, offset, size);
- }
+ return listIterator(0);
+ }
+
+ public ListIterator<E> listIterator() {
+ return listIterator(0);
}
public ListIterator<E> listIterator(int index) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException
- (outOfBounds(index, size));
- return new COWSubListIterator<E>(l, index, offset, size);
+ rangeCheckForAdd(index);
+ return new COWSubListIterator<E>(
+ CopyOnWriteArrayList.this, index, offset, size);
}
}
public List<E> subList(int fromIndex, int toIndex) {
- synchronized (l.lock) {
+ synchronized (lock) {
checkForComodification();
if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
throw new IndexOutOfBoundsException();
- return new COWSubList<E>(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<E> 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<E> spliterator() {
- synchronized (l.lock) {
+ synchronized (lock) {
return Spliterators.spliterator(
getArrayChecked(), offset, offset + size,
Spliterator.IMMUTABLE | Spliterator.ORDERED);
@@ -1398,7 +1526,7 @@
COWSubListIterator(List<E> l, int index, int offset, int size) {
this.offset = offset;
this.size = size;
- it = l.listIterator(index+offset);
+ it = l.listIterator(index + offset);
}
public boolean hasNext() {
@@ -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());
}
}
--- a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java Tue Apr 10 11:33:29 2018 -0700
@@ -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<Object>(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<Job> jobs) throws Throwable {
+ long[] time0(List<Job> 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 <T> List<T> asSubList(List<T> list) {
- return list.subList(0, list.size());
- }
-
private static <T> Iterable<T> backwards(final List<T> list) {
return new Iterable<T>() {
public Iterator<T> iterator() {
@@ -241,11 +247,32 @@
new IteratorMicroBenchmark(args).run();
}
+ HashMap<Class<?>, 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<Integer> makeSubList(List<Integer> list) {
+ final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ int size = list.size();
+ if (size <= 2) return list.subList(0, size);
+ List<Integer> subList = list.subList(rnd.nextInt(0, 2),
+ size - rnd.nextInt(0, 2));
+ List<Integer> 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<Integer> al = new ArrayList<>(size);
// Populate collections with random data
@@ -265,10 +292,14 @@
ArrayList<Job> jobs = Stream.<Collection<Integer>>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),
@@ -294,16 +325,25 @@
Stream<Job> jobs(Collection<Integer> x) {
return concatStreams(
collectionJobs(x),
+
(x instanceof Deque)
? dequeJobs((Deque<Integer>)x)
: Stream.empty(),
+
(x instanceof List)
? listJobs((List<Integer>)x)
: 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<Job> collectionJobs(Collection<Integer> 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 +385,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<Object> 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 +492,7 @@
}
Stream<Job> dequeJobs(Deque<Integer> 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 +512,50 @@
}
Stream<Job> listJobs(List<Integer> 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)") {
+ int sum = 0;
+ ListIterator<Integer> 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();
+ for (int i = 0; i < iterations; i++) {
+ int sum = 0;
+ ListIterator<Integer> 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++) {
- 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)") {
+ 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 size = x.size();
- Integer[] empty = new Integer[0];
+ int[] sum = new int[1];
+ Object sneakyAdder = sneakyAdder(sum);
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);}}});
+ 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<Integer> sneakyAdder =
+ x -> { sum[0] += x; return x; };
+ for (int i = 0; i < iterations; i++) {
+ sum[0] = 0;
+ x.replaceAll(sneakyAdder);
+ check.sum(sum[0]);}}});
}
}
--- a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java Tue Apr 10 11:33:29 2018 -0700
@@ -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<Integer> 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<Object>(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<Job> jobs) throws Throwable {
+ long[] time0(List<Job> 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<Job> filter(Pattern filter, List<Job> 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 <T> List<T> asSubList(List<T> list) {
- return list.subList(0, list.size());
- }
-
private static <T> Iterable<T> backwards(final List<T> list) {
return new Iterable<T>() {
public Iterator<T> iterator() {
@@ -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<Class<?>, String> goodClassName = new HashMap<>();
- final ArrayList<Integer> 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<Integer> makeSubList(List<Integer> 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<Job> jobs = new ArrayList<>();
+ private static <T> List<T> asSubList(List<T> list) {
+ return list.subList(0, list.size());
+ }
+
+ @SafeVarargs @SuppressWarnings("varargs")
+ private <T> Stream<T> concatStreams(Stream<T> ... streams) {
+ return Stream.of(streams).flatMap(s -> s);
+ }
- List.<Collection<Integer>>of(
- new ArrayList<>(),
- new LinkedList<>(),
- new Vector<>(),
- new ArrayDeque<>(),
- new PriorityQueue<>(),
- new ArrayBlockingQueue<>(al.size()),
- new ConcurrentLinkedQueue<>(),
- new ConcurrentLinkedDeque<>(),
- new LinkedBlockingQueue<>(),
- new LinkedBlockingDeque<>(),
- new LinkedTransferQueue<>(),
- new PriorityBlockingQueue<>()).forEach(
- x -> {
- String klazz = x.getClass().getSimpleName();
- jobs.addAll(collectionJobs(klazz, () -> x, al));
- if (x instanceof Queue) {
- Queue<Integer> queue = (Queue<Integer>) x;
- jobs.addAll(queueJobs(klazz, () -> queue, al));
- }
- if (x instanceof Deque) {
- Deque<Integer> deque = (Deque<Integer>) x;
- jobs.addAll(dequeJobs(klazz, () -> deque, al));
- }
- if (x instanceof BlockingQueue) {
- BlockingQueue<Integer> q = (BlockingQueue<Integer>) x;
- jobs.addAll(blockingQueueJobs(klazz, () -> q, al));
- }
- if (x instanceof BlockingDeque) {
- BlockingDeque<Integer> q = (BlockingDeque<Integer>) x;
- jobs.addAll(blockingDequeJobs(klazz, () -> q, al));
- }
- if (x instanceof List) {
- List<Integer> list = (List<Integer>) x;
- jobs.addAll(
- collectionJobs(
- klazz + " subList",
- () -> list.subList(0, x.size()),
- al));
- }
- });
+ 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<Job> jobs = Stream.<Collection<Integer>>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<>(elements.size()),
+ new ConcurrentLinkedQueue<>(),
+ new ConcurrentLinkedDeque<>(),
+ new LinkedBlockingQueue<>(),
+ new LinkedBlockingDeque<>(),
+ new LinkedTransferQueue<>(),
+ 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<Job> jobs(Collection<Integer> x) {
+ return concatStreams(
+ collectionJobs(x),
+
+ (CopyOnWriteArrayList.class.isAssignableFrom(topLevelClass(x)))
+ ? Stream.empty()
+ : iteratorRemoveJobs(x),
+
+ (x instanceof Queue)
+ ? queueJobs((Queue<Integer>)x)
+ : Stream.empty(),
+
+ (x instanceof Deque)
+ ? dequeJobs((Deque<Integer>)x)
+ : Stream.empty(),
+
+ (x instanceof BlockingQueue)
+ ? blockingQueueJobs((BlockingQueue<Integer>)x)
+ : Stream.empty(),
+
+ (x instanceof BlockingDeque)
+ ? blockingDequeJobs((BlockingDeque<Integer>)x)
+ : Stream.empty());
}
Collection<Integer> universeRecorder(int[] sum) {
@@ -323,75 +361,81 @@
}};
}
- List<Job> collectionJobs(
- String description,
- Supplier<Collection<Integer>> supplier,
- ArrayList<Integer> al) {
- return List.of(
- new Job(description + " removeIf") {
+ Stream<Job> collectionJobs(Collection<Integer> x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " removeIf") {
public void work() throws Throwable {
- Collection<Integer> x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.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<Integer> 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<Integer> x = supplier.get();
int[] sum = new int[1];
Collection<Integer> universe = universeRecorder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
x.removeAll(universe);
check.sum(sum[0]);}}},
- new Job(description + " retainAll") {
+ new Job(klazz + " retainAll") {
public void work() throws Throwable {
- Collection<Integer> x = supplier.get();
int[] sum = new int[1];
Collection<Integer> empty = emptyRecorder(sum);
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
x.retainAll(empty);
check.sum(sum[0]);}}},
- new Job(description + " Iterator.remove") {
+ new Job(klazz + " clear") {
public void work() throws Throwable {
- Collection<Integer> x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
+ x.forEach(e -> sum[0] += e);
+ x.clear();
+ check.sum(sum[0]);}}});
+ }
+
+ Stream<Job> iteratorRemoveJobs(Collection<Integer> 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<Integer> 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<Integer> 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<Integer> 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") {
- public void work() throws Throwable {
- Collection<Integer> x = supplier.get();
- int[] sum = new int[1];
- for (int i = 0; i < iterations; i++) {
- sum[0] = 0;
- x.addAll(al);
- x.forEach(e -> sum[0] += e);
- x.clear();
check.sum(sum[0]);}}});
}
- List<Job> queueJobs(
- String description,
- Supplier<Queue<Integer>> supplier,
- ArrayList<Integer> al) {
- return List.of(
- new Job(description + " poll()") {
+ Stream<Job> queueJobs(Queue<Integer> x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " poll()") {
public void work() throws Throwable {
- Queue<Integer> x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
for (Integer e; (e = x.poll()) != null; )
sum[0] += e;
check.sum(sum[0]);}}});
}
- List<Job> dequeJobs(
- String description,
- Supplier<Deque<Integer>> supplier,
- ArrayList<Integer> al) {
- return List.of(
- new Job(description + " descendingIterator().remove") {
+ Stream<Job> dequeJobs(Deque<Integer> x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " descendingIterator().remove") {
public void work() throws Throwable {
- Deque<Integer> x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ x.addAll(elements);
Iterator<Integer> 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<Integer> 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<Integer> 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<Job> blockingQueueJobs(
- String description,
- Supplier<BlockingQueue<Integer>> supplier,
- ArrayList<Integer> al) {
- return List.of(
- new Job(description + " drainTo(sink)") {
+ Stream<Job> blockingQueueJobs(BlockingQueue<Integer> x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " drainTo(sink)") {
public void work() throws Throwable {
- BlockingQueue<Integer> x = supplier.get();
ArrayList<Integer> sink = new ArrayList<>();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
sink.clear();
- x.addAll(al);
+ x.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<Integer> x = supplier.get();
ArrayList<Integer> sink = new ArrayList<>();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
sink.clear();
- x.addAll(al);
- x.drainTo(sink, al.size());
+ x.addAll(elements);
+ x.drainTo(sink, elements.size());
sink.forEach(e -> sum[0] += e);
check.sum(sum[0]);}}});
}
- List<Job> blockingDequeJobs(
- String description,
- Supplier<BlockingDeque<Integer>> supplier,
- ArrayList<Integer> al) {
- return List.of(
- new Job(description + " timed pollFirst()") {
+ Stream<Job> blockingDequeJobs(BlockingDeque<Integer> x) {
+ final String klazz = goodClassName(x.getClass());
+ return Stream.of(
+ new Job(klazz + " timed pollFirst()") {
public void work() throws Throwable {
- BlockingDeque<Integer> x = supplier.get();
int[] sum = new int[1];
for (int i = 0; i < iterations; i++) {
sum[0] = 0;
- x.addAll(al);
+ 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<Integer> 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]);}}});
--- a/test/jdk/java/util/concurrent/tck/Collection8Test.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/Collection8Test.java Tue Apr 10 11:33:29 2018 -0700
@@ -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());
// }
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java Tue Apr 10 11:33:29 2018 -0700
@@ -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<Integer> populatedArray(int n) {
- CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<>();
- assertTrue(a.isEmpty());
+ static CopyOnWriteArrayList<Integer> populatedList(int n) {
+ CopyOnWriteArrayList<Integer> 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<Integer> populatedArray(Integer[] elements) {
- CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<>();
- assertTrue(a.isEmpty());
+ static CopyOnWriteArrayList<Integer> populatedList(Integer[] elements) {
+ CopyOnWriteArrayList<Integer> 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<Integer> full = populatedArray(elements);
+ Collection<Integer> 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<Integer> full = populatedArray(elements);
+ Collection<Integer> 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<Integer> full = populatedArray(elements);
+ Collection<Integer> 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);
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java Tue Apr 10 11:33:29 2018 -0700
@@ -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<Integer> populatedSet(int n) {
--- a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java Tue Apr 10 11:33:29 2018 -0700
@@ -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;
-
- <T extends Throwable> RunnableShouldThrow(Class<T> 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])));
+ }
+ }
+ }
}
--- a/test/jdk/java/util/concurrent/tck/LinkedListTest.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/LinkedListTest.java Tue Apr 10 11:33:29 2018 -0700
@@ -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(
--- a/test/jdk/java/util/concurrent/tck/VectorTest.java Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/VectorTest.java Tue Apr 10 11:33:29 2018 -0700
@@ -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<Integer> populatedList(int n) {
+ Vector<Integer> 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()
*/