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.104 by jsr166, Mon Oct 31 21:15:35 2016 UTC

# Line 445 | Line 445 | public class ArrayDeque<E> extends Abstr
445              int i, end, to, todo;
446              todo = (end = (i = head) + size)
447                  - (to = (es.length - end >= 0) ? end : es.length);
448 <            for (;; to = todo, i = 0, todo = 0) {
448 >            for (;; to = todo, todo = 0, i = 0) {
449                  for (; i < to; i++)
450                      if (o.equals(es[i])) {
451                          delete(i);
# Line 867 | Line 867 | public class ArrayDeque<E> extends Abstr
867          int i, end, to, todo;
868          todo = (end = (i = head) + size)
869              - (to = (es.length - end >= 0) ? end : es.length);
870 <        for (;; to = todo, i = 0, todo = 0) {
870 >        for (;; to = todo, todo = 0, i = 0) {
871              for (; i < to; i++)
872                  action.accept((E) es[i]);
873              if (todo == 0) break;
# Line 885 | Line 885 | public class ArrayDeque<E> extends Abstr
885          int end, to, todo;
886          todo = (end = i + remaining)
887              - (to = (es.length - end >= 0) ? end : es.length);
888 <        for (;; to = todo, i = 0, todo = 0) {
888 >        for (;; to = todo, todo = 0, i = 0) {
889              for (; i < to; i++)
890                  action.accept(nonNullElementAt(es, i));
891              if (todo == 0) break;
# Line 906 | Line 906 | public class ArrayDeque<E> extends Abstr
906          int i, end, to, todo;
907          todo = (end = (i = head) + size)
908              - (to = (es.length - end >= 0) ? end : es.length);
909 <        for (;; to = todo, i = 0, todo = 0) {
909 >        for (;; to = todo, todo = 0, i = 0) {
910              for (; i < to; i++)
911                  es[i] = operator.apply((E) es[i]);
912              if (todo == 0) break;
# Line 939 | Line 939 | public class ArrayDeque<E> extends Abstr
939      }
940  
941      /** Implementation of bulk remove methods. */
942 +    @SuppressWarnings("unchecked")
943      private boolean bulkRemove(Predicate<? super E> filter) {
944          // checkInvariants();
945          final Object[] es = elements;
946 +        int i, end, to, todo;
947 +        todo = (end = (i = head) + size)
948 +            - (to = (es.length - end >= 0) ? end : es.length);
949 +        // Optimize for initial run of non-removed elements
950 +        findFirstRemoved:
951 +        for (;; to = todo, todo = 0, i = 0) {
952 +            for (; i < to; i++)
953 +                if (filter.test((E) es[i]))
954 +                    break findFirstRemoved;
955 +            if (todo == 0) return false;
956 +        }
957 +        bulkRemoveModified(filter, i, to, todo);
958 +        return true;
959 +    }
960 +
961 +    /**
962 +     * Helper for bulkRemove, in case of at least one deletion.
963 +     * @param i valid index of first element to be deleted
964 +     */
965 +    @SuppressWarnings("unchecked")
966 +    private void bulkRemoveModified(
967 +        Predicate<? super E> filter, int i, int to, int todo) {
968 +        final Object[] es = elements;
969          final int capacity = es.length;
970 <        int i = head, j = i, remaining = size, deleted = 0;
970 >        // a two-finger algorithm, with hare i and tortoise j
971 >        int j = i++;
972          try {
973 <            for (; remaining > 0; remaining--) {
974 <                @SuppressWarnings("unchecked") E e = (E) es[i];
975 <                if (filter.test(e))
976 <                    deleted++;
977 <                else {
978 <                    if (j != i)
979 <                        es[j] = e;
980 <                    if (++j >= capacity) j = 0;
981 <                }
982 <                if (++i >= capacity) i = 0;
973 >            for (;;) {
974 >                E e;
975 >                // In this loop, i and j are on the same leg, with i > j
976 >                for (; i < to; i++)
977 >                    if (!filter.test(e = (E) es[i]))
978 >                        es[j++] = e;
979 >                if (todo == 0) break;
980 >                // In this loop, j is on the first leg, i on the second
981 >                for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
982 >                    if (!filter.test(e = (E) es[i]))
983 >                        es[j++] = e;
984 >                if (i >= to) break;
985 >                j = 0;          // j rejoins i on second leg
986              }
987 <            return deleted > 0;
987 >            bulkRemoveClear(es, j, i);
988 >            // checkInvariants();
989          } catch (Throwable ex) {
990 <            if (deleted > 0)
991 <                for (; remaining > 0; remaining--) {
992 <                    es[j] = es[i];
993 <                    if (++i >= capacity) i = 0;
994 <                    if (++j >= capacity) j = 0;
995 <                }
996 <            throw ex;
968 <        } finally {
969 <            size -= deleted;
970 <            clearSlice(es, j, deleted);
990 >            // copy remaining elements
991 >            for (int remaining = (to - i) + todo; --remaining >= 0;) {
992 >                es[j] = es[i];
993 >                if (++i >= capacity) i = 0;
994 >                if (++j >= capacity) j = 0;
995 >            }
996 >            bulkRemoveClear(es, j, i);
997              // checkInvariants();
998 +            throw ex;
999          }
1000      }
1001  
1002      /**
1003 +     * Nulls out all elements from index j upto index i.
1004 +     */
1005 +    private void bulkRemoveClear(Object[] es, int j, int i) {
1006 +        int deleted;
1007 +        if ((deleted = i - j) <= 0) deleted += es.length;
1008 +        size -= deleted;
1009 +        circularClear(es, j, deleted);
1010 +    }
1011 +
1012 +    /**
1013       * Returns {@code true} if this deque contains the specified element.
1014       * More formally, returns {@code true} if and only if this deque contains
1015       * at least one element {@code e} such that {@code o.equals(e)}.
# Line 986 | Line 1023 | public class ArrayDeque<E> extends Abstr
1023              int i, end, to, todo;
1024              todo = (end = (i = head) + size)
1025                  - (to = (es.length - end >= 0) ? end : es.length);
1026 <            for (;; to = todo, i = 0, todo = 0) {
1026 >            for (;; to = todo, todo = 0, i = 0) {
1027                  for (; i < to; i++)
1028                      if (o.equals(es[i]))
1029                          return true;
# Line 1018 | Line 1055 | public class ArrayDeque<E> extends Abstr
1055       * The deque will be empty after this call returns.
1056       */
1057      public void clear() {
1058 <        clearSlice(elements, head, size);
1058 >        circularClear(elements, head, size);
1059          size = head = 0;
1060          // checkInvariants();
1061      }
1062  
1063      /**
1064 <     * Nulls out count elements, starting at array index i.
1064 >     * Nulls out count elements, starting at array index from.
1065 >     * Special case (from == es.length) is treated the same as (from == 0).
1066       */
1067 <    private static void clearSlice(Object[] es, int i, int count) {
1067 >    private static void circularClear(Object[] es, int from, int count) {
1068          int end, to, todo;
1069 <        todo = (end = i + count)
1069 >        todo = (end = from + count)
1070              - (to = (es.length - end >= 0) ? end : es.length);
1071 <        for (;; to = todo, i = 0, todo = 0) {
1072 <            Arrays.fill(es, i, to, null);
1071 >        for (;; to = todo, todo = 0, from = 0) {
1072 >            Arrays.fill(es, from, to, null);
1073              if (todo == 0) break;
1074          }
1075      }
# Line 1055 | Line 1093 | public class ArrayDeque<E> extends Abstr
1093  
1094      private <T> T[] toArray(Class<T[]> klazz) {
1095          final Object[] es = elements;
1058 –        final int capacity = es.length;
1059 –        final int head = this.head, end = head + size;
1096          final T[] a;
1097 <        if (end >= 0) {
1097 >        final int head, len, end, todo;
1098 >        todo = size - (len = Math.min(size, es.length - (head = this.head)));
1099 >        if ((end = head + size) >= 0) {
1100              a = Arrays.copyOfRange(es, head, end, klazz);
1101          } else {
1102              // integer overflow!
1103              a = Arrays.copyOfRange(es, 0, size, klazz);
1104 <            System.arraycopy(es, head, a, 0, capacity - head);
1104 >            System.arraycopy(es, head, a, 0, len);
1105          }
1106 <        if (end - capacity > 0)
1107 <            System.arraycopy(es, 0, a, capacity - head, end - capacity);
1106 >        if (todo > 0)
1107 >            System.arraycopy(es, 0, a, len, todo);
1108          return a;
1109      }
1110  
# Line 1112 | Line 1150 | public class ArrayDeque<E> extends Abstr
1150          if ((size = this.size) > a.length)
1151              return toArray((Class<T[]>) a.getClass());
1152          final Object[] es = elements;
1153 <        final int head = this.head, end = head + size;
1154 <        final int front = (es.length - end >= 0) ? size : es.length - head;
1155 <        System.arraycopy(es, head, a, 0, front);
1156 <        if (front < size)
1157 <            System.arraycopy(es, 0, a, front, size - front);
1153 >        int i, j, len, todo;
1154 >        todo = size - (len = Math.min(size, es.length - (i = head)));
1155 >        for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1156 >            System.arraycopy(es, i, a, j, len);
1157 >            if (todo == 0) break;
1158 >        }
1159          if (size < a.length)
1160              a[size] = null;
1161          return a;
# Line 1163 | Line 1202 | public class ArrayDeque<E> extends Abstr
1202          int i, end, to, todo;
1203          todo = (end = (i = head) + size)
1204              - (to = (es.length - end >= 0) ? end : es.length);
1205 <        for (;; to = todo, i = 0, todo = 0) {
1205 >        for (;; to = todo, todo = 0, i = 0) {
1206              for (; i < to; i++)
1207                  s.writeObject(es[i]);
1208              if (todo == 0) break;

Diff Legend

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