--- jsr166/src/main/java/util/ArrayDeque.java 2016/10/24 23:40:56 1.89 +++ 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"); @@ -137,8 +151,9 @@ public class ArrayDeque extends Abstr * @since TBD */ /* public */ void ensureCapacity(int minCapacity) { - if (minCapacity > elements.length) - grow(minCapacity - elements.length); + int needed; + if ((needed = (minCapacity + 1 - elements.length)) > 0) + grow(needed); // checkInvariants(); } @@ -148,9 +163,11 @@ public class ArrayDeque extends Abstr * @since TBD */ /* public */ void trimToSize() { - if (size < elements.length) { - elements = toArray(); + int size; + if ((size = size()) + 1 < elements.length) { + elements = toArray(new Object[size + 1]); head = 0; + tail = size; } // checkInvariants(); } @@ -170,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)]; } /** @@ -184,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) - size = elements.length; - if (elements.getClass() != Object[].class) - elements = Arrays.copyOf(elements, size, Object[].class); - for (Object obj : elements) - Objects.requireNonNull(obj); - this.elements = elements; + elements = new Object[c.size() + 1]; + addAll(c); } /** @@ -223,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") - private E elementAt(int i) { - return (E) elements[i]; + static final E elementAt(Object[] es, int i) { + return (E) es[i]; } /** @@ -243,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; @@ -261,18 +275,12 @@ 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, h; - final int s; - if ((s = size) == (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); - capacity = (elements = this.elements).length; - } - if ((h = head - 1) < 0) h = capacity - 1; - elements[head = h] = e; - size = s + 1; // checkInvariants(); } @@ -285,17 +293,12 @@ 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; - final int s; - if ((s = size) == (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); - capacity = (elements = this.elements).length; - } - elements[add(head, s, capacity)] = e; - size = s + 1; // checkInvariants(); } @@ -311,12 +314,12 @@ public class ArrayDeque extends Abstr * of its elements are null */ public boolean addAll(Collection c) { - final int s = size, needed = c.size() - (elements.length - s); - if (needed > 0) + 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; + return size() > s; } /** @@ -347,10 +350,10 @@ public class ArrayDeque extends Abstr * @throws NoSuchElementException {@inheritDoc} */ public E removeFirst() { - // checkInvariants(); E e = pollFirst(); if (e == null) throw new NoSuchElementException(); + // checkInvariants(); return e; } @@ -358,37 +361,32 @@ public class ArrayDeque extends Abstr * @throws NoSuchElementException {@inheritDoc} */ public E removeLast() { - // checkInvariants(); E e = pollLast(); if (e == null) throw new NoSuchElementException(); + // 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(); - 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; - if (++h >= elements.length) h = 0; - head = h; - 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 +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)); } /** @@ -434,18 +438,15 @@ public class ArrayDeque extends Abstr */ public boolean removeFirstOccurrence(Object o) { if (o != null) { - final Object[] elements = this.elements; - final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) - - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) - if (o.equals(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++) + if (o.equals(es[i])) { delete(i); return true; } - if (leftover == 0) break; + if (to == end) break; } } return false; @@ -465,17 +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; - int from, to, end, leftover; - leftover = (to = ((end = (from = tail()) - size) >= -1) ? end : -1) - end; - for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) { - for (int i = from; i > to; i--) - if (o.equals(elements[i])) { + 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 (leftover == 0) break; + if (to == end) break; } } return false; @@ -603,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; - if ((head = (h + 1)) >= capacity) head = 0; - size--; + es[h] = null; + head = inc(h, capacity); // 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; } @@ -653,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); } /** @@ -662,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; } /** @@ -686,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. @@ -701,19 +698,19 @@ public class ArrayDeque extends Abstr } public E next() { - if (remaining == 0) + if (remaining <= 0) throw new NoSuchElementException(); - final Object[] elements = ArrayDeque.this.elements; - E e = checkedElementAt(elements, cursor); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); lastRet = cursor; - if (++cursor >= elements.length) cursor = 0; + cursor = inc(cursor, es.length); remaining--; return e; } void postDelete(boolean leftShifted) { if (leftShifted) - if (--cursor < 0) cursor = elements.length - 1; + cursor = dec(cursor, elements.length); } public final void remove() { @@ -724,42 +721,66 @@ public class ArrayDeque extends Abstr } public void forEachRemaining(Consumer action) { - int k; - if ((k = remaining) > 0) { - remaining = 0; - ArrayDeque.forEachRemaining(action, elements, cursor, k); - if ((lastRet = cursor + k - 1) >= elements.length) - lastRet -= elements.length; + 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 = tail(); } + DescendingIterator() { cursor = dec(tail, elements.length); } public final E next() { - if (remaining == 0) + if (remaining <= 0) throw new NoSuchElementException(); - final Object[] elements = ArrayDeque.this.elements; - E e = checkedElementAt(elements, cursor); + final Object[] es = elements; + E e = nonNullElementAt(es, cursor); lastRet = cursor; - if (--cursor < 0) cursor = elements.length - 1; + cursor = dec(cursor, es.length); remaining--; return e; } void postDelete(boolean leftShifted) { if (!leftShifted) - if (++cursor >= elements.length) cursor = 0; + cursor = inc(cursor, elements.length); } public final void forEachRemaining(Consumer action) { - int k; - if ((k = remaining) > 0) { - remaining = 0; - forEachRemainingDescending(action, elements, cursor, k); - if ((lastRet = cursor - (k - 1)) < 0) - lastRet += elements.length; + 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; + } } } } @@ -778,62 +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) { - int k = remaining(); // side effect! - remaining = 0; - ArrayDeque.forEachRemaining(action, elements, cursor, k); + 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)); - if (++cursor >= elements.length) cursor = 0; - 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() { @@ -844,59 +879,19 @@ public class ArrayDeque extends Abstr } } - @SuppressWarnings("unchecked") public void forEach(Consumer action) { Objects.requireNonNull(action); - final Object[] elements = this.elements; - final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) - - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) - action.accept((E) elements[i]); - if (leftover == 0) break; - } - // checkInvariants(); - } - - /** - * A variant of forEach that also checks for concurrent - * modification, for use in iterators. - */ - static void forEachRemaining( - Consumer action, Object[] elements, int from, int size) { - Objects.requireNonNull(action); - final int capacity = elements.length; - int end, to, leftover; - leftover = (end = from + size) - - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) { - @SuppressWarnings("unchecked") E e = (E) elements[i]; - if (e == null) - throw new ConcurrentModificationException(); - action.accept(e); - } - if (leftover == 0) break; - } - } - - static void forEachRemainingDescending( - Consumer action, Object[] elements, int from, int size) { - Objects.requireNonNull(action); - final int capacity = elements.length; - int end, to, leftover; - leftover = (to = ((end = from - size) >= -1) ? end : -1) - end; - for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) { - for (int i = from; i > to; i--) { - @SuppressWarnings("unchecked") E e = (E) elements[i]; - if (e == null) - throw new ConcurrentModificationException(); - action.accept(e); + 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; } - if (leftover == 0) break; } + // checkInvariants(); } /** @@ -908,15 +903,15 @@ public class ArrayDeque extends Abstr */ /* public */ void replaceAll(UnaryOperator operator) { Objects.requireNonNull(operator); - final Object[] elements = this.elements; - final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) - - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) - elements[i] = operator.apply(elementAt(i)); - if (leftover == 0) break; + 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(); } @@ -948,33 +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--) { - @SuppressWarnings("unchecked") E e = (E) elements[i]; - if (filter.test(e)) - deleted++; - else { - if (j != i) - elements[j] = e; - if (++j >= capacity) j = 0; + 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; } - if (++i >= capacity) i = 0; } - return deleted > 0; + return true; } catch (Throwable ex) { - if (deleted > 0) - for (; remaining > 0; remaining--) { - elements[j] = elements[i]; - if (++i >= capacity) i = 0; - if (++j >= capacity) j = 0; - } + // copy remaining elements + for (; i != end; i = inc(i, capacity), j = inc(j, capacity)) + es[j] = es[i]; throw ex; } finally { - size -= deleted; - clearSlice(elements, j, deleted); + if (end != tail) throw new ConcurrentModificationException(); + circularClear(es, tail = j, end); // checkInvariants(); } } @@ -989,16 +1009,13 @@ public class ArrayDeque extends Abstr */ public boolean contains(Object o) { if (o != null) { - final Object[] elements = this.elements; - final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) - - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) - if (o.equals(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++) + if (o.equals(es[i])) return true; - if (leftover == 0) break; + if (to == end) break; } } return false; @@ -1026,20 +1043,20 @@ public class ArrayDeque extends Abstr * The deque will be empty after this call returns. */ public void clear() { - clearSlice(elements, head, size); - size = head = 0; + circularClear(elements, head, tail); + head = tail = 0; // checkInvariants(); } /** - * Nulls out size elements, starting at head. + * Nulls out slots starting at array index i, upto index end. */ - private static void clearSlice(Object[] elements, int head, int size) { - final int capacity = elements.length, end = head + size; - final int leg = (capacity - end >= 0) ? end : capacity; - Arrays.fill(elements, head, leg, null); - if (leg != end) - Arrays.fill(elements, 0, end - capacity, null); + 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; + } } /** @@ -1060,19 +1077,19 @@ public class ArrayDeque extends Abstr } private T[] toArray(Class klazz) { - final Object[] elements = this.elements; - final int capacity = elements.length; - final int head = this.head, end = head + size; + final Object[] es = elements; final T[] a; - if (end >= 0) { - a = Arrays.copyOfRange(elements, head, end, klazz); + 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(elements, 0, size, klazz); - System.arraycopy(elements, head, a, 0, capacity - head); + a = Arrays.copyOfRange(es, 0, size, klazz); + System.arraycopy(es, head, a, 0, len); } - if (end - capacity > 0) - System.arraycopy(elements, 0, a, capacity - head, end - capacity); + if (tail < head) + System.arraycopy(es, 0, a, len, tail); return a; } @@ -1114,16 +1131,15 @@ public class ArrayDeque extends Abstr */ @SuppressWarnings("unchecked") public T[] toArray(T[] a) { - final int size = this.size; - if (size > a.length) + final int size; + if ((size = size()) > a.length) return toArray((Class) a.getClass()); - final Object[] elements = this.elements; - final int capacity = elements.length; - final int head = this.head, end = head + size; - final int front = (capacity - end >= 0) ? size : capacity - head; - System.arraycopy(elements, head, a, 0, front); - if (front != size) - System.arraycopy(elements, 0, a, capacity - head, end - capacity); + 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 (size < a.length) a[size] = null; return a; @@ -1163,18 +1179,15 @@ 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; - int from, end, to, leftover; - leftover = (end = (from = head) + size) - - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) - s.writeObject(elements[i]); - if (leftover == 0) break; + 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; } } @@ -1190,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++) @@ -1201,16 +1216,16 @@ public class ArrayDeque extends Abstr void checkInvariants() { try { int capacity = elements.length; - // assert size >= 0 && size <= capacity; - // assert head >= 0; - // assert capacity == 0 || head < capacity; - // assert size == 0 || elements[head] != null; - // assert size == 0 || elements[tail()] != null; - // assert size == capacity || elements[dec(head, capacity)] == null; - // assert size == capacity || 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;