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.ArrayList;
40 import java.util.Arrays;
41 import java.util.Collection;
42 import java.util.Collections;
43 import java.util.Comparator;
44 import java.util.ConcurrentModificationException;
45 import java.util.Iterator;
46 import java.util.List;
47 import java.util.ListIterator;
48 import java.util.NoSuchElementException;
49 import java.util.Objects;
50 import java.util.RandomAccess;
51 import java.util.Spliterator;
52 import java.util.Spliterators;
53 import java.util.function.Consumer;
54 import java.util.function.IntFunction;
55 import java.util.function.Predicate;
56 import java.util.function.UnaryOperator;
57 import java.util.stream.Stream;
58 import java.util.stream.StreamSupport;
59 import jdk.internal.access.SharedSecrets;
60 import jdk.internal.util.ArraysSupport;
61 
62 // Android-changed: Removed javadoc link to collections framework docs
63 /**
64  * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
65  * operations ({@code add}, {@code set}, and so on) are implemented by
66  * making a fresh copy of the underlying array.
67  *
68  * <p>This is ordinarily too costly, but may be <em>more</em> efficient
69  * than alternatives when traversal operations vastly outnumber
70  * mutations, and is useful when you cannot or don't want to
71  * synchronize traversals, yet need to preclude interference among
72  * concurrent threads.  The "snapshot" style iterator method uses a
73  * reference to the state of the array at the point that the iterator
74  * was created. This array never changes during the lifetime of the
75  * iterator, so interference is impossible and the iterator is
76  * guaranteed not to throw {@code ConcurrentModificationException}.
77  * The iterator will not reflect additions, removals, or changes to
78  * the list since the iterator was created.  Element-changing
79  * operations on iterators themselves ({@code remove}, {@code set}, and
80  * {@code add}) are not supported. These methods throw
81  * {@code UnsupportedOperationException}.
82  *
83  * <p>All elements are permitted, including {@code null}.
84  *
85  * <p>Memory consistency effects: As with other concurrent
86  * collections, actions in a thread prior to placing an object into a
87  * {@code CopyOnWriteArrayList}
88  * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
89  * actions subsequent to the access or removal of that element from
90  * the {@code CopyOnWriteArrayList} in another thread.
91  *
92  * <p>This class is a member of the
93  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
94  * Java Collections Framework</a>.
95  *
96  * @since 1.5
97  * @author Doug Lea
98  * @param <E> the type of elements held in this list
99  */
100 public class CopyOnWriteArrayList<E>
101     implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
102     private static final long serialVersionUID = 8673264195747942595L;
103 
104     /**
105      * The lock protecting all mutators.  (We have a mild preference
106      * for builtin monitors over ReentrantLock when either will do.)
107      */
108     final transient Object lock = new Object();
109 
110     /** The array, accessed only via getArray/setArray. */
111     private transient volatile Object[] array;
112 
113     /**
114      * Gets the array.  Non-private so as to also be accessible
115      * from CopyOnWriteArraySet class.
116      */
getArray()117     final Object[] getArray() {
118         return array;
119     }
120 
121     /**
122      * Sets the array.
123      */
setArray(Object[] a)124     final void setArray(Object[] a) {
125         array = a;
126     }
127 
128     /**
129      * Creates an empty list.
130      */
CopyOnWriteArrayList()131     public CopyOnWriteArrayList() {
132         setArray(new Object[0]);
133     }
134 
135     /**
136      * Creates a list containing the elements of the specified
137      * collection, in the order they are returned by the collection's
138      * iterator.
139      *
140      * @param c the collection of initially held elements
141      * @throws NullPointerException if the specified collection is null
142      */
CopyOnWriteArrayList(Collection<? extends E> c)143     public CopyOnWriteArrayList(Collection<? extends E> c) {
144         Object[] es;
145         if (c.getClass() == CopyOnWriteArrayList.class)
146             es = ((CopyOnWriteArrayList<?>)c).getArray();
147         else {
148             es = c.toArray();
149             // Android-changed: Defend against c.toArray (incorrectly) not returning Object[]
150             //                  (see b/204397945)
151             // if (c.getClass() != java.util.ArrayList.class)
152             if (es.getClass() != Object[].class)
153                 es = Arrays.copyOf(es, es.length, Object[].class);
154         }
155         setArray(es);
156     }
157 
158     /**
159      * Creates a list holding a copy of the given array.
160      *
161      * @param toCopyIn the array (a copy of this array is used as the
162      *        internal array)
163      * @throws NullPointerException if the specified array is null
164      */
CopyOnWriteArrayList(E[] toCopyIn)165     public CopyOnWriteArrayList(E[] toCopyIn) {
166         setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
167     }
168 
169     /**
170      * Returns the number of elements in this list.
171      *
172      * @return the number of elements in this list
173      */
size()174     public int size() {
175         return getArray().length;
176     }
177 
178     /**
179      * Returns {@code true} if this list contains no elements.
180      *
181      * @return {@code true} if this list contains no elements
182      */
isEmpty()183     public boolean isEmpty() {
184         return size() == 0;
185     }
186 
187     /**
188      * static version of indexOf, to allow repeated calls without
189      * needing to re-acquire array each time.
190      * @param o element to search for
191      * @param es the array
192      * @param from first index to search
193      * @param to one past last index to search
194      * @return index of element, or -1 if absent
195      */
indexOfRange(Object o, Object[] es, int from, int to)196     private static int indexOfRange(Object o, Object[] es, int from, int to) {
197         if (o == null) {
198             for (int i = from; i < to; i++)
199                 if (es[i] == null)
200                     return i;
201         } else {
202             for (int i = from; i < to; i++)
203                 if (o.equals(es[i]))
204                     return i;
205         }
206         return -1;
207     }
208 
209     /**
210      * static version of lastIndexOf.
211      * @param o element to search for
212      * @param es the array
213      * @param from index of first element of range, last element to search
214      * @param to one past last element of range, first element to search
215      * @return index of element, or -1 if absent
216      */
lastIndexOfRange(Object o, Object[] es, int from, int to)217     private static int lastIndexOfRange(Object o, Object[] es, int from, int to) {
218         if (o == null) {
219             for (int i = to - 1; i >= from; i--)
220                 if (es[i] == null)
221                     return i;
222         } else {
223             for (int i = to - 1; i >= from; i--)
224                 if (o.equals(es[i]))
225                     return i;
226         }
227         return -1;
228     }
229 
230     /**
231      * Returns {@code true} if this list contains the specified element.
232      * More formally, returns {@code true} if and only if this list contains
233      * at least one element {@code e} such that {@code Objects.equals(o, e)}.
234      *
235      * @param o element whose presence in this list is to be tested
236      * @return {@code true} if this list contains the specified element
237      */
contains(Object o)238     public boolean contains(Object o) {
239         return indexOf(o) >= 0;
240     }
241 
242     /**
243      * {@inheritDoc}
244      */
indexOf(Object o)245     public int indexOf(Object o) {
246         Object[] es = getArray();
247         return indexOfRange(o, es, 0, es.length);
248     }
249 
250     /**
251      * Returns the index of the first occurrence of the specified element in
252      * this list, searching forwards from {@code index}, or returns -1 if
253      * the element is not found.
254      * More formally, returns the lowest index {@code i} such that
255      * {@code i >= index && Objects.equals(get(i), e)},
256      * or -1 if there is no such index.
257      *
258      * @param e element to search for
259      * @param index index to start searching from
260      * @return the index of the first occurrence of the element in
261      *         this list at position {@code index} or later in the list;
262      *         {@code -1} if the element is not found.
263      * @throws IndexOutOfBoundsException if the specified index is negative
264      */
indexOf(E e, int index)265     public int indexOf(E e, int index) {
266         Object[] es = getArray();
267         return indexOfRange(e, es, index, es.length);
268     }
269 
270     /**
271      * {@inheritDoc}
272      */
lastIndexOf(Object o)273     public int lastIndexOf(Object o) {
274         Object[] es = getArray();
275         return lastIndexOfRange(o, es, 0, es.length);
276     }
277 
278     /**
279      * Returns the index of the last occurrence of the specified element in
280      * this list, searching backwards from {@code index}, or returns -1 if
281      * the element is not found.
282      * More formally, returns the highest index {@code i} such that
283      * {@code i <= index && Objects.equals(get(i), e)},
284      * or -1 if there is no such index.
285      *
286      * @param e element to search for
287      * @param index index to start searching backwards from
288      * @return the index of the last occurrence of the element at position
289      *         less than or equal to {@code index} in this list;
290      *         -1 if the element is not found.
291      * @throws IndexOutOfBoundsException if the specified index is greater
292      *         than or equal to the current size of this list
293      */
lastIndexOf(E e, int index)294     public int lastIndexOf(E e, int index) {
295         Object[] es = getArray();
296         return lastIndexOfRange(e, es, 0, index + 1);
297     }
298 
299     /**
300      * Returns a shallow copy of this list.  (The elements themselves
301      * are not copied.)
302      *
303      * @return a clone of this list
304      */
clone()305     public Object clone() {
306         try {
307             @SuppressWarnings("unchecked")
308             CopyOnWriteArrayList<E> clone =
309                 (CopyOnWriteArrayList<E>) super.clone();
310             clone.resetLock();
311             // Unlike in readObject, here we cannot visibility-piggyback on the
312             // volatile write in setArray().
313             VarHandle.releaseFence();
314             return clone;
315         } catch (CloneNotSupportedException e) {
316             // this shouldn't happen, since we are Cloneable
317             throw new InternalError();
318         }
319     }
320 
321     /**
322      * Returns an array containing all of the elements in this list
323      * in proper sequence (from first to last element).
324      *
325      * <p>The returned array will be "safe" in that no references to it are
326      * maintained by this list.  (In other words, this method must allocate
327      * a new array).  The caller is thus free to modify the returned array.
328      *
329      * <p>This method acts as bridge between array-based and collection-based
330      * APIs.
331      *
332      * @return an array containing all the elements in this list
333      */
toArray()334     public Object[] toArray() {
335         return getArray().clone();
336     }
337 
338     /**
339      * Returns an array containing all of the elements in this list in
340      * proper sequence (from first to last element); the runtime type of
341      * the returned array is that of the specified array.  If the list fits
342      * in the specified array, it is returned therein.  Otherwise, a new
343      * array is allocated with the runtime type of the specified array and
344      * the size of this list.
345      *
346      * <p>If this list fits in the specified array with room to spare
347      * (i.e., the array has more elements than this list), the element in
348      * the array immediately following the end of the list is set to
349      * {@code null}.  (This is useful in determining the length of this
350      * list <i>only</i> if the caller knows that this list does not contain
351      * any null elements.)
352      *
353      * <p>Like the {@link #toArray()} method, this method acts as bridge between
354      * array-based and collection-based APIs.  Further, this method allows
355      * precise control over the runtime type of the output array, and may,
356      * under certain circumstances, be used to save allocation costs.
357      *
358      * <p>Suppose {@code x} is a list known to contain only strings.
359      * The following code can be used to dump the list into a newly
360      * allocated array of {@code String}:
361      *
362      * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
363      *
364      * Note that {@code toArray(new Object[0])} is identical in function to
365      * {@code toArray()}.
366      *
367      * @param a the array into which the elements of the list are to
368      *          be stored, if it is big enough; otherwise, a new array of the
369      *          same runtime type is allocated for this purpose.
370      * @return an array containing all the elements in this list
371      * @throws ArrayStoreException if the runtime type of the specified array
372      *         is not a supertype of the runtime type of every element in
373      *         this list
374      * @throws NullPointerException if the specified array is null
375      */
376     @SuppressWarnings("unchecked")
toArray(T[] a)377     public <T> T[] toArray(T[] a) {
378         Object[] es = getArray();
379         int len = es.length;
380         if (a.length < len)
381             return (T[]) Arrays.copyOf(es, len, a.getClass());
382         else {
383             System.arraycopy(es, 0, a, 0, len);
384             if (a.length > len)
385                 a[len] = null;
386             return a;
387         }
388     }
389 
390     // Positional Access Operations
391 
392     @SuppressWarnings("unchecked")
elementAt(Object[] a, int index)393     static <E> E elementAt(Object[] a, int index) {
394         return (E) a[index];
395     }
396 
outOfBounds(int index, int size)397     static String outOfBounds(int index, int size) {
398         return "Index: " + index + ", Size: " + size;
399     }
400 
401     /**
402      * {@inheritDoc}
403      *
404      * @throws IndexOutOfBoundsException {@inheritDoc}
405      */
get(int index)406     public E get(int index) {
407         return elementAt(getArray(), index);
408     }
409 
410     /**
411      * {@inheritDoc}
412      *
413      * @throws NoSuchElementException {@inheritDoc}
414      * @since 21
415      */
getFirst()416     public E getFirst() {
417         Object[] es = getArray();
418         if (es.length == 0)
419             throw new NoSuchElementException();
420         else
421             return elementAt(es, 0);
422     }
423 
424     /**
425      * {@inheritDoc}
426      *
427      * @throws NoSuchElementException {@inheritDoc}
428      * @since 21
429      */
getLast()430     public E getLast() {
431         Object[] es = getArray();
432         if (es.length == 0)
433             throw new NoSuchElementException();
434         else
435             return elementAt(es, es.length - 1);
436     }
437 
438     /**
439      * Replaces the element at the specified position in this list with the
440      * specified element.
441      *
442      * @throws IndexOutOfBoundsException {@inheritDoc}
443      */
set(int index, E element)444     public E set(int index, E element) {
445         synchronized (lock) {
446             Object[] es = getArray();
447             E oldValue = elementAt(es, index);
448 
449             if (oldValue != element) {
450                 es = es.clone();
451                 es[index] = element;
452             }
453             // Ensure volatile write semantics even when oldvalue == element
454             setArray(es);
455             return oldValue;
456         }
457     }
458 
459     /**
460      * Appends the specified element to the end of this list.
461      *
462      * @param e element to be appended to this list
463      * @return {@code true} (as specified by {@link Collection#add})
464      */
add(E e)465     public boolean add(E e) {
466         synchronized (lock) {
467             Object[] es = getArray();
468             int len = es.length;
469             es = Arrays.copyOf(es, len + 1);
470             es[len] = e;
471             setArray(es);
472             return true;
473         }
474     }
475 
476     /**
477      * Inserts the specified element at the specified position in this
478      * list. Shifts the element currently at that position (if any) and
479      * any subsequent elements to the right (adds one to their indices).
480      *
481      * @throws IndexOutOfBoundsException {@inheritDoc}
482      */
add(int index, E element)483     public void add(int index, E element) {
484         synchronized (lock) {
485             Object[] es = getArray();
486             int len = es.length;
487             if (index > len || index < 0)
488                 throw new IndexOutOfBoundsException(outOfBounds(index, len));
489             Object[] newElements;
490             int numMoved = len - index;
491             if (numMoved == 0)
492                 newElements = Arrays.copyOf(es, len + 1);
493             else {
494                 newElements = new Object[len + 1];
495                 System.arraycopy(es, 0, newElements, 0, index);
496                 System.arraycopy(es, index, newElements, index + 1,
497                                  numMoved);
498             }
499             newElements[index] = element;
500             setArray(newElements);
501         }
502     }
503 
504     /**
505      * {@inheritDoc}
506      *
507      * @since 21
508      */
addFirst(E e)509     public void addFirst(E e) {
510         add(0, e);
511     }
512 
513     /**
514      * {@inheritDoc}
515      *
516      * @since 21
517      */
addLast(E e)518     public void addLast(E e) {
519         synchronized (lock) {
520             add(getArray().length, e);
521         }
522     }
523 
524     /**
525      * Removes the element at the specified position in this list.
526      * Shifts any subsequent elements to the left (subtracts one from their
527      * indices).  Returns the element that was removed from the list.
528      *
529      * @throws IndexOutOfBoundsException {@inheritDoc}
530      */
remove(int index)531     public E remove(int index) {
532         synchronized (lock) {
533             Object[] es = getArray();
534             int len = es.length;
535             E oldValue = elementAt(es, index);
536             int numMoved = len - index - 1;
537             Object[] newElements;
538             if (numMoved == 0)
539                 newElements = Arrays.copyOf(es, len - 1);
540             else {
541                 newElements = new Object[len - 1];
542                 System.arraycopy(es, 0, newElements, 0, index);
543                 System.arraycopy(es, index + 1, newElements, index,
544                                  numMoved);
545             }
546             setArray(newElements);
547             return oldValue;
548         }
549     }
550 
551     /**
552      * {@inheritDoc}
553      *
554      * @throws NoSuchElementException {@inheritDoc}
555      * @since 21
556      */
removeFirst()557     public E removeFirst() {
558         synchronized (lock) {
559             if (getArray().length == 0)
560                 throw new NoSuchElementException();
561             else
562                 return remove(0);
563         }
564     }
565 
566     /**
567      * {@inheritDoc}
568      *
569      * @throws NoSuchElementException {@inheritDoc}
570      * @since 21
571      */
removeLast()572     public E removeLast() {
573         synchronized (lock) {
574             int size = getArray().length;
575             if (size == 0)
576                 throw new NoSuchElementException();
577             else
578                 return remove(size - 1);
579         }
580     }
581 
582     /**
583      * Removes the first occurrence of the specified element from this list,
584      * if it is present.  If this list does not contain the element, it is
585      * unchanged.  More formally, removes the element with the lowest index
586      * {@code i} such that {@code Objects.equals(o, get(i))}
587      * (if such an element exists).  Returns {@code true} if this list
588      * contained the specified element (or equivalently, if this list
589      * changed as a result of the call).
590      *
591      * @param o element to be removed from this list, if present
592      * @return {@code true} if this list contained the specified element
593      */
remove(Object o)594     public boolean remove(Object o) {
595         Object[] snapshot = getArray();
596         int index = indexOfRange(o, snapshot, 0, snapshot.length);
597         return index >= 0 && remove(o, snapshot, index);
598     }
599 
600     /**
601      * A version of remove(Object) using the strong hint that given
602      * recent snapshot contains o at the given index.
603      */
remove(Object o, Object[] snapshot, int index)604     private boolean remove(Object o, Object[] snapshot, int index) {
605         synchronized (lock) {
606             Object[] current = getArray();
607             int len = current.length;
608             if (snapshot != current) findIndex: {
609                 int prefix = Math.min(index, len);
610                 for (int i = 0; i < prefix; i++) {
611                     if (current[i] != snapshot[i]
612                         && Objects.equals(o, current[i])) {
613                         index = i;
614                         break findIndex;
615                     }
616                 }
617                 if (index >= len)
618                     return false;
619                 if (current[index] == o)
620                     break findIndex;
621                 index = indexOfRange(o, current, index, len);
622                 if (index < 0)
623                     return false;
624             }
625             Object[] newElements = new Object[len - 1];
626             System.arraycopy(current, 0, newElements, 0, index);
627             System.arraycopy(current, index + 1,
628                              newElements, index,
629                              len - index - 1);
630             setArray(newElements);
631             return true;
632         }
633     }
634 
635     /**
636      * Removes from this list all of the elements whose index is between
637      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
638      * Shifts any succeeding elements to the left (reduces their index).
639      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
640      * (If {@code toIndex==fromIndex}, this operation has no effect.)
641      *
642      * @param fromIndex index of first element to be removed
643      * @param toIndex index after last element to be removed
644      * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
645      *         ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
646      */
removeRange(int fromIndex, int toIndex)647     void removeRange(int fromIndex, int toIndex) {
648         synchronized (lock) {
649             Object[] es = getArray();
650             int len = es.length;
651 
652             if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
653                 throw new IndexOutOfBoundsException();
654             int newlen = len - (toIndex - fromIndex);
655             int numMoved = len - toIndex;
656             if (numMoved == 0)
657                 setArray(Arrays.copyOf(es, newlen));
658             else {
659                 Object[] newElements = new Object[newlen];
660                 System.arraycopy(es, 0, newElements, 0, fromIndex);
661                 System.arraycopy(es, toIndex, newElements,
662                                  fromIndex, numMoved);
663                 setArray(newElements);
664             }
665         }
666     }
667 
668     /**
669      * Appends the element, if not present.
670      *
671      * @param e element to be added to this list, if absent
672      * @return {@code true} if the element was added
673      */
addIfAbsent(E e)674     public boolean addIfAbsent(E e) {
675         Object[] snapshot = getArray();
676         return indexOfRange(e, snapshot, 0, snapshot.length) < 0
677             && addIfAbsent(e, snapshot);
678     }
679 
680     /**
681      * A version of addIfAbsent using the strong hint that given
682      * recent snapshot does not contain e.
683      */
addIfAbsent(E e, Object[] snapshot)684     private boolean addIfAbsent(E e, Object[] snapshot) {
685         synchronized (lock) {
686             Object[] current = getArray();
687             int len = current.length;
688             if (snapshot != current) {
689                 // Optimize for lost race to another addXXX operation
690                 int common = Math.min(snapshot.length, len);
691                 for (int i = 0; i < common; i++)
692                     if (current[i] != snapshot[i]
693                         && Objects.equals(e, current[i]))
694                         return false;
695                 if (indexOfRange(e, current, common, len) >= 0)
696                         return false;
697             }
698             Object[] newElements = Arrays.copyOf(current, len + 1);
699             newElements[len] = e;
700             setArray(newElements);
701             return true;
702         }
703     }
704 
705     /**
706      * Returns {@code true} if this list contains all of the elements of the
707      * specified collection.
708      *
709      * @param c collection to be checked for containment in this list
710      * @return {@code true} if this list contains all of the elements of the
711      *         specified collection
712      * @throws NullPointerException if the specified collection is null
713      * @see #contains(Object)
714      */
containsAll(Collection<?> c)715     public boolean containsAll(Collection<?> c) {
716         Object[] es = getArray();
717         int len = es.length;
718         for (Object e : c) {
719             if (indexOfRange(e, es, 0, len) < 0)
720                 return false;
721         }
722         return true;
723     }
724 
725     /**
726      * Removes from this list all of its elements that are contained in
727      * the specified collection. This is a particularly expensive operation
728      * in this class because of the need for an internal temporary array.
729      *
730      * @param c collection containing elements to be removed from this list
731      * @return {@code true} if this list changed as a result of the call
732      * @throws ClassCastException if the class of an element of this list
733      *         is incompatible with the specified collection
734      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
735      * @throws NullPointerException if this list contains a null element and the
736      *         specified collection does not permit null elements
737      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>),
738      *         or if the specified collection is null
739      * @see #remove(Object)
740      */
removeAll(Collection<?> c)741     public boolean removeAll(Collection<?> c) {
742         Objects.requireNonNull(c);
743         return bulkRemove(e -> c.contains(e));
744     }
745 
746     /**
747      * Retains only the elements in this list that are contained in the
748      * specified collection.  In other words, removes from this list all of
749      * its elements that are not contained in the specified collection.
750      *
751      * @param c collection containing elements to be retained in this list
752      * @return {@code true} if this list changed as a result of the call
753      * @throws ClassCastException if the class of an element of this list
754      *         is incompatible with the specified collection
755      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
756      * @throws NullPointerException if this list contains a null element and the
757      *         specified collection does not permit null elements
758      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>),
759      *         or if the specified collection is null
760      * @see #remove(Object)
761      */
retainAll(Collection<?> c)762     public boolean retainAll(Collection<?> c) {
763         Objects.requireNonNull(c);
764         return bulkRemove(e -> !c.contains(e));
765     }
766 
767     /**
768      * Appends all of the elements in the specified collection that
769      * are not already contained in this list, to the end of
770      * this list, in the order that they are returned by the
771      * specified collection's iterator.
772      *
773      * @param c collection containing elements to be added to this list
774      * @return the number of elements added
775      * @throws NullPointerException if the specified collection is null
776      * @see #addIfAbsent(Object)
777      */
addAllAbsent(Collection<? extends E> c)778     public int addAllAbsent(Collection<? extends E> c) {
779         Object[] cs = c.toArray();
780         if (c.getClass() != ArrayList.class) {
781             cs = cs.clone();
782         }
783         if (cs.length == 0)
784             return 0;
785         synchronized (lock) {
786             Object[] es = getArray();
787             int len = es.length;
788             int added = 0;
789             // uniquify and compact elements in cs
790             for (int i = 0; i < cs.length; ++i) {
791                 Object e = cs[i];
792                 if (indexOfRange(e, es, 0, len) < 0 &&
793                     indexOfRange(e, cs, 0, added) < 0)
794                     cs[added++] = e;
795             }
796             if (added > 0) {
797                 Object[] newElements = Arrays.copyOf(es, len + added);
798                 System.arraycopy(cs, 0, newElements, len, added);
799                 setArray(newElements);
800             }
801             return added;
802         }
803     }
804 
805     /**
806      * Removes all of the elements from this list.
807      * The list will be empty after this call returns.
808      */
clear()809     public void clear() {
810         synchronized (lock) {
811             setArray(new Object[0]);
812         }
813     }
814 
815     /**
816      * Appends all of the elements in the specified collection to the end
817      * of this list, in the order that they are returned by the specified
818      * collection's iterator.
819      *
820      * @param c collection containing elements to be added to this list
821      * @return {@code true} if this list changed as a result of the call
822      * @throws NullPointerException if the specified collection is null
823      * @see #add(Object)
824      */
addAll(Collection<? extends E> c)825     public boolean addAll(Collection<? extends E> c) {
826         Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
827             ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
828         if (cs.length == 0)
829             return false;
830         synchronized (lock) {
831             Object[] es = getArray();
832             int len = es.length;
833             Object[] newElements;
834             if (len == 0 && (c.getClass() == CopyOnWriteArrayList.class ||
835                              c.getClass() == ArrayList.class)) {
836                 newElements = cs;
837             } else {
838                 newElements = Arrays.copyOf(es, len + cs.length);
839                 System.arraycopy(cs, 0, newElements, len, cs.length);
840             }
841             setArray(newElements);
842             return true;
843         }
844     }
845 
846     /**
847      * Inserts all of the elements in the specified collection into this
848      * list, starting at the specified position.  Shifts the element
849      * currently at that position (if any) and any subsequent elements to
850      * the right (increases their indices).  The new elements will appear
851      * in this list in the order that they are returned by the
852      * specified collection's iterator.
853      *
854      * @param index index at which to insert the first element
855      *        from the specified collection
856      * @param c collection containing elements to be added to this list
857      * @return {@code true} if this list changed as a result of the call
858      * @throws IndexOutOfBoundsException {@inheritDoc}
859      * @throws NullPointerException if the specified collection is null
860      * @see #add(int,Object)
861      */
addAll(int index, Collection<? extends E> c)862     public boolean addAll(int index, Collection<? extends E> c) {
863         Object[] cs = c.toArray();
864         synchronized (lock) {
865             Object[] es = getArray();
866             int len = es.length;
867             if (index > len || index < 0)
868                 throw new IndexOutOfBoundsException(outOfBounds(index, len));
869             if (cs.length == 0)
870                 return false;
871             int numMoved = len - index;
872             Object[] newElements;
873             if (numMoved == 0)
874                 newElements = Arrays.copyOf(es, len + cs.length);
875             else {
876                 newElements = new Object[len + cs.length];
877                 System.arraycopy(es, 0, newElements, 0, index);
878                 System.arraycopy(es, index,
879                                  newElements, index + cs.length,
880                                  numMoved);
881             }
882             System.arraycopy(cs, 0, newElements, index, cs.length);
883             setArray(newElements);
884             return true;
885         }
886     }
887 
888     /**
889      * @throws NullPointerException {@inheritDoc}
890      */
forEach(Consumer<? super E> action)891     public void forEach(Consumer<? super E> action) {
892         Objects.requireNonNull(action);
893         for (Object x : getArray()) {
894             @SuppressWarnings("unchecked") E e = (E) x;
895             action.accept(e);
896         }
897     }
898 
899     /**
900      * @throws NullPointerException {@inheritDoc}
901      */
removeIf(Predicate<? super E> filter)902     public boolean removeIf(Predicate<? super E> filter) {
903         Objects.requireNonNull(filter);
904         return bulkRemove(filter);
905     }
906 
907     // A tiny bit set implementation
908 
nBits(int n)909     private static long[] nBits(int n) {
910         return new long[((n - 1) >> 6) + 1];
911     }
setBit(long[] bits, int i)912     private static void setBit(long[] bits, int i) {
913         bits[i >> 6] |= 1L << i;
914     }
isClear(long[] bits, int i)915     private static boolean isClear(long[] bits, int i) {
916         return (bits[i >> 6] & (1L << i)) == 0;
917     }
918 
bulkRemove(Predicate<? super E> filter)919     private boolean bulkRemove(Predicate<? super E> filter) {
920         synchronized (lock) {
921             return bulkRemove(filter, 0, getArray().length);
922         }
923     }
924 
bulkRemove(Predicate<? super E> filter, int i, int end)925     boolean bulkRemove(Predicate<? super E> filter, int i, int end) {
926         // assert Thread.holdsLock(lock);
927         final Object[] es = getArray();
928         // Optimize for initial run of survivors
929         for (; i < end && !filter.test(elementAt(es, i)); i++)
930             ;
931         if (i < end) {
932             final int beg = i;
933             final long[] deathRow = nBits(end - beg);
934             int deleted = 1;
935             deathRow[0] = 1L;   // set bit 0
936             for (i = beg + 1; i < end; i++)
937                 if (filter.test(elementAt(es, i))) {
938                     setBit(deathRow, i - beg);
939                     deleted++;
940                 }
941             // Did filter reentrantly modify the list?
942             if (es != getArray())
943                 throw new ConcurrentModificationException();
944             final Object[] newElts = Arrays.copyOf(es, es.length - deleted);
945             int w = beg;
946             for (i = beg; i < end; i++)
947                 if (isClear(deathRow, i - beg))
948                     newElts[w++] = es[i];
949             System.arraycopy(es, i, newElts, w, es.length - i);
950             setArray(newElts);
951             return true;
952         } else {
953             if (es != getArray())
954                 throw new ConcurrentModificationException();
955             return false;
956         }
957     }
958 
replaceAll(UnaryOperator<E> operator)959     public void replaceAll(UnaryOperator<E> operator) {
960         synchronized (lock) {
961             replaceAllRange(operator, 0, getArray().length);
962         }
963     }
964 
replaceAllRange(UnaryOperator<E> operator, int i, int end)965     void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
966         // assert Thread.holdsLock(lock);
967         Objects.requireNonNull(operator);
968         final Object[] es = getArray().clone();
969         for (; i < end; i++)
970             es[i] = operator.apply(elementAt(es, i));
971         setArray(es);
972     }
973 
sort(Comparator<? super E> c)974     public void sort(Comparator<? super E> c) {
975         synchronized (lock) {
976             sortRange(c, 0, getArray().length);
977         }
978     }
979 
980     @SuppressWarnings("unchecked")
sortRange(Comparator<? super E> c, int i, int end)981     void sortRange(Comparator<? super E> c, int i, int end) {
982         // assert Thread.holdsLock(lock);
983         final Object[] es = getArray().clone();
984         Arrays.sort(es, i, end, (Comparator<Object>)c);
985         setArray(es);
986     }
987 
988     /**
989      * Saves this list to a stream (that is, serializes it).
990      *
991      * @param s the stream
992      * @throws java.io.IOException if an I/O error occurs
993      * @serialData The length of the array backing the list is emitted
994      *               (int), followed by all of its elements (each an Object)
995      *               in the proper order.
996      */
writeObject(java.io.ObjectOutputStream s)997     private void writeObject(java.io.ObjectOutputStream s)
998         throws java.io.IOException {
999 
1000         s.defaultWriteObject();
1001 
1002         Object[] es = getArray();
1003         // Write out array length
1004         s.writeInt(es.length);
1005 
1006         // Write out all elements in the proper order.
1007         for (Object element : es)
1008             s.writeObject(element);
1009     }
1010 
1011     /**
1012      * Reconstitutes this list from a stream (that is, deserializes it).
1013      * @param s the stream
1014      * @throws ClassNotFoundException if the class of a serialized object
1015      *         could not be found
1016      * @throws java.io.IOException if an I/O error occurs
1017      */
readObject(java.io.ObjectInputStream s)1018     private void readObject(java.io.ObjectInputStream s)
1019         throws java.io.IOException, ClassNotFoundException {
1020 
1021         s.defaultReadObject();
1022 
1023         // bind to new lock
1024         resetLock();
1025 
1026         // Read in array length and allocate array
1027         int len = s.readInt();
1028         SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len);
1029         Object[] es = new Object[len];
1030 
1031         // Read in all elements in the proper order.
1032         for (int i = 0; i < len; i++)
1033             es[i] = s.readObject();
1034         setArray(es);
1035     }
1036 
1037     /**
1038      * Returns a string representation of this list.  The string
1039      * representation consists of the string representations of the list's
1040      * elements in the order they are returned by its iterator, enclosed in
1041      * square brackets ({@code "[]"}).  Adjacent elements are separated by
1042      * the characters {@code ", "} (comma and space).  Elements are
1043      * converted to strings as by {@link String#valueOf(Object)}.
1044      *
1045      * @return a string representation of this list
1046      */
toString()1047     public String toString() {
1048         return Arrays.toString(getArray());
1049     }
1050 
1051     /**
1052      * Compares the specified object with this list for equality.
1053      * Returns {@code true} if the specified object is the same object
1054      * as this object, or if it is also a {@link List} and the sequence
1055      * of elements returned by an {@linkplain List#iterator() iterator}
1056      * over the specified list is the same as the sequence returned by
1057      * an iterator over this list.  The two sequences are considered to
1058      * be the same if they have the same length and corresponding
1059      * elements at the same position in the sequence are <em>equal</em>.
1060      * Two elements {@code e1} and {@code e2} are considered
1061      * <em>equal</em> if {@code Objects.equals(e1, e2)}.
1062      *
1063      * @param o the object to be compared for equality with this list
1064      * @return {@code true} if the specified object is equal to this list
1065      */
equals(Object o)1066     public boolean equals(Object o) {
1067         if (o == this)
1068             return true;
1069         if (!(o instanceof List))
1070             return false;
1071 
1072         List<?> list = (List<?>)o;
1073         Iterator<?> it = list.iterator();
1074         for (Object element : getArray())
1075             if (!it.hasNext() || !Objects.equals(element, it.next()))
1076                 return false;
1077         return !it.hasNext();
1078     }
1079 
hashCodeOfRange(Object[] es, int from, int to)1080     private static int hashCodeOfRange(Object[] es, int from, int to) {
1081         int hashCode = 1;
1082         for (int i = from; i < to; i++) {
1083             Object x = es[i];
1084             hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
1085         }
1086         return hashCode;
1087     }
1088 
1089     /**
1090      * Returns the hash code value for this list.
1091      *
1092      * <p>This implementation uses the definition in {@link List#hashCode}.
1093      *
1094      * @return the hash code value for this list
1095      */
hashCode()1096     public int hashCode() {
1097         Object[] es = getArray();
1098         return hashCodeOfRange(es, 0, es.length);
1099     }
1100 
1101     /**
1102      * Returns an iterator over the elements in this list in proper sequence.
1103      *
1104      * <p>The returned iterator provides a snapshot of the state of the list
1105      * when the iterator was constructed. No synchronization is needed while
1106      * traversing the iterator. The iterator does <em>NOT</em> support the
1107      * {@code remove} method.
1108      *
1109      * @return an iterator over the elements in this list in proper sequence
1110      */
iterator()1111     public Iterator<E> iterator() {
1112         return new COWIterator<E>(getArray(), 0);
1113     }
1114 
1115     /**
1116      * {@inheritDoc}
1117      *
1118      * <p>The returned iterator provides a snapshot of the state of the list
1119      * when the iterator was constructed. No synchronization is needed while
1120      * traversing the iterator. The iterator does <em>NOT</em> support the
1121      * {@code remove}, {@code set} or {@code add} methods.
1122      */
listIterator()1123     public ListIterator<E> listIterator() {
1124         return new COWIterator<E>(getArray(), 0);
1125     }
1126 
1127     /**
1128      * {@inheritDoc}
1129      *
1130      * <p>The returned iterator provides a snapshot of the state of the list
1131      * when the iterator was constructed. No synchronization is needed while
1132      * traversing the iterator. The iterator does <em>NOT</em> support the
1133      * {@code remove}, {@code set} or {@code add} methods.
1134      *
1135      * @throws IndexOutOfBoundsException {@inheritDoc}
1136      */
listIterator(int index)1137     public ListIterator<E> listIterator(int index) {
1138         Object[] es = getArray();
1139         int len = es.length;
1140         if (index < 0 || index > len)
1141             throw new IndexOutOfBoundsException(outOfBounds(index, len));
1142 
1143         return new COWIterator<E>(es, index);
1144     }
1145 
1146     /**
1147      * Returns a {@link Spliterator} over the elements in this list.
1148      *
1149      * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE},
1150      * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and
1151      * {@link Spliterator#SUBSIZED}.
1152      *
1153      * <p>The spliterator provides a snapshot of the state of the list
1154      * when the spliterator was constructed. No synchronization is needed while
1155      * operating on the spliterator.
1156      *
1157      * @return a {@code Spliterator} over the elements in this list
1158      * @since 1.8
1159      */
spliterator()1160     public Spliterator<E> spliterator() {
1161         return Spliterators.spliterator
1162             (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
1163     }
1164 
1165     static final class COWIterator<E> implements ListIterator<E> {
1166         /** Snapshot of the array */
1167         private final Object[] snapshot;
1168         /** Index of element to be returned by subsequent call to next.  */
1169         private int cursor;
1170 
COWIterator(Object[] es, int initialCursor)1171         COWIterator(Object[] es, int initialCursor) {
1172             cursor = initialCursor;
1173             snapshot = es;
1174         }
1175 
hasNext()1176         public boolean hasNext() {
1177             return cursor < snapshot.length;
1178         }
1179 
hasPrevious()1180         public boolean hasPrevious() {
1181             return cursor > 0;
1182         }
1183 
1184         @SuppressWarnings("unchecked")
next()1185         public E next() {
1186             if (! hasNext())
1187                 throw new NoSuchElementException();
1188             return (E) snapshot[cursor++];
1189         }
1190 
1191         @SuppressWarnings("unchecked")
previous()1192         public E previous() {
1193             if (! hasPrevious())
1194                 throw new NoSuchElementException();
1195             return (E) snapshot[--cursor];
1196         }
1197 
nextIndex()1198         public int nextIndex() {
1199             return cursor;
1200         }
1201 
previousIndex()1202         public int previousIndex() {
1203             return cursor - 1;
1204         }
1205 
1206         /**
1207          * Not supported. Always throws UnsupportedOperationException.
1208          * @throws UnsupportedOperationException always; {@code remove}
1209          *         is not supported by this iterator.
1210          */
remove()1211         public void remove() {
1212             throw new UnsupportedOperationException();
1213         }
1214 
1215         /**
1216          * Not supported. Always throws UnsupportedOperationException.
1217          * @throws UnsupportedOperationException always; {@code set}
1218          *         is not supported by this iterator.
1219          */
set(E e)1220         public void set(E e) {
1221             throw new UnsupportedOperationException();
1222         }
1223 
1224         /**
1225          * Not supported. Always throws UnsupportedOperationException.
1226          * @throws UnsupportedOperationException always; {@code add}
1227          *         is not supported by this iterator.
1228          */
add(E e)1229         public void add(E e) {
1230             throw new UnsupportedOperationException();
1231         }
1232 
1233         @Override
forEachRemaining(Consumer<? super E> action)1234         public void forEachRemaining(Consumer<? super E> action) {
1235             Objects.requireNonNull(action);
1236             final int size = snapshot.length;
1237             int i = cursor;
1238             cursor = size;
1239             for (; i < size; i++)
1240                 action.accept(elementAt(snapshot, i));
1241         }
1242     }
1243 
1244     /**
1245      * Returns a view of the portion of this list between
1246      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
1247      * The returned list is backed by this list, so changes in the
1248      * returned list are reflected in this list.
1249      *
1250      * <p>The semantics of the list returned by this method become
1251      * undefined if the backing list (i.e., this list) is modified in
1252      * any way other than via the returned list.
1253      *
1254      * @param fromIndex low endpoint (inclusive) of the subList
1255      * @param toIndex high endpoint (exclusive) of the subList
1256      * @return a view of the specified range within this list
1257      * @throws IndexOutOfBoundsException {@inheritDoc}
1258      */
subList(int fromIndex, int toIndex)1259     public List<E> subList(int fromIndex, int toIndex) {
1260         synchronized (lock) {
1261             Object[] es = getArray();
1262             int len = es.length;
1263             int size = toIndex - fromIndex;
1264             if (fromIndex < 0 || toIndex > len || size < 0)
1265                 throw new IndexOutOfBoundsException();
1266             return new COWSubList(es, fromIndex, size);
1267         }
1268     }
1269 
1270     /**
1271      * Sublist for CopyOnWriteArrayList.
1272      */
1273     private class COWSubList implements List<E>, RandomAccess {
1274         private final int offset;
1275         private int size;
1276         private Object[] expectedArray;
1277 
COWSubList(Object[] es, int offset, int size)1278         COWSubList(Object[] es, int offset, int size) {
1279             // assert Thread.holdsLock(lock);
1280             expectedArray = es;
1281             this.offset = offset;
1282             this.size = size;
1283         }
1284 
checkForComodification()1285         private void checkForComodification() {
1286             // assert Thread.holdsLock(lock);
1287             if (getArray() != expectedArray)
1288                 throw new ConcurrentModificationException();
1289         }
1290 
getArrayChecked()1291         private Object[] getArrayChecked() {
1292             // assert Thread.holdsLock(lock);
1293             Object[] a = getArray();
1294             if (a != expectedArray)
1295                 throw new ConcurrentModificationException();
1296             return a;
1297         }
1298 
rangeCheck(int index)1299         private void rangeCheck(int index) {
1300             // assert Thread.holdsLock(lock);
1301             if (index < 0 || index >= size)
1302                 throw new IndexOutOfBoundsException(outOfBounds(index, size));
1303         }
1304 
rangeCheckForAdd(int index)1305         private void rangeCheckForAdd(int index) {
1306             // assert Thread.holdsLock(lock);
1307             if (index < 0 || index > size)
1308                 throw new IndexOutOfBoundsException(outOfBounds(index, size));
1309         }
1310 
toArray()1311         public Object[] toArray() {
1312             final Object[] es;
1313             final int offset;
1314             final int size;
1315             synchronized (lock) {
1316                 es = getArrayChecked();
1317                 offset = this.offset;
1318                 size = this.size;
1319             }
1320             return Arrays.copyOfRange(es, offset, offset + size);
1321         }
1322 
1323         @SuppressWarnings("unchecked")
toArray(T[] a)1324         public <T> T[] toArray(T[] a) {
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             if (a.length < size)
1334                 return (T[]) Arrays.copyOfRange(
1335                         es, offset, offset + size, a.getClass());
1336             else {
1337                 System.arraycopy(es, offset, a, 0, size);
1338                 if (a.length > size)
1339                     a[size] = null;
1340                 return a;
1341             }
1342         }
1343 
indexOf(Object o)1344         public int indexOf(Object o) {
1345             final Object[] es;
1346             final int offset;
1347             final int size;
1348             synchronized (lock) {
1349                 es = getArrayChecked();
1350                 offset = this.offset;
1351                 size = this.size;
1352             }
1353             int i = indexOfRange(o, es, offset, offset + size);
1354             return (i == -1) ? -1 : i - offset;
1355         }
1356 
lastIndexOf(Object o)1357         public int lastIndexOf(Object o) {
1358             final Object[] es;
1359             final int offset;
1360             final int size;
1361             synchronized (lock) {
1362                 es = getArrayChecked();
1363                 offset = this.offset;
1364                 size = this.size;
1365             }
1366             int i = lastIndexOfRange(o, es, offset, offset + size);
1367             return (i == -1) ? -1 : i - offset;
1368         }
1369 
contains(Object o)1370         public boolean contains(Object o) {
1371             return indexOf(o) >= 0;
1372         }
1373 
containsAll(Collection<?> c)1374         public boolean containsAll(Collection<?> c) {
1375             final Object[] es;
1376             final int offset;
1377             final int size;
1378             synchronized (lock) {
1379                 es = getArrayChecked();
1380                 offset = this.offset;
1381                 size = this.size;
1382             }
1383             for (Object o : c)
1384                 if (indexOfRange(o, es, offset, offset + size) < 0)
1385                     return false;
1386             return true;
1387         }
1388 
isEmpty()1389         public boolean isEmpty() {
1390             return size() == 0;
1391         }
1392 
toString()1393         public String toString() {
1394             return Arrays.toString(toArray());
1395         }
1396 
hashCode()1397         public int hashCode() {
1398             final Object[] es;
1399             final int offset;
1400             final int size;
1401             synchronized (lock) {
1402                 es = getArrayChecked();
1403                 offset = this.offset;
1404                 size = this.size;
1405             }
1406             return hashCodeOfRange(es, offset, offset + size);
1407         }
1408 
equals(Object o)1409         public boolean equals(Object o) {
1410             if (o == this)
1411                 return true;
1412             if (!(o instanceof List))
1413                 return false;
1414             Iterator<?> it = ((List<?>)o).iterator();
1415 
1416             final Object[] es;
1417             final int offset;
1418             final int size;
1419             synchronized (lock) {
1420                 es = getArrayChecked();
1421                 offset = this.offset;
1422                 size = this.size;
1423             }
1424 
1425             for (int i = offset, end = offset + size; i < end; i++)
1426                 if (!it.hasNext() || !Objects.equals(es[i], it.next()))
1427                     return false;
1428             return !it.hasNext();
1429         }
1430 
set(int index, E element)1431         public E set(int index, E element) {
1432             synchronized (lock) {
1433                 rangeCheck(index);
1434                 checkForComodification();
1435                 E x = CopyOnWriteArrayList.this.set(offset + index, element);
1436                 expectedArray = getArray();
1437                 return x;
1438             }
1439         }
1440 
get(int index)1441         public E get(int index) {
1442             synchronized (lock) {
1443                 rangeCheck(index);
1444                 checkForComodification();
1445                 return CopyOnWriteArrayList.this.get(offset + index);
1446             }
1447         }
1448 
getFirst()1449         public E getFirst() {
1450             synchronized (lock) {
1451                 if (size == 0)
1452                     throw new NoSuchElementException();
1453                 else
1454                     return get(0);
1455             }
1456         }
1457 
getLast()1458         public E getLast() {
1459             synchronized (lock) {
1460                 if (size == 0)
1461                     throw new NoSuchElementException();
1462                 else
1463                     return get(size - 1);
1464             }
1465         }
1466 
size()1467         public int size() {
1468             synchronized (lock) {
1469                 checkForComodification();
1470                 return size;
1471             }
1472         }
1473 
add(E element)1474         public boolean add(E element) {
1475             synchronized (lock) {
1476                 checkForComodification();
1477                 CopyOnWriteArrayList.this.add(offset + size, element);
1478                 expectedArray = getArray();
1479                 size++;
1480             }
1481             return true;
1482         }
1483 
add(int index, E element)1484         public void add(int index, E element) {
1485             synchronized (lock) {
1486                 checkForComodification();
1487                 rangeCheckForAdd(index);
1488                 CopyOnWriteArrayList.this.add(offset + index, element);
1489                 expectedArray = getArray();
1490                 size++;
1491             }
1492         }
1493 
addFirst(E e)1494         public void addFirst(E e) {
1495             add(0, e);
1496         }
1497 
addLast(E e)1498         public void addLast(E e) {
1499             synchronized (lock) {
1500                 add(size, e);
1501             }
1502         }
1503 
addAll(Collection<? extends E> c)1504         public boolean addAll(Collection<? extends E> c) {
1505             synchronized (lock) {
1506                 final Object[] oldArray = getArrayChecked();
1507                 boolean modified =
1508                     CopyOnWriteArrayList.this.addAll(offset + size, c);
1509                 size += (expectedArray = getArray()).length - oldArray.length;
1510                 return modified;
1511             }
1512         }
1513 
addAll(int index, Collection<? extends E> c)1514         public boolean addAll(int index, Collection<? extends E> c) {
1515             synchronized (lock) {
1516                 rangeCheckForAdd(index);
1517                 final Object[] oldArray = getArrayChecked();
1518                 boolean modified =
1519                     CopyOnWriteArrayList.this.addAll(offset + index, c);
1520                 size += (expectedArray = getArray()).length - oldArray.length;
1521                 return modified;
1522             }
1523         }
1524 
clear()1525         public void clear() {
1526             synchronized (lock) {
1527                 checkForComodification();
1528                 removeRange(offset, offset + size);
1529                 expectedArray = getArray();
1530                 size = 0;
1531             }
1532         }
1533 
remove(int index)1534         public E remove(int index) {
1535             synchronized (lock) {
1536                 rangeCheck(index);
1537                 checkForComodification();
1538                 E result = CopyOnWriteArrayList.this.remove(offset + index);
1539                 expectedArray = getArray();
1540                 size--;
1541                 return result;
1542             }
1543         }
1544 
removeFirst()1545         public E removeFirst() {
1546             synchronized (lock) {
1547                 if (size == 0)
1548                     throw new NoSuchElementException();
1549                 else
1550                     return remove(0);
1551             }
1552         }
1553 
removeLast()1554         public E removeLast() {
1555             synchronized (lock) {
1556                 if (size == 0)
1557                     throw new NoSuchElementException();
1558                 else
1559                     return remove(size - 1);
1560             }
1561         }
1562 
remove(Object o)1563         public boolean remove(Object o) {
1564             synchronized (lock) {
1565                 checkForComodification();
1566                 int index = indexOf(o);
1567                 if (index == -1)
1568                     return false;
1569                 remove(index);
1570                 return true;
1571             }
1572         }
1573 
iterator()1574         public Iterator<E> iterator() {
1575             return listIterator(0);
1576         }
1577 
listIterator()1578         public ListIterator<E> listIterator() {
1579             return listIterator(0);
1580         }
1581 
listIterator(int index)1582         public ListIterator<E> listIterator(int index) {
1583             synchronized (lock) {
1584                 checkForComodification();
1585                 rangeCheckForAdd(index);
1586                 return new COWSubListIterator<E>(
1587                     CopyOnWriteArrayList.this, index, offset, size);
1588             }
1589         }
1590 
subList(int fromIndex, int toIndex)1591         public List<E> subList(int fromIndex, int toIndex) {
1592             synchronized (lock) {
1593                 checkForComodification();
1594                 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
1595                     throw new IndexOutOfBoundsException();
1596                 return new COWSubList(expectedArray, fromIndex + offset, toIndex - fromIndex);
1597             }
1598         }
1599 
forEach(Consumer<? super E> action)1600         public void forEach(Consumer<? super E> action) {
1601             Objects.requireNonNull(action);
1602             int i, end; final Object[] es;
1603             synchronized (lock) {
1604                 es = getArrayChecked();
1605                 i = offset;
1606                 end = i + size;
1607             }
1608             for (; i < end; i++)
1609                 action.accept(elementAt(es, i));
1610         }
1611 
replaceAll(UnaryOperator<E> operator)1612         public void replaceAll(UnaryOperator<E> operator) {
1613             synchronized (lock) {
1614                 checkForComodification();
1615                 replaceAllRange(operator, offset, offset + size);
1616                 expectedArray = getArray();
1617             }
1618         }
1619 
sort(Comparator<? super E> c)1620         public void sort(Comparator<? super E> c) {
1621             synchronized (lock) {
1622                 checkForComodification();
1623                 sortRange(c, offset, offset + size);
1624                 expectedArray = getArray();
1625             }
1626         }
1627 
removeAll(Collection<?> c)1628         public boolean removeAll(Collection<?> c) {
1629             Objects.requireNonNull(c);
1630             return bulkRemove(e -> c.contains(e));
1631         }
1632 
retainAll(Collection<?> c)1633         public boolean retainAll(Collection<?> c) {
1634             Objects.requireNonNull(c);
1635             return bulkRemove(e -> !c.contains(e));
1636         }
1637 
removeIf(Predicate<? super E> filter)1638         public boolean removeIf(Predicate<? super E> filter) {
1639             Objects.requireNonNull(filter);
1640             return bulkRemove(filter);
1641         }
1642 
bulkRemove(Predicate<? super E> filter)1643         private boolean bulkRemove(Predicate<? super E> filter) {
1644             synchronized (lock) {
1645                 final Object[] oldArray = getArrayChecked();
1646                 boolean modified = CopyOnWriteArrayList.this.bulkRemove(
1647                     filter, offset, offset + size);
1648                 size += (expectedArray = getArray()).length - oldArray.length;
1649                 return modified;
1650             }
1651         }
1652 
spliterator()1653         public Spliterator<E> spliterator() {
1654             synchronized (lock) {
1655                 return Spliterators.spliterator(
1656                         getArrayChecked(), offset, offset + size,
1657                         Spliterator.IMMUTABLE | Spliterator.ORDERED);
1658             }
1659         }
1660 
reversed()1661         public List<E> reversed() {
1662             return new Reversed<>(this, lock);
1663         }
1664     }
1665 
1666     private static class COWSubListIterator<E> implements ListIterator<E> {
1667         private final ListIterator<E> it;
1668         private final int offset;
1669         private final int size;
1670 
COWSubListIterator(List<E> l, int index, int offset, int size)1671         COWSubListIterator(List<E> l, int index, int offset, int size) {
1672             this.offset = offset;
1673             this.size = size;
1674             it = l.listIterator(index + offset);
1675         }
1676 
hasNext()1677         public boolean hasNext() {
1678             return nextIndex() < size;
1679         }
1680 
next()1681         public E next() {
1682             if (hasNext())
1683                 return it.next();
1684             else
1685                 throw new NoSuchElementException();
1686         }
1687 
hasPrevious()1688         public boolean hasPrevious() {
1689             return previousIndex() >= 0;
1690         }
1691 
previous()1692         public E previous() {
1693             if (hasPrevious())
1694                 return it.previous();
1695             else
1696                 throw new NoSuchElementException();
1697         }
1698 
nextIndex()1699         public int nextIndex() {
1700             return it.nextIndex() - offset;
1701         }
1702 
previousIndex()1703         public int previousIndex() {
1704             return it.previousIndex() - offset;
1705         }
1706 
remove()1707         public void remove() {
1708             throw new UnsupportedOperationException();
1709         }
1710 
set(E e)1711         public void set(E e) {
1712             throw new UnsupportedOperationException();
1713         }
1714 
add(E e)1715         public void add(E e) {
1716             throw new UnsupportedOperationException();
1717         }
1718 
1719         @Override
1720         @SuppressWarnings("unchecked")
forEachRemaining(Consumer<? super E> action)1721         public void forEachRemaining(Consumer<? super E> action) {
1722             Objects.requireNonNull(action);
1723             while (hasNext()) {
1724                 action.accept(it.next());
1725             }
1726         }
1727     }
1728 
1729     /**
1730      * {@inheritDoc}
1731      * <p>
1732      * Modifications to the reversed view are permitted and will be propagated
1733      * to this list. In addition, modifications to this list will be visible
1734      * in the reversed view. Sublists and iterators of the reversed view have
1735      * the same restrictions as those of this list.
1736      *
1737      * @since 21
1738      */
reversed()1739     public List<E> reversed() {
1740         return new Reversed<>(this, lock);
1741     }
1742 
1743     /**
1744      * Reversed view for CopyOnWriteArrayList and its sublists.
1745      */
1746     private static class Reversed<E> implements List<E>, RandomAccess {
1747         final List<E> base;
1748         final Object lock;
1749 
Reversed(List<E> base, Object lock)1750         Reversed(List<E> base, Object lock) {
1751             this.base = base;
1752             this.lock = lock;
1753         }
1754 
1755         class DescendingIterator implements Iterator<E> {
1756             final ListIterator<E> it;
DescendingIterator()1757             DescendingIterator() {
1758                 synchronized (lock) {
1759                     it = base.listIterator(base.size());
1760                 }
1761             }
hasNext()1762             public boolean hasNext() { return it.hasPrevious(); }
next()1763             public E next() { return it.previous(); }
remove()1764             public void remove() { it.remove(); }
1765         }
1766 
1767         class DescendingListIterator implements ListIterator<E> {
1768             final ListIterator<E> it;
1769             final int size; // iterator holds a snapshot of the array so this is constant
1770 
DescendingListIterator(int pos)1771             DescendingListIterator(int pos) {
1772                 synchronized (lock) {
1773                     size = base.size();
1774                     if (pos < 0 || pos > size)
1775                         throw new IndexOutOfBoundsException();
1776                     it = base.listIterator(size - pos);
1777                 }
1778             }
1779 
hasNext()1780             public boolean hasNext() {
1781                 return it.hasPrevious();
1782             }
1783 
next()1784             public E next() {
1785                 return it.previous();
1786             }
1787 
hasPrevious()1788             public boolean hasPrevious() {
1789                 return it.hasNext();
1790             }
1791 
previous()1792             public E previous() {
1793                 return it.next();
1794             }
1795 
nextIndex()1796             public int nextIndex() {
1797                 return size - it.nextIndex();
1798             }
1799 
previousIndex()1800             public int previousIndex() {
1801                 return nextIndex() - 1;
1802             }
1803 
remove()1804             public void remove() {
1805                 throw new UnsupportedOperationException();
1806             }
1807 
set(E e)1808             public void set(E e) {
1809                 throw new UnsupportedOperationException();
1810             }
1811 
add(E e)1812             public void add(E e) {
1813                 throw new UnsupportedOperationException();
1814             }
1815         }
1816 
1817         // ========== Iterable ==========
1818 
forEach(Consumer<? super E> action)1819         public void forEach(Consumer<? super E> action) {
1820             for (E e : this)
1821                 action.accept(e);
1822         }
1823 
iterator()1824         public Iterator<E> iterator() {
1825             return new DescendingIterator();
1826         }
1827 
spliterator()1828         public Spliterator<E> spliterator() {
1829             return Spliterators.spliterator(this, Spliterator.ORDERED);
1830         }
1831 
1832         // ========== Collection ==========
1833 
add(E e)1834         public boolean add(E e) {
1835             base.add(0, e);
1836             return true;
1837         }
1838 
addAll(Collection<? extends E> c)1839         public boolean addAll(Collection<? extends E> c) {
1840             @SuppressWarnings("unchecked")
1841             E[] es = (E[]) c.toArray();
1842             if (es.length > 0) {
1843                 ArraysSupport.reverse(es);
1844                 base.addAll(0, Arrays.asList(es));
1845                 return true;
1846             } else {
1847                 return false;
1848             }
1849         }
1850 
clear()1851         public void clear() {
1852             base.clear();
1853         }
1854 
contains(Object o)1855         public boolean contains(Object o) {
1856             return base.contains(o);
1857         }
1858 
containsAll(Collection<?> c)1859         public boolean containsAll(Collection<?> c) {
1860             return base.containsAll(c);
1861         }
1862 
1863         // copied from AbstractList
equals(Object o)1864         public boolean equals(Object o) {
1865             if (o == this)
1866                 return true;
1867             if (!(o instanceof List))
1868                 return false;
1869 
1870             ListIterator<E> e1 = listIterator();
1871             ListIterator<?> e2 = ((List<?>) o).listIterator();
1872             while (e1.hasNext() && e2.hasNext()) {
1873                 E o1 = e1.next();
1874                 Object o2 = e2.next();
1875                 if (!(o1==null ? o2==null : o1.equals(o2)))
1876                     return false;
1877             }
1878             return !(e1.hasNext() || e2.hasNext());
1879         }
1880 
1881         // copied from AbstractList
hashCode()1882         public int hashCode() {
1883             int hashCode = 1;
1884             for (E e : this)
1885                 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
1886             return hashCode;
1887         }
1888 
isEmpty()1889         public boolean isEmpty() {
1890             return base.isEmpty();
1891         }
1892 
parallelStream()1893         public Stream<E> parallelStream() {
1894             return StreamSupport.stream(spliterator(), true);
1895         }
1896 
remove(Object o)1897         public boolean remove(Object o) {
1898             synchronized (lock) {
1899                 int index = indexOf(o);
1900                 if (index == -1)
1901                     return false;
1902                 remove(index);
1903                 return true;
1904             }
1905         }
1906 
removeAll(Collection<?> c)1907         public boolean removeAll(Collection<?> c) {
1908             return base.removeAll(c);
1909         }
1910 
retainAll(Collection<?> c)1911         public boolean retainAll(Collection<?> c) {
1912             return base.retainAll(c);
1913         }
1914 
size()1915         public int size() {
1916             return base.size();
1917         }
1918 
stream()1919         public Stream<E> stream() {
1920             return StreamSupport.stream(spliterator(), false);
1921         }
1922 
toArray()1923         public Object[] toArray() {
1924             return ArraysSupport.reverse(base.toArray());
1925         }
1926 
1927         @SuppressWarnings("unchecked")
toArray(T[] a)1928         public <T> T[] toArray(T[] a) {
1929             // TODO optimize this
1930             return toArray(i -> (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), i));
1931         }
1932 
toArray(IntFunction<T[]> generator)1933         public <T> T[] toArray(IntFunction<T[]> generator) {
1934             return ArraysSupport.reverse(base.toArray(generator));
1935         }
1936 
1937         // copied from AbstractCollection
toString()1938         public String toString() {
1939             Iterator<E> it = iterator();
1940             if (! it.hasNext())
1941                 return "[]";
1942 
1943             StringBuilder sb = new StringBuilder();
1944             sb.append('[');
1945             for (;;) {
1946                 E e = it.next();
1947                 sb.append(e == this ? "(this Collection)" : e);
1948                 if (! it.hasNext())
1949                     return sb.append(']').toString();
1950                 sb.append(',').append(' ');
1951             }
1952         }
1953 
1954         // ========== List ==========
1955 
add(int index, E element)1956         public void add(int index, E element) {
1957             synchronized (lock) {
1958                 base.add(base.size() - index, element);
1959             }
1960         }
1961 
addFirst(E e)1962         public void addFirst(E e) {
1963             base.add(e);
1964         }
1965 
addLast(E e)1966         public void addLast(E e) {
1967             base.add(0, e);
1968         }
1969 
addAll(int index, Collection<? extends E> c)1970         public boolean addAll(int index, Collection<? extends E> c) {
1971             @SuppressWarnings("unchecked")
1972             E[] es = (E[]) c.toArray();
1973             if (es.length > 0) {
1974                 ArraysSupport.reverse(es);
1975                 synchronized (lock) {
1976                     base.addAll(base.size() - index, Arrays.asList(es));
1977                 }
1978                 return true;
1979             } else {
1980                 return false;
1981             }
1982         }
1983 
get(int i)1984         public E get(int i) {
1985             synchronized (lock) {
1986                 return base.get(base.size() - i - 1);
1987             }
1988         }
1989 
getFirst()1990         public E getFirst() {
1991             synchronized (lock) {
1992                 int size = base.size();
1993                 if (size == 0)
1994                     throw new NoSuchElementException();
1995                 else
1996                     return base.get(size - 1);
1997             }
1998         }
1999 
getLast()2000         public E getLast() {
2001             synchronized (lock) {
2002                 if (base.size() == 0)
2003                     throw new NoSuchElementException();
2004                 else
2005                     return base.get(0);
2006             }
2007         }
2008 
indexOf(Object o)2009         public int indexOf(Object o) {
2010             synchronized (lock) {
2011                 int i = base.lastIndexOf(o);
2012                 return i == -1 ? -1 : base.size() - i - 1;
2013             }
2014         }
2015 
lastIndexOf(Object o)2016         public int lastIndexOf(Object o) {
2017             synchronized (lock) {
2018                 int i = base.indexOf(o);
2019                 return i == -1 ? -1 : base.size() - i - 1;
2020             }
2021         }
2022 
listIterator()2023         public ListIterator<E> listIterator() {
2024             return new DescendingListIterator(0);
2025         }
2026 
listIterator(int index)2027         public ListIterator<E> listIterator(int index) {
2028             return new DescendingListIterator(index);
2029         }
2030 
remove(int index)2031         public E remove(int index) {
2032             synchronized (lock) {
2033                 return base.remove(base.size() - index - 1);
2034             }
2035         }
2036 
removeFirst()2037         public E removeFirst() {
2038             synchronized (lock) {
2039                 int size = base.size();
2040                 if (size == 0)
2041                     throw new NoSuchElementException();
2042                 else
2043                     return base.remove(size - 1);
2044             }
2045         }
2046 
removeLast()2047         public E removeLast() {
2048             synchronized (lock) {
2049                 if (base.size() == 0)
2050                     throw new NoSuchElementException();
2051                 else
2052                     return base.remove(0);
2053             }
2054         }
2055 
removeIf(Predicate<? super E> filter)2056         public boolean removeIf(Predicate<? super E> filter) {
2057             return base.removeIf(filter);
2058         }
2059 
replaceAll(UnaryOperator<E> operator)2060         public void replaceAll(UnaryOperator<E> operator) {
2061             base.replaceAll(operator);
2062         }
2063 
sort(Comparator<? super E> c)2064         public void sort(Comparator<? super E> c) {
2065             base.sort(Collections.reverseOrder(c));
2066         }
2067 
set(int index, E element)2068         public E set(int index, E element) {
2069             synchronized (lock) {
2070                 return base.set(base.size() - index - 1, element);
2071             }
2072         }
2073 
subList(int fromIndex, int toIndex)2074         public List<E> subList(int fromIndex, int toIndex) {
2075             synchronized (lock) {
2076                 int size = base.size();
2077                 var sub = base.subList(size - toIndex, size - fromIndex);
2078                 return new Reversed<>(sub, lock);
2079             }
2080         }
2081 
reversed()2082         public List<E> reversed() {
2083             return base;
2084         }
2085     }
2086 
2087     /** Initializes the lock; for use when deserializing or cloning. */
resetLock()2088     private void resetLock() {
2089         @SuppressWarnings("removal")
2090         Field lockField = java.security.AccessController.doPrivileged(
2091             (java.security.PrivilegedAction<Field>) () -> {
2092                 try {
2093                     Field f = CopyOnWriteArrayList.class
2094                         .getDeclaredField("lock");
2095                     f.setAccessible(true);
2096                     return f;
2097                 } catch (ReflectiveOperationException e) {
2098                     throw new Error(e);
2099                 }});
2100         try {
2101             lockField.set(this, new Object());
2102         } catch (IllegalAccessException e) {
2103             throw new Error(e);
2104         }
2105     }
2106 }
2107