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/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 |
|
} |
442 |
|
return (E) elementData[index]; |
443 |
|
} |
444 |
|
|
445 |
+ |
@SuppressWarnings("unchecked") |
446 |
+ |
static <E> E elementAt(Object[] es, int index) { |
447 |
+ |
return (E) es[index]; |
448 |
+ |
} |
449 |
+ |
|
450 |
|
/** |
451 |
|
* Returns the element at the specified position in this list. |
452 |
|
* |
520 |
|
s - index); |
521 |
|
elementData[index] = element; |
522 |
|
size = s + 1; |
523 |
+ |
// checkInvariants(); |
524 |
|
} |
525 |
|
|
526 |
|
/** |
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); |
515 |
< |
|
516 |
< |
int numMoved = size - index - 1; |
517 |
< |
if (numMoved > 0) |
518 |
< |
System.arraycopy(elementData, index+1, elementData, index, |
519 |
< |
numMoved); |
520 |
< |
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 |
< |
/* |
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); |
565 |
< |
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 |
< |
|
685 |
< |
// clear to let GC do its work |
686 |
< |
for (int i = 0; i < size; i++) |
577 |
< |
elementData[i] = null; |
578 |
< |
|
579 |
< |
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 |
|
/** |
711 |
|
elementData = grow(s + numNew); |
712 |
|
System.arraycopy(a, 0, elementData, s, numNew); |
713 |
|
size = s + numNew; |
714 |
+ |
// checkInvariants(); |
715 |
|
return true; |
716 |
|
} |
717 |
|
|
750 |
|
numMoved); |
751 |
|
System.arraycopy(a, 0, elementData, index, numNew); |
752 |
|
size = s + numNew; |
753 |
+ |
// checkInvariants(); |
754 |
|
return true; |
755 |
|
} |
756 |
|
|
773 |
|
outOfBoundsMsg(fromIndex, toIndex)); |
774 |
|
} |
775 |
|
modCount++; |
776 |
< |
int numMoved = size - toIndex; |
777 |
< |
System.arraycopy(elementData, toIndex, elementData, fromIndex, |
778 |
< |
numMoved); |
779 |
< |
|
780 |
< |
// clear to let GC do its work |
781 |
< |
int newSize = size - (toIndex-fromIndex); |
782 |
< |
for (int i = newSize; i < size; i++) { |
783 |
< |
elementData[i] = null; |
784 |
< |
} |
676 |
< |
size = newSize; |
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 |
|
/** |
824 |
|
* @see Collection#contains(Object) |
825 |
|
*/ |
826 |
|
public boolean removeAll(Collection<?> c) { |
827 |
< |
Objects.requireNonNull(c); |
720 |
< |
return batchRemove(c, false); |
827 |
> |
return batchRemove(c, false, 0, size); |
828 |
|
} |
829 |
|
|
830 |
|
/** |
844 |
|
* @see Collection#contains(Object) |
845 |
|
*/ |
846 |
|
public boolean retainAll(Collection<?> c) { |
847 |
< |
Objects.requireNonNull(c); |
741 |
< |
return batchRemove(c, true); |
847 |
> |
return batchRemove(c, true, 0, size); |
848 |
|
} |
849 |
|
|
850 |
< |
private boolean batchRemove(Collection<?> c, boolean complement) { |
851 |
< |
final Object[] elementData = this.elementData; |
852 |
< |
int r = 0, w = 0; |
853 |
< |
boolean modified = false; |
850 |
> |
boolean batchRemove(Collection<?> c, boolean complement, |
851 |
> |
final int from, final int end) { |
852 |
> |
Objects.requireNonNull(c); |
853 |
> |
final Object[] es = elementData; |
854 |
> |
int r; |
855 |
> |
// Optimize for initial run of survivors |
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 (; r < size; r++) |
865 |
< |
if (c.contains(elementData[r]) == complement) |
866 |
< |
elementData[w++] = elementData[r]; |
867 |
< |
} finally { |
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 |
< |
if (r != size) { |
871 |
< |
System.arraycopy(elementData, r, |
872 |
< |
elementData, w, |
873 |
< |
size - r); |
874 |
< |
w += size - r; |
875 |
< |
} |
761 |
< |
if (w != size) { |
762 |
< |
// clear to let GC do its work |
763 |
< |
for (int i = w; i < size; i++) |
764 |
< |
elementData[i] = null; |
765 |
< |
modCount += size - w; |
766 |
< |
size = w; |
767 |
< |
modified = true; |
768 |
< |
} |
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 |
< |
return modified; |
877 |
> |
// checkInvariants(); |
878 |
> |
return true; |
879 |
|
} |
880 |
|
|
881 |
|
/** |
882 |
< |
* Save the state of the {@code ArrayList} instance to a stream (that |
883 |
< |
* is, serialize it). |
882 |
> |
* Saves the state of the {@code ArrayList} instance to a stream |
883 |
> |
* (that is, serializes it). |
884 |
|
* |
885 |
+ |
* @param s the stream |
886 |
+ |
* @throws java.io.IOException if an I/O error occurs |
887 |
|
* @serialData The length of the array backing the {@code ArrayList} |
888 |
|
* instance is emitted (int), followed by all of its elements |
889 |
|
* (each an {@code Object}) in the proper order. |
890 |
|
*/ |
891 |
|
private void writeObject(java.io.ObjectOutputStream s) |
892 |
< |
throws java.io.IOException{ |
892 |
> |
throws java.io.IOException { |
893 |
|
// Write out element count, and any hidden stuff |
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. |
908 |
|
} |
909 |
|
|
910 |
|
/** |
911 |
< |
* Reconstitute the {@code ArrayList} instance from a stream (that is, |
912 |
< |
* deserialize it). |
911 |
> |
* Reconstitutes the {@code ArrayList} instance from a stream (that is, |
912 |
> |
* deserializes it). |
913 |
> |
* @param s the stream |
914 |
> |
* @throws ClassNotFoundException if the class of a serialized object |
915 |
> |
* could not be found |
916 |
> |
* @throws java.io.IOException if an I/O error occurs |
917 |
|
*/ |
918 |
|
private void readObject(java.io.ObjectInputStream s) |
919 |
|
throws java.io.IOException, ClassNotFoundException { |
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. |
1026 |
|
} |
1027 |
|
|
1028 |
|
@Override |
1029 |
< |
@SuppressWarnings("unchecked") |
1030 |
< |
public void forEachRemaining(Consumer<? super E> consumer) { |
916 |
< |
Objects.requireNonNull(consumer); |
1029 |
> |
public void forEachRemaining(Consumer<? super E> action) { |
1030 |
> |
Objects.requireNonNull(action); |
1031 |
|
final int size = ArrayList.this.size; |
1032 |
|
int i = cursor; |
1033 |
< |
if (i >= size) { |
1034 |
< |
return; |
1035 |
< |
} |
1036 |
< |
final Object[] elementData = ArrayList.this.elementData; |
1037 |
< |
if (i >= elementData.length) { |
1038 |
< |
throw new ConcurrentModificationException(); |
1039 |
< |
} |
1040 |
< |
while (i != size && modCount == expectedModCount) { |
1041 |
< |
consumer.accept((E) elementData[i++]); |
1033 |
> |
if (i < size) { |
1034 |
> |
final Object[] es = elementData; |
1035 |
> |
if (i >= es.length) |
1036 |
> |
throw new ConcurrentModificationException(); |
1037 |
> |
for (; i < size && modCount == expectedModCount; i++) |
1038 |
> |
action.accept(elementAt(es, i)); |
1039 |
> |
// update once at end to reduce heap write traffic |
1040 |
> |
cursor = i; |
1041 |
> |
lastRet = i - 1; |
1042 |
> |
checkForComodification(); |
1043 |
|
} |
929 |
– |
// update once at end of iteration to reduce heap write traffic |
930 |
– |
cursor = i; |
931 |
– |
lastRet = i - 1; |
932 |
– |
checkForComodification(); |
1044 |
|
} |
1045 |
|
|
1046 |
|
final void checkForComodification() { |
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 |
+ |
} |
1237 |
+ |
|
1238 |
+ |
public boolean retainAll(Collection<?> c) { |
1239 |
+ |
return batchRemove(c, true); |
1240 |
+ |
} |
1241 |
+ |
|
1242 |
+ |
private boolean batchRemove(Collection<?> c, boolean complement) { |
1243 |
+ |
checkForComodification(); |
1244 |
+ |
int oldSize = root.size; |
1245 |
+ |
boolean modified = |
1246 |
+ |
root.batchRemove(c, complement, offset, offset + size); |
1247 |
+ |
if (modified) |
1248 |
+ |
updateSizeAndModCount(root.size - oldSize); |
1249 |
+ |
return modified; |
1250 |
+ |
} |
1251 |
+ |
|
1252 |
+ |
public boolean removeIf(Predicate<? super E> filter) { |
1253 |
+ |
checkForComodification(); |
1254 |
+ |
int oldSize = root.size; |
1255 |
+ |
boolean modified = root.removeIf(filter, offset, offset + size); |
1256 |
+ |
if (modified) |
1257 |
+ |
updateSizeAndModCount(root.size - oldSize); |
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 |
|
} |
1358 |
|
return (E) elementData[offset + (lastRet = i)]; |
1359 |
|
} |
1360 |
|
|
1361 |
< |
@SuppressWarnings("unchecked") |
1362 |
< |
public void forEachRemaining(Consumer<? super E> consumer) { |
1168 |
< |
Objects.requireNonNull(consumer); |
1361 |
> |
public void forEachRemaining(Consumer<? super E> action) { |
1362 |
> |
Objects.requireNonNull(action); |
1363 |
|
final int size = SubList.this.size; |
1364 |
|
int i = cursor; |
1365 |
< |
if (i >= size) { |
1366 |
< |
return; |
1367 |
< |
} |
1368 |
< |
final Object[] elementData = root.elementData; |
1369 |
< |
if (offset + i >= elementData.length) { |
1370 |
< |
throw new ConcurrentModificationException(); |
1371 |
< |
} |
1372 |
< |
while (i != size && modCount == expectedModCount) { |
1373 |
< |
consumer.accept((E) elementData[offset + (i++)]); |
1365 |
> |
if (i < size) { |
1366 |
> |
final Object[] es = root.elementData; |
1367 |
> |
if (offset + i >= es.length) |
1368 |
> |
throw new ConcurrentModificationException(); |
1369 |
> |
for (; i < size && modCount == expectedModCount; i++) |
1370 |
> |
action.accept(elementAt(es, offset + i)); |
1371 |
> |
// update once at end to reduce heap write traffic |
1372 |
> |
cursor = i; |
1373 |
> |
lastRet = i - 1; |
1374 |
> |
checkForComodification(); |
1375 |
|
} |
1181 |
– |
// update once at end of iteration to reduce heap write traffic |
1182 |
– |
lastRet = cursor = i; |
1183 |
– |
checkForComodification(); |
1376 |
|
} |
1377 |
|
|
1378 |
|
public int nextIndex() { |
1462 |
|
public Spliterator<E> spliterator() { |
1463 |
|
checkForComodification(); |
1464 |
|
|
1465 |
< |
// ArrayListSpliterator is not used because late-binding logic |
1466 |
< |
// is different here |
1275 |
< |
return new Spliterator<>() { |
1465 |
> |
// ArrayListSpliterator not used here due to late-binding |
1466 |
> |
return new Spliterator<E>() { |
1467 |
|
private int index = offset; // current index, modified on advance/split |
1468 |
|
private int fence = -1; // -1 until used; then one past last index |
1469 |
|
private int expectedModCount; // initialized when fence set |
1477 |
|
return hi; |
1478 |
|
} |
1479 |
|
|
1480 |
< |
public ArrayListSpliterator<E> trySplit() { |
1480 |
> |
public ArrayList<E>.ArrayListSpliterator trySplit() { |
1481 |
|
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
1482 |
< |
// ArrayListSpliterator could be used here as the source is already bound |
1482 |
> |
// ArrayListSpliterator can be used here as the source is already bound |
1483 |
|
return (lo >= mid) ? null : // divide range in half unless too small |
1484 |
< |
new ArrayListSpliterator<>(root, lo, index = mid, |
1294 |
< |
expectedModCount); |
1484 |
> |
root.new ArrayListSpliterator(lo, index = mid, expectedModCount); |
1485 |
|
} |
1486 |
|
|
1487 |
|
public boolean tryAdvance(Consumer<? super E> action) { |
1523 |
|
} |
1524 |
|
|
1525 |
|
public long estimateSize() { |
1526 |
< |
return (long) (getFence() - index); |
1526 |
> |
return getFence() - index; |
1527 |
|
} |
1528 |
|
|
1529 |
|
public int characteristics() { |
1533 |
|
} |
1534 |
|
} |
1535 |
|
|
1536 |
+ |
/** |
1537 |
+ |
* @throws NullPointerException {@inheritDoc} |
1538 |
+ |
*/ |
1539 |
|
@Override |
1540 |
|
public void forEach(Consumer<? super E> action) { |
1541 |
|
Objects.requireNonNull(action); |
1542 |
|
final int expectedModCount = modCount; |
1543 |
< |
@SuppressWarnings("unchecked") |
1351 |
< |
final E[] elementData = (E[]) this.elementData; |
1543 |
> |
final Object[] es = elementData; |
1544 |
|
final int size = this.size; |
1545 |
< |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1546 |
< |
action.accept(elementData[i]); |
1547 |
< |
} |
1356 |
< |
if (modCount != expectedModCount) { |
1545 |
> |
for (int i = 0; modCount == expectedModCount && i < size; i++) |
1546 |
> |
action.accept(elementAt(es, i)); |
1547 |
> |
if (modCount != expectedModCount) |
1548 |
|
throw new ConcurrentModificationException(); |
1358 |
– |
} |
1549 |
|
} |
1550 |
|
|
1551 |
|
/** |
1563 |
|
*/ |
1564 |
|
@Override |
1565 |
|
public Spliterator<E> spliterator() { |
1566 |
< |
return new ArrayListSpliterator<>(this, 0, -1, 0); |
1566 |
> |
return new ArrayListSpliterator(0, -1, 0); |
1567 |
|
} |
1568 |
|
|
1569 |
|
/** Index-based split-by-two, lazily initialized Spliterator */ |
1570 |
< |
static final class ArrayListSpliterator<E> implements Spliterator<E> { |
1570 |
> |
final class ArrayListSpliterator implements Spliterator<E> { |
1571 |
|
|
1572 |
|
/* |
1573 |
|
* If ArrayLists were immutable, or structurally immutable (no |
1601 |
|
* these streamlinings. |
1602 |
|
*/ |
1603 |
|
|
1414 |
– |
private final ArrayList<E> list; |
1604 |
|
private int index; // current index, modified on advance/split |
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 */ |
1609 |
< |
ArrayListSpliterator(ArrayList<E> list, int origin, int fence, |
1421 |
< |
int expectedModCount) { |
1422 |
< |
this.list = list; // OK if null unless traversed |
1608 |
> |
/** Creates new spliterator covering the given range. */ |
1609 |
> |
ArrayListSpliterator(int origin, int fence, int expectedModCount) { |
1610 |
|
this.index = origin; |
1611 |
|
this.fence = fence; |
1612 |
|
this.expectedModCount = expectedModCount; |
1614 |
|
|
1615 |
|
private int getFence() { // initialize fence to size on first use |
1616 |
|
int hi; // (a specialized variant appears in method forEach) |
1430 |
– |
ArrayList<E> lst; |
1617 |
|
if ((hi = fence) < 0) { |
1618 |
< |
if ((lst = list) == null) |
1619 |
< |
hi = fence = 0; |
1434 |
< |
else { |
1435 |
< |
expectedModCount = lst.modCount; |
1436 |
< |
hi = fence = lst.size; |
1437 |
< |
} |
1618 |
> |
expectedModCount = modCount; |
1619 |
> |
hi = fence = size; |
1620 |
|
} |
1621 |
|
return hi; |
1622 |
|
} |
1623 |
|
|
1624 |
< |
public ArrayListSpliterator<E> trySplit() { |
1624 |
> |
public ArrayListSpliterator trySplit() { |
1625 |
|
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
1626 |
|
return (lo >= mid) ? null : // divide range in half unless too small |
1627 |
< |
new ArrayListSpliterator<>(list, lo, index = mid, |
1446 |
< |
expectedModCount); |
1627 |
> |
new ArrayListSpliterator(lo, index = mid, expectedModCount); |
1628 |
|
} |
1629 |
|
|
1630 |
|
public boolean tryAdvance(Consumer<? super E> action) { |
1633 |
|
int hi = getFence(), i = index; |
1634 |
|
if (i < hi) { |
1635 |
|
index = i + 1; |
1636 |
< |
@SuppressWarnings("unchecked") E e = (E)list.elementData[i]; |
1636 |
> |
@SuppressWarnings("unchecked") E e = (E)elementData[i]; |
1637 |
|
action.accept(e); |
1638 |
< |
if (list.modCount != expectedModCount) |
1638 |
> |
if (modCount != expectedModCount) |
1639 |
|
throw new ConcurrentModificationException(); |
1640 |
|
return true; |
1641 |
|
} |
1644 |
|
|
1645 |
|
public void forEachRemaining(Consumer<? super E> action) { |
1646 |
|
int i, hi, mc; // hoist accesses and checks from loop |
1647 |
< |
ArrayList<E> lst; Object[] a; |
1647 |
> |
Object[] a; |
1648 |
|
if (action == null) |
1649 |
|
throw new NullPointerException(); |
1650 |
< |
if ((lst = list) != null && (a = lst.elementData) != null) { |
1650 |
> |
if ((a = elementData) != null) { |
1651 |
|
if ((hi = fence) < 0) { |
1652 |
< |
mc = lst.modCount; |
1653 |
< |
hi = lst.size; |
1652 |
> |
mc = modCount; |
1653 |
> |
hi = size; |
1654 |
|
} |
1655 |
|
else |
1656 |
|
mc = expectedModCount; |
1659 |
|
@SuppressWarnings("unchecked") E e = (E) a[i]; |
1660 |
|
action.accept(e); |
1661 |
|
} |
1662 |
< |
if (lst.modCount == mc) |
1662 |
> |
if (modCount == mc) |
1663 |
|
return; |
1664 |
|
} |
1665 |
|
} |
1667 |
|
} |
1668 |
|
|
1669 |
|
public long estimateSize() { |
1670 |
< |
return (long) (getFence() - index); |
1670 |
> |
return getFence() - index; |
1671 |
|
} |
1672 |
|
|
1673 |
|
public int characteristics() { |
1675 |
|
} |
1676 |
|
} |
1677 |
|
|
1678 |
+ |
// A tiny bit set implementation |
1679 |
+ |
|
1680 |
+ |
private static long[] nBits(int n) { |
1681 |
+ |
return new long[((n - 1) >> 6) + 1]; |
1682 |
+ |
} |
1683 |
+ |
private static void setBit(long[] bits, int i) { |
1684 |
+ |
bits[i >> 6] |= 1L << i; |
1685 |
+ |
} |
1686 |
+ |
private static boolean isClear(long[] bits, int i) { |
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); |
1696 |
+ |
} |
1697 |
+ |
|
1698 |
+ |
/** |
1699 |
+ |
* Removes all elements satisfying the given predicate, from index |
1700 |
+ |
* i (inclusive) to index end (exclusive). |
1701 |
+ |
*/ |
1702 |
+ |
boolean removeIf(Predicate<? super E> filter, int i, final int end) { |
1703 |
|
Objects.requireNonNull(filter); |
1704 |
< |
final int expectedModCount = modCount; |
1705 |
< |
final Object[] elementData = this.elementData; |
1706 |
< |
int r = 0, w = 0, remaining = size, deleted = 0; |
1707 |
< |
try { |
1708 |
< |
for (; remaining > 0; remaining--, r++) { |
1709 |
< |
@SuppressWarnings("unchecked") E e = (E) elementData[r]; |
1710 |
< |
if (filter.test(e)) |
1711 |
< |
deleted++; |
1712 |
< |
else { |
1713 |
< |
if (r != w) |
1714 |
< |
elementData[w] = e; |
1715 |
< |
w++; |
1716 |
< |
} |
1717 |
< |
} |
1704 |
> |
int expectedModCount = modCount; |
1705 |
> |
final Object[] es = elementData; |
1706 |
> |
// Optimize for initial run of survivors |
1707 |
> |
for (; i < end && !filter.test(elementAt(es, i)); i++) |
1708 |
> |
; |
1709 |
> |
// Tolerate predicates that reentrantly access the collection for |
1710 |
> |
// read (but writers still get CME), so traverse once to find |
1711 |
> |
// elements to delete, a second pass to physically expunge. |
1712 |
> |
if (i < end) { |
1713 |
> |
final int beg = i; |
1714 |
> |
final long[] deathRow = nBits(end - beg); |
1715 |
> |
deathRow[0] = 1L; // set bit 0 |
1716 |
> |
for (i = beg + 1; i < end; i++) |
1717 |
> |
if (filter.test(elementAt(es, i))) |
1718 |
> |
setBit(deathRow, i - beg); |
1719 |
|
if (modCount != expectedModCount) |
1720 |
|
throw new ConcurrentModificationException(); |
1721 |
< |
return deleted > 0; |
1722 |
< |
} catch (Throwable ex) { |
1723 |
< |
if (deleted > 0) |
1724 |
< |
for (; remaining > 0; remaining--, r++, w++) |
1725 |
< |
elementData[w] = elementData[r]; |
1726 |
< |
throw ex; |
1727 |
< |
} finally { |
1728 |
< |
if (deleted > 0) { |
1729 |
< |
modCount++; |
1730 |
< |
size -= deleted; |
1731 |
< |
while (--deleted >= 0) |
1732 |
< |
elementData[w++] = null; |
1733 |
< |
} |
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 |
> |
shiftTailOverGap(es, w, end); |
1727 |
> |
// checkInvariants(); |
1728 |
> |
return true; |
1729 |
> |
} else { |
1730 |
> |
if (modCount != expectedModCount) |
1731 |
> |
throw new ConcurrentModificationException(); |
1732 |
> |
// checkInvariants(); |
1733 |
> |
return false; |
1734 |
|
} |
1735 |
|
} |
1736 |
|
|
1737 |
|
@Override |
1533 |
– |
@SuppressWarnings("unchecked") |
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 int size = this.size; |
1746 |
< |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1747 |
< |
elementData[i] = operator.apply((E) elementData[i]); |
1748 |
< |
} |
1541 |
< |
if (modCount != expectedModCount) { |
1745 |
> |
final Object[] es = elementData; |
1746 |
> |
for (; modCount == expectedModCount && i < end; i++) |
1747 |
> |
es[i] = operator.apply(elementAt(es, i)); |
1748 |
> |
if (modCount != expectedModCount) |
1749 |
|
throw new ConcurrentModificationException(); |
1750 |
< |
} |
1544 |
< |
modCount++; |
1750 |
> |
// checkInvariants(); |
1751 |
|
} |
1752 |
|
|
1753 |
|
@Override |
1755 |
|
public void sort(Comparator<? super E> c) { |
1756 |
|
final int expectedModCount = modCount; |
1757 |
|
Arrays.sort((E[]) elementData, 0, size, c); |
1758 |
< |
if (modCount != expectedModCount) { |
1758 |
> |
if (modCount != expectedModCount) |
1759 |
|
throw new ConcurrentModificationException(); |
1554 |
– |
} |
1760 |
|
modCount++; |
1761 |
+ |
// checkInvariants(); |
1762 |
+ |
} |
1763 |
+ |
|
1764 |
+ |
void checkInvariants() { |
1765 |
+ |
// assert size >= 0; |
1766 |
+ |
// assert size == elementData.length || elementData[size] == null; |
1767 |
|
} |
1768 |
|
} |