| GNU Classpath (0.97.1) | |
| 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.Collection; 49: import java.util.Iterator; 50: import java.util.List; 51: import java.util.ListIterator; 52: import java.util.RandomAccess; 53: 54: /** 55: * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is 56: * as special ArrayList which performs copies of the underlying storage 57: * each time a write (<code>remove</code>, <code>add</code> etc..) operation 58: * is performed.<br /> 59: * <br /> 60: * The update operation in this class run usually in <code>O(n)</code> or worse, 61: * but traversal operations are fast and efficient, especially when running in 62: * a multi-thread environment without the need to design complex synchronize 63: * mechanisms.<br /> 64: * <br /> 65: * <code>Iterator</code>s in this class work on a snapshot of the backing store 66: * at the moment the iterator itself was created, hence the iterator will not 67: * reflect changes in the underlying storage. Thus, update operation on the 68: * <code>Iterator</code>s are not supported, but as interferences from other 69: * threads are impossible, no <code>ConcurrentModificationException</code> 70: * will be ever thrown from within the <code>Iterator</code>. 71: * <br /><br /> 72: * This class is especially useful when used with event handling, like the 73: * following code demonstrates:<br /> 74: * <code><pre> 75: * 76: * CopyOnWriteArrayList<EventListener> listeners = 77: * new CopyOnWriteArrayList<EventListener>(); 78: * 79: * [...] 80: * 81: * for (final EventListener listener : listeners) 82: * { 83: * Runnable dispatcher = new Runnable() { 84: * public void run() 85: * { 86: * listener.preferenceChange(event); 87: * } 88: * }; 89: * 90: * Executor executor = Executors.newSingleThreadExecutor(); 91: * executor.execute(dispatcher); 92: * } 93: * </pre></code> 94: * 95: * @since 1.5 96: */ 97: public class CopyOnWriteArrayList<E> extends AbstractList<E> implements 98: List<E>, RandomAccess, Cloneable, Serializable 99: { 100: /** 101: * 102: */ 103: private static final long serialVersionUID = 8673264195747942595L; 104: 105: /** 106: * Where the data is stored. 107: */ 108: private transient E[] data; 109: 110: /** 111: * Construct a new ArrayList with the default capacity (16). 112: */ 113: public CopyOnWriteArrayList() 114: { 115: data = (E[]) new Object[0]; 116: } 117: 118: /** 119: * Construct a new ArrayList, and initialize it with the elements in the 120: * supplied Collection. The initial capacity is 110% of the Collection's size. 121: * 122: * @param c 123: * the collection whose elements will initialize this list 124: * @throws NullPointerException 125: * if c is null 126: */ 127: public CopyOnWriteArrayList(Collection< ? extends E> c) 128: { 129: // FIXME ... correct? use c.toArray() 130: data = (E[]) new Object[c.size()]; 131: int index = 0; 132: for (E value : c) 133: data[index++] = value; 134: } 135: 136: /** 137: * Construct a new ArrayList, and initialize it with the elements in the 138: * supplied array. 139: * 140: * @param array 141: * the array used to initialize this list 142: * @throws NullPointerException 143: * if array is null 144: */ 145: public CopyOnWriteArrayList(E[] array) 146: { 147: data = array.clone(); 148: } 149: 150: /** 151: * Returns the number of elements in this list. 152: * 153: * @return the list size 154: */ 155: public int size() 156: { 157: return data.length; 158: } 159: 160: /** 161: * Checks if the list is empty. 162: * 163: * @return true if there are no elements 164: */ 165: public boolean isEmpty() 166: { 167: return data.length == 0; 168: } 169: 170: /** 171: * Returns true if element is in this ArrayList. 172: * 173: * @param e 174: * the element whose inclusion in the List is being tested 175: * @return true if the list contains e 176: */ 177: public boolean contains(Object e) 178: { 179: return indexOf(e) != -1; 180: } 181: 182: /** 183: * Returns the lowest index at which element appears in this List, or -1 if it 184: * does not appear. 185: * 186: * @param e 187: * the element whose inclusion in the List is being tested 188: * @return the index where e was found 189: */ 190: public int indexOf(Object e) 191: { 192: E[] data = this.data; 193: for (int i = 0; i < data.length; i++) 194: if (equals(e, data[i])) 195: return i; 196: return -1; 197: } 198: 199: /** 200: * Return the lowest index greater equal <code>index</code> at which 201: * <code>e</code> appears in this List, or -1 if it does not 202: * appear. 203: * 204: * @param e the element whose inclusion in the list is being tested 205: * @param index the index at which the search begins 206: * @return the index where <code>e</code> was found 207: */ 208: public int indexOf(E e, int index) 209: { 210: E[] data = this.data; 211: 212: for (int i = index; i < data.length; i++) 213: if (equals(e, data[i])) 214: return i; 215: return -1; 216: } 217: 218: /** 219: * Returns the highest index at which element appears in this List, or -1 if 220: * it does not appear. 221: * 222: * @param e 223: * the element whose inclusion in the List is being tested 224: * @return the index where e was found 225: */ 226: public int lastIndexOf(Object e) 227: { 228: E[] data = this.data; 229: for (int i = data.length - 1; i >= 0; i--) 230: if (equals(e, data[i])) 231: return i; 232: return -1; 233: } 234: 235: /** 236: * Returns the highest index lesser equal <code>index</code> at 237: * which <code>e</code> appears in this List, or -1 if it does not 238: * appear. 239: * 240: * @param e the element whose inclusion in the list is being tested 241: * @param index the index at which the search begins 242: * @return the index where <code>e</code> was found 243: */ 244: public int lastIndexOf(E e, int index) 245: { 246: E[] data = this.data; 247: 248: for (int i = index; i >= 0; i--) 249: if (equals(e, data[i])) 250: return i; 251: return -1; 252: } 253: 254: /** 255: * Creates a shallow copy of this ArrayList (elements are not cloned). 256: * 257: * @return the cloned object 258: */ 259: public Object clone() 260: { 261: CopyOnWriteArrayList<E> clone = null; 262: try 263: { 264: clone = (CopyOnWriteArrayList<E>) super.clone(); 265: clone.data = (E[]) data.clone(); 266: } 267: catch (CloneNotSupportedException e) 268: { 269: // Impossible to get here. 270: } 271: return clone; 272: } 273: 274: /** 275: * Returns an Object array containing all of the elements in this ArrayList. 276: * The array is independent of this list. 277: * 278: * @return an array representation of this list 279: */ 280: public Object[] toArray() 281: { 282: E[] data = this.data; 283: E[] array = (E[]) new Object[data.length]; 284: System.arraycopy(data, 0, array, 0, data.length); 285: return array; 286: } 287: 288: /** 289: * Returns an Array whose component type is the runtime component type of the 290: * passed-in Array. The returned Array is populated with all of the elements 291: * in this ArrayList. If the passed-in Array is not large enough to store all 292: * of the elements in this List, a new Array will be created and returned; if 293: * the passed-in Array is <i>larger</i> than the size of this List, then 294: * size() index will be set to null. 295: * 296: * @param a 297: * the passed-in Array 298: * @return an array representation of this list 299: * @throws ArrayStoreException 300: * if the runtime type of a does not allow an element in this list 301: * @throws NullPointerException 302: * if a is null 303: */ 304: public <T> T[] toArray(T[] a) 305: { 306: E[] data = this.data; 307: if (a.length < data.length) 308: a = (T[]) Array.newInstance(a.getClass().getComponentType(), data.length); 309: else if (a.length > data.length) 310: a[data.length] = null; 311: System.arraycopy(data, 0, a, 0, data.length); 312: return a; 313: } 314: 315: /** 316: * Retrieves the element at the user-supplied index. 317: * 318: * @param index 319: * the index of the element we are fetching 320: * @throws IndexOutOfBoundsException 321: * if index < 0 || index >= size() 322: */ 323: public E get(int index) 324: { 325: return data[index]; 326: } 327: 328: /** 329: * Sets the element at the specified index. The new element, e, can be an 330: * object of any type or null. 331: * 332: * @param index 333: * the index at which the element is being set 334: * @param e 335: * the element to be set 336: * @return the element previously at the specified index 337: * @throws IndexOutOfBoundsException 338: * if index < 0 || index >= 0 339: */ 340: public synchronized E set(int index, E e) 341: { 342: E result = data[index]; 343: E[] newData = data.clone(); 344: newData[index] = e; 345: data = newData; 346: return result; 347: } 348: 349: /** 350: * Appends the supplied element to the end of this list. The element, e, can 351: * be an object of any type or null. 352: * 353: * @param e 354: * the element to be appended to this list 355: * @return true, the add will always succeed 356: */ 357: public synchronized boolean add(E e) 358: { 359: E[] data = this.data; 360: E[] newData = (E[]) new Object[data.length + 1]; 361: System.arraycopy(data, 0, newData, 0, data.length); 362: newData[data.length] = e; 363: this.data = newData; 364: return true; 365: } 366: 367: /** 368: * Adds the supplied element at the specified index, shifting all elements 369: * currently at that index or higher one to the right. The element, e, can be 370: * an object of any type or null. 371: * 372: * @param index 373: * the index at which the element is being added 374: * @param e 375: * the item being added 376: * @throws IndexOutOfBoundsException 377: * if index < 0 || index > size() 378: */ 379: public synchronized void add(int index, E e) 380: { 381: E[] data = this.data; 382: E[] newData = (E[]) new Object[data.length + 1]; 383: System.arraycopy(data, 0, newData, 0, index); 384: newData[index] = e; 385: System.arraycopy(data, index, newData, index + 1, data.length - index); 386: this.data = newData; 387: } 388: 389: /** 390: * Removes the element at the user-supplied index. 391: * 392: * @param index 393: * the index of the element to be removed 394: * @return the removed Object 395: * @throws IndexOutOfBoundsException 396: * if index < 0 || index >= size() 397: */ 398: public synchronized E remove(int index) 399: { 400: if (index < 0 || index >= this.size()) 401: throw new IndexOutOfBoundsException("index = " + index); 402: 403: E[] snapshot = this.data; 404: E[] newData = (E[]) new Object[snapshot.length - 1]; 405: 406: E result = snapshot[index]; 407: 408: if (index > 0) 409: System.arraycopy(snapshot, 0, newData, 0, index); 410: 411: System.arraycopy(snapshot, index + 1, newData, index, 412: snapshot.length - index - 1); 413: 414: this.data = newData; 415: 416: return result; 417: } 418: 419: /** 420: * Remove the first occurrence, if any, of the given object from this list, 421: * returning <code>true</code> if the object was removed, <code>false</code> 422: * otherwise. 423: * 424: * @param element the object to be removed. 425: * @return true if element was removed, false otherwise. false means also that 426: * the underlying storage was unchanged after this operation concluded. 427: */ 428: public synchronized boolean remove(Object element) 429: { 430: E[] snapshot = this.data; 431: E[] newData = (E[]) new Object[snapshot.length - 1]; 432: 433: // search the element to remove while filling the backup array 434: // this way we can run this method in O(n) 435: int elementIndex = -1; 436: for (int i = 0; i < snapshot.length; i++) 437: { 438: if (equals(element, snapshot[i])) 439: { 440: elementIndex = i; 441: break; 442: } 443: 444: if (i < newData.length) 445: newData[i] = snapshot[i]; 446: } 447: 448: if (elementIndex < 0) 449: return false; 450: 451: System.arraycopy(snapshot, elementIndex + 1, newData, elementIndex, 452: snapshot.length - elementIndex - 1); 453: this.data = newData; 454: 455: return true; 456: } 457: 458: /** 459: * Removes all the elements contained in the given collection. 460: * This method removes the elements that are contained in both 461: * this list and in the given collection. 462: * 463: * @param c the collection containing the elements to be removed from this 464: * list. 465: * @return true if at least one element was removed, indicating that 466: * the list internal storage changed as a result, false otherwise. 467: */ 468: public synchronized boolean removeAll(Collection<?> c) 469: { 470: if (c.size() == 0) 471: return false; 472: 473: E [] snapshot = this.data; 474: E [] storage = (E[]) new Object[this.data.length]; 475: boolean changed = false; 476: 477: int length = 0; 478: for (E element : snapshot) 479: { 480: // copy all the elements, including null values 481: // if the collection can hold it 482: // FIXME: slow operation 483: if (c.contains(element)) 484: changed = true; 485: else 486: storage[length++] = element; 487: } 488: 489: if (!changed) 490: return false; 491: 492: E[] newData = (E[]) new Object[length]; 493: System.arraycopy(storage, 0, newData, 0, length); 494: 495: this.data = newData; 496: 497: return true; 498: } 499: 500: /** 501: * Removes all the elements that are not in the passed collection. 502: * If the collection is void, this method has the same effect of 503: * <code>clear()</code>. 504: * Please, note that this method is extremely slow (unless the argument has 505: * <code>size == 0</code>) and has bad performance is both space and time 506: * usage. 507: * 508: * @param c the collection containing the elements to be retained by this 509: * list. 510: * @return true the list internal storage changed as a result of this 511: * operation, false otherwise. 512: */ 513: public synchronized boolean retainAll(Collection<?> c) 514: { 515: // if the given collection does not contain elements 516: // we remove all the elements from our storage 517: if (c.size() == 0) 518: { 519: this.clear(); 520: return true; 521: } 522: 523: E [] snapshot = this.data; 524: E [] storage = (E[]) new Object[this.data.length]; 525: 526: int length = 0; 527: for (E element : snapshot) 528: { 529: if (c.contains(element)) 530: storage[length++] = element; 531: } 532: 533: // means we retained all the elements previously in our storage 534: // we are running already slow here, but at least we avoid copying 535: // another array and changing the internal storage 536: if (length == snapshot.length) 537: return false; 538: 539: E[] newData = (E[]) new Object[length]; 540: System.arraycopy(storage, 0, newData, 0, length); 541: 542: this.data = newData; 543: 544: return true; 545: } 546: 547: /** 548: * Removes all elements from this List 549: */ 550: public synchronized void clear() 551: { 552: data = (E[]) new Object[0]; 553: } 554: 555: /** 556: * Add each element in the supplied Collection to this List. It is undefined 557: * what happens if you modify the list while this is taking place; for 558: * example, if the collection contains this list. c can contain objects of any 559: * type, as well as null values. 560: * 561: * @param c 562: * a Collection containing elements to be added to this List 563: * @return true if the list was modified, in other words c is not empty 564: * @throws NullPointerException 565: * if c is null 566: */ 567: public synchronized boolean addAll(Collection< ? extends E> c) 568: { 569: return addAll(data.length, c); 570: } 571: 572: /** 573: * Add all elements in the supplied collection, inserting them beginning at 574: * the specified index. c can contain objects of any type, as well as null 575: * values. 576: * 577: * @param index 578: * the index at which the elements will be inserted 579: * @param c 580: * the Collection containing the elements to be inserted 581: * @throws IndexOutOfBoundsException 582: * if index < 0 || index > 0 583: * @throws NullPointerException 584: * if c is null 585: */ 586: public synchronized boolean addAll(int index, Collection< ? extends E> c) 587: { 588: if (index < 0 || index > this.size()) 589: throw new IndexOutOfBoundsException("index = " + index); 590: 591: int csize = c.size(); 592: if (csize == 0) 593: return false; 594: 595: E[] data = this.data; 596: Iterator<? extends E> itr = c.iterator(); 597: 598: E[] newData = (E[]) new Object[data.length + csize]; 599: 600: // avoid this call at all if we were asked to put the elements at the 601: // beginning of our storage 602: if (index != 0) 603: System.arraycopy(data, 0, newData, 0, index); 604: 605: int itemsLeft = index; 606: 607: for (E value : c) 608: newData[index++] = value; 609: 610: // now copy the remaining elements 611: System.arraycopy(data, itemsLeft, newData, 0, data.length - itemsLeft); 612: 613: this.data = newData; 614: 615: return true; 616: } 617: 618: /** 619: * Adds an element if the list does not contains it already. 620: * 621: * @param val the element to add to the list. 622: * @return true if the element was added, false otherwise. 623: */ 624: public synchronized boolean addIfAbsent(E val) 625: { 626: if (contains(val)) 627: return false; 628: add(val); 629: return true; 630: } 631: 632: /** 633: * Adds all the element from the given collection that are not already 634: * in this list. 635: * 636: * @param c the Collection containing the elements to be inserted 637: * @return true the list internal storage changed as a result of this 638: * operation, false otherwise. 639: */ 640: public synchronized int addAllAbsent(Collection<? extends E> c) 641: { 642: int size = c.size(); 643: if (size == 0) 644: return 0; 645: 646: E [] snapshot = this.data; 647: E [] storage = (E[]) new Object[size]; 648: 649: size = 0; 650: for (E val : c) 651: { 652: if (!this.contains(val)) 653: storage[size++] = val; 654: } 655: 656: if (size == 0) 657: return 0; 658: 659: // append storage to data 660: E [] newData = (E[]) new Object[snapshot.length + size]; 661: 662: System.arraycopy(snapshot, 0, newData, 0, snapshot.length); 663: System.arraycopy(storage, 0, newData, snapshot.length, size); 664: 665: this.data = newData; 666: 667: return size; 668: } 669: 670: /** 671: * Return an Iterator containing the elements of this list. 672: * The Iterator uses a snapshot of the state of the internal storage 673: * at the moment this method is called and does <strong>not</strong> support 674: * update operations, so no synchronization is needed to traverse the 675: * iterator. 676: * 677: * @return an Iterator containing the elements of this list in sequence. 678: */ 679: public Iterator<E> iterator() 680: { 681: return new Iterator<E>() 682: { 683: E [] iteratorData = CopyOnWriteArrayList.this.data; 684: int currentElement = 0; 685: 686: public boolean hasNext() 687: { 688: return (currentElement < iteratorData.length); 689: } 690: 691: public E next() 692: { 693: return iteratorData[currentElement++]; 694: } 695: 696: public void remove() 697: { 698: throw new UnsupportedOperationException("updating of elements in " + 699: "iterators is not supported " + 700: "by this class"); 701: } 702: }; 703: } 704: 705: /** 706: * Return a ListIterator containing the elements of this list. 707: * The Iterator uses a snapshot of the state of the internal storage 708: * at the moment this method is called and does <strong>not</strong> support 709: * update operations, so no synchronization is needed to traverse the 710: * iterator. 711: * 712: * @return a ListIterator containing the elements of this list in sequence. 713: */ 714: public ListIterator<E> listIterator(final int index) 715: { 716: if (index < 0 || index > size()) 717: throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 718: + size()); 719: 720: return new ListIterator<E>() 721: { 722: E [] iteratorData = CopyOnWriteArrayList.this.data; 723: int currentElement = index; 724: 725: public void add(E o) 726: { 727: throw new UnsupportedOperationException("updating of elements in " + 728: "iterators is not supported " + 729: "by this class"); 730: } 731: 732: public boolean hasNext() 733: { 734: return (currentElement < iteratorData.length); 735: } 736: 737: public boolean hasPrevious() 738: { 739: return (currentElement > 0); 740: } 741: 742: public E next() 743: { 744: if (hasNext() == false) 745: throw new java.util.NoSuchElementException(); 746: 747: return iteratorData[currentElement++]; 748: } 749: 750: public int nextIndex() 751: { 752: return (currentElement + 1); 753: } 754: 755: public E previous() 756: { 757: if (hasPrevious() == false) 758: throw new java.util.NoSuchElementException(); 759: 760: return iteratorData[--currentElement]; 761: } 762: 763: public int previousIndex() 764: { 765: return (currentElement - 1); 766: } 767: 768: public void remove() 769: { 770: throw new UnsupportedOperationException("updating of elements in " + 771: "iterators is not supported " + 772: "by this class"); 773: } 774: 775: public void set(E o) 776: { 777: throw new UnsupportedOperationException("updating of elements in " + 778: "iterators is not supported " + 779: "by this class"); 780: } 781: 782: }; 783: } 784: 785: /** 786: * Serializes this object to the given stream. 787: * 788: * @param s 789: * the stream to write to 790: * @throws IOException 791: * if the underlying stream fails 792: * @serialData the size field (int), the length of the backing array (int), 793: * followed by its elements (Objects) in proper order. 794: */ 795: private void writeObject(ObjectOutputStream s) throws IOException 796: { 797: // The 'size' field. 798: s.defaultWriteObject(); 799: // We serialize unused list entries to preserve capacity. 800: int len = data.length; 801: s.writeInt(len); 802: // it would be more efficient to just write "size" items, 803: // this need readObject read "size" items too. 804: for (int i = 0; i < data.length; i++) 805: s.writeObject(data[i]); 806: } 807: 808: /** 809: * Deserializes this object from the given stream. 810: * 811: * @param s 812: * the stream to read from 813: * @throws ClassNotFoundException 814: * if the underlying stream fails 815: * @throws IOException 816: * if the underlying stream fails 817: * @serialData the size field (int), the length of the backing array (int), 818: * followed by its elements (Objects) in proper order. 819: */ 820: private void readObject(ObjectInputStream s) throws IOException, 821: ClassNotFoundException 822: { 823: // the `size' field. 824: s.defaultReadObject(); 825: int capacity = s.readInt(); 826: data = (E[]) new Object[capacity]; 827: for (int i = 0; i < capacity; i++) 828: data[i] = (E) s.readObject(); 829: } 830: 831: static final boolean equals(Object o1, Object o2) 832: { 833: return o1 == null ? o2 == null : o1.equals(o2); 834: } 835: 836: Object[] getArray() 837: { 838: return data; 839: } 840: }
| GNU Classpath (0.97.1) |