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