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