001/* CopyOnWriteArrayList.java 002 Copyright (C) 2006 Free Software Foundation 003 004This file is part of GNU Classpath. 005 006GNU Classpath is free software; you can redistribute it and/or modify 007it under the terms of the GNU General Public License as published by 008the Free Software Foundation; either version 2, or (at your option) 009any later version. 010 011GNU Classpath is distributed in the hope that it will be useful, but 012WITHOUT ANY WARRANTY; without even the implied warranty of 013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014General Public License for more details. 015 016You should have received a copy of the GNU General Public License 017along with GNU Classpath; see the file COPYING. If not, write to the 018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 01902110-1301 USA. 020 021Linking this library statically or dynamically with other modules is 022making a combined work based on this library. Thus, the terms and 023conditions of the GNU General Public License cover the whole 024combination. 025 026As a special exception, the copyright holders of this library give you 027permission to link this library with independent modules to produce an 028executable, regardless of the license terms of these independent 029modules, and to copy and distribute the resulting executable under 030terms of your choice, provided that you also meet, for each linked 031independent module, the terms and conditions of the license of that 032module. An independent module is a module which is not derived from 033or based on this library. If you modify this library, you may extend 034this exception to your version of the library, but you are not 035obligated to do so. If you do not wish to do so, delete this 036exception statement from your version. */ 037 038package java.util.concurrent; 039 040import java.io.IOException; 041import java.io.ObjectInputStream; 042import java.io.ObjectOutputStream; 043import java.io.Serializable; 044 045import java.lang.reflect.Array; 046 047import java.util.AbstractList; 048import java.util.Arrays; 049import java.util.Collection; 050import java.util.ConcurrentModificationException; 051import java.util.Iterator; 052import java.util.List; 053import java.util.ListIterator; 054import java.util.NoSuchElementException; 055import 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 */ 100public 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 int len = snapshot.length; 456 457 if (len == 0) 458 return false; 459 460 E[] newData = (E[]) new Object[len - 1]; 461 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++) 466 { 467 if (equals(element, snapshot[i])) 468 { 469 elementIndex = i; 470 break; 471 } 472 473 if (i < newData.length) 474 newData[i] = snapshot[i]; 475 } 476 477 if (elementIndex < 0) 478 return false; 479 480 System.arraycopy(snapshot, elementIndex + 1, newData, elementIndex, 481 snapshot.length - elementIndex - 1); 482 this.data = newData; 483 484 return true; 485 } 486 487 /** 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. 491 * 492 * @param c the collection containing the elements to be removed from this 493 * list. 494 * @return true if at least one element was removed, indicating that 495 * the list internal storage changed as a result, false otherwise. 496 */ 497 public synchronized boolean removeAll(Collection<?> c) 498 { 499 if (c.size() == 0) 500 return false; 501 502 E [] snapshot = this.data; 503 E [] storage = (E[]) new Object[this.data.length]; 504 boolean changed = false; 505 506 int length = 0; 507 for (E element : snapshot) 508 { 509 // copy all the elements, including null values 510 // if the collection can hold it 511 // FIXME: slow operation 512 if (c.contains(element)) 513 changed = true; 514 else 515 storage[length++] = element; 516 } 517 518 if (!changed) 519 return false; 520 521 E[] newData = (E[]) new Object[length]; 522 System.arraycopy(storage, 0, newData, 0, length); 523 524 this.data = newData; 525 526 return true; 527 } 528 529 /** 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 535 * usage. 536 * 537 * @param c the collection containing the elements to be retained by this 538 * list. 539 * @return true the list internal storage changed as a result of this 540 * operation, false otherwise. 541 */ 542 public synchronized boolean retainAll(Collection<?> c) 543 { 544 // if the given collection does not contain elements 545 // we remove all the elements from our storage 546 if (c.size() == 0) 547 { 548 this.clear(); 549 return true; 550 } 551 552 E [] snapshot = this.data; 553 E [] storage = (E[]) new Object[this.data.length]; 554 555 int length = 0; 556 for (E element : snapshot) 557 { 558 if (c.contains(element)) 559 storage[length++] = element; 560 } 561 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) 566 return false; 567 568 E[] newData = (E[]) new Object[length]; 569 System.arraycopy(storage, 0, newData, 0, length); 570 571 this.data = newData; 572 573 return true; 574 } 575 576 /** 577 * Removes all elements from this List 578 */ 579 public synchronized void clear() 580 { 581 data = (E[]) new Object[0]; 582 } 583 584 /** 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. 589 * 590 * @param c 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 594 * if c is null 595 */ 596 public synchronized boolean addAll(Collection< ? extends E> c) 597 { 598 return addAll(data.length, c); 599 } 600 601 /** 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 604 * values. 605 * 606 * @param index 607 * the index at which the elements will be inserted 608 * @param c 609 * the Collection containing the elements to be inserted 610 * @throws IndexOutOfBoundsException 611 * if index < 0 || index > 0 612 * @throws NullPointerException 613 * if c is null 614 */ 615 public synchronized boolean addAll(int index, Collection< ? extends E> c) 616 { 617 if (index < 0 || index > this.size()) 618 throw new IndexOutOfBoundsException("index = " + index); 619 620 int csize = c.size(); 621 if (csize == 0) 622 return false; 623 624 E[] data = this.data; 625 Iterator<? extends E> itr = c.iterator(); 626 627 E[] newData = (E[]) new Object[data.length + csize]; 628 629 // avoid this call at all if we were asked to put the elements at the 630 // beginning of our storage 631 if (index != 0) 632 System.arraycopy(data, 0, newData, 0, index); 633 634 int itemsLeft = index; 635 636 for (E value : c) 637 newData[index++] = value; 638 639 // now copy the remaining elements 640 System.arraycopy(data, itemsLeft, newData, 0, data.length - itemsLeft); 641 642 this.data = newData; 643 644 return true; 645 } 646 647 /** 648 * Adds an element if the list does not contains it already. 649 * 650 * @param val the element to add to the list. 651 * @return true if the element was added, false otherwise. 652 */ 653 public synchronized boolean addIfAbsent(E val) 654 { 655 if (contains(val)) 656 return false; 657 add(val); 658 return true; 659 } 660 661 /** 662 * Adds all the element from the given collection that are not already 663 * in this list. 664 * 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. 668 */ 669 public synchronized int addAllAbsent(Collection<? extends E> c) 670 { 671 int size = c.size(); 672 if (size == 0) 673 return 0; 674 675 E [] snapshot = this.data; 676 E [] storage = (E[]) new Object[size]; 677 678 size = 0; 679 for (E val : c) 680 { 681 if (!this.contains(val)) 682 storage[size++] = val; 683 } 684 685 if (size == 0) 686 return 0; 687 688 // append storage to data 689 E [] newData = (E[]) new Object[snapshot.length + size]; 690 691 System.arraycopy(snapshot, 0, newData, 0, snapshot.length); 692 System.arraycopy(storage, 0, newData, snapshot.length, size); 693 694 this.data = newData; 695 696 return size; 697 } 698 699 public String toString() 700 { 701 return Arrays.toString(this.data); 702 } 703 704 public boolean equals(Object o) 705 { 706 if (o == null) 707 return false; 708 709 if (this == o) 710 return true; 711 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) 715 { 716 List<?> source = (List<?>) o; 717 718 if (source.size() != this.size()) 719 return false; 720 721 Iterator<?> sourceIterator = source.iterator(); 722 for (E element : this) 723 { 724 if (!element.equals(sourceIterator.next())) 725 return false; 726 } 727 728 return true; 729 } 730 731 return false; 732 } 733 734 public int hashCode() 735 { 736 // see http://java.sun.com/6/docs/api/java/util/List.html#hashcode() 737 int hashcode = 1; 738 for (E element : this) 739 { 740 hashcode = 31 * hashcode + (element == null ? 0 : element.hashCode()); 741 } 742 return hashcode; 743 } 744 745 /** 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 750 * iterator. 751 * 752 * @return an Iterator containing the elements of this list in sequence. 753 */ 754 public Iterator<E> iterator() 755 { 756 return new Iterator<E>() 757 { 758 E [] iteratorData = CopyOnWriteArrayList.this.data; 759 int currentElement = 0; 760 761 public boolean hasNext() 762 { 763 return (currentElement < iteratorData.length); 764 } 765 766 public E next() 767 { 768 return iteratorData[currentElement++]; 769 } 770 771 public void remove() 772 { 773 throw new UnsupportedOperationException("updating of elements in " + 774 "iterators is not supported " + 775 "by this class"); 776 } 777 }; 778 } 779 780 /** 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 785 * iterator. 786 * 787 * @return a ListIterator containing the elements of this list in sequence. 788 */ 789 public ListIterator<E> listIterator() 790 { 791 return listIterator(0); 792 } 793 794 /** 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 802 * iterator. 803 * 804 * @param index the index at which to start iterating. 805 * @return a ListIterator containing the elements of this list in sequence. 806 */ 807 public ListIterator<E> listIterator(final int index) 808 { 809 if (index < 0 || index > size()) 810 throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 811 + size()); 812 813 return new ListIterator<E>() 814 { 815 E [] iteratorData = CopyOnWriteArrayList.this.data; 816 int currentElement = index; 817 818 public void add(E o) 819 { 820 throw new UnsupportedOperationException("updating of elements in " + 821 "iterators is not supported " + 822 "by this class"); 823 } 824 825 public boolean hasNext() 826 { 827 return (currentElement < iteratorData.length); 828 } 829 830 public boolean hasPrevious() 831 { 832 return (currentElement > 0); 833 } 834 835 public E next() 836 { 837 if (hasNext() == false) 838 throw new java.util.NoSuchElementException(); 839 840 return iteratorData[currentElement++]; 841 } 842 843 public int nextIndex() 844 { 845 return (currentElement + 1); 846 } 847 848 public E previous() 849 { 850 if (hasPrevious() == false) 851 throw new java.util.NoSuchElementException(); 852 853 return iteratorData[--currentElement]; 854 } 855 856 public int previousIndex() 857 { 858 return (currentElement - 1); 859 } 860 861 public void remove() 862 { 863 throw new UnsupportedOperationException("updating of elements in " + 864 "iterators is not supported " + 865 "by this class"); 866 } 867 868 public void set(E o) 869 { 870 throw new UnsupportedOperationException("updating of elements in " + 871 "iterators is not supported " + 872 "by this class"); 873 } 874 875 }; 876 } 877 878 /** 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. 886 * <p> 887 * 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. 892 * <p> 893 * 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. 906 * <p> 907 * 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. 911 * 912 * @param fromIndex the index that the returned list should start from 913 * (inclusive) 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 920 * @see RandomAccess 921 */ 922 public synchronized List<E> subList(int fromIndex, int toIndex) 923 { 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(); 930 931 if (this instanceof RandomAccess) 932 return new RandomAccessSubList<E>(this, fromIndex, toIndex); 933 return new SubList<E>(this, fromIndex, toIndex); 934 } 935 936 /** 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. 940 * 941 * @author Original author unknown 942 * @author Eric Blake (ebb9@email.byu.edu) 943 */ 944 private static class SubList<E> 945 extends AbstractList<E> 946 { 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. */ 951 final int offset; 952 /** The size of the sublist. */ 953 int size; 954 /** The backing data */ 955 E[] data; 956 957 /** 958 * Construct the sublist. 959 * 960 * @param backing the list this comes from 961 * @param fromIndex the lower bound, inclusive 962 * @param toIndex the upper bound, exclusive 963 */ 964 SubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex) 965 { 966 backingList = backing; 967 data = backing.data; 968 offset = fromIndex; 969 size = toIndex - fromIndex; 970 } 971 972 /** 973 * This method checks the two modCount fields to ensure that there has 974 * not been a concurrent modification, returning if all is okay. 975 * 976 * @throws ConcurrentModificationException if the backing list has been 977 * modified externally to this sublist 978 */ 979 // This can be inlined. Package visible, for use by iterator. 980 void checkMod() 981 { 982 if (data != backingList.data) 983 throw new ConcurrentModificationException(); 984 } 985 986 /** 987 * This method checks that a value is between 0 and size (inclusive). If 988 * it is not, an exception is thrown. 989 * 990 * @param index the value to check 991 * @throws IndexOutOfBoundsException if index < 0 || index > size() 992 */ 993 // This will get inlined, since it is private. 994 private void checkBoundsInclusive(int index) 995 { 996 if (index < 0 || index > size) 997 throw new IndexOutOfBoundsException("Index: " + index + 998 ", Size:" + size); 999 } 1000 1001 /** 1002 * This method checks that a value is between 0 (inclusive) and size 1003 * (exclusive). If it is not, an exception is thrown. 1004 * 1005 * @param index the value to check 1006 * @throws IndexOutOfBoundsException if index < 0 || index >= size() 1007 */ 1008 // This will get inlined, since it is private. 1009 private void checkBoundsExclusive(int index) 1010 { 1011 if (index < 0 || index >= size) 1012 throw new IndexOutOfBoundsException("Index: " + index + 1013 ", Size:" + size); 1014 } 1015 1016 /** 1017 * Specified by AbstractList.subList to return the private field size. 1018 * 1019 * @return the sublist size 1020 * @throws ConcurrentModificationException if the backing list has been 1021 * modified externally to this sublist 1022 */ 1023 public int size() 1024 { 1025 synchronized (backingList) 1026 { 1027 checkMod(); 1028 return size; 1029 } 1030 } 1031 1032 public void clear() 1033 { 1034 synchronized (backingList) 1035 { 1036 E[] snapshot = backingList.data; 1037 E[] newData = (E[]) new Object[snapshot.length - size]; 1038 1039 int toIndex = size + offset; 1040 1041 System.arraycopy(snapshot, 0, newData, 0, offset); 1042 System.arraycopy(snapshot, toIndex, newData, offset, 1043 snapshot.length - toIndex); 1044 1045 backingList.data = newData; 1046 this.data = backingList.data; 1047 this.size = 0; 1048 } 1049 } 1050 1051 /** 1052 * Specified by AbstractList.subList to delegate to the backing list. 1053 * 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 1063 * to its type 1064 * @throws IllegalArgumentException if o cannot be added to the backing list 1065 * for some other reason 1066 */ 1067 public E set(int index, E o) 1068 { 1069 synchronized (backingList) 1070 { 1071 checkMod(); 1072 checkBoundsExclusive(index); 1073 1074 E el = backingList.set(index + offset, o); 1075 this.data = backingList.data; 1076 1077 return el; 1078 } 1079 } 1080 1081 /** 1082 * Specified by AbstractList.subList to delegate to the backing list. 1083 * 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() 1089 */ 1090 public E get(int index) 1091 { 1092 synchronized (backingList) 1093 { 1094 checkMod(); 1095 checkBoundsExclusive(index); 1096 1097 return backingList.get(index + offset); 1098 } 1099 } 1100 1101 /** 1102 * Specified by AbstractList.subList to delegate to the backing list. 1103 * 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 1112 * to its type. 1113 * @throws IllegalArgumentException if o cannot be added to the backing 1114 * list for some other reason. 1115 */ 1116 public void add(int index, E o) 1117 { 1118 synchronized (backingList) 1119 { 1120 checkMod(); 1121 checkBoundsInclusive(index); 1122 1123 backingList.add(index + offset, o); 1124 1125 this.data = backingList.data; 1126 size++; 1127 } 1128 } 1129 1130 /** 1131 * Specified by AbstractList.subList to delegate to the backing list. 1132 * 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 1140 */ 1141 public E remove(int index) 1142 { 1143 synchronized (backingList) 1144 { 1145 checkMod(); 1146 checkBoundsExclusive(index); 1147 E o = backingList.remove(index + offset); 1148 1149 this.data = backingList.data; 1150 size--; 1151 1152 return o; 1153 } 1154 } 1155 1156 /** 1157 * Specified by AbstractList.subList to delegate to the backing list. 1158 * 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 1166 * addAll operation 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 1172 */ 1173 public boolean addAll(int index, Collection<? extends E> c) 1174 { 1175 synchronized (backingList) 1176 { 1177 checkMod(); 1178 checkBoundsInclusive(index); 1179 int csize = c.size(); 1180 boolean result = backingList.addAll(offset + index, c); 1181 1182 this.data = backingList.data; 1183 size += csize; 1184 1185 return result; 1186 } 1187 } 1188 1189 /** 1190 * Specified by AbstractList.subList to return addAll(size, c). 1191 * 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 1197 * addAll operation 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 1203 */ 1204 public boolean addAll(Collection<? extends E> c) 1205 { 1206 synchronized (backingList) 1207 { 1208 return addAll(size, c); 1209 } 1210 } 1211 1212 /** 1213 * Specified by AbstractList.subList to return listIterator(). 1214 * 1215 * @return an iterator over the sublist 1216 */ 1217 public Iterator<E> iterator() 1218 { 1219 return listIterator(); 1220 } 1221 1222 /** 1223 * Specified by AbstractList.subList to return a wrapper around the 1224 * backing list's iterator. 1225 * 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 1231 */ 1232 public ListIterator<E> listIterator(final int index) 1233 { 1234 checkMod(); 1235 checkBoundsInclusive(index); 1236 1237 return new ListIterator<E>() 1238 { 1239 private final ListIterator<E> i = 1240 backingList.listIterator(index + offset); 1241 private int position = index; 1242 1243 /** 1244 * Tests to see if there are any more objects to 1245 * return. 1246 * 1247 * @return True if the end of the list has not yet been 1248 * reached. 1249 */ 1250 public boolean hasNext() 1251 { 1252 return position < size; 1253 } 1254 1255 /** 1256 * Tests to see if there are objects prior to the 1257 * current position in the list. 1258 * 1259 * @return True if objects exist prior to the current 1260 * position of the iterator. 1261 */ 1262 public boolean hasPrevious() 1263 { 1264 return position > 0; 1265 } 1266 1267 /** 1268 * Retrieves the next object from the list. 1269 * 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. 1275 */ 1276 public E next() 1277 { 1278 if (position == size) 1279 throw new NoSuchElementException(); 1280 position++; 1281 return i.next(); 1282 } 1283 1284 /** 1285 * Retrieves the previous object from the list. 1286 * 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. 1292 */ 1293 public E previous() 1294 { 1295 if (position == 0) 1296 throw new NoSuchElementException(); 1297 position--; 1298 return i.previous(); 1299 } 1300 1301 /** 1302 * Returns the index of the next element in the 1303 * list, which will be retrieved by <code>next()</code> 1304 * 1305 * @return The index of the next element. 1306 */ 1307 public int nextIndex() 1308 { 1309 return i.nextIndex() - offset; 1310 } 1311 1312 /** 1313 * Returns the index of the previous element in the 1314 * list, which will be retrieved by <code>previous()</code> 1315 * 1316 * @return The index of the previous element. 1317 */ 1318 public int previousIndex() 1319 { 1320 return i.previousIndex() - offset; 1321 } 1322 1323 /** 1324 * Removes the last object retrieved by <code>next()</code> 1325 * from the list, if the list supports object removal. 1326 * 1327 * @throws IllegalStateException if the iterator is positioned 1328 * before the start of the list or the last object has already 1329 * been removed. 1330 * @throws UnsupportedOperationException if the list does 1331 * not support removing elements. 1332 */ 1333 public void remove() 1334 { 1335 throw new UnsupportedOperationException("Modification not supported " + 1336 "on CopyOnWriteArrayList iterators"); 1337 } 1338 1339 /** 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 1343 * been performed. 1344 * 1345 * @throws IllegalStateException if the iterator is positioned 1346 * before the start of the list or the last object has already 1347 * been removed. 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 1351 * for this list. 1352 * @throws IllegalArgumentException if something else related to o 1353 * prevents its addition. 1354 * @throws ConcurrentModificationException if the list 1355 * has been modified elsewhere. 1356 */ 1357 public void set(E o) 1358 { 1359 throw new UnsupportedOperationException("Modification not supported " + 1360 "on CopyOnWriteArrayList iterators"); 1361 } 1362 1363 /** 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. 1366 * 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 1371 * for this list. 1372 * @throws IllegalArgumentException if something else related to o 1373 * prevents its addition. 1374 * @throws ConcurrentModificationException if the list 1375 * has been modified elsewhere. 1376 */ 1377 public void add(E o) 1378 { 1379 throw new UnsupportedOperationException("Modification not supported " + 1380 "on CopyOnWriteArrayList iterators"); 1381 } 1382 }; 1383 } 1384 } // class SubList 1385 1386 /** 1387 * This class is a RandomAccess version of SubList, as required by 1388 * {@link AbstractList#subList(int, int)}. 1389 * 1390 * @author Eric Blake (ebb9@email.byu.edu) 1391 */ 1392 private static final class RandomAccessSubList<E> extends SubList<E> 1393 implements RandomAccess 1394 { 1395 /** 1396 * Construct the sublist. 1397 * 1398 * @param backing the list this comes from 1399 * @param fromIndex the lower bound, inclusive 1400 * @param toIndex the upper bound, exclusive 1401 */ 1402 RandomAccessSubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex) 1403 { 1404 super(backing, fromIndex, toIndex); 1405 } 1406 } // class RandomAccessSubList 1407 1408 /** 1409 * Serializes this object to the given stream. 1410 * 1411 * @param s 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. 1417 */ 1418 private void writeObject(ObjectOutputStream s) throws IOException 1419 { 1420 // The 'size' field. 1421 s.defaultWriteObject(); 1422 // We serialize unused list entries to preserve capacity. 1423 int len = data.length; 1424 s.writeInt(len); 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]); 1429 } 1430 1431 /** 1432 * Deserializes this object from the given stream. 1433 * 1434 * @param s 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. 1442 */ 1443 private void readObject(ObjectInputStream s) throws IOException, 1444 ClassNotFoundException 1445 { 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(); 1452 } 1453 1454 static final boolean equals(Object o1, Object o2) 1455 { 1456 return o1 == null ? o2 == null : o1.equals(o2); 1457 } 1458 1459 Object[] getArray() 1460 { 1461 return data; 1462 } 1463}