| Frames | No Frames |
1: /* CopyOnWriteArrayList.java 2: Copyright (C) 2006 Free Software Foundation 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: package java.util.concurrent; 39: 40: import java.io.IOException; 41: import java.io.ObjectInputStream; 42: import java.io.ObjectOutputStream; 43: import java.io.Serializable; 44: 45: import java.lang.reflect.Array; 46: 47: import java.util.AbstractList; 48: import java.util.Arrays; 49: import java.util.Collection; 50: import java.util.ConcurrentModificationException; 51: import java.util.Iterator; 52: import java.util.List; 53: import java.util.ListIterator; 54: import java.util.NoSuchElementException; 55: import java.util.RandomAccess; 56: 57: /** 58: * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is 59: * as special ArrayList which performs copies of the underlying storage 60: * each time a write (<code>remove</code>, <code>add</code> etc..) operation 61: * is performed.<br /> 62: * <br /> 63: * The update operation in this class run usually in <code>O(n)</code> or worse, 64: * but traversal operations are fast and efficient, especially when running in 65: * a multi-thread environment without the need to design complex synchronize 66: * mechanisms.<br /> 67: * <br /> 68: * <code>Iterator</code>s in this class work on a snapshot of the backing store 69: * at the moment the iterator itself was created, hence the iterator will not 70: * reflect changes in the underlying storage. Thus, update operation on the 71: * <code>Iterator</code>s are not supported, but as interferences from other 72: * threads are impossible, no <code>ConcurrentModificationException</code> 73: * will be ever thrown from within the <code>Iterator</code>. 74: * <br /><br /> 75: * This class is especially useful when used with event handling, like the 76: * following code demonstrates:<br /> 77: * <code><pre> 78: * 79: * CopyOnWriteArrayList<EventListener> listeners = 80: * new CopyOnWriteArrayList<EventListener>(); 81: * 82: * [...] 83: * 84: * for (final EventListener listener : listeners) 85: * { 86: * Runnable dispatcher = new Runnable() { 87: * public void run() 88: * { 89: * listener.preferenceChange(event); 90: * } 91: * }; 92: * 93: * Executor executor = Executors.newSingleThreadExecutor(); 94: * executor.execute(dispatcher); 95: * } 96: * </pre></code> 97: * 98: * @since 1.5 99: */ 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: 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: }