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 }