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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt; 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 &lt; 0 || index &gt;= 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 &lt; 0 || index &gt; 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    }