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.89 by jsr166, Mon Oct 24 23:40:56 2016 UTC vs.
Revision 1.98 by jsr166, Sat Oct 29 22:47:55 2016 UTC

# Line 93 | Line 93 | public class ArrayDeque<E> extends Abstr
93      private void grow(int needed) {
94          // overflow-conscious code
95          // checkInvariants();
96 <        int oldCapacity = elements.length;
96 >        final int oldCapacity = elements.length;
97          int newCapacity;
98          // Double size if small; else grow by 50%
99          int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
# Line 115 | Line 115 | public class ArrayDeque<E> extends Abstr
115  
116      /** Capacity calculation for edge conditions, especially overflow. */
117      private int newCapacity(int needed, int jump) {
118 <        int oldCapacity = elements.length;
119 <        int minCapacity;
118 >        final int oldCapacity = elements.length, minCapacity;
119          if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
120              if (minCapacity < 0)
121                  throw new IllegalStateException("Sorry, deque too big");
# Line 184 | Line 183 | public class ArrayDeque<E> extends Abstr
183       * @throws NullPointerException if the specified collection is null
184       */
185      public ArrayDeque(Collection<? extends E> c) {
186 <        Object[] elements = c.toArray();
186 >        Object[] es = c.toArray();
187          // defend against c.toArray (incorrectly) not returning Object[]
188          // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
189 <        size = elements.length;
190 <        if (elements.getClass() != Object[].class)
191 <            elements = Arrays.copyOf(elements, size, Object[].class);
193 <        for (Object obj : elements)
189 >        if (es.getClass() != Object[].class)
190 >            es = Arrays.copyOf(es, es.length, Object[].class);
191 >        for (Object obj : es)
192              Objects.requireNonNull(obj);
193 <        this.elements = elements;
193 >        this.elements = es;
194 >        this.size = es.length;
195      }
196  
197      /**
# Line 241 | Line 240 | public class ArrayDeque<E> extends Abstr
240      /**
241       * A version of elementAt that checks for null elements.
242       * This check doesn't catch all possible comodifications,
243 <     * but does catch ones that corrupt traversal.
243 >     * but does catch ones that corrupt traversal.  It's a little
244 >     * surprising that javac allows this abuse of generics.
245       */
246 <    E checkedElementAt(Object[] elements, int i) {
247 <        @SuppressWarnings("unchecked") E e = (E) elements[i];
246 >    static final <E> E nonNullElementAt(Object[] es, int i) {
247 >        @SuppressWarnings("unchecked") E e = (E) es[i];
248          if (e == null)
249              throw new ConcurrentModificationException();
250          return e;
# Line 263 | Line 263 | public class ArrayDeque<E> extends Abstr
263      public void addFirst(E e) {
264          // checkInvariants();
265          Objects.requireNonNull(e);
266 <        Object[] elements;
266 >        Object[] es;
267          int capacity, h;
268          final int s;
269 <        if ((s = size) == (capacity = (elements = this.elements).length)) {
269 >        if ((s = size) == (capacity = (es = elements).length)) {
270              grow(1);
271 <            capacity = (elements = this.elements).length;
271 >            capacity = (es = elements).length;
272          }
273          if ((h = head - 1) < 0) h = capacity - 1;
274 <        elements[head = h] = e;
274 >        es[head = h] = e;
275          size = s + 1;
276          // checkInvariants();
277      }
# Line 287 | Line 287 | public class ArrayDeque<E> extends Abstr
287      public void addLast(E e) {
288          // checkInvariants();
289          Objects.requireNonNull(e);
290 <        Object[] elements;
290 >        Object[] es;
291          int capacity;
292          final int s;
293 <        if ((s = size) == (capacity = (elements = this.elements).length)) {
293 >        if ((s = size) == (capacity = (es = elements).length)) {
294              grow(1);
295 <            capacity = (elements = this.elements).length;
295 >            capacity = (es = elements).length;
296          }
297 <        elements[add(head, s, capacity)] = e;
297 >        es[add(head, s, capacity)] = e;
298          size = s + 1;
299          // checkInvariants();
300      }
# Line 368 | Line 368 | public class ArrayDeque<E> extends Abstr
368      public E pollFirst() {
369          // checkInvariants();
370          int s, h;
371 <        if ((s = size) == 0)
371 >        if ((s = size) <= 0)
372              return null;
373          final Object[] elements = this.elements;
374          @SuppressWarnings("unchecked") E e = (E) elements[h = head];
# Line 382 | Line 382 | public class ArrayDeque<E> extends Abstr
382      public E pollLast() {
383          // checkInvariants();
384          final int s, tail;
385 <        if ((s = size) == 0)
385 >        if ((s = size) <= 0)
386              return null;
387          final Object[] elements = this.elements;
388          @SuppressWarnings("unchecked")
# Line 397 | Line 397 | public class ArrayDeque<E> extends Abstr
397       */
398      public E getFirst() {
399          // checkInvariants();
400 <        if (size == 0) throw new NoSuchElementException();
400 >        if (size <= 0) throw new NoSuchElementException();
401          return elementAt(head);
402      }
403  
404      /**
405       * @throws NoSuchElementException {@inheritDoc}
406       */
407 +    @SuppressWarnings("unchecked")
408      public E getLast() {
409          // checkInvariants();
410 <        if (size == 0) throw new NoSuchElementException();
411 <        return elementAt(tail());
410 >        final int s;
411 >        if ((s = size) <= 0) throw new NoSuchElementException();
412 >        final Object[] elements = this.elements;
413 >        return (E) elements[add(head, s - 1, elements.length)];
414      }
415  
416      public E peekFirst() {
417          // checkInvariants();
418 <        return (size == 0) ? null : elementAt(head);
418 >        return (size <= 0) ? null : elementAt(head);
419      }
420  
421 +    @SuppressWarnings("unchecked")
422      public E peekLast() {
423          // checkInvariants();
424 <        return (size == 0) ? null : elementAt(tail());
424 >        final int s;
425 >        if ((s = size) <= 0) return null;
426 >        final Object[] elements = this.elements;
427 >        return (E) elements[add(head, s - 1, elements.length)];
428      }
429  
430      /**
# Line 436 | Line 443 | public class ArrayDeque<E> extends Abstr
443          if (o != null) {
444              final Object[] elements = this.elements;
445              final int capacity = elements.length;
446 <            int from, end, to, leftover;
447 <            leftover = (end = (from = head) + size)
446 >            int i, end, to, todo;
447 >            todo = (end = (i = head) + size)
448                  - (to = (capacity - end >= 0) ? end : capacity);
449 <            for (;; from = 0, to = leftover, leftover = 0) {
450 <                for (int i = from; i < to; i++)
449 >            for (;; to = todo, i = 0, todo = 0) {
450 >                for (; i < to; i++)
451                      if (o.equals(elements[i])) {
452                          delete(i);
453                          return true;
454                      }
455 <                if (leftover == 0) break;
455 >                if (todo == 0) break;
456              }
457          }
458          return false;
# Line 467 | Line 474 | public class ArrayDeque<E> extends Abstr
474          if (o != null) {
475              final Object[] elements = this.elements;
476              final int capacity = elements.length;
477 <            int from, to, end, leftover;
478 <            leftover = (to = ((end = (from = tail()) - size) >= -1) ? end : -1) - end;
479 <            for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) {
480 <                for (int i = from; i > to; i--)
477 >            int i, to, end, todo;
478 >            todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
479 >            for (;; to = (i = capacity - 1) - todo, todo = 0) {
480 >                for (; i > to; i--)
481                      if (o.equals(elements[i])) {
482                          delete(i);
483                          return true;
484                      }
485 <                if (leftover == 0) break;
485 >                if (todo == 0) break;
486              }
487          }
488          return false;
# Line 701 | Line 708 | public class ArrayDeque<E> extends Abstr
708          }
709  
710          public E next() {
711 <            if (remaining == 0)
711 >            if (remaining <= 0)
712                  throw new NoSuchElementException();
713              final Object[] elements = ArrayDeque.this.elements;
714 <            E e = checkedElementAt(elements, cursor);
714 >            E e = nonNullElementAt(elements, cursor);
715              lastRet = cursor;
716              if (++cursor >= elements.length) cursor = 0;
717              remaining--;
# Line 724 | Line 731 | public class ArrayDeque<E> extends Abstr
731          }
732  
733          public void forEachRemaining(Consumer<? super E> action) {
734 <            int k;
734 >            Objects.requireNonNull(action);
735 >            final int k;
736              if ((k = remaining) > 0) {
737                  remaining = 0;
738                  ArrayDeque.forEachRemaining(action, elements, cursor, k);
# Line 738 | Line 746 | public class ArrayDeque<E> extends Abstr
746          DescendingIterator() { cursor = tail(); }
747  
748          public final E next() {
749 <            if (remaining == 0)
749 >            if (remaining <= 0)
750                  throw new NoSuchElementException();
751              final Object[] elements = ArrayDeque.this.elements;
752 <            E e = checkedElementAt(elements, cursor);
752 >            E e = nonNullElementAt(elements, cursor);
753              lastRet = cursor;
754              if (--cursor < 0) cursor = elements.length - 1;
755              remaining--;
# Line 754 | Line 762 | public class ArrayDeque<E> extends Abstr
762          }
763  
764          public final void forEachRemaining(Consumer<? super E> action) {
765 <            int k;
765 >            Objects.requireNonNull(action);
766 >            final int k;
767              if ((k = remaining) > 0) {
768                  remaining = 0;
769 <                forEachRemainingDescending(action, elements, cursor, k);
769 >                final Object[] elements = ArrayDeque.this.elements;
770 >                int i, end, to, todo;
771 >                todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
772 >                for (;; to = (i = elements.length - 1) - todo, todo = 0) {
773 >                    for (; i > to; i--)
774 >                        action.accept(nonNullElementAt(elements, i));
775 >                    if (todo == 0) break;
776 >                }
777                  if ((lastRet = cursor - (k - 1)) < 0)
778                      lastRet += elements.length;
779              }
# Line 817 | Line 833 | public class ArrayDeque<E> extends Abstr
833          }
834  
835          public void forEachRemaining(Consumer<? super E> action) {
836 <            int k = remaining(); // side effect!
836 >            Objects.requireNonNull(action);
837 >            final int k = remaining(); // side effect!
838              remaining = 0;
839              ArrayDeque.forEachRemaining(action, elements, cursor, k);
840          }
841  
842          public boolean tryAdvance(Consumer<? super E> action) {
843              Objects.requireNonNull(action);
844 <            if (remaining() == 0)
844 >            final int k;
845 >            if ((k = remaining()) <= 0)
846                  return false;
847 <            action.accept(checkedElementAt(elements, cursor));
847 >            action.accept(nonNullElementAt(elements, cursor));
848              if (++cursor >= elements.length) cursor = 0;
849 <            remaining--;
849 >            remaining = k - 1;
850              return true;
851          }
852  
# Line 849 | Line 867 | public class ArrayDeque<E> extends Abstr
867          Objects.requireNonNull(action);
868          final Object[] elements = this.elements;
869          final int capacity = elements.length;
870 <        int from, end, to, leftover;
871 <        leftover = (end = (from = head) + size)
870 >        int i, end, to, todo;
871 >        todo = (end = (i = head) + size)
872              - (to = (capacity - end >= 0) ? end : capacity);
873 <        for (;; from = 0, to = leftover, leftover = 0) {
874 <            for (int i = from; i < to; i++)
873 >        for (;; to = todo, i = 0, todo = 0) {
874 >            for (; i < to; i++)
875                  action.accept((E) elements[i]);
876 <            if (leftover == 0) break;
876 >            if (todo == 0) break;
877          }
878          // checkInvariants();
879      }
880  
881      /**
882 <     * A variant of forEach that also checks for concurrent
883 <     * modification, for use in iterators.
882 >     * Calls action on remaining elements, starting at index i and
883 >     * traversing in ascending order.  A variant of forEach that also
884 >     * checks for concurrent modification, for use in iterators.
885       */
886      static <E> void forEachRemaining(
887 <        Consumer<? super E> action, Object[] elements, int from, int size) {
888 <        Objects.requireNonNull(action);
889 <        final int capacity = elements.length;
890 <        int end, to, leftover;
872 <        leftover = (end = from + size)
887 >        Consumer<? super E> action, Object[] es, int i, int remaining) {
888 >        final int capacity = es.length;
889 >        int end, to, todo;
890 >        todo = (end = i + remaining)
891              - (to = (capacity - end >= 0) ? end : capacity);
892 <        for (;; from = 0, to = leftover, leftover = 0) {
893 <            for (int i = from; i < to; i++) {
894 <                @SuppressWarnings("unchecked") E e = (E) elements[i];
895 <                if (e == null)
878 <                    throw new ConcurrentModificationException();
879 <                action.accept(e);
880 <            }
881 <            if (leftover == 0) break;
882 <        }
883 <    }
884 <
885 <    static <E> void forEachRemainingDescending(
886 <        Consumer<? super E> action, Object[] elements, int from, int size) {
887 <        Objects.requireNonNull(action);
888 <        final int capacity = elements.length;
889 <        int end, to, leftover;
890 <        leftover = (to = ((end = from - size) >= -1) ? end : -1) - end;
891 <        for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) {
892 <            for (int i = from; i > to; i--) {
893 <                @SuppressWarnings("unchecked") E e = (E) elements[i];
894 <                if (e == null)
895 <                    throw new ConcurrentModificationException();
896 <                action.accept(e);
897 <            }
898 <            if (leftover == 0) break;
892 >        for (;; to = todo, i = 0, todo = 0) {
893 >            for (; i < to; i++)
894 >                action.accept(nonNullElementAt(es, i));
895 >            if (todo == 0) break;
896          }
897      }
898  
# Line 910 | Line 907 | public class ArrayDeque<E> extends Abstr
907          Objects.requireNonNull(operator);
908          final Object[] elements = this.elements;
909          final int capacity = elements.length;
910 <        int from, end, to, leftover;
911 <        leftover = (end = (from = head) + size)
910 >        int i, end, to, todo;
911 >        todo = (end = (i = head) + size)
912              - (to = (capacity - end >= 0) ? end : capacity);
913 <        for (;; from = 0, to = leftover, leftover = 0) {
914 <            for (int i = from; i < to; i++)
913 >        for (;; to = todo, i = 0, todo = 0) {
914 >            for (; i < to; i++)
915                  elements[i] = operator.apply(elementAt(i));
916 <            if (leftover == 0) break;
916 >            if (todo == 0) break;
917          }
918          // checkInvariants();
919      }
# Line 991 | Line 988 | public class ArrayDeque<E> extends Abstr
988          if (o != null) {
989              final Object[] elements = this.elements;
990              final int capacity = elements.length;
991 <            int from, end, to, leftover;
992 <            leftover = (end = (from = head) + size)
991 >            int i, end, to, todo;
992 >            todo = (end = (i = head) + size)
993                  - (to = (capacity - end >= 0) ? end : capacity);
994 <            for (;; from = 0, to = leftover, leftover = 0) {
995 <                for (int i = from; i < to; i++)
994 >            for (;; to = todo, i = 0, todo = 0) {
995 >                for (; i < to; i++)
996                      if (o.equals(elements[i]))
997                          return true;
998 <                if (leftover == 0) break;
998 >                if (todo == 0) break;
999              }
1000          }
1001          return false;
# Line 1032 | Line 1029 | public class ArrayDeque<E> extends Abstr
1029      }
1030  
1031      /**
1032 <     * Nulls out size elements, starting at head.
1032 >     * Nulls out count elements, starting at array index from.
1033       */
1034 <    private static void clearSlice(Object[] elements, int head, int size) {
1035 <        final int capacity = elements.length, end = head + size;
1034 >    private static void clearSlice(Object[] es, int from, int count) {
1035 >        final int capacity = es.length, end = from + count;
1036          final int leg = (capacity - end >= 0) ? end : capacity;
1037 <        Arrays.fill(elements, head, leg, null);
1037 >        Arrays.fill(es, from, leg, null);
1038          if (leg != end)
1039 <            Arrays.fill(elements, 0, end - capacity, null);
1039 >            Arrays.fill(es, 0, end - capacity, null);
1040      }
1041  
1042      /**
# Line 1168 | Line 1165 | public class ArrayDeque<E> extends Abstr
1165          // Write out elements in order.
1166          final Object[] elements = this.elements;
1167          final int capacity = elements.length;
1168 <        int from, end, to, leftover;
1169 <        leftover = (end = (from = head) + size)
1168 >        int i, end, to, todo;
1169 >        todo = (end = (i = head) + size)
1170              - (to = (capacity - end >= 0) ? end : capacity);
1171 <        for (;; from = 0, to = leftover, leftover = 0) {
1172 <            for (int i = from; i < to; i++)
1171 >        for (;; to = todo, i = 0, todo = 0) {
1172 >            for (; i < to; i++)
1173                  s.writeObject(elements[i]);
1174 <            if (leftover == 0) break;
1174 >            if (todo == 0) break;
1175          }
1176      }
1177  

Diff Legend

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