CopyOnWriteArrayListpublic class CopyOnWriteArrayList extends Object implements RandomAccess, List, Cloneable, Serializable| A thread-safe variant of {@link java.util.ArrayList} in which all mutative
operations (add, set, and so on) are implemented by
making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient
than alternatives when traversal operations vastly outnumber
mutations, and is useful when you cannot or don't want to
synchronize traversals, yet need to preclude interference among
concurrent threads. The "snapshot" style iterator method uses a
reference to the state of the array at the point that the iterator
was created. This array never changes during the lifetime of the
iterator, so interference is impossible and the iterator is
guaranteed not to throw ConcurrentModificationException.
The iterator will not reflect additions, removals, or changes to
the list since the iterator was created. Element-changing
operations on iterators themselves (remove, set, and
add) are not supported. These methods throw
UnsupportedOperationException.
All elements are permitted, including null.
Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
{@code CopyOnWriteArrayList}
happen-before
actions subsequent to the access or removal of that element from
the {@code CopyOnWriteArrayList} in another thread.
This class is a member of the
Java Collections Framework. |
| Fields Summary |
|---|
| private static final long | serialVersionUID | | final transient ReentrantLock | lockThe lock protecting all mutators | | private volatile transient Object[] | arrayThe array, accessed only via getArray/setArray. | | private static final Unsafe | unsafe | | private static final long | lockOffset |
| Constructors Summary |
|---|
public CopyOnWriteArrayList()Creates an empty list.
setArray(new Object[0]);
| public CopyOnWriteArrayList(Collection c)Creates a list containing the elements of the specified
collection, in the order they are returned by the collection's
iterator.
Object[] elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
setArray(elements);
| public CopyOnWriteArrayList(E[] toCopyIn)Creates a list holding a copy of the given array.
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
|
| Methods Summary |
|---|
| public boolean | add(E e)Appends the specified element to the end of this list.
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
| | public void | add(int index, E element)Inserts the specified element at the specified position in this
list. Shifts the element currently at that position (if any) and
any subsequent elements to the right (adds one to their indices).
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
| | public boolean | addAll(java.util.Collection c)Appends all of the elements in the specified collection to the end
of this list, in the order that they are returned by the specified
collection's iterator.
Object[] cs = c.toArray();
if (cs.length == 0)
return false;
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + cs.length);
System.arraycopy(cs, 0, newElements, len, cs.length);
setArray(newElements);
return true;
} finally {
lock.unlock();
}
| | public boolean | addAll(int index, java.util.Collection c)Inserts all of the elements in the specified collection into this
list, starting at the specified position. Shifts the element
currently at that position (if any) and any subsequent elements to
the right (increases their indices). The new elements will appear
in this list in the order that they are returned by the
specified collection's iterator.
Object[] cs = c.toArray();
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
if (cs.length == 0)
return false;
int numMoved = len - index;
Object[] newElements;
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + cs.length);
else {
newElements = new Object[len + cs.length];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index,
newElements, index + cs.length,
numMoved);
}
System.arraycopy(cs, 0, newElements, index, cs.length);
setArray(newElements);
return true;
} finally {
lock.unlock();
}
| | public int | addAllAbsent(java.util.Collection c)Appends all of the elements in the specified collection that
are not already contained in this list, to the end of
this list, in the order that they are returned by the
specified collection's iterator.
Object[] cs = c.toArray();
if (cs.length == 0)
return 0;
Object[] uniq = new Object[cs.length];
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
int added = 0;
for (int i = 0; i < cs.length; ++i) { // scan for duplicates
Object e = cs[i];
if (indexOf(e, elements, 0, len) < 0 &&
indexOf(e, uniq, 0, added) < 0)
uniq[added++] = e;
}
if (added > 0) {
Object[] newElements = Arrays.copyOf(elements, len + added);
System.arraycopy(uniq, 0, newElements, len, added);
setArray(newElements);
}
return added;
} finally {
lock.unlock();
}
| | public boolean | addIfAbsent(E e)Append the element if not present.
final ReentrantLock lock = this.lock;
lock.lock();
try {
// Copy while checking if already present.
// This wins in the most common case where it is not present
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = new Object[len + 1];
for (int i = 0; i < len; ++i) {
if (eq(e, elements[i]))
return false; // exit, throwing away copy
else
newElements[i] = elements[i];
}
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
| | public void | clear()Removes all of the elements from this list.
The list will be empty after this call returns.
final ReentrantLock lock = this.lock;
lock.lock();
try {
setArray(new Object[0]);
} finally {
lock.unlock();
}
| | public java.lang.Object | clone()Returns a shallow copy of this list. (The elements themselves
are not copied.)
try {
CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
c.resetLock();
return c;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
| | public boolean | contains(java.lang.Object o)Returns true if this list contains the specified element.
More formally, returns true if and only if this list contains
at least one element e such that
(o==null ? e==null : o.equals(e)).
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length) >= 0;
| | public boolean | containsAll(java.util.Collection c)Returns true if this list contains all of the elements of the
specified collection.
Object[] elements = getArray();
int len = elements.length;
for (Object e : c) {
if (indexOf(e, elements, 0, len) < 0)
return false;
}
return true;
| | private static boolean | eq(java.lang.Object o1, java.lang.Object o2)Test for equality, coping with nulls.
return (o1 == null ? o2 == null : o1.equals(o2));
| | public boolean | equals(java.lang.Object o)Compares the specified object with this list for equality.
Returns {@code true} if the specified object is the same object
as this object, or if it is also a {@link List} and the sequence
of elements returned by an {@linkplain List#iterator() iterator}
over the specified list is the same as the sequence returned by
an iterator over this list. The two sequences are considered to
be the same if they have the same length and corresponding
elements at the same position in the sequence are equal.
Two elements {@code e1} and {@code e2} are considered
equal if {@code (e1==null ? e2==null : e1.equals(e2))}.
if (o == this)
return true;
if (!(o instanceof List))
return false;
List<?> list = (List<?>)(o);
Iterator<?> it = list.iterator();
Object[] elements = getArray();
int len = elements.length;
for (int i = 0; i < len; ++i)
if (!it.hasNext() || !eq(elements[i], it.next()))
return false;
if (it.hasNext())
return false;
return true;
| | public E | get(int index){@inheritDoc}
return (E)(getArray()[index]);
| | final java.lang.Object[] | getArray()Gets the array. Non-private so as to also be accessible
from CopyOnWriteArraySet class.
return array;
| | public int | hashCode()Returns the hash code value for this list.
This implementation uses the definition in {@link List#hashCode}.
int hashCode = 1;
Object[] elements = getArray();
int len = elements.length;
for (int i = 0; i < len; ++i) {
Object obj = elements[i];
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;
| | public int | indexOf(java.lang.Object o){@inheritDoc}
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length);
| | public int | indexOf(E e, int index)Returns the index of the first occurrence of the specified element in
this list, searching forwards from index, or returns -1 if
the element is not found.
More formally, returns the lowest index i such that
(i >= index && (e==null ? get(i)==null : e.equals(get(i)))),
or -1 if there is no such index.
Object[] elements = getArray();
return indexOf(e, elements, index, elements.length);
| | private static int | indexOf(java.lang.Object o, java.lang.Object[] elements, int index, int fence)static version of indexOf, to allow repeated calls without
needing to re-acquire array each time.
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
| | public boolean | isEmpty()Returns true if this list contains no elements.
return size() == 0;
| | public java.util.Iterator | iterator()Returns an iterator over the elements in this list in proper sequence.
The returned iterator provides a snapshot of the state of the list
when the iterator was constructed. No synchronization is needed while
traversing the iterator. The iterator does NOT support the
remove method.
return new COWIterator<E>(getArray(), 0);
| | private static int | lastIndexOf(java.lang.Object o, java.lang.Object[] elements, int index)static version of lastIndexOf.
if (o == null) {
for (int i = index; i >= 0; i--)
if (elements[i] == null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elements[i]))
return i;
}
return -1;
| | public int | lastIndexOf(java.lang.Object o){@inheritDoc}
Object[] elements = getArray();
return lastIndexOf(o, elements, elements.length - 1);
| | public int | lastIndexOf(E e, int index)Returns the index of the last occurrence of the specified element in
this list, searching backwards from index, or returns -1 if
the element is not found.
More formally, returns the highest index i such that
(i <= index && (e==null ? get(i)==null : e.equals(get(i)))),
or -1 if there is no such index.
Object[] elements = getArray();
return lastIndexOf(e, elements, index);
| | public java.util.ListIterator | listIterator(){@inheritDoc}
The returned iterator provides a snapshot of the state of the list
when the iterator was constructed. No synchronization is needed while
traversing the iterator. The iterator does NOT support the
remove, set or add methods.
return new COWIterator<E>(getArray(), 0);
| | public java.util.ListIterator | listIterator(int index){@inheritDoc}
The returned iterator provides a snapshot of the state of the list
when the iterator was constructed. No synchronization is needed while
traversing the iterator. The iterator does NOT support the
remove, set or add methods.
Object[] elements = getArray();
int len = elements.length;
if (index<0 || index>len)
throw new IndexOutOfBoundsException("Index: "+index);
return new COWIterator<E>(elements, index);
| | private void | readObject(java.io.ObjectInputStream s)Reconstitute the list from a stream (i.e., deserialize it).
// Read in size, and any hidden stuff
s.defaultReadObject();
// bind to new lock
resetLock();
// Read in array length and allocate array
int len = s.readInt();
Object[] elements = new Object[len];
// Read in all elements in the proper order.
for (int i = 0; i < len; i++)
elements[i] = s.readObject();
setArray(elements);
| | public E | remove(int index)Removes the element at the specified position in this list.
Shifts any subsequent elements to the left (subtracts one from their
indices). Returns the element that was removed from the list.
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object oldValue = elements[index];
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return (E)oldValue;
} finally {
lock.unlock();
}
| | public boolean | remove(java.lang.Object o)Removes the first occurrence of the specified element from this list,
if it is present. If this list does not contain the element, it is
unchanged. More formally, removes the element with the lowest index
i such that
(o==null ? get(i)==null : o.equals(get(i)))
(if such an element exists). Returns true if this list
contained the specified element (or equivalently, if this list
changed as a result of the call).
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// Copy while searching for element to remove
// This wins in the normal case of element being present
int newlen = len - 1;
Object[] newElements = new Object[newlen];
for (int i = 0; i < newlen; ++i) {
if (eq(o, elements[i])) {
// found one; copy remaining and exit
for (int k = i + 1; k < len; ++k)
newElements[k-1] = elements[k];
setArray(newElements);
return true;
} else
newElements[i] = elements[i];
}
// special handling for last cell
if (eq(o, elements[newlen])) {
setArray(newElements);
return true;
}
}
return false;
} finally {
lock.unlock();
}
| | public boolean | removeAll(java.util.Collection c)Removes from this list all of its elements that are contained in
the specified collection. This is a particularly expensive operation
in this class because of the need for an internal temporary array.
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// temp array holds those elements we know we want to keep
int newlen = 0;
Object[] temp = new Object[len];
for (int i = 0; i < len; ++i) {
Object element = elements[i];
if (!c.contains(element))
temp[newlen++] = element;
}
if (newlen != len) {
setArray(Arrays.copyOf(temp, newlen));
return true;
}
}
return false;
} finally {
lock.unlock();
}
| | private void | removeRange(int fromIndex, int toIndex)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 list by (toIndex - fromIndex) elements.
(If toIndex==fromIndex, this operation has no effect.)
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (fromIndex < 0 || fromIndex >= len ||
toIndex > len || toIndex < fromIndex)
throw new IndexOutOfBoundsException();
int newlen = len - (toIndex - fromIndex);
int numMoved = len - toIndex;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, newlen));
else {
Object[] newElements = new Object[newlen];
System.arraycopy(elements, 0, newElements, 0, fromIndex);
System.arraycopy(elements, toIndex, newElements,
fromIndex, numMoved);
setArray(newElements);
}
} finally {
lock.unlock();
}
| | private void | resetLock()
try {
lockOffset = unsafe.objectFieldOffset
(CopyOnWriteArrayList.class.getDeclaredField("lock"));
} catch (Exception ex) { throw new Error(ex); }
unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
| | public boolean | retainAll(java.util.Collection c)Retains only the elements in this list that are contained in the
specified collection. In other words, removes from this list all of
its elements that are not contained in the specified collection.
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// temp array holds those elements we know we want to keep
int newlen = 0;
Object[] temp = new Object[len];
for (int i = 0; i < len; ++i) {
Object element = elements[i];
if (c.contains(element))
temp[newlen++] = element;
}
if (newlen != len) {
setArray(Arrays.copyOf(temp, newlen));
return true;
}
}
return false;
} finally {
lock.unlock();
}
| | public E | set(int index, E element)Replaces the element at the specified position in this list with the
specified element.
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
Object oldValue = elements[index];
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return (E)oldValue;
} finally {
lock.unlock();
}
| | final void | setArray(java.lang.Object[] a)Sets the array.
array = a;
| | public int | size()Returns the number of elements in this list.
return getArray().length;
| | public java.util.List | subList(int fromIndex, int toIndex)Returns a view of the portion of this list between
fromIndex, inclusive, and toIndex, exclusive.
The returned list is backed by this list, so changes in the
returned list are reflected in this list, and vice-versa.
While mutative operations are supported, they are probably not
very useful for CopyOnWriteArrayLists.
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.)
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
throw new IndexOutOfBoundsException();
return new COWSubList<E>(this, fromIndex, toIndex);
} finally {
lock.unlock();
}
| | public java.lang.Object[] | toArray()Returns an array containing all of the elements in this list
in proper sequence (from first to last element).
The returned array will be "safe" in that no references to it are
maintained by this list. (In other words, this method must allocate
a new array). The caller is thus free to modify the returned array.
This method acts as bridge between array-based and collection-based
APIs.
Object[] elements = getArray();
return Arrays.copyOf(elements, elements.length);
| | public T[] | toArray(T[] a)Returns an array containing all of the elements in this list in
proper sequence (from first to last element); the runtime type of
the returned array is that of the specified array. If the list fits
in the specified array, it is returned therein. Otherwise, a new
array is allocated with the runtime type of the specified array and
the size of this list.
If this list fits in the specified array with room to spare
(i.e., the array has more elements than this list), the element in
the array immediately following the end of the list is set to
null. (This is useful in determining the length of this
list only if the caller knows that this list does not contain
any null elements.)
Like the {@link #toArray()} method, this method acts as bridge between
array-based and collection-based APIs. Further, this method allows
precise control over the runtime type of the output array, and may,
under certain circumstances, be used to save allocation costs.
Suppose x is a list known to contain only strings.
The following code can be used to dump the list into a newly
allocated array of String:
String[] y = x.toArray(new String[0]);
Note that toArray(new Object[0]) is identical in function to
toArray().
Object[] elements = getArray();
int len = elements.length;
if (a.length < len)
return (T[]) Arrays.copyOf(elements, len, a.getClass());
else {
System.arraycopy(elements, 0, a, 0, len);
if (a.length > len)
a[len] = null;
return a;
}
| | public java.lang.String | toString()Returns a string representation of this list. The string
representation consists of the string representations of the list's
elements in the order they are returned by its iterator, enclosed in
square brackets ("[]"). Adjacent elements are separated by
the characters ", " (comma and space). Elements are
converted to strings as by {@link String#valueOf(Object)}.
return Arrays.toString(getArray());
| | private void | writeObject(java.io.ObjectOutputStream s)Save the state of the list to a stream (i.e., serialize it).
// Write out element count, and any hidden stuff
s.defaultWriteObject();
Object[] elements = getArray();
int len = elements.length;
// Write out array length
s.writeInt(len);
// Write out all elements in the proper order.
for (int i = 0; i < len; i++)
s.writeObject(elements[i]);
|
|
