--- jsr166/src/main/java/util/ArrayDeque.java 2016/11/08 18:23:10 1.112
+++ jsr166/src/main/java/util/ArrayDeque.java 2018/11/11 17:37:30 1.137
@@ -8,7 +8,7 @@ package java.util;
import java.io.Serializable;
import java.util.function.Consumer;
import java.util.function.Predicate;
-import java.util.function.UnaryOperator;
+// OPENJDK import jdk.internal.access.SharedSecrets;
/**
* Resizable-array implementation of the {@link Deque} interface. Array
@@ -50,7 +50,7 @@ import java.util.function.UnaryOperator;
* Iterator} interfaces.
*
*
This class is a member of the
- *
+ *
* Java Collections Framework.
*
* @author Josh Bloch and Doug Lea
@@ -68,13 +68,15 @@ public class ArrayDeque extends Abstr
*
* Because in a circular array, elements are in general stored in
* two disjoint such slices, we help the VM by writing unusual
- * nested loops for all traversals over the elements.
+ * nested loops for all traversals over the elements. Having only
+ * one hot inner loop body instead of two or three eases human
+ * maintenance and encourages VM loop inlining into the caller.
*/
/**
* The array in which the elements of the deque are stored.
- * We guarantee that all array cells not holding deque elements
- * are always null.
+ * All array cells not holding deque elements are always null.
+ * The array always has at least one null slot (at tail).
*/
transient Object[] elements;
@@ -88,7 +90,8 @@ public class ArrayDeque extends Abstr
/**
* The index at which the next element would be added to the tail
- * of the deque (via addLast(E), add(E), or push(E)).
+ * of the deque (via addLast(E), add(E), or push(E));
+ * elements[tail] is always null.
*/
transient int tail;
@@ -114,16 +117,16 @@ public class ArrayDeque extends Abstr
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;
}
// checkInvariants();
}
@@ -177,7 +180,7 @@ public class ArrayDeque extends Abstr
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
- elements = new Object[16];
+ elements = new Object[16 + 1];
}
/**
@@ -187,7 +190,10 @@ public class ArrayDeque extends Abstr
* @param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
- elements = new Object[Math.max(1, numElements + 1)];
+ elements =
+ new Object[(numElements < 1) ? 1 :
+ (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
+ numElements + 1];
}
/**
@@ -201,12 +207,12 @@ public class ArrayDeque extends Abstr
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection extends E> c) {
- elements = new Object[c.size() + 1];
- addAll(c);
+ this(c.size());
+ copyElements(c);
}
/**
- * Increments i, mod modulus.
+ * Circularly increments i, mod modulus.
* Precondition and postcondition: 0 <= i < modulus.
*/
static final int inc(int i, int modulus) {
@@ -215,7 +221,7 @@ public class ArrayDeque extends Abstr
}
/**
- * Decrements i, mod modulus.
+ * Circularly decrements i, mod modulus.
* Precondition and postcondition: 0 <= i < modulus.
*/
static final int dec(int i, int modulus) {
@@ -224,19 +230,21 @@ public class ArrayDeque extends Abstr
}
/**
- * Adds i and j, mod modulus.
- * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
+ * Circularly adds the given distance to index i, mod modulus.
+ * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
+ * @return index 0 <= i < modulus
*/
- static final int add(int i, int j, int modulus) {
- if ((i += j) - modulus >= 0) i -= modulus;
+ static final int inc(int i, int distance, int modulus) {
+ if ((i += distance) - modulus >= 0) i -= modulus;
return i;
}
/**
* Subtracts j from i, mod modulus.
- * Index i must be logically ahead of j.
- * Returns the "circular distance" from j to i.
- * Precondition and postcondition: 0 <= i < modulus, 0 <= j < modulus.
+ * Index i must be logically ahead of index j.
+ * Precondition: 0 <= i < modulus, 0 <= j < modulus.
+ * @return the "circular distance" from j to i; corner case i == j
+ * is disambiguated to "empty", returning 0.
*/
static final int sub(int i, int j, int modulus) {
if ((i -= j) < 0) i += modulus;
@@ -305,8 +313,7 @@ public class ArrayDeque extends Abstr
/**
* Adds all of the elements in the specified collection at the end
* of this deque, as if by calling {@link #addLast} on each one,
- * in the order that they are returned by the collection's
- * iterator.
+ * in the order that they are returned by the collection's iterator.
*
* @param c the elements to be inserted into this deque
* @return {@code true} if this deque changed as a result of the call
@@ -314,14 +321,18 @@ public class ArrayDeque extends Abstr
* of its elements are null
*/
public boolean addAll(Collection extends E> c) {
- final int s = size(), needed;
- if ((needed = s + c.size() - elements.length + 1) > 0)
+ final int s, needed;
+ if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
grow(needed);
- c.forEach(e -> addLast(e));
+ copyElements(c);
// checkInvariants();
return size() > s;
}
+ private void copyElements(Collection extends E> c) {
+ c.forEach(this::addLast);
+ }
+
/**
* Inserts the specified element at the front of this deque.
*
@@ -512,8 +523,8 @@ public class ArrayDeque extends Abstr
/**
* Retrieves and removes the head of the queue represented by this deque.
*
- * This method differs from {@link #poll poll} only in that it throws an
- * exception if this deque is empty.
+ * This method differs from {@link #poll() poll()} only in that it
+ * throws an exception if this deque is empty.
*
* This method is equivalent to {@link #removeFirst}.
*
@@ -608,10 +619,11 @@ public class ArrayDeque extends Abstr
// checkInvariants();
final Object[] es = elements;
final int capacity = es.length;
- final int h = head;
+ final int h, t;
// number of elements before to-be-deleted elt
- final int front = sub(i, h, capacity);
- final int back = size() - front - 1; // number of elements after
+ final int front = sub(i, h = head, capacity);
+ // number of elements after to-be-deleted elt
+ final int back = sub(t = tail, i, capacity) - 1;
if (front < back) {
// move front elements forwards
if (h <= i) {
@@ -627,14 +639,13 @@ public class ArrayDeque extends Abstr
return false;
} else {
// move back elements backwards
- tail = dec(tail, capacity);
+ tail = dec(t, capacity);
if (i <= tail) {
System.arraycopy(es, i + 1, es, i, back);
} else { // Wrap around
- int firstLeg = capacity - (i + 1);
- System.arraycopy(es, i + 1, es, i, firstLeg);
+ System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
es[capacity - 1] = es[0];
- System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
+ System.arraycopy(es, 1, es, 0, t - 1);
}
es[tail] = null;
// checkInvariants();
@@ -702,8 +713,7 @@ public class ArrayDeque extends Abstr
throw new NoSuchElementException();
final Object[] es = elements;
E e = nonNullElementAt(es, cursor);
- lastRet = cursor;
- cursor = inc(cursor, es.length);
+ cursor = inc(lastRet = cursor, es.length);
remaining--;
return e;
}
@@ -751,8 +761,7 @@ public class ArrayDeque extends Abstr
throw new NoSuchElementException();
final Object[] es = elements;
E e = nonNullElementAt(es, cursor);
- lastRet = cursor;
- cursor = dec(cursor, es.length);
+ cursor = dec(lastRet = cursor, es.length);
remaining--;
return e;
}
@@ -814,6 +823,8 @@ public class ArrayDeque extends Abstr
/** Constructs spliterator over the given range. */
DeqSpliterator(int origin, int fence) {
+ // assert 0 <= origin && origin < elements.length;
+ // assert 0 <= fence && fence < elements.length;
this.cursor = origin;
this.fence = fence;
}
@@ -833,7 +844,7 @@ public class ArrayDeque extends Abstr
final int i, n;
return ((n = sub(getFence(), i = cursor, es.length) >> 1) <= 0)
? null
- : new DeqSpliterator(i, cursor = add(i, n, es.length));
+ : new DeqSpliterator(i, cursor = inc(i, n, es.length));
}
public void forEachRemaining(Consumer super E> action) {
@@ -856,15 +867,15 @@ public class ArrayDeque extends Abstr
}
public boolean tryAdvance(Consumer super E> action) {
- if (action == null)
- throw new NullPointerException();
- int t, i;
- if ((t = fence) < 0) t = getFence();
- if (t == (i = cursor))
+ Objects.requireNonNull(action);
+ final Object[] es = elements;
+ if (fence < 0) { fence = tail; cursor = head; } // late-binding
+ final int i;
+ if ((i = cursor) == fence)
return false;
- final Object[] es;
- action.accept(nonNullElementAt(es = elements, i));
+ E e = nonNullElementAt(es, i);
cursor = inc(i, es.length);
+ action.accept(e);
return true;
}
@@ -880,6 +891,9 @@ public class ArrayDeque extends Abstr
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
public void forEach(Consumer super E> action) {
Objects.requireNonNull(action);
final Object[] es = elements;
@@ -902,7 +916,7 @@ public class ArrayDeque extends Abstr
* @param operator the operator to apply to each element
* @since TBD
*/
- /* public */ void replaceAll(UnaryOperator operator) {
+ /* public */ void replaceAll(java.util.function.UnaryOperator operator) {
Objects.requireNonNull(operator);
final Object[] es = elements;
for (int i = head, end = tail, to = (i <= end) ? end : es.length;
@@ -950,7 +964,7 @@ public class ArrayDeque extends Abstr
; i = 0, to = end) {
for (; i < to; i++)
if (filter.test(elementAt(es, i)))
- return bulkRemoveModified(filter, i, to);
+ return bulkRemoveModified(filter, i);
if (to == end) {
if (end != tail) throw new ConcurrentModificationException();
break;
@@ -959,45 +973,62 @@ public class ArrayDeque extends Abstr
return false;
}
+ // A tiny bit set implementation
+
+ private static long[] nBits(int n) {
+ return new long[((n - 1) >> 6) + 1];
+ }
+ private static void setBit(long[] bits, int i) {
+ bits[i >> 6] |= 1L << i;
+ }
+ private static boolean isClear(long[] bits, int i) {
+ return (bits[i >> 6] & (1L << i)) == 0;
+ }
+
/**
* Helper for bulkRemove, in case of at least one deletion.
- * @param i valid index of first element to be deleted
+ * Tolerate predicates that reentrantly access the collection for
+ * read (but writers still get CME), so traverse once to find
+ * elements to delete, a second pass to physically expunge.
+ *
+ * @param beg valid index of first element to be deleted
*/
private boolean bulkRemoveModified(
- Predicate super E> filter, int i, int to) {
+ Predicate super E> filter, final int beg) {
final Object[] es = elements;
final int capacity = es.length;
- // a two-finger algorithm, with hare i reading, tortoise j writing
- int j = i++;
final int end = tail;
- try {
- for (;; j = 0) { // j rejoins i on second leg
- E e;
- // In this loop, i and j are on the same leg, with i > j
- for (; i < to; i++)
- if (!filter.test(e = elementAt(es, i)))
- es[j++] = e;
- if (to == end) break;
- // In this loop, j is on the first leg, i on the second
- for (i = 0, to = end; i < to && j < capacity; i++)
- if (!filter.test(e = elementAt(es, i)))
- es[j++] = e;
- if (i >= to) {
- if (j == capacity) j = 0; // "corner" case
- break;
- }
+ final long[] deathRow = nBits(sub(end, beg, capacity));
+ deathRow[0] = 1L; // set bit 0
+ for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+ ; i = 0, to = end, k -= capacity) {
+ for (; i < to; i++)
+ if (filter.test(elementAt(es, i)))
+ setBit(deathRow, i - k);
+ if (to == end) break;
+ }
+ // a two-finger traversal, with hare i reading, tortoise w writing
+ int w = beg;
+ for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg;
+ ; w = 0) { // w rejoins i on second leg
+ // In this loop, i and w are on the same leg, with i > w
+ for (; i < to; i++)
+ if (isClear(deathRow, i - k))
+ es[w++] = es[i];
+ if (to == end) break;
+ // In this loop, w is on the first leg, i on the second
+ for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++)
+ if (isClear(deathRow, i - k))
+ es[w++] = es[i];
+ if (i >= to) {
+ if (w == capacity) w = 0; // "corner" case
+ break;
}
- return true;
- } catch (Throwable ex) {
- // copy remaining elements
- for (; i != end; i = inc(i, capacity), j = inc(j, capacity))
- es[j] = es[i];
- throw ex;
- } finally {
- if (end != tail) throw new ConcurrentModificationException();
- circularClear(es, tail = j, end);
- // checkInvariants();
}
+ if (end != tail) throw new ConcurrentModificationException();
+ circularClear(es, tail = w, end);
+ // checkInvariants();
+ return true;
}
/**
@@ -1051,11 +1082,14 @@ public class ArrayDeque extends Abstr
/**
* 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;
}
}
@@ -1080,17 +1114,17 @@ public class ArrayDeque extends Abstr
private T[] toArray(Class klazz) {
final Object[] es = elements;
final T[] a;
- final int size = size(), head = this.head, end;
- final int len = Math.min(size, es.length - head);
- if ((end = head + size) >= 0) {
+ final int head = this.head, tail = this.tail, end;
+ if ((end = tail + ((head <= tail) ? 0 : es.length)) >= 0) {
+ // Uses null extension feature of copyOfRange
a = Arrays.copyOfRange(es, head, end, klazz);
} else {
// integer overflow!
- a = Arrays.copyOfRange(es, 0, size, klazz);
- System.arraycopy(es, head, a, 0, len);
+ a = Arrays.copyOfRange(es, 0, end - head, klazz);
+ System.arraycopy(es, head, a, 0, es.length - head);
}
- if (tail < head)
- System.arraycopy(es, 0, a, len, tail);
+ if (end != tail)
+ System.arraycopy(es, 0, a, es.length - head, tail);
return a;
}
@@ -1205,6 +1239,7 @@ public class ArrayDeque extends Abstr
// Read in size and allocate array
int size = s.readInt();
+ jsr166.Platform.checkArray(s, Object[].class, size + 1);
elements = new Object[size + 1];
this.tail = size;
@@ -1215,10 +1250,12 @@ public class ArrayDeque extends Abstr
/** debugging */
void checkInvariants() {
+ // Use head and tail fields with empty slot at tail strategy.
+ // head == tail disambiguates to "empty".
try {
int capacity = elements.length;
- // assert head >= 0 && head < capacity;
- // assert tail >= 0 && tail < capacity;
+ // assert 0 <= head && head < capacity;
+ // assert 0 <= tail && tail < capacity;
// assert capacity > 0;
// assert size() < capacity;
// assert head == tail || elements[head] != null;