--- jsr166/src/main/java/util/ArrayDeque.java 2013/05/02 06:02:17 1.55 +++ jsr166/src/main/java/util/ArrayDeque.java 2016/11/13 02:10:09 1.113 @@ -4,9 +4,11 @@ */ package java.util; + import java.io.Serializable; import java.util.function.Consumer; -import java.util.stream.Stream; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; /** * Resizable-array implementation of the {@link Deque} interface. Array @@ -52,28 +54,35 @@ import java.util.stream.Stream; * Java Collections Framework. * * @author Josh Bloch and Doug Lea + * @param the type of elements held in this deque * @since 1.6 - * @param the type of elements held in this collection */ 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. + */ + /** * The array in which the elements of the deque are stored. - * The capacity of the deque is the length of this array, which is - * always a power of two. The array is never allowed to become - * full, except transiently within an addX method where it is - * resized (see doubleCapacity) immediately upon becoming full, - * thus avoiding head and tail wrapping around to equal each - * other. We also guarantee that all array cells not holding - * deque elements are always null. + * We guarantee that all array cells not holding deque elements + * are always null. */ - transient Object[] elements; // non-private to simplify nested class access + 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 equal to tail if the deque is empty. + * arbitrary number 0 <= head < elements.length equal to tail if + * the deque is empty. */ transient int head; @@ -84,55 +93,83 @@ public class ArrayDeque extends Abstr transient int tail; /** - * The minimum capacity that we'll use for a newly created deque. - * Must be a power of 2. + * The maximum size of array to allocate. + * Some VMs reserve some header words in an array. + * Attempts to allocate larger arrays may result in + * OutOfMemoryError: Requested array size exceeds VM limit */ - private static final int MIN_INITIAL_CAPACITY = 8; + private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; - // ****** Array allocation and resizing utilities ****** + /** + * Increases the capacity of this deque by at least the given amount. + * + * @param needed the required minimum extra capacity; must be positive + */ + private void grow(int needed) { + // overflow-conscious code + final int oldCapacity = elements.length; + int newCapacity; + // 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); + // Exceptionally, here tail == head needs to be disambiguated + if (tail < head || (tail == head && elements[head] != null)) { + // wrap around; slide first leg forward to end of array + int newSpace = newCapacity - oldCapacity; + System.arraycopy(elements, head, + elements, head + newSpace, + oldCapacity - head); + Arrays.fill(elements, head, head + newSpace, null); + head += newSpace; + } + // checkInvariants(); + } + + /** Capacity calculation for edge conditions, especially overflow. */ + private int newCapacity(int needed, int jump) { + final int oldCapacity = elements.length, minCapacity; + if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) { + if (minCapacity < 0) + throw new IllegalStateException("Sorry, deque too big"); + return Integer.MAX_VALUE; + } + if (needed > jump) + return minCapacity; + return (oldCapacity + jump - MAX_ARRAY_SIZE < 0) + ? oldCapacity + jump + : MAX_ARRAY_SIZE; + } /** - * Allocates empty array to hold the given number of elements. - * - * @param numElements the number of elements to hold - */ - private void allocateElements(int numElements) { - int initialCapacity = MIN_INITIAL_CAPACITY; - // Find the best power of two to hold elements. - // Tests "<=" because arrays aren't kept full. - if (numElements >= initialCapacity) { - initialCapacity = numElements; - initialCapacity |= (initialCapacity >>> 1); - initialCapacity |= (initialCapacity >>> 2); - initialCapacity |= (initialCapacity >>> 4); - initialCapacity |= (initialCapacity >>> 8); - initialCapacity |= (initialCapacity >>> 16); - initialCapacity++; - - if (initialCapacity < 0) // Too many elements, must back off - initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements - } - elements = new Object[initialCapacity]; + * Increases the internal storage of this collection, if necessary, + * to ensure that it can hold at least the given number of elements. + * + * @param minCapacity the desired minimum capacity + * @since TBD + */ + /* public */ void ensureCapacity(int minCapacity) { + int needed; + if ((needed = (minCapacity + 1 - elements.length)) > 0) + grow(needed); + // checkInvariants(); } /** - * Doubles the capacity of this deque. Call only when full, i.e., - * when head and tail have wrapped around to become equal. - */ - private void doubleCapacity() { - assert head == tail; - int p = head; - int n = elements.length; - int r = n - p; // number of elements to the right of p - int newCapacity = n << 1; - if (newCapacity < 0) - throw new IllegalStateException("Sorry, deque too big"); - Object[] a = new Object[newCapacity]; - System.arraycopy(elements, p, a, 0, r); - System.arraycopy(elements, 0, a, r, p); - elements = a; - head = 0; - tail = n; + * Minimizes the internal storage of this collection. + * + * @since TBD + */ + /* public */ void trimToSize() { + int size; + if ((size = size()) + 1 < elements.length) { + elements = toArray(new Object[size + 1]); + head = 0; + tail = size; + } + // checkInvariants(); } /** @@ -147,10 +184,10 @@ public class ArrayDeque extends Abstr * Constructs an empty array deque with an initial capacity * sufficient to hold the specified number of elements. * - * @param numElements lower bound on initial capacity of the deque + * @param numElements lower bound on initial capacity of the deque */ public ArrayDeque(int numElements) { - allocateElements(numElements); + elements = new Object[Math.max(1, numElements + 1)]; } /** @@ -164,10 +201,69 @@ public class ArrayDeque extends Abstr * @throws NullPointerException if the specified collection is null */ public ArrayDeque(Collection c) { - allocateElements(c.size()); + elements = new Object[c.size() + 1]; addAll(c); } + /** + * Increments i, mod modulus. + * Precondition and postcondition: 0 <= i < modulus. + */ + static final int inc(int i, int modulus) { + if (++i >= modulus) i = 0; + return i; + } + + /** + * Decrements i, mod modulus. + * Precondition and postcondition: 0 <= i < modulus. + */ + static final int dec(int i, int modulus) { + if (--i < 0) i = modulus - 1; + return i; + } + + /** + * Adds i and j, mod modulus. + * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus. + */ + static final int add(int i, int j, int modulus) { + if ((i += j) - 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. + */ + 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") + static final E elementAt(Object[] es, int i) { + return (E) es[i]; + } + + /** + * A version of elementAt that checks for null elements. + * This check doesn't catch all possible comodifications, + * but does catch ones that corrupt traversal. + */ + static final E nonNullElementAt(Object[] es, int i) { + @SuppressWarnings("unchecked") E e = (E) es[i]; + if (e == null) + throw new ConcurrentModificationException(); + return e; + } + // The main insertion and extraction methods are addFirst, // addLast, pollFirst, pollLast. The other methods are defined in // terms of these. @@ -181,9 +277,11 @@ public class ArrayDeque extends Abstr public void addFirst(E e) { if (e == null) throw new NullPointerException(); - elements[head = (head - 1) & (elements.length - 1)] = e; + final Object[] es = elements; + es[head = dec(head, es.length)] = e; if (head == tail) - doubleCapacity(); + grow(1); + // checkInvariants(); } /** @@ -197,9 +295,31 @@ public class ArrayDeque extends Abstr public void addLast(E e) { if (e == null) throw new NullPointerException(); - elements[tail] = e; - if ( (tail = (tail + 1) & (elements.length - 1)) == head) - doubleCapacity(); + final Object[] es = elements; + es[tail] = e; + if (head == (tail = inc(tail, es.length))) + grow(1); + // checkInvariants(); + } + + /** + * 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. + * + * @param c the elements to be inserted into this deque + * @return {@code true} if this deque changed as a result of the call + * @throws NullPointerException if the specified collection or any + * of its elements are null + */ + public boolean addAll(Collection c) { + final int s = size(), needed; + if ((needed = s + c.size() - elements.length + 1) > 0) + grow(needed); + c.forEach(e -> addLast(e)); + // checkInvariants(); + return size() > s; } /** @@ -230,76 +350,78 @@ public class ArrayDeque extends Abstr * @throws NoSuchElementException {@inheritDoc} */ public E removeFirst() { - 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() { - E x = pollLast(); - if (x == null) + E e = pollLast(); + if (e == null) throw new NoSuchElementException(); - return x; + // checkInvariants(); + return e; } public E pollFirst() { - int h = head; - @SuppressWarnings("unchecked") - E result = (E) elements[h]; - // Element is null if deque empty - if (result == null) - return null; - elements[h] = null; // Must null out slot - head = (h + 1) & (elements.length - 1); - return result; + 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(); + return e; } public E pollLast() { - int t = (tail - 1) & (elements.length - 1); - @SuppressWarnings("unchecked") - E result = (E) elements[t]; - if (result == null) - return null; - elements[t] = null; - tail = t; - return result; + final Object[] es; + final int t; + E e = elementAt(es = elements, t = dec(tail, es.length)); + if (e != null) + es[tail = t] = null; + // checkInvariants(); + return e; } /** * @throws NoSuchElementException {@inheritDoc} */ public E getFirst() { - @SuppressWarnings("unchecked") - E result = (E) elements[head]; - if (result == null) + E e = elementAt(elements, head); + if (e == null) throw new NoSuchElementException(); - return result; + // checkInvariants(); + return e; } /** * @throws NoSuchElementException {@inheritDoc} */ public E getLast() { - @SuppressWarnings("unchecked") - E result = (E) elements[(tail - 1) & (elements.length - 1)]; - if (result == null) + final Object[] es = elements; + E e = elementAt(es, dec(tail, es.length)); + if (e == null) throw new NoSuchElementException(); - return result; + // checkInvariants(); + return e; } - @SuppressWarnings("unchecked") public E peekFirst() { - // elements[head] is null if deque empty - return (E) elements[head]; + // checkInvariants(); + return elementAt(elements, head); } - @SuppressWarnings("unchecked") public E peekLast() { - return (E) elements[(tail - 1) & (elements.length - 1)]; + // checkInvariants(); + final Object[] es; + return elementAt(es = elements, dec(tail, es.length)); } /** @@ -315,17 +437,17 @@ public class ArrayDeque extends Abstr * @return {@code true} if the deque contained the specified element */ public boolean removeFirstOccurrence(Object o) { - if (o == null) - return false; - int mask = elements.length - 1; - int i = head; - Object x; - while ( (x = elements[i]) != null) { - if (o.equals(x)) { - delete(i); - return true; + if (o != null) { + 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; } - i = (i + 1) & mask; } return false; } @@ -343,17 +465,17 @@ public class ArrayDeque extends Abstr * @return {@code true} if the deque contained the specified element */ public boolean removeLastOccurrence(Object o) { - if (o == null) - return false; - int mask = elements.length - 1; - int i = (tail - 1) & mask; - Object x; - while ( (x = elements[i]) != null) { - if (o.equals(x)) { - delete(i); - return true; + if (o != null) { + 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; } - i = (i - 1) & mask; } return false; } @@ -472,59 +594,50 @@ public class ArrayDeque extends Abstr return removeFirst(); } - private void checkInvariants() { - assert elements[tail] == null; - assert head == tail ? elements[head] == null : - (elements[head] != null && - elements[(tail - 1) & (elements.length - 1)] != null); - assert elements[(head - 1) & (elements.length - 1)] == null; - } - /** - * Removes the element at the specified position in the elements array, - * adjusting head and tail as necessary. This can result in motion of - * elements backwards or forwards in the array. + * Removes the element at the specified position in the elements array. + * This can result in forward or backwards motion of array elements. + * We optimize for least element motion. * *

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 */ - private boolean delete(int i) { - checkInvariants(); - final Object[] elements = this.elements; - final int mask = elements.length - 1; + boolean delete(int i) { + // checkInvariants(); + final Object[] es = elements; + final int capacity = es.length; final int h = head; - final int t = tail; - final int front = (i - h) & mask; - final int back = (t - i) & mask; - - // Invariant: head <= i < tail mod circularity - if (front >= ((t - h) & mask)) - throw new ConcurrentModificationException(); - - // Optimize for least element motion + // 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 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[mask]; - System.arraycopy(elements, h, elements, h + 1, mask - h); + 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; - head = (h + 1) & mask; + es[h] = null; + head = inc(h, capacity); + // checkInvariants(); return false; } else { - if (i < t) { // Copy the null tail as well - System.arraycopy(elements, i + 1, elements, i, back); - tail = t - 1; + // move back elements backwards + tail = dec(tail, capacity); + if (i <= tail) { + System.arraycopy(es, i + 1, es, i, back); } else { // Wrap around - System.arraycopy(elements, i + 1, elements, i, mask - i); - elements[mask] = elements[0]; - System.arraycopy(elements, 1, elements, 0, t); - tail = (t - 1) & mask; + int firstLeg = capacity - (i + 1); + System.arraycopy(es, i + 1, es, i, firstLeg); + es[capacity - 1] = es[0]; + System.arraycopy(es, 1, es, 0, back - firstLeg - 1); } + es[tail] = null; + // checkInvariants(); return true; } } @@ -537,7 +650,7 @@ public class ArrayDeque extends Abstr * @return the number of elements in this deque */ public int size() { - return (tail - head) & (elements.length - 1); + return sub(tail, head, elements.length); } /** @@ -566,87 +679,342 @@ public class ArrayDeque extends Abstr } private class DeqIterator implements Iterator { - /** - * Index of element to be returned by subsequent call to next. - */ - private int cursor = head; + /** Index of element to be returned by subsequent call to next. */ + int cursor; - /** - * Tail recorded at construction (also in remove), to stop - * iterator and also to check for comodification. - */ - private int fence = tail; + /** Number of elements yet to be returned. */ + int remaining = size(); /** * Index of element returned by most recent call to next. * Reset to -1 if element is deleted by a call to remove. */ - private int lastRet = -1; + int lastRet = -1; - public boolean hasNext() { - return cursor != fence; + DeqIterator() { cursor = head; } + + public final boolean hasNext() { + return remaining > 0; } public E next() { - if (cursor == fence) + if (remaining <= 0) throw new NoSuchElementException(); - @SuppressWarnings("unchecked") - E result = (E) elements[cursor]; - // This check doesn't catch all possible comodifications, - // but does catch the ones that corrupt traversal - if (tail != fence || result == null) - throw new ConcurrentModificationException(); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); lastRet = cursor; - cursor = (cursor + 1) & (elements.length - 1); - return result; + cursor = inc(cursor, es.length); + remaining--; + return e; + } + + void postDelete(boolean leftShifted) { + if (leftShifted) + cursor = dec(cursor, elements.length); } - public void remove() { + public final void remove() { if (lastRet < 0) throw new IllegalStateException(); - if (delete(lastRet)) { // if left-shifted, undo increment in next() - cursor = (cursor - 1) & (elements.length - 1); - fence = tail; - } + postDelete(delete(lastRet)); lastRet = -1; } + + public 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(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 = dec(tail, elements.length); } + + public final E next() { + if (remaining <= 0) + throw new NoSuchElementException(); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); + lastRet = cursor; + cursor = dec(cursor, es.length); + remaining--; + return e; + } + + 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; + } + } + } } /** - * This class is nearly a mirror-image of DeqIterator, using tail - * instead of head for initial cursor, and head instead of tail - * for fence. - */ - private class DescendingIterator implements Iterator { - private int cursor = tail; - private int fence = head; - private int lastRet = -1; + * Creates a late-binding + * and fail-fast {@link Spliterator} over the elements in this + * deque. + * + *

The {@code Spliterator} reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#NONNULL}. Overriding implementations should document + * the reporting of additional characteristic values. + * + * @return a {@code Spliterator} over the elements in this deque + * @since 1.8 + */ + public Spliterator spliterator() { + return new DeqSpliterator(); + } + + final class DeqSpliterator implements Spliterator { + private int fence; // -1 until first use + private int cursor; // current index, modified on traverse/split - public boolean hasNext() { - return cursor != fence; + /** Constructs late-binding spliterator over all elements. */ + DeqSpliterator() { + this.fence = -1; } - public E next() { - if (cursor == fence) - throw new NoSuchElementException(); - cursor = (cursor - 1) & (elements.length - 1); - @SuppressWarnings("unchecked") - E result = (E) elements[cursor]; - if (head != fence || result == null) - throw new ConcurrentModificationException(); - lastRet = cursor; - return result; + /** Constructs spliterator over the given range. */ + DeqSpliterator(int origin, int fence) { + this.cursor = origin; + this.fence = fence; } - public void remove() { - if (lastRet < 0) - throw new IllegalStateException(); - if (!delete(lastRet)) { - cursor = (cursor + 1) & (elements.length - 1); - fence = head; + /** Ensures late-binding initialization; then returns fence. */ + private int getFence() { // force initialization + int t; + if ((t = fence) < 0) { + t = fence = tail; + cursor = head; + } + return t; + } + + 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) { + 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) { + if (action == null) + throw new NullPointerException(); + int t, i; + if ((t = fence) < 0) t = getFence(); + if (t == (i = cursor)) + return false; + final Object[] es; + action.accept(nonNullElementAt(es = elements, i)); + cursor = inc(i, es.length); + return true; + } + + public long estimateSize() { + return sub(getFence(), cursor, elements.length); + } + + public int characteristics() { + return Spliterator.NONNULL + | Spliterator.ORDERED + | Spliterator.SIZED + | Spliterator.SUBSIZED; + } + } + + public void forEach(Consumer action) { + Objects.requireNonNull(action); + 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(); + } + + /** + * Replaces each element of this deque with the result of applying the + * operator to that element, as specified by {@link List#replaceAll}. + * + * @param operator the operator to apply to each element + * @since TBD + */ + /* public */ void replaceAll(UnaryOperator operator) { + Objects.requireNonNull(operator); + 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} + */ + public boolean removeIf(Predicate 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 filter) { + // checkInvariants(); + 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; } - lastRet = -1; } + if (end != tail) throw new ConcurrentModificationException(); + circularClear(es, tail = w, end); + // checkInvariants(); + return true; } /** @@ -658,15 +1026,15 @@ public class ArrayDeque extends Abstr * @return {@code true} if this deque contains the specified element */ public boolean contains(Object o) { - if (o == null) - return false; - int mask = elements.length - 1; - int i = head; - Object x; - while ( (x = elements[i]) != null) { - if (o.equals(x)) - return true; - i = (i + 1) & mask; + if (o != null) { + 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; } @@ -693,16 +1061,19 @@ public class ArrayDeque extends Abstr * The deque will be empty after this call returns. */ public void clear() { - int h = head; - int t = tail; - if (h != t) { // clear all cells - head = tail = 0; - int i = h; - int mask = elements.length - 1; - do { - elements[i] = null; - i = (i + 1) & mask; - } while (i != t); + circularClear(elements, head, tail); + head = tail = 0; + // checkInvariants(); + } + + /** + * Nulls out slots starting at array index i, upto index end. + */ + private static void circularClear(Object[] es, int i, int end) { + for (int to = (i <= end) ? end : es.length; + ; i = 0, to = end) { + Arrays.fill(es, i, to, null); + if (to == end) break; } } @@ -720,13 +1091,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 tail = this.tail; - boolean wrap = (tail < head); - int end = wrap ? tail + elements.length : tail; - Object[] a = Arrays.copyOfRange(elements, head, end); - if (wrap) - System.arraycopy(elements, 0, a, elements.length - head, tail); + return toArray(Object[].class); + } + + 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) { + a = Arrays.copyOfRange(es, head, end, klazz); + } else { + // integer overflow! + a = Arrays.copyOfRange(es, 0, size, klazz); + System.arraycopy(es, head, a, 0, len); + } + if (tail < head) + System.arraycopy(es, 0, a, len, tail); return a; } @@ -752,7 +1133,7 @@ public class ArrayDeque extends Abstr * The following code can be used to dump the deque into a newly * allocated array of {@code String}: * - * 

 {@code String[] y = x.toArray(new String[0]);}
+ * 
 {@code String[] y = x.toArray(new String[0]);}
* * Note that {@code toArray(new Object[0])} is identical in function to * {@code toArray()}. @@ -768,22 +1149,17 @@ public class ArrayDeque extends Abstr */ @SuppressWarnings("unchecked") public T[] toArray(T[] a) { - final int head = this.head; - final int tail = this.tail; - boolean wrap = (tail < head); - int size = (tail - head) + (wrap ? elements.length : 0); - int firstLeg = size - (wrap ? tail : 0); - int len = a.length; - if (size > len) { - a = (T[]) Arrays.copyOfRange(elements, head, head + size, - a.getClass()); - } else { - System.arraycopy(elements, head, a, 0, firstLeg); - if (size < len) - 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, tail); + if (size < a.length) + a[size] = null; return a; } @@ -810,6 +1186,8 @@ public class ArrayDeque extends Abstr /** * Saves this deque to a stream (that is, serializes it). * + * @param s the stream + * @throws java.io.IOException if an I/O error occurs * @serialData The current size ({@code int}) of the deque, * followed by all of its elements (each an object reference) in * first-to-last order. @@ -822,13 +1200,21 @@ public class ArrayDeque extends Abstr s.writeInt(size()); // Write out elements in order. - int mask = elements.length - 1; - for (int i = head; i != tail; i = (i + 1) & mask) - 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; + } } /** * Reconstitutes this deque 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 { @@ -836,93 +1222,31 @@ public class ArrayDeque extends Abstr // Read in size and allocate array int size = s.readInt(); - allocateElements(size); - head = 0; - tail = size; + elements = new Object[size + 1]; + this.tail = size; // Read in all elements in the proper order. for (int i = 0; i < size; i++) elements[i] = s.readObject(); } - public Spliterator spliterator() { - return new DeqSpliterator(this, -1, -1); - } - - static final class DeqSpliterator implements Spliterator { - private final ArrayDeque deq; - private int fence; // -1 until first use - private int index; // current index, modified on traverse/split - - /** Creates new spliterator covering the given array and range */ - DeqSpliterator(ArrayDeque deq, int origin, int fence) { - this.deq = deq; - this.index = origin; - this.fence = fence; - } - - private int getFence() { // force initialization - int t; - if ((t = fence) < 0) { - t = fence = deq.tail; - index = deq.head; - } - return t; - } - - public Spliterator trySplit() { - int t = getFence(), h = index, n = deq.elements.length; - if (h != t && ((h + 1) & (n - 1)) != t) { - if (h > t) - t += n; - int m = ((h + t) >>> 1) & (n - 1); - return new DeqSpliterator<>(deq, h, index = m); - } - return null; - } - - public void forEachRemaining(Consumer consumer) { - if (consumer == null) - throw new NullPointerException(); - Object[] a = deq.elements; - int m = a.length - 1, f = getFence(), i = index; - index = f; - while (i != f) { - @SuppressWarnings("unchecked") E e = (E)a[i]; - i = (i + 1) & m; - if (e == null) - throw new ConcurrentModificationException(); - consumer.accept(e); - } - } - - public boolean tryAdvance(Consumer consumer) { - if (consumer == null) - throw new NullPointerException(); - Object[] a = deq.elements; - int m = a.length - 1, f = getFence(), i = index; - if (i != fence) { - @SuppressWarnings("unchecked") E e = (E)a[i]; - index = (i + 1) & m; - if (e == null) - throw new ConcurrentModificationException(); - consumer.accept(e); - return true; - } - return false; - } - - public long estimateSize() { - int n = getFence() - index; - if (n < 0) - n += deq.elements.length; - return (long) n; - } - - @Override - public int characteristics() { - return Spliterator.ORDERED | Spliterator.SIZED | - Spliterator.NONNULL | Spliterator.SUBSIZED; + /** debugging */ + void checkInvariants() { + try { + int capacity = elements.length; + // assert head >= 0 && head < capacity; + // assert tail >= 0 && 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 tail=%d capacity=%d%n", + head, tail, elements.length); + System.err.printf("elements=%s%n", + Arrays.toString(elements)); + throw t; } }