--- jsr166/src/main/java/util/Vector.java 2005/11/26 03:12:10 1.2 +++ jsr166/src/main/java/util/Vector.java 2006/05/28 23:36:29 1.13 @@ -1,34 +1,29 @@ /* * %W% %E% * - * Copyright 2005 Sun Microsystems, Inc. All rights reserved. + * Copyright 2006 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; -import java.util.*; // for javadoc (till 6280605 is fixed) /** * The Vector class implements a growable array of * objects. Like an array, it contains components that can be * accessed using an integer index. However, the size of a * Vector can grow or shrink as needed to accommodate - * adding and removing items after the Vector has been created.

+ * adding and removing items after the Vector has been created. * - * Each vector tries to optimize storage management by maintaining a + *

Each vector tries to optimize storage management by maintaining a * capacity and a capacityIncrement. The * capacity is always at least as large as the vector * size; it is usually larger because as components are added to the * vector, the vector's storage increases in chunks the size of * capacityIncrement. An application can increase the * capacity of a vector before inserting a large number of - * components; this reduces the amount of incremental reallocation.

+ * components; this reduces the amount of incremental reallocation. * - * As of the Java 2 platform v1.2, this class has been retrofitted to - * implement List, so that it becomes a part of Java's collection framework. - * Unlike the new collection implementations, Vector is synchronized.

- * - * The Iterators returned by Vector's iterator and listIterator + *

The Iterators returned by Vector's iterator and listIterator * methods are fail-fast: if the Vector is structurally modified * at any time after the Iterator is created, in any way except through the * Iterator's own remove or add methods, the Iterator will throw a @@ -44,11 +39,13 @@ import java.util.*; // for javadoc (till * throw ConcurrentModificationException on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators - * should be used only to detect bugs.

+ * should be used only to detect bugs. * - * This class is a member of the - * - * Java Collections Framework. + *

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. * * @author Lee Boynton * @author Jonathan Payne @@ -147,13 +144,11 @@ public class Vector * @since 1.2 */ public Vector(Collection c) { - Object[] a = c.toArray(); - elementCount = a.length; - // If c.toArray incorrectly doesn't return Object[], copy it. - if (a.getClass() == Object[].class) - elementData = a; - else - elementData = Arrays.copyOf(a, a.length, Object[].class); + elementData = c.toArray(); + elementCount = elementData.length; + // c.toArray might (incorrectly) not return Object[] (see 6260652) + if (elementData.getClass() != Object[].class) + elementData = Arrays.copyOf(elementData, elementCount, Object[].class); } /** @@ -957,49 +952,10 @@ public class Vector } /** - * Returns a view of the portion of this List between fromIndex, - * inclusive, and toIndex, exclusive. (If fromIndex and toIndex are - * equal, the returned List is empty.) The returned List is backed by this - * List, so changes in the returned List are reflected in this List, and - * vice-versa. The returned List supports all of the optional List - * operations supported by this List.

- * - * This method eliminates the need for explicit range operations (of - * the sort that commonly exist for arrays). Any operation that expects - * a List can be used as a range operation by operating on a subList view - * instead of a whole List. For example, the following idiom - * removes a range of elements from a List: - * 

-     *	    list.subList(from, to).clear();
-     *
- * Similar idioms may be constructed for indexOf and lastIndexOf, - * and all of the algorithms in the Collections class can be applied to - * a subList.

- * - * The semantics of the List returned by this method become undefined if - * the backing list (i.e., this List) is structurally modified in - * any way other than via the returned List. (Structural modifications are - * those that change the size of the List, or otherwise perturb it in such - * a fashion that iterations in progress may yield incorrect results.) - * - * @param fromIndex low endpoint (inclusive) of the subList - * @param toIndex high endpoint (exclusive) of the subList - * @return a view of the specified range within this List - * @throws IndexOutOfBoundsException endpoint index value out of range - * (fromIndex < 0 || toIndex > size) - * @throws IllegalArgumentException endpoint indices out of order - * (fromIndex > toIndex) - */ - public synchronized List subList(int fromIndex, int toIndex) { - return Collections.synchronizedList(super.subList(fromIndex, toIndex), - this); - } - - /** * Removes from this List all of the elements whose index is between * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding * elements to the left (reduces their index). - * This call shortens the ArrayList by (toIndex - fromIndex) elements. (If + * This call shortens the Vector by (toIndex - fromIndex) elements. (If * toIndex==fromIndex, this operation has no effect.) * * @param fromIndex index of first element to be removed @@ -1031,28 +987,34 @@ public class Vector /** * Returns a list-iterator of the elements in this list (in proper * sequence), starting at the specified position in the list. - * Obeys the general contract of List.listIterator(int).

+ * Obeys the general contract of {@link List#listIterator(int)}. * - * The list-iterator is fail-fast: if the list is structurally + *

The list-iterator is fail-fast: if the list is structurally * modified at any time after the Iterator is created, in any way except - * through the list-iterator's own remove or add + * through the list-iterator's own {@code remove} or {@code add} * methods, the list-iterator will throw a - * ConcurrentModificationException. Thus, in the face of + * {@code ConcurrentModificationException}. Thus, in the face of * concurrent modification, the iterator fails quickly and cleanly, rather * than risking arbitrary, non-deterministic behavior at an undetermined * time in the future. * * @param index index of the first element to be returned from the - * list-iterator (by a call to next) - * @return a ListIterator of the elements in this list (in proper + * list-iterator (by a call to {@link ListIterator#next}) + * @return a list-iterator of the elements in this list (in proper * sequence), starting at the specified position in the list * @throws IndexOutOfBoundsException {@inheritDoc} - * @see List#listIterator(int) */ public synchronized ListIterator listIterator(int index) { if (index < 0 || index > elementCount) throw new IndexOutOfBoundsException("Index: "+index); - return new VectorIterator(index); + return new VectorIterator(index, elementCount); + } + + /** + * {@inheritDoc} + */ + public synchronized ListIterator listIterator() { + return new VectorIterator(0, elementCount); } /** @@ -1061,26 +1023,45 @@ public class Vector * @return an iterator over the elements in this list in proper sequence */ public synchronized Iterator iterator() { - return new VectorIterator(0); + return new VectorIterator(0, elementCount); } /** - * A streamlined version of AbstractList.Itr. + * Helper method to access array elements under synchronization by + * iterators. The caller performs index check with respect to + * expected bounds, so errors accessing the element are reported + * as ConcurrentModificationExceptions. */ - final class VectorIterator implements ListIterator { - int cursor; // index of next element to return; - int lastRet; // index of last element, or -1 if no such - int expectedModCount; // to check for CME + final synchronized Object iteratorGet(int index, int expectedModCount) { + if (modCount == expectedModCount) { + try { + return elementData[index]; + } catch(IndexOutOfBoundsException fallThrough) { + } + } + throw new ConcurrentModificationException(); + } - VectorIterator(int index) { - cursor = index; - lastRet = -1; - expectedModCount = modCount; + /** + * Streamlined specialization of AbstractList version of iterator. + * Locally perfroms bounds checks, but relies on outer Vector + * to access elements under synchronization. + */ + private final class VectorIterator implements ListIterator { + int cursor; // Index of next element to return; + int fence; // Upper bound on cursor (cache of size()) + int lastRet; // Index of last element, or -1 if no such + int expectedModCount; // To check for CME + + VectorIterator(int index, int fence) { + this.cursor = index; + this.fence = fence; + this.lastRet = -1; + this.expectedModCount = Vector.this.modCount; } public boolean hasNext() { - // Racy but within spec and backwards-compatible - return cursor < elementCount; + return cursor < fence; } public boolean hasPrevious() { @@ -1096,80 +1077,382 @@ public class Vector } public E next() { - synchronized(Vector.this) { - if (expectedModCount == modCount) { - int i = cursor; - if (i < elementCount) { - try { - E e = (E)elementData[i]; - lastRet = i; - cursor = i + 1; - return e; - } catch (IndexOutOfBoundsException fallthrough) { - } - } - } - // Prefer reporting CME if applicable on failures - if (expectedModCount == modCount) - throw new NoSuchElementException(); - throw new ConcurrentModificationException(); - } + int i = cursor; + if (i >= fence) + throw new NoSuchElementException(); + Object next = Vector.this.iteratorGet(i, expectedModCount); + lastRet = i; + cursor = i + 1; + return (E)next; } public E previous() { - synchronized(Vector.this) { - if (expectedModCount == modCount) { - int i = cursor - 1; - if (i < elementCount) { - try { - E e = (E)elementData[i]; - lastRet = i; - cursor = i; - return e; - } catch (IndexOutOfBoundsException fallthrough) { - } - } - } - if (expectedModCount == modCount) - throw new NoSuchElementException(); - throw new ConcurrentModificationException(); - } + int i = cursor - 1; + if (i < 0) + throw new NoSuchElementException(); + Object prev = Vector.this.iteratorGet(i, expectedModCount); + lastRet = i; + cursor = i; + return (E)prev; } - public void remove() { + public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); - synchronized(Vector.this) { - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - Vector.this.remove(lastRet); - if (lastRet < cursor) - cursor--; - lastRet = -1; - expectedModCount = modCount; - } + if (Vector.this.modCount != expectedModCount) + throw new ConcurrentModificationException(); + try { + Vector.this.set(lastRet, e); + expectedModCount = Vector.this.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } } - public void set(E e) { - if (lastRet < 0) + public void remove() { + int i = lastRet; + if (i < 0) throw new IllegalStateException(); - synchronized(Vector.this) { - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - Vector.this.set(lastRet, e); - expectedModCount = modCount; - } + if (Vector.this.modCount != expectedModCount) + throw new ConcurrentModificationException(); + try { + Vector.this.remove(i); + if (i < cursor) + cursor--; + lastRet = -1; + fence = Vector.this.size(); + expectedModCount = Vector.this.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } } public void add(E e) { - synchronized(Vector.this) { - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - Vector.this.add(cursor++, e); + if (Vector.this.modCount != expectedModCount) + throw new ConcurrentModificationException(); + try { + int i = cursor; + Vector.this.add(i, e); + cursor = i + 1; lastRet = -1; - expectedModCount = modCount; - } + fence = Vector.this.size(); + expectedModCount = Vector.this.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } } } + /** + * Returns a view of the portion of this List between fromIndex, + * inclusive, and toIndex, exclusive. (If fromIndex and toIndex are + * equal, the returned List is empty.) The returned List is backed by this + * List, so changes in the returned List are reflected in this List, and + * vice-versa. The returned List supports all of the optional List + * operations supported by this List.

+ * + * This method eliminates the need for explicit range operations (of + * the sort that commonly exist for arrays). Any operation that expects + * a List can be used as a range operation by operating on a subList view + * instead of a whole List. For example, the following idiom + * removes a range of elements from a List: + * 

+     *	    list.subList(from, to).clear();
+     *
+ * Similar idioms may be constructed for indexOf and lastIndexOf, + * and all of the algorithms in the Collections class can be applied to + * a subList.

+ * + * The semantics of the List returned by this method become undefined if + * the backing list (i.e., this List) is structurally modified in + * any way other than via the returned List. (Structural modifications are + * those that change the size of the List, or otherwise perturb it in such + * a fashion that iterations in progress may yield incorrect results.) + * + * @param fromIndex low endpoint (inclusive) of the subList + * @param toIndex high endpoint (exclusive) of the subList + * @return a view of the specified range within this List + * @throws IndexOutOfBoundsException endpoint index value out of range + * (fromIndex < 0 || toIndex > size) + * @throws IllegalArgumentException endpoint indices out of order + * (fromIndex > toIndex) + */ + public synchronized List subList(int fromIndex, int toIndex) { + return new VectorSubList(this, this, fromIndex, fromIndex, toIndex); + } + + /** + * This class specializes the AbstractList version of SubList to + * avoid the double-indirection penalty that would arise using a + * synchronized wrapper, as well as to avoid some unnecessary + * checks in sublist iterators. + */ + private static final class VectorSubList extends AbstractList implements RandomAccess { + final Vector base; // base list + final AbstractList parent; // Creating list + final int baseOffset; // index wrt Vector + final int parentOffset; // index wrt parent + int length; // length of sublist + + VectorSubList(Vector base, AbstractList parent, int baseOffset, + int fromIndex, int toIndex) { + if (fromIndex < 0) + throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); + if (toIndex > parent.size()) + throw new IndexOutOfBoundsException("toIndex = " + toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex(" + fromIndex + + ") > toIndex(" + toIndex + ")"); + + this.base = base; + this.parent = parent; + this.baseOffset = baseOffset; + this.parentOffset = fromIndex; + this.length = toIndex - fromIndex; + modCount = base.modCount; + } + + /** + * Returns an IndexOutOfBoundsException with nicer message + */ + private IndexOutOfBoundsException indexError(int index) { + return new IndexOutOfBoundsException("Index: " + index + + ", Size: " + length); + } + + public E set(int index, E element) { + synchronized(base) { + if (index < 0 || index >= length) + throw indexError(index); + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + return base.set(index + baseOffset, element); + } + } + + public E get(int index) { + synchronized(base) { + if (index < 0 || index >= length) + throw indexError(index); + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + return base.get(index + baseOffset); + } + } + + public int size() { + synchronized(base) { + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + return length; + } + } + + public void add(int index, E element) { + synchronized(base) { + if (index < 0 || index > length) + throw indexError(index); + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + parent.add(index + parentOffset, element); + length++; + modCount = base.modCount; + } + } + + public E remove(int index) { + synchronized(base) { + if (index < 0 || index >= length) + throw indexError(index); + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + E result = parent.remove(index + parentOffset); + length--; + modCount = base.modCount; + return result; + } + } + + protected void removeRange(int fromIndex, int toIndex) { + synchronized(base) { + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + parent.removeRange(fromIndex + parentOffset, + toIndex + parentOffset); + length -= (toIndex-fromIndex); + modCount = base.modCount; + } + } + + public boolean addAll(Collection c) { + return addAll(length, c); + } + + public boolean addAll(int index, Collection c) { + synchronized(base) { + if (index < 0 || index > length) + throw indexError(index); + int cSize = c.size(); + if (cSize==0) + return false; + + if (base.modCount != modCount) + throw new ConcurrentModificationException(); + parent.addAll(parentOffset + index, c); + modCount = base.modCount; + length += cSize; + return true; + } + } + + public boolean equals(Object o) { + synchronized(base) {return super.equals(o);} + } + + public int hashCode() { + synchronized(base) {return super.hashCode();} + } + + public int indexOf(Object o) { + synchronized(base) {return super.indexOf(o);} + } + + public int lastIndexOf(Object o) { + synchronized(base) {return super.lastIndexOf(o);} + } + + public List subList(int fromIndex, int toIndex) { + return new VectorSubList(base, this, fromIndex + baseOffset, + fromIndex, toIndex); + } + + public Iterator iterator() { + synchronized(base) { + return new VectorSubListIterator(this, 0); + } + } + + public synchronized ListIterator listIterator() { + synchronized(base) { + return new VectorSubListIterator(this, 0); + } + } + + public ListIterator listIterator(int index) { + synchronized(base) { + if (index < 0 || index > length) + throw indexError(index); + return new VectorSubListIterator(this, index); + } + } + + /** + * Same idea as VectorIterator, except routing structural + * change operations through the sublist. + */ + private static final class VectorSubListIterator implements ListIterator { + final Vector base; // base list + final VectorSubList outer; // Sublist creating this iteraor + final int offset; // cursor offset wrt base + int cursor; // Current index + int fence; // Upper bound on cursor + int lastRet; // Index of returned element, or -1 + int expectedModCount; // Expected modCount of base Vector + + VectorSubListIterator(VectorSubList list, int index) { + this.lastRet = -1; + this.cursor = index; + this.outer = list; + this.offset = list.baseOffset; + this.fence = list.length; + this.base = list.base; + this.expectedModCount = base.modCount; + } + + public boolean hasNext() { + return cursor < fence; + } + + public boolean hasPrevious() { + return cursor > 0; + } + + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor - 1; + } + + public E next() { + int i = cursor; + if (cursor >= fence) + throw new NoSuchElementException(); + Object next = base.iteratorGet(i + offset, expectedModCount); + lastRet = i; + cursor = i + 1; + return (E)next; + } + + public E previous() { + int i = cursor - 1; + if (i < 0) + throw new NoSuchElementException(); + Object prev = base.iteratorGet(i + offset, expectedModCount); + lastRet = i; + cursor = i; + return (E)prev; + } + + public void set(E e) { + if (lastRet < 0) + throw new IllegalStateException(); + if (base.modCount != expectedModCount) + throw new ConcurrentModificationException(); + try { + outer.set(lastRet, e); + expectedModCount = base.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void remove() { + int i = lastRet; + if (i < 0) + throw new IllegalStateException(); + if (base.modCount != expectedModCount) + throw new ConcurrentModificationException(); + try { + outer.remove(i); + if (i < cursor) + cursor--; + lastRet = -1; + fence = outer.length; + expectedModCount = base.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void add(E e) { + if (base.modCount != expectedModCount) + throw new ConcurrentModificationException(); + try { + int i = cursor; + outer.add(i, e); + cursor = i + 1; + lastRet = -1; + fence = outer.length; + expectedModCount = base.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + } + } } + + +