--- jsr166/src/main/java/util/ArrayDeque.java 2016/10/24 23:40:56 1.89 +++ jsr166/src/main/java/util/ArrayDeque.java 2016/10/29 19:10:27 1.95 @@ -93,7 +93,7 @@ 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% int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1); @@ -115,8 +115,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"); @@ -184,15 +183,15 @@ public class ArrayDeque extends Abstr * @throws NullPointerException if the specified collection is null */ public ArrayDeque(Collection c) { - Object[] elements = c.toArray(); + Object[] es = 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) + if (es.getClass() != Object[].class) + es = Arrays.copyOf(es, es.length, Object[].class); + for (Object obj : es) Objects.requireNonNull(obj); - this.elements = elements; + this.elements = es; + this.size = es.length; } /** @@ -241,9 +240,10 @@ public class ArrayDeque extends Abstr /** * A version of elementAt that checks for null elements. * This check doesn't catch all possible comodifications, - * but does catch ones that corrupt traversal. + * but does catch ones that corrupt traversal. It's a little + * surprising that javac allows this abuse of generics. */ - E checkedElementAt(Object[] elements, int i) { + static final E nonNullElementAt(Object[] elements, int i) { @SuppressWarnings("unchecked") E e = (E) elements[i]; if (e == null) throw new ConcurrentModificationException(); @@ -263,15 +263,15 @@ public class ArrayDeque extends Abstr public void addFirst(E e) { // checkInvariants(); Objects.requireNonNull(e); - Object[] elements; + Object[] es; int capacity, h; final int s; - if ((s = size) == (capacity = (elements = this.elements).length)) { + if ((s = size) == (capacity = (es = elements).length)) { grow(1); - capacity = (elements = this.elements).length; + capacity = (es = elements).length; } if ((h = head - 1) < 0) h = capacity - 1; - elements[head = h] = e; + es[head = h] = e; size = s + 1; // checkInvariants(); } @@ -287,14 +287,14 @@ public class ArrayDeque extends Abstr public void addLast(E e) { // checkInvariants(); Objects.requireNonNull(e); - Object[] elements; + Object[] es; int capacity; final int s; - if ((s = size) == (capacity = (elements = this.elements).length)) { + if ((s = size) == (capacity = (es = elements).length)) { grow(1); - capacity = (elements = this.elements).length; + capacity = (es = elements).length; } - elements[add(head, s, capacity)] = e; + es[add(head, s, capacity)] = e; size = s + 1; // checkInvariants(); } @@ -368,7 +368,7 @@ public class ArrayDeque extends Abstr public E pollFirst() { // checkInvariants(); int s, h; - if ((s = size) == 0) + if ((s = size) <= 0) return null; final Object[] elements = this.elements; @SuppressWarnings("unchecked") E e = (E) elements[h = head]; @@ -382,7 +382,7 @@ public class ArrayDeque extends Abstr public E pollLast() { // checkInvariants(); final int s, tail; - if ((s = size) == 0) + if ((s = size) <= 0) return null; final Object[] elements = this.elements; @SuppressWarnings("unchecked") @@ -397,27 +397,34 @@ public class ArrayDeque extends Abstr */ public E getFirst() { // checkInvariants(); - if (size == 0) throw new NoSuchElementException(); + if (size <= 0) throw new NoSuchElementException(); return elementAt(head); } /** * @throws NoSuchElementException {@inheritDoc} */ + @SuppressWarnings("unchecked") public E getLast() { // checkInvariants(); - if (size == 0) throw new NoSuchElementException(); - return elementAt(tail()); + final int s; + if ((s = size) <= 0) throw new NoSuchElementException(); + final Object[] elements = this.elements; + return (E) elements[add(head, s - 1, elements.length)]; } public E peekFirst() { // checkInvariants(); - return (size == 0) ? null : elementAt(head); + return (size <= 0) ? null : elementAt(head); } + @SuppressWarnings("unchecked") public E peekLast() { // checkInvariants(); - return (size == 0) ? null : elementAt(tail()); + final int s; + if ((s = size) <= 0) return null; + final Object[] elements = this.elements; + return (E) elements[add(head, s - 1, elements.length)]; } /** @@ -436,16 +443,16 @@ public class ArrayDeque extends Abstr if (o != null) { final Object[] elements = this.elements; final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) + int i, end, to, todo; + todo = (end = (i = head) + size) - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) + for (;; to = todo, i = 0, todo = 0) { + for (; i < to; i++) if (o.equals(elements[i])) { delete(i); return true; } - if (leftover == 0) break; + if (todo == 0) break; } } return false; @@ -467,15 +474,15 @@ public class ArrayDeque extends Abstr 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--) + int i, to, end, todo; + todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end; + for (;; to = (i = capacity - 1) - todo, todo = 0) { + for (; i > to; i--) if (o.equals(elements[i])) { delete(i); return true; } - if (leftover == 0) break; + if (todo == 0) break; } } return false; @@ -701,10 +708,10 @@ 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); + E e = nonNullElementAt(elements, cursor); lastRet = cursor; if (++cursor >= elements.length) cursor = 0; remaining--; @@ -724,7 +731,7 @@ public class ArrayDeque extends Abstr } public void forEachRemaining(Consumer action) { - int k; + final int k; if ((k = remaining) > 0) { remaining = 0; ArrayDeque.forEachRemaining(action, elements, cursor, k); @@ -738,10 +745,10 @@ public class ArrayDeque extends Abstr DescendingIterator() { cursor = tail(); } public final E next() { - if (remaining == 0) + if (remaining <= 0) throw new NoSuchElementException(); final Object[] elements = ArrayDeque.this.elements; - E e = checkedElementAt(elements, cursor); + E e = nonNullElementAt(elements, cursor); lastRet = cursor; if (--cursor < 0) cursor = elements.length - 1; remaining--; @@ -754,7 +761,7 @@ public class ArrayDeque extends Abstr } public final void forEachRemaining(Consumer action) { - int k; + final int k; if ((k = remaining) > 0) { remaining = 0; forEachRemainingDescending(action, elements, cursor, k); @@ -817,18 +824,19 @@ public class ArrayDeque extends Abstr } public void forEachRemaining(Consumer action) { - int k = remaining(); // side effect! + final int k = remaining(); // side effect! remaining = 0; ArrayDeque.forEachRemaining(action, elements, cursor, k); } public boolean tryAdvance(Consumer action) { Objects.requireNonNull(action); - if (remaining() == 0) + final int k; + if ((k = remaining()) <= 0) return false; - action.accept(checkedElementAt(elements, cursor)); + action.accept(nonNullElementAt(elements, cursor)); if (++cursor >= elements.length) cursor = 0; - remaining--; + remaining = k - 1; return true; } @@ -849,53 +857,46 @@ public class ArrayDeque extends Abstr Objects.requireNonNull(action); final Object[] elements = this.elements; final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) + int i, end, to, todo; + todo = (end = (i = head) + size) - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) + for (;; to = todo, i = 0, todo = 0) { + for (; i < to; i++) action.accept((E) elements[i]); - if (leftover == 0) break; + if (todo == 0) break; } // checkInvariants(); } /** - * A variant of forEach that also checks for concurrent - * modification, for use in iterators. + * Calls action on remaining elements, starting at index i and + * traversing in ascending order. 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) { + Consumer action, Object[] elements, int i, int remaining) { Objects.requireNonNull(action); final int capacity = elements.length; - int end, to, leftover; - leftover = (end = from + size) + int end, to, todo; + todo = (end = i + remaining) - (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; + for (;; to = todo, i = 0, todo = 0) { + for (; i < to; i++) + action.accept(nonNullElementAt(elements, i)); + if (todo == 0) break; } } static void forEachRemainingDescending( - Consumer action, Object[] elements, int from, int size) { + Consumer action, Object[] elements, int i, int remaining) { 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); - } - if (leftover == 0) break; + int end, to, todo; + todo = (to = ((end = i - remaining) >= -1) ? end : -1) - end; + for (;; to = (i = capacity - 1) - todo, todo = 0) { + for (; i > to; i--) + action.accept(nonNullElementAt(elements, i)); + if (todo == 0) break; } } @@ -910,13 +911,13 @@ public class ArrayDeque extends Abstr Objects.requireNonNull(operator); final Object[] elements = this.elements; final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) + int i, end, to, todo; + todo = (end = (i = head) + size) - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) + for (;; to = todo, i = 0, todo = 0) { + for (; i < to; i++) elements[i] = operator.apply(elementAt(i)); - if (leftover == 0) break; + if (todo == 0) break; } // checkInvariants(); } @@ -991,14 +992,14 @@ public class ArrayDeque extends Abstr if (o != null) { final Object[] elements = this.elements; final int capacity = elements.length; - int from, end, to, leftover; - leftover = (end = (from = head) + size) + int i, end, to, todo; + todo = (end = (i = head) + size) - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) + for (;; to = todo, i = 0, todo = 0) { + for (; i < to; i++) if (o.equals(elements[i])) return true; - if (leftover == 0) break; + if (todo == 0) break; } } return false; @@ -1032,12 +1033,12 @@ public class ArrayDeque extends Abstr } /** - * Nulls out size elements, starting at head. + * Nulls out count elements, starting at array index from. */ - private static void clearSlice(Object[] elements, int head, int size) { - final int capacity = elements.length, end = head + size; + private static void clearSlice(Object[] elements, int from, int count) { + final int capacity = elements.length, end = from + count; final int leg = (capacity - end >= 0) ? end : capacity; - Arrays.fill(elements, head, leg, null); + Arrays.fill(elements, from, leg, null); if (leg != end) Arrays.fill(elements, 0, end - capacity, null); } @@ -1168,13 +1169,13 @@ public class ArrayDeque extends Abstr // 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) + int i, end, to, todo; + todo = (end = (i = head) + size) - (to = (capacity - end >= 0) ? end : capacity); - for (;; from = 0, to = leftover, leftover = 0) { - for (int i = from; i < to; i++) + for (;; to = todo, i = 0, todo = 0) { + for (; i < to; i++) s.writeObject(elements[i]); - if (leftover == 0) break; + if (todo == 0) break; } }