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