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.92 by jsr166, Wed Oct 26 21:19:22 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 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) {
246 >    static final <E> E nonNullElementAt(Object[] elements, int i) {
247          @SuppressWarnings("unchecked") E e = (E) elements[i];
248          if (e == null)
249              throw new ConcurrentModificationException();
# 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 (;; i = 0, to = todo, 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 (;; i = capacity - 1, to = 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 >            final int k;
735              if ((k = remaining) > 0) {
736                  remaining = 0;
737                  ArrayDeque.forEachRemaining(action, elements, cursor, k);
# Line 738 | Line 745 | public class ArrayDeque<E> extends Abstr
745          DescendingIterator() { cursor = tail(); }
746  
747          public final E next() {
748 <            if (remaining == 0)
748 >            if (remaining <= 0)
749                  throw new NoSuchElementException();
750              final Object[] elements = ArrayDeque.this.elements;
751 <            E e = checkedElementAt(elements, cursor);
751 >            E e = nonNullElementAt(elements, cursor);
752              lastRet = cursor;
753              if (--cursor < 0) cursor = elements.length - 1;
754              remaining--;
# Line 754 | Line 761 | public class ArrayDeque<E> extends Abstr
761          }
762  
763          public final void forEachRemaining(Consumer<? super E> action) {
764 <            int k;
764 >            final int k;
765              if ((k = remaining) > 0) {
766                  remaining = 0;
767                  forEachRemainingDescending(action, elements, cursor, k);
# Line 817 | Line 824 | public class ArrayDeque<E> extends Abstr
824          }
825  
826          public void forEachRemaining(Consumer<? super E> action) {
827 <            int k = remaining(); // side effect!
827 >            final int k = remaining(); // side effect!
828              remaining = 0;
829              ArrayDeque.forEachRemaining(action, elements, cursor, k);
830          }
831  
832          public boolean tryAdvance(Consumer<? super E> action) {
833              Objects.requireNonNull(action);
834 <            if (remaining() == 0)
834 >            final int k;
835 >            if ((k = remaining()) <= 0)
836                  return false;
837 <            action.accept(checkedElementAt(elements, cursor));
837 >            action.accept(nonNullElementAt(elements, cursor));
838              if (++cursor >= elements.length) cursor = 0;
839 <            remaining--;
839 >            remaining = k - 1;
840              return true;
841          }
842  
# Line 849 | Line 857 | public class ArrayDeque<E> extends Abstr
857          Objects.requireNonNull(action);
858          final Object[] elements = this.elements;
859          final int capacity = elements.length;
860 <        int from, end, to, leftover;
861 <        leftover = (end = (from = head) + size)
860 >        int i, end, to, todo;
861 >        todo = (end = (i = head) + size)
862              - (to = (capacity - end >= 0) ? end : capacity);
863 <        for (;; from = 0, to = leftover, leftover = 0) {
864 <            for (int i = from; i < to; i++)
863 >        for (;; i = 0, to = todo, todo = 0) {
864 >            for (; i < to; i++)
865                  action.accept((E) elements[i]);
866 <            if (leftover == 0) break;
866 >            if (todo == 0) break;
867          }
868          // checkInvariants();
869      }
870  
871      /**
872 <     * A variant of forEach that also checks for concurrent
873 <     * modification, for use in iterators.
872 >     * Calls action on remaining elements, starting at index i and
873 >     * traversing in ascending order.  A variant of forEach that also
874 >     * checks for concurrent modification, for use in iterators.
875       */
876      static <E> void forEachRemaining(
877 <        Consumer<? super E> action, Object[] elements, int from, int size) {
877 >        Consumer<? super E> action, Object[] elements, int i, int remaining) {
878          Objects.requireNonNull(action);
879          final int capacity = elements.length;
880 <        int end, to, leftover;
881 <        leftover = (end = from + size)
880 >        int end, to, todo;
881 >        todo = (end = i + remaining)
882              - (to = (capacity - end >= 0) ? end : capacity);
883 <        for (;; from = 0, to = leftover, leftover = 0) {
884 <            for (int i = from; i < to; i++) {
885 <                @SuppressWarnings("unchecked") E e = (E) elements[i];
886 <                if (e == null)
878 <                    throw new ConcurrentModificationException();
879 <                action.accept(e);
880 <            }
881 <            if (leftover == 0) break;
883 >        for (;; i = 0, to = todo, todo = 0) {
884 >            for (; i < to; i++)
885 >                action.accept(nonNullElementAt(elements, i));
886 >            if (todo == 0) break;
887          }
888      }
889  
890      static <E> void forEachRemainingDescending(
891 <        Consumer<? super E> action, Object[] elements, int from, int size) {
891 >        Consumer<? super E> action, Object[] elements, int i, int remaining) {
892          Objects.requireNonNull(action);
893          final int capacity = elements.length;
894 <        int end, to, leftover;
895 <        leftover = (to = ((end = from - size) >= -1) ? end : -1) - end;
896 <        for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) {
897 <            for (int i = from; i > to; i--) {
898 <                @SuppressWarnings("unchecked") E e = (E) elements[i];
899 <                if (e == null)
895 <                    throw new ConcurrentModificationException();
896 <                action.accept(e);
897 <            }
898 <            if (leftover == 0) break;
894 >        int end, to, todo;
895 >        todo = (to = ((end = i - remaining) >= -1) ? end : -1) - end;
896 >        for (;; i = capacity - 1, to = capacity - 1 - todo, todo = 0) {
897 >            for (; i > to; i--)
898 >                action.accept(nonNullElementAt(elements, i));
899 >            if (todo == 0) break;
900          }
901      }
902  
# Line 910 | Line 911 | public class ArrayDeque<E> extends Abstr
911          Objects.requireNonNull(operator);
912          final Object[] elements = this.elements;
913          final int capacity = elements.length;
914 <        int from, end, to, leftover;
915 <        leftover = (end = (from = head) + size)
914 >        int i, end, to, todo;
915 >        todo = (end = (i = head) + size)
916              - (to = (capacity - end >= 0) ? end : capacity);
917 <        for (;; from = 0, to = leftover, leftover = 0) {
918 <            for (int i = from; i < to; i++)
917 >        for (;; i = 0, to = todo, todo = 0) {
918 >            for (; i < to; i++)
919                  elements[i] = operator.apply(elementAt(i));
920 <            if (leftover == 0) break;
920 >            if (todo == 0) break;
921          }
922          // checkInvariants();
923      }
# Line 991 | Line 992 | public class ArrayDeque<E> extends Abstr
992          if (o != null) {
993              final Object[] elements = this.elements;
994              final int capacity = elements.length;
995 <            int from, end, to, leftover;
996 <            leftover = (end = (from = head) + size)
995 >            int i, end, to, todo;
996 >            todo = (end = (i = head) + size)
997                  - (to = (capacity - end >= 0) ? end : capacity);
998 <            for (;; from = 0, to = leftover, leftover = 0) {
999 <                for (int i = from; i < to; i++)
998 >            for (;; i = 0, to = todo, todo = 0) {
999 >                for (; i < to; i++)
1000                      if (o.equals(elements[i]))
1001                          return true;
1002 <                if (leftover == 0) break;
1002 >                if (todo == 0) break;
1003              }
1004          }
1005          return false;
# Line 1032 | Line 1033 | public class ArrayDeque<E> extends Abstr
1033      }
1034  
1035      /**
1036 <     * Nulls out size elements, starting at head.
1036 >     * Nulls out count elements, starting at array index from.
1037       */
1038 <    private static void clearSlice(Object[] elements, int head, int size) {
1039 <        final int capacity = elements.length, end = head + size;
1038 >    private static void clearSlice(Object[] elements, int from, int count) {
1039 >        final int capacity = elements.length, end = from + count;
1040          final int leg = (capacity - end >= 0) ? end : capacity;
1041 <        Arrays.fill(elements, head, leg, null);
1041 >        Arrays.fill(elements, from, leg, null);
1042          if (leg != end)
1043              Arrays.fill(elements, 0, end - capacity, null);
1044      }
# Line 1168 | Line 1169 | public class ArrayDeque<E> extends Abstr
1169          // Write out elements in order.
1170          final Object[] elements = this.elements;
1171          final int capacity = elements.length;
1172 <        int from, end, to, leftover;
1173 <        leftover = (end = (from = head) + size)
1172 >        int i, end, to, todo;
1173 >        todo = (end = (i = head) + size)
1174              - (to = (capacity - end >= 0) ? end : capacity);
1175 <        for (;; from = 0, to = leftover, leftover = 0) {
1176 <            for (int i = from; i < to; i++)
1175 >        for (;; i = 0, to = todo, todo = 0) {
1176 >            for (; i < to; i++)
1177                  s.writeObject(elements[i]);
1178 <            if (leftover == 0) break;
1178 >            if (todo == 0) break;
1179          }
1180      }
1181  

Diff Legend

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