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