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