diff --git a/src/java.base/share/classes/java/util/ArrayDeque.java b/src/java.base/share/classes/java/util/ArrayDeque.java --- a/src/java.base/share/classes/java/util/ArrayDeque.java +++ b/src/java.base/share/classes/java/util/ArrayDeque.java @@ -208,7 +208,7 @@ */ public ArrayDeque(Collection c) { this(c.size()); - addAll(c); + copyElements(c); } /** @@ -322,8 +322,12 @@ final int s, needed; if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0) grow(needed); + copyElements(c); + return size() > s; + } + + private void copyElements(Collection c) { c.forEach(this::addLast); - return size() > s; } /** diff --git a/src/java.base/share/classes/java/util/Deque.java b/src/java.base/share/classes/java/util/Deque.java --- a/src/java.base/share/classes/java/util/Deque.java +++ b/src/java.base/share/classes/java/util/Deque.java @@ -141,8 +141,8 @@ *

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