--- a/jdk/src/java.base/share/classes/java/util/Vector.java Mon Nov 28 23:33:25 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/Vector.java Mon Nov 28 23:36:11 2016 -0800
@@ -513,7 +513,7 @@
* Returns the last component of the vector.
*
* @return the last component of the vector, i.e., the component at index
- * <code>size() - 1</code>.
+ * {@code size() - 1}
* @throws NoSuchElementException if this vector is empty
*/
public synchronized E lastElement() {
@@ -675,10 +675,7 @@
* method (which is part of the {@link List} interface).
*/
public synchronized void removeAllElements() {
- // Let gc do its work
- for (int i = 0; i < elementCount; i++)
- elementData[i] = null;
-
+ Arrays.fill(elementData, 0, elementCount, null);
modCount++;
elementCount = 0;
}
@@ -693,7 +690,7 @@
public synchronized Object clone() {
try {
@SuppressWarnings("unchecked")
- Vector<E> v = (Vector<E>) super.clone();
+ Vector<E> v = (Vector<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, elementCount);
v.modCount = 0;
return v;
@@ -759,6 +756,11 @@
return (E) elementData[index];
}
+ @SuppressWarnings("unchecked")
+ static <E> E elementAt(Object[] es, int index) {
+ return (E) es[index];
+ }
+
/**
* Returns the element at the specified position in this Vector.
*
@@ -855,10 +857,10 @@
* Shifts any subsequent elements to the left (subtracts one from their
* indices). Returns the element that was removed from the Vector.
*
+ * @param index the index of the element to be removed
+ * @return element that was removed
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
- * @param index the index of the element to be removed
- * @return element that was removed
* @since 1.2
*/
public synchronized E remove(int index) {
@@ -949,8 +951,9 @@
* or if the specified collection is null
* @since 1.2
*/
- public synchronized boolean removeAll(Collection<?> c) {
- return super.removeAll(c);
+ public boolean removeAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
}
/**
@@ -972,8 +975,62 @@
* or if the specified collection is null
* @since 1.2
*/
- public synchronized boolean retainAll(Collection<?> c) {
- return super.retainAll(c);
+ public boolean retainAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
+ }
+
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ // A tiny bit set implementation
+
+ private static long[] nBits(int n) {
+ return new long[((n - 1) >> 6) + 1];
+ }
+ private static void setBit(long[] bits, int i) {
+ bits[i >> 6] |= 1L << i;
+ }
+ private static boolean isClear(long[] bits, int i) {
+ return (bits[i >> 6] & (1L << i)) == 0;
+ }
+
+ private synchronized boolean bulkRemove(Predicate<? super E> filter) {
+ int expectedModCount = modCount;
+ final Object[] es = elementData;
+ final int end = elementCount;
+ int i;
+ // Optimize for initial run of survivors
+ for (i = 0; i < end && !filter.test(elementAt(es, i)); i++)
+ ;
+ // Tolerate predicates that reentrantly access the collection for
+ // read (but writers still get CME), so traverse once to find
+ // elements to delete, a second pass to physically expunge.
+ if (i < end) {
+ final int beg = i;
+ final long[] deathRow = nBits(end - beg);
+ deathRow[0] = 1L; // set bit 0
+ for (i = beg + 1; i < end; i++)
+ if (filter.test(elementAt(es, i)))
+ setBit(deathRow, i - beg);
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ expectedModCount++;
+ modCount++;
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ es[w++] = es[i];
+ Arrays.fill(es, elementCount = w, end, null);
+ return true;
+ } else {
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return false;
+ }
}
/**
@@ -1095,15 +1152,12 @@
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*/
protected synchronized void removeRange(int fromIndex, int toIndex) {
- int numMoved = elementCount - toIndex;
- System.arraycopy(elementData, toIndex, elementData, fromIndex,
- numMoved);
+ final Object[] es = elementData;
+ final int oldSize = elementCount;
+ System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
- // Let gc do its work
modCount++;
- int newElementCount = elementCount - (toIndex-fromIndex);
- while (elementCount != newElementCount)
- elementData[--elementCount] = null;
+ Arrays.fill(es, elementCount -= (toIndex - fromIndex), oldSize, null);
}
/**
@@ -1212,14 +1266,11 @@
if (i >= size) {
return;
}
- @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) Vector.this.elementData;
- if (i >= elementData.length) {
+ final Object[] es = elementData;
+ if (i >= es.length)
throw new ConcurrentModificationException();
- }
- while (i != size && modCount == expectedModCount) {
- action.accept(elementData[i++]);
- }
+ while (i < size && modCount == expectedModCount)
+ action.accept(elementAt(es, i++));
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
@@ -1290,73 +1341,24 @@
public synchronized void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
- @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) this.elementData;
- final int elementCount = this.elementCount;
- for (int i=0; modCount == expectedModCount && i < elementCount; i++) {
- action.accept(elementData[i]);
- }
- if (modCount != expectedModCount) {
+ final Object[] es = elementData;
+ final int size = elementCount;
+ for (int i = 0; modCount == expectedModCount && i < size; i++)
+ action.accept(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
}
@Override
- @SuppressWarnings("unchecked")
- public synchronized boolean removeIf(Predicate<? super E> filter) {
- Objects.requireNonNull(filter);
- // figure out which elements are to be removed
- // any exception thrown from the filter predicate at this stage
- // will leave the collection unmodified
- int removeCount = 0;
- final int size = elementCount;
- final BitSet removeSet = new BitSet(size);
- final int expectedModCount = modCount;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- @SuppressWarnings("unchecked")
- final E element = (E) elementData[i];
- if (filter.test(element)) {
- removeSet.set(i);
- removeCount++;
- }
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
-
- // shift surviving elements left over the spaces left by removed elements
- final boolean anyToRemove = removeCount > 0;
- if (anyToRemove) {
- final int newSize = size - removeCount;
- for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
- i = removeSet.nextClearBit(i);
- elementData[j] = elementData[i];
- }
- for (int k=newSize; k < size; k++) {
- elementData[k] = null; // Let gc do its work
- }
- elementCount = newSize;
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- modCount++;
- }
-
- return anyToRemove;
- }
-
- @Override
- @SuppressWarnings("unchecked")
public synchronized void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
+ final Object[] es = elementData;
final int size = elementCount;
- for (int i=0; modCount == expectedModCount && i < size; i++) {
- elementData[i] = operator.apply((E) elementData[i]);
- }
- if (modCount != expectedModCount) {
+ for (int i = 0; modCount == expectedModCount && i < size; i++)
+ es[i] = operator.apply(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
modCount++;
}
@@ -1365,9 +1367,8 @@
public synchronized void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, elementCount, c);
- if (modCount != expectedModCount) {
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
modCount++;
}
@@ -1397,7 +1398,7 @@
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
- /** Create new spliterator covering the given range */
+ /** Create new spliterator covering the given range */
VectorSpliterator(Vector<E> list, Object[] array, int origin, int fence,
int expectedModCount) {
this.list = list;
@@ -1410,7 +1411,7 @@
private int getFence() { // initialize on first use
int hi;
if ((hi = fence) < 0) {
- synchronized(list) {
+ synchronized (list) {
array = list.elementData;
expectedModCount = list.modCount;
hi = fence = list.elementCount;
@@ -1449,7 +1450,7 @@
throw new NullPointerException();
if ((lst = list) != null) {
if ((hi = fence) < 0) {
- synchronized(lst) {
+ synchronized (lst) {
expectedModCount = lst.modCount;
a = array = lst.elementData;
hi = fence = lst.elementCount;
@@ -1475,4 +1476,9 @@
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
+
+ void checkInvariants() {
+ // assert elementCount >= 0;
+ // assert elementCount == elementData.length || elementData[elementCount] == null;
+ }
}