1 /* CopyOnWriteArrayList.java
2 Copyright (C) 2006 Free Software Foundation
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
38 package java
.util
.concurrent
;
40 import java
.io
.IOException
;
41 import java
.io
.ObjectInputStream
;
42 import java
.io
.ObjectOutputStream
;
43 import java
.io
.Serializable
;
45 import java
.lang
.reflect
.Array
;
47 import java
.util
.AbstractList
;
48 import java
.util
.Arrays
;
49 import java
.util
.Collection
;
50 import java
.util
.ConcurrentModificationException
;
51 import java
.util
.Iterator
;
52 import java
.util
.List
;
53 import java
.util
.ListIterator
;
54 import java
.util
.NoSuchElementException
;
55 import java
.util
.RandomAccess
;
58 * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is
59 * as special ArrayList which performs copies of the underlying storage
60 * each time a write (<code>remove</code>, <code>add</code> etc..) operation
63 * The update operation in this class run usually in <code>O(n)</code> or worse,
64 * but traversal operations are fast and efficient, especially when running in
65 * a multi-thread environment without the need to design complex synchronize
68 * <code>Iterator</code>s in this class work on a snapshot of the backing store
69 * at the moment the iterator itself was created, hence the iterator will not
70 * reflect changes in the underlying storage. Thus, update operation on the
71 * <code>Iterator</code>s are not supported, but as interferences from other
72 * threads are impossible, no <code>ConcurrentModificationException</code>
73 * will be ever thrown from within the <code>Iterator</code>.
75 * This class is especially useful when used with event handling, like the
76 * following code demonstrates:<br />
79 * CopyOnWriteArrayList<EventListener> listeners =
80 * new CopyOnWriteArrayList<EventListener>();
84 * for (final EventListener listener : listeners)
86 * Runnable dispatcher = new Runnable() {
89 * listener.preferenceChange(event);
93 * Executor executor = Executors.newSingleThreadExecutor();
94 * executor.execute(dispatcher);
100 public class CopyOnWriteArrayList
<E
>
101 implements List
<E
>, RandomAccess
, Cloneable
, Serializable
106 private static final long serialVersionUID
= 8673264195747942595L;
109 * Where the data is stored.
111 private transient E
[] data
;
114 * Construct a new ArrayList with the default capacity (16).
116 public CopyOnWriteArrayList()
118 data
= (E
[]) new Object
[0];
122 * Construct a new ArrayList, and initialize it with the elements in the
123 * supplied Collection. The initial capacity is 110% of the Collection's size.
126 * the collection whose elements will initialize this list
127 * @throws NullPointerException
130 public CopyOnWriteArrayList(Collection
< ?
extends E
> c
)
132 // FIXME ... correct? use c.toArray()
133 data
= (E
[]) new Object
[c
.size()];
136 data
[index
++] = value
;
140 * Construct a new ArrayList, and initialize it with the elements in the
144 * the array used to initialize this list
145 * @throws NullPointerException
148 public CopyOnWriteArrayList(E
[] array
)
150 data
= (E
[]) array
.clone();
154 * Returns the number of elements in this list.
156 * @return the list size
164 * Checks if the list is empty.
166 * @return true if there are no elements
168 public boolean isEmpty()
170 return data
.length
== 0;
174 * Returns true if element is in this ArrayList.
177 * the element whose inclusion in the List is being tested
178 * @return true if the list contains e
180 public boolean contains(Object e
)
182 return indexOf(e
) != -1;
186 * Tests whether this collection contains all the elements in a given
187 * collection. This implementation iterates over the given collection,
188 * testing whether each element is contained in this collection. If any one
189 * is not, false is returned. Otherwise true is returned.
191 * @param c the collection to test against
192 * @return true if this collection contains all the elements in the given
194 * @throws NullPointerException if the given collection is null
195 * @see #contains(Object)
197 public boolean containsAll(Collection
<?
> c
)
199 Iterator
<?
> itr
= c
.iterator();
202 if (!contains(itr
.next()))
208 * Returns the lowest index at which element appears in this List, or -1 if it
212 * the element whose inclusion in the List is being tested
213 * @return the index where e was found
215 public int indexOf(Object e
)
217 E
[] data
= this.data
;
218 for (int i
= 0; i
< data
.length
; i
++)
219 if (equals(e
, data
[i
]))
225 * Return the lowest index greater equal <code>index</code> at which
226 * <code>e</code> appears in this List, or -1 if it does not
229 * @param e the element whose inclusion in the list is being tested
230 * @param index the index at which the search begins
231 * @return the index where <code>e</code> was found
233 public int indexOf(E e
, int index
)
235 E
[] data
= this.data
;
237 for (int i
= index
; i
< data
.length
; i
++)
238 if (equals(e
, data
[i
]))
244 * Returns the highest index at which element appears in this List, or -1 if
245 * it does not appear.
248 * the element whose inclusion in the List is being tested
249 * @return the index where e was found
251 public int lastIndexOf(Object e
)
253 E
[] data
= this.data
;
254 for (int i
= data
.length
- 1; i
>= 0; i
--)
255 if (equals(e
, data
[i
]))
261 * Returns the highest index lesser equal <code>index</code> at
262 * which <code>e</code> appears in this List, or -1 if it does not
265 * @param e the element whose inclusion in the list is being tested
266 * @param index the index at which the search begins
267 * @return the index where <code>e</code> was found
269 public int lastIndexOf(E e
, int index
)
271 E
[] data
= this.data
;
273 for (int i
= index
; i
>= 0; i
--)
274 if (equals(e
, data
[i
]))
280 * Creates a shallow copy of this ArrayList (elements are not cloned).
282 * @return the cloned object
284 public Object
clone()
286 CopyOnWriteArrayList
<E
> clone
= null;
289 clone
= (CopyOnWriteArrayList
<E
>) super.clone();
291 catch (CloneNotSupportedException e
)
293 // Impossible to get here.
299 * Returns an Object array containing all of the elements in this ArrayList.
300 * The array is independent of this list.
302 * @return an array representation of this list
304 public Object
[] toArray()
306 E
[] data
= this.data
;
307 E
[] array
= (E
[]) new Object
[data
.length
];
308 System
.arraycopy(data
, 0, array
, 0, data
.length
);
313 * Returns an Array whose component type is the runtime component type of the
314 * passed-in Array. The returned Array is populated with all of the elements
315 * in this ArrayList. If the passed-in Array is not large enough to store all
316 * of the elements in this List, a new Array will be created and returned; if
317 * the passed-in Array is <i>larger</i> than the size of this List, then
318 * size() index will be set to null.
321 * the passed-in Array
322 * @return an array representation of this list
323 * @throws ArrayStoreException
324 * if the runtime type of a does not allow an element in this list
325 * @throws NullPointerException
328 public <T
> T
[] toArray(T
[] a
)
330 E
[] data
= this.data
;
331 if (a
.length
< data
.length
)
332 a
= (T
[]) Array
.newInstance(a
.getClass().getComponentType(), data
.length
);
333 else if (a
.length
> data
.length
)
334 a
[data
.length
] = null;
335 System
.arraycopy(data
, 0, a
, 0, data
.length
);
340 * Retrieves the element at the user-supplied index.
343 * the index of the element we are fetching
344 * @throws IndexOutOfBoundsException
345 * if index < 0 || index >= size()
347 public E
get(int index
)
353 * Sets the element at the specified index. The new element, e, can be an
354 * object of any type or null.
357 * the index at which the element is being set
359 * the element to be set
360 * @return the element previously at the specified index
361 * @throws IndexOutOfBoundsException
362 * if index < 0 || index >= 0
364 public synchronized E
set(int index
, E e
)
366 E result
= data
[index
];
367 E
[] newData
= (E
[]) data
.clone();
374 * Appends the supplied element to the end of this list. The element, e, can
375 * be an object of any type or null.
378 * the element to be appended to this list
379 * @return true, the add will always succeed
381 public synchronized boolean add(E e
)
383 E
[] data
= this.data
;
384 E
[] newData
= (E
[]) new Object
[data
.length
+ 1];
385 System
.arraycopy(data
, 0, newData
, 0, data
.length
);
386 newData
[data
.length
] = e
;
392 * Adds the supplied element at the specified index, shifting all elements
393 * currently at that index or higher one to the right. The element, e, can be
394 * an object of any type or null.
397 * the index at which the element is being added
399 * the item being added
400 * @throws IndexOutOfBoundsException
401 * if index < 0 || index > size()
403 public synchronized void add(int index
, E e
)
405 E
[] data
= this.data
;
406 E
[] newData
= (E
[]) new Object
[data
.length
+ 1];
407 System
.arraycopy(data
, 0, newData
, 0, index
);
409 System
.arraycopy(data
, index
, newData
, index
+ 1, data
.length
- index
);
414 * Removes the element at the user-supplied index.
417 * the index of the element to be removed
418 * @return the removed Object
419 * @throws IndexOutOfBoundsException
420 * if index < 0 || index >= size()
422 public synchronized E
remove(int index
)
424 if (index
< 0 || index
>= this.size())
425 throw new IndexOutOfBoundsException("index = " + index
);
427 E
[] snapshot
= this.data
;
428 E
[] newData
= (E
[]) new Object
[snapshot
.length
- 1];
430 E result
= snapshot
[index
];
433 System
.arraycopy(snapshot
, 0, newData
, 0, index
);
435 System
.arraycopy(snapshot
, index
+ 1, newData
, index
,
436 snapshot
.length
- index
- 1);
444 * Remove the first occurrence, if any, of the given object from this list,
445 * returning <code>true</code> if the object was removed, <code>false</code>
448 * @param element the object to be removed.
449 * @return true if element was removed, false otherwise. false means also that
450 * the underlying storage was unchanged after this operation concluded.
452 public synchronized boolean remove(Object element
)
454 E
[] snapshot
= this.data
;
455 int len
= snapshot
.length
;
460 E
[] newData
= (E
[]) new Object
[len
- 1];
462 // search the element to remove while filling the backup array
463 // this way we can run this method in O(n)
464 int elementIndex
= -1;
465 for (int i
= 0; i
< snapshot
.length
; i
++)
467 if (equals(element
, snapshot
[i
]))
473 if (i
< newData
.length
)
474 newData
[i
] = snapshot
[i
];
477 if (elementIndex
< 0)
480 System
.arraycopy(snapshot
, elementIndex
+ 1, newData
, elementIndex
,
481 snapshot
.length
- elementIndex
- 1);
488 * Removes all the elements contained in the given collection.
489 * This method removes the elements that are contained in both
490 * this list and in the given collection.
492 * @param c the collection containing the elements to be removed from this
494 * @return true if at least one element was removed, indicating that
495 * the list internal storage changed as a result, false otherwise.
497 public synchronized boolean removeAll(Collection
<?
> c
)
502 E
[] snapshot
= this.data
;
503 E
[] storage
= (E
[]) new Object
[this.data
.length
];
504 boolean changed
= false;
507 for (E element
: snapshot
)
509 // copy all the elements, including null values
510 // if the collection can hold it
511 // FIXME: slow operation
512 if (c
.contains(element
))
515 storage
[length
++] = element
;
521 E
[] newData
= (E
[]) new Object
[length
];
522 System
.arraycopy(storage
, 0, newData
, 0, length
);
530 * Removes all the elements that are not in the passed collection.
531 * If the collection is void, this method has the same effect of
532 * <code>clear()</code>.
533 * Please, note that this method is extremely slow (unless the argument has
534 * <code>size == 0</code>) and has bad performance is both space and time
537 * @param c the collection containing the elements to be retained by this
539 * @return true the list internal storage changed as a result of this
540 * operation, false otherwise.
542 public synchronized boolean retainAll(Collection
<?
> c
)
544 // if the given collection does not contain elements
545 // we remove all the elements from our storage
552 E
[] snapshot
= this.data
;
553 E
[] storage
= (E
[]) new Object
[this.data
.length
];
556 for (E element
: snapshot
)
558 if (c
.contains(element
))
559 storage
[length
++] = element
;
562 // means we retained all the elements previously in our storage
563 // we are running already slow here, but at least we avoid copying
564 // another array and changing the internal storage
565 if (length
== snapshot
.length
)
568 E
[] newData
= (E
[]) new Object
[length
];
569 System
.arraycopy(storage
, 0, newData
, 0, length
);
577 * Removes all elements from this List
579 public synchronized void clear()
581 data
= (E
[]) new Object
[0];
585 * Add each element in the supplied Collection to this List. It is undefined
586 * what happens if you modify the list while this is taking place; for
587 * example, if the collection contains this list. c can contain objects of any
588 * type, as well as null values.
591 * a Collection containing elements to be added to this List
592 * @return true if the list was modified, in other words c is not empty
593 * @throws NullPointerException
596 public synchronized boolean addAll(Collection
< ?
extends E
> c
)
598 return addAll(data
.length
, c
);
602 * Add all elements in the supplied collection, inserting them beginning at
603 * the specified index. c can contain objects of any type, as well as null
607 * the index at which the elements will be inserted
609 * the Collection containing the elements to be inserted
610 * @throws IndexOutOfBoundsException
611 * if index < 0 || index > 0
612 * @throws NullPointerException
615 public synchronized boolean addAll(int index
, Collection
< ?
extends E
> c
)
617 if (index
< 0 || index
> this.size())
618 throw new IndexOutOfBoundsException("index = " + index
);
620 int csize
= c
.size();
624 E
[] data
= this.data
;
625 Iterator
<?
extends E
> itr
= c
.iterator();
627 E
[] newData
= (E
[]) new Object
[data
.length
+ csize
];
629 // avoid this call at all if we were asked to put the elements at the
630 // beginning of our storage
632 System
.arraycopy(data
, 0, newData
, 0, index
);
634 int itemsLeft
= index
;
637 newData
[index
++] = value
;
639 // now copy the remaining elements
640 System
.arraycopy(data
, itemsLeft
, newData
, 0, data
.length
- itemsLeft
);
648 * Adds an element if the list does not contains it already.
650 * @param val the element to add to the list.
651 * @return true if the element was added, false otherwise.
653 public synchronized boolean addIfAbsent(E val
)
662 * Adds all the element from the given collection that are not already
665 * @param c the Collection containing the elements to be inserted
666 * @return true the list internal storage changed as a result of this
667 * operation, false otherwise.
669 public synchronized int addAllAbsent(Collection
<?
extends E
> c
)
675 E
[] snapshot
= this.data
;
676 E
[] storage
= (E
[]) new Object
[size
];
681 if (!this.contains(val
))
682 storage
[size
++] = val
;
688 // append storage to data
689 E
[] newData
= (E
[]) new Object
[snapshot
.length
+ size
];
691 System
.arraycopy(snapshot
, 0, newData
, 0, snapshot
.length
);
692 System
.arraycopy(storage
, 0, newData
, snapshot
.length
, size
);
699 public String
toString()
701 return Arrays
.toString(this.data
);
704 public boolean equals(Object o
)
712 // let's see if 'o' is a list, if so, we need to compare the elements
713 // as returned by the iterator
714 if (o
instanceof List
)
716 List
<?
> source
= (List
<?
>) o
;
718 if (source
.size() != this.size())
721 Iterator
<?
> sourceIterator
= source
.iterator();
722 for (E element
: this)
724 if (!element
.equals(sourceIterator
.next()))
734 public int hashCode()
736 // see http://java.sun.com/6/docs/api/java/util/List.html#hashcode()
738 for (E element
: this)
740 hashcode
= 31 * hashcode
+ (element
== null ?
0 : element
.hashCode());
746 * Return an Iterator containing the elements of this list.
747 * The Iterator uses a snapshot of the state of the internal storage
748 * at the moment this method is called and does <strong>not</strong> support
749 * update operations, so no synchronization is needed to traverse the
752 * @return an Iterator containing the elements of this list in sequence.
754 public Iterator
<E
> iterator()
756 return new Iterator
<E
>()
758 E
[] iteratorData
= CopyOnWriteArrayList
.this.data
;
759 int currentElement
= 0;
761 public boolean hasNext()
763 return (currentElement
< iteratorData
.length
);
768 return iteratorData
[currentElement
++];
773 throw new UnsupportedOperationException("updating of elements in " +
774 "iterators is not supported " +
781 * Return a ListIterator containing the elements of this list.
782 * The Iterator uses a snapshot of the state of the internal storage
783 * at the moment this method is called and does <strong>not</strong> support
784 * update operations, so no synchronization is needed to traverse the
787 * @return a ListIterator containing the elements of this list in sequence.
789 public ListIterator
<E
> listIterator()
791 return listIterator(0);
795 * Return a ListIterator over the elements of this list starting at
796 * the specified index. An initial call to {@code next()} will thus
797 * return the element at {@code index}, while an initial call to
798 * {@code previous()} will return the element at {@code index-1}. The
799 * Iterator uses a snapshot of the state of the internal storage
800 * at the moment this method is called and does <strong>not</strong> support
801 * update operations, so no synchronization is needed to traverse the
804 * @param index the index at which to start iterating.
805 * @return a ListIterator containing the elements of this list in sequence.
807 public ListIterator
<E
> listIterator(final int index
)
809 if (index
< 0 || index
> size())
810 throw new IndexOutOfBoundsException("Index: " + index
+ ", Size:"
813 return new ListIterator
<E
>()
815 E
[] iteratorData
= CopyOnWriteArrayList
.this.data
;
816 int currentElement
= index
;
820 throw new UnsupportedOperationException("updating of elements in " +
821 "iterators is not supported " +
825 public boolean hasNext()
827 return (currentElement
< iteratorData
.length
);
830 public boolean hasPrevious()
832 return (currentElement
> 0);
837 if (hasNext() == false)
838 throw new java
.util
.NoSuchElementException();
840 return iteratorData
[currentElement
++];
843 public int nextIndex()
845 return (currentElement
+ 1);
850 if (hasPrevious() == false)
851 throw new java
.util
.NoSuchElementException();
853 return iteratorData
[--currentElement
];
856 public int previousIndex()
858 return (currentElement
- 1);
863 throw new UnsupportedOperationException("updating of elements in " +
864 "iterators is not supported " +
870 throw new UnsupportedOperationException("updating of elements in " +
871 "iterators is not supported " +
879 * Obtain a List view of a subsection of this list, from fromIndex
880 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
881 * sublist is empty. The returned list should be modifiable if and only
882 * if this list is modifiable. Changes to the returned list should be
883 * reflected in this list. If this list is structurally modified in
884 * any way other than through the returned list, the result of any subsequent
885 * operations on the returned list is undefined.
888 * This implementation returns a subclass of AbstractList. It stores, in
889 * private fields, the offset and size of the sublist, and the expected
890 * modCount of the backing list. If the backing list implements RandomAccess,
891 * the sublist will also.
894 * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
895 * <code>add(int, Object)</code>, <code>remove(int)</code>,
896 * <code>addAll(int, Collection)</code> and
897 * <code>removeRange(int, int)</code> methods all delegate to the
898 * corresponding methods on the backing abstract list, after
899 * bounds-checking the index and adjusting for the offset. The
900 * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
901 * The <code>listIterator(int)</code> method returns a "wrapper object"
902 * over a list iterator on the backing list, which is created with the
903 * corresponding method on the backing list. The <code>iterator()</code>
904 * method merely returns listIterator(), and the <code>size()</code> method
905 * merely returns the subclass's size field.
908 * All methods first check to see if the actual modCount of the backing
909 * list is equal to its expected value, and throw a
910 * ConcurrentModificationException if it is not.
912 * @param fromIndex the index that the returned list should start from
914 * @param toIndex the index that the returned list should go to (exclusive)
915 * @return a List backed by a subsection of this list
916 * @throws IndexOutOfBoundsException if fromIndex < 0
917 * || toIndex > size()
918 * @throws IndexOutOfBoundsException if fromIndex > toIndex
919 * @see ConcurrentModificationException
922 public synchronized List
<E
> subList(int fromIndex
, int toIndex
)
924 // This follows the specification of AbstractList, but is inconsistent
925 // with the one in List. Don't you love Sun's inconsistencies?
926 if (fromIndex
> toIndex
)
927 throw new IndexOutOfBoundsException(fromIndex
+ " > " + toIndex
);
928 if (fromIndex
< 0 || toIndex
> size())
929 throw new IndexOutOfBoundsException();
931 if (this instanceof RandomAccess
)
932 return new RandomAccessSubList
<E
>(this, fromIndex
, toIndex
);
933 return new SubList
<E
>(this, fromIndex
, toIndex
);
937 * This class follows the implementation requirements set forth in
938 * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
939 * by using a non-public top-level class in the same package.
941 * @author Original author unknown
942 * @author Eric Blake (ebb9@email.byu.edu)
944 private static class SubList
<E
>
945 extends AbstractList
<E
>
947 // Package visible, for use by iterator.
948 /** The original list. */
949 final CopyOnWriteArrayList
<E
> backingList
;
950 /** The index of the first element of the sublist. */
952 /** The size of the sublist. */
954 /** The backing data */
958 * Construct the sublist.
960 * @param backing the list this comes from
961 * @param fromIndex the lower bound, inclusive
962 * @param toIndex the upper bound, exclusive
964 SubList(CopyOnWriteArrayList
<E
> backing
, int fromIndex
, int toIndex
)
966 backingList
= backing
;
969 size
= toIndex
- fromIndex
;
973 * This method checks the two modCount fields to ensure that there has
974 * not been a concurrent modification, returning if all is okay.
976 * @throws ConcurrentModificationException if the backing list has been
977 * modified externally to this sublist
979 // This can be inlined. Package visible, for use by iterator.
982 if (data
!= backingList
.data
)
983 throw new ConcurrentModificationException();
987 * This method checks that a value is between 0 and size (inclusive). If
988 * it is not, an exception is thrown.
990 * @param index the value to check
991 * @throws IndexOutOfBoundsException if index < 0 || index > size()
993 // This will get inlined, since it is private.
994 private void checkBoundsInclusive(int index
)
996 if (index
< 0 || index
> size
)
997 throw new IndexOutOfBoundsException("Index: " + index
+
1002 * This method checks that a value is between 0 (inclusive) and size
1003 * (exclusive). If it is not, an exception is thrown.
1005 * @param index the value to check
1006 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1008 // This will get inlined, since it is private.
1009 private void checkBoundsExclusive(int index
)
1011 if (index
< 0 || index
>= size
)
1012 throw new IndexOutOfBoundsException("Index: " + index
+
1017 * Specified by AbstractList.subList to return the private field size.
1019 * @return the sublist size
1020 * @throws ConcurrentModificationException if the backing list has been
1021 * modified externally to this sublist
1025 synchronized (backingList
)
1034 synchronized (backingList
)
1036 E
[] snapshot
= backingList
.data
;
1037 E
[] newData
= (E
[]) new Object
[snapshot
.length
- size
];
1039 int toIndex
= size
+ offset
;
1041 System
.arraycopy(snapshot
, 0, newData
, 0, offset
);
1042 System
.arraycopy(snapshot
, toIndex
, newData
, offset
,
1043 snapshot
.length
- toIndex
);
1045 backingList
.data
= newData
;
1046 this.data
= backingList
.data
;
1052 * Specified by AbstractList.subList to delegate to the backing list.
1054 * @param index the location to modify
1055 * @param o the new value
1056 * @return the old value
1057 * @throws ConcurrentModificationException if the backing list has been
1058 * modified externally to this sublist
1059 * @throws UnsupportedOperationException if the backing list does not
1060 * support the set operation
1061 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1062 * @throws ClassCastException if o cannot be added to the backing list due
1064 * @throws IllegalArgumentException if o cannot be added to the backing list
1065 * for some other reason
1067 public E
set(int index
, E o
)
1069 synchronized (backingList
)
1072 checkBoundsExclusive(index
);
1074 E el
= backingList
.set(index
+ offset
, o
);
1075 this.data
= backingList
.data
;
1082 * Specified by AbstractList.subList to delegate to the backing list.
1084 * @param index the location to get from
1085 * @return the object at that location
1086 * @throws ConcurrentModificationException if the backing list has been
1087 * modified externally to this sublist
1088 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1090 public E
get(int index
)
1092 synchronized (backingList
)
1095 checkBoundsExclusive(index
);
1097 return backingList
.get(index
+ offset
);
1102 * Specified by AbstractList.subList to delegate to the backing list.
1104 * @param index the index to insert at
1105 * @param o the object to add
1106 * @throws ConcurrentModificationException if the backing list has been
1107 * modified externally to this sublist
1108 * @throws IndexOutOfBoundsException if index < 0 || index > size()
1109 * @throws UnsupportedOperationException if the backing list does not
1110 * support the add operation.
1111 * @throws ClassCastException if o cannot be added to the backing list due
1113 * @throws IllegalArgumentException if o cannot be added to the backing
1114 * list for some other reason.
1116 public void add(int index
, E o
)
1118 synchronized (backingList
)
1121 checkBoundsInclusive(index
);
1123 backingList
.add(index
+ offset
, o
);
1125 this.data
= backingList
.data
;
1131 * Specified by AbstractList.subList to delegate to the backing list.
1133 * @param index the index to remove
1134 * @return the removed object
1135 * @throws ConcurrentModificationException if the backing list has been
1136 * modified externally to this sublist
1137 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1138 * @throws UnsupportedOperationException if the backing list does not
1139 * support the remove operation
1141 public E
remove(int index
)
1143 synchronized (backingList
)
1146 checkBoundsExclusive(index
);
1147 E o
= backingList
.remove(index
+ offset
);
1149 this.data
= backingList
.data
;
1157 * Specified by AbstractList.subList to delegate to the backing list.
1159 * @param index the location to insert at
1160 * @param c the collection to insert
1161 * @return true if this list was modified, in other words, c is non-empty
1162 * @throws ConcurrentModificationException if the backing list has been
1163 * modified externally to this sublist
1164 * @throws IndexOutOfBoundsException if index < 0 || index > size()
1165 * @throws UnsupportedOperationException if this list does not support the
1167 * @throws ClassCastException if some element of c cannot be added to this
1168 * list due to its type
1169 * @throws IllegalArgumentException if some element of c cannot be added
1170 * to this list for some other reason
1171 * @throws NullPointerException if the specified collection is null
1173 public boolean addAll(int index
, Collection
<?
extends E
> c
)
1175 synchronized (backingList
)
1178 checkBoundsInclusive(index
);
1179 int csize
= c
.size();
1180 boolean result
= backingList
.addAll(offset
+ index
, c
);
1182 this.data
= backingList
.data
;
1190 * Specified by AbstractList.subList to return addAll(size, c).
1192 * @param c the collection to insert
1193 * @return true if this list was modified, in other words, c is non-empty
1194 * @throws ConcurrentModificationException if the backing list has been
1195 * modified externally to this sublist
1196 * @throws UnsupportedOperationException if this list does not support the
1198 * @throws ClassCastException if some element of c cannot be added to this
1199 * list due to its type
1200 * @throws IllegalArgumentException if some element of c cannot be added
1201 * to this list for some other reason
1202 * @throws NullPointerException if the specified collection is null
1204 public boolean addAll(Collection
<?
extends E
> c
)
1206 synchronized (backingList
)
1208 return addAll(size
, c
);
1213 * Specified by AbstractList.subList to return listIterator().
1215 * @return an iterator over the sublist
1217 public Iterator
<E
> iterator()
1219 return listIterator();
1223 * Specified by AbstractList.subList to return a wrapper around the
1224 * backing list's iterator.
1226 * @param index the start location of the iterator
1227 * @return a list iterator over the sublist
1228 * @throws ConcurrentModificationException if the backing list has been
1229 * modified externally to this sublist
1230 * @throws IndexOutOfBoundsException if the value is out of range
1232 public ListIterator
<E
> listIterator(final int index
)
1235 checkBoundsInclusive(index
);
1237 return new ListIterator
<E
>()
1239 private final ListIterator
<E
> i
=
1240 backingList
.listIterator(index
+ offset
);
1241 private int position
= index
;
1244 * Tests to see if there are any more objects to
1247 * @return True if the end of the list has not yet been
1250 public boolean hasNext()
1252 return position
< size
;
1256 * Tests to see if there are objects prior to the
1257 * current position in the list.
1259 * @return True if objects exist prior to the current
1260 * position of the iterator.
1262 public boolean hasPrevious()
1264 return position
> 0;
1268 * Retrieves the next object from the list.
1270 * @return The next object.
1271 * @throws NoSuchElementException if there are no
1272 * more objects to retrieve.
1273 * @throws ConcurrentModificationException if the
1274 * list has been modified elsewhere.
1278 if (position
== size
)
1279 throw new NoSuchElementException();
1285 * Retrieves the previous object from the list.
1287 * @return The next object.
1288 * @throws NoSuchElementException if there are no
1289 * previous objects to retrieve.
1290 * @throws ConcurrentModificationException if the
1291 * list has been modified elsewhere.
1296 throw new NoSuchElementException();
1298 return i
.previous();
1302 * Returns the index of the next element in the
1303 * list, which will be retrieved by <code>next()</code>
1305 * @return The index of the next element.
1307 public int nextIndex()
1309 return i
.nextIndex() - offset
;
1313 * Returns the index of the previous element in the
1314 * list, which will be retrieved by <code>previous()</code>
1316 * @return The index of the previous element.
1318 public int previousIndex()
1320 return i
.previousIndex() - offset
;
1324 * Removes the last object retrieved by <code>next()</code>
1325 * from the list, if the list supports object removal.
1327 * @throws IllegalStateException if the iterator is positioned
1328 * before the start of the list or the last object has already
1330 * @throws UnsupportedOperationException if the list does
1331 * not support removing elements.
1333 public void remove()
1335 throw new UnsupportedOperationException("Modification not supported " +
1336 "on CopyOnWriteArrayList iterators");
1340 * Replaces the last object retrieved by <code>next()</code>
1341 * or <code>previous</code> with o, if the list supports object
1342 * replacement and an add or remove operation has not already
1345 * @throws IllegalStateException if the iterator is positioned
1346 * before the start of the list or the last object has already
1348 * @throws UnsupportedOperationException if the list doesn't support
1349 * the addition or removal of elements.
1350 * @throws ClassCastException if the type of o is not a valid type
1352 * @throws IllegalArgumentException if something else related to o
1353 * prevents its addition.
1354 * @throws ConcurrentModificationException if the list
1355 * has been modified elsewhere.
1357 public void set(E o
)
1359 throw new UnsupportedOperationException("Modification not supported " +
1360 "on CopyOnWriteArrayList iterators");
1364 * Adds the supplied object before the element that would be returned
1365 * by a call to <code>next()</code>, if the list supports addition.
1367 * @param o The object to add to the list.
1368 * @throws UnsupportedOperationException if the list doesn't support
1369 * the addition of new elements.
1370 * @throws ClassCastException if the type of o is not a valid type
1372 * @throws IllegalArgumentException if something else related to o
1373 * prevents its addition.
1374 * @throws ConcurrentModificationException if the list
1375 * has been modified elsewhere.
1377 public void add(E o
)
1379 throw new UnsupportedOperationException("Modification not supported " +
1380 "on CopyOnWriteArrayList iterators");
1387 * This class is a RandomAccess version of SubList, as required by
1388 * {@link AbstractList#subList(int, int)}.
1390 * @author Eric Blake (ebb9@email.byu.edu)
1392 private static final class RandomAccessSubList
<E
> extends SubList
<E
>
1393 implements RandomAccess
1396 * Construct the sublist.
1398 * @param backing the list this comes from
1399 * @param fromIndex the lower bound, inclusive
1400 * @param toIndex the upper bound, exclusive
1402 RandomAccessSubList(CopyOnWriteArrayList
<E
> backing
, int fromIndex
, int toIndex
)
1404 super(backing
, fromIndex
, toIndex
);
1406 } // class RandomAccessSubList
1409 * Serializes this object to the given stream.
1412 * the stream to write to
1413 * @throws IOException
1414 * if the underlying stream fails
1415 * @serialData the size field (int), the length of the backing array (int),
1416 * followed by its elements (Objects) in proper order.
1418 private void writeObject(ObjectOutputStream s
) throws IOException
1420 // The 'size' field.
1421 s
.defaultWriteObject();
1422 // We serialize unused list entries to preserve capacity.
1423 int len
= data
.length
;
1425 // it would be more efficient to just write "size" items,
1426 // this need readObject read "size" items too.
1427 for (int i
= 0; i
< data
.length
; i
++)
1428 s
.writeObject(data
[i
]);
1432 * Deserializes this object from the given stream.
1435 * the stream to read from
1436 * @throws ClassNotFoundException
1437 * if the underlying stream fails
1438 * @throws IOException
1439 * if the underlying stream fails
1440 * @serialData the size field (int), the length of the backing array (int),
1441 * followed by its elements (Objects) in proper order.
1443 private void readObject(ObjectInputStream s
) throws IOException
,
1444 ClassNotFoundException
1446 // the `size' field.
1447 s
.defaultReadObject();
1448 int capacity
= s
.readInt();
1449 data
= (E
[]) new Object
[capacity
];
1450 for (int i
= 0; i
< capacity
; i
++)
1451 data
[i
] = (E
) s
.readObject();
1454 static final boolean equals(Object o1
, Object o2
)
1456 return o1
== null ? o2
== null : o1
.equals(o2
);