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 |
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 |
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 |
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 |
|
} |
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 |
|
} |
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 |
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 |
|
/** |
681 |
|
*/ |
682 |
|
public void clear() { |
683 |
|
modCount++; |
684 |
< |
Arrays.fill(elementData, 0, size, null); |
685 |
< |
size = 0; |
684 |
> |
final Object[] es = elementData; |
685 |
> |
for (int to = size, i = size = 0; i < to; i++) |
686 |
> |
es[i] = null; |
687 |
|
} |
688 |
|
|
689 |
|
/** |
773 |
|
outOfBoundsMsg(fromIndex, toIndex)); |
774 |
|
} |
775 |
|
modCount++; |
776 |
< |
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); |
776 |
> |
shiftTailOverGap(elementData, fromIndex, toIndex); |
777 |
|
// checkInvariants(); |
778 |
|
} |
779 |
|
|
780 |
+ |
/** Erases the gap from lo to hi, by sliding down following elements. */ |
781 |
+ |
private void shiftTailOverGap(Object[] es, int lo, int hi) { |
782 |
+ |
System.arraycopy(es, hi, es, lo, size - hi); |
783 |
+ |
for (int to = size, i = (size -= hi - lo); i < to; i++) |
784 |
+ |
es[i] = null; |
785 |
+ |
} |
786 |
+ |
|
787 |
|
/** |
788 |
|
* A version of rangeCheck used by add and addAll. |
789 |
|
*/ |
851 |
|
final int from, final int end) { |
852 |
|
Objects.requireNonNull(c); |
853 |
|
final Object[] es = elementData; |
746 |
– |
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 |
< |
final int oldSize = size, deleted = end - w; |
872 |
< |
modCount += deleted; |
873 |
< |
System.arraycopy(es, end, es, w, oldSize - end); |
874 |
< |
Arrays.fill(es, size -= deleted, oldSize, null); |
875 |
< |
} |
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 |
|
/** |
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. |
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. |
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 |
|
} |
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 |
|
} |
1533 |
|
} |
1534 |
|
} |
1535 |
|
|
1536 |
+ |
/** |
1537 |
+ |
* @throws NullPointerException {@inheritDoc} |
1538 |
+ |
*/ |
1539 |
|
@Override |
1540 |
|
public void forEach(Consumer<? super E> action) { |
1541 |
|
Objects.requireNonNull(action); |
1605 |
|
private int fence; // -1 until used; then one past last index |
1606 |
|
private int expectedModCount; // initialized when fence set |
1607 |
|
|
1608 |
< |
/** Create new spliterator covering the given range */ |
1608 |
> |
/** Creates new spliterator covering the given range. */ |
1609 |
|
ArrayListSpliterator(int origin, int fence, int expectedModCount) { |
1610 |
|
this.index = origin; |
1611 |
|
this.fence = fence; |
1687 |
|
return (bits[i >> 6] & (1L << i)) == 0; |
1688 |
|
} |
1689 |
|
|
1690 |
+ |
/** |
1691 |
+ |
* @throws NullPointerException {@inheritDoc} |
1692 |
+ |
*/ |
1693 |
|
@Override |
1694 |
|
public boolean removeIf(Predicate<? super E> filter) { |
1695 |
|
return removeIf(filter, 0, size); |
1718 |
|
setBit(deathRow, i - beg); |
1719 |
|
if (modCount != expectedModCount) |
1720 |
|
throw new ConcurrentModificationException(); |
1550 |
– |
expectedModCount++; |
1721 |
|
modCount++; |
1722 |
|
int w = beg; |
1723 |
|
for (i = beg; i < end; i++) |
1724 |
|
if (isClear(deathRow, i - beg)) |
1725 |
|
es[w++] = es[i]; |
1726 |
< |
final int oldSize = size; |
1557 |
< |
System.arraycopy(es, end, es, w, oldSize - end); |
1558 |
< |
Arrays.fill(es, size -= (end - w), oldSize, null); |
1726 |
> |
shiftTailOverGap(es, w, end); |
1727 |
|
// checkInvariants(); |
1728 |
|
return true; |
1729 |
|
} else { |
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; |
1575 |
< |
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(); |
1579 |
– |
modCount++; |
1750 |
|
// checkInvariants(); |
1751 |
|
} |
1752 |
|
|