1 /*
2 * Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.3 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.4 *5 *6 *7 *8 *9 *10 *11 *12 *13 *14 *15 *16 *17 *18 *19 *20 *21 *22 *23 *24 */
25
26 /*
27 * Written by Doug Lea with assistance from members of JCP JSR-16628 * 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, .33 * All rights reserved.34 */
35
36 ;37 import .*;38 import .*;39 ;40
41 /**
42 * A thread-safe variant of {@} in which all mutative43 * operations (add, set, and so on) are implemented by44 * making a fresh copy of the underlying array.45 *46 *
This is ordinarily too costly, but may be more efficient47 * than alternatives when traversal operations vastly outnumber48 * mutations, and is useful when you cannot or don't want to49 * synchronize traversals, yet need to preclude interference among50 * concurrent threads. The "snapshot" style iterator method uses a51 * reference to the state of the array at the point that the iterator52 * was created. This array never changes during the lifetime of the53 * iterator, so interference is impossible and the iterator is54 * guaranteed not to throw ConcurrentModificationException.55 * The iterator will not reflect additions, removals, or changes to56 * the list since the iterator was created. Element-changing57 * operations on iterators themselves (remove, set, and58 * add) are not supported. These methods throw59 * UnsupportedOperationException.60 *61 *
All elements are permitted, including null.62 *63 *
Memory consistency effects: As with other concurrent64 * collections, actions in a thread prior to placing an object into a65 * {@codeCopyOnWriteArrayList}66 * happen-before67 * actions subsequent to the access or removal of that element from68 * the {@codeCopyOnWriteArrayList} in another thread.69 *70 *
This class is a member of the71 * 72 * Java Collections Framework.73 *74 *@since1.575 *@authorDoug Lea76 *@param the type of elements held in this collection77 */
78 public class CopyOnWriteArrayList
79 implements List, RandomAccess, Cloneable, {80 private static final long serialVersionUID = 8673264195747942595L;81
82 /**The lock protecting all mutators*/
83 transient final ReentrantLock lock = newReentrantLock();84
85 /**The array, accessed only via getArray/setArray.*/
86 private volatile transientObject[] array;87
88 /**
89 * Gets the array. Non-private so as to also be accessible90 * from CopyOnWriteArraySet class.91 */
92 finalObject[] getArray() {93 returnarray;94 }95
96 /**
97 * Sets the array.98 */
99 final voidsetArray(Object[] a) {100 array =a;101 }102
103 /**
104 * Creates an empty list.105 */
106 publicCopyOnWriteArrayList() {107 setArray(new Object[0]);108 }109
110 /**
111 * Creates a list containing the elements of the specified112 * collection, in the order they are returned by the collection's113 * iterator.114 *115 *@paramc the collection of initially held elements116 *@throwsNullPointerException if the specified collection is null117 */
118 public CopyOnWriteArrayList(Collection extends E>c) {119 Object[] elements =();120 // might (incorrectly) not return Object[] (see 6260652)
121 if (() != Object[].class)122 elements = (elements, , Object[].class);123 setArray(elements);124 }125
126 /**
127 * Creates a list holding a copy of the given array.128 *129 *@paramtoCopyIn the array (a copy of this array is used as the130 * internal array)131 *@throwsNullPointerException if the specified array is null132 */
133 publicCopyOnWriteArrayList(E[] toCopyIn) {134 setArray((toCopyIn, , Object[].class));135 }136
137 /**
138 * Returns the number of elements in this list.139 *140 *@returnthe number of elements in this list141 */
142 public intsize() {143 returngetArray().length;144 }145
146 /**
147 * Returns true if this list contains no elements.148 *149 *@returntrue if this list contains no elements150 */
151 public booleanisEmpty() {152 return size() == 0;153 }154
155 /**
156 * Test for equality, coping with nulls.157 */
158 private static booleaneq(Object o1, Object o2) {159 return (o1 == null ? o2 == null: (o2));160 }161
162 /**
163 * static version of indexOf, to allow repeated calls without164 * needing to re-acquire array each time.165 *@paramo element to search for166 *@paramelements the array167 *@paramindex first index to search168 *@paramfence one past last index to search169 *@returnindex of element, or -1 if absent170 */
171 private static intindexOf(Object o, Object[] elements,172 int index, intfence) {173 if (o == null) {174 for (int i = index; i < fence; i++)175 if (elements[i] == null)176 returni;177 } else{178 for (int i = index; i < fence; i++)179 if((elements[i]))180 returni;181 }182 return -1;183 }184
185 /**
186 * static version of lastIndexOf.187 *@paramo element to search for188 *@paramelements the array189 *@paramindex first index to search190 *@returnindex of element, or -1 if absent191 */
192 private static int lastIndexOf(Object o, Object[] elements, intindex) {193 if (o == null) {194 for (int i = index; i >= 0; i--)195 if (elements[i] == null)196 returni;197 } else{198 for (int i = index; i >= 0; i--)199 if((elements[i]))200 returni;201 }202 return -1;203 }204
205 /**
206 * Returns true if this list contains the specified element.207 * More formally, returns true if and only if this list contains208 * at least one element e such that209 * (o==null ? e==null : (e)).210 *211 *@paramo element whose presence in this list is to be tested212 *@returntrue if this list contains the specified element213 */
214 public booleancontains(Object o) {215 Object[] elements =getArray();216 return indexOf(o, elements, 0, ) >= 0;217 }218
219 /**
220 * {@inheritDoc}221 */
222 public intindexOf(Object o) {223 Object[] elements =getArray();224 return indexOf(o, elements, 0, );225 }226
227 /**
228 * Returns the index of the first occurrence of the specified element in229 * this list, searching forwards from index, or returns -1 if230 * the element is not found.231 * More formally, returns the lowest index i such that232 * (i >= index && (e==null ? get(i)==null : (get(i)))),233 * or -1 if there is no such index.234 *235 *@parame element to search for236 *@paramindex index to start searching from237 *@returnthe index of the first occurrence of the element in238 * this list at position index or later in the list;239 * -1 if the element is not found.240 *@throwsIndexOutOfBoundsException if the specified index is negative241 */
242 public int indexOf(E e, intindex) {243 Object[] elements =getArray();244 returnindexOf(e, elements, index, );245 }246
247 /**
248 * {@inheritDoc}249 */
250 public intlastIndexOf(Object o) {251 Object[] elements =getArray();252 return lastIndexOf(o, elements, - 1);253 }254
255 /**
256 * Returns the index of the last occurrence of the specified element in257 * this list, searching backwards from index, or returns -1 if258 * the element is not found.259 * More formally, returns the highest index i such that260 * (i <= index && (e==null ? get(i)==null : (get(i)))),261 * or -1 if there is no such index.262 *263 *@parame element to search for264 *@paramindex index to start searching backwards from265 *@returnthe index of the last occurrence of the element at position266 * less than or equal to index in this list;267 * -1 if the element is not found.268 *@throwsIndexOutOfBoundsException if the specified index is greater269 * than or equal to the current size of this list270 */
271 public int lastIndexOf(E e, intindex) {272 Object[] elements =getArray();273 returnlastIndexOf(e, elements, index);274 }275
276 /**
277 * Returns a shallow copy of this list. (The elements themselves278 * are not copied.)279 *280 *@returna clone of this list281 */
282 publicObject clone() {283 try{284 CopyOnWriteArrayList c = (CopyOnWriteArrayList)(());285 ();286 returnc;287 } catch(CloneNotSupportedException e) {288 //this shouldn't happen, since we are Cloneable
289 throw newInternalError();290 }291 }292
293 /**
294 * Returns an array containing all of the elements in this list295 * in proper sequence (from first to last element).296 *297 *
The returned array will be "safe" in that no references to it are298 * maintained by this list. (In other words, this method must allocate299 * a new array). The caller is thus free to modify the returned array.300 *301 *
This method acts as bridge between array-based and collection-based302 * APIs.303 *304 *@returnan array containing all the elements in this list305 */
306 publicObject[] toArray() {307 Object[] elements =getArray();308 (elements, );309 }310
311 /**
312 * Returns an array containing all of the elements in this list in313 * proper sequence (from first to last element); the runtime type of314 * the returned array is that of the specified array. If the list fits315 * in the specified array, it is returned therein. Otherwise, a new316 * array is allocated with the runtime type of the specified array and317 * the size of this list.318 *319 *
If this list fits in the specified array with room to spare320 * (., the array has more elements than this list), the element in321 * the array immediately following the end of the list is set to322 * null. (This is useful in determining the length of this323 * list only if the caller knows that this list does not contain324 * any null elements.)325 *326 *
Like the {@link#toArray()} method, this method acts as bridge between327 * array-based and collection-based APIs. Further, this method allows328 * precise control over the runtime type of the output array, and may,329 * under certain circumstances, be used to save allocation costs.330 *331 *
Suppose x is a list known to contain only strings.332 * The following code can be used to dump the list into a newly333 * allocated array of String:334 *335 *
336 * String[] y = (new String[0]);337 *338 * Note that toArray(new Object[0]) is identical in function to339 * toArray().340 *341 *@parama the array into which the elements of the list are to342 * be stored, if it is big enough; otherwise, a new array of the343 * same runtime type is allocated for this purpose.344 *@returnan array containing all the elements in this list345 *@throwsArrayStoreException if the runtime type of the specified array346 * is not a supertype of the runtime type of every element in347 * this list348 *@throwsNullPointerException if the specified array is null349 */
350 @SuppressWarnings("unchecked")351 public T[] toArray(T a[]) {352 Object[] elements =getArray();353 int len =;354 if ( len)359 a[len] = null;360 returna;361 }362 }363
364 //Positional Access Operations
365
366 @SuppressWarnings("unchecked")367 private E get(Object[] a, intindex) {368 return(E) a[index];369 }370
371 /**
372 * {@inheritDoc}373 *374 *@throwsIndexOutOfBoundsException {@inheritDoc}375 */
376 public E get(intindex) {377 returnget(getArray(), index);378 }379
380 /**
381 * Replaces the element at the specified position in this list with the382 * specified element.383 *384 *@throwsIndexOutOfBoundsException {@inheritDoc}385 */
386 public E set(intindex, E element) {387 final ReentrantLock lock = ;388 ();389 try{390 Object[] elements =getArray();391 E oldValue =get(elements, index);392
393 if (oldValue !=element) {394 int len =;395 Object[] newElements =(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 returnoldValue;403 } finally{404 lock.unlock();405 }406 }407
408 /**
409 * Appends the specified element to the end of this list.410 *411 *@parame element to be appended to this list412 *@returntrue (as specified by {@linkCollection#add})413 */
414 public booleanadd(E e) {415 final ReentrantLock lock = ;416 ();417 try{418 Object[] elements =getArray();419 int len =;420 Object[] newElements = (elements, len + 1);421 newElements[len] =e;422 setArray(newElements);423 return true;424 } finally{425 ();426 }427 }428
429 /**
430 * Inserts the specified element at the specified position in this431 * list. Shifts the element currently at that position (if any) and432 * any subsequent elements to the right (adds one to their indices).433 *434 *@throwsIndexOutOfBoundsException {@inheritDoc}435 */
436 public void add(intindex, E element) {437 final ReentrantLock lock = ;438 ();439 try{440 Object[] elements =getArray();441 int len =;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 = (elements, len + 1);449 else{450 newElements = new Object[len + 1];451 (elements, 0, newElements, 0, index);452 (elements, index, newElements, index + 1,453 numMoved);454 }455 newElements[index] =element;456 setArray(newElements);457 } finally{458 ();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 their465 * indices). Returns the element that was removed from the list.466 *467 *@throwsIndexOutOfBoundsException {@inheritDoc}468 */
469 public E remove(intindex) {470 final ReentrantLock lock = ;471 ();472 try{473 Object[] elements =getArray();474 int len =;475 E oldValue =get(elements, index);476 int numMoved = len - index - 1;477 if (numMoved == 0)478 setArray((elements, len - 1));479 else{480 Object[] newElements = new Object[len - 1];481 (elements, 0, newElements, 0, index);482 (elements, index + 1, newElements, index,483 numMoved);484 setArray(newElements);485 }486 returnoldValue;487 } finally{488 ();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 is495 * unchanged. More formally, removes the element with the lowest index496 * i such that497 * (o==null ? get(i)==null : (get(i)))498 * (if such an element exists). Returns true if this list499 * contained the specified element (or equivalently, if this list500 * changed as a result of the call).501 *502 *@paramo element to be removed from this list, if present503 *@returntrue if this list contained the specified element504 */
505 public booleanremove(Object o) {506 final ReentrantLock lock = ;507 ();508 try{509 Object[] elements =getArray();510 int len =;511 if (len != 0) {512 //Copy while searching for element to remove513 //This wins in the normal case of element being present
514 int newlen = len - 1;515 Object[] newElements = newObject[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 ();537 }538 }539
540 /**
541 * Removes from this list all of the elements whose index is between542 * fromIndex, inclusive, and toIndex, exclusive.543 * Shifts any succeeding elements to the left (reduces their index).544 * This call shortens the list by (toIndex - fromIndex) elements.545 * (If toIndex==fromIndex, this operation has no effect.)546 *547 *@paramfromIndex index of first element to be removed548 *@paramtoIndex index after last element to be removed549 *@throwsIndexOutOfBoundsException if fromIndex or toIndex out of range550 * ({@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex})551 */
552 private void removeRange(int fromIndex, inttoIndex) {553 final ReentrantLock lock = ;554 ();555 try{556 Object[] elements =getArray();557 int len =;558
559 if (fromIndex < 0 || toIndex > len || toIndex
577 /**
578 * Append the element if not present.579 *580 *@parame element to be added to this list, if absent581 *@returntrue if the element was added582 */
583 public booleanaddIfAbsent(E e) {584 final ReentrantLock lock = ;585 ();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 =;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 ();603 }604 }605
606 /**
607 * Returns true if this list contains all of the elements of the608 * specified collection.609 *610 *@paramc collection to be checked for containment in this list611 *@returntrue if this list contains all of the elements of the612 * specified collection613 *@throwsNullPointerException if the specified collection is null614 *@see#contains(Object)615 */
616 public boolean containsAll(Collection>c) {617 Object[] elements =getArray();618 int len =;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 in628 * the specified collection. This is a particularly expensive operation629 * in this class because of the need for an internal temporary array.630 *631 *@paramc collection containing elements to be removed from this list632 *@returntrue if this list changed as a result of the call633 *@throwsClassCastException if the class of an element of this list634 * is incompatible with the specified collection635 * (optional)636 *@throwsNullPointerException if this list contains a null element and the637 * specified collection does not permit null elements638 * (optional),639 * or if the specified collection is null640 *@see#remove(Object)641 */
642 public boolean removeAll(Collection>c) {643 final ReentrantLock lock = ;644 ();645 try{646 Object[] elements =getArray();647 int len =;648 if (len != 0) {649 //temp array holds those elements we know we want to keep
650 int newlen = 0;651 Object[] temp = newObject[len];652 for (int i = 0; i < len; ++i) {653 Object element =elements[i];654 if (!(element))655 temp[newlen++] =element;656 }657 if (newlen !=len) {658 setArray((temp, newlen));659 return true;660 }661 }662 return false;663 } finally{664 ();665 }666 }667
668 /**
669 * Retains only the elements in this list that are contained in the670 * specified collection. In other words, removes from this list all of671 * its elements that are not contained in the specified collection.672 *673 *@paramc collection containing elements to be retained in this list674 *@returntrue if this list changed as a result of the call675 *@throwsClassCastException if the class of an element of this list676 * is incompatible with the specified collection677 * (optional)678 *@throwsNullPointerException if this list contains a null element and the679 * specified collection does not permit null elements680 * (optional),681 * or if the specified collection is null682 *@see#remove(Object)683 */
684 public boolean retainAll(Collection>c) {685 final ReentrantLock lock = ;686 ();687 try{688 Object[] elements =getArray();689 int len =;690 if (len != 0) {691 //temp array holds those elements we know we want to keep
692 int newlen = 0;693 Object[] temp = newObject[len];694 for (int i = 0; i < len; ++i) {695 Object element =elements[i];696 if((element))697 temp[newlen++] =element;698 }699 if (newlen !=len) {700 setArray((temp, newlen));701 return true;702 }703 }704 return false;705 } finally{706 ();707 }708 }709
710 /**
711 * Appends all of the elements in the specified collection that712 * are not already contained in this list, to the end of713 * this list, in the order that they are returned by the714 * specified collection's iterator.715 *716 *@paramc collection containing elements to be added to this list717 *@returnthe number of elements added718 *@throwsNullPointerException if the specified collection is null719 *@see#addIfAbsent(Object)720 */
721 public int addAllAbsent(Collection extends E>c) {722 Object[] cs =();723 if ( == 0)724 return 0;725 Object[] uniq = newObject[];726 final ReentrantLock lock = ;727 ();728 try{729 Object[] elements =getArray();730 int len =;731 int added = 0;732 for (int i = 0; i < ; ++i) { //scan for duplicates
733 Object e =cs[i];734 if (indexOf(e, elements, 0, len) < 0 &&
735 indexOf(e, uniq, 0, added) < 0)736 uniq[added++] =e;737 }738 if (added > 0) {739 Object[] newElements = (elements, len +added);740 (uniq, 0, newElements, len, added);741 setArray(newElements);742 }743 returnadded;744 } finally{745 ();746 }747 }748
749 /**
750 * Removes all of the elements from this list.751 * The list will be empty after this call returns.752 */
753 public voidclear() {754 final ReentrantLock lock = ;755 ();756 try{757 setArray(new Object[0]);758 } finally{759 ();760 }761 }762
763 /**
764 * Appends all of the elements in the specified collection to the end765 * of this list, in the order that they are returned by the specified766 * collection's iterator.767 *768 *@paramc collection containing elements to be added to this list769 *@returntrue if this list changed as a result of the call770 *@throwsNullPointerException if the specified collection is null771 *@see#add(Object)772 */
773 public boolean addAll(Collection extends E>c) {774 Object[] cs =();775 if ( == 0)776 return false;777 final ReentrantLock lock = ;778 ();779 try{780 Object[] elements =getArray();781 int len =;782 Object[] newElements = (elements, len +);783 (cs, 0, newElements, len, );784 setArray(newElements);785 return true;786 } finally{787 ();788 }789 }790
791 /**
792 * Inserts all of the elements in the specified collection into this793 * list, starting at the specified position. Shifts the element794 * currently at that position (if any) and any subsequent elements to795 * the right (increases their indices). The new elements will appear796 * in this list in the order that they are returned by the797 * specified collection's iterator.798 *799 *@paramindex index at which to insert the first element800 * from the specified collection801 *@paramc collection containing elements to be added to this list802 *@returntrue if this list changed as a result of the call803 *@throwsIndexOutOfBoundsException {@inheritDoc}804 *@throwsNullPointerException if the specified collection is null805 *@see#add(int,Object)806 */
807 public boolean addAll(int index, Collection extends E>c) {808 Object[] cs =();809 final ReentrantLock lock = ;810 ();811 try{812 Object[] elements =getArray();813 int len =;814 if (index > len || index < 0)815 throw new IndexOutOfBoundsException("Index: "+index+
816 ", Size: "+len);817 if ( == 0)818 return false;819 int numMoved = len -index;820 Object[] newElements;821 if (numMoved == 0)822 newElements = (elements, len +);823 else{824 newElements = new Object[len +];825 (elements, 0, newElements, 0, index);826 (elements, index,827 newElements, index +,828 numMoved);829 }830 (cs, 0, newElements, index, );831 setArray(newElements);832 return true;833 } finally{834 ();835 }836 }837
838 /**
839 * Saves the state of the list to a stream (that is, serializes it).840 *841 *@serialDataThe length of the array backing the list is emitted842 * (int), followed by all of its elements (each an Object)843 * in the proper order.844 *@params the stream845 */
846 private voidwriteObject( s)847 {848
849 ();850
851 Object[] elements =getArray();852 //Write out array length
853 ();854
855 //Write out all elements in the proper order.
856 for(Object element : elements)857 (element);858 }859
860 /**
861 * Reconstitutes the list from a stream (that is, deserializes it).862 *863 *@params the stream864 */
865 private voidreadObject( s)866 , ClassNotFoundException {867
868 ();869
870 //bind to new lock
871 resetLock();872
873 //Read in array length and allocate array
874 int len =();875 Object[] elements = newObject[len];876
877 //Read in all elements in the proper order.
878 for (int i = 0; i < len; i++)879 elements[i] =();880 setArray(elements);881 }882
883 /**
884 * Returns a string representation of this list. The string885 * representation consists of the string representations of the list's886 * elements in the order they are returned by its iterator, enclosed in887 * square brackets ("[]"). Adjacent elements are separated by888 * the characters ", " (comma and space). Elements are889 * converted to strings as by {@linkString#valueOf(Object)}.890 *891 *@returna string representation of this list892 */
893 publicString toString() {894 (getArray());895 }896
897 /**
898 * Compares the specified object with this list for equality.899 * Returns {@codetrue} if the specified object is the same object900 * as this object, or if it is also a {@linkList} and the sequence901 * of elements returned by an {@linkplainList#iterator() iterator}902 * over the specified list is the same as the sequence returned by903 * an iterator over this list. The two sequences are considered to904 * be the same if they have the same length and corresponding905 * elements at the same position in the sequence are equal.906 * Two elements {@codee1} and {@codee2} are considered907 * equal if {@code(e1==null ? e2==null : (e2))}.908 *909 *@paramo the object to be compared for equality with this list910 *@return{@codetrue} if the specified object is equal to this list911 */
912 public booleanequals(Object o) {913 if (o == this)914 return true;915 if (!(o instanceofList))916 return false;917
918 List> list = (List>)(o);919 Iterator> it =();920 Object[] elements =getArray();921 int len =;922 for (int i = 0; i < len; ++i)923 if (!() || !eq(elements[i], ()))924 return false;925 if(())926 return false;927 return true;928 }929
930 /**
931 * Returns the hash code value for this list.932 *933 *
This implementation uses the definition in {@linkList#hashCode}.934 *935 *@returnthe hash code value for this list936 */
937 public inthashCode() {938 int hashCode = 1;939 Object[] elements =getArray();940 int len =;941 for (int i = 0; i < len; ++i) {942 Object obj =elements[i];943 hashCode = 31*hashCode + (obj==null ? 0: ());944 }945 returnhashCode;946 }947
948 /**
949 * Returns an iterator over the elements in this list in proper sequence.950 *951 *
The returned iterator provides a snapshot of the state of the list952 * when the iterator was constructed. No synchronization is needed while953 * traversing the iterator. The iterator does NOT support the954 * remove method.955 *956 *@returnan iterator over the elements in this list in proper sequence957 */
958 public Iteratoriterator() {959 return new COWIterator(getArray(), 0);960 }961
962 /**
963 * {@inheritDoc}964 *965 *
The returned iterator provides a snapshot of the state of the list966 * when the iterator was constructed. No synchronization is needed while967 * traversing the iterator. The iterator does NOT support the968 * remove, set or add methods.969 */
970 public ListIteratorlistIterator() {971 return new COWIterator(getArray(), 0);972 }973
974 /**
975 * {@inheritDoc}976 *977 *
The returned iterator provides a snapshot of the state of the list978 * when the iterator was constructed. No synchronization is needed while979 * traversing the iterator. The iterator does NOT support the980 * remove, set or add methods.981 *982 *@throwsIndexOutOfBoundsException {@inheritDoc}983 */
984 public ListIterator listIterator(final intindex) {985 Object[] elements =getArray();986 int len =;987 if (index<0 || index>len)988 throw new IndexOutOfBoundsException("Index: "+index);989
990 return new COWIterator(elements, index);991 }992
993 private static class COWIterator implements ListIterator{994 /**Snapshot of the array*/
995 private finalObject[] snapshot;996 /**Index of element to be returned by subsequent call to next.*/
997 private intcursor;998
999 private COWIterator(Object[] elements, intinitialCursor) {1000 cursor =initialCursor;1001 snapshot =elements;1002 }1003
1004 public booleanhasNext() {1005 return cursor
1008 public booleanhasPrevious() {1009 return cursor > 0;1010 }1011
1012 @SuppressWarnings("unchecked")1013 publicE next() {1014 if (!hasNext())1015 throw newNoSuchElementException();1016 return (E) snapshot[cursor++];1017 }1018
1019 @SuppressWarnings("unchecked")1020 publicE previous() {1021 if (!hasPrevious())1022 throw newNoSuchElementException();1023 return (E) snapshot[--cursor];1024 }1025
1026 public intnextIndex() {1027 returncursor;1028 }1029
1030 public intpreviousIndex() {1031 return cursor-1;1032 }1033
1034 /**
1035 * Not supported. Always throws UnsupportedOperationException.1036 *@throwsUnsupportedOperationException always; remove1037 * is not supported by this iterator.1038 */
1039 public voidremove() {1040 throw newUnsupportedOperationException();1041 }1042
1043 /**
1044 * Not supported. Always throws UnsupportedOperationException.1045 *@throwsUnsupportedOperationException always; set1046 * is not supported by this iterator.1047 */
1048 public voidset(E e) {1049 throw newUnsupportedOperationException();1050 }1051
1052 /**
1053 * Not supported. Always throws UnsupportedOperationException.1054 *@throwsUnsupportedOperationException always; add1055 * is not supported by this iterator.1056 */
1057 public voidadd(E e) {1058 throw newUnsupportedOperationException();1059 }1060 }1061
1062 /**
1063 * Returns a view of the portion of this list between1064 * fromIndex, inclusive, and toIndex, exclusive.1065 * The returned list is backed by this list, so changes in the1066 * returned list are reflected in this list.1067 *1068 *
The semantics of the list returned by this method become1069 * undefined if the backing list (., this list) is modified in1070 * any way other than via the returned list.1071 *1072 *@paramfromIndex low endpoint (inclusive) of the subList1073 *@paramtoIndex high endpoint (exclusive) of the subList1074 *@returna view of the specified range within this list1075 *@throwsIndexOutOfBoundsException {@inheritDoc}1076 */
1077 public List subList(int fromIndex, inttoIndex) {1078 final ReentrantLock lock = ;1079 ();1080 try{1081 Object[] elements =getArray();1082 int len =;1083 if (fromIndex < 0 || toIndex > len || fromIndex >toIndex)1084 throw newIndexOutOfBoundsException();1085 return new COWSubList(this, fromIndex, toIndex);1086 } finally{1087 ();1088 }1089 }1090
1091 /**
1092 * Sublist for CopyOnWriteArrayList.1093 * This class extends AbstractList merely for convenience, to1094 * avoid having to define addAll, etc. This doesn't hurt, but1095 * is wasteful. This class does not need or use modCount1096 * mechanics in AbstractList, but does need to check for1097 * concurrent modification using similar mechanics. On each1098 * operation, the array that we expect the backing list to use1099 * is checked and updated. Since we do this for all of the1100 * base operations invoked by those defined in AbstractList,1101 * all is well. While inefficient, this is not worth1102 * improving. The kinds of list operations inherited from1103 * AbstractList are already so slow on COW sublists that1104 * adding a bit more space/time doesn't seem even noticeable.1105 */
1106 private static class COWSubList
1107 extends AbstractList
1108 implementsRandomAccess1109 {1110 private final CopyOnWriteArrayListl;1111 private final intoffset;1112 private intsize;1113 privateObject[] expectedArray;1114
1115 //only call this holding l's lock
1116 COWSubList(CopyOnWriteArrayListlist,1117 int fromIndex, inttoIndex) {1118 l =list;1119 expectedArray =();1120 offset =fromIndex;1121 size = toIndex -fromIndex;1122 }1123
1124 //only call this holding l's lock
1125 private voidcheckForComodification() {1126 if (() !=expectedArray)1127 throw newConcurrentModificationException();1128 }1129
1130 //only call this holding l's lock
1131 private void rangeCheck(intindex) {1132 if (index<0 || index>=size)1133 throw new IndexOutOfBoundsException("Index: "+index+
1134 ",Size: "+size);1135 }1136
1137 public E set(intindex, E element) {1138 final ReentrantLock lock =;1139 ();1140 try{1141 rangeCheck(index);1142 checkForComodification();1143 E x = (index+offset, element);1144 expectedArray =();1145 returnx;1146 } finally{1147 ();1148 }1149 }1150
1151 public E get(intindex) {1152 final ReentrantLock lock =;1153 ();1154 try{1155 rangeCheck(index);1156 checkForComodification();1157 return (index+offset);1158 } finally{1159 ();1160 }1161 }1162
1163 public intsize() {1164 final ReentrantLock lock =;1165 ();1166 try{1167 checkForComodification();1168 returnsize;1169 } finally{1170 ();1171 }1172 }1173
1174 public void add(intindex, E element) {1175 final ReentrantLock lock =;1176 ();1177 try{1178 checkForComodification();1179 if (index<0 || index>size)1180 throw newIndexOutOfBoundsException();1181 (index+offset, element);1182 expectedArray =();1183 size++;1184 } finally{1185 ();1186 }1187 }1188
1189 public voidclear() {1190 final ReentrantLock lock =;1191 ();1192 try{1193 checkForComodification();1194 (offset, offset+size);1195 expectedArray =();1196 size = 0;1197 } finally{1198 ();1199 }1200 }1201
1202 public E remove(intindex) {1203 final ReentrantLock lock =;1204 ();1205 try{1206 rangeCheck(index);1207 checkForComodification();1208 E result = (index+offset);1209 expectedArray =();1210 size--;1211 returnresult;1212 } finally{1213 ();1214 }1215 }1216
1217 public booleanremove(Object o) {1218 int index =indexOf(o);1219 if (index == -1)1220 return false;1221 remove(index);1222 return true;1223 }1224
1225 public Iteratoriterator() {1226 final ReentrantLock lock =;1227 ();1228 try{1229 checkForComodification();1230 return new COWSubListIterator(l, 0, offset, size);1231 } finally{1232 ();1233 }1234 }1235
1236 public ListIterator listIterator(final intindex) {1237 final ReentrantLock lock =;1238 ();1239 try{1240 checkForComodification();1241 if (index<0 || index>size)1242 throw new IndexOutOfBoundsException("Index: "+index+
1243 ", Size: "+size);1244 return new COWSubListIterator(l, index, offset, size);1245 } finally{1246 ();1247 }1248 }1249
1250 public List subList(int fromIndex, inttoIndex) {1251 final ReentrantLock lock =;1252 ();1253 try{1254 checkForComodification();1255 if (fromIndex<0 || toIndex>size)1256 throw newIndexOutOfBoundsException();1257 return new COWSubList(l, fromIndex +offset,1258 toIndex +offset);1259 } finally{1260 ();1261 }1262 }1263
1264 }1265
1266
1267 private static class COWSubListIterator implements ListIterator{1268 private final ListIteratori;1269 private final intindex;1270 private final intoffset;1271 private final intsize;1272
1273 COWSubListIterator(List l, int index, intoffset,1274 intsize) {1275 =index;1276 =offset;1277 =size;1278 i = (index+offset);1279 }1280
1281 public booleanhasNext() {1282 return nextIndex()
1285 publicE next() {1286 if(hasNext())1287 ();1288 else
1289 throw newNoSuchElementException();1290 }1291
1292 public booleanhasPrevious() {1293 return previousIndex() >= 0;1294 }1295
1296 publicE previous() {1297 if(hasPrevious())1298 ();1299 else
1300 throw newNoSuchElementException();1301 }1302
1303 public intnextIndex() {1304 return () -offset;1305 }1306
1307 public intpreviousIndex() {1308 return () -offset;1309 }1310
1311 public voidremove() {1312 throw newUnsupportedOperationException();1313 }1314
1315 public voidset(E e) {1316 throw newUnsupportedOperationException();1317 }1318
1319 public voidadd(E e) {1320 throw newUnsupportedOperationException();1321 }1322 }1323
1324 //Support for resetting lock while deserializing
1325 private voidresetLock() {1326 (this, lockOffset, newReentrantLock());1327 }1328 private static UNSAFE;1329 private static final longlockOffset;1330 static{1331 try{1332 UNSAFE =();1333 Class k = ;1334 lockOffset =UNSAFE.objectFieldOffset1335 (("lock"));1336 } catch(Exception e) {1337 throw newError(e);1338 }1339 }1340 }