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 }