8170484: Miscellaneous changes imported from jsr166 CVS 2016-12
Reviewed-by: martin, smarks, psandoz
--- a/jdk/src/java.base/share/classes/java/util/ArrayDeque.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/ArrayDeque.java Wed Dec 21 14:26:52 2016 -0800
@@ -146,16 +146,16 @@
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
- elements = Arrays.copyOf(elements, newCapacity);
+ final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
- if (tail < head || (tail == head && elements[head] != null)) {
+ if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
- System.arraycopy(elements, head,
- elements, head + newSpace,
+ System.arraycopy(es, head,
+ es, head + newSpace,
oldCapacity - head);
- Arrays.fill(elements, head, head + newSpace, null);
- head += newSpace;
+ for (int i = head, to = (head += newSpace); i < to; i++)
+ es[i] = null;
}
}
@@ -873,6 +873,9 @@
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final Object[] es = elements;
@@ -1035,11 +1038,14 @@
/**
* Nulls out slots starting at array index i, upto index end.
+ * Condition i == end means "empty" - nothing to do.
*/
private static void circularClear(Object[] es, int i, int end) {
+ // assert 0 <= i && i < es.length;
+ // assert 0 <= end && end < es.length;
for (int to = (i <= end) ? end : es.length;
; i = 0, to = end) {
- Arrays.fill(es, i, to, null);
+ for (; i < to; i++) es[i] = null;
if (to == end) break;
}
}
--- a/jdk/src/java.base/share/classes/java/util/ArrayList.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/ArrayList.java Wed Dec 21 14:26:52 2016 -0800
@@ -576,8 +576,9 @@
*/
public void clear() {
modCount++;
- Arrays.fill(elementData, 0, size, null);
- size = 0;
+ final Object[] es = elementData;
+ for (int to = size, i = size = 0; i < to; i++)
+ es[i] = null;
}
/**
@@ -665,10 +666,14 @@
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
- final Object[] es = elementData;
- final int oldSize = size;
- System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
- Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null);
+ shiftTailOverGap(elementData, fromIndex, toIndex);
+ }
+
+ /** Erases the gap from lo to hi, by sliding down following elements. */
+ private void shiftTailOverGap(Object[] es, int lo, int hi) {
+ System.arraycopy(es, hi, es, lo, size - hi);
+ for (int to = size, i = (size -= hi - lo); i < to; i++)
+ es[i] = null;
}
/**
@@ -756,25 +761,25 @@
w += end - r;
throw ex;
} finally {
- final int oldSize = size, deleted = end - w;
- modCount += deleted;
- System.arraycopy(es, end, es, w, oldSize - end);
- Arrays.fill(es, size -= deleted, oldSize, null);
+ modCount += end - w;
+ shiftTailOverGap(es, w, end);
}
}
return modified;
}
/**
- * Save the state of the {@code ArrayList} instance to a stream (that
- * is, serialize it).
+ * Saves the state of the {@code ArrayList} instance to a stream
+ * (that is, serializes it).
*
+ * @param s the stream
+ * @throws java.io.IOException if an I/O error occurs
* @serialData The length of the array backing the {@code ArrayList}
* instance is emitted (int), followed by all of its elements
* (each an {@code Object}) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
- throws java.io.IOException{
+ throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
@@ -793,8 +798,12 @@
}
/**
- * Reconstitute the {@code ArrayList} instance from a stream (that is,
- * deserialize it).
+ * Reconstitutes the {@code ArrayList} instance from a stream (that is,
+ * deserializes it).
+ * @param s the stream
+ * @throws ClassNotFoundException if the class of a serialized object
+ * could not be found
+ * @throws java.io.IOException if an I/O error occurs
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
@@ -1285,9 +1294,8 @@
public Spliterator<E> spliterator() {
checkForComodification();
- // ArrayListSpliterator is not used because late-binding logic
- // is different here
- return new Spliterator<>() {
+ // ArrayListSpliterator not used here due to late-binding
+ return new Spliterator<E>() {
private int index = offset; // current index, modified on advance/split
private int fence = -1; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
@@ -1301,12 +1309,11 @@
return hi;
}
- public ArrayListSpliterator<E> trySplit() {
+ public ArrayList<E>.ArrayListSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
- // ArrayListSpliterator could be used here as the source is already bound
+ // ArrayListSpliterator can be used here as the source is already bound
return (lo >= mid) ? null : // divide range in half unless too small
- new ArrayListSpliterator<>(root, lo, index = mid,
- expectedModCount);
+ root.new ArrayListSpliterator(lo, index = mid, expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
@@ -1348,7 +1355,7 @@
}
public long estimateSize() {
- return (long) (getFence() - index);
+ return getFence() - index;
}
public int characteristics() {
@@ -1358,6 +1365,9 @@
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
@@ -1385,11 +1395,11 @@
*/
@Override
public Spliterator<E> spliterator() {
- return new ArrayListSpliterator<>(this, 0, -1, 0);
+ return new ArrayListSpliterator(0, -1, 0);
}
/** Index-based split-by-two, lazily initialized Spliterator */
- static final class ArrayListSpliterator<E> implements Spliterator<E> {
+ final class ArrayListSpliterator implements Spliterator<E> {
/*
* If ArrayLists were immutable, or structurally immutable (no
@@ -1423,15 +1433,12 @@
* these streamlinings.
*/
- private final ArrayList<E> list;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
- /** Create new spliterator covering the given range */
- ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
- int expectedModCount) {
- this.list = list; // OK if null unless traversed
+ /** Creates new spliterator covering the given range. */
+ ArrayListSpliterator(int origin, int fence, int expectedModCount) {
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
@@ -1439,23 +1446,17 @@
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
- ArrayList<E> lst;
if ((hi = fence) < 0) {
- if ((lst = list) == null)
- hi = fence = 0;
- else {
- expectedModCount = lst.modCount;
- hi = fence = lst.size;
- }
+ expectedModCount = modCount;
+ hi = fence = size;
}
return hi;
}
- public ArrayListSpliterator<E> trySplit() {
+ public ArrayListSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
- new ArrayListSpliterator<>(list, lo, index = mid,
- expectedModCount);
+ new ArrayListSpliterator(lo, index = mid, expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
@@ -1464,9 +1465,9 @@
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
- @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
+ @SuppressWarnings("unchecked") E e = (E)elementData[i];
action.accept(e);
- if (list.modCount != expectedModCount)
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
@@ -1475,13 +1476,13 @@
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
- ArrayList<E> lst; Object[] a;
+ Object[] a;
if (action == null)
throw new NullPointerException();
- if ((lst = list) != null && (a = lst.elementData) != null) {
+ if ((a = elementData) != null) {
if ((hi = fence) < 0) {
- mc = lst.modCount;
- hi = lst.size;
+ mc = modCount;
+ hi = size;
}
else
mc = expectedModCount;
@@ -1490,7 +1491,7 @@
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
- if (lst.modCount == mc)
+ if (modCount == mc)
return;
}
}
@@ -1498,7 +1499,7 @@
}
public long estimateSize() {
- return (long) (getFence() - index);
+ return getFence() - index;
}
public int characteristics() {
@@ -1518,6 +1519,9 @@
return (bits[i >> 6] & (1L << i)) == 0;
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@Override
public boolean removeIf(Predicate<? super E> filter) {
return removeIf(filter, 0, size);
@@ -1552,9 +1556,7 @@
for (i = beg; i < end; i++)
if (isClear(deathRow, i - beg))
es[w++] = es[i];
- final int oldSize = size;
- System.arraycopy(es, end, es, w, oldSize - end);
- Arrays.fill(es, size -= (end - w), oldSize, null);
+ shiftTailOverGap(es, w, end);
return true;
} else {
if (modCount != expectedModCount)
--- a/jdk/src/java.base/share/classes/java/util/PriorityQueue.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/PriorityQueue.java Wed Dec 21 14:26:52 2016 -0800
@@ -522,6 +522,8 @@
*/
private int expectedModCount = modCount;
+ Itr() {} // prevent access constructor creation
+
public boolean hasNext() {
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
@@ -631,7 +633,7 @@
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
- * To simplify and speed up coercions and comparisons. the
+ * To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
@@ -727,11 +729,18 @@
/**
* Establishes the heap invariant (described above) in the entire tree,
* assuming nothing about the order of the elements prior to the call.
+ * This classic algorithm due to Floyd (1964) is known to be O(size).
*/
@SuppressWarnings("unchecked")
private void heapify() {
- for (int i = (size >>> 1) - 1; i >= 0; i--)
- siftDown(i, (E) queue[i]);
+ final Object[] es = queue;
+ final int half = (size >>> 1) - 1;
+ if (comparator == null)
+ for (int i = half; i >= 0; i--)
+ siftDownComparable(i, (E) es[i]);
+ else
+ for (int i = half; i >= 0; i--)
+ siftDownUsingComparator(i, (E) es[i]);
}
/**
@@ -812,23 +821,16 @@
* @since 1.8
*/
public final Spliterator<E> spliterator() {
- return new PriorityQueueSpliterator<>(this, 0, -1, 0);
+ return new PriorityQueueSpliterator(0, -1, 0);
}
- static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
- /*
- * This is very similar to ArrayList Spliterator, except for
- * extra null checks.
- */
- private final PriorityQueue<E> pq;
+ final class PriorityQueueSpliterator implements Spliterator<E> {
private int index; // current index, modified on advance/split
private int fence; // -1 until first use
private int expectedModCount; // initialized when fence set
/** Creates new spliterator covering the given range. */
- PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
- int expectedModCount) {
- this.pq = pq;
+ PriorityQueueSpliterator(int origin, int fence, int expectedModCount) {
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
@@ -837,68 +839,54 @@
private int getFence() { // initialize fence to size on first use
int hi;
if ((hi = fence) < 0) {
- expectedModCount = pq.modCount;
- hi = fence = pq.size;
+ expectedModCount = modCount;
+ hi = fence = size;
}
return hi;
}
- public PriorityQueueSpliterator<E> trySplit() {
+ public PriorityQueueSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null :
- new PriorityQueueSpliterator<>(pq, lo, index = mid,
- expectedModCount);
+ new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> action) {
- int i, hi, mc; // hoist accesses and checks from loop
- PriorityQueue<E> q; Object[] a;
if (action == null)
throw new NullPointerException();
- if ((q = pq) != null && (a = q.queue) != null) {
- if ((hi = fence) < 0) {
- mc = q.modCount;
- hi = q.size;
- }
- else
- mc = expectedModCount;
- if ((i = index) >= 0 && (index = hi) <= a.length) {
- for (E e;; ++i) {
- if (i < hi) {
- if ((e = (E) a[i]) == null) // must be CME
- break;
- action.accept(e);
- }
- else if (q.modCount != mc)
- break;
- else
- return;
- }
- }
+ if (fence < 0) { fence = size; expectedModCount = modCount; }
+ final Object[] a = queue;
+ int i, hi; E e;
+ for (i = index, index = hi = fence; i < hi; i++) {
+ if ((e = (E) a[i]) == null)
+ break; // must be CME
+ action.accept(e);
}
- throw new ConcurrentModificationException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
}
+ @SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
- int hi = getFence(), lo = index;
- if (lo >= 0 && lo < hi) {
- index = lo + 1;
- @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
- if (e == null)
+ if (fence < 0) { fence = size; expectedModCount = modCount; }
+ int i;
+ if ((i = index) < fence) {
+ index = i + 1;
+ E e;
+ if ((e = (E) queue[i]) == null
+ || modCount != expectedModCount)
throw new ConcurrentModificationException();
action.accept(e);
- if (pq.modCount != expectedModCount)
- throw new ConcurrentModificationException();
return true;
}
return false;
}
public long estimateSize() {
- return (long) (getFence() - index);
+ return getFence() - index;
}
public int characteristics() {
--- a/jdk/src/java.base/share/classes/java/util/SplittableRandom.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/SplittableRandom.java Wed Dec 21 14:26:52 2016 -0800
@@ -375,7 +375,7 @@
* may, and typically does, vary across program invocations.
*/
public SplittableRandom() { // emulate defaultGen.split()
- long s = defaultGen.getAndAdd(2 * GOLDEN_GAMMA);
+ long s = defaultGen.getAndAdd(GOLDEN_GAMMA << 1);
this.seed = mix64(s);
this.gamma = mixGamma(s + GOLDEN_GAMMA);
}
--- a/jdk/src/java.base/share/classes/java/util/Vector.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/Vector.java Wed Dec 21 14:26:52 2016 -0800
@@ -306,9 +306,9 @@
modCount++;
if (newSize > elementData.length)
grow(newSize);
- for (int i = newSize; i < elementCount; i++)
- elementData[i] = null;
- elementCount = newSize;
+ final Object[] es = elementData;
+ for (int to = elementCount, i = elementCount = newSize; i < to; i++)
+ es[i] = null;
}
/**
@@ -675,9 +675,10 @@
* method (which is part of the {@link List} interface).
*/
public synchronized void removeAllElements() {
- Arrays.fill(elementData, 0, elementCount, null);
+ final Object[] es = elementData;
+ for (int to = elementCount, i = elementCount = 0; i < to; i++)
+ es[i] = null;
modCount++;
- elementCount = 0;
}
/**
@@ -980,6 +981,9 @@
return bulkRemove(e -> !c.contains(e));
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
@@ -1024,7 +1028,8 @@
for (i = beg; i < end; i++)
if (isClear(deathRow, i - beg))
es[w++] = es[i];
- Arrays.fill(es, elementCount = w, end, null);
+ for (i = elementCount = w; i < end; i++)
+ es[i] = null;
return true;
} else {
if (modCount != expectedModCount)
@@ -1152,19 +1157,25 @@
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*/
protected synchronized void removeRange(int fromIndex, int toIndex) {
- final Object[] es = elementData;
- final int oldSize = elementCount;
- System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
+ modCount++;
+ shiftTailOverGap(elementData, fromIndex, toIndex);
+ }
- modCount++;
- Arrays.fill(es, elementCount -= (toIndex - fromIndex), oldSize, null);
+ /** Erases the gap from lo to hi, by sliding down following elements. */
+ private void shiftTailOverGap(Object[] es, int lo, int hi) {
+ System.arraycopy(es, hi, es, lo, elementCount - hi);
+ for (int to = elementCount, i = (elementCount -= hi - lo); i < to; i++)
+ es[i] = null;
}
/**
- * Save the state of the {@code Vector} instance to a stream (that
- * is, serialize it).
+ * Saves the state of the {@code Vector} instance to a stream
+ * (that is, serializes it).
* This method performs synchronization to ensure the consistency
* of the serialized data.
+ *
+ * @param s the stream
+ * @throws java.io.IOException if an I/O error occurs
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
@@ -1337,6 +1348,9 @@
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@Override
public synchronized void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
@@ -1349,6 +1363,9 @@
throw new ConcurrentModificationException();
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@Override
public synchronized void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
@@ -1387,21 +1404,19 @@
*/
@Override
public Spliterator<E> spliterator() {
- return new VectorSpliterator<>(this, null, 0, -1, 0);
+ return new VectorSpliterator(null, 0, -1, 0);
}
/** Similar to ArrayList Spliterator */
- static final class VectorSpliterator<E> implements Spliterator<E> {
- private final Vector<E> list;
+ final class VectorSpliterator implements Spliterator<E> {
private Object[] array;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
- /** Create new spliterator covering the given range */
- VectorSpliterator(Vector<E> list, Object[] array, int origin, int fence,
+ /** Creates new spliterator covering the given range. */
+ VectorSpliterator(Object[] array, int origin, int fence,
int expectedModCount) {
- this.list = list;
this.array = array;
this.index = origin;
this.fence = fence;
@@ -1411,10 +1426,10 @@
private int getFence() { // initialize on first use
int hi;
if ((hi = fence) < 0) {
- synchronized (list) {
- array = list.elementData;
- expectedModCount = list.modCount;
- hi = fence = list.elementCount;
+ synchronized (Vector.this) {
+ array = elementData;
+ expectedModCount = modCount;
+ hi = fence = elementCount;
}
}
return hi;
@@ -1423,8 +1438,7 @@
public Spliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null :
- new VectorSpliterator<>(list, array, lo, index = mid,
- expectedModCount);
+ new VectorSpliterator(array, lo, index = mid, expectedModCount);
}
@SuppressWarnings("unchecked")
@@ -1435,7 +1449,7 @@
if (getFence() > (i = index)) {
index = i + 1;
action.accept((E)array[i]);
- if (list.modCount != expectedModCount)
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
@@ -1444,28 +1458,15 @@
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> action) {
- int i, hi; // hoist accesses and checks from loop
- Vector<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
- if ((lst = list) != null) {
- if ((hi = fence) < 0) {
- synchronized (lst) {
- expectedModCount = lst.modCount;
- a = array = lst.elementData;
- hi = fence = lst.elementCount;
- }
- }
- else
- a = array;
- if (a != null && (i = index) >= 0 && (index = hi) <= a.length) {
- while (i < hi)
- action.accept((E) a[i++]);
- if (lst.modCount == expectedModCount)
- return;
- }
- }
- throw new ConcurrentModificationException();
+ final int hi = getFence();
+ final Object[] a = array;
+ int i;
+ for (i = index, index = hi; i < hi; i++)
+ action.accept((E) a[i]);
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
}
public long estimateSize() {
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java Wed Dec 21 14:26:52 2016 -0800
@@ -675,12 +675,14 @@
/**
* Nulls out slots starting at array index i, upto index end.
- * If i == end, the entire array is cleared!
+ * Condition i == end means "full" - the entire array is cleared.
*/
private static void circularClear(Object[] items, int i, int end) {
+ // assert 0 <= i && i < items.length;
+ // assert 0 <= end && end < items.length;
for (int to = (i < end) ? end : items.length;
; i = 0, to = end) {
- Arrays.fill(items, i, to, null);
+ for (; i < to; i++) items[i] = null;
if (to == end) break;
}
}
@@ -1011,6 +1013,11 @@
* expected element to remove, in lastItem. Yes, we may fail to
* remove lastItem from the queue if it moved due to an interleaved
* interior remove while in detached mode.
+ *
+ * Method forEachRemaining, added in Java 8, is treated similarly
+ * to hasNext returning false, in that we switch to detached mode,
+ * but we regard it as an even stronger request to "close" this
+ * iteration, and don't bother supporting subsequent remove().
*/
private class Itr implements Iterator<E> {
/** Index to look for new nextItem; NONE at end */
@@ -1432,6 +1439,9 @@
Spliterator.CONCURRENT));
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final ReentrantLock lock = this.lock;
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java Wed Dec 21 14:26:52 2016 -0800
@@ -48,6 +48,7 @@
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;
+import java.util.function.Predicate;
/**
* An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
@@ -864,8 +865,8 @@
public E peekFirst() {
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.item;
- if (item != null)
+ final E item;
+ if ((item = p.item) != null)
return item;
}
return null;
@@ -873,8 +874,8 @@
public E peekLast() {
for (Node<E> p = last(); p != null; p = pred(p)) {
- E item = p.item;
- if (item != null)
+ final E item;
+ if ((item = p.item) != null)
return item;
}
return null;
@@ -896,8 +897,9 @@
public E pollFirst() {
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.item;
- if (item != null && ITEM.compareAndSet(p, item, null)) {
+ final E item;
+ if ((item = p.item) != null
+ && ITEM.compareAndSet(p, item, null)) {
unlink(p);
return item;
}
@@ -907,8 +909,9 @@
public E pollLast() {
for (Node<E> p = last(); p != null; p = pred(p)) {
- E item = p.item;
- if (item != null && ITEM.compareAndSet(p, item, null)) {
+ final E item;
+ if ((item = p.item) != null
+ && ITEM.compareAndSet(p, item, null)) {
unlink(p);
return item;
}
@@ -993,9 +996,10 @@
public boolean removeFirstOccurrence(Object o) {
Objects.requireNonNull(o);
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.item;
- if (item != null && o.equals(item) &&
- ITEM.compareAndSet(p, item, null)) {
+ final E item;
+ if ((item = p.item) != null
+ && o.equals(item)
+ && ITEM.compareAndSet(p, item, null)) {
unlink(p);
return true;
}
@@ -1018,9 +1022,10 @@
public boolean removeLastOccurrence(Object o) {
Objects.requireNonNull(o);
for (Node<E> p = last(); p != null; p = pred(p)) {
- E item = p.item;
- if (item != null && o.equals(item) &&
- ITEM.compareAndSet(p, item, null)) {
+ final E item;
+ if ((item = p.item) != null
+ && o.equals(item)
+ && ITEM.compareAndSet(p, item, null)) {
unlink(p);
return true;
}
@@ -1039,8 +1044,8 @@
public boolean contains(Object o) {
if (o != null) {
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.item;
- if (item != null && o.equals(item))
+ final E item;
+ if ((item = p.item) != null && o.equals(item))
return true;
}
}
@@ -1181,8 +1186,8 @@
int charLength = 0;
int size = 0;
for (Node<E> p = first(); p != null;) {
- E item = p.item;
- if (item != null) {
+ final E item;
+ if ((item = p.item) != null) {
if (a == null)
a = new String[4];
else if (size == a.length)
@@ -1207,8 +1212,8 @@
restartFromHead: for (;;) {
int size = 0;
for (Node<E> p = first(); p != null;) {
- E item = p.item;
- if (item != null) {
+ final E item;
+ if ((item = p.item) != null) {
if (x == null)
x = new Object[4];
else if (size == x.length)
@@ -1360,8 +1365,8 @@
nextItem = null;
break;
}
- E item = p.item;
- if (item != null) {
+ final E item;
+ if ((item = p.item) != null) {
nextNode = p;
nextItem = item;
break;
@@ -1391,36 +1396,33 @@
/** Forward iterator */
private class Itr extends AbstractItr {
+ Itr() {} // prevent access constructor creation
Node<E> startNode() { return first(); }
Node<E> nextNode(Node<E> p) { return succ(p); }
}
/** Descending iterator */
private class DescendingItr extends AbstractItr {
+ DescendingItr() {} // prevent access constructor creation
Node<E> startNode() { return last(); }
Node<E> nextNode(Node<E> p) { return pred(p); }
}
/** A customized variant of Spliterators.IteratorSpliterator */
- static final class CLDSpliterator<E> implements Spliterator<E> {
+ final class CLDSpliterator implements Spliterator<E> {
static final int MAX_BATCH = 1 << 25; // max batch array size;
- final ConcurrentLinkedDeque<E> queue;
Node<E> current; // current node; null until initialized
int batch; // batch size for splits
boolean exhausted; // true when no more nodes
- CLDSpliterator(ConcurrentLinkedDeque<E> queue) {
- this.queue = queue;
- }
public Spliterator<E> trySplit() {
Node<E> p;
- final ConcurrentLinkedDeque<E> q = this.queue;
int b = batch;
int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
if (!exhausted &&
- ((p = current) != null || (p = q.first()) != null)) {
+ ((p = current) != null || (p = first()) != null)) {
if (p.item == null && p == (p = p.next))
- current = p = q.first();
+ current = p = first();
if (p != null && p.next != null) {
Object[] a = new Object[n];
int i = 0;
@@ -1428,7 +1430,7 @@
if ((a[i] = p.item) != null)
++i;
if (p == (p = p.next))
- p = q.first();
+ p = first();
} while (p != null && i < n);
if ((current = p) == null)
exhausted = true;
@@ -1447,14 +1449,13 @@
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
- final ConcurrentLinkedDeque<E> q = this.queue;
if (!exhausted &&
- ((p = current) != null || (p = q.first()) != null)) {
+ ((p = current) != null || (p = first()) != null)) {
exhausted = true;
do {
E e = p.item;
if (p == (p = p.next))
- p = q.first();
+ p = first();
if (e != null)
action.accept(e);
} while (p != null);
@@ -1464,14 +1465,13 @@
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
- final ConcurrentLinkedDeque<E> q = this.queue;
if (!exhausted &&
- ((p = current) != null || (p = q.first()) != null)) {
+ ((p = current) != null || (p = first()) != null)) {
E e;
do {
e = p.item;
if (p == (p = p.next))
- p = q.first();
+ p = first();
} while (e == null && p != null);
if ((current = p) == null)
exhausted = true;
@@ -1508,7 +1508,7 @@
* @since 1.8
*/
public Spliterator<E> spliterator() {
- return new CLDSpliterator<E>(this);
+ return new CLDSpliterator();
}
/**
@@ -1527,8 +1527,8 @@
// Write out all elements in the proper order.
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.item;
- if (item != null)
+ final E item;
+ if ((item = p.item) != null)
s.writeObject(item);
}
@@ -1563,6 +1563,57 @@
initHeadTail(h, t);
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean retainAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
+ }
+
+ /** Implementation of bulk remove methods. */
+ private boolean bulkRemove(Predicate<? super E> filter) {
+ boolean removed = false;
+ for (Node<E> p = first(), succ; p != null; p = succ) {
+ succ = succ(p);
+ final E item;
+ if ((item = p.item) != null
+ && filter.test(item)
+ && ITEM.compareAndSet(p, item, null)) {
+ unlink(p);
+ removed = true;
+ }
+ }
+ return removed;
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void forEach(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ E item;
+ for (Node<E> p = first(); p != null; p = succ(p))
+ if ((item = p.item) != null)
+ action.accept(item);
+ }
+
// VarHandle mechanics
private static final VarHandle HEAD;
private static final VarHandle TAIL;
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Wed Dec 21 14:26:52 2016 -0800
@@ -47,6 +47,7 @@
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;
+import java.util.function.Predicate;
/**
* An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.
@@ -112,7 +113,7 @@
/*
* This is a modification of the Michael & Scott algorithm,
* adapted for a garbage-collected environment, with support for
- * interior node deletion (to support remove(Object)). For
+ * interior node deletion (to support e.g. remove(Object)). For
* explanation, read the paper.
*
* Note that like most non-blocking algorithms in this package,
@@ -160,12 +161,13 @@
* it is possible for tail to lag behind head (why not)?
*
* CASing a Node's item reference to null atomically removes the
- * element from the queue. Iterators skip over Nodes with null
- * items. Prior implementations of this class had a race between
- * poll() and remove(Object) where the same element would appear
- * to be successfully removed by two concurrent operations. The
- * method remove(Object) also lazily unlinks deleted Nodes, but
- * this is merely an optimization.
+ * element from the queue, leaving a "dead" node that should later
+ * be unlinked (but unlinking is merely an optimization).
+ * Interior element removal methods (other than Iterator.remove())
+ * keep track of the predecessor node during traversal so that the
+ * node can be CAS-unlinked. Some traversal methods try to unlink
+ * any deleted nodes encountered during traversal. See comments
+ * in bulkRemove.
*
* When constructing a Node (before enqueuing it) we avoid paying
* for a volatile write to item. This allows the cost of enqueue
@@ -290,6 +292,21 @@
}
/**
+ * Tries to CAS pred.next (or head, if pred is null) from c to p.
+ */
+ private boolean tryCasSuccessor(Node<E> pred, Node<E> c, Node<E> p) {
+ // assert c.item == null;
+ // assert c != p;
+ if (pred != null)
+ return NEXT.compareAndSet(pred, c, p);
+ if (HEAD.compareAndSet(this, c, p)) {
+ NEXT.setRelease(c, c);
+ return true;
+ }
+ return false;
+ }
+
+ /**
* Inserts the specified element at the tail of this queue.
* As the queue is unbounded, this method will never return {@code false}.
*
@@ -326,12 +343,11 @@
}
public E poll() {
- restartFromHead:
- for (;;) {
- for (Node<E> h = head, p = h, q;;) {
- E item = p.item;
-
- if (item != null && ITEM.compareAndSet(p, item, null)) {
+ restartFromHead: for (;;) {
+ for (Node<E> h = head, p = h, q;; p = q) {
+ final E item;
+ if ((item = p.item) != null
+ && ITEM.compareAndSet(p, item, null)) {
// Successful CAS is the linearization point
// for item to be removed from this queue.
if (p != h) // hop two nodes at a time
@@ -344,25 +360,21 @@
}
else if (p == q)
continue restartFromHead;
- else
- p = q;
}
}
}
public E peek() {
- restartFromHead:
- for (;;) {
- for (Node<E> h = head, p = h, q;;) {
- E item = p.item;
- if (item != null || (q = p.next) == null) {
+ restartFromHead: for (;;) {
+ for (Node<E> h = head, p = h, q;; p = q) {
+ final E item;
+ if ((item = p.item) != null
+ || (q = p.next) == null) {
updateHead(h, p);
return item;
}
else if (p == q)
continue restartFromHead;
- else
- p = q;
}
}
}
@@ -376,9 +388,8 @@
* of losing a race to a concurrent poll().
*/
Node<E> first() {
- restartFromHead:
- for (;;) {
- for (Node<E> h = head, p = h, q;;) {
+ restartFromHead: for (;;) {
+ for (Node<E> h = head, p = h, q;; p = q) {
boolean hasItem = (p.item != null);
if (hasItem || (q = p.next) == null) {
updateHead(h, p);
@@ -386,8 +397,6 @@
}
else if (p == q)
continue restartFromHead;
- else
- p = q;
}
}
}
@@ -440,14 +449,24 @@
* @return {@code true} if this queue contains the specified element
*/
public boolean contains(Object o) {
- if (o != null) {
- for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.item;
- if (item != null && o.equals(item))
+ if (o == null) return false;
+ restartFromHead: for (;;) {
+ for (Node<E> p = head, c = p, pred = null, q; p != null; p = q) {
+ final E item;
+ if ((item = p.item) != null && o.equals(item))
return true;
+ if (c != p && tryCasSuccessor(pred, c, p))
+ c = p;
+ q = p.next;
+ if (item != null || c != p) {
+ pred = p;
+ c = q;
+ }
+ else if (p == q)
+ continue restartFromHead;
}
+ return false;
}
- return false;
}
/**
@@ -462,27 +481,28 @@
* @return {@code true} if this queue changed as a result of the call
*/
public boolean remove(Object o) {
- if (o != null) {
- Node<E> next, pred = null;
- for (Node<E> p = first(); p != null; pred = p, p = next) {
- boolean removed = false;
- E item = p.item;
- if (item != null) {
- if (!o.equals(item)) {
- next = succ(p);
- continue;
- }
- removed = ITEM.compareAndSet(p, item, null);
- }
-
- next = succ(p);
- if (pred != null && next != null) // unlink
- NEXT.weakCompareAndSet(pred, p, next);
+ if (o == null) return false;
+ restartFromHead: for (;;) {
+ for (Node<E> p = head, c = p, pred = null, q; p != null; p = q) {
+ final E item;
+ final boolean removed =
+ (item = p.item) != null
+ && o.equals(item)
+ && ITEM.compareAndSet(p, item, null);
+ if (c != p && tryCasSuccessor(pred, c, p))
+ c = p;
if (removed)
return true;
+ q = p.next;
+ if (item != null || c != p) {
+ pred = p;
+ c = q;
+ }
+ else if (p == q)
+ continue restartFromHead;
}
+ return false;
}
- return false;
}
/**
@@ -553,8 +573,8 @@
int charLength = 0;
int size = 0;
for (Node<E> p = first(); p != null;) {
- E item = p.item;
- if (item != null) {
+ final E item;
+ if ((item = p.item) != null) {
if (a == null)
a = new String[4];
else if (size == a.length)
@@ -579,8 +599,8 @@
restartFromHead: for (;;) {
int size = 0;
for (Node<E> p = first(); p != null;) {
- E item = p.item;
- if (item != null) {
+ final E item;
+ if ((item = p.item) != null) {
if (x == null)
x = new Object[4];
else if (size == x.length)
@@ -697,7 +717,7 @@
restartFromHead: for (;;) {
Node<E> h, p, q;
for (p = h = head;; p = q) {
- E item;
+ final E item;
if ((item = p.item) != null) {
nextNode = p;
nextItem = item;
@@ -762,8 +782,8 @@
// Write out all elements in the proper order.
for (Node<E> p = first(); p != null; p = succ(p)) {
- Object item = p.item;
- if (item != null)
+ final E item;
+ if ((item = p.item) != null)
s.writeObject(item);
}
@@ -801,23 +821,18 @@
}
/** A customized variant of Spliterators.IteratorSpliterator */
- static final class CLQSpliterator<E> implements Spliterator<E> {
+ final class CLQSpliterator implements Spliterator<E> {
static final int MAX_BATCH = 1 << 25; // max batch array size;
- final ConcurrentLinkedQueue<E> queue;
Node<E> current; // current node; null until initialized
int batch; // batch size for splits
boolean exhausted; // true when no more nodes
- CLQSpliterator(ConcurrentLinkedQueue<E> queue) {
- this.queue = queue;
- }
public Spliterator<E> trySplit() {
Node<E> p;
- final ConcurrentLinkedQueue<E> q = this.queue;
int b = batch;
int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
if (!exhausted &&
- ((p = current) != null || (p = q.first()) != null) &&
+ ((p = current) != null || (p = first()) != null) &&
p.next != null) {
Object[] a = new Object[n];
int i = 0;
@@ -825,7 +840,7 @@
if ((a[i] = p.item) != null)
++i;
if (p == (p = p.next))
- p = q.first();
+ p = first();
} while (p != null && i < n);
if ((current = p) == null)
exhausted = true;
@@ -843,14 +858,13 @@
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
- final ConcurrentLinkedQueue<E> q = this.queue;
if (!exhausted &&
- ((p = current) != null || (p = q.first()) != null)) {
+ ((p = current) != null || (p = first()) != null)) {
exhausted = true;
do {
E e = p.item;
if (p == (p = p.next))
- p = q.first();
+ p = first();
if (e != null)
action.accept(e);
} while (p != null);
@@ -860,14 +874,13 @@
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
- final ConcurrentLinkedQueue<E> q = this.queue;
if (!exhausted &&
- ((p = current) != null || (p = q.first()) != null)) {
+ ((p = current) != null || (p = first()) != null)) {
E e;
do {
e = p.item;
if (p == (p = p.next))
- p = q.first();
+ p = first();
} while (e == null && p != null);
if ((current = p) == null)
exhausted = true;
@@ -905,7 +918,100 @@
*/
@Override
public Spliterator<E> spliterator() {
- return new CLQSpliterator<E>(this);
+ return new CLQSpliterator();
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean retainAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
+ }
+
+ public void clear() {
+ bulkRemove(e -> true);
+ }
+
+ /**
+ * Tolerate this many consecutive dead nodes before CAS-collapsing.
+ * Amortized cost of clear() is (1 + 1/MAX_HOPS) CASes per element.
+ */
+ private static final int MAX_HOPS = 8;
+
+ /** Implementation of bulk remove methods. */
+ private boolean bulkRemove(Predicate<? super E> filter) {
+ boolean removed = false;
+ restartFromHead: for (;;) {
+ int hops = MAX_HOPS;
+ // c will be CASed to collapse intervening dead nodes between
+ // pred (or head if null) and p.
+ for (Node<E> p = head, c = p, pred = null, q; p != null; p = q) {
+ final E item; boolean pAlive;
+ if (pAlive = ((item = p.item) != null)) {
+ if (filter.test(item)) {
+ if (ITEM.compareAndSet(p, item, null))
+ removed = true;
+ pAlive = false;
+ }
+ }
+ if ((q = p.next) == null || pAlive || --hops == 0) {
+ // p might already be self-linked here, but if so:
+ // - CASing head will surely fail
+ // - CASing pred's next will be useless but harmless.
+ if (c != p && tryCasSuccessor(pred, c, p))
+ c = p;
+ // if c != p, CAS failed, so abandon old pred
+ if (pAlive || c != p) {
+ hops = MAX_HOPS;
+ pred = p;
+ c = q;
+ }
+ } else if (p == q)
+ continue restartFromHead;
+ }
+ return removed;
+ }
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void forEach(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ restartFromHead: for (;;) {
+ for (Node<E> p = head, c = p, pred = null, q; p != null; p = q) {
+ final E item;
+ if ((item = p.item) != null)
+ action.accept(item);
+ if (c != p && tryCasSuccessor(pred, c, p))
+ c = p;
+ q = p.next;
+ if (item != null || c != p) {
+ pred = p;
+ c = q;
+ }
+ else if (p == q)
+ continue restartFromHead;
+ }
+ return;
+ }
}
// VarHandle mechanics
--- a/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java Wed Dec 21 14:26:52 2016 -0800
@@ -793,6 +793,9 @@
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public void forEach(Consumer<? super E> action) {
if (action == null) throw new NullPointerException();
for (Object x : getArray()) {
@@ -801,6 +804,9 @@
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public boolean removeIf(Predicate<? super E> filter) {
if (filter == null) throw new NullPointerException();
return bulkRemove(filter);
--- a/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArraySet.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArraySet.java Wed Dec 21 14:26:52 2016 -0800
@@ -411,10 +411,16 @@
&& compareSets(al.getArray(), (Set<?>) o) == 0);
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public boolean removeIf(Predicate<? super E> filter) {
return al.removeIf(filter);
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public void forEach(Consumer<? super E> action) {
al.forEach(action);
}
--- a/jdk/src/java.base/share/classes/java/util/concurrent/CyclicBarrier.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/CyclicBarrier.java Wed Dec 21 14:26:52 2016 -0800
@@ -149,7 +149,8 @@
* but no subsequent reset.
*/
private static class Generation {
- boolean broken; // initially false
+ Generation() {} // prevent access constructor creation
+ boolean broken; // initially false
}
/** The lock for guarding barrier entry */
--- a/jdk/src/java.base/share/classes/java/util/concurrent/DelayQueue.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/DelayQueue.java Wed Dec 21 14:26:52 2016 -0800
@@ -547,8 +547,7 @@
public E next() {
if (cursor >= array.length)
throw new NoSuchElementException();
- lastRet = cursor;
- return (E)array[cursor++];
+ return (E)array[lastRet = cursor++];
}
public void remove() {
--- a/jdk/src/java.base/share/classes/java/util/concurrent/Phaser.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/Phaser.java Wed Dec 21 14:26:52 2016 -0800
@@ -179,7 +179,7 @@
* void startTasks(List<Runnable> tasks, int iterations) {
* Phaser phaser = new Phaser() {
* protected boolean onAdvance(int phase, int registeredParties) {
- * return phase >= iterations || registeredParties == 0;
+ * return phase >= iterations - 1 || registeredParties == 0;
* }
* };
* phaser.register();
--- a/jdk/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java Wed Dec 21 14:26:52 2016 -0800
@@ -345,11 +345,9 @@
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
- * To simplify and speed up coercions and comparisons. the
+ * To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
- * These methods are static, with heap state as arguments, to
- * simplify use in light of possible comparator exceptions.
*
* @param k the position to fill
* @param x the item to insert
@@ -435,6 +433,7 @@
/**
* Establishes the heap invariant (described above) in the entire tree,
* assuming nothing about the order of the elements prior to the call.
+ * This classic algorithm due to Floyd (1964) is known to be O(size).
*/
private void heapify() {
Object[] array = queue;
@@ -878,8 +877,7 @@
public E next() {
if (cursor >= array.length)
throw new NoSuchElementException();
- lastRet = cursor;
- return (E)array[cursor++];
+ return (E)array[lastRet = cursor++];
}
public void remove() {
@@ -936,15 +934,12 @@
/**
* Immutable snapshot spliterator that binds to elements "late".
*/
- static final class PBQSpliterator<E> implements Spliterator<E> {
- final PriorityBlockingQueue<E> queue;
+ final class PBQSpliterator implements Spliterator<E> {
Object[] array;
int index;
int fence;
- PBQSpliterator(PriorityBlockingQueue<E> queue, Object[] array,
- int index, int fence) {
- this.queue = queue;
+ PBQSpliterator(Object[] array, int index, int fence) {
this.array = array;
this.index = index;
this.fence = fence;
@@ -953,14 +948,14 @@
final int getFence() {
int hi;
if ((hi = fence) < 0)
- hi = fence = (array = queue.toArray()).length;
+ hi = fence = (array = toArray()).length;
return hi;
}
- public PBQSpliterator<E> trySplit() {
+ public PBQSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null :
- new PBQSpliterator<E>(queue, array, lo, index = mid);
+ new PBQSpliterator(array, lo, index = mid);
}
@SuppressWarnings("unchecked")
@@ -969,7 +964,7 @@
if (action == null)
throw new NullPointerException();
if ((a = array) == null)
- fence = (a = queue.toArray()).length;
+ fence = (a = toArray()).length;
if ((hi = fence) <= a.length &&
(i = index) >= 0 && i < (index = hi)) {
do { action.accept((E)a[i]); } while (++i < hi);
@@ -987,7 +982,7 @@
return false;
}
- public long estimateSize() { return (long)(getFence() - index); }
+ public long estimateSize() { return getFence() - index; }
public int characteristics() {
return Spliterator.NONNULL | Spliterator.SIZED | Spliterator.SUBSIZED;
@@ -1012,7 +1007,7 @@
* @since 1.8
*/
public Spliterator<E> spliterator() {
- return new PBQSpliterator<E>(this, null, 0, -1);
+ return new PBQSpliterator(null, 0, -1);
}
// VarHandle mechanics
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ScheduledThreadPoolExecutor.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ScheduledThreadPoolExecutor.java Wed Dec 21 14:26:52 2016 -0800
@@ -1306,8 +1306,7 @@
public Runnable next() {
if (cursor >= array.length)
throw new NoSuchElementException();
- lastRet = cursor;
- return array[cursor++];
+ return array[lastRet = cursor++];
}
public void remove() {
--- a/jdk/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java Wed Dec 21 14:26:52 2016 -0800
@@ -195,6 +195,7 @@
/** Fallback if ForkJoinPool.commonPool() cannot support parallelism */
private static final class ThreadPerTaskExecutor implements Executor {
+ ThreadPerTaskExecutor() {} // prevent access constructor creation
public void execute(Runnable r) { new Thread(r).start(); }
}
@@ -1454,7 +1455,17 @@
*/
private boolean checkControl(Flow.Subscriber<? super T> s, int c) {
boolean stat = true;
- if ((c & ERROR) != 0) {
+ if ((c & SUBSCRIBE) != 0) {
+ if (CTL.compareAndSet(this, c, c & ~SUBSCRIBE)) {
+ try {
+ if (s != null)
+ s.onSubscribe(this);
+ } catch (Throwable ex) {
+ onError(ex);
+ }
+ }
+ }
+ else if ((c & ERROR) != 0) {
Throwable ex = pendingError;
ctl = DISABLED; // no need for CAS
if (ex != null) { // null if errorless cancel
@@ -1465,16 +1476,6 @@
}
}
}
- else if ((c & SUBSCRIBE) != 0) {
- if (CTL.compareAndSet(this, c, c & ~SUBSCRIBE)) {
- try {
- if (s != null)
- s.onSubscribe(this);
- } catch (Throwable ex) {
- onError(ex);
- }
- }
- }
else {
detach();
stat = false;
--- a/jdk/src/java.base/share/classes/java/util/concurrent/locks/ReentrantReadWriteLock.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/locks/ReentrantReadWriteLock.java Wed Dec 21 14:26:52 2016 -0800
@@ -138,7 +138,7 @@
* <pre> {@code
* class CachedData {
* Object data;
- * volatile boolean cacheValid;
+ * boolean cacheValid;
* final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
*
* void processCachedData() {
--- a/jdk/test/java/util/concurrent/tck/JSR166TestCase.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/JSR166TestCase.java Wed Dec 21 14:26:52 2016 -0800
@@ -35,13 +35,30 @@
/*
* @test
- * @summary JSR-166 tck tests
+ * @summary JSR-166 tck tests (conformance testing mode)
+ * @build *
+ * @modules java.management
+ * @run junit/othervm/timeout=1000 JSR166TestCase
+ */
+
+/*
+ * @test
+ * @summary JSR-166 tck tests (whitebox tests allowed)
+ * @build *
* @modules java.base/java.util.concurrent:open
* java.management
- * @build *
- * @run junit/othervm/timeout=1000 -Djsr166.testImplementationDetails=true JSR166TestCase
- * @run junit/othervm/timeout=1000 -Djava.util.concurrent.ForkJoinPool.common.parallelism=0 -Djsr166.testImplementationDetails=true JSR166TestCase
- * @run junit/othervm/timeout=1000 -Djava.util.concurrent.ForkJoinPool.common.parallelism=1 -Djava.util.secureRandomSeed=true JSR166TestCase
+ * @run junit/othervm/timeout=1000
+ * -Djsr166.testImplementationDetails=true
+ * JSR166TestCase
+ * @run junit/othervm/timeout=1000
+ * -Djsr166.testImplementationDetails=true
+ * -Djava.util.concurrent.ForkJoinPool.common.parallelism=0
+ * JSR166TestCase
+ * @run junit/othervm/timeout=1000
+ * -Djsr166.testImplementationDetails=true
+ * -Djava.util.concurrent.ForkJoinPool.common.parallelism=1
+ * -Djava.util.secureRandomSeed=true
+ * JSR166TestCase
*/
import static java.util.concurrent.TimeUnit.MILLISECONDS;
@@ -543,6 +560,8 @@
"DoubleAdderTest",
"ForkJoinPool8Test",
"ForkJoinTask8Test",
+ "LinkedBlockingDeque8Test",
+ "LinkedBlockingQueue8Test",
"LongAccumulatorTest",
"LongAdderTest",
"SplittableRandomTest",
--- a/jdk/test/java/util/concurrent/tck/ScheduledExecutorSubclassTest.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/ScheduledExecutorSubclassTest.java Wed Dec 21 14:26:52 2016 -0800
@@ -71,9 +71,9 @@
}
static class CustomTask<V> implements RunnableScheduledFuture<V> {
- RunnableScheduledFuture<V> task;
+ private final RunnableScheduledFuture<V> task;
volatile boolean ran;
- CustomTask(RunnableScheduledFuture<V> t) { task = t; }
+ CustomTask(RunnableScheduledFuture<V> task) { this.task = task; }
public boolean isPeriodic() { return task.isPeriodic(); }
public void run() {
ran = true;
--- a/jdk/test/java/util/concurrent/tck/SubmissionPublisherTest.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/SubmissionPublisherTest.java Wed Dec 21 14:26:52 2016 -0800
@@ -402,6 +402,7 @@
/**
* Closing a publisher exceptionally causes onError to subscribers
+ * after they are subscribed
*/
public void testCloseExceptionallyError() {
SubmissionPublisher<Integer> p = basicPublisher();
@@ -412,9 +413,11 @@
p.submit(1);
p.closeExceptionally(new SPException());
assertTrue(p.isClosed());
+ s1.awaitSubscribe();
s1.awaitError();
assertTrue(s1.nexts <= 1);
assertEquals(1, s1.errors);
+ s2.awaitSubscribe();
s2.awaitError();
assertTrue(s2.nexts <= 1);
assertEquals(1, s2.errors);
--- a/jdk/test/java/util/concurrent/tck/ThreadLocalRandomTest.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/ThreadLocalRandomTest.java Wed Dec 21 14:26:52 2016 -0800
@@ -85,32 +85,41 @@
*/
public void testNext() throws ReflectiveOperationException {
ThreadLocalRandom rnd = ThreadLocalRandom.current();
+ final java.lang.reflect.Method m;
try {
- java.lang.reflect.Method m
- = ThreadLocalRandom.class.getDeclaredMethod(
+ m = ThreadLocalRandom.class.getDeclaredMethod(
"next", new Class[] { int.class });
m.setAccessible(true);
-
- int i;
- {
- int val = new java.util.Random().nextInt(4);
- for (i = 0; i < NCALLS; i++) {
- int q = (int) m.invoke(rnd, new Object[] { 2 });
- if (val == q) break;
- }
- assertTrue(i < NCALLS);
- }
+ } catch (SecurityException acceptable) {
+ // Security manager may deny access
+ return;
+ } catch (Exception ex) {
+ // jdk9 module system may deny access
+ if (ex.getClass().getSimpleName()
+ .equals("InaccessibleObjectException"))
+ return;
+ throw ex;
+ }
- {
- int r = (int) m.invoke(rnd, new Object[] { 3 });
- for (i = 0; i < NCALLS; i++) {
- int q = (int) m.invoke(rnd, new Object[] { 3 });
- assertTrue(q < (1<<3));
- if (r != q) break;
- }
- assertTrue(i < NCALLS);
+ int i;
+ {
+ int val = new java.util.Random().nextInt(4);
+ for (i = 0; i < NCALLS; i++) {
+ int q = (int) m.invoke(rnd, new Object[] { 2 });
+ if (val == q) break;
}
- } catch (SecurityException acceptable) {}
+ assertTrue(i < NCALLS);
+ }
+
+ {
+ int r = (int) m.invoke(rnd, new Object[] { 3 });
+ for (i = 0; i < NCALLS; i++) {
+ int q = (int) m.invoke(rnd, new Object[] { 3 });
+ assertTrue(q < (1<<3));
+ if (r != q) break;
+ }
+ assertTrue(i < NCALLS);
+ }
}
/**
--- a/jdk/test/java/util/concurrent/tck/VectorTest.java Wed Dec 21 14:22:53 2016 -0800
+++ b/jdk/test/java/util/concurrent/tck/VectorTest.java Wed Dec 21 14:26:52 2016 -0800
@@ -58,9 +58,22 @@
}
}
return newTestSuite(
- // VectorTest.class,
+ VectorTest.class,
CollectionTest.testSuite(new Implementation()),
CollectionTest.testSuite(new SubListImplementation()));
}
+ /**
+ * tests for setSize()
+ */
+ public void testSetSize() {
+ Vector v = new Vector();
+ for (int n : new int[] { 100, 5, 50 }) {
+ v.setSize(n);
+ assertEquals(n, v.size());
+ assertNull(v.get(0));
+ assertNull(v.get(n - 1));
+ }
+ }
+
}