--- jsr166/src/main/java/util/ArrayDeque.java 2016/10/18 20:32:55 1.79 +++ jsr166/src/main/java/util/ArrayDeque.java 2016/11/05 16:21:06 1.109 @@ -60,6 +60,17 @@ 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. + */ + /** * The array in which the elements of the deque are stored. * We guarantee that all array cells not holding deque elements @@ -70,12 +81,16 @@ public class ArrayDeque extends Abstr /** * 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)). + */ + transient int tail; /** * The maximum size of array to allocate. @@ -92,16 +107,16 @@ 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) { + // 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, @@ -115,8 +130,7 @@ public class ArrayDeque extends Abstr /** 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,20 +148,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 TBD */ - /* TODO: public */ private 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 TBD */ - /* TODO: public */ private 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(); } @@ -167,7 +187,7 @@ 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[Math.max(1, numElements + 1)]; } /** @@ -181,15 +201,8 @@ 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; + elements = new Object[c.size() + 1]; + addAll(c); } /** @@ -197,7 +210,7 @@ public class ArrayDeque extends Abstr * Precondition and postcondition: 0 <= i < modulus. */ static final int inc(int i, int modulus) { - if (++i == modulus) i = 0; + if (++i >= modulus) i = 0; return i; } @@ -206,7 +219,7 @@ public class ArrayDeque extends Abstr * Precondition and postcondition: 0 <= i < modulus. */ static final int dec(int i, int modulus) { - if (--i < 0) i += modulus; + if (--i < 0) i = modulus - 1; return i; } @@ -220,19 +233,23 @@ public class ArrayDeque extends Abstr } /** - * Returns the array index of the last element. - * May return invalid index -1 if there are no elements. + * 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. */ - final int tail() { - return add(head, size - 1, elements.length); + 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]; } /** @@ -240,8 +257,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; @@ -258,14 +275,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(); } /** @@ -277,14 +293,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(); } /** @@ -298,23 +313,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 = size(), needed; + if ((needed = s + c.size() - elements.length + 1) > 0) + grow(needed); + c.forEach((e) -> addLast(e)); // checkInvariants(); - Object[] a, elements; - int newcomers, capacity, s = size; - if ((newcomers = (a = c.toArray()).length) == 0) - return false; - while ((capacity = (elements = this.elements).length) - s < newcomers) - grow(newcomers - (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; } /** @@ -345,47 +350,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; } @@ -393,28 +394,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)); } /** @@ -430,15 +437,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; @@ -458,14 +466,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) { + while (--i >= to) + if (o.equals(es[i])) { + delete(i); + return true; + } + if (to == end) break; } } return false; @@ -593,43 +602,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 Object[] es = elements; + final int capacity = es.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 + // 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[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(tail, 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, firstLeg); + es[capacity - 1] = es[0]; + System.arraycopy(es, 1, es, 0, back - firstLeg - 1); } - elements[tail] = null; - size--; + es[tail] = null; // checkInvariants(); return true; } @@ -643,7 +650,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); } /** @@ -652,7 +659,7 @@ public class ArrayDeque extends Abstr * @return {@code true} if this deque contains no elements */ public boolean isEmpty() { - return size == 0; + return head == tail; } /** @@ -676,7 +683,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. @@ -686,60 +693,96 @@ 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); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); lastRet = cursor; - cursor = advance(cursor, elements.length); + cursor = inc(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); + lastRet = cursor; + cursor = dec(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) { + for (; i >= to; i--) + action.accept(elementAt(es, i)); + if (to == end) { + if (end != head) + throw new ConcurrentModificationException(); + lastRet = head; + break; + } + } + } } /** @@ -756,66 +799,76 @@ 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; + /** Constructs spliterator over the given range. */ + DeqSpliterator(int origin, int fence) { + this.cursor = origin; + this.fence = fence; } - /** Ensures late-binding initialization; then returns remaining. */ - private int remaining() { - if (remaining < 0) { + /** 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) + if (action == null) + throw new NullPointerException(); + int t, i; + if ((t = fence) < 0) t = getFence(); + if (t == (i = cursor)) return false; - action.accept(checkedElementAt(elements, cursor)); - cursor = inc(cursor, elements.length); - remaining--; + final Object[] es; + action.accept(nonNullElementAt(es = elements, i)); + cursor = inc(i, es.length); return true; } public long estimateSize() { - return remaining(); + return sub(getFence(), cursor, elements.length); } public int characteristics() { @@ -826,14 +879,18 @@ public class ArrayDeque extends Abstr } } - @Override 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(); } @@ -842,20 +899,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 TBD */ - /* TODO: public */ private 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); @@ -864,7 +927,6 @@ public class ArrayDeque extends Abstr /** * @throws NullPointerException {@inheritDoc} */ - @Override public boolean removeAll(Collection c) { Objects.requireNonNull(c); return bulkRemove(e -> c.contains(e)); @@ -873,7 +935,6 @@ public class ArrayDeque extends Abstr /** * @throws NullPointerException {@inheritDoc} */ - @Override public boolean retainAll(Collection c) { Objects.requireNonNull(c); return bulkRemove(e -> !c.contains(e)); @@ -882,31 +943,58 @@ 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; + 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, to); + if (to == end) { + if (end != tail) throw new ConcurrentModificationException(); + break; + } + } + return false; + } + + /** + * Helper for bulkRemove, in case of at least one deletion. + * @param i valid index of first element to be deleted + */ + private boolean bulkRemoveModified( + Predicate filter, int i, int to) { + 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 (; 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); + 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; } } - return deleted > 0; + return true; } catch (Throwable ex) { - if (deleted > 0) - for (; remaining > 0; - remaining--, i = inc(i, capacity), j = inc(j, capacity)) - elements[j] = elements[i]; + // copy remaining elements + for (; i != end; i = inc(i, capacity), j = inc(j, capacity)) + es[j] = es[i]; throw ex; } finally { - size -= deleted; - for (; --deleted >= 0; j = inc(j, capacity)) - elements[j] = null; + if (end != tail) throw new ConcurrentModificationException(); + circularClear(es, tail = j, end); // checkInvariants(); } } @@ -921,11 +1009,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; } @@ -952,21 +1043,23 @@ 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. + */ + 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; + } + } + + /** * Returns an array containing all of the elements in this deque * in proper sequence (from first to last element). * @@ -980,11 +1073,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 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; } @@ -1026,20 +1131,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; } @@ -1077,13 +1179,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; + } } /** @@ -1098,7 +1203,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++) @@ -1106,20 +1213,19 @@ public class ArrayDeque extends Abstr } /** debugging */ - private void checkInvariants() { + void checkInvariants() { 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 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 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;