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.44 by jsr166, Wed Nov 16 00:17:25 2016 UTC vs.
Revision 1.52 by jsr166, Wed May 31 22:37:31 2017 UTC

# Line 91 | Line 91 | import java.util.function.UnaryOperator;
91   * should be used only to detect bugs.</i>
92   *
93   * <p>This class is a member of the
94 < * <a href="{@docRoot}/../technotes/guides/collections/index.html">
94 > * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
95   * Java Collections Framework</a>.
96   *
97   * @param <E> the type of elements in this list
# Line 515 | Line 515 | public class ArrayList<E> extends Abstra
515       */
516      public E remove(int index) {
517          Objects.checkIndex(index, size);
518 +        final Object[] es = elementData;
519  
520 <        modCount++;
521 <        E oldValue = elementData(index);
521 <
522 <        int numMoved = size - index - 1;
523 <        if (numMoved > 0)
524 <            System.arraycopy(elementData, index+1, elementData, index,
525 <                             numMoved);
526 <        elementData[--size] = null; // clear to let GC do its work
520 >        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
521 >        fastRemove(es, index);
522  
523          // checkInvariants();
524          return oldValue;
# Line 543 | Line 538 | public class ArrayList<E> extends Abstra
538       * @return {@code true} if this list contained the specified element
539       */
540      public boolean remove(Object o) {
541 <        if (o == null) {
542 <            for (int index = 0; index < size; index++)
543 <                if (elementData[index] == null) {
544 <                    fastRemove(index);
545 <                    return true;
546 <                }
547 <        } else {
548 <            for (int index = 0; index < size; index++)
549 <                if (o.equals(elementData[index])) {
550 <                    fastRemove(index);
551 <                    return true;
552 <                }
541 >        final Object[] es = elementData;
542 >        final int size = this.size;
543 >        int i = 0;
544 >        found: {
545 >            if (o == null) {
546 >                for (; i < size; i++)
547 >                    if (es[i] == null)
548 >                        break found;
549 >            } else {
550 >                for (; i < size; i++)
551 >                    if (o.equals(es[i]))
552 >                        break found;
553 >            }
554 >            return false;
555          }
556 <        return false;
556 >        fastRemove(es, i);
557 >        return true;
558      }
559  
560      /**
561       * Private remove method that skips bounds checking and does not
562       * return the value removed.
563       */
564 <    private void fastRemove(int index) {
564 >    private void fastRemove(Object[] es, int i) {
565          modCount++;
566 <        int numMoved = size - index - 1;
567 <        if (numMoved > 0)
568 <            System.arraycopy(elementData, index+1, elementData, index,
569 <                             numMoved);
572 <        elementData[--size] = null; // clear to let GC do its work
566 >        final int newSize;
567 >        if ((newSize = size - 1) > i)
568 >            System.arraycopy(es, i + 1, es, i, newSize - i);
569 >        es[size = newSize] = null;
570      }
571  
572      /**
# Line 578 | Line 575 | public class ArrayList<E> extends Abstra
575       */
576      public void clear() {
577          modCount++;
578 <        Arrays.fill(elementData, 0, size, null);
579 <        size = 0;
578 >        final Object[] es = elementData;
579 >        for (int to = size, i = size = 0; i < to; i++)
580 >            es[i] = null;
581      }
582  
583      /**
# Line 669 | Line 667 | public class ArrayList<E> extends Abstra
667                      outOfBoundsMsg(fromIndex, toIndex));
668          }
669          modCount++;
670 <        final Object[] es = elementData;
673 <        final int oldSize = size;
674 <        System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
675 <        Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null);
670 >        shiftTailOverGap(elementData, fromIndex, toIndex);
671          // checkInvariants();
672      }
673  
674 +    /** Erases the gap from lo to hi, by sliding down following elements. */
675 +    private void shiftTailOverGap(Object[] es, int lo, int hi) {
676 +        System.arraycopy(es, hi, es, lo, size - hi);
677 +        for (int to = size, i = (size -= hi - lo); i < to; i++)
678 +            es[i] = null;
679 +    }
680 +
681      /**
682       * A version of rangeCheck used by add and addAll.
683       */
# Line 761 | Line 763 | public class ArrayList<E> extends Abstra
763                  w += end - r;
764                  throw ex;
765              } finally {
766 <                final int oldSize = size, deleted = end - w;
767 <                modCount += deleted;
766 <                System.arraycopy(es, end, es, w, oldSize - end);
767 <                Arrays.fill(es, size -= deleted, oldSize, null);
766 >                modCount += end - w;
767 >                shiftTailOverGap(es, w, end);
768              }
769          }
770          // checkInvariants();
# Line 772 | Line 772 | public class ArrayList<E> extends Abstra
772      }
773  
774      /**
775 <     * Save the state of the {@code ArrayList} instance to a stream (that
776 <     * is, serialize it).
775 >     * Saves the state of the {@code ArrayList} instance to a stream
776 >     * (that is, serializes it).
777       *
778 +     * @param s the stream
779 +     * @throws java.io.IOException if an I/O error occurs
780       * @serialData The length of the array backing the {@code ArrayList}
781       *             instance is emitted (int), followed by all of its elements
782       *             (each an {@code Object}) in the proper order.
783       */
784      private void writeObject(java.io.ObjectOutputStream s)
785 <        throws java.io.IOException{
785 >        throws java.io.IOException {
786          // Write out element count, and any hidden stuff
787          int expectedModCount = modCount;
788          s.defaultWriteObject();
789  
790 <        // Write out size as capacity for behavioural compatibility with clone()
790 >        // Write out size as capacity for behavioral compatibility with clone()
791          s.writeInt(size);
792  
793          // Write out all elements in the proper order.
# Line 799 | Line 801 | public class ArrayList<E> extends Abstra
801      }
802  
803      /**
804 <     * Reconstitute the {@code ArrayList} instance from a stream (that is,
805 <     * deserialize it).
804 >     * Reconstitutes the {@code ArrayList} instance from a stream (that is,
805 >     * deserializes it).
806 >     * @param s the stream
807 >     * @throws ClassNotFoundException if the class of a serialized object
808 >     *         could not be found
809 >     * @throws java.io.IOException if an I/O error occurs
810       */
811      private void readObject(java.io.ObjectInputStream s)
812          throws java.io.IOException, ClassNotFoundException {
# Line 1291 | Line 1297 | public class ArrayList<E> extends Abstra
1297          public Spliterator<E> spliterator() {
1298              checkForComodification();
1299  
1300 <            // ArrayListSpliterator is not used because late-binding logic
1301 <            // is different here
1296 <            return new Spliterator<>() {
1300 >            // ArrayListSpliterator not used here due to late-binding
1301 >            return new Spliterator<E>() {
1302                  private int index = offset; // current index, modified on advance/split
1303                  private int fence = -1; // -1 until used; then one past last index
1304                  private int expectedModCount; // initialized when fence set
# Line 1307 | Line 1312 | public class ArrayList<E> extends Abstra
1312                      return hi;
1313                  }
1314  
1315 <                public ArrayListSpliterator<E> trySplit() {
1315 >                public ArrayList<E>.ArrayListSpliterator trySplit() {
1316                      int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1317 <                    // ArrayListSpliterator could be used here as the source is already bound
1317 >                    // ArrayListSpliterator can be used here as the source is already bound
1318                      return (lo >= mid) ? null : // divide range in half unless too small
1319 <                        new ArrayListSpliterator<>(root, lo, index = mid,
1315 <                                                   expectedModCount);
1319 >                        root.new ArrayListSpliterator(lo, index = mid, expectedModCount);
1320                  }
1321  
1322                  public boolean tryAdvance(Consumer<? super E> action) {
# Line 1354 | Line 1358 | public class ArrayList<E> extends Abstra
1358                  }
1359  
1360                  public long estimateSize() {
1361 <                    return (long) (getFence() - index);
1361 >                    return getFence() - index;
1362                  }
1363  
1364                  public int characteristics() {
# Line 1364 | Line 1368 | public class ArrayList<E> extends Abstra
1368          }
1369      }
1370  
1371 +    /**
1372 +     * @throws NullPointerException {@inheritDoc}
1373 +     */
1374      @Override
1375      public void forEach(Consumer<? super E> action) {
1376          Objects.requireNonNull(action);
# Line 1391 | Line 1398 | public class ArrayList<E> extends Abstra
1398       */
1399      @Override
1400      public Spliterator<E> spliterator() {
1401 <        return new ArrayListSpliterator<>(this, 0, -1, 0);
1401 >        return new ArrayListSpliterator(0, -1, 0);
1402      }
1403  
1404      /** Index-based split-by-two, lazily initialized Spliterator */
1405 <    static final class ArrayListSpliterator<E> implements Spliterator<E> {
1405 >    final class ArrayListSpliterator implements Spliterator<E> {
1406  
1407          /*
1408           * If ArrayLists were immutable, or structurally immutable (no
# Line 1429 | Line 1436 | public class ArrayList<E> extends Abstra
1436           * these streamlinings.
1437           */
1438  
1432 –        private final ArrayList<E> list;
1439          private int index; // current index, modified on advance/split
1440          private int fence; // -1 until used; then one past last index
1441          private int expectedModCount; // initialized when fence set
1442  
1443 <        /** Create new spliterator covering the given range */
1444 <        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
1439 <                             int expectedModCount) {
1440 <            this.list = list; // OK if null unless traversed
1443 >        /** Creates new spliterator covering the given range. */
1444 >        ArrayListSpliterator(int origin, int fence, int expectedModCount) {
1445              this.index = origin;
1446              this.fence = fence;
1447              this.expectedModCount = expectedModCount;
# Line 1445 | Line 1449 | public class ArrayList<E> extends Abstra
1449  
1450          private int getFence() { // initialize fence to size on first use
1451              int hi; // (a specialized variant appears in method forEach)
1448 –            ArrayList<E> lst;
1452              if ((hi = fence) < 0) {
1453 <                if ((lst = list) == null)
1454 <                    hi = fence = 0;
1452 <                else {
1453 <                    expectedModCount = lst.modCount;
1454 <                    hi = fence = lst.size;
1455 <                }
1453 >                expectedModCount = modCount;
1454 >                hi = fence = size;
1455              }
1456              return hi;
1457          }
1458  
1459 <        public ArrayListSpliterator<E> trySplit() {
1459 >        public ArrayListSpliterator trySplit() {
1460              int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1461              return (lo >= mid) ? null : // divide range in half unless too small
1462 <                new ArrayListSpliterator<>(list, lo, index = mid,
1464 <                                           expectedModCount);
1462 >                new ArrayListSpliterator(lo, index = mid, expectedModCount);
1463          }
1464  
1465          public boolean tryAdvance(Consumer<? super E> action) {
# Line 1470 | Line 1468 | public class ArrayList<E> extends Abstra
1468              int hi = getFence(), i = index;
1469              if (i < hi) {
1470                  index = i + 1;
1471 <                @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
1471 >                @SuppressWarnings("unchecked") E e = (E)elementData[i];
1472                  action.accept(e);
1473 <                if (list.modCount != expectedModCount)
1473 >                if (modCount != expectedModCount)
1474                      throw new ConcurrentModificationException();
1475                  return true;
1476              }
# Line 1481 | Line 1479 | public class ArrayList<E> extends Abstra
1479  
1480          public void forEachRemaining(Consumer<? super E> action) {
1481              int i, hi, mc; // hoist accesses and checks from loop
1482 <            ArrayList<E> lst; Object[] a;
1482 >            Object[] a;
1483              if (action == null)
1484                  throw new NullPointerException();
1485 <            if ((lst = list) != null && (a = lst.elementData) != null) {
1485 >            if ((a = elementData) != null) {
1486                  if ((hi = fence) < 0) {
1487 <                    mc = lst.modCount;
1488 <                    hi = lst.size;
1487 >                    mc = modCount;
1488 >                    hi = size;
1489                  }
1490                  else
1491                      mc = expectedModCount;
# Line 1496 | Line 1494 | public class ArrayList<E> extends Abstra
1494                          @SuppressWarnings("unchecked") E e = (E) a[i];
1495                          action.accept(e);
1496                      }
1497 <                    if (lst.modCount == mc)
1497 >                    if (modCount == mc)
1498                          return;
1499                  }
1500              }
# Line 1504 | Line 1502 | public class ArrayList<E> extends Abstra
1502          }
1503  
1504          public long estimateSize() {
1505 <            return (long) (getFence() - index);
1505 >            return getFence() - index;
1506          }
1507  
1508          public int characteristics() {
# Line 1524 | Line 1522 | public class ArrayList<E> extends Abstra
1522          return (bits[i >> 6] & (1L << i)) == 0;
1523      }
1524  
1525 +    /**
1526 +     * @throws NullPointerException {@inheritDoc}
1527 +     */
1528      @Override
1529      public boolean removeIf(Predicate<? super E> filter) {
1530          return removeIf(filter, 0, size);
# Line 1558 | Line 1559 | public class ArrayList<E> extends Abstra
1559              for (i = beg; i < end; i++)
1560                  if (isClear(deathRow, i - beg))
1561                      es[w++] = es[i];
1562 <            final int oldSize = size;
1562 <            System.arraycopy(es, end, es, w, oldSize - end);
1563 <            Arrays.fill(es, size -= (end - w), oldSize, null);
1562 >            shiftTailOverGap(es, w, end);
1563              // checkInvariants();
1564              return true;
1565          } else {

Diff Legend

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