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 import java.lang.reflect.Array; 045 import java.util.AbstractList; 046 import java.util.Collection; 047 import java.util.Iterator; 048 import java.util.List; 049 import java.util.RandomAccess; 050 051 /** @since 1.5 */ 052 public class CopyOnWriteArrayList<E> extends AbstractList<E> implements 053 List<E>, RandomAccess, Cloneable, Serializable 054 { 055 /** 056 * Where the data is stored. 057 */ 058 private transient E[] data; 059 060 /** 061 * Construct a new ArrayList with the default capacity (16). 062 */ 063 public CopyOnWriteArrayList() 064 { 065 data = (E[]) new Object[0]; 066 } 067 068 /** 069 * Construct a new ArrayList, and initialize it with the elements in the 070 * supplied Collection. The initial capacity is 110% of the Collection's size. 071 * 072 * @param c 073 * the collection whose elements will initialize this list 074 * @throws NullPointerException 075 * if c is null 076 */ 077 public CopyOnWriteArrayList(Collection< ? extends E> c) 078 { 079 // FIXME ... correct? use c.toArray() 080 data = (E[]) new Object[c.size()]; 081 int index = 0; 082 for (E value : c) 083 data[index++] = value; 084 } 085 086 /** 087 * Construct a new ArrayList, and initialize it with the elements in the 088 * supplied array. 089 * 090 * @param array 091 * the array used to initialize this list 092 * @throws NullPointerException 093 * if array is null 094 */ 095 public CopyOnWriteArrayList(E[] array) 096 { 097 data = (E[]) array.clone(); 098 } 099 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 = (E[]) 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 }