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

Comparing jsr166/src/main/java/util/ArrayList.java (file contents):
Revision 1.35 by jsr166, Tue Oct 18 22:15:15 2016 UTC vs.
Revision 1.39 by jsr166, Sun Nov 13 02:10:09 2016 UTC

# Line 423 | Line 423 | public class ArrayList<E> extends Abstra
423          return (E) elementData[index];
424      }
425  
426 +    @SuppressWarnings("unchecked")
427 +    static <E> E elementAt(Object[] es, int index) {
428 +        return (E) es[index];
429 +    }
430 +
431      /**
432       * Returns the element at the specified position in this list.
433       *
# Line 716 | Line 721 | public class ArrayList<E> extends Abstra
721       * @see Collection#contains(Object)
722       */
723      public boolean removeAll(Collection<?> c) {
719 –        Objects.requireNonNull(c);
724          return batchRemove(c, false);
725      }
726  
# Line 737 | Line 741 | public class ArrayList<E> extends Abstra
741       * @see Collection#contains(Object)
742       */
743      public boolean retainAll(Collection<?> c) {
740 –        Objects.requireNonNull(c);
744          return batchRemove(c, true);
745      }
746  
747      private boolean batchRemove(Collection<?> c, boolean complement) {
748 <        final Object[] elementData = this.elementData;
749 <        int r = 0, w = 0;
750 <        boolean modified = false;
751 <        try {
752 <            for (; r < size; r++)
753 <                if (c.contains(elementData[r]) == complement)
754 <                    elementData[w++] = elementData[r];
755 <        } finally {
756 <            // Preserve behavioral compatibility with AbstractCollection,
757 <            // even if c.contains() throws.
758 <            if (r != size) {
759 <                System.arraycopy(elementData, r,
760 <                                 elementData, w,
761 <                                 size - r);
762 <                w += size - r;
763 <            }
764 <            if (w != size) {
765 <                // clear to let GC do its work
766 <                for (int i = w; i < size; i++)
767 <                    elementData[i] = null;
768 <                modCount += size - w;
769 <                size = w;
770 <                modified = true;
748 >        Objects.requireNonNull(c);
749 >        final Object[] es = elementData;
750 >        final int end = size;
751 >        final boolean modified;
752 >        int r;
753 >        // Optimize for initial run of survivors
754 >        for (r = 0; r < end && c.contains(es[r]) == complement; r++)
755 >            ;
756 >        if (modified = (r < end)) {
757 >            int w = r++;
758 >            try {
759 >                for (Object e; r < end; r++)
760 >                    if (c.contains(e = es[r]) == complement)
761 >                        es[w++] = e;
762 >            } catch (Throwable ex) {
763 >                // Preserve behavioral compatibility with AbstractCollection,
764 >                // even if c.contains() throws.
765 >                System.arraycopy(es, r, es, w, end - r);
766 >                w += end - r;
767 >                throw ex;
768 >            } finally {
769 >                modCount += end - w;
770 >                Arrays.fill(es, size = w, end, null);
771              }
772          }
773          return modified;
# Line 1347 | Line 1350 | public class ArrayList<E> extends Abstra
1350      public void forEach(Consumer<? super E> action) {
1351          Objects.requireNonNull(action);
1352          final int expectedModCount = modCount;
1353 <        @SuppressWarnings("unchecked")
1351 <        final E[] elementData = (E[]) this.elementData;
1353 >        final Object[] es = elementData;
1354          final int size = this.size;
1355 <        for (int i=0; modCount == expectedModCount && i < size; i++) {
1356 <            action.accept(elementData[i]);
1355 >        for (int i = 0; modCount == expectedModCount && i < size; i++) {
1356 >            action.accept(elementAt(es, i));
1357          }
1358          if (modCount != expectedModCount) {
1359              throw new ConcurrentModificationException();
# Line 1494 | Line 1496 | public class ArrayList<E> extends Abstra
1496          }
1497      }
1498  
1499 +    // A tiny bit set implementation
1500 +
1501 +    private static long[] nBits(int n) {
1502 +        return new long[((n - 1) >> 6) + 1];
1503 +    }
1504 +    private static void setBit(long[] bits, int i) {
1505 +        bits[i >> 6] |= 1L << i;
1506 +    }
1507 +    private static boolean isClear(long[] bits, int i) {
1508 +        return (bits[i >> 6] & (1L << i)) == 0;
1509 +    }
1510 +
1511      @Override
1512 <    public boolean removeIf(Predicate<? super E> filter) {
1512 >        public boolean removeIf(Predicate<? super E> filter) {
1513          Objects.requireNonNull(filter);
1514 <        final int expectedModCount = modCount;
1515 <        final Object[] elementData = this.elementData;
1516 <        int r = 0, w = 0, remaining = size, deleted = 0;
1517 <        try {
1518 <            for (; remaining > 0; remaining--, r++) {
1519 <                @SuppressWarnings("unchecked") E e = (E) elementData[r];
1520 <                if (filter.test(e))
1521 <                    deleted++;
1522 <                else {
1523 <                    if (r != w)
1524 <                        elementData[w] = e;
1525 <                    w++;
1526 <                }
1527 <            }
1528 <            if (modCount != expectedModCount)
1529 <                throw new ConcurrentModificationException();
1530 <            return deleted > 0;
1531 <        } catch (Throwable ex) {
1532 <            if (deleted > 0)
1533 <                for (; remaining > 0; remaining--, r++, w++)
1534 <                    elementData[w] = elementData[r];
1535 <            throw ex;
1536 <        } finally {
1537 <            if (deleted > 0) {
1538 <                modCount++;
1525 <                size -= deleted;
1526 <                while (--deleted >= 0)
1527 <                    elementData[w++] = null;
1528 <            }
1514 >        int expectedModCount = modCount;
1515 >        final Object[] es = elementData;
1516 >        final int end = size;
1517 >        final boolean modified;
1518 >        int i;
1519 >        // Optimize for initial run of survivors
1520 >        for (i = 0; i < end && !filter.test(elementAt(es, i)); i++)
1521 >            ;
1522 >        // Tolerate predicates that reentrantly access the collection for
1523 >        // read (but writers still get CME), so traverse once to find
1524 >        // elements to delete, a second pass to physically expunge.
1525 >        if (modified = (i < end)) {
1526 >            expectedModCount++;
1527 >            modCount++;
1528 >            final int beg = i;
1529 >            final long[] deathRow = nBits(end - beg);
1530 >            deathRow[0] = 1L;   // set bit 0
1531 >            for (i = beg + 1; i < end; i++)
1532 >                if (filter.test(elementAt(es, i)))
1533 >                    setBit(deathRow, i - beg);
1534 >            int w = beg;
1535 >            for (i = beg; i < end; i++)
1536 >                if (isClear(deathRow, i - beg))
1537 >                    es[w++] = es[i];
1538 >            Arrays.fill(es, size = w, end, null);
1539          }
1540 +        if (modCount != expectedModCount)
1541 +            throw new ConcurrentModificationException();
1542 +        return modified;
1543      }
1544  
1545      @Override
1533 –    @SuppressWarnings("unchecked")
1546      public void replaceAll(UnaryOperator<E> operator) {
1547          Objects.requireNonNull(operator);
1548          final int expectedModCount = modCount;
1549 +        final Object[] es = elementData;
1550          final int size = this.size;
1551          for (int i=0; modCount == expectedModCount && i < size; i++) {
1552 <            elementData[i] = operator.apply((E) elementData[i]);
1552 >            es[i] = operator.apply(elementAt(es, i));
1553          }
1554          if (modCount != expectedModCount) {
1555              throw new ConcurrentModificationException();

Diff Legend

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