0001 /*
0002 * Copyright 2003-2007 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 /*
0027 * Written by Doug Lea with assistance from members of JCP JSR-166
0028 * Expert Group. Adapted and released, under explicit permission,
0029 * from JDK ArrayList.java which carries the following copyright:
0030 *
0031 * Copyright 1997 by Sun Microsystems, Inc.,
0032 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
0033 * All rights reserved.
0034 */
0035
0036 package java.util.concurrent;
0037
0038 import java.util.*;
0039 import java.util.concurrent.locks.*;
0040 import sun.misc.Unsafe;
0041
0042 /**
0043 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
0044 * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
0045 * making a fresh copy of the underlying array.
0046 *
0047 * <p> This is ordinarily too costly, but may be <em>more</em> efficient
0048 * than alternatives when traversal operations vastly outnumber
0049 * mutations, and is useful when you cannot or don't want to
0050 * synchronize traversals, yet need to preclude interference among
0051 * concurrent threads. The "snapshot" style iterator method uses a
0052 * reference to the state of the array at the point that the iterator
0053 * was created. This array never changes during the lifetime of the
0054 * iterator, so interference is impossible and the iterator is
0055 * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
0056 * The iterator will not reflect additions, removals, or changes to
0057 * the list since the iterator was created. Element-changing
0058 * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
0059 * <tt>add</tt>) are not supported. These methods throw
0060 * <tt>UnsupportedOperationException</tt>.
0061 *
0062 * <p>All elements are permitted, including <tt>null</tt>.
0063 *
0064 * <p>Memory consistency effects: As with other concurrent
0065 * collections, actions in a thread prior to placing an object into a
0066 * {@code CopyOnWriteArrayList}
0067 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
0068 * actions subsequent to the access or removal of that element from
0069 * the {@code CopyOnWriteArrayList} in another thread.
0070 *
0071 * <p>This class is a member of the
0072 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0073 * Java Collections Framework</a>.
0074 *
0075 * @since 1.5
0076 * @author Doug Lea
0077 * @param <E> the type of elements held in this collection
0078 */
0079 public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess,
0080 Cloneable, java.io.Serializable {
0081 private static final long serialVersionUID = 8673264195747942595L;
0082
0083 /** The lock protecting all mutators */
0084 transient final ReentrantLock lock = new ReentrantLock();
0085
0086 /** The array, accessed only via getArray/setArray. */
0087 private volatile transient Object[] array;
0088
0089 /**
0090 * Gets the array. Non-private so as to also be accessible
0091 * from CopyOnWriteArraySet class.
0092 */
0093 final Object[] getArray() {
0094 return array;
0095 }
0096
0097 /**
0098 * Sets the array.
0099 */
0100 final void setArray(Object[] a) {
0101 array = a;
0102 }
0103
0104 /**
0105 * Creates an empty list.
0106 */
0107 public CopyOnWriteArrayList() {
0108 setArray(new Object[0]);
0109 }
0110
0111 /**
0112 * Creates a list containing the elements of the specified
0113 * collection, in the order they are returned by the collection's
0114 * iterator.
0115 *
0116 * @param c the collection of initially held elements
0117 * @throws NullPointerException if the specified collection is null
0118 */
0119 public CopyOnWriteArrayList(Collection<? extends E> c) {
0120 Object[] elements = c.toArray();
0121 // c.toArray might (incorrectly) not return Object[] (see 6260652)
0122 if (elements.getClass() != Object[].class)
0123 elements = Arrays.copyOf(elements, elements.length,
0124 Object[].class);
0125 setArray(elements);
0126 }
0127
0128 /**
0129 * Creates a list holding a copy of the given array.
0130 *
0131 * @param toCopyIn the array (a copy of this array is used as the
0132 * internal array)
0133 * @throws NullPointerException if the specified array is null
0134 */
0135 public CopyOnWriteArrayList(E[] toCopyIn) {
0136 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length,
0137 Object[].class));
0138 }
0139
0140 /**
0141 * Returns the number of elements in this list.
0142 *
0143 * @return the number of elements in this list
0144 */
0145 public int size() {
0146 return getArray().length;
0147 }
0148
0149 /**
0150 * Returns <tt>true</tt> if this list contains no elements.
0151 *
0152 * @return <tt>true</tt> if this list contains no elements
0153 */
0154 public boolean isEmpty() {
0155 return size() == 0;
0156 }
0157
0158 /**
0159 * Test for equality, coping with nulls.
0160 */
0161 private static boolean eq(Object o1, Object o2) {
0162 return (o1 == null ? o2 == null : o1.equals(o2));
0163 }
0164
0165 /**
0166 * static version of indexOf, to allow repeated calls without
0167 * needing to re-acquire array each time.
0168 * @param o element to search for
0169 * @param elements the array
0170 * @param index first index to search
0171 * @param fence one past last index to search
0172 * @return index of element, or -1 if absent
0173 */
0174 private static int indexOf(Object o, Object[] elements, int index,
0175 int fence) {
0176 if (o == null) {
0177 for (int i = index; i < fence; i++)
0178 if (elements[i] == null)
0179 return i;
0180 } else {
0181 for (int i = index; i < fence; i++)
0182 if (o.equals(elements[i]))
0183 return i;
0184 }
0185 return -1;
0186 }
0187
0188 /**
0189 * static version of lastIndexOf.
0190 * @param o element to search for
0191 * @param elements the array
0192 * @param index first index to search
0193 * @return index of element, or -1 if absent
0194 */
0195 private static int lastIndexOf(Object o, Object[] elements,
0196 int index) {
0197 if (o == null) {
0198 for (int i = index; i >= 0; i--)
0199 if (elements[i] == null)
0200 return i;
0201 } else {
0202 for (int i = index; i >= 0; i--)
0203 if (o.equals(elements[i]))
0204 return i;
0205 }
0206 return -1;
0207 }
0208
0209 /**
0210 * Returns <tt>true</tt> if this list contains the specified element.
0211 * More formally, returns <tt>true</tt> if and only if this list contains
0212 * at least one element <tt>e</tt> such that
0213 * <tt>(o==null ? e==null : o.equals(e))</tt>.
0214 *
0215 * @param o element whose presence in this list is to be tested
0216 * @return <tt>true</tt> if this list contains the specified element
0217 */
0218 public boolean contains(Object o) {
0219 Object[] elements = getArray();
0220 return indexOf(o, elements, 0, elements.length) >= 0;
0221 }
0222
0223 /**
0224 * {@inheritDoc}
0225 */
0226 public int indexOf(Object o) {
0227 Object[] elements = getArray();
0228 return indexOf(o, elements, 0, elements.length);
0229 }
0230
0231 /**
0232 * Returns the index of the first occurrence of the specified element in
0233 * this list, searching forwards from <tt>index</tt>, or returns -1 if
0234 * the element is not found.
0235 * More formally, returns the lowest index <tt>i</tt> such that
0236 * <tt>(i >= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
0237 * or -1 if there is no such index.
0238 *
0239 * @param e element to search for
0240 * @param index index to start searching from
0241 * @return the index of the first occurrence of the element in
0242 * this list at position <tt>index</tt> or later in the list;
0243 * <tt>-1</tt> if the element is not found.
0244 * @throws IndexOutOfBoundsException if the specified index is negative
0245 */
0246 public int indexOf(E e, int index) {
0247 Object[] elements = getArray();
0248 return indexOf(e, elements, index, elements.length);
0249 }
0250
0251 /**
0252 * {@inheritDoc}
0253 */
0254 public int lastIndexOf(Object o) {
0255 Object[] elements = getArray();
0256 return lastIndexOf(o, elements, elements.length - 1);
0257 }
0258
0259 /**
0260 * Returns the index of the last occurrence of the specified element in
0261 * this list, searching backwards from <tt>index</tt>, or returns -1 if
0262 * the element is not found.
0263 * More formally, returns the highest index <tt>i</tt> such that
0264 * <tt>(i <= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
0265 * or -1 if there is no such index.
0266 *
0267 * @param e element to search for
0268 * @param index index to start searching backwards from
0269 * @return the index of the last occurrence of the element at position
0270 * less than or equal to <tt>index</tt> in this list;
0271 * -1 if the element is not found.
0272 * @throws IndexOutOfBoundsException if the specified index is greater
0273 * than or equal to the current size of this list
0274 */
0275 public int lastIndexOf(E e, int index) {
0276 Object[] elements = getArray();
0277 return lastIndexOf(e, elements, index);
0278 }
0279
0280 /**
0281 * Returns a shallow copy of this list. (The elements themselves
0282 * are not copied.)
0283 *
0284 * @return a clone of this list
0285 */
0286 public Object clone() {
0287 try {
0288 CopyOnWriteArrayList c = (CopyOnWriteArrayList) (super
0289 .clone());
0290 c.resetLock();
0291 return c;
0292 } catch (CloneNotSupportedException e) {
0293 // this shouldn't happen, since we are Cloneable
0294 throw new InternalError();
0295 }
0296 }
0297
0298 /**
0299 * Returns an array containing all of the elements in this list
0300 * in proper sequence (from first to last element).
0301 *
0302 * <p>The returned array will be "safe" in that no references to it are
0303 * maintained by this list. (In other words, this method must allocate
0304 * a new array). The caller is thus free to modify the returned array.
0305 *
0306 * <p>This method acts as bridge between array-based and collection-based
0307 * APIs.
0308 *
0309 * @return an array containing all the elements in this list
0310 */
0311 public Object[] toArray() {
0312 Object[] elements = getArray();
0313 return Arrays.copyOf(elements, elements.length);
0314 }
0315
0316 /**
0317 * Returns an array containing all of the elements in this list in
0318 * proper sequence (from first to last element); the runtime type of
0319 * the returned array is that of the specified array. If the list fits
0320 * in the specified array, it is returned therein. Otherwise, a new
0321 * array is allocated with the runtime type of the specified array and
0322 * the size of this list.
0323 *
0324 * <p>If this list fits in the specified array with room to spare
0325 * (i.e., the array has more elements than this list), the element in
0326 * the array immediately following the end of the list is set to
0327 * <tt>null</tt>. (This is useful in determining the length of this
0328 * list <i>only</i> if the caller knows that this list does not contain
0329 * any null elements.)
0330 *
0331 * <p>Like the {@link #toArray()} method, this method acts as bridge between
0332 * array-based and collection-based APIs. Further, this method allows
0333 * precise control over the runtime type of the output array, and may,
0334 * under certain circumstances, be used to save allocation costs.
0335 *
0336 * <p>Suppose <tt>x</tt> is a list known to contain only strings.
0337 * The following code can be used to dump the list into a newly
0338 * allocated array of <tt>String</tt>:
0339 *
0340 * <pre>
0341 * String[] y = x.toArray(new String[0]);</pre>
0342 *
0343 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
0344 * <tt>toArray()</tt>.
0345 *
0346 * @param a the array into which the elements of the list are to
0347 * be stored, if it is big enough; otherwise, a new array of the
0348 * same runtime type is allocated for this purpose.
0349 * @return an array containing all the elements in this list
0350 * @throws ArrayStoreException if the runtime type of the specified array
0351 * is not a supertype of the runtime type of every element in
0352 * this list
0353 * @throws NullPointerException if the specified array is null
0354 */
0355 @SuppressWarnings("unchecked")
0356 public <T> T[] toArray(T a[]) {
0357 Object[] elements = getArray();
0358 int len = elements.length;
0359 if (a.length < len)
0360 return (T[]) Arrays.copyOf(elements, len, a.getClass());
0361 else {
0362 System.arraycopy(elements, 0, a, 0, len);
0363 if (a.length > len)
0364 a[len] = null;
0365 return a;
0366 }
0367 }
0368
0369 // Positional Access Operations
0370
0371 @SuppressWarnings("unchecked")
0372 private E get(Object[] a, int index) {
0373 return (E) a[index];
0374 }
0375
0376 /**
0377 * {@inheritDoc}
0378 *
0379 * @throws IndexOutOfBoundsException {@inheritDoc}
0380 */
0381 public E get(int index) {
0382 return get(getArray(), index);
0383 }
0384
0385 /**
0386 * Replaces the element at the specified position in this list with the
0387 * specified element.
0388 *
0389 * @throws IndexOutOfBoundsException {@inheritDoc}
0390 */
0391 public E set(int index, E element) {
0392 final ReentrantLock lock = this .lock;
0393 lock.lock();
0394 try {
0395 Object[] elements = getArray();
0396 E oldValue = get(elements, index);
0397
0398 if (oldValue != element) {
0399 int len = elements.length;
0400 Object[] newElements = Arrays.copyOf(elements, len);
0401 newElements[index] = element;
0402 setArray(newElements);
0403 } else {
0404 // Not quite a no-op; ensures volatile write semantics
0405 setArray(elements);
0406 }
0407 return oldValue;
0408 } finally {
0409 lock.unlock();
0410 }
0411 }
0412
0413 /**
0414 * Appends the specified element to the end of this list.
0415 *
0416 * @param e element to be appended to this list
0417 * @return <tt>true</tt> (as specified by {@link Collection#add})
0418 */
0419 public boolean add(E e) {
0420 final ReentrantLock lock = this .lock;
0421 lock.lock();
0422 try {
0423 Object[] elements = getArray();
0424 int len = elements.length;
0425 Object[] newElements = Arrays.copyOf(elements, len + 1);
0426 newElements[len] = e;
0427 setArray(newElements);
0428 return true;
0429 } finally {
0430 lock.unlock();
0431 }
0432 }
0433
0434 /**
0435 * Inserts the specified element at the specified position in this
0436 * list. Shifts the element currently at that position (if any) and
0437 * any subsequent elements to the right (adds one to their indices).
0438 *
0439 * @throws IndexOutOfBoundsException {@inheritDoc}
0440 */
0441 public void add(int index, E element) {
0442 final ReentrantLock lock = this .lock;
0443 lock.lock();
0444 try {
0445 Object[] elements = getArray();
0446 int len = elements.length;
0447 if (index > len || index < 0)
0448 throw new IndexOutOfBoundsException("Index: " + index
0449 + ", Size: " + len);
0450 Object[] newElements;
0451 int numMoved = len - index;
0452 if (numMoved == 0)
0453 newElements = Arrays.copyOf(elements, len + 1);
0454 else {
0455 newElements = new Object[len + 1];
0456 System.arraycopy(elements, 0, newElements, 0, index);
0457 System.arraycopy(elements, index, newElements,
0458 index + 1, numMoved);
0459 }
0460 newElements[index] = element;
0461 setArray(newElements);
0462 } finally {
0463 lock.unlock();
0464 }
0465 }
0466
0467 /**
0468 * Removes the element at the specified position in this list.
0469 * Shifts any subsequent elements to the left (subtracts one from their
0470 * indices). Returns the element that was removed from the list.
0471 *
0472 * @throws IndexOutOfBoundsException {@inheritDoc}
0473 */
0474 public E remove(int index) {
0475 final ReentrantLock lock = this .lock;
0476 lock.lock();
0477 try {
0478 Object[] elements = getArray();
0479 int len = elements.length;
0480 E oldValue = get(elements, index);
0481 int numMoved = len - index - 1;
0482 if (numMoved == 0)
0483 setArray(Arrays.copyOf(elements, len - 1));
0484 else {
0485 Object[] newElements = new Object[len - 1];
0486 System.arraycopy(elements, 0, newElements, 0, index);
0487 System.arraycopy(elements, index + 1, newElements,
0488 index, numMoved);
0489 setArray(newElements);
0490 }
0491 return oldValue;
0492 } finally {
0493 lock.unlock();
0494 }
0495 }
0496
0497 /**
0498 * Removes the first occurrence of the specified element from this list,
0499 * if it is present. If this list does not contain the element, it is
0500 * unchanged. More formally, removes the element with the lowest index
0501 * <tt>i</tt> such that
0502 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
0503 * (if such an element exists). Returns <tt>true</tt> if this list
0504 * contained the specified element (or equivalently, if this list
0505 * changed as a result of the call).
0506 *
0507 * @param o element to be removed from this list, if present
0508 * @return <tt>true</tt> if this list contained the specified element
0509 */
0510 public boolean remove(Object o) {
0511 final ReentrantLock lock = this .lock;
0512 lock.lock();
0513 try {
0514 Object[] elements = getArray();
0515 int len = elements.length;
0516 if (len != 0) {
0517 // Copy while searching for element to remove
0518 // This wins in the normal case of element being present
0519 int newlen = len - 1;
0520 Object[] newElements = new Object[newlen];
0521
0522 for (int i = 0; i < newlen; ++i) {
0523 if (eq(o, elements[i])) {
0524 // found one; copy remaining and exit
0525 for (int k = i + 1; k < len; ++k)
0526 newElements[k - 1] = elements[k];
0527 setArray(newElements);
0528 return true;
0529 } else
0530 newElements[i] = elements[i];
0531 }
0532
0533 // special handling for last cell
0534 if (eq(o, elements[newlen])) {
0535 setArray(newElements);
0536 return true;
0537 }
0538 }
0539 return false;
0540 } finally {
0541 lock.unlock();
0542 }
0543 }
0544
0545 /**
0546 * Removes from this list all of the elements whose index is between
0547 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
0548 * Shifts any succeeding elements to the left (reduces their index).
0549 * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
0550 * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
0551 *
0552 * @param fromIndex index of first element to be removed
0553 * @param toIndex index after last element to be removed
0554 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
0555 * (@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
0556 */
0557 private void removeRange(int fromIndex, int toIndex) {
0558 final ReentrantLock lock = this .lock;
0559 lock.lock();
0560 try {
0561 Object[] elements = getArray();
0562 int len = elements.length;
0563
0564 if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
0565 throw new IndexOutOfBoundsException();
0566 int newlen = len - (toIndex - fromIndex);
0567 int numMoved = len - toIndex;
0568 if (numMoved == 0)
0569 setArray(Arrays.copyOf(elements, newlen));
0570 else {
0571 Object[] newElements = new Object[newlen];
0572 System
0573 .arraycopy(elements, 0, newElements, 0,
0574 fromIndex);
0575 System.arraycopy(elements, toIndex, newElements,
0576 fromIndex, numMoved);
0577 setArray(newElements);
0578 }
0579 } finally {
0580 lock.unlock();
0581 }
0582 }
0583
0584 /**
0585 * Append the element if not present.
0586 *
0587 * @param e element to be added to this list, if absent
0588 * @return <tt>true</tt> if the element was added
0589 */
0590 public boolean addIfAbsent(E e) {
0591 final ReentrantLock lock = this .lock;
0592 lock.lock();
0593 try {
0594 // Copy while checking if already present.
0595 // This wins in the most common case where it is not present
0596 Object[] elements = getArray();
0597 int len = elements.length;
0598 Object[] newElements = new Object[len + 1];
0599 for (int i = 0; i < len; ++i) {
0600 if (eq(e, elements[i]))
0601 return false; // exit, throwing away copy
0602 else
0603 newElements[i] = elements[i];
0604 }
0605 newElements[len] = e;
0606 setArray(newElements);
0607 return true;
0608 } finally {
0609 lock.unlock();
0610 }
0611 }
0612
0613 /**
0614 * Returns <tt>true</tt> if this list contains all of the elements of the
0615 * specified collection.
0616 *
0617 * @param c collection to be checked for containment in this list
0618 * @return <tt>true</tt> if this list contains all of the elements of the
0619 * specified collection
0620 * @throws NullPointerException if the specified collection is null
0621 * @see #contains(Object)
0622 */
0623 public boolean containsAll(Collection<?> c) {
0624 Object[] elements = getArray();
0625 int len = elements.length;
0626 for (Object e : c) {
0627 if (indexOf(e, elements, 0, len) < 0)
0628 return false;
0629 }
0630 return true;
0631 }
0632
0633 /**
0634 * Removes from this list all of its elements that are contained in
0635 * the specified collection. This is a particularly expensive operation
0636 * in this class because of the need for an internal temporary array.
0637 *
0638 * @param c collection containing elements to be removed from this list
0639 * @return <tt>true</tt> if this list changed as a result of the call
0640 * @throws ClassCastException if the class of an element of this list
0641 * is incompatible with the specified collection (optional)
0642 * @throws NullPointerException if this list contains a null element and the
0643 * specified collection does not permit null elements (optional),
0644 * or if the specified collection is null
0645 * @see #remove(Object)
0646 */
0647 public boolean removeAll(Collection<?> c) {
0648 final ReentrantLock lock = this .lock;
0649 lock.lock();
0650 try {
0651 Object[] elements = getArray();
0652 int len = elements.length;
0653 if (len != 0) {
0654 // temp array holds those elements we know we want to keep
0655 int newlen = 0;
0656 Object[] temp = new Object[len];
0657 for (int i = 0; i < len; ++i) {
0658 Object element = elements[i];
0659 if (!c.contains(element))
0660 temp[newlen++] = element;
0661 }
0662 if (newlen != len) {
0663 setArray(Arrays.copyOf(temp, newlen));
0664 return true;
0665 }
0666 }
0667 return false;
0668 } finally {
0669 lock.unlock();
0670 }
0671 }
0672
0673 /**
0674 * Retains only the elements in this list that are contained in the
0675 * specified collection. In other words, removes from this list all of
0676 * its elements that are not contained in the specified collection.
0677 *
0678 * @param c collection containing elements to be retained in this list
0679 * @return <tt>true</tt> if this list changed as a result of the call
0680 * @throws ClassCastException if the class of an element of this list
0681 * is incompatible with the specified collection (optional)
0682 * @throws NullPointerException if this list contains a null element and the
0683 * specified collection does not permit null elements (optional),
0684 * or if the specified collection is null
0685 * @see #remove(Object)
0686 */
0687 public boolean retainAll(Collection<?> c) {
0688 final ReentrantLock lock = this .lock;
0689 lock.lock();
0690 try {
0691 Object[] elements = getArray();
0692 int len = elements.length;
0693 if (len != 0) {
0694 // temp array holds those elements we know we want to keep
0695 int newlen = 0;
0696 Object[] temp = new Object[len];
0697 for (int i = 0; i < len; ++i) {
0698 Object element = elements[i];
0699 if (c.contains(element))
0700 temp[newlen++] = element;
0701 }
0702 if (newlen != len) {
0703 setArray(Arrays.copyOf(temp, newlen));
0704 return true;
0705 }
0706 }
0707 return false;
0708 } finally {
0709 lock.unlock();
0710 }
0711 }
0712
0713 /**
0714 * Appends all of the elements in the specified collection that
0715 * are not already contained in this list, to the end of
0716 * this list, in the order that they are returned by the
0717 * specified collection's iterator.
0718 *
0719 * @param c collection containing elements to be added to this list
0720 * @return the number of elements added
0721 * @throws NullPointerException if the specified collection is null
0722 * @see #addIfAbsent(Object)
0723 */
0724 public int addAllAbsent(Collection<? extends E> c) {
0725 Object[] cs = c.toArray();
0726 if (cs.length == 0)
0727 return 0;
0728 Object[] uniq = new Object[cs.length];
0729 final ReentrantLock lock = this .lock;
0730 lock.lock();
0731 try {
0732 Object[] elements = getArray();
0733 int len = elements.length;
0734 int added = 0;
0735 for (int i = 0; i < cs.length; ++i) { // scan for duplicates
0736 Object e = cs[i];
0737 if (indexOf(e, elements, 0, len) < 0
0738 && indexOf(e, uniq, 0, added) < 0)
0739 uniq[added++] = e;
0740 }
0741 if (added > 0) {
0742 Object[] newElements = Arrays.copyOf(elements, len
0743 + added);
0744 System.arraycopy(uniq, 0, newElements, len, added);
0745 setArray(newElements);
0746 }
0747 return added;
0748 } finally {
0749 lock.unlock();
0750 }
0751 }
0752
0753 /**
0754 * Removes all of the elements from this list.
0755 * The list will be empty after this call returns.
0756 */
0757 public void clear() {
0758 final ReentrantLock lock = this .lock;
0759 lock.lock();
0760 try {
0761 setArray(new Object[0]);
0762 } finally {
0763 lock.unlock();
0764 }
0765 }
0766
0767 /**
0768 * Appends all of the elements in the specified collection to the end
0769 * of this list, in the order that they are returned by the specified
0770 * collection's iterator.
0771 *
0772 * @param c collection containing elements to be added to this list
0773 * @return <tt>true</tt> if this list changed as a result of the call
0774 * @throws NullPointerException if the specified collection is null
0775 * @see #add(Object)
0776 */
0777 public boolean addAll(Collection<? extends E> c) {
0778 Object[] cs = c.toArray();
0779 if (cs.length == 0)
0780 return false;
0781 final ReentrantLock lock = this .lock;
0782 lock.lock();
0783 try {
0784 Object[] elements = getArray();
0785 int len = elements.length;
0786 Object[] newElements = Arrays.copyOf(elements, len
0787 + cs.length);
0788 System.arraycopy(cs, 0, newElements, len, cs.length);
0789 setArray(newElements);
0790 return true;
0791 } finally {
0792 lock.unlock();
0793 }
0794 }
0795
0796 /**
0797 * Inserts all of the elements in the specified collection into this
0798 * list, starting at the specified position. Shifts the element
0799 * currently at that position (if any) and any subsequent elements to
0800 * the right (increases their indices). The new elements will appear
0801 * in this list in the order that they are returned by the
0802 * specified collection's iterator.
0803 *
0804 * @param index index at which to insert the first element
0805 * from the specified collection
0806 * @param c collection containing elements to be added to this list
0807 * @return <tt>true</tt> if this list changed as a result of the call
0808 * @throws IndexOutOfBoundsException {@inheritDoc}
0809 * @throws NullPointerException if the specified collection is null
0810 * @see #add(int,Object)
0811 */
0812 public boolean addAll(int index, Collection<? extends E> c) {
0813 Object[] cs = c.toArray();
0814 final ReentrantLock lock = this .lock;
0815 lock.lock();
0816 try {
0817 Object[] elements = getArray();
0818 int len = elements.length;
0819 if (index > len || index < 0)
0820 throw new IndexOutOfBoundsException("Index: " + index
0821 + ", Size: " + len);
0822 if (cs.length == 0)
0823 return false;
0824 int numMoved = len - index;
0825 Object[] newElements;
0826 if (numMoved == 0)
0827 newElements = Arrays.copyOf(elements, len + cs.length);
0828 else {
0829 newElements = new Object[len + cs.length];
0830 System.arraycopy(elements, 0, newElements, 0, index);
0831 System.arraycopy(elements, index, newElements, index
0832 + cs.length, numMoved);
0833 }
0834 System.arraycopy(cs, 0, newElements, index, cs.length);
0835 setArray(newElements);
0836 return true;
0837 } finally {
0838 lock.unlock();
0839 }
0840 }
0841
0842 /**
0843 * Save the state of the list to a stream (i.e., serialize it).
0844 *
0845 * @serialData The length of the array backing the list is emitted
0846 * (int), followed by all of its elements (each an Object)
0847 * in the proper order.
0848 * @param s the stream
0849 */
0850 private void writeObject(java.io.ObjectOutputStream s)
0851 throws java.io.IOException {
0852
0853 // Write out element count, and any hidden stuff
0854 s.defaultWriteObject();
0855
0856 Object[] elements = getArray();
0857 int len = elements.length;
0858 // Write out array length
0859 s.writeInt(len);
0860
0861 // Write out all elements in the proper order.
0862 for (int i = 0; i < len; i++)
0863 s.writeObject(elements[i]);
0864 }
0865
0866 /**
0867 * Reconstitute the list from a stream (i.e., deserialize it).
0868 * @param s the stream
0869 */
0870 private void readObject(java.io.ObjectInputStream s)
0871 throws java.io.IOException, ClassNotFoundException {
0872
0873 // Read in size, and any hidden stuff
0874 s.defaultReadObject();
0875
0876 // bind to new lock
0877 resetLock();
0878
0879 // Read in array length and allocate array
0880 int len = s.readInt();
0881 Object[] elements = new Object[len];
0882
0883 // Read in all elements in the proper order.
0884 for (int i = 0; i < len; i++)
0885 elements[i] = s.readObject();
0886 setArray(elements);
0887 }
0888
0889 /**
0890 * Returns a string representation of this list. The string
0891 * representation consists of the string representations of the list's
0892 * elements in the order they are returned by its iterator, enclosed in
0893 * square brackets (<tt>"[]"</tt>). Adjacent elements are separated by
0894 * the characters <tt>", "</tt> (comma and space). Elements are
0895 * converted to strings as by {@link String#valueOf(Object)}.
0896 *
0897 * @return a string representation of this list
0898 */
0899 public String toString() {
0900 return Arrays.toString(getArray());
0901 }
0902
0903 /**
0904 * Compares the specified object with this list for equality.
0905 * Returns {@code true} if the specified object is the same object
0906 * as this object, or if it is also a {@link List} and the sequence
0907 * of elements returned by an {@linkplain List#iterator() iterator}
0908 * over the specified list is the same as the sequence returned by
0909 * an iterator over this list. The two sequences are considered to
0910 * be the same if they have the same length and corresponding
0911 * elements at the same position in the sequence are <em>equal</em>.
0912 * Two elements {@code e1} and {@code e2} are considered
0913 * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
0914 *
0915 * @param o the object to be compared for equality with this list
0916 * @return {@code true} if the specified object is equal to this list
0917 */
0918 public boolean equals(Object o) {
0919 if (o == this )
0920 return true;
0921 if (!(o instanceof List))
0922 return false;
0923
0924 List<?> list = (List<?>) (o);
0925 Iterator<?> it = list.iterator();
0926 Object[] elements = getArray();
0927 int len = elements.length;
0928 for (int i = 0; i < len; ++i)
0929 if (!it.hasNext() || !eq(elements[i], it.next()))
0930 return false;
0931 if (it.hasNext())
0932 return false;
0933 return true;
0934 }
0935
0936 /**
0937 * Returns the hash code value for this list.
0938 *
0939 * <p>This implementation uses the definition in {@link List#hashCode}.
0940 *
0941 * @return the hash code value for this list
0942 */
0943 public int hashCode() {
0944 int hashCode = 1;
0945 Object[] elements = getArray();
0946 int len = elements.length;
0947 for (int i = 0; i < len; ++i) {
0948 Object obj = elements[i];
0949 hashCode = 31 * hashCode
0950 + (obj == null ? 0 : obj.hashCode());
0951 }
0952 return hashCode;
0953 }
0954
0955 /**
0956 * Returns an iterator over the elements in this list in proper sequence.
0957 *
0958 * <p>The returned iterator provides a snapshot of the state of the list
0959 * when the iterator was constructed. No synchronization is needed while
0960 * traversing the iterator. The iterator does <em>NOT</em> support the
0961 * <tt>remove</tt> method.
0962 *
0963 * @return an iterator over the elements in this list in proper sequence
0964 */
0965 public Iterator<E> iterator() {
0966 return new COWIterator<E>(getArray(), 0);
0967 }
0968
0969 /**
0970 * {@inheritDoc}
0971 *
0972 * <p>The returned iterator provides a snapshot of the state of the list
0973 * when the iterator was constructed. No synchronization is needed while
0974 * traversing the iterator. The iterator does <em>NOT</em> support the
0975 * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
0976 */
0977 public ListIterator<E> listIterator() {
0978 return new COWIterator<E>(getArray(), 0);
0979 }
0980
0981 /**
0982 * {@inheritDoc}
0983 *
0984 * <p>The returned iterator provides a snapshot of the state of the list
0985 * when the iterator was constructed. No synchronization is needed while
0986 * traversing the iterator. The iterator does <em>NOT</em> support the
0987 * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
0988 *
0989 * @throws IndexOutOfBoundsException {@inheritDoc}
0990 */
0991 public ListIterator<E> listIterator(final int index) {
0992 Object[] elements = getArray();
0993 int len = elements.length;
0994 if (index < 0 || index > len)
0995 throw new IndexOutOfBoundsException("Index: " + index);
0996
0997 return new COWIterator<E>(elements, index);
0998 }
0999
1000 private static class COWIterator<E> implements ListIterator<E> {
1001 /** Snapshot of the array **/
1002 private final Object[] snapshot;
1003 /** Index of element to be returned by subsequent call to next. */
1004 private int cursor;
1005
1006 private COWIterator(Object[] elements, int initialCursor) {
1007 cursor = initialCursor;
1008 snapshot = elements;
1009 }
1010
1011 public boolean hasNext() {
1012 return cursor < snapshot.length;
1013 }
1014
1015 public boolean hasPrevious() {
1016 return cursor > 0;
1017 }
1018
1019 @SuppressWarnings("unchecked")
1020 public E next() {
1021 if (!hasNext())
1022 throw new NoSuchElementException();
1023 return (E) snapshot[cursor++];
1024 }
1025
1026 @SuppressWarnings("unchecked")
1027 public E previous() {
1028 if (!hasPrevious())
1029 throw new NoSuchElementException();
1030 return (E) snapshot[--cursor];
1031 }
1032
1033 public int nextIndex() {
1034 return cursor;
1035 }
1036
1037 public int previousIndex() {
1038 return cursor - 1;
1039 }
1040
1041 /**
1042 * Not supported. Always throws UnsupportedOperationException.
1043 * @throws UnsupportedOperationException always; <tt>remove</tt>
1044 * is not supported by this iterator.
1045 */
1046 public void remove() {
1047 throw new UnsupportedOperationException();
1048 }
1049
1050 /**
1051 * Not supported. Always throws UnsupportedOperationException.
1052 * @throws UnsupportedOperationException always; <tt>set</tt>
1053 * is not supported by this iterator.
1054 */
1055 public void set(E e) {
1056 throw new UnsupportedOperationException();
1057 }
1058
1059 /**
1060 * Not supported. Always throws UnsupportedOperationException.
1061 * @throws UnsupportedOperationException always; <tt>add</tt>
1062 * is not supported by this iterator.
1063 */
1064 public void add(E e) {
1065 throw new UnsupportedOperationException();
1066 }
1067 }
1068
1069 /**
1070 * Returns a view of the portion of this list between
1071 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1072 * The returned list is backed by this list, so changes in the
1073 * returned list are reflected in this list.
1074 *
1075 * <p>The semantics of the list returned by this method become
1076 * undefined if the backing list (i.e., this list) is modified in
1077 * any way other than via the returned list.
1078 *
1079 * @param fromIndex low endpoint (inclusive) of the subList
1080 * @param toIndex high endpoint (exclusive) of the subList
1081 * @return a view of the specified range within this list
1082 * @throws IndexOutOfBoundsException {@inheritDoc}
1083 */
1084 public List<E> subList(int fromIndex, int toIndex) {
1085 final ReentrantLock lock = this .lock;
1086 lock.lock();
1087 try {
1088 Object[] elements = getArray();
1089 int len = elements.length;
1090 if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1091 throw new IndexOutOfBoundsException();
1092 return new COWSubList<E>(this , fromIndex, toIndex);
1093 } finally {
1094 lock.unlock();
1095 }
1096 }
1097
1098 /**
1099 * Sublist for CopyOnWriteArrayList.
1100 * This class extends AbstractList merely for convenience, to
1101 * avoid having to define addAll, etc. This doesn't hurt, but
1102 * is wasteful. This class does not need or use modCount
1103 * mechanics in AbstractList, but does need to check for
1104 * concurrent modification using similar mechanics. On each
1105 * operation, the array that we expect the backing list to use
1106 * is checked and updated. Since we do this for all of the
1107 * base operations invoked by those defined in AbstractList,
1108 * all is well. While inefficient, this is not worth
1109 * improving. The kinds of list operations inherited from
1110 * AbstractList are already so slow on COW sublists that
1111 * adding a bit more space/time doesn't seem even noticeable.
1112 */
1113 private static class COWSubList<E> extends AbstractList<E>
1114 implements RandomAccess {
1115 private final CopyOnWriteArrayList<E> l;
1116 private final int offset;
1117 private int size;
1118 private Object[] expectedArray;
1119
1120 // only call this holding l's lock
1121 COWSubList(CopyOnWriteArrayList<E> list, int fromIndex,
1122 int toIndex) {
1123 l = list;
1124 expectedArray = l.getArray();
1125 offset = fromIndex;
1126 size = toIndex - fromIndex;
1127 }
1128
1129 // only call this holding l's lock
1130 private void checkForComodification() {
1131 if (l.getArray() != expectedArray)
1132 throw new ConcurrentModificationException();
1133 }
1134
1135 // only call this holding l's lock
1136 private void rangeCheck(int index) {
1137 if (index < 0 || index >= size)
1138 throw new IndexOutOfBoundsException("Index: " + index
1139 + ",Size: " + size);
1140 }
1141
1142 public E set(int index, E element) {
1143 final ReentrantLock lock = l.lock;
1144 lock.lock();
1145 try {
1146 rangeCheck(index);
1147 checkForComodification();
1148 E x = l.set(index + offset, element);
1149 expectedArray = l.getArray();
1150 return x;
1151 } finally {
1152 lock.unlock();
1153 }
1154 }
1155
1156 public E get(int index) {
1157 final ReentrantLock lock = l.lock;
1158 lock.lock();
1159 try {
1160 rangeCheck(index);
1161 checkForComodification();
1162 return l.get(index + offset);
1163 } finally {
1164 lock.unlock();
1165 }
1166 }
1167
1168 public int size() {
1169 final ReentrantLock lock = l.lock;
1170 lock.lock();
1171 try {
1172 checkForComodification();
1173 return size;
1174 } finally {
1175 lock.unlock();
1176 }
1177 }
1178
1179 public void add(int index, E element) {
1180 final ReentrantLock lock = l.lock;
1181 lock.lock();
1182 try {
1183 checkForComodification();
1184 if (index < 0 || index > size)
1185 throw new IndexOutOfBoundsException();
1186 l.add(index + offset, element);
1187 expectedArray = l.getArray();
1188 size++;
1189 } finally {
1190 lock.unlock();
1191 }
1192 }
1193
1194 public void clear() {
1195 final ReentrantLock lock = l.lock;
1196 lock.lock();
1197 try {
1198 checkForComodification();
1199 l.removeRange(offset, offset + size);
1200 expectedArray = l.getArray();
1201 size = 0;
1202 } finally {
1203 lock.unlock();
1204 }
1205 }
1206
1207 public E remove(int index) {
1208 final ReentrantLock lock = l.lock;
1209 lock.lock();
1210 try {
1211 rangeCheck(index);
1212 checkForComodification();
1213 E result = l.remove(index + offset);
1214 expectedArray = l.getArray();
1215 size--;
1216 return result;
1217 } finally {
1218 lock.unlock();
1219 }
1220 }
1221
1222 public boolean remove(Object o) {
1223 int index = indexOf(o);
1224 if (index == -1)
1225 return false;
1226 remove(index);
1227 return true;
1228 }
1229
1230 public Iterator<E> iterator() {
1231 final ReentrantLock lock = l.lock;
1232 lock.lock();
1233 try {
1234 checkForComodification();
1235 return new COWSubListIterator<E>(l, 0, offset, size);
1236 } finally {
1237 lock.unlock();
1238 }
1239 }
1240
1241 public ListIterator<E> listIterator(final int index) {
1242 final ReentrantLock lock = l.lock;
1243 lock.lock();
1244 try {
1245 checkForComodification();
1246 if (index < 0 || index > size)
1247 throw new IndexOutOfBoundsException("Index: "
1248 + index + ", Size: " + size);
1249 return new COWSubListIterator<E>(l, index, offset, size);
1250 } finally {
1251 lock.unlock();
1252 }
1253 }
1254
1255 public List<E> subList(int fromIndex, int toIndex) {
1256 final ReentrantLock lock = l.lock;
1257 lock.lock();
1258 try {
1259 checkForComodification();
1260 if (fromIndex < 0 || toIndex > size)
1261 throw new IndexOutOfBoundsException();
1262 return new COWSubList<E>(l, fromIndex + offset, toIndex
1263 + offset);
1264 } finally {
1265 lock.unlock();
1266 }
1267 }
1268
1269 }
1270
1271 private static class COWSubListIterator<E> implements
1272 ListIterator<E> {
1273 private final ListIterator<E> i;
1274 private final int index;
1275 private final int offset;
1276 private final int size;
1277
1278 COWSubListIterator(List<E> l, int index, int offset, int size) {
1279 this .index = index;
1280 this .offset = offset;
1281 this .size = size;
1282 i = l.listIterator(index + offset);
1283 }
1284
1285 public boolean hasNext() {
1286 return nextIndex() < size;
1287 }
1288
1289 public E next() {
1290 if (hasNext())
1291 return i.next();
1292 else
1293 throw new NoSuchElementException();
1294 }
1295
1296 public boolean hasPrevious() {
1297 return previousIndex() >= 0;
1298 }
1299
1300 public E previous() {
1301 if (hasPrevious())
1302 return i.previous();
1303 else
1304 throw new NoSuchElementException();
1305 }
1306
1307 public int nextIndex() {
1308 return i.nextIndex() - offset;
1309 }
1310
1311 public int previousIndex() {
1312 return i.previousIndex() - offset;
1313 }
1314
1315 public void remove() {
1316 throw new UnsupportedOperationException();
1317 }
1318
1319 public void set(E e) {
1320 throw new UnsupportedOperationException();
1321 }
1322
1323 public void add(E e) {
1324 throw new UnsupportedOperationException();
1325 }
1326 }
1327
1328 // Support for resetting lock while deserializing
1329 private static final Unsafe unsafe = Unsafe.getUnsafe();
1330 private static final long lockOffset;
1331 static {
1332 try {
1333 lockOffset = unsafe
1334 .objectFieldOffset(CopyOnWriteArrayList.class
1335 .getDeclaredField("lock"));
1336 } catch (Exception ex) {
1337 throw new Error(ex);
1338 }
1339 }
1340
1341 private void resetLock() {
1342 unsafe.putObjectVolatile(this , lockOffset, new ReentrantLock());
1343 }
1344
1345 }
|