ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayDeque.java
(Generate patch)

Comparing jsr166/src/main/java/util/ArrayDeque.java (file contents):
Revision 1.116 by jsr166, Fri Nov 18 16:45:26 2016 UTC vs.
Revision 1.134 by jsr166, Sat Jun 30 22:35:55 2018 UTC

# Line 9 | Line 9 | import java.io.Serializable;
9   import java.util.function.Consumer;
10   import java.util.function.Predicate;
11   import java.util.function.UnaryOperator;
12 + import jdk.internal.misc.SharedSecrets;
13  
14   /**
15   * Resizable-array implementation of the {@link Deque} interface.  Array
# Line 50 | Line 51 | import java.util.function.UnaryOperator;
51   * Iterator} interfaces.
52   *
53   * <p>This class is a member of the
54 < * <a href="{@docRoot}/../technotes/guides/collections/index.html">
54 > * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
55   * Java Collections Framework</a>.
56   *
57   * @author  Josh Bloch and Doug Lea
# Line 117 | Line 118 | public class ArrayDeque<E> extends Abstr
118          if (jump < needed
119              || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
120              newCapacity = newCapacity(needed, jump);
121 <        elements = Arrays.copyOf(elements, newCapacity);
121 >        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
122          // Exceptionally, here tail == head needs to be disambiguated
123 <        if (tail < head || (tail == head && elements[head] != null)) {
123 >        if (tail < head || (tail == head && es[head] != null)) {
124              // wrap around; slide first leg forward to end of array
125              int newSpace = newCapacity - oldCapacity;
126 <            System.arraycopy(elements, head,
127 <                             elements, head + newSpace,
126 >            System.arraycopy(es, head,
127 >                             es, head + newSpace,
128                               oldCapacity - head);
129 <            Arrays.fill(elements, head, head + newSpace, null);
130 <            head += newSpace;
129 >            for (int i = head, to = (head += newSpace); i < to; i++)
130 >                es[i] = null;
131          }
132          // checkInvariants();
133      }
# Line 180 | Line 181 | public class ArrayDeque<E> extends Abstr
181       * sufficient to hold 16 elements.
182       */
183      public ArrayDeque() {
184 <        elements = new Object[16];
184 >        elements = new Object[16 + 1];
185      }
186  
187      /**
# Line 208 | Line 209 | public class ArrayDeque<E> extends Abstr
209       */
210      public ArrayDeque(Collection<? extends E> c) {
211          this(c.size());
212 <        addAll(c);
212 >        copyElements(c);
213      }
214  
215      /**
216 <     * Increments i, mod modulus.
216 >     * Circularly increments i, mod modulus.
217       * Precondition and postcondition: 0 <= i < modulus.
218       */
219      static final int inc(int i, int modulus) {
# Line 221 | Line 222 | public class ArrayDeque<E> extends Abstr
222      }
223  
224      /**
225 <     * Decrements i, mod modulus.
225 >     * Circularly decrements i, mod modulus.
226       * Precondition and postcondition: 0 <= i < modulus.
227       */
228      static final int dec(int i, int modulus) {
# Line 234 | Line 235 | public class ArrayDeque<E> extends Abstr
235       * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
236       * @return index 0 <= i < modulus
237       */
238 <    static final int add(int i, int distance, int modulus) {
239 <        if ((i += distance) - modulus >= 0) distance -= modulus;
238 >    static final int inc(int i, int distance, int modulus) {
239 >        if ((i += distance) - modulus >= 0) i -= modulus;
240          return i;
241      }
242  
# Line 244 | Line 245 | public class ArrayDeque<E> extends Abstr
245       * Index i must be logically ahead of index j.
246       * Precondition: 0 <= i < modulus, 0 <= j < modulus.
247       * @return the "circular distance" from j to i; corner case i == j
248 <     * is diambiguated to "empty", returning 0.
248 >     * is disambiguated to "empty", returning 0.
249       */
250      static final int sub(int i, int j, int modulus) {
251          if ((i -= j) < 0) i += modulus;
# Line 313 | Line 314 | public class ArrayDeque<E> extends Abstr
314      /**
315       * Adds all of the elements in the specified collection at the end
316       * of this deque, as if by calling {@link #addLast} on each one,
317 <     * in the order that they are returned by the collection's
317 <     * iterator.
317 >     * in the order that they are returned by the collection's iterator.
318       *
319       * @param c the elements to be inserted into this deque
320       * @return {@code true} if this deque changed as a result of the call
# Line 322 | Line 322 | public class ArrayDeque<E> extends Abstr
322       *         of its elements are null
323       */
324      public boolean addAll(Collection<? extends E> c) {
325 <        final int s = size(), needed;
326 <        if ((needed = s + c.size() - elements.length + 1) > 0)
325 >        final int s, needed;
326 >        if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
327              grow(needed);
328 <        c.forEach(this::addLast);
328 >        copyElements(c);
329          // checkInvariants();
330          return size() > s;
331      }
332  
333 +    private void copyElements(Collection<? extends E> c) {
334 +        c.forEach(this::addLast);
335 +    }
336 +
337      /**
338       * Inserts the specified element at the front of this deque.
339       *
# Line 520 | Line 524 | public class ArrayDeque<E> extends Abstr
524      /**
525       * Retrieves and removes the head of the queue represented by this deque.
526       *
527 <     * This method differs from {@link #poll poll} only in that it throws an
528 <     * exception if this deque is empty.
527 >     * This method differs from {@link #poll() poll()} only in that it
528 >     * throws an exception if this deque is empty.
529       *
530       * <p>This method is equivalent to {@link #removeFirst}.
531       *
# Line 616 | Line 620 | public class ArrayDeque<E> extends Abstr
620          // checkInvariants();
621          final Object[] es = elements;
622          final int capacity = es.length;
623 <        final int h = head;
623 >        final int h, t;
624          // number of elements before to-be-deleted elt
625 <        final int front = sub(i, h, capacity);
626 <        final int back = size() - front - 1; // number of elements after
625 >        final int front = sub(i, h = head, capacity);
626 >        // number of elements after to-be-deleted elt
627 >        final int back = sub(t = tail, i, capacity) - 1;
628          if (front < back) {
629              // move front elements forwards
630              if (h <= i) {
# Line 635 | Line 640 | public class ArrayDeque<E> extends Abstr
640              return false;
641          } else {
642              // move back elements backwards
643 <            tail = dec(tail, capacity);
643 >            tail = dec(t, capacity);
644              if (i <= tail) {
645                  System.arraycopy(es, i + 1, es, i, back);
646              } else { // Wrap around
647 <                int firstLeg = capacity - (i + 1);
643 <                System.arraycopy(es, i + 1, es, i, firstLeg);
647 >                System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
648                  es[capacity - 1] = es[0];
649 <                System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
649 >                System.arraycopy(es, 1, es, 0, t - 1);
650              }
651              es[tail] = null;
652              // checkInvariants();
# Line 710 | Line 714 | public class ArrayDeque<E> extends Abstr
714                  throw new NoSuchElementException();
715              final Object[] es = elements;
716              E e = nonNullElementAt(es, cursor);
717 <            lastRet = cursor;
714 <            cursor = inc(cursor, es.length);
717 >            cursor = inc(lastRet = cursor, es.length);
718              remaining--;
719              return e;
720          }
# Line 759 | Line 762 | public class ArrayDeque<E> extends Abstr
762                  throw new NoSuchElementException();
763              final Object[] es = elements;
764              E e = nonNullElementAt(es, cursor);
765 <            lastRet = cursor;
763 <            cursor = dec(cursor, es.length);
765 >            cursor = dec(lastRet = cursor, es.length);
766              remaining--;
767              return e;
768          }
# Line 822 | Line 824 | public class ArrayDeque<E> extends Abstr
824  
825          /** Constructs spliterator over the given range. */
826          DeqSpliterator(int origin, int fence) {
827 +            // assert 0 <= origin && origin < elements.length;
828 +            // assert 0 <= fence && fence < elements.length;
829              this.cursor = origin;
830              this.fence = fence;
831          }
# Line 841 | Line 845 | public class ArrayDeque<E> extends Abstr
845              final int i, n;
846              return ((n = sub(getFence(), i = cursor, es.length) >> 1) <= 0)
847                  ? null
848 <                : new DeqSpliterator(i, cursor = add(i, n, es.length));
848 >                : new DeqSpliterator(i, cursor = inc(i, n, es.length));
849          }
850  
851          public void forEachRemaining(Consumer<? super E> action) {
# Line 864 | Line 868 | public class ArrayDeque<E> extends Abstr
868          }
869  
870          public boolean tryAdvance(Consumer<? super E> action) {
871 <            if (action == null)
868 <                throw new NullPointerException();
869 <            final int t, i;
870 <            if ((t = getFence()) == (i = cursor))
871 <                return false;
871 >            Objects.requireNonNull(action);
872              final Object[] es = elements;
873 +            if (fence < 0) { fence = tail; cursor = head; } // late-binding
874 +            final int i;
875 +            if ((i = cursor) == fence)
876 +                return false;
877 +            E e = nonNullElementAt(es, i);
878              cursor = inc(i, es.length);
879 <            action.accept(nonNullElementAt(es, i));
879 >            action.accept(e);
880              return true;
881          }
882  
# Line 887 | Line 892 | public class ArrayDeque<E> extends Abstr
892          }
893      }
894  
895 +    /**
896 +     * @throws NullPointerException {@inheritDoc}
897 +     */
898      public void forEach(Consumer<? super E> action) {
899          Objects.requireNonNull(action);
900          final Object[] es = elements;
# Line 1075 | Line 1083 | public class ArrayDeque<E> extends Abstr
1083  
1084      /**
1085       * Nulls out slots starting at array index i, upto index end.
1086 +     * Condition i == end means "empty" - nothing to do.
1087       */
1088      private static void circularClear(Object[] es, int i, int end) {
1089 +        // assert 0 <= i && i < es.length;
1090 +        // assert 0 <= end && end < es.length;
1091          for (int to = (i <= end) ? end : es.length;
1092               ; i = 0, to = end) {
1093 <            Arrays.fill(es, i, to, null);
1093 >            for (; i < to; i++) es[i] = null;
1094              if (to == end) break;
1095          }
1096      }
# Line 1104 | Line 1115 | public class ArrayDeque<E> extends Abstr
1115      private <T> T[] toArray(Class<T[]> klazz) {
1116          final Object[] es = elements;
1117          final T[] a;
1118 <        final int size = size(), head = this.head, end;
1119 <        final int len = Math.min(size, es.length - head);
1120 <        if ((end = head + size) >= 0) {
1118 >        final int head = this.head, tail = this.tail, end;
1119 >        if ((end = tail + ((head <= tail) ? 0 : es.length)) >= 0) {
1120 >            // Uses null extension feature of copyOfRange
1121              a = Arrays.copyOfRange(es, head, end, klazz);
1122          } else {
1123              // integer overflow!
1124 <            a = Arrays.copyOfRange(es, 0, size, klazz);
1125 <            System.arraycopy(es, head, a, 0, len);
1124 >            a = Arrays.copyOfRange(es, 0, end - head, klazz);
1125 >            System.arraycopy(es, head, a, 0, es.length - head);
1126          }
1127 <        if (tail < head)
1128 <            System.arraycopy(es, 0, a, len, tail);
1127 >        if (end != tail)
1128 >            System.arraycopy(es, 0, a, es.length - head, tail);
1129          return a;
1130      }
1131  
# Line 1229 | Line 1240 | public class ArrayDeque<E> extends Abstr
1240  
1241          // Read in size and allocate array
1242          int size = s.readInt();
1243 +        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size + 1);
1244          elements = new Object[size + 1];
1245          this.tail = size;
1246  
# Line 1243 | Line 1255 | public class ArrayDeque<E> extends Abstr
1255          // head == tail disambiguates to "empty".
1256          try {
1257              int capacity = elements.length;
1258 <            // assert head >= 0 && head < capacity;
1259 <            // assert tail >= 0 && tail < capacity;
1258 >            // assert 0 <= head && head < capacity;
1259 >            // assert 0 <= tail && tail < capacity;
1260              // assert capacity > 0;
1261              // assert size() < capacity;
1262              // assert head == tail || elements[head] != null;

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines