--- jsr166/src/main/java/util/Vector.java 2016/11/04 02:56:17 1.31 +++ jsr166/src/main/java/util/Vector.java 2018/05/22 15:51:31 1.51 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1994, 2013, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1994, 2018, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -25,6 +25,9 @@ package java.util; +import java.io.IOException; +import java.io.ObjectInputStream; +import java.io.StreamCorruptedException; import java.util.function.Consumer; import java.util.function.Predicate; import java.util.function.UnaryOperator; @@ -70,7 +73,7 @@ import java.util.function.UnaryOperator; * *

As of the Java 2 platform v1.2, this class was retrofitted to * implement the {@link List} interface, making it a member of the - * + * * Java Collections Framework. Unlike the new collection * implementations, {@code Vector} is synchronized. If a thread-safe * implementation is not needed, it is recommended to use {@link @@ -306,8 +309,9 @@ public class Vector modCount++; if (newSize > elementData.length) grow(newSize); - for (int i = newSize; i < elementCount; i++) - elementData[i] = null; + final Object[] es = elementData; + for (int to = elementCount, i = newSize; i < to; i++) + es[i] = null; elementCount = newSize; } @@ -585,6 +589,7 @@ public class Vector modCount++; elementCount--; elementData[elementCount] = null; /* to let gc do its work */ + // checkInvariants(); } /** @@ -675,12 +680,10 @@ public class Vector * 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; - + final Object[] es = elementData; + for (int to = elementCount, i = elementCount = 0; i < to; i++) + es[i] = null; modCount++; - elementCount = 0; } /** @@ -693,7 +696,7 @@ public class Vector public synchronized Object clone() { try { @SuppressWarnings("unchecked") - Vector v = (Vector) super.clone(); + Vector v = (Vector) super.clone(); v.elementData = Arrays.copyOf(elementData, elementCount); v.modCount = 0; return v; @@ -759,6 +762,11 @@ public class Vector return (E) elementData[index]; } + @SuppressWarnings("unchecked") + static E elementAt(Object[] es, int index) { + return (E) es[index]; + } + /** * Returns the element at the specified position in this Vector. * @@ -805,6 +813,7 @@ public class Vector elementData = grow(); elementData[s] = e; elementCount = s + 1; + // checkInvariants(); } /** @@ -873,6 +882,7 @@ public class Vector numMoved); elementData[--elementCount] = null; // Let gc do its work + // checkInvariants(); return oldValue; } @@ -928,6 +938,7 @@ public class Vector elementData = grow(s + numNew); System.arraycopy(a, 0, elementData, s, numNew); elementCount = s + numNew; + // checkInvariants(); return true; } } @@ -978,43 +989,62 @@ public class Vector return bulkRemove(e -> !c.contains(e)); } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override public boolean removeIf(Predicate filter) { Objects.requireNonNull(filter); return bulkRemove(filter); } - @SuppressWarnings("unchecked") + // 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 filter) { int expectedModCount = modCount; final Object[] es = elementData; - final int size = elementCount; - final boolean modified; - int r; + final int end = elementCount; + int i; // Optimize for initial run of survivors - for (r = 0; r < size; r++) - if (filter.test((E) es[r])) - break; - if (modified = (r < size)) { - expectedModCount++; + 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(); modCount++; - int w = r++; - try { - for (E e; r < size; r++) - if (!filter.test(e = (E) es[r])) - es[w++] = e; - } catch (Throwable ex) { - // copy remaining elements - System.arraycopy(es, r, es, w, size - r); - w += size - r; - throw ex; - } finally { - Arrays.fill(es, elementCount = w, size, null); - } + int w = beg; + for (i = beg; i < end; i++) + if (isClear(deathRow, i - beg)) + es[w++] = es[i]; + for (i = elementCount = w; i < end; i++) + es[i] = null; + // checkInvariants(); + return true; + } else { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + // checkInvariants(); + return false; } - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - return modified; } /** @@ -1055,6 +1085,7 @@ public class Vector numMoved); System.arraycopy(a, 0, elementData, index, numNew); elementCount = s + numNew; + // checkInvariants(); return true; } @@ -1136,22 +1167,49 @@ public class Vector * (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); - - // Let gc do its work modCount++; - int newElementCount = elementCount - (toIndex-fromIndex); - while (elementCount != newElementCount) - elementData[--elementCount] = null; + shiftTailOverGap(elementData, fromIndex, toIndex); + // checkInvariants(); + } + + /** Erases the gap from lo to hi, by sliding down following elements. */ + private void shiftTailOverGap(Object[] es, int lo, int hi) { + System.arraycopy(es, hi, es, lo, elementCount - hi); + for (int to = elementCount, i = (elementCount -= hi - lo); i < to; i++) + es[i] = null; + } + + /** + * Loads a {@code Vector} instance from a stream + * (that is, deserializes it). + * This method performs checks to ensure the consistency + * of the fields. + * + * @param in the stream + * @throws java.io.IOException if an I/O error occurs + * @throws ClassNotFoundException if the stream contains data + * of a non-existing class + */ + private void readObject(ObjectInputStream in) + throws IOException, ClassNotFoundException { + ObjectInputStream.GetField gfields = in.readFields(); + int count = gfields.get("elementCount", 0); + Object[] data = (Object[])gfields.get("elementData", null); + if (count < 0 || data == null || count > data.length) { + throw new StreamCorruptedException("Inconsistent vector internals"); + } + elementCount = count; + elementData = data.clone(); } /** - * Save the state of the {@code Vector} instance to a stream (that - * is, serialize it). + * Saves the state of the {@code Vector} instance to a stream + * (that is, serializes it). * This method performs synchronization to ensure the consistency * of the serialized data. + * + * @param s the stream + * @throws java.io.IOException if an I/O error occurs */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { @@ -1253,14 +1311,11 @@ public class Vector 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; @@ -1327,34 +1382,37 @@ public class Vector } } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override public synchronized void forEach(Consumer 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(); - } + // checkInvariants(); } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override - @SuppressWarnings("unchecked") public synchronized void replaceAll(UnaryOperator 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++; + // checkInvariants(); } @SuppressWarnings("unchecked") @@ -1362,10 +1420,10 @@ public class Vector public synchronized void sort(Comparator c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, elementCount, c); - if (modCount != expectedModCount) { + if (modCount != expectedModCount) throw new ConcurrentModificationException(); - } modCount++; + // checkInvariants(); } /** @@ -1383,21 +1441,19 @@ public class Vector */ @Override public Spliterator spliterator() { - return new VectorSpliterator<>(this, null, 0, -1, 0); + return new VectorSpliterator(null, 0, -1, 0); } /** Similar to ArrayList Spliterator */ - static final class VectorSpliterator implements Spliterator { - private final Vector list; + final class VectorSpliterator implements Spliterator { private Object[] array; private int index; // current index, modified on advance/split 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 */ - VectorSpliterator(Vector list, Object[] array, int origin, int fence, + /** Creates new spliterator covering the given range. */ + VectorSpliterator(Object[] array, int origin, int fence, int expectedModCount) { - this.list = list; this.array = array; this.index = origin; this.fence = fence; @@ -1407,10 +1463,10 @@ public class Vector private int getFence() { // initialize on first use int hi; if ((hi = fence) < 0) { - synchronized (list) { - array = list.elementData; - expectedModCount = list.modCount; - hi = fence = list.elementCount; + synchronized (Vector.this) { + array = elementData; + expectedModCount = modCount; + hi = fence = elementCount; } } return hi; @@ -1419,19 +1475,17 @@ public class Vector public Spliterator trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : - new VectorSpliterator<>(list, array, lo, index = mid, - expectedModCount); + new VectorSpliterator(array, lo, index = mid, expectedModCount); } @SuppressWarnings("unchecked") public boolean tryAdvance(Consumer action) { + Objects.requireNonNull(action); int i; - if (action == null) - throw new NullPointerException(); if (getFence() > (i = index)) { index = i + 1; action.accept((E)array[i]); - if (list.modCount != expectedModCount) + if (modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } @@ -1440,28 +1494,14 @@ public class Vector @SuppressWarnings("unchecked") public void forEachRemaining(Consumer action) { - int i, hi; // hoist accesses and checks from loop - Vector lst; Object[] a; - if (action == null) - throw new NullPointerException(); - if ((lst = list) != null) { - if ((hi = fence) < 0) { - synchronized (lst) { - expectedModCount = lst.modCount; - a = array = lst.elementData; - hi = fence = lst.elementCount; - } - } - else - a = array; - if (a != null && (i = index) >= 0 && (index = hi) <= a.length) { - while (i < hi) - action.accept((E) a[i++]); - if (lst.modCount == expectedModCount) - return; - } - } - throw new ConcurrentModificationException(); + Objects.requireNonNull(action); + final int hi = getFence(); + final Object[] a = array; + int i; + for (i = index, index = hi; i < hi; i++) + action.accept((E) a[i]); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); } public long estimateSize() { @@ -1472,4 +1512,9 @@ public class Vector return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } } + + void checkInvariants() { + // assert elementCount >= 0; + // assert elementCount == elementData.length || elementData[elementCount] == null; + } }