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.99 by jsr166, Sun Oct 30 16:32:40 2016 UTC vs.
Revision 1.105 by jsr166, Tue Nov 1 21:42:45 2016 UTC

# Line 90 | Line 90 | public class ArrayDeque<E> extends Abstr
90       *
91       * @param needed the required minimum extra capacity; must be positive
92       */
93 <    private void grow(int needed) {
93 >    private Object[] grow(int needed) {
94          // overflow-conscious code
95          // checkInvariants();
96          final int oldCapacity = elements.length;
# Line 110 | Line 110 | public class ArrayDeque<E> extends Abstr
110              Arrays.fill(elements, head, head + newSpace, null);
111              head += newSpace;
112          }
113 +        return elements;
114          // checkInvariants();
115      }
116  
# Line 266 | Line 267 | public class ArrayDeque<E> extends Abstr
267          Object[] es;
268          int capacity, h;
269          final int s;
270 <        if ((s = size) == (capacity = (es = elements).length)) {
271 <            grow(1);
271 <            capacity = (es = elements).length;
272 <        }
270 >        if ((s = size) == (capacity = (es = elements).length))
271 >            capacity = (es = grow(1)).length;
272          if ((h = head - 1) < 0) h = capacity - 1;
273          es[head = h] = e;
274          size = s + 1;
# Line 290 | Line 289 | public class ArrayDeque<E> extends Abstr
289          Object[] es;
290          int capacity;
291          final int s;
292 <        if ((s = size) == (capacity = (es = elements).length)) {
293 <            grow(1);
295 <            capacity = (es = elements).length;
296 <        }
292 >        if ((s = size) == (capacity = (es = elements).length))
293 >            capacity = (es = grow(1)).length;
294          es[add(head, s, capacity)] = e;
295          size = s + 1;
296          // checkInvariants();
# Line 445 | Line 442 | public class ArrayDeque<E> extends Abstr
442              int i, end, to, todo;
443              todo = (end = (i = head) + size)
444                  - (to = (es.length - end >= 0) ? end : es.length);
445 <            for (;; to = todo, i = 0, todo = 0) {
445 >            for (;; to = todo, todo = 0, i = 0) {
446                  for (; i < to; i++)
447                      if (o.equals(es[i])) {
448                          delete(i);
# Line 867 | Line 864 | public class ArrayDeque<E> extends Abstr
864          int i, end, to, todo;
865          todo = (end = (i = head) + size)
866              - (to = (es.length - end >= 0) ? end : es.length);
867 <        for (;; to = todo, i = 0, todo = 0) {
867 >        for (;; to = todo, todo = 0, i = 0) {
868              for (; i < to; i++)
869                  action.accept((E) es[i]);
870              if (todo == 0) break;
# Line 885 | Line 882 | public class ArrayDeque<E> extends Abstr
882          int end, to, todo;
883          todo = (end = i + remaining)
884              - (to = (es.length - end >= 0) ? end : es.length);
885 <        for (;; to = todo, i = 0, todo = 0) {
885 >        for (;; to = todo, todo = 0, i = 0) {
886              for (; i < to; i++)
887                  action.accept(nonNullElementAt(es, i));
888              if (todo == 0) break;
# Line 906 | Line 903 | public class ArrayDeque<E> extends Abstr
903          int i, end, to, todo;
904          todo = (end = (i = head) + size)
905              - (to = (es.length - end >= 0) ? end : es.length);
906 <        for (;; to = todo, i = 0, todo = 0) {
906 >        for (;; to = todo, todo = 0, i = 0) {
907              for (; i < to; i++)
908                  es[i] = operator.apply((E) es[i]);
909              if (todo == 0) break;
# Line 939 | Line 936 | public class ArrayDeque<E> extends Abstr
936      }
937  
938      /** Implementation of bulk remove methods. */
939 +    @SuppressWarnings("unchecked")
940      private boolean bulkRemove(Predicate<? super E> filter) {
941          // checkInvariants();
942          final Object[] es = elements;
943 +        int i, end, to, todo;
944 +        todo = (end = (i = head) + size)
945 +            - (to = (es.length - end >= 0) ? end : es.length);
946 +        // Optimize for initial run of non-removed elements
947 +        findFirstRemoved:
948 +        for (;; to = todo, todo = 0, i = 0) {
949 +            for (; i < to; i++)
950 +                if (filter.test((E) es[i]))
951 +                    break findFirstRemoved;
952 +            if (todo == 0) return false;
953 +        }
954 +        bulkRemoveModified(filter, i, to, todo);
955 +        return true;
956 +    }
957 +
958 +    /**
959 +     * Helper for bulkRemove, in case of at least one deletion.
960 +     * @param i valid index of first element to be deleted
961 +     */
962 +    @SuppressWarnings("unchecked")
963 +    private void bulkRemoveModified(
964 +        Predicate<? super E> filter, int i, int to, int todo) {
965 +        final Object[] es = elements;
966          final int capacity = es.length;
967 <        int i = head, j = i, remaining = size, deleted = 0;
967 >        // a two-finger algorithm, with hare i and tortoise j
968 >        int j = i++;
969          try {
970 <            for (; remaining > 0; remaining--) {
971 <                @SuppressWarnings("unchecked") E e = (E) es[i];
972 <                if (filter.test(e))
973 <                    deleted++;
974 <                else {
975 <                    if (j != i)
976 <                        es[j] = e;
977 <                    if (++j >= capacity) j = 0;
978 <                }
979 <                if (++i >= capacity) i = 0;
970 >            for (;;) {
971 >                E e;
972 >                // In this loop, i and j are on the same leg, with i > j
973 >                for (; i < to; i++)
974 >                    if (!filter.test(e = (E) es[i]))
975 >                        es[j++] = e;
976 >                if (todo == 0) break;
977 >                // In this loop, j is on the first leg, i on the second
978 >                for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
979 >                    if (!filter.test(e = (E) es[i]))
980 >                        es[j++] = e;
981 >                if (i >= to) break;
982 >                j = 0;          // j rejoins i on second leg
983              }
984 <            return deleted > 0;
984 >            bulkRemoveClear(es, j, i);
985 >            // checkInvariants();
986          } catch (Throwable ex) {
987 <            if (deleted > 0)
988 <                for (; remaining > 0; remaining--) {
989 <                    es[j] = es[i];
990 <                    if (++i >= capacity) i = 0;
991 <                    if (++j >= capacity) j = 0;
992 <                }
993 <            throw ex;
968 <        } finally {
969 <            size -= deleted;
970 <            clearSlice(es, j, deleted);
987 >            // copy remaining elements
988 >            for (int remaining = (to - i) + todo; --remaining >= 0;) {
989 >                es[j] = es[i];
990 >                if (++i >= capacity) i = 0;
991 >                if (++j >= capacity) j = 0;
992 >            }
993 >            bulkRemoveClear(es, j, i);
994              // checkInvariants();
995 +            throw ex;
996          }
997      }
998  
999      /**
1000 +     * Nulls out all elements from index j upto index i.
1001 +     */
1002 +    private void bulkRemoveClear(Object[] es, int j, int i) {
1003 +        int deleted;
1004 +        if ((deleted = i - j) <= 0) deleted += es.length;
1005 +        size -= deleted;
1006 +        circularClear(es, j, deleted);
1007 +    }
1008 +
1009 +    /**
1010       * Returns {@code true} if this deque contains the specified element.
1011       * More formally, returns {@code true} if and only if this deque contains
1012       * at least one element {@code e} such that {@code o.equals(e)}.
# Line 986 | Line 1020 | public class ArrayDeque<E> extends Abstr
1020              int i, end, to, todo;
1021              todo = (end = (i = head) + size)
1022                  - (to = (es.length - end >= 0) ? end : es.length);
1023 <            for (;; to = todo, i = 0, todo = 0) {
1023 >            for (;; to = todo, todo = 0, i = 0) {
1024                  for (; i < to; i++)
1025                      if (o.equals(es[i]))
1026                          return true;
# Line 1018 | Line 1052 | public class ArrayDeque<E> extends Abstr
1052       * The deque will be empty after this call returns.
1053       */
1054      public void clear() {
1055 <        clearSlice(elements, head, size);
1055 >        circularClear(elements, head, size);
1056          size = head = 0;
1057          // checkInvariants();
1058      }
1059  
1060      /**
1061 <     * Nulls out count elements, starting at array index i.
1061 >     * Nulls out count elements, starting at array index from.
1062 >     * Special case (from == es.length) is treated the same as (from == 0).
1063       */
1064 <    private static void clearSlice(Object[] es, int i, int count) {
1064 >    private static void circularClear(Object[] es, int from, int count) {
1065          int end, to, todo;
1066 <        todo = (end = i + count)
1066 >        todo = (end = from + count)
1067              - (to = (es.length - end >= 0) ? end : es.length);
1068 <        for (;; to = todo, i = 0, todo = 0) {
1069 <            Arrays.fill(es, i, to, null);
1068 >        for (;; to = todo, todo = 0, from = 0) {
1069 >            Arrays.fill(es, from, to, null);
1070              if (todo == 0) break;
1071          }
1072      }
# Line 1055 | Line 1090 | public class ArrayDeque<E> extends Abstr
1090  
1091      private <T> T[] toArray(Class<T[]> klazz) {
1092          final Object[] es = elements;
1058 –        final int capacity = es.length;
1059 –        final int head = this.head, end = head + size;
1093          final T[] a;
1094 <        if (end >= 0) {
1094 >        final int head, len, end, todo;
1095 >        todo = size - (len = Math.min(size, es.length - (head = this.head)));
1096 >        if ((end = head + size) >= 0) {
1097              a = Arrays.copyOfRange(es, head, end, klazz);
1098          } else {
1099              // integer overflow!
1100              a = Arrays.copyOfRange(es, 0, size, klazz);
1101 <            System.arraycopy(es, head, a, 0, capacity - head);
1101 >            System.arraycopy(es, head, a, 0, len);
1102          }
1103 <        if (end - capacity > 0)
1104 <            System.arraycopy(es, 0, a, capacity - head, end - capacity);
1103 >        if (todo > 0)
1104 >            System.arraycopy(es, 0, a, len, todo);
1105          return a;
1106      }
1107  
# Line 1112 | Line 1147 | public class ArrayDeque<E> extends Abstr
1147          if ((size = this.size) > a.length)
1148              return toArray((Class<T[]>) a.getClass());
1149          final Object[] es = elements;
1150 <        final int head = this.head, end = head + size;
1151 <        final int front = (es.length - end >= 0) ? size : es.length - head;
1152 <        System.arraycopy(es, head, a, 0, front);
1153 <        if (front < size)
1154 <            System.arraycopy(es, 0, a, front, size - front);
1150 >        int i, j, len, todo;
1151 >        todo = size - (len = Math.min(size, es.length - (i = head)));
1152 >        for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1153 >            System.arraycopy(es, i, a, j, len);
1154 >            if (todo == 0) break;
1155 >        }
1156          if (size < a.length)
1157              a[size] = null;
1158          return a;
# Line 1163 | Line 1199 | public class ArrayDeque<E> extends Abstr
1199          int i, end, to, todo;
1200          todo = (end = (i = head) + size)
1201              - (to = (es.length - end >= 0) ? end : es.length);
1202 <        for (;; to = todo, i = 0, todo = 0) {
1202 >        for (;; to = todo, todo = 0, i = 0) {
1203              for (; i < to; i++)
1204                  s.writeObject(es[i]);
1205              if (todo == 0) break;

Diff Legend

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