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: import java.lang.reflect.Array; 45: import java.util.AbstractList; 46: import java.util.Collection; 47: import java.util.Iterator; 48: import java.util.List; 49: import java.util.RandomAccess; 50: 51: /** @since 1.5 */ 52: public class CopyOnWriteArrayList<E> extends AbstractList<E> implements 53: List<E>, RandomAccess, Cloneable, Serializable 54: { 55: /** 56: * Where the data is stored. 57: */ 58: private transient E[] data; 59: 60: /** 61: * Construct a new ArrayList with the default capacity (16). 62: */ 63: public CopyOnWriteArrayList() 64: { 65: data = (E[]) new Object[0]; 66: } 67: 68: /** 69: * Construct a new ArrayList, and initialize it with the elements in the 70: * supplied Collection. The initial capacity is 110% of the Collection's size. 71: * 72: * @param c 73: * the collection whose elements will initialize this list 74: * @throws NullPointerException 75: * if c is null 76: */ 77: public CopyOnWriteArrayList(Collection< ? extends E> c) 78: { 79: // FIXME ... correct? use c.toArray() 80: data = (E[]) new Object[c.size()]; 81: int index = 0; 82: for (E value : c) 83: data[index++] = value; 84: } 85: 86: /** 87: * Construct a new ArrayList, and initialize it with the elements in the 88: * supplied array. 89: * 90: * @param array 91: * the array used to initialize this list 92: * @throws NullPointerException 93: * if array is null 94: */ 95: public CopyOnWriteArrayList(E[] array) 96: { 97: data = array.clone(); 98: } 99: 100: /** 101: * Returns the number of elements in this list. 102: * 103: * @return the list size 104: */ 105: public int size() 106: { 107: return data.length; 108: } 109: 110: /** 111: * Checks if the list is empty. 112: * 113: * @return true if there are no elements 114: */ 115: public boolean isEmpty() 116: { 117: return data.length == 0; 118: } 119: 120: /** 121: * Returns true iff element is in this ArrayList. 122: * 123: * @param e 124: * the element whose inclusion in the List is being tested 125: * @return true if the list contains e 126: */ 127: public boolean contains(Object e) 128: { 129: return indexOf(e) != -1; 130: } 131: 132: /** 133: * Returns the lowest index at which element appears in this List, or -1 if it 134: * does not appear. 135: * 136: * @param e 137: * the element whose inclusion in the List is being tested 138: * @return the index where e was found 139: */ 140: public int indexOf(Object e) 141: { 142: E[] data = this.data; 143: for (int i = 0; i < data.length; i++) 144: if (equals(e, data[i])) 145: return i; 146: return -1; 147: } 148: 149: /** 150: * Return the lowest index greater equal <code>index</code> at which 151: * <code>e</code> appears in this List, or -1 if it does not 152: * appear. 153: * 154: * @param e the element whose inclusion in the list is being tested 155: * @param index the index at which the search begins 156: * @return the index where <code>e</code> was found 157: */ 158: public int indexOf(E e, int index) 159: { 160: E[] data = this.data; 161: 162: for (int i = index; i < data.length; i++) 163: if (equals(e, data[i])) 164: return i; 165: return -1; 166: } 167: 168: /** 169: * Returns the highest index at which element appears in this List, or -1 if 170: * it does not appear. 171: * 172: * @param e 173: * the element whose inclusion in the List is being tested 174: * @return the index where e was found 175: */ 176: public int lastIndexOf(Object e) 177: { 178: E[] data = this.data; 179: for (int i = data.length - 1; i >= 0; i--) 180: if (equals(e, data[i])) 181: return i; 182: return -1; 183: } 184: 185: /** 186: * Returns the highest index lesser equal <code>index</code> at 187: * which <code>e</code> appears in this List, or -1 if it does not 188: * appear. 189: * 190: * @param e the element whose inclusion in the list is being tested 191: * @param index the index at which the search begins 192: * @return the index where <code>e</code> was found 193: */ 194: public int lastIndexOf(E e, int index) 195: { 196: E[] data = this.data; 197: 198: for (int i = index; i >= 0; i--) 199: if (equals(e, data[i])) 200: return i; 201: return -1; 202: } 203: 204: /** 205: * Creates a shallow copy of this ArrayList (elements are not cloned). 206: * 207: * @return the cloned object 208: */ 209: public Object clone() 210: { 211: CopyOnWriteArrayList<E> clone = null; 212: try 213: { 214: clone = (CopyOnWriteArrayList<E>) super.clone(); 215: clone.data = (E[]) data.clone(); 216: } 217: catch (CloneNotSupportedException e) 218: { 219: // Impossible to get here. 220: } 221: return clone; 222: } 223: 224: /** 225: * Returns an Object array containing all of the elements in this ArrayList. 226: * The array is independent of this list. 227: * 228: * @return an array representation of this list 229: */ 230: public Object[] toArray() 231: { 232: E[] data = this.data; 233: E[] array = (E[]) new Object[data.length]; 234: System.arraycopy(data, 0, array, 0, data.length); 235: return array; 236: } 237: 238: /** 239: * Returns an Array whose component type is the runtime component type of the 240: * passed-in Array. The returned Array is populated with all of the elements 241: * in this ArrayList. If the passed-in Array is not large enough to store all 242: * of the elements in this List, a new Array will be created and returned; if 243: * the passed-in Array is <i>larger</i> than the size of this List, then 244: * size() index will be set to null. 245: * 246: * @param a 247: * the passed-in Array 248: * @return an array representation of this list 249: * @throws ArrayStoreException 250: * if the runtime type of a does not allow an element in this list 251: * @throws NullPointerException 252: * if a is null 253: */ 254: public <T> T[] toArray(T[] a) 255: { 256: E[] data = this.data; 257: if (a.length < data.length) 258: a = (T[]) Array.newInstance(a.getClass().getComponentType(), data.length); 259: else if (a.length > data.length) 260: a[data.length] = null; 261: System.arraycopy(data, 0, a, 0, data.length); 262: return a; 263: } 264: 265: /** 266: * Retrieves the element at the user-supplied index. 267: * 268: * @param index 269: * the index of the element we are fetching 270: * @throws IndexOutOfBoundsException 271: * if index < 0 || index >= size() 272: */ 273: public E get(int index) 274: { 275: return data[index]; 276: } 277: 278: /** 279: * Sets the element at the specified index. The new element, e, can be an 280: * object of any type or null. 281: * 282: * @param index 283: * the index at which the element is being set 284: * @param e 285: * the element to be set 286: * @return the element previously at the specified index 287: * @throws IndexOutOfBoundsException 288: * if index < 0 || index >= 0 289: */ 290: public synchronized E set(int index, E e) 291: { 292: E result = data[index]; 293: E[] newData = data.clone(); 294: newData[index] = e; 295: data = newData; 296: return result; 297: } 298: 299: /** 300: * Appends the supplied element to the end of this list. The element, e, can 301: * be an object of any type or null. 302: * 303: * @param e 304: * the element to be appended to this list 305: * @return true, the add will always succeed 306: */ 307: public synchronized boolean add(E e) 308: { 309: E[] data = this.data; 310: E[] newData = (E[]) new Object[data.length + 1]; 311: System.arraycopy(data, 0, newData, 0, data.length); 312: newData[data.length] = e; 313: this.data = newData; 314: return true; 315: } 316: 317: /** 318: * Adds the supplied element at the specified index, shifting all elements 319: * currently at that index or higher one to the right. The element, e, can be 320: * an object of any type or null. 321: * 322: * @param index 323: * the index at which the element is being added 324: * @param e 325: * the item being added 326: * @throws IndexOutOfBoundsException 327: * if index < 0 || index > size() 328: */ 329: public synchronized void add(int index, E e) 330: { 331: E[] data = this.data; 332: E[] newData = (E[]) new Object[data.length + 1]; 333: System.arraycopy(data, 0, newData, 0, index); 334: newData[index] = e; 335: System.arraycopy(data, index, newData, index + 1, data.length - index); 336: this.data = newData; 337: } 338: 339: /** 340: * Removes the element at the user-supplied index. 341: * 342: * @param index 343: * the index of the element to be removed 344: * @return the removed Object 345: * @throws IndexOutOfBoundsException 346: * if index < 0 || index >= size() 347: */ 348: public synchronized E remove(int index) 349: { 350: E[] data = this.data; 351: E[] newData = (E[]) new Object[data.length - 1]; 352: if (index > 0) 353: System.arraycopy(data, 0, newData, 0, index - 1); 354: System.arraycopy(data, index + 1, newData, index, 355: data.length - index - 1); 356: E r = data[index]; 357: this.data = newData; 358: return r; 359: } 360: 361: /** 362: * Removes all elements from this List 363: */ 364: public synchronized void clear() 365: { 366: data = (E[]) new Object[0]; 367: } 368: 369: /** 370: * Add each element in the supplied Collection to this List. It is undefined 371: * what happens if you modify the list while this is taking place; for 372: * example, if the collection contains this list. c can contain objects of any 373: * type, as well as null values. 374: * 375: * @param c 376: * a Collection containing elements to be added to this List 377: * @return true if the list was modified, in other words c is not empty 378: * @throws NullPointerException 379: * if c is null 380: */ 381: public synchronized boolean addAll(Collection< ? extends E> c) 382: { 383: return addAll(data.length, c); 384: } 385: 386: /** 387: * Add all elements in the supplied collection, inserting them beginning at 388: * the specified index. c can contain objects of any type, as well as null 389: * values. 390: * 391: * @param index 392: * the index at which the elements will be inserted 393: * @param c 394: * the Collection containing the elements to be inserted 395: * @throws IndexOutOfBoundsException 396: * if index < 0 || index > 0 397: * @throws NullPointerException 398: * if c is null 399: */ 400: public synchronized boolean addAll(int index, Collection< ? extends E> c) 401: { 402: E[] data = this.data; 403: Iterator<? extends E> itr = c.iterator(); 404: int csize = c.size(); 405: if (csize == 0) 406: return false; 407: 408: E[] newData = (E[]) new Object[data.length + csize]; 409: System.arraycopy(data, 0, newData, 0, data.length); 410: int end = data.length; 411: for (E value : c) 412: newData[end++] = value; 413: this.data = newData; 414: return true; 415: } 416: 417: public synchronized boolean addIfAbsent(E val) 418: { 419: if (contains(val)) 420: return false; 421: add(val); 422: return true; 423: } 424: 425: public synchronized int addAllAbsent(Collection<? extends E> c) 426: { 427: int result = 0; 428: for (E val : c) 429: { 430: if (addIfAbsent(val)) 431: ++result; 432: } 433: return result; 434: } 435: 436: /** 437: * Serializes this object to the given stream. 438: * 439: * @param s 440: * the stream to write to 441: * @throws IOException 442: * if the underlying stream fails 443: * @serialData the size field (int), the length of the backing array (int), 444: * followed by its elements (Objects) in proper order. 445: */ 446: private void writeObject(ObjectOutputStream s) throws IOException 447: { 448: // The 'size' field. 449: s.defaultWriteObject(); 450: // We serialize unused list entries to preserve capacity. 451: int len = data.length; 452: s.writeInt(len); 453: // it would be more efficient to just write "size" items, 454: // this need readObject read "size" items too. 455: for (int i = 0; i < data.length; i++) 456: s.writeObject(data[i]); 457: } 458: 459: /** 460: * Deserializes this object from the given stream. 461: * 462: * @param s 463: * the stream to read from 464: * @throws ClassNotFoundException 465: * if the underlying stream fails 466: * @throws IOException 467: * if the underlying stream fails 468: * @serialData the size field (int), the length of the backing array (int), 469: * followed by its elements (Objects) in proper order. 470: */ 471: private void readObject(ObjectInputStream s) throws IOException, 472: ClassNotFoundException 473: { 474: // the `size' field. 475: s.defaultReadObject(); 476: int capacity = s.readInt(); 477: data = (E[]) new Object[capacity]; 478: for (int i = 0; i < capacity; i++) 479: data[i] = (E) s.readObject(); 480: } 481: 482: static final boolean equals(Object o1, Object o2) 483: { 484: return o1 == null ? o2 == null : o1.equals(o2); 485: } 486: 487: Object[] getArray() 488: { 489: return data; 490: } 491: }