libcore/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java

   1 /*
   2  * Written by Doug Lea with assistance from members of JCP JSR-166
   3  * Expert Group.  Adapted and released, under explicit permission,
   4  * from JDK ArrayList.java which carries the following copyright:
   5  *
   6  * Copyright 1997 by Sun Microsystems, Inc.,
   7  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
   8  * All rights reserved.
   9  *
  10  * This software is the confidential and proprietary information
  11  * of Sun Microsystems, Inc. ("Confidential Information").  You
  12  * shall not disclose such Confidential Information and shall use
  13  * it only in accordance with the terms of the license agreement
  14  * you entered into with Sun.
  15  */
  16
  17 package java.util.concurrent;
  18 import java.util.*;
  19 import java.util.concurrent.locks.*;
  20 import java.lang.reflect.Array;
  21
  22 import sun.misc.Unsafe;
  23
  24 // BEGIN android-note
  25 // removed link to collections framework docs
  26 // END android-note
  27
  28 /**
  29  * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
  30  * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
  31  * making a fresh copy of the underlying array.
  32  *
  33  * <p> This is ordinarily too costly, but may be <em>more</em> efficient
  34  * than alternatives when traversal operations vastly outnumber
  35  * mutations, and is useful when you cannot or don't want to
  36  * synchronize traversals, yet need to preclude interference among
  37  * concurrent threads.  The "snapshot" style iterator method uses a
  38  * reference to the state of the array at the point that the iterator
  39  * was created. This array never changes during the lifetime of the
  40  * iterator, so interference is impossible and the iterator is
  41  * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
  42  * The iterator will not reflect additions, removals, or changes to
  43  * the list since the iterator was created.  Element-changing
  44  * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
  45  * <tt>add</tt>) are not supported. These methods throw
  46  * <tt>UnsupportedOperationException</tt>.
  47  *
  48  * <p>All elements are permitted, including <tt>null</tt>.
  49  *
  50  * <p>Memory consistency effects: As with other concurrent
  51  * collections, actions in a thread prior to placing an object into a
  52  * {@code CopyOnWriteArrayList}
  53  * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
  54  * actions subsequent to the access or removal of that element from
  55  * the {@code CopyOnWriteArrayList} in another thread.
  56  *
  57  * @since 1.5
  58  * @author Doug Lea
  59  * @param <E> the type of elements held in this collection
  60  */
  61 public class CopyOnWriteArrayList<E>
  62     implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  63     private static final long serialVersionUID = 8673264195747942595L;
  64
  65     /** The lock protecting all mutators */
  66     transient final ReentrantLock lock = new ReentrantLock();
  67
  68     /** The array, accessed only via getArray/setArray. */
  69     private volatile transient Object[] array;
  70
  71     /**
  72      * Gets the array.  Non-private so as to also be accessible
  73      * from CopyOnWriteArraySet class.
  74      */
  75     final Object[] getArray() {
  76         return array;
  77     }
  78
  79     /**
  80      * Sets the array.
  81      */
  82     final void setArray(Object[] a) {
  83         array = a;
  84     }
  85
  86     /**
  87      * Creates an empty list.
  88      */
  89     public CopyOnWriteArrayList() {
  90         setArray(new Object[0]);
  91     }
  92
  93     /**
  94      * Creates a list containing the elements of the specified
  95      * collection, in the order they are returned by the collection's
  96      * iterator.
  97      *
  98      * @param c the collection of initially held elements
  99      * @throws NullPointerException if the specified collection is null
 100      */
 101     public CopyOnWriteArrayList(Collection<? extends E> c) {
 102         Object[] elements = c.toArray();
 103         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 104         if (elements.getClass() != Object[].class)
 105             elements = Java6Arrays.copyOf(elements, elements.length, Object[].class);
 106         setArray(elements);
 107     }
 108
 109     /**
 110      * Creates a list holding a copy of the given array.
 111      *
 112      * @param toCopyIn the array (a copy of this array is used as the
 113      *        internal array)
 114      * @throws NullPointerException if the specified array is null
 115      */
 116     public CopyOnWriteArrayList(E[] toCopyIn) {
 117         setArray(Java6Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
 118     }
 119
 120     /**
 121      * Returns the number of elements in this list.
 122      *
 123      * @return the number of elements in this list
 124      */
 125     public int size() {
 126         return getArray().length;
 127     }
 128
 129     /**
 130      * Returns <tt>true</tt> if this list contains no elements.
 131      *
 132      * @return <tt>true</tt> if this list contains no elements
 133      */
 134     public boolean isEmpty() {
 135         return size() == 0;
 136     }
 137
 138     /**
 139      * Test for equality, coping with nulls.
 140      */
 141     private static boolean eq(Object o1, Object o2) {
 142         return (o1 == null ? o2 == null : o1.equals(o2));
 143     }
 144
 145     /**
 146      * static version of indexOf, to allow repeated calls without
 147      * needing to re-acquire array each time.
 148      * @param o element to search for
 149      * @param elements the array
 150      * @param index first index to search
 151      * @param fence one past last index to search
 152      * @return index of element, or -1 if absent
 153      */
 154     private static int indexOf(Object o, Object[] elements,
 155                                int index, int fence) {
 156         if (o == null) {
 157             for (int i = index; i < fence; i++)
 158                 if (elements[i] == null)
 159                     return i;
 160         } else {
 161             for (int i = index; i < fence; i++)
 162                 if (o.equals(elements[i]))
 163                     return i;
 164         }
 165         return -1;
 166     }
 167
 168     /**
 169      * static version of lastIndexOf.
 170      * @param o element to search for
 171      * @param elements the array
 172      * @param index first index to search
 173      * @return index of element, or -1 if absent
 174      */
 175     private static int lastIndexOf(Object o, Object[] elements, int index) {
 176         if (o == null) {
 177             for (int i = index; i >= 0; i--)
 178                 if (elements[i] == null)
 179                     return i;
 180         } else {
 181             for (int i = index; i >= 0; i--)
 182                 if (o.equals(elements[i]))
 183                     return i;
 184         }
 185         return -1;
 186     }
 187
 188     /**
 189      * Returns <tt>true</tt> if this list contains the specified element.
 190      * More formally, returns <tt>true</tt> if and only if this list contains
 191      * at least one element <tt>e</tt> such that
 192      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 193      *
 194      * @param o element whose presence in this list is to be tested
 195      * @return <tt>true</tt> if this list contains the specified element
 196      */
 197     public boolean contains(Object o) {
 198         Object[] elements = getArray();
 199         return indexOf(o, elements, 0, elements.length) >= 0;
 200     }
 201
 202     /**
 203      * {@inheritDoc}
 204      */
 205     public int indexOf(Object o) {
 206         Object[] elements = getArray();
 207         return indexOf(o, elements, 0, elements.length);
 208     }
 209
 210     /**
 211      * Returns the index of the first occurrence of the specified element in
 212      * this list, searching forwards from <tt>index</tt>, or returns -1 if
 213      * the element is not found.
 214      * More formally, returns the lowest index <tt>i</tt> such that
 215      * <tt>(i&nbsp;&gt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
 216      * or -1 if there is no such index.
 217      *
 218      * @param e element to search for
 219      * @param index index to start searching from
 220      * @return the index of the first occurrence of the element in
 221      *         this list at position <tt>index</tt> or later in the list;
 222      *         <tt>-1</tt> if the element is not found.
 223      * @throws IndexOutOfBoundsException if the specified index is negative
 224      */
 225     public int indexOf(E e, int index) {
 226         Object[] elements = getArray();
 227         return indexOf(e, elements, index, elements.length);
 228     }
 229
 230     /**
 231      * {@inheritDoc}
 232      */
 233     public int lastIndexOf(Object o) {
 234         Object[] elements = getArray();
 235         return lastIndexOf(o, elements, elements.length - 1);
 236     }
 237
 238     /**
 239      * Returns the index of the last occurrence of the specified element in
 240      * this list, searching backwards from <tt>index</tt>, or returns -1 if
 241      * the element is not found.
 242      * More formally, returns the highest index <tt>i</tt> such that
 243      * <tt>(i&nbsp;&lt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
 244      * or -1 if there is no such index.
 245      *
 246      * @param e element to search for
 247      * @param index index to start searching backwards from
 248      * @return the index of the last occurrence of the element at position
 249      *         less than or equal to <tt>index</tt> in this list;
 250      *         -1 if the element is not found.
 251      * @throws IndexOutOfBoundsException if the specified index is greater
 252      *         than or equal to the current size of this list
 253      */
 254     public int lastIndexOf(E e, int index) {
 255         Object[] elements = getArray();
 256         return lastIndexOf(e, elements, index);
 257     }
 258
 259     /**
 260      * Returns a shallow copy of this list.  (The elements themselves
 261      * are not copied.)
 262      *
 263      * @return a clone of this list
 264      */
 265     public Object clone() {
 266         try {
 267             CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
 268             c.resetLock();
 269             return c;
 270         } catch (CloneNotSupportedException e) {
 271             // this shouldn't happen, since we are Cloneable
 272             throw new InternalError();
 273         }
 274     }
 275
 276     /**
 277      * Returns an array containing all of the elements in this list
 278      * in proper sequence (from first to last element).
 279      *
 280      * <p>The returned array will be "safe" in that no references to it are
 281      * maintained by this list.  (In other words, this method must allocate
 282      * a new array).  The caller is thus free to modify the returned array.
 283      *
 284      * <p>This method acts as bridge between array-based and collection-based
 285      * APIs.
 286      *
 287      * @return an array containing all the elements in this list
 288      */
 289     public Object[] toArray() {
 290         Object[] elements = getArray();
 291         return Java6Arrays.copyOf(elements, elements.length);
 292     }
 293
 294     /**
 295      * Returns an array containing all of the elements in this list in
 296      * proper sequence (from first to last element); the runtime type of
 297      * the returned array is that of the specified array.  If the list fits
 298      * in the specified array, it is returned therein.  Otherwise, a new
 299      * array is allocated with the runtime type of the specified array and
 300      * the size of this list.
 301      *
 302      * <p>If this list fits in the specified array with room to spare
 303      * (i.e., the array has more elements than this list), the element in
 304      * the array immediately following the end of the list is set to
 305      * <tt>null</tt>.  (This is useful in determining the length of this
 306      * list <i>only</i> if the caller knows that this list does not contain
 307      * any null elements.)
 308      *
 309      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 310      * array-based and collection-based APIs.  Further, this method allows
 311      * precise control over the runtime type of the output array, and may,
 312      * under certain circumstances, be used to save allocation costs.
 313      *
 314      * <p>Suppose <tt>x</tt> is a list known to contain only strings.
 315      * The following code can be used to dump the list into a newly
 316      * allocated array of <tt>String</tt>:
 317      *
 318      * <pre>
 319      *     String[] y = x.toArray(new String[0]);</pre>
 320      *
 321      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 322      * <tt>toArray()</tt>.
 323      *
 324      * @param a the array into which the elements of the list are to
 325      *          be stored, if it is big enough; otherwise, a new array of the
 326      *          same runtime type is allocated for this purpose.
 327      * @return an array containing all the elements in this list
 328      * @throws ArrayStoreException if the runtime type of the specified array
 329      *         is not a supertype of the runtime type of every element in
 330      *         this list
 331      * @throws NullPointerException if the specified array is null
 332      */
 333     @SuppressWarnings("unchecked")
 334     public <T> T[] toArray(T a[]) {
 335         Object[] elements = getArray();
 336         int len = elements.length;
 337         if (a.length < len)
 338             return (T[]) Java6Arrays.copyOf(elements, len, a.getClass());
 339         else {
 340             System.arraycopy(elements, 0, a, 0, len);
 341             if (a.length > len)
 342                 a[len] = null;
 343             return a;
 344         }
 345     }
 346
 347     // Positional Access Operations
 348
 349     @SuppressWarnings("unchecked")
 350     private E get(Object[] a, int index) {
 351         return (E) a[index];
 352     }
 353
 354     /**
 355      * {@inheritDoc}
 356      *
 357      * @throws IndexOutOfBoundsException {@inheritDoc}
 358      */
 359     public E get(int index) {
 360         return get(getArray(), index);
 361     }
 362
 363     /**
 364      * Replaces the element at the specified position in this list with the
 365      * specified element.
 366      *
 367      * @throws IndexOutOfBoundsException {@inheritDoc}
 368      */
 369     public E set(int index, E element) {
 370         final ReentrantLock lock = this.lock;
 371         lock.lock();
 372         try {
 373             Object[] elements = getArray();
 374             E oldValue = get(elements, index);
 375
 376             if (oldValue != element) {
 377                 int len = elements.length;
 378                 Object[] newElements = Java6Arrays.copyOf(elements, len);
 379                 newElements[index] = element;
 380                 setArray(newElements);
 381             } else {
 382                 // Not quite a no-op; ensures volatile write semantics
 383                 setArray(elements);
 384             }
 385             return oldValue;
 386         } finally {
 387             lock.unlock();
 388         }
 389     }
 390
 391     /**
 392      * Appends the specified element to the end of this list.
 393      *
 394      * @param e element to be appended to this list
 395      * @return <tt>true</tt> (as specified by {@link Collection#add})
 396      */
 397     public boolean add(E e) {
 398         final ReentrantLock lock = this.lock;
 399         lock.lock();
 400         try {
 401             Object[] elements = getArray();
 402             int len = elements.length;
 403             Object[] newElements = Java6Arrays.copyOf(elements, len + 1);
 404             newElements[len] = e;
 405             setArray(newElements);
 406             return true;
 407         } finally {
 408             lock.unlock();
 409         }
 410     }
 411
 412     /**
 413      * Inserts the specified element at the specified position in this
 414      * list. Shifts the element currently at that position (if any) and
 415      * any subsequent elements to the right (adds one to their indices).
 416      *
 417      * @throws IndexOutOfBoundsException {@inheritDoc}
 418      */
 419     public void add(int index, E element) {
 420         final ReentrantLock lock = this.lock;
 421         lock.lock();
 422         try {
 423             Object[] elements = getArray();
 424             int len = elements.length;
 425             if (index > len || index < 0)
 426                 throw new IndexOutOfBoundsException("Index: "+index+
 427                                                     ", Size: "+len);
 428             Object[] newElements;
 429             int numMoved = len - index;
 430             if (numMoved == 0)
 431                 newElements = Java6Arrays.copyOf(elements, len + 1);
 432             else {
 433                 newElements = new Object[len + 1];
 434                 System.arraycopy(elements, 0, newElements, 0, index);
 435                 System.arraycopy(elements, index, newElements, index + 1,
 436                                  numMoved);
 437             }
 438             newElements[index] = element;
 439             setArray(newElements);
 440         } finally {
 441             lock.unlock();
 442         }
 443     }
 444
 445     /**
 446      * Removes the element at the specified position in this list.
 447      * Shifts any subsequent elements to the left (subtracts one from their
 448      * indices).  Returns the element that was removed from the list.
 449      *
 450      * @throws IndexOutOfBoundsException {@inheritDoc}
 451      */
 452     public E remove(int index) {
 453         final ReentrantLock lock = this.lock;
 454         lock.lock();
 455         try {
 456             Object[] elements = getArray();
 457             int len = elements.length;
 458             E oldValue = get(elements, index);
 459             int numMoved = len - index - 1;
 460             if (numMoved == 0)
 461                 setArray(Java6Arrays.copyOf(elements, len - 1));
 462             else {
 463                 Object[] newElements = new Object[len - 1];
 464                 System.arraycopy(elements, 0, newElements, 0, index);
 465                 System.arraycopy(elements, index + 1, newElements, index,
 466                                  numMoved);
 467                 setArray(newElements);
 468             }
 469             return oldValue;
 470         } finally {
 471             lock.unlock();
 472         }
 473     }
 474
 475     /**
 476      * Removes the first occurrence of the specified element from this list,
 477      * if it is present.  If this list does not contain the element, it is
 478      * unchanged.  More formally, removes the element with the lowest index
 479      * <tt>i</tt> such that
 480      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 481      * (if such an element exists).  Returns <tt>true</tt> if this list
 482      * contained the specified element (or equivalently, if this list
 483      * changed as a result of the call).
 484      *
 485      * @param o element to be removed from this list, if present
 486      * @return <tt>true</tt> if this list contained the specified element
 487      */
 488     public boolean remove(Object o) {
 489         final ReentrantLock lock = this.lock;
 490         lock.lock();
 491         try {
 492             Object[] elements = getArray();
 493             int len = elements.length;
 494             if (len != 0) {
 495                 // Copy while searching for element to remove
 496                 // This wins in the normal case of element being present
 497                 int newlen = len - 1;
 498                 Object[] newElements = new Object[newlen];
 499
 500                 for (int i = 0; i < newlen; ++i) {
 501                     if (eq(o, elements[i])) {
 502                         // found one;  copy remaining and exit
 503                         for (int k = i + 1; k < len; ++k)
 504                             newElements[k-1] = elements[k];
 505                         setArray(newElements);
 506                         return true;
 507                     } else
 508                         newElements[i] = elements[i];
 509                 }
 510
 511                 // special handling for last cell
 512                 if (eq(o, elements[newlen])) {
 513                     setArray(newElements);
 514                     return true;
 515                 }
 516             }
 517             return false;
 518         } finally {
 519             lock.unlock();
 520         }
 521     }
 522
 523     /**
 524      * Removes from this list all of the elements whose index is between
 525      * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
 526      * Shifts any succeeding elements to the left (reduces their index).
 527      * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
 528      * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
 529      *
 530      * @param fromIndex index of first element to be removed
 531      * @param toIndex index after last element to be removed
 532      * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
 533      *         (@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
 534      */
 535     private void removeRange(int fromIndex, int toIndex) {
 536         final ReentrantLock lock = this.lock;
 537         lock.lock();
 538         try {
 539             Object[] elements = getArray();
 540             int len = elements.length;
 541
 542             if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
 543                 throw new IndexOutOfBoundsException();
 544             int newlen = len - (toIndex - fromIndex);
 545             int numMoved = len - toIndex;
 546             if (numMoved == 0)
 547                 setArray(Java6Arrays.copyOf(elements, newlen));
 548             else {
 549                 Object[] newElements = new Object[newlen];
 550                 System.arraycopy(elements, 0, newElements, 0, fromIndex);
 551                 System.arraycopy(elements, toIndex, newElements,
 552                                  fromIndex, numMoved);
 553                 setArray(newElements);
 554             }
 555         } finally {
 556             lock.unlock();
 557         }
 558     }
 559
 560     /**
 561      * Append the element if not present.
 562      *
 563      * @param e element to be added to this list, if absent
 564      * @return <tt>true</tt> if the element was added
 565      */
 566     public boolean addIfAbsent(E e) {
 567         final ReentrantLock lock = this.lock;
 568         lock.lock();
 569         try {
 570             // Copy while checking if already present.
 571             // This wins in the most common case where it is not present
 572             Object[] elements = getArray();
 573             int len = elements.length;
 574             Object[] newElements = new Object[len + 1];
 575             for (int i = 0; i < len; ++i) {
 576                 if (eq(e, elements[i]))
 577                     return false; // exit, throwing away copy
 578                 else
 579                     newElements[i] = elements[i];
 580             }
 581             newElements[len] = e;
 582             setArray(newElements);
 583             return true;
 584         } finally {
 585             lock.unlock();
 586         }
 587     }
 588
 589     /**
 590      * Returns <tt>true</tt> if this list contains all of the elements of the
 591      * specified collection.
 592      *
 593      * @param c collection to be checked for containment in this list
 594      * @return <tt>true</tt> if this list contains all of the elements of the
 595      *         specified collection
 596      * @throws NullPointerException if the specified collection is null
 597      * @see #contains(Object)
 598      */
 599     public boolean containsAll(Collection<?> c) {
 600         Object[] elements = getArray();
 601         int len = elements.length;
 602         for (Object e : c) {
 603             if (indexOf(e, elements, 0, len) < 0)
 604                 return false;
 605         }
 606         return true;
 607     }
 608
 609     /**
 610      * Removes from this list all of its elements that are contained in
 611      * the specified collection. This is a particularly expensive operation
 612      * in this class because of the need for an internal temporary array.
 613      *
 614      * @param c collection containing elements to be removed from this list
 615      * @return <tt>true</tt> if this list changed as a result of the call
 616      * @throws ClassCastException if the class of an element of this list
 617      *         is incompatible with the specified collection (optional)
 618      * @throws NullPointerException if this list contains a null element and the
 619      *         specified collection does not permit null elements (optional),
 620      *         or if the specified collection is null
 621      * @see #remove(Object)
 622      */
 623     public boolean removeAll(Collection<?> c) {
 624         final ReentrantLock lock = this.lock;
 625         lock.lock();
 626         try {
 627             Object[] elements = getArray();
 628             int len = elements.length;
 629             if (len != 0) {
 630                 // temp array holds those elements we know we want to keep
 631                 int newlen = 0;
 632                 Object[] temp = new Object[len];
 633                 for (int i = 0; i < len; ++i) {
 634                     Object element = elements[i];
 635                     if (!c.contains(element))
 636                         temp[newlen++] = element;
 637                 }
 638                 if (newlen != len) {
 639                     setArray(Java6Arrays.copyOf(temp, newlen));
 640                     return true;
 641                 }
 642             }
 643             return false;
 644         } finally {
 645             lock.unlock();
 646         }
 647     }
 648
 649     /**
 650      * Retains only the elements in this list that are contained in the
 651      * specified collection.  In other words, removes from this list all of
 652      * its elements that are not contained in the specified collection.
 653      *
 654      * @param c collection containing elements to be retained in this list
 655      * @return <tt>true</tt> if this list changed as a result of the call
 656      * @throws ClassCastException if the class of an element of this list
 657      *         is incompatible with the specified collection (optional)
 658      * @throws NullPointerException if this list contains a null element and the
 659      *         specified collection does not permit null elements (optional),
 660      *         or if the specified collection is null
 661      * @see #remove(Object)
 662      */
 663     public boolean retainAll(Collection<?> c) {
 664         final ReentrantLock lock = this.lock;
 665         lock.lock();
 666         try {
 667             Object[] elements = getArray();
 668             int len = elements.length;
 669             if (len != 0) {
 670                 // temp array holds those elements we know we want to keep
 671                 int newlen = 0;
 672                 Object[] temp = new Object[len];
 673                 for (int i = 0; i < len; ++i) {
 674                     Object element = elements[i];
 675                     if (c.contains(element))
 676                         temp[newlen++] = element;
 677                 }
 678                 if (newlen != len) {
 679                     setArray(Java6Arrays.copyOf(temp, newlen));
 680                     return true;
 681                 }
 682             }
 683             return false;
 684         } finally {
 685             lock.unlock();
 686         }
 687     }
 688
 689     /**
 690      * Appends all of the elements in the specified collection that
 691      * are not already contained in this list, to the end of
 692      * this list, in the order that they are returned by the
 693      * specified collection's iterator.
 694      *
 695      * @param c collection containing elements to be added to this list
 696      * @return the number of elements added
 697      * @throws NullPointerException if the specified collection is null
 698      * @see #addIfAbsent(Object)
 699      */
 700     public int addAllAbsent(Collection<? extends E> c) {
 701         Object[] cs = c.toArray();
 702         if (cs.length == 0)
 703             return 0;
 704         Object[] uniq = new Object[cs.length];
 705         final ReentrantLock lock = this.lock;
 706         lock.lock();
 707         try {
 708             Object[] elements = getArray();
 709             int len = elements.length;
 710             int added = 0;
 711             for (int i = 0; i < cs.length; ++i) { // scan for duplicates
 712                 Object e = cs[i];
 713                 if (indexOf(e, elements, 0, len) < 0 &&
 714                     indexOf(e, uniq, 0, added) < 0)
 715                     uniq[added++] = e;
 716             }
 717             if (added > 0) {
 718                 Object[] newElements = Java6Arrays.copyOf(elements, len + added);
 719                 System.arraycopy(uniq, 0, newElements, len, added);
 720                 setArray(newElements);
 721             }
 722             return added;
 723         } finally {
 724             lock.unlock();
 725         }
 726     }
 727
 728     /**
 729      * Removes all of the elements from this list.
 730      * The list will be empty after this call returns.
 731      */
 732     public void clear() {
 733         final ReentrantLock lock = this.lock;
 734         lock.lock();
 735         try {
 736             setArray(new Object[0]);
 737         } finally {
 738             lock.unlock();
 739         }
 740     }
 741
 742     /**
 743      * Appends all of the elements in the specified collection to the end
 744      * of this list, in the order that they are returned by the specified
 745      * collection's iterator.
 746      *
 747      * @param c collection containing elements to be added to this list
 748      * @return <tt>true</tt> if this list changed as a result of the call
 749      * @throws NullPointerException if the specified collection is null
 750      * @see #add(Object)
 751      */
 752     public boolean addAll(Collection<? extends E> c) {
 753         Object[] cs = c.toArray();
 754         if (cs.length == 0)
 755             return false;
 756         final ReentrantLock lock = this.lock;
 757         lock.lock();
 758         try {
 759             Object[] elements = getArray();
 760             int len = elements.length;
 761             Object[] newElements = Java6Arrays.copyOf(elements, len + cs.length);
 762             System.arraycopy(cs, 0, newElements, len, cs.length);
 763             setArray(newElements);
 764             return true;
 765         } finally {
 766             lock.unlock();
 767         }
 768     }
 769
 770     /**
 771      * Inserts all of the elements in the specified collection into this
 772      * list, starting at the specified position.  Shifts the element
 773      * currently at that position (if any) and any subsequent elements to
 774      * the right (increases their indices).  The new elements will appear
 775      * in this list in the order that they are returned by the
 776      * specified collection's iterator.
 777      *
 778      * @param index index at which to insert the first element
 779      *        from the specified collection
 780      * @param c collection containing elements to be added to this list
 781      * @return <tt>true</tt> if this list changed as a result of the call
 782      * @throws IndexOutOfBoundsException {@inheritDoc}
 783      * @throws NullPointerException if the specified collection is null
 784      * @see #add(int,Object)
 785      */
 786     public boolean addAll(int index, Collection<? extends E> c) {
 787         Object[] cs = c.toArray();
 788         final ReentrantLock lock = this.lock;
 789         lock.lock();
 790         try {
 791             Object[] elements = getArray();
 792             int len = elements.length;
 793             if (index > len || index < 0)
 794                 throw new IndexOutOfBoundsException("Index: "+index+
 795                                                     ", Size: "+len);
 796             if (cs.length == 0)
 797                 return false;
 798             int numMoved = len - index;
 799             Object[] newElements;
 800             if (numMoved == 0)
 801                 newElements = Java6Arrays.copyOf(elements, len + cs.length);
 802             else {
 803                 newElements = new Object[len + cs.length];
 804                 System.arraycopy(elements, 0, newElements, 0, index);
 805                 System.arraycopy(elements, index,
 806                                  newElements, index + cs.length,
 807                                  numMoved);
 808             }
 809             System.arraycopy(cs, 0, newElements, index, cs.length);
 810             setArray(newElements);
 811             return true;
 812         } finally {
 813             lock.unlock();
 814         }
 815     }
 816
 817     /**
 818      * Save the state of the list to a stream (i.e., serialize it).
 819      *
 820      * @serialData The length of the array backing the list is emitted
 821      *               (int), followed by all of its elements (each an Object)
 822      *               in the proper order.
 823      * @param s the stream
 824      */
 825     private void writeObject(java.io.ObjectOutputStream s)
 826         throws java.io.IOException{
 827
 828         // Write out element count, and any hidden stuff
 829         s.defaultWriteObject();
 830
 831         Object[] elements = getArray();
 832         int len = elements.length;
 833         // Write out array length
 834         s.writeInt(len);
 835
 836         // Write out all elements in the proper order.
 837         for (int i = 0; i < len; i++)
 838             s.writeObject(elements[i]);
 839     }
 840
 841     /**
 842      * Reconstitute the list from a stream (i.e., deserialize it).
 843      * @param s the stream
 844      */
 845     private void readObject(java.io.ObjectInputStream s)
 846         throws java.io.IOException, ClassNotFoundException {
 847
 848         // Read in size, and any hidden stuff
 849         s.defaultReadObject();
 850
 851         // bind to new lock
 852         resetLock();
 853
 854         // Read in array length and allocate array
 855         int len = s.readInt();
 856         Object[] elements = new Object[len];
 857
 858         // Read in all elements in the proper order.
 859         for (int i = 0; i < len; i++)
 860             elements[i] = s.readObject();
 861         setArray(elements);
 862     }
 863
 864     /**
 865      * Returns a string representation of this list.  The string
 866      * representation consists of the string representations of the list's
 867      * elements in the order they are returned by its iterator, enclosed in
 868      * square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by
 869      * the characters <tt>", "</tt> (comma and space).  Elements are
 870      * converted to strings as by {@link String#valueOf(Object)}.
 871      *
 872      * @return a string representation of this list
 873      */
 874     public String toString() {
 875         return Arrays.toString(getArray());
 876     }
 877
 878     /**
 879      * Compares the specified object with this list for equality.
 880      * Returns {@code true} if the specified object is the same object
 881      * as this object, or if it is also a {@link List} and the sequence
 882      * of elements returned by an {@linkplain List#iterator() iterator}
 883      * over the specified list is the same as the sequence returned by
 884      * an iterator over this list.  The two sequences are considered to
 885      * be the same if they have the same length and corresponding
 886      * elements at the same position in the sequence are <em>equal</em>.
 887      * Two elements {@code e1} and {@code e2} are considered
 888      * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
 889      *
 890      * @param o the object to be compared for equality with this list
 891      * @return {@code true} if the specified object is equal to this list
 892      */
 893     public boolean equals(Object o) {
 894         if (o == this)
 895             return true;
 896         if (!(o instanceof List))
 897             return false;
 898
 899         List<?> list = (List<?>)(o);
 900         Iterator<?> it = list.iterator();
 901         Object[] elements = getArray();
 902         int len = elements.length;
 903         for (int i = 0; i < len; ++i)
 904             if (!it.hasNext() || !eq(elements[i], it.next()))
 905                 return false;
 906         if (it.hasNext())
 907             return false;
 908         return true;
 909     }
 910
 911     /**
 912      * Returns the hash code value for this list.
 913      *
 914      * <p>This implementation uses the definition in {@link List#hashCode}.
 915      *
 916      * @return the hash code value for this list
 917      */
 918     public int hashCode() {
 919         int hashCode = 1;
 920         Object[] elements = getArray();
 921         int len = elements.length;
 922         for (int i = 0; i < len; ++i) {
 923             Object obj = elements[i];
 924             hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
 925         }
 926         return hashCode;
 927     }
 928
 929     /**
 930      * Returns an iterator over the elements in this list in proper sequence.
 931      *
 932      * <p>The returned iterator provides a snapshot of the state of the list
 933      * when the iterator was constructed. No synchronization is needed while
 934      * traversing the iterator. The iterator does <em>NOT</em> support the
 935      * <tt>remove</tt> method.
 936      *
 937      * @return an iterator over the elements in this list in proper sequence
 938      */
 939     public Iterator<E> iterator() {
 940         return new COWIterator<E>(getArray(), 0);
 941     }
 942
 943     /**
 944      * {@inheritDoc}
 945      *
 946      * <p>The returned iterator provides a snapshot of the state of the list
 947      * when the iterator was constructed. No synchronization is needed while
 948      * traversing the iterator. The iterator does <em>NOT</em> support the
 949      * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
 950      */
 951     public ListIterator<E> listIterator() {
 952         return new COWIterator<E>(getArray(), 0);
 953     }
 954
 955     /**
 956      * {@inheritDoc}
 957      *
 958      * <p>The returned iterator provides a snapshot of the state of the list
 959      * when the iterator was constructed. No synchronization is needed while
 960      * traversing the iterator. The iterator does <em>NOT</em> support the
 961      * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
 962      *
 963      * @throws IndexOutOfBoundsException {@inheritDoc}
 964      */
 965     public ListIterator<E> listIterator(final int index) {
 966         Object[] elements = getArray();
 967         int len = elements.length;
 968         if (index<0 || index>len)
 969             throw new IndexOutOfBoundsException("Index: "+index);
 970
 971         return new COWIterator<E>(elements, index);
 972     }
 973
 974     private static class COWIterator<E> implements ListIterator<E> {
 975         /** Snapshot of the array **/
 976         private final Object[] snapshot;
 977         /** Index of element to be returned by subsequent call to next.  */
 978         private int cursor;
 979
 980         private COWIterator(Object[] elements, int initialCursor) {
 981             cursor = initialCursor;
 982             snapshot = elements;
 983         }
 984
 985         public boolean hasNext() {
 986             return cursor < snapshot.length;
 987         }
 988
 989         public boolean hasPrevious() {
 990             return cursor > 0;
 991         }
 992
 993         @SuppressWarnings("unchecked")
 994         public E next() {
 995             if (! hasNext())
 996                 throw new NoSuchElementException();
 997             return (E) snapshot[cursor++];
 998         }
 999
1000         @SuppressWarnings("unchecked")
1001         public E previous() {
1002             if (! hasPrevious())
1003                 throw new NoSuchElementException();
1004             return (E) snapshot[--cursor];
1005         }
1006
1007         public int nextIndex() {
1008             return cursor;
1009         }
1010
1011         public int previousIndex() {
1012             return cursor-1;
1013         }
1014
1015         /**
1016          * Not supported. Always throws UnsupportedOperationException.
1017          * @throws UnsupportedOperationException always; <tt>remove</tt>
1018          *         is not supported by this iterator.
1019          */
1020         public void remove() {
1021             throw new UnsupportedOperationException();
1022         }
1023
1024         /**
1025          * Not supported. Always throws UnsupportedOperationException.
1026          * @throws UnsupportedOperationException always; <tt>set</tt>
1027          *         is not supported by this iterator.
1028          */
1029         public void set(E e) {
1030             throw new UnsupportedOperationException();
1031         }
1032
1033         /**
1034          * Not supported. Always throws UnsupportedOperationException.
1035          * @throws UnsupportedOperationException always; <tt>add</tt>
1036          *         is not supported by this iterator.
1037          */
1038         public void add(E e) {
1039             throw new UnsupportedOperationException();
1040         }
1041     }
1042
1043     /**
1044      * Returns a view of the portion of this list between
1045      * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1046      * The returned list is backed by this list, so changes in the
1047      * returned list are reflected in this list.
1048      *
1049      * <p>The semantics of the list returned by this method become
1050      * undefined if the backing list (i.e., this list) is modified in
1051      * any way other than via the returned list.
1052      *
1053      * @param fromIndex low endpoint (inclusive) of the subList
1054      * @param toIndex high endpoint (exclusive) of the subList
1055      * @return a view of the specified range within this list
1056      * @throws IndexOutOfBoundsException {@inheritDoc}
1057      */
1058     public List<E> subList(int fromIndex, int toIndex) {
1059         final ReentrantLock lock = this.lock;
1060         lock.lock();
1061         try {
1062             Object[] elements = getArray();
1063             int len = elements.length;
1064             if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1065                 throw new IndexOutOfBoundsException();
1066             return new COWSubList<E>(this, fromIndex, toIndex);
1067         } finally {
1068             lock.unlock();
1069         }
1070     }
1071
1072     /**
1073      * Sublist for CopyOnWriteArrayList.
1074      * This class extends AbstractList merely for convenience, to
1075      * avoid having to define addAll, etc. This doesn't hurt, but
1076      * is wasteful.  This class does not need or use modCount
1077      * mechanics in AbstractList, but does need to check for
1078      * concurrent modification using similar mechanics.  On each
1079      * operation, the array that we expect the backing list to use
1080      * is checked and updated.  Since we do this for all of the
1081      * base operations invoked by those defined in AbstractList,
1082      * all is well.  While inefficient, this is not worth
1083      * improving.  The kinds of list operations inherited from
1084      * AbstractList are already so slow on COW sublists that
1085      * adding a bit more space/time doesn't seem even noticeable.
1086      */
1087     private static class COWSubList<E>
1088         extends AbstractList<E>
1089         implements RandomAccess
1090     {
1091         private final CopyOnWriteArrayList<E> l;
1092         private final int offset;
1093         private int size;
1094         private Object[] expectedArray;
1095
1096         // only call this holding l's lock
1097         COWSubList(CopyOnWriteArrayList<E> list,
1098                    int fromIndex, int toIndex) {
1099             l = list;
1100             expectedArray = l.getArray();
1101             offset = fromIndex;
1102             size = toIndex - fromIndex;
1103         }
1104
1105         // only call this holding l's lock
1106         private void checkForComodification() {
1107             if (l.getArray() != expectedArray)
1108                 throw new ConcurrentModificationException();
1109         }
1110
1111         // only call this holding l's lock
1112         private void rangeCheck(int index) {
1113             if (index<0 || index>=size)
1114                 throw new IndexOutOfBoundsException("Index: "+index+
1115                                                     ",Size: "+size);
1116         }
1117
1118         public E set(int index, E element) {
1119             final ReentrantLock lock = l.lock;
1120             lock.lock();
1121             try {
1122                 rangeCheck(index);
1123                 checkForComodification();
1124                 E x = l.set(index+offset, element);
1125                 expectedArray = l.getArray();
1126                 return x;
1127             } finally {
1128                 lock.unlock();
1129             }
1130         }
1131
1132         public E get(int index) {
1133             final ReentrantLock lock = l.lock;
1134             lock.lock();
1135             try {
1136                 rangeCheck(index);
1137                 checkForComodification();
1138                 return l.get(index+offset);
1139             } finally {
1140                 lock.unlock();
1141             }
1142         }
1143
1144         public int size() {
1145             final ReentrantLock lock = l.lock;
1146             lock.lock();
1147             try {
1148                 checkForComodification();
1149                 return size;
1150             } finally {
1151                 lock.unlock();
1152             }
1153         }
1154
1155         public void add(int index, E element) {
1156             final ReentrantLock lock = l.lock;
1157             lock.lock();
1158             try {
1159                 checkForComodification();
1160                 if (index<0 || index>size)
1161                     throw new IndexOutOfBoundsException();
1162                 l.add(index+offset, element);
1163                 expectedArray = l.getArray();
1164                 size++;
1165             } finally {
1166                 lock.unlock();
1167             }
1168         }
1169
1170         public void clear() {
1171             final ReentrantLock lock = l.lock;
1172             lock.lock();
1173             try {
1174                 checkForComodification();
1175                 l.removeRange(offset, offset+size);
1176                 expectedArray = l.getArray();
1177                 size = 0;
1178             } finally {
1179                 lock.unlock();
1180             }
1181         }
1182
1183         public E remove(int index) {
1184             final ReentrantLock lock = l.lock;
1185             lock.lock();
1186             try {
1187                 rangeCheck(index);
1188                 checkForComodification();
1189                 E result = l.remove(index+offset);
1190                 expectedArray = l.getArray();
1191                 size--;
1192                 return result;
1193             } finally {
1194                 lock.unlock();
1195             }
1196         }
1197
1198         public boolean remove(Object o) {
1199             int index = indexOf(o);
1200             if (index == -1)
1201                 return false;
1202             remove(index);
1203             return true;
1204         }
1205
1206         public Iterator<E> iterator() {
1207             final ReentrantLock lock = l.lock;
1208             lock.lock();
1209             try {
1210                 checkForComodification();
1211                 return new COWSubListIterator<E>(l, 0, offset, size);
1212             } finally {
1213                 lock.unlock();
1214             }
1215         }
1216
1217         public ListIterator<E> listIterator(final int index) {
1218             final ReentrantLock lock = l.lock;
1219             lock.lock();
1220             try {
1221                 checkForComodification();
1222                 if (index<0 || index>size)
1223                     throw new IndexOutOfBoundsException("Index: "+index+
1224                                                         ", Size: "+size);
1225                 return new COWSubListIterator<E>(l, index, offset, size);
1226             } finally {
1227                 lock.unlock();
1228             }
1229         }
1230
1231         public List<E> subList(int fromIndex, int toIndex) {
1232             final ReentrantLock lock = l.lock;
1233             lock.lock();
1234             try {
1235                 checkForComodification();
1236                 if (fromIndex<0 || toIndex>size)
1237                     throw new IndexOutOfBoundsException();
1238                 return new COWSubList<E>(l, fromIndex + offset,
1239                                          toIndex + offset);
1240             } finally {
1241                 lock.unlock();
1242             }
1243         }
1244
1245     }
1246
1247
1248     private static class COWSubListIterator<E> implements ListIterator<E> {
1249         private final ListIterator<E> i;
1250         private final int index;
1251         private final int offset;
1252         private final int size;
1253
1254         COWSubListIterator(List<E> l, int index, int offset,
1255                            int size) {
1256             this.index = index;
1257             this.offset = offset;
1258             this.size = size;
1259             i = l.listIterator(index+offset);
1260         }
1261
1262         public boolean hasNext() {
1263             return nextIndex() < size;
1264         }
1265
1266         public E next() {
1267             if (hasNext())
1268                 return i.next();
1269             else
1270                 throw new NoSuchElementException();
1271         }
1272
1273         public boolean hasPrevious() {
1274             return previousIndex() >= 0;
1275         }
1276
1277         public E previous() {
1278             if (hasPrevious())
1279                 return i.previous();
1280             else
1281                 throw new NoSuchElementException();
1282         }
1283
1284         public int nextIndex() {
1285             return i.nextIndex() - offset;
1286         }
1287
1288         public int previousIndex() {
1289             return i.previousIndex() - offset;
1290         }
1291
1292         public void remove() {
1293             throw new UnsupportedOperationException();
1294         }
1295
1296         public void set(E e) {
1297             throw new UnsupportedOperationException();
1298         }
1299
1300         public void add(E e) {
1301             throw new UnsupportedOperationException();
1302         }
1303     }
1304
1305     // Support for resetting lock while deserializing
1306     private static final Unsafe unsafe = Unsafe.getUnsafe();
1307     private static final long lockOffset;
1308     static {
1309         try {
1310             lockOffset = unsafe.objectFieldOffset
1311                 (CopyOnWriteArrayList.class.getDeclaredField("lock"));
1312             } catch (Exception ex) { throw new Error(ex); }
1313     }
1314     private void resetLock() {
1315         unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
1316     }
1317 }