1 /*
2 * Copyright 2003-2007 Sun Microsystems, Inc. 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. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any 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 import sun.misc.Unsafe;
40
41 /**
42 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
43 * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
44 * making a fresh copy of the underlying array.
45 *
46 * <p> This is ordinarily too costly, but may be <em>more</em> efficient
47 * than alternatives when traversal operations vastly outnumber
48 * mutations, and is useful when you cannot or don't want to
49 * synchronize traversals, yet need to preclude interference among
50 * concurrent threads. The "snapshot" style iterator method uses a
51 * reference to the state of the array at the point that the iterator
52 * was created. This array never changes during the lifetime of the
53 * iterator, so interference is impossible and the iterator is
54 * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
55 * The iterator will not reflect additions, removals, or changes to
56 * the list since the iterator was created. Element-changing
57 * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
58 * <tt>add</tt>) are not supported. These methods throw
59 * <tt>UnsupportedOperationException</tt>.
60 *
61 * <p>All elements are permitted, including <tt>null</tt>.
62 *
63 * <p>Memory consistency effects: As with other concurrent
64 * collections, actions in a thread prior to placing an object into a
65 * {@code CopyOnWriteArrayList}
66 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
67 * actions subsequent to the access or removal of that element from
68 * the {@code CopyOnWriteArrayList} in another thread.
69 *
70 * <p>This class is a member of the
71 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
72 * Java Collections Framework</a>.
73 *
74 * @since 1.5
75 * @author Doug Lea
76 * @param <E> the type of elements held in this collection
77 */
78 public class CopyOnWriteArrayList<E>
79 implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
80 private static final long serialVersionUID = 8673264195747942595L;
81
82 /** The lock protecting all mutators */
83 transient final ReentrantLock lock = new ReentrantLock();
84
85 /** The array, accessed only via getArray/setArray. */
86 private volatile transient Object[] array;
87
88 /**
89 * Gets the array. Non-private so as to also be accessible
90 * from CopyOnWriteArraySet class.
91 */
92 final Object[] getArray() {
93 return array;
94 }
95
96 /**
97 * Sets the array.
98 */
99 final void setArray(Object[] a) {
100 array = a;
101 }
102
103 /**
104 * Creates an empty list.
105 */
106 public CopyOnWriteArrayList() {
107 setArray(new Object[0]);
108 }
109
110 /**
111 * Creates a list containing the elements of the specified
112 * collection, in the order they are returned by the collection's
113 * iterator.
114 *
115 * @param c the collection of initially held elements
116 * @throws NullPointerException if the specified collection is null
117 */
118 public CopyOnWriteArrayList(Collection<? extends E> c) {
119 Object[] elements = c.toArray();
120 // c.toArray might (incorrectly) not return Object[] (see 6260652)
121 if (elements.getClass() != Object[].class)
122 elements = Arrays.copyOf(elements, elements.length, Object[].class);
123 setArray(elements);
124 }
125
126 /**
127 * Creates a list holding a copy of the given array.
128 *
129 * @param toCopyIn the array (a copy of this array is used as the
130 * internal array)
131 * @throws NullPointerException if the specified array is null
132 */
133 public CopyOnWriteArrayList(E[] toCopyIn) {
134 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
135 }
136
137 /**
138 * Returns the number of elements in this list.
139 *
140 * @return the number of elements in this list
141 */
142 public int size() {
143 return getArray().length;
144 }
145
146 /**
147 * Returns <tt>true</tt> if this list contains no elements.
148 *
149 * @return <tt>true</tt> if this list contains no elements
150 */
151 public boolean isEmpty() {
152 return size() == 0;
153 }
154
155 /**
156 * Test for equality, coping with nulls.
157 */
158 private static boolean eq(Object o1, Object o2) {
159 return (o1 == null ? o2 == null : o1.equals(o2));
160 }
161
162 /**
163 * static version of indexOf, to allow repeated calls without
164 * needing to re-acquire array each time.
165 * @param o element to search for
166 * @param elements the array
167 * @param index first index to search
168 * @param fence one past last index to search
169 * @return index of element, or -1 if absent
170 */
171 private static int indexOf(Object o, Object[] elements,
172 int index, int fence) {
173 if (o == null) {
174 for (int i = index; i < fence; i++)
175 if (elements[i] == null)
176 return i;
177 } else {
178 for (int i = index; i < fence; i++)
179 if (o.equals(elements[i]))
180 return i;
181 }
182 return -1;
183 }
184
185 /**
186 * static version of lastIndexOf.
187 * @param o element to search for
188 * @param elements the array
189 * @param index first index to search
190 * @return index of element, or -1 if absent
191 */
192 private static int lastIndexOf(Object o, Object[] elements, int index) {
193 if (o == null) {
194 for (int i = index; i >= 0; i--)
195 if (elements[i] == null)
196 return i;
197 } else {
198 for (int i = index; i >= 0; i--)
199 if (o.equals(elements[i]))
200 return i;
201 }
202 return -1;
203 }
204
205 /**
206 * Returns <tt>true</tt> if this list contains the specified element.
207 * More formally, returns <tt>true</tt> if and only if this list contains
208 * at least one element <tt>e</tt> such that
209 * <tt>(o==null ? e==null : o.equals(e))</tt>.
210 *
211 * @param o element whose presence in this list is to be tested
212 * @return <tt>true</tt> if this list contains the specified element
213 */
214 public boolean contains(Object o) {
215 Object[] elements = getArray();
216 return indexOf(o, elements, 0, elements.length) >= 0;
217 }
218
219 /**
220 * {@inheritDoc}
221 */
222 public int indexOf(Object o) {
223 Object[] elements = getArray();
224 return indexOf(o, elements, 0, elements.length);
225 }
226
227 /**
228 * Returns the index of the first occurrence of the specified element in
229 * this list, searching forwards from <tt>index</tt>, or returns -1 if
230 * the element is not found.
231 * More formally, returns the lowest index <tt>i</tt> such that
232 * <tt>(i >= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
233 * or -1 if there is no such index.
234 *
235 * @param e element to search for
236 * @param index index to start searching from
237 * @return the index of the first occurrence of the element in
238 * this list at position <tt>index</tt> or later in the list;
239 * <tt>-1</tt> if the element is not found.
240 * @throws IndexOutOfBoundsException if the specified index is negative
241 */
242 public int indexOf(E e, int index) {
243 Object[] elements = getArray();
244 return indexOf(e, elements, index, elements.length);
245 }
246
247 /**
248 * {@inheritDoc}
249 */
250 public int lastIndexOf(Object o) {
251 Object[] elements = getArray();
252 return lastIndexOf(o, elements, elements.length - 1);
253 }
254
255 /**
256 * Returns the index of the last occurrence of the specified element in
257 * this list, searching backwards from <tt>index</tt>, or returns -1 if
258 * the element is not found.
259 * More formally, returns the highest index <tt>i</tt> such that
260 * <tt>(i <= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
261 * or -1 if there is no such index.
262 *
263 * @param e element to search for
264 * @param index index to start searching backwards from
265 * @return the index of the last occurrence of the element at position
266 * less than or equal to <tt>index</tt> in this list;
267 * -1 if the element is not found.
268 * @throws IndexOutOfBoundsException if the specified index is greater
269 * than or equal to the current size of this list
270 */
271 public int lastIndexOf(E e, int index) {
272 Object[] elements = getArray();
273 return lastIndexOf(e, elements, index);
274 }
275
276 /**
277 * Returns a shallow copy of this list. (The elements themselves
278 * are not copied.)
279 *
280 * @return a clone of this list
281 */
282 public Object clone() {
283 try {
284 CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
285 c.resetLock();
286 return c;
287 } catch (CloneNotSupportedException e) {
288 // this shouldn't happen, since we are Cloneable
289 throw new InternalError();
290 }
291 }
292
293 /**
294 * Returns an array containing all of the elements in this list
295 * in proper sequence (from first to last element).
296 *
297 * <p>The returned array will be "safe" in that no references to it are
298 * maintained by this list. (In other words, this method must allocate
299 * a new array). The caller is thus free to modify the returned array.
300 *
301 * <p>This method acts as bridge between array-based and collection-based
302 * APIs.
303 *
304 * @return an array containing all the elements in this list
305 */
306 public Object[] toArray() {
307 Object[] elements = getArray();
308 return Arrays.copyOf(elements, elements.length);
309 }
310
311 /**
312 * Returns an array containing all of the elements in this list in
313 * proper sequence (from first to last element); the runtime type of
314 * the returned array is that of the specified array. If the list fits
315 * in the specified array, it is returned therein. Otherwise, a new
316 * array is allocated with the runtime type of the specified array and
317 * the size of this list.
318 *
319 * <p>If this list fits in the specified array with room to spare
320 * (i.e., the array has more elements than this list), the element in
321 * the array immediately following the end of the list is set to
322 * <tt>null</tt>. (This is useful in determining the length of this
323 * list <i>only</i> if the caller knows that this list does not contain
324 * any null elements.)
325 *
326 * <p>Like the {@link #toArray()} method, this method acts as bridge between
327 * array-based and collection-based APIs. Further, this method allows
328 * precise control over the runtime type of the output array, and may,
329 * under certain circumstances, be used to save allocation costs.
330 *
331 * <p>Suppose <tt>x</tt> is a list known to contain only strings.
332 * The following code can be used to dump the list into a newly
333 * allocated array of <tt>String</tt>:
334 *
335 * <pre>
336 * 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 private 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 * Append 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 (optional)
635 * @throws NullPointerException if this list contains a null element and the
636 * specified collection does not permit null elements (optional),
637 * or if the specified collection is null
638 * @see #remove(Object)
639 */
640 public boolean removeAll(Collection<?> c) {
641 final ReentrantLock lock = this.lock;
642 lock.lock();
643 try {
644 Object[] elements = getArray();
645 int len = elements.length;
646 if (len != 0) {
647 // temp array holds those elements we know we want to keep
648 int newlen = 0;
649 Object[] temp = new Object[len];
650 for (int i = 0; i < len; ++i) {
651 Object element = elements[i];
652 if (!c.contains(element))
653 temp[newlen++] = element;
654 }
655 if (newlen != len) {
656 setArray(Arrays.copyOf(temp, newlen));
657 return true;
658 }
659 }
660 return false;
661 } finally {
662 lock.unlock();
663 }
664 }
665
666 /**
667 * Retains only the elements in this list that are contained in the
668 * specified collection. In other words, removes from this list all of
669 * its elements that are not contained in the specified collection.
670 *
671 * @param c collection containing elements to be retained in this list
672 * @return <tt>true</tt> if this list changed as a result of the call
673 * @throws ClassCastException if the class of an element of this list
674 * is incompatible with the specified collection (optional)
675 * @throws NullPointerException if this list contains a null element and the
676 * specified collection does not permit null elements (optional),
677 * or if the specified collection is null
678 * @see #remove(Object)
679 */
680 public boolean retainAll(Collection<?> c) {
681 final ReentrantLock lock = this.lock;
682 lock.lock();
683 try {
684 Object[] elements = getArray();
685 int len = elements.length;
686 if (len != 0) {
687 // temp array holds those elements we know we want to keep
688 int newlen = 0;
689 Object[] temp = new Object[len];
690 for (int i = 0; i < len; ++i) {
691 Object element = elements[i];
692 if (c.contains(element))
693 temp[newlen++] = element;
694 }
695 if (newlen != len) {
696 setArray(Arrays.copyOf(temp, newlen));
697 return true;
698 }
699 }
700 return false;
701 } finally {
702 lock.unlock();
703 }
704 }
705
706 /**
707 * Appends all of the elements in the specified collection that
708 * are not already contained in this list, to the end of
709 * this list, in the order that they are returned by the
710 * specified collection's iterator.
711 *
712 * @param c collection containing elements to be added to this list
713 * @return the number of elements added
714 * @throws NullPointerException if the specified collection is null
715 * @see #addIfAbsent(Object)
716 */
717 public int addAllAbsent(Collection<? extends E> c) {
718 Object[] cs = c.toArray();
719 if (cs.length == 0)
720 return 0;
721 Object[] uniq = new Object[cs.length];
722 final ReentrantLock lock = this.lock;
723 lock.lock();
724 try {
725 Object[] elements = getArray();
726 int len = elements.length;
727 int added = 0;
728 for (int i = 0; i < cs.length; ++i) { // scan for duplicates
729 Object e = cs[i];
730 if (indexOf(e, elements, 0, len) < 0 &&
731 indexOf(e, uniq, 0, added) < 0)
732 uniq[added++] = e;
733 }
734 if (added > 0) {
735 Object[] newElements = Arrays.copyOf(elements, len + added);
736 System.arraycopy(uniq, 0, newElements, len, added);
737 setArray(newElements);
738 }
739 return added;
740 } finally {
741 lock.unlock();
742 }
743 }
744
745 /**
746 * Removes all of the elements from this list.
747 * The list will be empty after this call returns.
748 */
749 public void clear() {
750 final ReentrantLock lock = this.lock;
751 lock.lock();
752 try {
753 setArray(new Object[0]);
754 } finally {
755 lock.unlock();
756 }
757 }
758
759 /**
760 * Appends all of the elements in the specified collection to the end
761 * of this list, in the order that they are returned by the specified
762 * collection's iterator.
763 *
764 * @param c collection containing elements to be added to this list
765 * @return <tt>true</tt> if this list changed as a result of the call
766 * @throws NullPointerException if the specified collection is null
767 * @see #add(Object)
768 */
769 public boolean addAll(Collection<? extends E> c) {
770 Object[] cs = c.toArray();
771 if (cs.length == 0)
772 return false;
773 final ReentrantLock lock = this.lock;
774 lock.lock();
775 try {
776 Object[] elements = getArray();
777 int len = elements.length;
778 Object[] newElements = Arrays.copyOf(elements, len + cs.length);
779 System.arraycopy(cs, 0, newElements, len, cs.length);
780 setArray(newElements);
781 return true;
782 } finally {
783 lock.unlock();
784 }
785 }
786
787 /**
788 * Inserts all of the elements in the specified collection into this
789 * list, starting at the specified position. Shifts the element
790 * currently at that position (if any) and any subsequent elements to
791 * the right (increases their indices). The new elements will appear
792 * in this list in the order that they are returned by the
793 * specified collection's iterator.
794 *
795 * @param index index at which to insert the first element
796 * from the specified collection
797 * @param c collection containing elements to be added to this list
798 * @return <tt>true</tt> if this list changed as a result of the call
799 * @throws IndexOutOfBoundsException {@inheritDoc}
800 * @throws NullPointerException if the specified collection is null
801 * @see #add(int,Object)
802 */
803 public boolean addAll(int index, Collection<? extends E> c) {
804 Object[] cs = c.toArray();
805 final ReentrantLock lock = this.lock;
806 lock.lock();
807 try {
808 Object[] elements = getArray();
809 int len = elements.length;
810 if (index > len || index < 0)
811 throw new IndexOutOfBoundsException("Index: "+index+
812 ", Size: "+len);
813 if (cs.length == 0)
814 return false;
815 int numMoved = len - index;
816 Object[] newElements;
817 if (numMoved == 0)
818 newElements = Arrays.copyOf(elements, len + cs.length);
819 else {
820 newElements = new Object[len + cs.length];
821 System.arraycopy(elements, 0, newElements, 0, index);
822 System.arraycopy(elements, index,
823 newElements, index + cs.length,
824 numMoved);
825 }
826 System.arraycopy(cs, 0, newElements, index, cs.length);
827 setArray(newElements);
828 return true;
829 } finally {
830 lock.unlock();
831 }
832 }
833
834 /**
835 * Save the state of the list to a stream (i.e., serialize it).
836 *
837 * @serialData The length of the array backing the list is emitted
838 * (int), followed by all of its elements (each an Object)
839 * in the proper order.
840 * @param s the stream
841 */
842 private void writeObject(java.io.ObjectOutputStream s)
843 throws java.io.IOException{
844
845 // Write out element count, and any hidden stuff
846 s.defaultWriteObject();
847
848 Object[] elements = getArray();
849 int len = elements.length;
850 // Write out array length
851 s.writeInt(len);
852
853 // Write out all elements in the proper order.
854 for (int i = 0; i < len; i++)
855 s.writeObject(elements[i]);
856 }
857
858 /**
859 * Reconstitute the list from a stream (i.e., deserialize it).
860 * @param s the stream
861 */
862 private void readObject(java.io.ObjectInputStream s)
863 throws java.io.IOException, ClassNotFoundException {
864
865 // Read in size, and any hidden stuff
866 s.defaultReadObject();
867
868 // bind to new lock
869 resetLock();
870
871 // Read in array length and allocate array
872 int len = s.readInt();
873 Object[] elements = new Object[len];
874
875 // Read in all elements in the proper order.
876 for (int i = 0; i < len; i++)
877 elements[i] = s.readObject();
878 setArray(elements);
879 }
880
881 /**
882 * Returns a string representation of this list. The string
883 * representation consists of the string representations of the list's
884 * elements in the order they are returned by its iterator, enclosed in
885 * square brackets (<tt>"[]"</tt>). Adjacent elements are separated by
886 * the characters <tt>", "</tt> (comma and space). Elements are
887 * converted to strings as by {@link String#valueOf(Object)}.
888 *
889 * @return a string representation of this list
890 */
891 public String toString() {
892 return Arrays.toString(getArray());
893 }
894
895 /**
896 * Compares the specified object with this list for equality.
897 * Returns {@code true} if the specified object is the same object
898 * as this object, or if it is also a {@link List} and the sequence
899 * of elements returned by an {@linkplain List#iterator() iterator}
900 * over the specified list is the same as the sequence returned by
901 * an iterator over this list. The two sequences are considered to
902 * be the same if they have the same length and corresponding
903 * elements at the same position in the sequence are <em>equal</em>.
904 * Two elements {@code e1} and {@code e2} are considered
905 * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
906 *
907 * @param o the object to be compared for equality with this list
908 * @return {@code true} if the specified object is equal to this list
909 */
910 public boolean equals(Object o) {
911 if (o == this)
912 return true;
913 if (!(o instanceof List))
914 return false;
915
916 List<?> list = (List<?>)(o);
917 Iterator<?> it = list.iterator();
918 Object[] elements = getArray();
919 int len = elements.length;
920 for (int i = 0; i < len; ++i)
921 if (!it.hasNext() || !eq(elements[i], it.next()))
922 return false;
923 if (it.hasNext())
924 return false;
925 return true;
926 }
927
928 /**
929 * Returns the hash code value for this list.
930 *
931 * <p>This implementation uses the definition in {@link List#hashCode}.
932 *
933 * @return the hash code value for this list
934 */
935 public int hashCode() {
936 int hashCode = 1;
937 Object[] elements = getArray();
938 int len = elements.length;
939 for (int i = 0; i < len; ++i) {
940 Object obj = elements[i];
941 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
942 }
943 return hashCode;
944 }
945
946 /**
947 * Returns an iterator over the elements in this list in proper sequence.
948 *
949 * <p>The returned iterator provides a snapshot of the state of the list
950 * when the iterator was constructed. No synchronization is needed while
951 * traversing the iterator. The iterator does <em>NOT</em> support the
952 * <tt>remove</tt> method.
953 *
954 * @return an iterator over the elements in this list in proper sequence
955 */
956 public Iterator<E> iterator() {
957 return new COWIterator<E>(getArray(), 0);
958 }
959
960 /**
961 * {@inheritDoc}
962 *
963 * <p>The returned iterator provides a snapshot of the state of the list
964 * when the iterator was constructed. No synchronization is needed while
965 * traversing the iterator. The iterator does <em>NOT</em> support the
966 * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
967 */
968 public ListIterator<E> listIterator() {
969 return new COWIterator<E>(getArray(), 0);
970 }
971
972 /**
973 * {@inheritDoc}
974 *
975 * <p>The returned iterator provides a snapshot of the state of the list
976 * when the iterator was constructed. No synchronization is needed while
977 * traversing the iterator. The iterator does <em>NOT</em> support the
978 * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
979 *
980 * @throws IndexOutOfBoundsException {@inheritDoc}
981 */
982 public ListIterator<E> listIterator(final int index) {
983 Object[] elements = getArray();
984 int len = elements.length;
985 if (index<0 || index>len)
986 throw new IndexOutOfBoundsException("Index: "+index);
987
988 return new COWIterator<E>(elements, index);
989 }
990
991 private static class COWIterator<E> implements ListIterator<E> {
992 /** Snapshot of the array **/
993 private final Object[] snapshot;
994 /** Index of element to be returned by subsequent call to next. */
995 private int cursor;
996
997 private COWIterator(Object[] elements, int initialCursor) {
998 cursor = initialCursor;
999 snapshot = elements;
1000 }
1001
1002 public boolean hasNext() {
1003 return cursor < snapshot.length;
1004 }
1005
1006 public boolean hasPrevious() {
1007 return cursor > 0;
1008 }
1009
1010 @SuppressWarnings("unchecked")
1011 public E next() {
1012 if (! hasNext())
1013 throw new NoSuchElementException();
1014 return (E) snapshot[cursor++];
1015 }
1016
1017 @SuppressWarnings("unchecked")
1018 public E previous() {
1019 if (! hasPrevious())
1020 throw new NoSuchElementException();
1021 return (E) snapshot[--cursor];
1022 }
1023
1024 public int nextIndex() {
1025 return cursor;
1026 }
1027
1028 public int previousIndex() {
1029 return cursor-1;
1030 }
1031
1032 /**
1033 * Not supported. Always throws UnsupportedOperationException.
1034 * @throws UnsupportedOperationException always; <tt>remove</tt>
1035 * is not supported by this iterator.
1036 */
1037 public void remove() {
1038 throw new UnsupportedOperationException();
1039 }
1040
1041 /**
1042 * Not supported. Always throws UnsupportedOperationException.
1043 * @throws UnsupportedOperationException always; <tt>set</tt>
1044 * is not supported by this iterator.
1045 */
1046 public void set(E e) {
1047 throw new UnsupportedOperationException();
1048 }
1049
1050 /**
1051 * Not supported. Always throws UnsupportedOperationException.
1052 * @throws UnsupportedOperationException always; <tt>add</tt>
1053 * is not supported by this iterator.
1054 */
1055 public void add(E e) {
1056 throw new UnsupportedOperationException();
1057 }
1058 }
1059
1060 /**
1061 * Returns a view of the portion of this list between
1062 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1063 * The returned list is backed by this list, so changes in the
1064 * returned list are reflected in this list.
1065 *
1066 * <p>The semantics of the list returned by this method become
1067 * undefined if the backing list (i.e., this list) is modified in
1068 * any way other than via the returned list.
1069 *
1070 * @param fromIndex low endpoint (inclusive) of the subList
1071 * @param toIndex high endpoint (exclusive) of the subList
1072 * @return a view of the specified range within this list
1073 * @throws IndexOutOfBoundsException {@inheritDoc}
1074 */
1075 public List<E> subList(int fromIndex, int toIndex) {
1076 final ReentrantLock lock = this.lock;
1077 lock.lock();
1078 try {
1079 Object[] elements = getArray();
1080 int len = elements.length;
1081 if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1082 throw new IndexOutOfBoundsException();
1083 return new COWSubList<E>(this, fromIndex, toIndex);
1084 } finally {
1085 lock.unlock();
1086 }
1087 }
1088
1089 /**
1090 * Sublist for CopyOnWriteArrayList.
1091 * This class extends AbstractList merely for convenience, to
1092 * avoid having to define addAll, etc. This doesn't hurt, but
1093 * is wasteful. This class does not need or use modCount
1094 * mechanics in AbstractList, but does need to check for
1095 * concurrent modification using similar mechanics. On each
1096 * operation, the array that we expect the backing list to use
1097 * is checked and updated. Since we do this for all of the
1098 * base operations invoked by those defined in AbstractList,
1099 * all is well. While inefficient, this is not worth
1100 * improving. The kinds of list operations inherited from
1101 * AbstractList are already so slow on COW sublists that
1102 * adding a bit more space/time doesn't seem even noticeable.
1103 */
1104 private static class COWSubList<E>
1105 extends AbstractList<E>
1106 implements RandomAccess
1107 {
1108 private final CopyOnWriteArrayList<E> l;
1109 private final int offset;
1110 private int size;
1111 private Object[] expectedArray;
1112
1113 // only call this holding l's lock
1114 COWSubList(CopyOnWriteArrayList<E> list,
1115 int fromIndex, int toIndex) {
1116 l = list;
1117 expectedArray = l.getArray();
1118 offset = fromIndex;
1119 size = toIndex - fromIndex;
1120 }
1121
1122 // only call this holding l's lock
1123 private void checkForComodification() {
1124 if (l.getArray() != expectedArray)
1125 throw new ConcurrentModificationException();
1126 }
1127
1128 // only call this holding l's lock
1129 private void rangeCheck(int index) {
1130 if (index<0 || index>=size)
1131 throw new IndexOutOfBoundsException("Index: "+index+
1132 ",Size: "+size);
1133 }
1134
1135 public E set(int index, E element) {
1136 final ReentrantLock lock = l.lock;
1137 lock.lock();
1138 try {
1139 rangeCheck(index);
1140 checkForComodification();
1141 E x = l.set(index+offset, element);
1142 expectedArray = l.getArray();
1143 return x;
1144 } finally {
1145 lock.unlock();
1146 }
1147 }
1148
1149 public E get(int index) {
1150 final ReentrantLock lock = l.lock;
1151 lock.lock();
1152 try {
1153 rangeCheck(index);
1154 checkForComodification();
1155 return l.get(index+offset);
1156 } finally {
1157 lock.unlock();
1158 }
1159 }
1160
1161 public int size() {
1162 final ReentrantLock lock = l.lock;
1163 lock.lock();
1164 try {
1165 checkForComodification();
1166 return size;
1167 } finally {
1168 lock.unlock();
1169 }
1170 }
1171
1172 public void add(int index, E element) {
1173 final ReentrantLock lock = l.lock;
1174 lock.lock();
1175 try {
1176 checkForComodification();
1177 if (index<0 || index>size)
1178 throw new IndexOutOfBoundsException();
1179 l.add(index+offset, element);
1180 expectedArray = l.getArray();
1181 size++;
1182 } finally {
1183 lock.unlock();
1184 }
1185 }
1186
1187 public void clear() {
1188 final ReentrantLock lock = l.lock;
1189 lock.lock();
1190 try {
1191 checkForComodification();
1192 l.removeRange(offset, offset+size);
1193 expectedArray = l.getArray();
1194 size = 0;
1195 } finally {
1196 lock.unlock();
1197 }
1198 }
1199
1200 public E remove(int index) {
1201 final ReentrantLock lock = l.lock;
1202 lock.lock();
1203 try {
1204 rangeCheck(index);
1205 checkForComodification();
1206 E result = l.remove(index+offset);
1207 expectedArray = l.getArray();
1208 size--;
1209 return result;
1210 } finally {
1211 lock.unlock();
1212 }
1213 }
1214
1215 public boolean remove(Object o) {
1216 int index = indexOf(o);
1217 if (index == -1)
1218 return false;
1219 remove(index);
1220 return true;
1221 }
1222
1223 public Iterator<E> iterator() {
1224 final ReentrantLock lock = l.lock;
1225 lock.lock();
1226 try {
1227 checkForComodification();
1228 return new COWSubListIterator<E>(l, 0, offset, size);
1229 } finally {
1230 lock.unlock();
1231 }
1232 }
1233
1234 public ListIterator<E> listIterator(final int index) {
1235 final ReentrantLock lock = l.lock;
1236 lock.lock();
1237 try {
1238 checkForComodification();
1239 if (index<0 || index>size)
1240 throw new IndexOutOfBoundsException("Index: "+index+
1241 ", Size: "+size);
1242 return new COWSubListIterator<E>(l, index, offset, size);
1243 } finally {
1244 lock.unlock();
1245 }
1246 }
1247
1248 public List<E> subList(int fromIndex, int toIndex) {
1249 final ReentrantLock lock = l.lock;
1250 lock.lock();
1251 try {
1252 checkForComodification();
1253 if (fromIndex<0 || toIndex>size)
1254 throw new IndexOutOfBoundsException();
1255 return new COWSubList<E>(l, fromIndex + offset,
1256 toIndex + offset);
1257 } finally {
1258 lock.unlock();
1259 }
1260 }
1261
1262 }
1263
1264
1265 private static class COWSubListIterator<E> implements ListIterator<E> {
1266 private final ListIterator<E> i;
1267 private final int index;
1268 private final int offset;
1269 private final int size;
1270
1271 COWSubListIterator(List<E> l, int index, int offset,
1272 int size) {
1273 this.index = index;
1274 this.offset = offset;
1275 this.size = size;
1276 i = l.listIterator(index+offset);
1277 }
1278
1279 public boolean hasNext() {
1280 return nextIndex() < size;
1281 }
1282
1283 public E next() {
1284 if (hasNext())
1285 return i.next();
1286 else
1287 throw new NoSuchElementException();
1288 }
1289
1290 public boolean hasPrevious() {
1291 return previousIndex() >= 0;
1292 }
1293
1294 public E previous() {
1295 if (hasPrevious())
1296 return i.previous();
1297 else
1298 throw new NoSuchElementException();
1299 }
1300
1301 public int nextIndex() {
1302 return i.nextIndex() - offset;
1303 }
1304
1305 public int previousIndex() {
1306 return i.previousIndex() - offset;
1307 }
1308
1309 public void remove() {
1310 throw new UnsupportedOperationException();
1311 }
1312
1313 public void set(E e) {
1314 throw new UnsupportedOperationException();
1315 }
1316
1317 public void add(E e) {
1318 throw new UnsupportedOperationException();
1319 }
1320 }
1321
1322 // Support for resetting lock while deserializing
1323 private static final Unsafe unsafe = Unsafe.getUnsafe();
1324 private static final long lockOffset;
1325 static {
1326 try {
1327 lockOffset = unsafe.objectFieldOffset
1328 (CopyOnWriteArrayList.class.getDeclaredField("lock"));
1329 } catch (Exception ex) { throw new Error(ex); }
1330 }
1331 private void resetLock() {
1332 unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
1333 }
1334
1335 }
Save This Page