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