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.49 by jsr166, Wed Dec 21 05:15:36 2016 UTC vs.
Revision 1.64 by jsr166, Mon Oct 1 00:10:52 2018 UTC

# Line 1 | Line 1
1   /*
2 < * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
2 > * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
3   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4   *
5   * This code is free software; you can redistribute it and/or modify it
# Line 28 | Line 28 | package java.util;
28   import java.util.function.Consumer;
29   import java.util.function.Predicate;
30   import java.util.function.UnaryOperator;
31 + import jdk.internal.misc.SharedSecrets;
32  
33   /**
34   * Resizable-array implementation of the {@code List} interface.  Implements
# Line 91 | Line 92 | import java.util.function.UnaryOperator;
92   * should be used only to detect bugs.</i>
93   *
94   * <p>This class is a member of the
95 < * <a href="{@docRoot}/../technotes/guides/collections/index.html">
95 > * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
96   * Java Collections Framework</a>.
97   *
98   * @param <E> the type of elements in this list
# Line 313 | Line 314 | public class ArrayList<E> extends Abstra
314       * or -1 if there is no such index.
315       */
316      public int indexOf(Object o) {
317 +        return indexOfRange(o, 0, size);
318 +    }
319 +
320 +    int indexOfRange(Object o, int start, int end) {
321 +        Object[] es = elementData;
322          if (o == null) {
323 <            for (int i = 0; i < size; i++)
324 <                if (elementData[i]==null)
323 >            for (int i = start; i < end; i++) {
324 >                if (es[i] == null) {
325                      return i;
326 +                }
327 +            }
328          } else {
329 <            for (int i = 0; i < size; i++)
330 <                if (o.equals(elementData[i]))
329 >            for (int i = start; i < end; i++) {
330 >                if (o.equals(es[i])) {
331                      return i;
332 +                }
333 +            }
334          }
335          return -1;
336      }
# Line 333 | Line 343 | public class ArrayList<E> extends Abstra
343       * or -1 if there is no such index.
344       */
345      public int lastIndexOf(Object o) {
346 +        return lastIndexOfRange(o, 0, size);
347 +    }
348 +
349 +    int lastIndexOfRange(Object o, int start, int end) {
350 +        Object[] es = elementData;
351          if (o == null) {
352 <            for (int i = size-1; i >= 0; i--)
353 <                if (elementData[i]==null)
352 >            for (int i = end - 1; i >= start; i--) {
353 >                if (es[i] == null) {
354                      return i;
355 +                }
356 +            }
357          } else {
358 <            for (int i = size-1; i >= 0; i--)
359 <                if (o.equals(elementData[i]))
358 >            for (int i = end - 1; i >= start; i--) {
359 >                if (o.equals(es[i])) {
360                      return i;
361 +                }
362 +            }
363          }
364          return -1;
365      }
# Line 515 | Line 534 | public class ArrayList<E> extends Abstra
534       */
535      public E remove(int index) {
536          Objects.checkIndex(index, size);
537 +        final Object[] es = elementData;
538  
539 <        modCount++;
540 <        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
539 >        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
540 >        fastRemove(es, index);
541  
542          // checkInvariants();
543          return oldValue;
544      }
545  
546      /**
547 +     * {@inheritDoc}
548 +     */
549 +    public boolean equals(Object o) {
550 +        if (o == this) {
551 +            return true;
552 +        }
553 +
554 +        if (!(o instanceof List)) {
555 +            return false;
556 +        }
557 +
558 +        final int expectedModCount = modCount;
559 +        // ArrayList can be subclassed and given arbitrary behavior, but we can
560 +        // still deal with the common case where o is ArrayList precisely
561 +        boolean equal = (o.getClass() == ArrayList.class)
562 +            ? equalsArrayList((ArrayList<?>) o)
563 +            : equalsRange((List<?>) o, 0, size);
564 +
565 +        checkForComodification(expectedModCount);
566 +        return equal;
567 +    }
568 +
569 +    boolean equalsRange(List<?> other, int from, int to) {
570 +        final Object[] es = elementData;
571 +        if (to > es.length) {
572 +            throw new ConcurrentModificationException();
573 +        }
574 +        Iterator<?> oit = other.iterator();
575 +        for (; from < to; from++) {
576 +            if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
577 +                return false;
578 +            }
579 +        }
580 +        return !oit.hasNext();
581 +    }
582 +
583 +    private boolean equalsArrayList(ArrayList<?> other) {
584 +        final int otherModCount = other.modCount;
585 +        final int s = size;
586 +        boolean equal;
587 +        if (equal = (s == other.size)) {
588 +            final Object[] otherEs = other.elementData;
589 +            final Object[] es = elementData;
590 +            if (s > es.length || s > otherEs.length) {
591 +                throw new ConcurrentModificationException();
592 +            }
593 +            for (int i = 0; i < s; i++) {
594 +                if (!Objects.equals(es[i], otherEs[i])) {
595 +                    equal = false;
596 +                    break;
597 +                }
598 +            }
599 +        }
600 +        other.checkForComodification(otherModCount);
601 +        return equal;
602 +    }
603 +
604 +    private void checkForComodification(final int expectedModCount) {
605 +        if (modCount != expectedModCount) {
606 +            throw new ConcurrentModificationException();
607 +        }
608 +    }
609 +
610 +    /**
611 +     * {@inheritDoc}
612 +     */
613 +    public int hashCode() {
614 +        int expectedModCount = modCount;
615 +        int hash = hashCodeRange(0, size);
616 +        checkForComodification(expectedModCount);
617 +        return hash;
618 +    }
619 +
620 +    int hashCodeRange(int from, int to) {
621 +        final Object[] es = elementData;
622 +        if (to > es.length) {
623 +            throw new ConcurrentModificationException();
624 +        }
625 +        int hashCode = 1;
626 +        for (int i = from; i < to; i++) {
627 +            Object e = es[i];
628 +            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
629 +        }
630 +        return hashCode;
631 +    }
632 +
633 +    /**
634       * Removes the first occurrence of the specified element from this list,
635       * if it is present.  If the list does not contain the element, it is
636       * unchanged.  More formally, removes the element with the lowest index
# Line 543 | Line 644 | public class ArrayList<E> extends Abstra
644       * @return {@code true} if this list contained the specified element
645       */
646      public boolean remove(Object o) {
647 <        if (o == null) {
648 <            for (int index = 0; index < size; index++)
649 <                if (elementData[index] == null) {
650 <                    fastRemove(index);
651 <                    return true;
652 <                }
653 <        } else {
654 <            for (int index = 0; index < size; index++)
655 <                if (o.equals(elementData[index])) {
656 <                    fastRemove(index);
657 <                    return true;
658 <                }
647 >        final Object[] es = elementData;
648 >        final int size = this.size;
649 >        int i = 0;
650 >        found: {
651 >            if (o == null) {
652 >                for (; i < size; i++)
653 >                    if (es[i] == null)
654 >                        break found;
655 >            } else {
656 >                for (; i < size; i++)
657 >                    if (o.equals(es[i]))
658 >                        break found;
659 >            }
660 >            return false;
661          }
662 <        return false;
662 >        fastRemove(es, i);
663 >        return true;
664      }
665  
666      /**
667       * Private remove method that skips bounds checking and does not
668       * return the value removed.
669       */
670 <    private void fastRemove(int index) {
670 >    private void fastRemove(Object[] es, int i) {
671          modCount++;
672 <        int numMoved = size - index - 1;
673 <        if (numMoved > 0)
674 <            System.arraycopy(elementData, index+1, elementData, index,
675 <                             numMoved);
572 <        elementData[--size] = null; // clear to let GC do its work
672 >        final int newSize;
673 >        if ((newSize = size - 1) > i)
674 >            System.arraycopy(es, i + 1, es, i, newSize - i);
675 >        es[size = newSize] = null;
676      }
677  
678      /**
# Line 748 | Line 851 | public class ArrayList<E> extends Abstra
851                          final int from, final int end) {
852          Objects.requireNonNull(c);
853          final Object[] es = elementData;
751 –        final boolean modified;
854          int r;
855          // Optimize for initial run of survivors
856 <        for (r = from; r < end && c.contains(es[r]) == complement; r++)
857 <            ;
858 <        if (modified = (r < end)) {
859 <            int w = r++;
860 <            try {
861 <                for (Object e; r < end; r++)
862 <                    if (c.contains(e = es[r]) == complement)
863 <                        es[w++] = e;
864 <            } catch (Throwable ex) {
865 <                // Preserve behavioral compatibility with AbstractCollection,
866 <                // even if c.contains() throws.
867 <                System.arraycopy(es, r, es, w, end - r);
868 <                w += end - r;
869 <                throw ex;
870 <            } finally {
871 <                modCount += end - w;
872 <                shiftTailOverGap(es, w, end);
873 <            }
856 >        for (r = from;; r++) {
857 >            if (r == end)
858 >                return false;
859 >            if (c.contains(es[r]) != complement)
860 >                break;
861 >        }
862 >        int w = r++;
863 >        try {
864 >            for (Object e; r < end; r++)
865 >                if (c.contains(e = es[r]) == complement)
866 >                    es[w++] = e;
867 >        } catch (Throwable ex) {
868 >            // Preserve behavioral compatibility with AbstractCollection,
869 >            // even if c.contains() throws.
870 >            System.arraycopy(es, r, es, w, end - r);
871 >            w += end - r;
872 >            throw ex;
873 >        } finally {
874 >            modCount += end - w;
875 >            shiftTailOverGap(es, w, end);
876          }
877          // checkInvariants();
878 <        return modified;
878 >        return true;
879      }
880  
881      /**
# Line 790 | Line 894 | public class ArrayList<E> extends Abstra
894          int expectedModCount = modCount;
895          s.defaultWriteObject();
896  
897 <        // Write out size as capacity for behavioural compatibility with clone()
897 >        // Write out size as capacity for behavioral compatibility with clone()
898          s.writeInt(size);
899  
900          // Write out all elements in the proper order.
# Line 822 | Line 926 | public class ArrayList<E> extends Abstra
926  
927          if (size > 0) {
928              // like clone(), allocate array based upon size not capacity
929 +            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
930              Object[] elements = new Object[size];
931  
932              // Read in all elements in the proper order.
# Line 1122 | Line 1227 | public class ArrayList<E> extends Abstra
1227              return true;
1228          }
1229  
1230 +        public void replaceAll(UnaryOperator<E> operator) {
1231 +            root.replaceAllRange(operator, offset, offset + size);
1232 +        }
1233 +
1234          public boolean removeAll(Collection<?> c) {
1235              return batchRemove(c, false);
1236          }
# Line 1149 | Line 1258 | public class ArrayList<E> extends Abstra
1258              return modified;
1259          }
1260  
1261 +        public Object[] toArray() {
1262 +            checkForComodification();
1263 +            return Arrays.copyOfRange(root.elementData, offset, offset + size);
1264 +        }
1265 +
1266 +        @SuppressWarnings("unchecked")
1267 +        public <T> T[] toArray(T[] a) {
1268 +            checkForComodification();
1269 +            if (a.length < size)
1270 +                return (T[]) Arrays.copyOfRange(
1271 +                        root.elementData, offset, offset + size, a.getClass());
1272 +            System.arraycopy(root.elementData, offset, a, 0, size);
1273 +            if (a.length > size)
1274 +                a[size] = null;
1275 +            return a;
1276 +        }
1277 +
1278 +        public boolean equals(Object o) {
1279 +            if (o == this) {
1280 +                return true;
1281 +            }
1282 +
1283 +            if (!(o instanceof List)) {
1284 +                return false;
1285 +            }
1286 +
1287 +            boolean equal = root.equalsRange((List<?>)o, offset, offset + size);
1288 +            checkForComodification();
1289 +            return equal;
1290 +        }
1291 +
1292 +        public int hashCode() {
1293 +            int hash = root.hashCodeRange(offset, offset + size);
1294 +            checkForComodification();
1295 +            return hash;
1296 +        }
1297 +
1298 +        public int indexOf(Object o) {
1299 +            int index = root.indexOfRange(o, offset, offset + size);
1300 +            checkForComodification();
1301 +            return index >= 0 ? index - offset : -1;
1302 +        }
1303 +
1304 +        public int lastIndexOf(Object o) {
1305 +            int index = root.lastIndexOfRange(o, offset, offset + size);
1306 +            checkForComodification();
1307 +            return index >= 0 ? index - offset : -1;
1308 +        }
1309 +
1310 +        public boolean contains(Object o) {
1311 +            return indexOf(o) >= 0;
1312 +        }
1313 +
1314          public Iterator<E> iterator() {
1315              return listIterator();
1316          }
# Line 1556 | Line 1718 | public class ArrayList<E> extends Abstra
1718                      setBit(deathRow, i - beg);
1719              if (modCount != expectedModCount)
1720                  throw new ConcurrentModificationException();
1559 –            expectedModCount++;
1721              modCount++;
1722              int w = beg;
1723              for (i = beg; i < end; i++)
# Line 1575 | Line 1736 | public class ArrayList<E> extends Abstra
1736  
1737      @Override
1738      public void replaceAll(UnaryOperator<E> operator) {
1739 +        replaceAllRange(operator, 0, size);
1740 +    }
1741 +
1742 +    private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
1743          Objects.requireNonNull(operator);
1744          final int expectedModCount = modCount;
1745          final Object[] es = elementData;
1746 <        final int size = this.size;
1582 <        for (int i = 0; modCount == expectedModCount && i < size; i++)
1746 >        for (; modCount == expectedModCount && i < end; i++)
1747              es[i] = operator.apply(elementAt(es, i));
1748          if (modCount != expectedModCount)
1749              throw new ConcurrentModificationException();
1586 –        modCount++;
1750          // checkInvariants();
1751      }
1752  

Diff Legend

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