001 /* CopyOnWriteArrayList.java
002 Copyright (C) 2006 Free Software Foundation
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038 package java.util.concurrent;
039
040 import java.io.IOException;
041 import java.io.ObjectInputStream;
042 import java.io.ObjectOutputStream;
043 import java.io.Serializable;
044
045 import java.lang.reflect.Array;
046
047 import java.util.AbstractList;
048 import java.util.Arrays;
049 import java.util.Collection;
050 import java.util.ConcurrentModificationException;
051 import java.util.Iterator;
052 import java.util.List;
053 import java.util.ListIterator;
054 import java.util.NoSuchElementException;
055 import java.util.RandomAccess;
056
057 /**
058 * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is
059 * as special ArrayList which performs copies of the underlying storage
060 * each time a write (<code>remove</code>, <code>add</code> etc..) operation
061 * is performed.<br />
062 * <br />
063 * The update operation in this class run usually in <code>O(n)</code> or worse,
064 * but traversal operations are fast and efficient, especially when running in
065 * a multi-thread environment without the need to design complex synchronize
066 * mechanisms.<br />
067 * <br />
068 * <code>Iterator</code>s in this class work on a snapshot of the backing store
069 * at the moment the iterator itself was created, hence the iterator will not
070 * reflect changes in the underlying storage. Thus, update operation on the
071 * <code>Iterator</code>s are not supported, but as interferences from other
072 * threads are impossible, no <code>ConcurrentModificationException</code>
073 * will be ever thrown from within the <code>Iterator</code>.
074 * <br /><br />
075 * This class is especially useful when used with event handling, like the
076 * following code demonstrates:<br />
077 * <code><pre>
078 *
079 * CopyOnWriteArrayList<EventListener> listeners =
080 * new CopyOnWriteArrayList<EventListener>();
081 *
082 * [...]
083 *
084 * for (final EventListener listener : listeners)
085 * {
086 * Runnable dispatcher = new Runnable() {
087 * public void run()
088 * {
089 * listener.preferenceChange(event);
090 * }
091 * };
092 *
093 * Executor executor = Executors.newSingleThreadExecutor();
094 * executor.execute(dispatcher);
095 * }
096 * </pre></code>
097 *
098 * @since 1.5
099 */
100 public class CopyOnWriteArrayList<E>
101 implements List<E>, RandomAccess, Cloneable, Serializable
102 {
103 /**
104 *
105 */
106 private static final long serialVersionUID = 8673264195747942595L;
107
108 /**
109 * Where the data is stored.
110 */
111 private transient E[] data;
112
113 /**
114 * Construct a new ArrayList with the default capacity (16).
115 */
116 public CopyOnWriteArrayList()
117 {
118 data = (E[]) new Object[0];
119 }
120
121 /**
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.
124 *
125 * @param c
126 * the collection whose elements will initialize this list
127 * @throws NullPointerException
128 * if c is null
129 */
130 public CopyOnWriteArrayList(Collection< ? extends E> c)
131 {
132 // FIXME ... correct? use c.toArray()
133 data = (E[]) new Object[c.size()];
134 int index = 0;
135 for (E value : c)
136 data[index++] = value;
137 }
138
139 /**
140 * Construct a new ArrayList, and initialize it with the elements in the
141 * supplied array.
142 *
143 * @param array
144 * the array used to initialize this list
145 * @throws NullPointerException
146 * if array is null
147 */
148 public CopyOnWriteArrayList(E[] array)
149 {
150 data = (E[]) array.clone();
151 }
152
153 /**
154 * Returns the number of elements in this list.
155 *
156 * @return the list size
157 */
158 public int size()
159 {
160 return data.length;
161 }
162
163 /**
164 * Checks if the list is empty.
165 *
166 * @return true if there are no elements
167 */
168 public boolean isEmpty()
169 {
170 return data.length == 0;
171 }
172
173 /**
174 * Returns true if element is in this ArrayList.
175 *
176 * @param e
177 * the element whose inclusion in the List is being tested
178 * @return true if the list contains e
179 */
180 public boolean contains(Object e)
181 {
182 return indexOf(e) != -1;
183 }
184
185 /**
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.
190 *
191 * @param c the collection to test against
192 * @return true if this collection contains all the elements in the given
193 * collection
194 * @throws NullPointerException if the given collection is null
195 * @see #contains(Object)
196 */
197 public boolean containsAll(Collection<?> c)
198 {
199 Iterator<?> itr = c.iterator();
200 int pos = c.size();
201 while (--pos >= 0)
202 if (!contains(itr.next()))
203 return false;
204 return true;
205 }
206
207 /**
208 * Returns the lowest index at which element appears in this List, or -1 if it
209 * does not appear.
210 *
211 * @param e
212 * the element whose inclusion in the List is being tested
213 * @return the index where e was found
214 */
215 public int indexOf(Object e)
216 {
217 E[] data = this.data;
218 for (int i = 0; i < data.length; i++)
219 if (equals(e, data[i]))
220 return i;
221 return -1;
222 }
223
224 /**
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
227 * appear.
228 *
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
232 */
233 public int indexOf(E e, int index)
234 {
235 E[] data = this.data;
236
237 for (int i = index; i < data.length; i++)
238 if (equals(e, data[i]))
239 return i;
240 return -1;
241 }
242
243 /**
244 * Returns the highest index at which element appears in this List, or -1 if
245 * it does not appear.
246 *
247 * @param e
248 * the element whose inclusion in the List is being tested
249 * @return the index where e was found
250 */
251 public int lastIndexOf(Object e)
252 {
253 E[] data = this.data;
254 for (int i = data.length - 1; i >= 0; i--)
255 if (equals(e, data[i]))
256 return i;
257 return -1;
258 }
259
260 /**
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
263 * appear.
264 *
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
268 */
269 public int lastIndexOf(E e, int index)
270 {
271 E[] data = this.data;
272
273 for (int i = index; i >= 0; i--)
274 if (equals(e, data[i]))
275 return i;
276 return -1;
277 }
278
279 /**
280 * Creates a shallow copy of this ArrayList (elements are not cloned).
281 *
282 * @return the cloned object
283 */
284 public Object clone()
285 {
286 CopyOnWriteArrayList<E> clone = null;
287 try
288 {
289 clone = (CopyOnWriteArrayList<E>) super.clone();
290 }
291 catch (CloneNotSupportedException e)
292 {
293 // Impossible to get here.
294 }
295 return clone;
296 }
297
298 /**
299 * Returns an Object array containing all of the elements in this ArrayList.
300 * The array is independent of this list.
301 *
302 * @return an array representation of this list
303 */
304 public Object[] toArray()
305 {
306 E[] data = this.data;
307 E[] array = (E[]) new Object[data.length];
308 System.arraycopy(data, 0, array, 0, data.length);
309 return array;
310 }
311
312 /**
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.
319 *
320 * @param a
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
326 * if a is null
327 */
328 public <T> T[] toArray(T[] a)
329 {
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);
336 return a;
337 }
338
339 /**
340 * Retrieves the element at the user-supplied index.
341 *
342 * @param index
343 * the index of the element we are fetching
344 * @throws IndexOutOfBoundsException
345 * if index < 0 || index >= size()
346 */
347 public E get(int index)
348 {
349 return data[index];
350 }
351
352 /**
353 * Sets the element at the specified index. The new element, e, can be an
354 * object of any type or null.
355 *
356 * @param index
357 * the index at which the element is being set
358 * @param e
359 * the element to be set
360 * @return the element previously at the specified index
361 * @throws IndexOutOfBoundsException
362 * if index < 0 || index >= 0
363 */
364 public synchronized E set(int index, E e)
365 {
366 E result = data[index];
367 E[] newData = (E[]) data.clone();
368 newData[index] = e;
369 data = newData;
370 return result;
371 }
372
373 /**
374 * Appends the supplied element to the end of this list. The element, e, can
375 * be an object of any type or null.
376 *
377 * @param e
378 * the element to be appended to this list
379 * @return true, the add will always succeed
380 */
381 public synchronized boolean add(E e)
382 {
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;
387 this.data = newData;
388 return true;
389 }
390
391 /**
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.
395 *
396 * @param index
397 * the index at which the element is being added
398 * @param e
399 * the item being added
400 * @throws IndexOutOfBoundsException
401 * if index < 0 || index > size()
402 */
403 public synchronized void add(int index, E e)
404 {
405 E[] data = this.data;
406 E[] newData = (E[]) new Object[data.length + 1];
407 System.arraycopy(data, 0, newData, 0, index);
408 newData[index] = e;
409 System.arraycopy(data, index, newData, index + 1, data.length - index);
410 this.data = newData;
411 }
412
413 /**
414 * Removes the element at the user-supplied index.
415 *
416 * @param index
417 * the index of the element to be removed
418 * @return the removed Object
419 * @throws IndexOutOfBoundsException
420 * if index < 0 || index >= size()
421 */
422 public synchronized E remove(int index)
423 {
424 if (index < 0 || index >= this.size())
425 throw new IndexOutOfBoundsException("index = " + index);
426
427 E[] snapshot = this.data;
428 E[] newData = (E[]) new Object[snapshot.length - 1];
429
430 E result = snapshot[index];
431
432 if (index > 0)
433 System.arraycopy(snapshot, 0, newData, 0, index);
434
435 System.arraycopy(snapshot, index + 1, newData, index,
436 snapshot.length - index - 1);
437
438 this.data = newData;
439
440 return result;
441 }
442
443 /**
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>
446 * otherwise.
447 *
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.
451 */
452 public synchronized boolean remove(Object element)
453 {
454 E[] snapshot = this.data;
455 E[] newData = (E[]) new Object[snapshot.length - 1];
456
457 // search the element to remove while filling the backup array
458 // this way we can run this method in O(n)
459 int elementIndex = -1;
460 for (int i = 0; i < snapshot.length; i++)
461 {
462 if (equals(element, snapshot[i]))
463 {
464 elementIndex = i;
465 break;
466 }
467
468 if (i < newData.length)
469 newData[i] = snapshot[i];
470 }
471
472 if (elementIndex < 0)
473 return false;
474
475 System.arraycopy(snapshot, elementIndex + 1, newData, elementIndex,
476 snapshot.length - elementIndex - 1);
477 this.data = newData;
478
479 return true;
480 }
481
482 /**
483 * Removes all the elements contained in the given collection.
484 * This method removes the elements that are contained in both
485 * this list and in the given collection.
486 *
487 * @param c the collection containing the elements to be removed from this
488 * list.
489 * @return true if at least one element was removed, indicating that
490 * the list internal storage changed as a result, false otherwise.
491 */
492 public synchronized boolean removeAll(Collection<?> c)
493 {
494 if (c.size() == 0)
495 return false;
496
497 E [] snapshot = this.data;
498 E [] storage = (E[]) new Object[this.data.length];
499 boolean changed = false;
500
501 int length = 0;
502 for (E element : snapshot)
503 {
504 // copy all the elements, including null values
505 // if the collection can hold it
506 // FIXME: slow operation
507 if (c.contains(element))
508 changed = true;
509 else
510 storage[length++] = element;
511 }
512
513 if (!changed)
514 return false;
515
516 E[] newData = (E[]) new Object[length];
517 System.arraycopy(storage, 0, newData, 0, length);
518
519 this.data = newData;
520
521 return true;
522 }
523
524 /**
525 * Removes all the elements that are not in the passed collection.
526 * If the collection is void, this method has the same effect of
527 * <code>clear()</code>.
528 * Please, note that this method is extremely slow (unless the argument has
529 * <code>size == 0</code>) and has bad performance is both space and time
530 * usage.
531 *
532 * @param c the collection containing the elements to be retained by this
533 * list.
534 * @return true the list internal storage changed as a result of this
535 * operation, false otherwise.
536 */
537 public synchronized boolean retainAll(Collection<?> c)
538 {
539 // if the given collection does not contain elements
540 // we remove all the elements from our storage
541 if (c.size() == 0)
542 {
543 this.clear();
544 return true;
545 }
546
547 E [] snapshot = this.data;
548 E [] storage = (E[]) new Object[this.data.length];
549
550 int length = 0;
551 for (E element : snapshot)
552 {
553 if (c.contains(element))
554 storage[length++] = element;
555 }
556
557 // means we retained all the elements previously in our storage
558 // we are running already slow here, but at least we avoid copying
559 // another array and changing the internal storage
560 if (length == snapshot.length)
561 return false;
562
563 E[] newData = (E[]) new Object[length];
564 System.arraycopy(storage, 0, newData, 0, length);
565
566 this.data = newData;
567
568 return true;
569 }
570
571 /**
572 * Removes all elements from this List
573 */
574 public synchronized void clear()
575 {
576 data = (E[]) new Object[0];
577 }
578
579 /**
580 * Add each element in the supplied Collection to this List. It is undefined
581 * what happens if you modify the list while this is taking place; for
582 * example, if the collection contains this list. c can contain objects of any
583 * type, as well as null values.
584 *
585 * @param c
586 * a Collection containing elements to be added to this List
587 * @return true if the list was modified, in other words c is not empty
588 * @throws NullPointerException
589 * if c is null
590 */
591 public synchronized boolean addAll(Collection< ? extends E> c)
592 {
593 return addAll(data.length, c);
594 }
595
596 /**
597 * Add all elements in the supplied collection, inserting them beginning at
598 * the specified index. c can contain objects of any type, as well as null
599 * values.
600 *
601 * @param index
602 * the index at which the elements will be inserted
603 * @param c
604 * the Collection containing the elements to be inserted
605 * @throws IndexOutOfBoundsException
606 * if index < 0 || index > 0
607 * @throws NullPointerException
608 * if c is null
609 */
610 public synchronized boolean addAll(int index, Collection< ? extends E> c)
611 {
612 if (index < 0 || index > this.size())
613 throw new IndexOutOfBoundsException("index = " + index);
614
615 int csize = c.size();
616 if (csize == 0)
617 return false;
618
619 E[] data = this.data;
620 Iterator<? extends E> itr = c.iterator();
621
622 E[] newData = (E[]) new Object[data.length + csize];
623
624 // avoid this call at all if we were asked to put the elements at the
625 // beginning of our storage
626 if (index != 0)
627 System.arraycopy(data, 0, newData, 0, index);
628
629 int itemsLeft = index;
630
631 for (E value : c)
632 newData[index++] = value;
633
634 // now copy the remaining elements
635 System.arraycopy(data, itemsLeft, newData, 0, data.length - itemsLeft);
636
637 this.data = newData;
638
639 return true;
640 }
641
642 /**
643 * Adds an element if the list does not contains it already.
644 *
645 * @param val the element to add to the list.
646 * @return true if the element was added, false otherwise.
647 */
648 public synchronized boolean addIfAbsent(E val)
649 {
650 if (contains(val))
651 return false;
652 add(val);
653 return true;
654 }
655
656 /**
657 * Adds all the element from the given collection that are not already
658 * in this list.
659 *
660 * @param c the Collection containing the elements to be inserted
661 * @return true the list internal storage changed as a result of this
662 * operation, false otherwise.
663 */
664 public synchronized int addAllAbsent(Collection<? extends E> c)
665 {
666 int size = c.size();
667 if (size == 0)
668 return 0;
669
670 E [] snapshot = this.data;
671 E [] storage = (E[]) new Object[size];
672
673 size = 0;
674 for (E val : c)
675 {
676 if (!this.contains(val))
677 storage[size++] = val;
678 }
679
680 if (size == 0)
681 return 0;
682
683 // append storage to data
684 E [] newData = (E[]) new Object[snapshot.length + size];
685
686 System.arraycopy(snapshot, 0, newData, 0, snapshot.length);
687 System.arraycopy(storage, 0, newData, snapshot.length, size);
688
689 this.data = newData;
690
691 return size;
692 }
693
694 public String toString()
695 {
696 return Arrays.toString(this.data);
697 }
698
699 public boolean equals(Object o)
700 {
701 if (o == null)
702 return false;
703
704 if (this == o)
705 return true;
706
707 // let's see if 'o' is a list, if so, we need to compare the elements
708 // as returned by the iterator
709 if (o instanceof List)
710 {
711 List<?> source = (List<?>) o;
712
713 if (source.size() != this.size())
714 return false;
715
716 Iterator<?> sourceIterator = source.iterator();
717 for (E element : this)
718 {
719 if (!element.equals(sourceIterator.next()))
720 return false;
721 }
722
723 return true;
724 }
725
726 return false;
727 }
728
729 public int hashCode()
730 {
731 // see http://java.sun.com/6/docs/api/java/util/List.html#hashcode()
732 int hashcode = 1;
733 for (E element : this)
734 {
735 hashcode = 31 * hashcode + (element == null ? 0 : element.hashCode());
736 }
737 return hashcode;
738 }
739
740 /**
741 * Return an Iterator containing the elements of this list.
742 * The Iterator uses a snapshot of the state of the internal storage
743 * at the moment this method is called and does <strong>not</strong> support
744 * update operations, so no synchronization is needed to traverse the
745 * iterator.
746 *
747 * @return an Iterator containing the elements of this list in sequence.
748 */
749 public Iterator<E> iterator()
750 {
751 return new Iterator<E>()
752 {
753 E [] iteratorData = CopyOnWriteArrayList.this.data;
754 int currentElement = 0;
755
756 public boolean hasNext()
757 {
758 return (currentElement < iteratorData.length);
759 }
760
761 public E next()
762 {
763 return iteratorData[currentElement++];
764 }
765
766 public void remove()
767 {
768 throw new UnsupportedOperationException("updating of elements in " +
769 "iterators is not supported " +
770 "by this class");
771 }
772 };
773 }
774
775 /**
776 * Return a ListIterator containing the elements of this list.
777 * The Iterator uses a snapshot of the state of the internal storage
778 * at the moment this method is called and does <strong>not</strong> support
779 * update operations, so no synchronization is needed to traverse the
780 * iterator.
781 *
782 * @return a ListIterator containing the elements of this list in sequence.
783 */
784 public ListIterator<E> listIterator()
785 {
786 return listIterator(0);
787 }
788
789 /**
790 * Return a ListIterator over the elements of this list starting at
791 * the specified index. An initial call to {@code next()} will thus
792 * return the element at {@code index}, while an initial call to
793 * {@code previous()} will return the element at {@code index-1}. The
794 * Iterator uses a snapshot of the state of the internal storage
795 * at the moment this method is called and does <strong>not</strong> support
796 * update operations, so no synchronization is needed to traverse the
797 * iterator.
798 *
799 * @param index the index at which to start iterating.
800 * @return a ListIterator containing the elements of this list in sequence.
801 */
802 public ListIterator<E> listIterator(final int index)
803 {
804 if (index < 0 || index > size())
805 throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
806 + size());
807
808 return new ListIterator<E>()
809 {
810 E [] iteratorData = CopyOnWriteArrayList.this.data;
811 int currentElement = index;
812
813 public void add(E o)
814 {
815 throw new UnsupportedOperationException("updating of elements in " +
816 "iterators is not supported " +
817 "by this class");
818 }
819
820 public boolean hasNext()
821 {
822 return (currentElement < iteratorData.length);
823 }
824
825 public boolean hasPrevious()
826 {
827 return (currentElement > 0);
828 }
829
830 public E next()
831 {
832 if (hasNext() == false)
833 throw new java.util.NoSuchElementException();
834
835 return iteratorData[currentElement++];
836 }
837
838 public int nextIndex()
839 {
840 return (currentElement + 1);
841 }
842
843 public E previous()
844 {
845 if (hasPrevious() == false)
846 throw new java.util.NoSuchElementException();
847
848 return iteratorData[--currentElement];
849 }
850
851 public int previousIndex()
852 {
853 return (currentElement - 1);
854 }
855
856 public void remove()
857 {
858 throw new UnsupportedOperationException("updating of elements in " +
859 "iterators is not supported " +
860 "by this class");
861 }
862
863 public void set(E o)
864 {
865 throw new UnsupportedOperationException("updating of elements in " +
866 "iterators is not supported " +
867 "by this class");
868 }
869
870 };
871 }
872
873 /**
874 * Obtain a List view of a subsection of this list, from fromIndex
875 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
876 * sublist is empty. The returned list should be modifiable if and only
877 * if this list is modifiable. Changes to the returned list should be
878 * reflected in this list. If this list is structurally modified in
879 * any way other than through the returned list, the result of any subsequent
880 * operations on the returned list is undefined.
881 * <p>
882 *
883 * This implementation returns a subclass of AbstractList. It stores, in
884 * private fields, the offset and size of the sublist, and the expected
885 * modCount of the backing list. If the backing list implements RandomAccess,
886 * the sublist will also.
887 * <p>
888 *
889 * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
890 * <code>add(int, Object)</code>, <code>remove(int)</code>,
891 * <code>addAll(int, Collection)</code> and
892 * <code>removeRange(int, int)</code> methods all delegate to the
893 * corresponding methods on the backing abstract list, after
894 * bounds-checking the index and adjusting for the offset. The
895 * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
896 * The <code>listIterator(int)</code> method returns a "wrapper object"
897 * over a list iterator on the backing list, which is created with the
898 * corresponding method on the backing list. The <code>iterator()</code>
899 * method merely returns listIterator(), and the <code>size()</code> method
900 * merely returns the subclass's size field.
901 * <p>
902 *
903 * All methods first check to see if the actual modCount of the backing
904 * list is equal to its expected value, and throw a
905 * ConcurrentModificationException if it is not.
906 *
907 * @param fromIndex the index that the returned list should start from
908 * (inclusive)
909 * @param toIndex the index that the returned list should go to (exclusive)
910 * @return a List backed by a subsection of this list
911 * @throws IndexOutOfBoundsException if fromIndex < 0
912 * || toIndex > size()
913 * @throws IndexOutOfBoundsException if fromIndex > toIndex
914 * @see ConcurrentModificationException
915 * @see RandomAccess
916 */
917 public synchronized List<E> subList(int fromIndex, int toIndex)
918 {
919 // This follows the specification of AbstractList, but is inconsistent
920 // with the one in List. Don't you love Sun's inconsistencies?
921 if (fromIndex > toIndex)
922 throw new IndexOutOfBoundsException(fromIndex + " > " + toIndex);
923 if (fromIndex < 0 || toIndex > size())
924 throw new IndexOutOfBoundsException();
925
926 if (this instanceof RandomAccess)
927 return new RandomAccessSubList<E>(this, fromIndex, toIndex);
928 return new SubList<E>(this, fromIndex, toIndex);
929 }
930
931 /**
932 * This class follows the implementation requirements set forth in
933 * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
934 * by using a non-public top-level class in the same package.
935 *
936 * @author Original author unknown
937 * @author Eric Blake (ebb9@email.byu.edu)
938 */
939 private static class SubList<E>
940 extends AbstractList<E>
941 {
942 // Package visible, for use by iterator.
943 /** The original list. */
944 final CopyOnWriteArrayList<E> backingList;
945 /** The index of the first element of the sublist. */
946 final int offset;
947 /** The size of the sublist. */
948 int size;
949 /** The backing data */
950 E[] data;
951
952 /**
953 * Construct the sublist.
954 *
955 * @param backing the list this comes from
956 * @param fromIndex the lower bound, inclusive
957 * @param toIndex the upper bound, exclusive
958 */
959 SubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex)
960 {
961 backingList = backing;
962 data = backing.data;
963 offset = fromIndex;
964 size = toIndex - fromIndex;
965 }
966
967 /**
968 * This method checks the two modCount fields to ensure that there has
969 * not been a concurrent modification, returning if all is okay.
970 *
971 * @throws ConcurrentModificationException if the backing list has been
972 * modified externally to this sublist
973 */
974 // This can be inlined. Package visible, for use by iterator.
975 void checkMod()
976 {
977 if (data != backingList.data)
978 throw new ConcurrentModificationException();
979 }
980
981 /**
982 * This method checks that a value is between 0 and size (inclusive). If
983 * it is not, an exception is thrown.
984 *
985 * @param index the value to check
986 * @throws IndexOutOfBoundsException if index < 0 || index > size()
987 */
988 // This will get inlined, since it is private.
989 private void checkBoundsInclusive(int index)
990 {
991 if (index < 0 || index > size)
992 throw new IndexOutOfBoundsException("Index: " + index +
993 ", Size:" + size);
994 }
995
996 /**
997 * This method checks that a value is between 0 (inclusive) and size
998 * (exclusive). If it is not, an exception is thrown.
999 *
1000 * @param index the value to check
1001 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1002 */
1003 // This will get inlined, since it is private.
1004 private void checkBoundsExclusive(int index)
1005 {
1006 if (index < 0 || index >= size)
1007 throw new IndexOutOfBoundsException("Index: " + index +
1008 ", Size:" + size);
1009 }
1010
1011 /**
1012 * Specified by AbstractList.subList to return the private field size.
1013 *
1014 * @return the sublist size
1015 * @throws ConcurrentModificationException if the backing list has been
1016 * modified externally to this sublist
1017 */
1018 public int size()
1019 {
1020 synchronized (backingList)
1021 {
1022 checkMod();
1023 return size;
1024 }
1025 }
1026
1027 public void clear()
1028 {
1029 synchronized (backingList)
1030 {
1031 E[] snapshot = backingList.data;
1032 E[] newData = (E[]) new Object[snapshot.length - size];
1033
1034 int toIndex = size + offset;
1035
1036 System.arraycopy(snapshot, 0, newData, 0, offset);
1037 System.arraycopy(snapshot, toIndex, newData, offset,
1038 snapshot.length - toIndex);
1039
1040 backingList.data = newData;
1041 this.data = backingList.data;
1042 this.size = 0;
1043 }
1044 }
1045
1046 /**
1047 * Specified by AbstractList.subList to delegate to the backing list.
1048 *
1049 * @param index the location to modify
1050 * @param o the new value
1051 * @return the old value
1052 * @throws ConcurrentModificationException if the backing list has been
1053 * modified externally to this sublist
1054 * @throws UnsupportedOperationException if the backing list does not
1055 * support the set operation
1056 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1057 * @throws ClassCastException if o cannot be added to the backing list due
1058 * to its type
1059 * @throws IllegalArgumentException if o cannot be added to the backing list
1060 * for some other reason
1061 */
1062 public E set(int index, E o)
1063 {
1064 synchronized (backingList)
1065 {
1066 checkMod();
1067 checkBoundsExclusive(index);
1068
1069 E el = backingList.set(index + offset, o);
1070 this.data = backingList.data;
1071
1072 return el;
1073 }
1074 }
1075
1076 /**
1077 * Specified by AbstractList.subList to delegate to the backing list.
1078 *
1079 * @param index the location to get from
1080 * @return the object at that location
1081 * @throws ConcurrentModificationException if the backing list has been
1082 * modified externally to this sublist
1083 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1084 */
1085 public E get(int index)
1086 {
1087 synchronized (backingList)
1088 {
1089 checkMod();
1090 checkBoundsExclusive(index);
1091
1092 return backingList.get(index + offset);
1093 }
1094 }
1095
1096 /**
1097 * Specified by AbstractList.subList to delegate to the backing list.
1098 *
1099 * @param index the index to insert at
1100 * @param o the object to add
1101 * @throws ConcurrentModificationException if the backing list has been
1102 * modified externally to this sublist
1103 * @throws IndexOutOfBoundsException if index < 0 || index > size()
1104 * @throws UnsupportedOperationException if the backing list does not
1105 * support the add operation.
1106 * @throws ClassCastException if o cannot be added to the backing list due
1107 * to its type.
1108 * @throws IllegalArgumentException if o cannot be added to the backing
1109 * list for some other reason.
1110 */
1111 public void add(int index, E o)
1112 {
1113 synchronized (backingList)
1114 {
1115 checkMod();
1116 checkBoundsInclusive(index);
1117
1118 backingList.add(index + offset, o);
1119
1120 this.data = backingList.data;
1121 size++;
1122 }
1123 }
1124
1125 /**
1126 * Specified by AbstractList.subList to delegate to the backing list.
1127 *
1128 * @param index the index to remove
1129 * @return the removed object
1130 * @throws ConcurrentModificationException if the backing list has been
1131 * modified externally to this sublist
1132 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
1133 * @throws UnsupportedOperationException if the backing list does not
1134 * support the remove operation
1135 */
1136 public E remove(int index)
1137 {
1138 synchronized (backingList)
1139 {
1140 checkMod();
1141 checkBoundsExclusive(index);
1142 E o = backingList.remove(index + offset);
1143
1144 this.data = backingList.data;
1145 size--;
1146
1147 return o;
1148 }
1149 }
1150
1151 /**
1152 * Specified by AbstractList.subList to delegate to the backing list.
1153 *
1154 * @param index the location to insert at
1155 * @param c the collection to insert
1156 * @return true if this list was modified, in other words, c is non-empty
1157 * @throws ConcurrentModificationException if the backing list has been
1158 * modified externally to this sublist
1159 * @throws IndexOutOfBoundsException if index < 0 || index > size()
1160 * @throws UnsupportedOperationException if this list does not support the
1161 * addAll operation
1162 * @throws ClassCastException if some element of c cannot be added to this
1163 * list due to its type
1164 * @throws IllegalArgumentException if some element of c cannot be added
1165 * to this list for some other reason
1166 * @throws NullPointerException if the specified collection is null
1167 */
1168 public boolean addAll(int index, Collection<? extends E> c)
1169 {
1170 synchronized (backingList)
1171 {
1172 checkMod();
1173 checkBoundsInclusive(index);
1174 int csize = c.size();
1175 boolean result = backingList.addAll(offset + index, c);
1176
1177 this.data = backingList.data;
1178 size += csize;
1179
1180 return result;
1181 }
1182 }
1183
1184 /**
1185 * Specified by AbstractList.subList to return addAll(size, c).
1186 *
1187 * @param c the collection to insert
1188 * @return true if this list was modified, in other words, c is non-empty
1189 * @throws ConcurrentModificationException if the backing list has been
1190 * modified externally to this sublist
1191 * @throws UnsupportedOperationException if this list does not support the
1192 * addAll operation
1193 * @throws ClassCastException if some element of c cannot be added to this
1194 * list due to its type
1195 * @throws IllegalArgumentException if some element of c cannot be added
1196 * to this list for some other reason
1197 * @throws NullPointerException if the specified collection is null
1198 */
1199 public boolean addAll(Collection<? extends E> c)
1200 {
1201 synchronized (backingList)
1202 {
1203 return addAll(size, c);
1204 }
1205 }
1206
1207 /**
1208 * Specified by AbstractList.subList to return listIterator().
1209 *
1210 * @return an iterator over the sublist
1211 */
1212 public Iterator<E> iterator()
1213 {
1214 return listIterator();
1215 }
1216
1217 /**
1218 * Specified by AbstractList.subList to return a wrapper around the
1219 * backing list's iterator.
1220 *
1221 * @param index the start location of the iterator
1222 * @return a list iterator over the sublist
1223 * @throws ConcurrentModificationException if the backing list has been
1224 * modified externally to this sublist
1225 * @throws IndexOutOfBoundsException if the value is out of range
1226 */
1227 public ListIterator<E> listIterator(final int index)
1228 {
1229 checkMod();
1230 checkBoundsInclusive(index);
1231
1232 return new ListIterator<E>()
1233 {
1234 private final ListIterator<E> i =
1235 backingList.listIterator(index + offset);
1236 private int position = index;
1237
1238 /**
1239 * Tests to see if there are any more objects to
1240 * return.
1241 *
1242 * @return True if the end of the list has not yet been
1243 * reached.
1244 */
1245 public boolean hasNext()
1246 {
1247 return position < size;
1248 }
1249
1250 /**
1251 * Tests to see if there are objects prior to the
1252 * current position in the list.
1253 *
1254 * @return True if objects exist prior to the current
1255 * position of the iterator.
1256 */
1257 public boolean hasPrevious()
1258 {
1259 return position > 0;
1260 }
1261
1262 /**
1263 * Retrieves the next object from the list.
1264 *
1265 * @return The next object.
1266 * @throws NoSuchElementException if there are no
1267 * more objects to retrieve.
1268 * @throws ConcurrentModificationException if the
1269 * list has been modified elsewhere.
1270 */
1271 public E next()
1272 {
1273 if (position == size)
1274 throw new NoSuchElementException();
1275 position++;
1276 return i.next();
1277 }
1278
1279 /**
1280 * Retrieves the previous object from the list.
1281 *
1282 * @return The next object.
1283 * @throws NoSuchElementException if there are no
1284 * previous objects to retrieve.
1285 * @throws ConcurrentModificationException if the
1286 * list has been modified elsewhere.
1287 */
1288 public E previous()
1289 {
1290 if (position == 0)
1291 throw new NoSuchElementException();
1292 position--;
1293 return i.previous();
1294 }
1295
1296 /**
1297 * Returns the index of the next element in the
1298 * list, which will be retrieved by <code>next()</code>
1299 *
1300 * @return The index of the next element.
1301 */
1302 public int nextIndex()
1303 {
1304 return i.nextIndex() - offset;
1305 }
1306
1307 /**
1308 * Returns the index of the previous element in the
1309 * list, which will be retrieved by <code>previous()</code>
1310 *
1311 * @return The index of the previous element.
1312 */
1313 public int previousIndex()
1314 {
1315 return i.previousIndex() - offset;
1316 }
1317
1318 /**
1319 * Removes the last object retrieved by <code>next()</code>
1320 * from the list, if the list supports object removal.
1321 *
1322 * @throws IllegalStateException if the iterator is positioned
1323 * before the start of the list or the last object has already
1324 * been removed.
1325 * @throws UnsupportedOperationException if the list does
1326 * not support removing elements.
1327 */
1328 public void remove()
1329 {
1330 throw new UnsupportedOperationException("Modification not supported " +
1331 "on CopyOnWriteArrayList iterators");
1332 }
1333
1334 /**
1335 * Replaces the last object retrieved by <code>next()</code>
1336 * or <code>previous</code> with o, if the list supports object
1337 * replacement and an add or remove operation has not already
1338 * been performed.
1339 *
1340 * @throws IllegalStateException if the iterator is positioned
1341 * before the start of the list or the last object has already
1342 * been removed.
1343 * @throws UnsupportedOperationException if the list doesn't support
1344 * the addition or removal of elements.
1345 * @throws ClassCastException if the type of o is not a valid type
1346 * for this list.
1347 * @throws IllegalArgumentException if something else related to o
1348 * prevents its addition.
1349 * @throws ConcurrentModificationException if the list
1350 * has been modified elsewhere.
1351 */
1352 public void set(E o)
1353 {
1354 throw new UnsupportedOperationException("Modification not supported " +
1355 "on CopyOnWriteArrayList iterators");
1356 }
1357
1358 /**
1359 * Adds the supplied object before the element that would be returned
1360 * by a call to <code>next()</code>, if the list supports addition.
1361 *
1362 * @param o The object to add to the list.
1363 * @throws UnsupportedOperationException if the list doesn't support
1364 * the addition of new elements.
1365 * @throws ClassCastException if the type of o is not a valid type
1366 * for this list.
1367 * @throws IllegalArgumentException if something else related to o
1368 * prevents its addition.
1369 * @throws ConcurrentModificationException if the list
1370 * has been modified elsewhere.
1371 */
1372 public void add(E o)
1373 {
1374 throw new UnsupportedOperationException("Modification not supported " +
1375 "on CopyOnWriteArrayList iterators");
1376 }
1377 };
1378 }
1379 } // class SubList
1380
1381 /**
1382 * This class is a RandomAccess version of SubList, as required by
1383 * {@link AbstractList#subList(int, int)}.
1384 *
1385 * @author Eric Blake (ebb9@email.byu.edu)
1386 */
1387 private static final class RandomAccessSubList<E> extends SubList<E>
1388 implements RandomAccess
1389 {
1390 /**
1391 * Construct the sublist.
1392 *
1393 * @param backing the list this comes from
1394 * @param fromIndex the lower bound, inclusive
1395 * @param toIndex the upper bound, exclusive
1396 */
1397 RandomAccessSubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex)
1398 {
1399 super(backing, fromIndex, toIndex);
1400 }
1401 } // class RandomAccessSubList
1402
1403 /**
1404 * Serializes this object to the given stream.
1405 *
1406 * @param s
1407 * the stream to write to
1408 * @throws IOException
1409 * if the underlying stream fails
1410 * @serialData the size field (int), the length of the backing array (int),
1411 * followed by its elements (Objects) in proper order.
1412 */
1413 private void writeObject(ObjectOutputStream s) throws IOException
1414 {
1415 // The 'size' field.
1416 s.defaultWriteObject();
1417 // We serialize unused list entries to preserve capacity.
1418 int len = data.length;
1419 s.writeInt(len);
1420 // it would be more efficient to just write "size" items,
1421 // this need readObject read "size" items too.
1422 for (int i = 0; i < data.length; i++)
1423 s.writeObject(data[i]);
1424 }
1425
1426 /**
1427 * Deserializes this object from the given stream.
1428 *
1429 * @param s
1430 * the stream to read from
1431 * @throws ClassNotFoundException
1432 * if the underlying stream fails
1433 * @throws IOException
1434 * if the underlying stream fails
1435 * @serialData the size field (int), the length of the backing array (int),
1436 * followed by its elements (Objects) in proper order.
1437 */
1438 private void readObject(ObjectInputStream s) throws IOException,
1439 ClassNotFoundException
1440 {
1441 // the `size' field.
1442 s.defaultReadObject();
1443 int capacity = s.readInt();
1444 data = (E[]) new Object[capacity];
1445 for (int i = 0; i < capacity; i++)
1446 data[i] = (E) s.readObject();
1447 }
1448
1449 static final boolean equals(Object o1, Object o2)
1450 {
1451 return o1 == null ? o2 == null : o1.equals(o2);
1452 }
1453
1454 Object[] getArray()
1455 {
1456 return data;
1457 }
1458 }