--- jsr166/src/main/java/util/ArrayDeque.java 2016/10/18 00:33:05 1.77 +++ jsr166/src/main/java/util/ArrayDeque.java 2017/05/06 06:49:45 1.128 @@ -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 @@ -60,22 +60,40 @@ import java.util.function.UnaryOperator; public class ArrayDeque extends AbstractCollection implements Deque, Cloneable, Serializable { + /* + * VMs excel at optimizing simple array loops where indices are + * incrementing or decrementing over a valid slice, e.g. + * + * for (int i = start; i < end; i++) ... elements[i] + * + * 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. 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; /** * The index of the element at the head of the deque (which is the * element that would be removed by remove() or pop()); or an - * arbitrary number 0 <= head < elements.length if the deque is empty. + * arbitrary number 0 <= head < elements.length equal to tail if + * the deque is empty. */ transient int head; - /** Number of elements in this collection. */ - transient int size; + /** + * The index at which the next element would be added to the tail + * of the deque (via addLast(E), add(E), or push(E)); + * elements[tail] is always null. + */ + transient int tail; /** * The maximum size of array to allocate. @@ -92,31 +110,30 @@ public class ArrayDeque extends Abstr */ private void grow(int needed) { // overflow-conscious code - // checkInvariants(); - int oldCapacity = elements.length; + final int oldCapacity = elements.length; int newCapacity; - // Double size if small; else grow by 50% + // Double capacity if small; else grow by 50% int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1); if (jump < needed || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0) newCapacity = newCapacity(needed, jump); - elements = Arrays.copyOf(elements, newCapacity); - if (oldCapacity - head < size) { + final Object[] es = elements = Arrays.copyOf(elements, newCapacity); + // Exceptionally, here tail == head needs to be disambiguated + 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(); } /** Capacity calculation for edge conditions, especially overflow. */ private int newCapacity(int needed, int jump) { - int oldCapacity = elements.length; - int minCapacity; + final int oldCapacity = elements.length, minCapacity; if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) { if (minCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); @@ -134,23 +151,26 @@ public class ArrayDeque extends Abstr * to ensure that it can hold at least the given number of elements. * * @param minCapacity the desired minimum capacity - * @since 9 + * @since TBD */ - public void ensureCapacity(int minCapacity) { - if (minCapacity > elements.length) - grow(minCapacity - elements.length); + /* public */ void ensureCapacity(int minCapacity) { + int needed; + if ((needed = (minCapacity + 1 - elements.length)) > 0) + grow(needed); // checkInvariants(); } /** * Minimizes the internal storage of this collection. * - * @since 9 + * @since TBD */ - public void trimToSize() { - if (size < elements.length) { - elements = toArray(); + /* public */ void trimToSize() { + int size; + if ((size = size()) + 1 < elements.length) { + elements = toArray(new Object[size + 1]); head = 0; + tail = size; } // checkInvariants(); } @@ -170,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[numElements]; + elements = + new Object[(numElements < 1) ? 1 : + (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : + numElements + 1]; } /** @@ -184,58 +207,57 @@ public class ArrayDeque extends Abstr * @throws NullPointerException if the specified collection is null */ public ArrayDeque(Collection c) { - Object[] elements = 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, size, Object[].class); - for (Object obj : elements) - Objects.requireNonNull(obj); - size = elements.length; - this.elements = elements; + this(c.size()); + addAll(c); } /** - * Returns the array index of the last element. - * May return invalid index -1 if there are no elements. + * Increments i, mod modulus. + * Precondition and postcondition: 0 <= i < modulus. */ - final int tail() { - return add(head, size - 1, elements.length); + static final int inc(int i, int modulus) { + if (++i >= modulus) i = 0; + return i; } /** - * Adds i and j, mod modulus. - * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus. + * Decrements i, mod modulus. + * Precondition and postcondition: 0 <= i < modulus. */ - static final int add(int i, int j, int modulus) { - if ((i += j) - modulus >= 0) i -= modulus; + static final int dec(int i, int modulus) { + if (--i < 0) i = modulus - 1; return i; } /** - * Increments i, mod modulus. - * Precondition and postcondition: 0 <= i < 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 inc(int i, int modulus) { - if (++i == modulus) i = 0; + static final int add(int i, int distance, int modulus) { + if ((i += distance) - modulus >= 0) i -= modulus; return i; } /** - * Decrements i, mod modulus. - * Precondition and postcondition: 0 <= i < modulus. + * Subtracts j from i, mod 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 diambiguated to "empty", returning 0. */ - static final int dec(int i, int modulus) { - if (--i < 0) i += modulus; + static final int sub(int i, int j, int modulus) { + if ((i -= j) < 0) i += modulus; return i; } /** * Returns element at array index i. + * This is a slight abuse of generics, accepted by javac. */ @SuppressWarnings("unchecked") - final E elementAt(int i) { - return (E) elements[i]; + static final E elementAt(Object[] es, int i) { + return (E) es[i]; } /** @@ -243,8 +265,8 @@ public class ArrayDeque extends Abstr * This check doesn't catch all possible comodifications, * but does catch ones that corrupt traversal. */ - E checkedElementAt(Object[] elements, int i) { - @SuppressWarnings("unchecked") E e = (E) elements[i]; + static final E nonNullElementAt(Object[] es, int i) { + @SuppressWarnings("unchecked") E e = (E) es[i]; if (e == null) throw new ConcurrentModificationException(); return e; @@ -261,14 +283,13 @@ public class ArrayDeque extends Abstr * @throws NullPointerException if the specified element is null */ public void addFirst(E e) { - // checkInvariants(); - Objects.requireNonNull(e); - Object[] elements; - int capacity, s = size; - while (s == (capacity = (elements = this.elements).length)) + if (e == null) + throw new NullPointerException(); + final Object[] es = elements; + es[head = dec(head, es.length)] = e; + if (head == tail) grow(1); - elements[head = dec(head, capacity)] = e; - size = s + 1; + // checkInvariants(); } /** @@ -280,14 +301,13 @@ public class ArrayDeque extends Abstr * @throws NullPointerException if the specified element is null */ public void addLast(E e) { - // checkInvariants(); - Objects.requireNonNull(e); - Object[] elements; - int capacity, s = size; - while (s == (capacity = (elements = this.elements).length)) + if (e == null) + throw new NullPointerException(); + final Object[] es = elements; + es[tail] = e; + if (head == (tail = inc(tail, es.length))) grow(1); - elements[add(head, s, capacity)] = e; - size = s + 1; + // checkInvariants(); } /** @@ -301,23 +321,13 @@ public class ArrayDeque extends Abstr * @throws NullPointerException if the specified collection or any * of its elements are null */ - @Override public boolean addAll(Collection c) { + final int s, needed; + if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0) + grow(needed); + c.forEach(this::addLast); // checkInvariants(); - Object[] a, elements; - int len, capacity, s = size; - if ((len = (a = c.toArray()).length) == 0) - return false; - while ((capacity = (elements = this.elements).length) - s < len) - grow(len - (capacity - s)); - int i = add(head, s, capacity); - for (Object x : a) { - Objects.requireNonNull(x); - elements[i] = x; - i = inc(i, capacity); - size++; - } - return true; + return size() > s; } /** @@ -348,47 +358,43 @@ public class ArrayDeque extends Abstr * @throws NoSuchElementException {@inheritDoc} */ public E removeFirst() { - // checkInvariants(); - E x = pollFirst(); - if (x == null) + E e = pollFirst(); + if (e == null) throw new NoSuchElementException(); - return x; + // checkInvariants(); + return e; } /** * @throws NoSuchElementException {@inheritDoc} */ public E removeLast() { - // checkInvariants(); - E x = pollLast(); - if (x == null) + E e = pollLast(); + if (e == null) throw new NoSuchElementException(); - return x; + // checkInvariants(); + return e; } public E pollFirst() { + final Object[] es; + final int h; + E e = elementAt(es = elements, h = head); + if (e != null) { + es[h] = null; + head = inc(h, es.length); + } // checkInvariants(); - final int s, h; - if ((s = size) == 0) - return null; - final Object[] elements = this.elements; - @SuppressWarnings("unchecked") E e = (E) elements[h = head]; - elements[h] = null; - head = inc(h, elements.length); - size = s - 1; return e; } public E pollLast() { + final Object[] es; + final int t; + E e = elementAt(es = elements, t = dec(tail, es.length)); + if (e != null) + es[tail = t] = null; // checkInvariants(); - final int s, tail; - if ((s = size) == 0) - return null; - final Object[] elements = this.elements; - @SuppressWarnings("unchecked") - E e = (E) elements[tail = add(head, s - 1, elements.length)]; - elements[tail] = null; - size = s - 1; return e; } @@ -396,28 +402,34 @@ public class ArrayDeque extends Abstr * @throws NoSuchElementException {@inheritDoc} */ public E getFirst() { + E e = elementAt(elements, head); + if (e == null) + throw new NoSuchElementException(); // checkInvariants(); - if (size == 0) throw new NoSuchElementException(); - return elementAt(head); + return e; } /** * @throws NoSuchElementException {@inheritDoc} */ public E getLast() { + final Object[] es = elements; + E e = elementAt(es, dec(tail, es.length)); + if (e == null) + throw new NoSuchElementException(); // checkInvariants(); - if (size == 0) throw new NoSuchElementException(); - return elementAt(tail()); + return e; } public E peekFirst() { // checkInvariants(); - return (size == 0) ? null : elementAt(head); + return elementAt(elements, head); } public E peekLast() { // checkInvariants(); - return (size == 0) ? null : elementAt(tail()); + final Object[] es; + return elementAt(es = elements, dec(tail, es.length)); } /** @@ -433,15 +445,16 @@ public class ArrayDeque extends Abstr * @return {@code true} if the deque contained the specified element */ public boolean removeFirstOccurrence(Object o) { - // checkInvariants(); if (o != null) { - final Object[] elements = this.elements; - final int capacity = elements.length; - for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) { - if (o.equals(elements[i])) { - delete(i); - return true; - } + final Object[] es = elements; + for (int i = head, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + if (o.equals(es[i])) { + delete(i); + return true; + } + if (to == end) break; } } return false; @@ -461,14 +474,15 @@ public class ArrayDeque extends Abstr */ public boolean removeLastOccurrence(Object o) { if (o != null) { - final Object[] elements = this.elements; - final int capacity = elements.length; - for (int k = size, i = add(head, k - 1, capacity); - --k >= 0; i = dec(i, capacity)) { - if (o.equals(elements[i])) { - delete(i); - return true; - } + final Object[] es = elements; + for (int i = tail, end = head, to = (i >= end) ? end : 0; + ; i = es.length, to = end) { + for (i--; i > to - 1; i--) + if (o.equals(es[i])) { + delete(i); + return true; + } + if (to == end) break; } } return false; @@ -506,8 +520,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}. * @@ -596,43 +610,41 @@ public class ArrayDeque extends Abstr *

This method is called delete rather than remove to emphasize * that its semantics differ from those of {@link List#remove(int)}. * - * @return true if elements moved backwards + * @return true if elements near tail moved backwards */ boolean delete(int i) { // checkInvariants(); - final Object[] elements = this.elements; - final int capacity = elements.length; - final int h = head; - int front; // number of elements before to-be-deleted elt - if ((front = i - h) < 0) front += capacity; - final int back = size - front - 1; // number of elements after + final Object[] es = elements; + final int capacity = es.length; + final int h, t; + // number of elements before to-be-deleted elt + 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) { - System.arraycopy(elements, h, elements, h + 1, front); + System.arraycopy(es, h, es, h + 1, front); } else { // Wrap around - System.arraycopy(elements, 0, elements, 1, i); - elements[0] = elements[capacity - 1]; - System.arraycopy(elements, h, elements, h + 1, front - (i + 1)); + System.arraycopy(es, 0, es, 1, i); + es[0] = es[capacity - 1]; + System.arraycopy(es, h, es, h + 1, front - (i + 1)); } - elements[h] = null; + es[h] = null; head = inc(h, capacity); - size--; // checkInvariants(); return false; } else { // move back elements backwards - int tail = tail(); + tail = dec(t, capacity); if (i <= tail) { - System.arraycopy(elements, i + 1, elements, i, back); + System.arraycopy(es, i + 1, es, i, back); } else { // Wrap around - int firstLeg = capacity - (i + 1); - System.arraycopy(elements, i + 1, elements, i, firstLeg); - elements[capacity - 1] = elements[0]; - System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1); + System.arraycopy(es, i + 1, es, i, capacity - (i + 1)); + es[capacity - 1] = es[0]; + System.arraycopy(es, 1, es, 0, t - 1); } - elements[tail] = null; - size--; + es[tail] = null; // checkInvariants(); return true; } @@ -646,7 +658,7 @@ public class ArrayDeque extends Abstr * @return the number of elements in this deque */ public int size() { - return size; + return sub(tail, head, elements.length); } /** @@ -655,7 +667,7 @@ public class ArrayDeque extends Abstr * @return {@code true} if this deque contains no elements */ public boolean isEmpty() { - return size == 0; + return head == tail; } /** @@ -679,7 +691,7 @@ public class ArrayDeque extends Abstr int cursor; /** Number of elements yet to be returned. */ - int remaining = size; + int remaining = size(); /** * Index of element returned by most recent call to next. @@ -689,60 +701,95 @@ public class ArrayDeque extends Abstr DeqIterator() { cursor = head; } - int advance(int i, int modulus) { - return inc(i, modulus); - } - - void doRemove() { - if (delete(lastRet)) - // if left-shifted, undo advance in next() - cursor = dec(cursor, elements.length); - } - public final boolean hasNext() { return remaining > 0; } - public final E next() { - if (remaining == 0) + public E next() { + if (remaining <= 0) throw new NoSuchElementException(); - E e = checkedElementAt(elements, cursor); - lastRet = cursor; - cursor = advance(cursor, elements.length); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); + cursor = inc(lastRet = cursor, es.length); remaining--; return e; } + void postDelete(boolean leftShifted) { + if (leftShifted) + cursor = dec(cursor, elements.length); + } + public final void remove() { if (lastRet < 0) throw new IllegalStateException(); - doRemove(); + postDelete(delete(lastRet)); lastRet = -1; } - public final void forEachRemaining(Consumer action) { + public void forEachRemaining(Consumer action) { Objects.requireNonNull(action); - final Object[] elements = ArrayDeque.this.elements; - final int capacity = elements.length; - int k = remaining; + int r; + if ((r = remaining) <= 0) + return; remaining = 0; - for (int i = cursor; --k >= 0; i = advance(i, capacity)) - action.accept(checkedElementAt(elements, i)); + final Object[] es = elements; + if (es[cursor] == null || sub(tail, cursor, es.length) != r) + throw new ConcurrentModificationException(); + for (int i = cursor, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + action.accept(elementAt(es, i)); + if (to == end) { + if (end != tail) + throw new ConcurrentModificationException(); + lastRet = dec(end, es.length); + break; + } + } } } private class DescendingIterator extends DeqIterator { - DescendingIterator() { cursor = tail(); } + DescendingIterator() { cursor = dec(tail, elements.length); } - @Override int advance(int i, int modulus) { - return dec(i, modulus); + public final E next() { + if (remaining <= 0) + throw new NoSuchElementException(); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); + cursor = dec(lastRet = cursor, es.length); + remaining--; + return e; } - @Override void doRemove() { - if (!delete(lastRet)) - // if right-shifted, undo advance in next + void postDelete(boolean leftShifted) { + if (!leftShifted) cursor = inc(cursor, elements.length); } + + public final void forEachRemaining(Consumer action) { + Objects.requireNonNull(action); + int r; + if ((r = remaining) <= 0) + return; + remaining = 0; + final Object[] es = elements; + if (es[cursor] == null || sub(cursor, head, es.length) + 1 != r) + throw new ConcurrentModificationException(); + for (int i = cursor, end = head, to = (i >= end) ? end : 0; + ; i = es.length - 1, to = end) { + // hotspot generates faster code than for: i >= to ! + for (; i > to - 1; i--) + action.accept(elementAt(es, i)); + if (to == end) { + if (end != head) + throw new ConcurrentModificationException(); + lastRet = end; + break; + } + } + } } /** @@ -759,66 +806,78 @@ public class ArrayDeque extends Abstr * @since 1.8 */ public Spliterator spliterator() { - return new ArrayDequeSpliterator(); + return new DeqSpliterator(); } - final class ArrayDequeSpliterator implements Spliterator { - private int cursor; - private int remaining; // -1 until late-binding first use + final class DeqSpliterator implements Spliterator { + private int fence; // -1 until first use + private int cursor; // current index, modified on traverse/split /** Constructs late-binding spliterator over all elements. */ - ArrayDequeSpliterator() { - this.remaining = -1; + DeqSpliterator() { + this.fence = -1; } - /** Constructs spliterator over the given slice. */ - ArrayDequeSpliterator(int cursor, int count) { - this.cursor = cursor; - this.remaining = count; - } - - /** Ensures late-binding initialization; then returns remaining. */ - private int remaining() { - if (remaining < 0) { + /** 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; + } + + /** Ensures late-binding initialization; then returns fence. */ + private int getFence() { // force initialization + int t; + if ((t = fence) < 0) { + t = fence = tail; cursor = head; - remaining = size; } - return remaining; + return t; } - public ArrayDequeSpliterator trySplit() { - final int mid; - if ((mid = remaining() >> 1) > 0) { - int oldCursor = cursor; - cursor = add(cursor, mid, elements.length); - remaining -= mid; - return new ArrayDequeSpliterator(oldCursor, mid); - } - return null; + public DeqSpliterator trySplit() { + final Object[] es = elements; + final int i, n; + return ((n = sub(getFence(), i = cursor, es.length) >> 1) <= 0) + ? null + : new DeqSpliterator(i, cursor = add(i, n, es.length)); } public void forEachRemaining(Consumer action) { - Objects.requireNonNull(action); - final Object[] elements = ArrayDeque.this.elements; - final int capacity = elements.length; - int k = remaining(); - remaining = 0; - for (int i = cursor; --k >= 0; i = inc(i, capacity)) - action.accept(checkedElementAt(elements, i)); + if (action == null) + throw new NullPointerException(); + final int end = getFence(), cursor = this.cursor; + final Object[] es = elements; + if (cursor != end) { + this.cursor = end; + // null check at both ends of range is sufficient + if (es[cursor] == null || es[dec(end, es.length)] == null) + throw new ConcurrentModificationException(); + for (int i = cursor, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + action.accept(elementAt(es, i)); + if (to == end) break; + } + } } public boolean tryAdvance(Consumer action) { Objects.requireNonNull(action); - if (remaining() == 0) + final Object[] es = elements; + if (fence < 0) { fence = tail; cursor = head; } // late-binding + final int i; + if ((i = cursor) == fence) return false; - action.accept(checkedElementAt(elements, cursor)); - cursor = inc(cursor, elements.length); - remaining--; + E e = nonNullElementAt(es, i); + cursor = inc(i, es.length); + action.accept(e); return true; } public long estimateSize() { - return remaining(); + return sub(getFence(), cursor, elements.length); } public int characteristics() { @@ -829,14 +888,21 @@ public class ArrayDeque extends Abstr } } - @Override + /** + * @throws NullPointerException {@inheritDoc} + */ public void forEach(Consumer action) { - // checkInvariants(); Objects.requireNonNull(action); - final Object[] elements = this.elements; - final int capacity = elements.length; - for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) - action.accept(elementAt(i)); + final Object[] es = elements; + for (int i = head, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + action.accept(elementAt(es, i)); + if (to == end) { + if (end != tail) throw new ConcurrentModificationException(); + break; + } + } // checkInvariants(); } @@ -845,21 +911,26 @@ public class ArrayDeque extends Abstr * operator to that element, as specified by {@link List#replaceAll}. * * @param operator the operator to apply to each element - * @since 9 + * @since TBD */ - public void replaceAll(UnaryOperator operator) { + /* public */ void replaceAll(UnaryOperator operator) { Objects.requireNonNull(operator); - final Object[] elements = this.elements; - final int capacity = elements.length; - for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) - elements[i] = operator.apply(elementAt(i)); + final Object[] es = elements; + for (int i = head, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + es[i] = operator.apply(elementAt(es, i)); + if (to == end) { + if (end != tail) throw new ConcurrentModificationException(); + break; + } + } // checkInvariants(); } /** * @throws NullPointerException {@inheritDoc} */ - @Override public boolean removeIf(Predicate filter) { Objects.requireNonNull(filter); return bulkRemove(filter); @@ -868,7 +939,6 @@ public class ArrayDeque extends Abstr /** * @throws NullPointerException {@inheritDoc} */ - @Override public boolean removeAll(Collection c) { Objects.requireNonNull(c); return bulkRemove(e -> c.contains(e)); @@ -877,7 +947,6 @@ public class ArrayDeque extends Abstr /** * @throws NullPointerException {@inheritDoc} */ - @Override public boolean retainAll(Collection c) { Objects.requireNonNull(c); return bulkRemove(e -> !c.contains(e)); @@ -886,32 +955,77 @@ public class ArrayDeque extends Abstr /** Implementation of bulk remove methods. */ private boolean bulkRemove(Predicate filter) { // checkInvariants(); - final Object[] elements = this.elements; - final int capacity = elements.length; - int i = head, j = i, remaining = size, deleted = 0; - try { - for (; remaining > 0; remaining--, i = inc(i, capacity)) { - @SuppressWarnings("unchecked") E e = (E) elements[i]; - if (filter.test(e)) - deleted++; - else { - if (j != i) - elements[j] = e; - j = inc(j, capacity); - } + final Object[] es = elements; + // Optimize for initial run of survivors + for (int i = head, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + if (filter.test(elementAt(es, i))) + return bulkRemoveModified(filter, i); + if (to == end) { + if (end != tail) throw new ConcurrentModificationException(); + break; + } + } + 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. + * 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 filter, final int beg) { + final Object[] es = elements; + final int capacity = es.length; + final int end = tail; + 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 deleted > 0; - } catch (Throwable ex) { - for (; remaining > 0; - remaining--, i = inc(i, capacity), j = inc(j, capacity)) - elements[j] = elements[i]; - throw ex; - } finally { - size -= deleted; - for (; --deleted >= 0; j = inc(j, capacity)) - elements[j] = null; - // checkInvariants(); } + if (end != tail) throw new ConcurrentModificationException(); + circularClear(es, tail = w, end); + // checkInvariants(); + return true; } /** @@ -924,11 +1038,14 @@ public class ArrayDeque extends Abstr */ public boolean contains(Object o) { if (o != null) { - final Object[] elements = this.elements; - final int capacity = elements.length; - for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) - if (o.equals(elements[i])) - return true; + final Object[] es = elements; + for (int i = head, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + if (o.equals(es[i])) + return true; + if (to == end) break; + } } return false; } @@ -955,21 +1072,26 @@ public class ArrayDeque extends Abstr * The deque will be empty after this call returns. */ public void clear() { - final Object[] elements = this.elements; - final int capacity = elements.length; - final int h = this.head; - final int s = size; - if (capacity - h >= s) - Arrays.fill(elements, h, h + s, null); - else { - Arrays.fill(elements, h, capacity, null); - Arrays.fill(elements, 0, s - capacity + h, null); - } - size = head = 0; + circularClear(elements, head, tail); + head = tail = 0; // checkInvariants(); } /** + * 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) { + for (; i < to; i++) es[i] = null; + if (to == end) break; + } + } + + /** * Returns an array containing all of the elements in this deque * in proper sequence (from first to last element). * @@ -983,11 +1105,23 @@ public class ArrayDeque extends Abstr * @return an array containing all of the elements in this deque */ public Object[] toArray() { - final int head = this.head; - final int firstLeg; - Object[] a = Arrays.copyOfRange(elements, head, head + size); - if ((firstLeg = elements.length - head) < size) - System.arraycopy(elements, 0, a, firstLeg, size - firstLeg); + return toArray(Object[].class); + } + + private T[] toArray(Class klazz) { + final Object[] es = elements; + final T[] a; + 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, end - head, klazz); + System.arraycopy(es, head, a, 0, es.length - head); + } + if (end != tail) + System.arraycopy(es, 0, a, es.length - head, tail); return a; } @@ -1029,20 +1163,17 @@ public class ArrayDeque extends Abstr */ @SuppressWarnings("unchecked") public T[] toArray(T[] a) { - final Object[] elements = this.elements; - final int head = this.head; - final int firstLeg; - boolean wrap = (firstLeg = elements.length - head) < size; - if (size > a.length) { - a = (T[]) Arrays.copyOfRange(elements, head, head + size, - a.getClass()); - } else { - System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size); - if (size < a.length) - a[size] = null; + final int size; + if ((size = size()) > a.length) + return toArray((Class) a.getClass()); + final Object[] es = elements; + for (int i = head, j = 0, len = Math.min(size, es.length - i); + ; i = 0, len = tail) { + System.arraycopy(es, i, a, j, len); + if ((j += len) == size) break; } - if (wrap) - System.arraycopy(elements, 0, a, firstLeg, size - firstLeg); + if (size < a.length) + a[size] = null; return a; } @@ -1080,13 +1211,16 @@ public class ArrayDeque extends Abstr s.defaultWriteObject(); // Write out size - s.writeInt(size); + s.writeInt(size()); // Write out elements in order. - final Object[] elements = this.elements; - final int capacity = elements.length; - for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) - s.writeObject(elements[i]); + final Object[] es = elements; + for (int i = head, end = tail, to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + for (; i < to; i++) + s.writeObject(es[i]); + if (to == end) break; + } } /** @@ -1101,7 +1235,9 @@ public class ArrayDeque extends Abstr s.defaultReadObject(); // Read in size and allocate array - elements = new Object[size = s.readInt()]; + int size = s.readInt(); + elements = new Object[size + 1]; + this.tail = size; // Read in all elements in the proper order. for (int i = 0; i < size; i++) @@ -1109,20 +1245,21 @@ public class ArrayDeque extends Abstr } /** debugging */ - private void checkInvariants() { + void checkInvariants() { + // Use head and tail fields with empty slot at tail strategy. + // head == tail disambiguates to "empty". try { int capacity = elements.length; - assert size >= 0 && size <= capacity; - assert head >= 0 && ((capacity == 0 && head == 0 && size == 0) - || head < capacity); - assert size == 0 - || (elements[head] != null && elements[tail()] != null); - assert size == capacity - || (elements[dec(head, capacity)] == null - && elements[inc(tail(), capacity)] == null); + // assert 0 <= head && head < capacity; + // assert 0 <= tail && tail < capacity; + // assert capacity > 0; + // assert size() < capacity; + // assert head == tail || elements[head] != null; + // assert elements[tail] == null; + // assert head == tail || elements[dec(tail, capacity)] != null; } catch (Throwable t) { - System.err.printf("head=%d size=%d capacity=%d%n", - head, size, elements.length); + System.err.printf("head=%d tail=%d capacity=%d%n", + head, tail, elements.length); System.err.printf("elements=%s%n", Arrays.toString(elements)); throw t;