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
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 * Tests 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> {@code String[] y = x.toArray(new String[0]);}</pre>
337 *
338 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
339 * <tt>toArray()</tt>.
340 *
341 * @param a the array into which the elements of the list are to
342 * be stored, if it is big enough; otherwise, a new array of the
343 * same runtime type is allocated for this purpose.
344 * @return an array containing all the elements in this list
345 * @throws ArrayStoreException if the runtime type of the specified array
346 * is not a supertype of the runtime type of every element in
347 * this list
348 * @throws NullPointerException if the specified array is null
349 */
350 @SuppressWarnings("unchecked")
351 public <T> T[] toArray(T a[]) {
352 Object[] elements = getArray();
353 int len = elements.length;
354 if (a.length < len)
355 return (T[]) Arrays.copyOf(elements, len, a.getClass());
356 else {
357 System.arraycopy(elements, 0, a, 0, len);
358 if (a.length > len)
359 a[len] = null;
360 return a;
361 }
362 }
363
364 // Positional Access Operations
365
366 @SuppressWarnings("unchecked")
367 private E get(Object[] a, int index) {
368 return (E) a[index];
369 }
370
371 /**
372 * {@inheritDoc}
373 *
374 * @throws IndexOutOfBoundsException {@inheritDoc}
375 */
376 public E get(int index) {
377 return get(getArray(), index);
378 }
379
380 /**
381 * Replaces the element at the specified position in this list with the
382 * specified element.
383 *
384 * @throws IndexOutOfBoundsException {@inheritDoc}
385 */
386 public E set(int index, E element) {
387 final ReentrantLock lock = this.lock;
388 lock.lock();
389 try {
390 Object[] elements = getArray();
391 E oldValue = get(elements, index);
392
393 if (oldValue != element) {
394 int len = elements.length;
395 Object[] newElements = Arrays.copyOf(elements, len);
396 newElements[index] = element;
397 setArray(newElements);
398 } else {
399 // Not quite a no-op; ensures volatile write semantics
400 setArray(elements);
401 }
402 return oldValue;
403 } finally {
404 lock.unlock();
405 }
406 }
407
408 /**
409 * Appends the specified element to the end of this list.
410 *
411 * @param e element to be appended to this list
412 * @return <tt>true</tt> (as specified by {@link Collection#add})
413 */
414 public boolean add(E e) {
415 final ReentrantLock lock = this.lock;
416 lock.lock();
417 try {
418 Object[] elements = getArray();
419 int len = elements.length;
420 Object[] newElements = Arrays.copyOf(elements, len + 1);
421 newElements[len] = e;
422 setArray(newElements);
423 return true;
424 } finally {
425 lock.unlock();
426 }
427 }
428
429 /**
430 * Inserts the specified element at the specified position in this
431 * list. Shifts the element currently at that position (if any) and
432 * any subsequent elements to the right (adds one to their indices).
433 *
434 * @throws IndexOutOfBoundsException {@inheritDoc}
435 */
436 public void add(int index, E element) {
437 final ReentrantLock lock = this.lock;
438 lock.lock();
439 try {
440 Object[] elements = getArray();
441 int len = elements.length;
442 if (index > len || index < 0)
443 throw new IndexOutOfBoundsException("Index: "+index+
444 ", Size: "+len);
445 Object[] newElements;
446 int numMoved = len - index;
447 if (numMoved == 0)
448 newElements = Arrays.copyOf(elements, len + 1);
449 else {
450 newElements = new Object[len + 1];
451 System.arraycopy(elements, 0, newElements, 0, index);
452 System.arraycopy(elements, index, newElements, index + 1,
453 numMoved);
454 }
455 newElements[index] = element;
456 setArray(newElements);
457 } finally {
458 lock.unlock();
459 }
460 }
461
462 /**
463 * Removes the element at the specified position in this list.
464 * Shifts any subsequent elements to the left (subtracts one from their
465 * indices). Returns the element that was removed from the list.
466 *
467 * @throws IndexOutOfBoundsException {@inheritDoc}
468 */
469 public E remove(int index) {
470 final ReentrantLock lock = this.lock;
471 lock.lock();
472 try {
473 Object[] elements = getArray();
474 int len = elements.length;
475 E oldValue = get(elements, index);
476 int numMoved = len - index - 1;
477 if (numMoved == 0)
478 setArray(Arrays.copyOf(elements, len - 1));
479 else {
480 Object[] newElements = new Object[len - 1];
481 System.arraycopy(elements, 0, newElements, 0, index);
482 System.arraycopy(elements, index + 1, newElements, index,
483 numMoved);
484 setArray(newElements);
485 }
486 return oldValue;
487 } finally {
488 lock.unlock();
489 }
490 }
491
492 /**
493 * Removes the first occurrence of the specified element from this list,
494 * if it is present. If this list does not contain the element, it is
495 * unchanged. More formally, removes the element with the lowest index
496 * <tt>i</tt> such that
497 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
498 * (if such an element exists). Returns <tt>true</tt> if this list
499 * contained the specified element (or equivalently, if this list
500 * changed as a result of the call).
501 *
502 * @param o element to be removed from this list, if present
503 * @return <tt>true</tt> if this list contained the specified element
504 */
505 public boolean remove(Object o) {
506 final ReentrantLock lock = this.lock;
507 lock.lock();
508 try {
509 Object[] elements = getArray();
510 int len = elements.length;
511 if (len != 0) {
512 // Copy while searching for element to remove
513 // This wins in the normal case of element being present
514 int newlen = len - 1;
515 Object[] newElements = new Object[newlen];
516
517 for (int i = 0; i < newlen; ++i) {
518 if (eq(o, elements[i])) {
519 // found one; copy remaining and exit
520 for (int k = i + 1; k < len; ++k)
521 newElements[k-1] = elements[k];
522 setArray(newElements);
523 return true;
524 } else
525 newElements[i] = elements[i];
526 }
527
528 // special handling for last cell
529 if (eq(o, elements[newlen])) {
530 setArray(newElements);
531 return true;
532 }
533 }
534 return false;
535 } finally {
536 lock.unlock();
537 }
538 }
539
540 /**
541 * Removes from this list all of the elements whose index is between
542 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
543 * Shifts any succeeding elements to the left (reduces their index).
544 * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
545 * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
546 *
547 * @param fromIndex index of first element to be removed
548 * @param toIndex index after last element to be removed
549 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
550 * ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
551 */
552 void removeRange(int fromIndex, int toIndex) {
553 final ReentrantLock lock = this.lock;
554 lock.lock();
555 try {
556 Object[] elements = getArray();
557 int len = elements.length;
558
559 if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
560 throw new IndexOutOfBoundsException();
561 int newlen = len - (toIndex - fromIndex);
562 int numMoved = len - toIndex;
563 if (numMoved == 0)
564 setArray(Arrays.copyOf(elements, newlen));
565 else {
566 Object[] newElements = new Object[newlen];
567 System.arraycopy(elements, 0, newElements, 0, fromIndex);
568 System.arraycopy(elements, toIndex, newElements,
569 fromIndex, numMoved);
570 setArray(newElements);
571 }
572 } finally {
573 lock.unlock();
574 }
575 }
576
577 /**
578 * Appends the element, if not present.
579 *
580 * @param e element to be added to this list, if absent
581 * @return <tt>true</tt> if the element was added
582 */
583 public boolean addIfAbsent(E e) {
584 final ReentrantLock lock = this.lock;
585 lock.lock();
586 try {
587 // Copy while checking if already present.
588 // This wins in the most common case where it is not present
589 Object[] elements = getArray();
590 int len = elements.length;
591 Object[] newElements = new Object[len + 1];
592 for (int i = 0; i < len; ++i) {
593 if (eq(e, elements[i]))
594 return false; // exit, throwing away copy
595 else
596 newElements[i] = elements[i];
597 }
598 newElements[len] = e;
599 setArray(newElements);
600 return true;
601 } finally {
602 lock.unlock();
603 }
604 }
605
606 /**
607 * Returns <tt>true</tt> if this list contains all of the elements of the
608 * specified collection.
609 *
610 * @param c collection to be checked for containment in this list
611 * @return <tt>true</tt> if this list contains all of the elements of the
612 * specified collection
613 * @throws NullPointerException if the specified collection is null
614 * @see #contains(Object)
615 */
616 public boolean containsAll(Collection<?> c) {
617 Object[] elements = getArray();
618 int len = elements.length;
619 for (Object e : c) {
620 if (indexOf(e, elements, 0, len) < 0)
621 return false;
622 }
623 return true;
624 }
625
626 /**
627 * Removes from this list all of its elements that are contained in
628 * the specified collection. This is a particularly expensive operation
629 * in this class because of the need for an internal temporary array.
630 *
631 * @param c collection containing elements to be removed from this list
632 * @return <tt>true</tt> if this list changed as a result of the call
633 * @throws ClassCastException if the class of an element of this list
634 * is incompatible with the specified collection
635 * (<a href="../Collection.html#optional-restrictions">optional</a>)
636 * @throws NullPointerException if this list contains a null element and the
637 * specified collection does not permit null elements
638 * (<a href="../Collection.html#optional-restrictions">optional</a>),
639 * or if the specified collection is null
640 * @see #remove(Object)
641 */
642 public boolean removeAll(Collection<?> c) {
643 if (c == null) throw new NullPointerException();
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 if (c == null) throw new NullPointerException();
687 final ReentrantLock lock = this.lock;
688 lock.lock();
689 try {
690 Object[] elements = getArray();
691 int len = elements.length;
692 if (len != 0) {
693 // temp array holds those elements we know we want to keep
694 int newlen = 0;
695 Object[] temp = new Object[len];
696 for (int i = 0; i < len; ++i) {
697 Object element = elements[i];
698 if (c.contains(element))
699 temp[newlen++] = element;
700 }
701 if (newlen != len) {
702 setArray(Arrays.copyOf(temp, newlen));
703 return true;
704 }
705 }
706 return false;
707 } finally {
708 lock.unlock();
709 }
710 }
711
712 /**
713 * Appends all of the elements in the specified collection that
714 * are not already contained in this list, to the end of
715 * this list, in the order that they are returned by the
716 * specified collection's iterator.
717 *
718 * @param c collection containing elements to be added to this list
719 * @return the number of elements added
720 * @throws NullPointerException if the specified collection is null
721 * @see #addIfAbsent(Object)
722 */
723 public int addAllAbsent(Collection<? extends E> c) {
724 Object[] cs = c.toArray();
725 if (cs.length == 0)
726 return 0;
727 Object[] uniq = new Object[cs.length];
728 final ReentrantLock lock = this.lock;
729 lock.lock();
730 try {
731 Object[] elements = getArray();
732 int len = elements.length;
733 int added = 0;
734 for (int i = 0; i < cs.length; ++i) { // scan for duplicates
735 Object e = cs[i];
736 if (indexOf(e, elements, 0, len) < 0 &&
737 indexOf(e, uniq, 0, added) < 0)
738 uniq[added++] = e;
739 }
740 if (added > 0) {
741 Object[] newElements = Arrays.copyOf(elements, len + added);
742 System.arraycopy(uniq, 0, newElements, len, added);
743 setArray(newElements);
744 }
745 return added;
746 } finally {
747 lock.unlock();
748 }
749 }
750
751 /**
752 * Removes all of the elements from this list.
753 * The list will be empty after this call returns.
754 */
755 public void clear() {
756 final ReentrantLock lock = this.lock;
757 lock.lock();
758 try {
759 setArray(new Object[0]);
760 } finally {
761 lock.unlock();
762 }
763 }
764
765 /**
766 * Appends all of the elements in the specified collection to the end
767 * of this list, in the order that they are returned by the specified
768 * collection's iterator.
769 *
770 * @param c collection containing elements to be added to this list
771 * @return <tt>true</tt> if this list changed as a result of the call
772 * @throws NullPointerException if the specified collection is null
773 * @see #add(Object)
774 */
775 public boolean addAll(Collection<? extends E> c) {
776 Object[] cs = c.toArray();
777 if (cs.length == 0)
778 return false;
779 final ReentrantLock lock = this.lock;
780 lock.lock();
781 try {
782 Object[] elements = getArray();
783 int len = elements.length;
784 Object[] newElements = Arrays.copyOf(elements, len + cs.length);
785 System.arraycopy(cs, 0, newElements, len, cs.length);
786 setArray(newElements);
787 return true;
788 } finally {
789 lock.unlock();
790 }
791 }
792
793 /**
794 * Inserts all of the elements in the specified collection into this
795 * list, starting at the specified position. Shifts the element
796 * currently at that position (if any) and any subsequent elements to
797 * the right (increases their indices). The new elements will appear
798 * in this list in the order that they are returned by the
799 * specified collection's iterator.
800 *
801 * @param index index at which to insert the first element
802 * from the specified collection
803 * @param c collection containing elements to be added to this list
804 * @return <tt>true</tt> if this list changed as a result of the call
805 * @throws IndexOutOfBoundsException {@inheritDoc}
806 * @throws NullPointerException if the specified collection is null
807 * @see #add(int,Object)
808 */
809 public boolean addAll(int index, Collection<? extends E> c) {
810 Object[] cs = c.toArray();
811 final ReentrantLock lock = this.lock;
812 lock.lock();
813 try {
814 Object[] elements = getArray();
815 int len = elements.length;
816 if (index > len || index < 0)
817 throw new IndexOutOfBoundsException("Index: "+index+
818 ", Size: "+len);
819 if (cs.length == 0)
820 return false;
821 int numMoved = len - index;
822 Object[] newElements;
823 if (numMoved == 0)
824 newElements = Arrays.copyOf(elements, len + cs.length);
825 else {
826 newElements = new Object[len + cs.length];
827 System.arraycopy(elements, 0, newElements, 0, index);
828 System.arraycopy(elements, index,
829 newElements, index + cs.length,
830 numMoved);
831 }
832 System.arraycopy(cs, 0, newElements, index, cs.length);
833 setArray(newElements);
834 return true;
835 } finally {
836 lock.unlock();
837 }
838 }
839
840 /**
841 * Saves this list to a stream (that is, serializes it).
842 *
843 * @serialData The length of the array backing the list is emitted
844 * (int), followed by all of its elements (each an Object)
845 * in the proper order.
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 this list from a stream (that is, deserializes it).
863 */
864 private void readObject(java.io.ObjectInputStream s)
865 throws java.io.IOException, ClassNotFoundException {
866
867 s.defaultReadObject();
868
869 // bind to new lock
870 resetLock();
871
872 // Read in array length and allocate array
873 int len = s.readInt();
874 Object[] elements = new Object[len];
875
876 // Read in all elements in the proper order.
877 for (int i = 0; i < len; i++)
878 elements[i] = s.readObject();
879 setArray(elements);
880 }
881
882 /**
883 * Returns a string representation of this list. The string
884 * representation consists of the string representations of the list's
885 * elements in the order they are returned by its iterator, enclosed in
886 * square brackets (<tt>"[]"</tt>). Adjacent elements are separated by
887 * the characters <tt>", "</tt> (comma and space). Elements are
888 * converted to strings as by {@link String#valueOf(Object)}.
889 *
890 * @return a string representation of this list
891 */
892 public String toString() {
893 return Arrays.toString(getArray());
894 }
895
896 /**
897 * Compares the specified object with this list for equality.
898 * Returns {@code true} if the specified object is the same object
899 * as this object, or if it is also a {@link List} and the sequence
900 * of elements returned by an {@linkplain List#iterator() iterator}
901 * over the specified list is the same as the sequence returned by
902 * an iterator over this list. The two sequences are considered to
903 * be the same if they have the same length and corresponding
904 * elements at the same position in the sequence are <em>equal</em>.
905 * Two elements {@code e1} and {@code e2} are considered
906 * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
907 *
908 * @param o the object to be compared for equality with this list
909 * @return {@code true} if the specified object is equal to this list
910 */
911 public boolean equals(Object o) {
912 if (o == this)
913 return true;
914 if (!(o instanceof List))
915 return false;
916
917 List<?> list = (List<?>)(o);
918 Iterator<?> it = list.iterator();
919 Object[] elements = getArray();
920 int len = elements.length;
921 for (int i = 0; i < len; ++i)
922 if (!it.hasNext() || !eq(elements[i], it.next()))
923 return false;
924 if (it.hasNext())
925 return false;
926 return true;
927 }
928
929 /**
930 * Returns the hash code value for this list.
931 *
932 * <p>This implementation uses the definition in {@link List#hashCode}.
933 *
934 * @return the hash code value for this list
935 */
936 public int hashCode() {
937 int hashCode = 1;
938 Object[] elements = getArray();
939 int len = elements.length;
940 for (int i = 0; i < len; ++i) {
941 Object obj = elements[i];
942 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
943 }
944 return hashCode;
945 }
946
947 /**
948 * Returns an iterator over the elements in this list in proper sequence.
949 *
950 * <p>The returned iterator provides a snapshot of the state of the list
951 * when the iterator was constructed. No synchronization is needed while
952 * traversing the iterator. The iterator does <em>NOT</em> support the
953 * <tt>remove</tt> method.
954 *
955 * @return an iterator over the elements in this list in proper sequence
956 */
957 public Iterator<E> iterator() {
958 return new COWIterator<E>(getArray(), 0);
959 }
960
961 /**
962 * {@inheritDoc}
963 *
964 * <p>The returned iterator provides a snapshot of the state of the list
965 * when the iterator was constructed. No synchronization is needed while
966 * traversing the iterator. The iterator does <em>NOT</em> support the
967 * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
968 */
969 public ListIterator<E> listIterator() {
970 return new COWIterator<E>(getArray(), 0);
971 }
972
973 /**
974 * {@inheritDoc}
975 *
976 * <p>The returned iterator provides a snapshot of the state of the list
977 * when the iterator was constructed. No synchronization is needed while
978 * traversing the iterator. The iterator does <em>NOT</em> support the
979 * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
980 *
981 * @throws IndexOutOfBoundsException {@inheritDoc}
982 */
983 public ListIterator<E> listIterator(final int index) {
984 Object[] elements = getArray();
985 int len = elements.length;
986 if (index<0 || index>len)
987 throw new IndexOutOfBoundsException("Index: "+index);
988
989 return new COWIterator<E>(elements, index);
990 }
991
992 private static class COWIterator<E> implements ListIterator<E> {
993 /** Snapshot of the array */
994 private final Object[] snapshot;
995 /** Index of element to be returned by subsequent call to next. */
996 private int cursor;
997
998 private COWIterator(Object[] elements, int initialCursor) {
999 cursor = initialCursor;
1000 snapshot = elements;
1001 }
1002
1003 public boolean hasNext() {
1004 return cursor < snapshot.length;
1005 }
1006
1007 public boolean hasPrevious() {
1008 return cursor > 0;
1009 }
1010
1011 @SuppressWarnings("unchecked")
1012 public E next() {
1013 if (! hasNext())
1014 throw new NoSuchElementException();
1015 return (E) snapshot[cursor++];
1016 }
1017
1018 @SuppressWarnings("unchecked")
1019 public E previous() {
1020 if (! hasPrevious())
1021 throw new NoSuchElementException();
1022 return (E) snapshot[--cursor];
1023 }
1024
1025 public int nextIndex() {
1026 return cursor;
1027 }
1028
1029 public int previousIndex() {
1030 return cursor-1;
1031 }
1032
1033 /**
1034 * Not supported. Always throws UnsupportedOperationException.
1035 * @throws UnsupportedOperationException always; <tt>remove</tt>
1036 * is not supported by this iterator.
1037 */
1038 public void remove() {
1039 throw new UnsupportedOperationException();
1040 }
1041
1042 /**
1043 * Not supported. Always throws UnsupportedOperationException.
1044 * @throws UnsupportedOperationException always; <tt>set</tt>
1045 * is not supported by this iterator.
1046 */
1047 public void set(E e) {
1048 throw new UnsupportedOperationException();
1049 }
1050
1051 /**
1052 * Not supported. Always throws UnsupportedOperationException.
1053 * @throws UnsupportedOperationException always; <tt>add</tt>
1054 * is not supported by this iterator.
1055 */
1056 public void add(E e) {
1057 throw new UnsupportedOperationException();
1058 }
1059 }
1060
1061 /**
1062 * Returns a view of the portion of this list between
1063 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1064 * The returned list is backed by this list, so changes in the
1065 * returned list are reflected in this list.
1066 *
1067 * <p>The semantics of the list returned by this method become
1068 * undefined if the backing list (i.e., this list) is modified in
1069 * any way other than via the returned list.
1070 *
1071 * @param fromIndex low endpoint (inclusive) of the subList
1072 * @param toIndex high endpoint (exclusive) of the subList
1073 * @return a view of the specified range within this list
1074 * @throws IndexOutOfBoundsException {@inheritDoc}
1075 */
1076 public List<E> subList(int fromIndex, int toIndex) {
1077 final ReentrantLock lock = this.lock;
1078 lock.lock();
1079 try {
1080 Object[] elements = getArray();
1081 int len = elements.length;
1082 if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1083 throw new IndexOutOfBoundsException();
1084 return new COWSubList<E>(this, fromIndex, toIndex);
1085 } finally {
1086 lock.unlock();
1087 }
1088 }
1089
1090 /**
1091 * Sublist for CopyOnWriteArrayList.
1092 * This class extends AbstractList merely for convenience, to
1093 * avoid having to define addAll, etc. This doesn't hurt, but
1094 * is wasteful. This class does not need or use modCount
1095 * mechanics in AbstractList, but does need to check for
1096 * concurrent modification using similar mechanics. On each
1097 * operation, the array that we expect the backing list to use
1098 * is checked and updated. Since we do this for all of the
1099 * base operations invoked by those defined in AbstractList,
1100 * all is well. While inefficient, this is not worth
1101 * improving. The kinds of list operations inherited from
1102 * AbstractList are already so slow on COW sublists that
1103 * adding a bit more space/time doesn't seem even noticeable.
1104 */
1105 private static class COWSubList<E>
1106 extends AbstractList<E>
1107 implements RandomAccess
1108 {
1109 private final CopyOnWriteArrayList<E> l;
1110 private final int offset;
1111 private int size;
1112 private Object[] expectedArray;
1113
1114 // only call this holding l's lock
1115 COWSubList(CopyOnWriteArrayList<E> list,
1116 int fromIndex, int toIndex) {
1117 l = list;
1118 expectedArray = l.getArray();
1119 offset = fromIndex;
1120 size = toIndex - fromIndex;
1121 }
1122
1123 // only call this holding l's lock
1124 private void checkForComodification() {
1125 if (l.getArray() != expectedArray)
1126 throw new ConcurrentModificationException();
1127 }
1128
1129 // only call this holding l's lock
1130 private void rangeCheck(int index) {
1131 if (index<0 || index>=size)
1132 throw new IndexOutOfBoundsException("Index: "+index+
1133 ",Size: "+size);
1134 }
1135
1136 public E set(int index, E element) {
1137 final ReentrantLock lock = l.lock;
1138 lock.lock();
1139 try {
1140 rangeCheck(index);
1141 checkForComodification();
1142 E x = l.set(index+offset, element);
1143 expectedArray = l.getArray();
1144 return x;
1145 } finally {
1146 lock.unlock();
1147 }
1148 }
1149
1150 public E get(int index) {
1151 final ReentrantLock lock = l.lock;
1152 lock.lock();
1153 try {
1154 rangeCheck(index);
1155 checkForComodification();
1156 return l.get(index+offset);
1157 } finally {
1158 lock.unlock();
1159 }
1160 }
1161
1162 public int size() {
1163 final ReentrantLock lock = l.lock;
1164 lock.lock();
1165 try {
1166 checkForComodification();
1167 return size;
1168 } finally {
1169 lock.unlock();
1170 }
1171 }
1172
1173 public void add(int index, E element) {
1174 final ReentrantLock lock = l.lock;
1175 lock.lock();
1176 try {
1177 checkForComodification();
1178 if (index<0 || index>size)
1179 throw new IndexOutOfBoundsException();
1180 l.add(index+offset, element);
1181 expectedArray = l.getArray();
1182 size++;
1183 } finally {
1184 lock.unlock();
1185 }
1186 }
1187
1188 public void clear() {
1189 final ReentrantLock lock = l.lock;
1190 lock.lock();
1191 try {
1192 checkForComodification();
1193 l.removeRange(offset, offset+size);
1194 expectedArray = l.getArray();
1195 size = 0;
1196 } finally {
1197 lock.unlock();
1198 }
1199 }
1200
1201 public E remove(int index) {
1202 final ReentrantLock lock = l.lock;
1203 lock.lock();
1204 try {
1205 rangeCheck(index);
1206 checkForComodification();
1207 E result = l.remove(index+offset);
1208 expectedArray = l.getArray();
1209 size--;
1210 return result;
1211 } finally {
1212 lock.unlock();
1213 }
1214 }
1215
1216 public boolean remove(Object o) {
1217 int index = indexOf(o);
1218 if (index == -1)
1219 return false;
1220 remove(index);
1221 return true;
1222 }
1223
1224 public Iterator<E> iterator() {
1225 final ReentrantLock lock = l.lock;
1226 lock.lock();
1227 try {
1228 checkForComodification();
1229 return new COWSubListIterator<E>(l, 0, offset, size);
1230 } finally {
1231 lock.unlock();
1232 }
1233 }
1234
1235 public ListIterator<E> listIterator(final int index) {
1236 final ReentrantLock lock = l.lock;
1237 lock.lock();
1238 try {
1239 checkForComodification();
1240 if (index<0 || index>size)
1241 throw new IndexOutOfBoundsException("Index: "+index+
1242 ", Size: "+size);
1243 return new COWSubListIterator<E>(l, index, offset, size);
1244 } finally {
1245 lock.unlock();
1246 }
1247 }
1248
1249 public List<E> subList(int fromIndex, int toIndex) {
1250 final ReentrantLock lock = l.lock;
1251 lock.lock();
1252 try {
1253 checkForComodification();
1254 if (fromIndex<0 || toIndex>size)
1255 throw new IndexOutOfBoundsException();
1256 return new COWSubList<E>(l, fromIndex + offset,
1257 toIndex + offset);
1258 } finally {
1259 lock.unlock();
1260 }
1261 }
1262
1263 }
1264
1265
1266 private static class COWSubListIterator<E> implements ListIterator<E> {
1267 private final ListIterator<E> it;
1268 private final int offset;
1269 private final int size;
1270
1271 COWSubListIterator(List<E> l, int index, int offset, int size) {
1272 this.offset = offset;
1273 this.size = size;
1274 it = l.listIterator(index+offset);
1275 }
1276
1277 public boolean hasNext() {
1278 return nextIndex() < size;
1279 }
1280
1281 public E next() {
1282 if (hasNext())
1283 return it.next();
1284 else
1285 throw new NoSuchElementException();
1286 }
1287
1288 public boolean hasPrevious() {
1289 return previousIndex() >= 0;
1290 }
1291
1292 public E previous() {
1293 if (hasPrevious())
1294 return it.previous();
1295 else
1296 throw new NoSuchElementException();
1297 }
1298
1299 public int nextIndex() {
1300 return it.nextIndex() - offset;
1301 }
1302
1303 public int previousIndex() {
1304 return it.previousIndex() - offset;
1305 }
1306
1307 public void remove() {
1308 throw new UnsupportedOperationException();
1309 }
1310
1311 public void set(E e) {
1312 throw new UnsupportedOperationException();
1313 }
1314
1315 public void add(E e) {
1316 throw new UnsupportedOperationException();
1317 }
1318 }
1319
1320 // Support for resetting lock while deserializing
1321 private void resetLock() {
1322 UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
1323 }
1324 private static final sun.misc.Unsafe UNSAFE;
1325 private static final long lockOffset;
1326 static {
1327 try {
1328 UNSAFE = sun.misc.Unsafe.getUnsafe();
1329 Class<?> k = CopyOnWriteArrayList.class;
1330 lockOffset = UNSAFE.objectFieldOffset
1331 (k.getDeclaredField("lock"));
1332 } catch (Exception e) {
1333 throw new Error(e);
1334 }
1335 }
1336 }