libjava/classpath/java/util/concurrent/CopyOnWriteArrayList.java

   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 = (E[]) 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 &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     System.arraycopy(data, 0, newData, 0, index - 1);
 353     System.arraycopy(data, index + 1, newData, index,
 354                      data.length - index - 1);
 355     E r = data[index];
 356     this.data = newData;
 357     return r;
 358   }
 359
 360   /**
 361    * Removes all elements from this List
 362    */
 363   public synchronized void clear()
 364   {
 365     data = (E[]) new Object[0];
 366   }
 367
 368   /**
 369    * Add each element in the supplied Collection to this List. It is undefined
 370    * what happens if you modify the list while this is taking place; for
 371    * example, if the collection contains this list. c can contain objects of any
 372    * type, as well as null values.
 373    *
 374    * @param c
 375    *          a Collection containing elements to be added to this List
 376    * @return true if the list was modified, in other words c is not empty
 377    * @throws NullPointerException
 378    *           if c is null
 379    */
 380   public synchronized boolean addAll(Collection< ? extends E> c)
 381   {
 382     return addAll(data.length, c);
 383   }
 384
 385   /**
 386    * Add all elements in the supplied collection, inserting them beginning at
 387    * the specified index. c can contain objects of any type, as well as null
 388    * values.
 389    *
 390    * @param index
 391    *          the index at which the elements will be inserted
 392    * @param c
 393    *          the Collection containing the elements to be inserted
 394    * @throws IndexOutOfBoundsException
 395    *           if index &lt; 0 || index &gt; 0
 396    * @throws NullPointerException
 397    *           if c is null
 398    */
 399   public synchronized boolean addAll(int index, Collection< ? extends E> c)
 400   {
 401     E[] data = this.data;
 402     Iterator<? extends E> itr = c.iterator();
 403     int csize = c.size();
 404     if (csize == 0)
 405       return false;
 406
 407     E[] newData = (E[]) new Object[data.length + csize];
 408     System.arraycopy(data, 0, newData, 0, data.length);
 409     int end = data.length;
 410     for (E value : c)
 411       newData[end++] = value;
 412     this.data = newData;
 413     return true;
 414   }
 415
 416   public synchronized boolean addIfAbsent(E val)
 417   {
 418     if (contains(val))
 419       return false;
 420     add(val);
 421     return true;
 422   }
 423
 424   public synchronized int addAllAbsent(Collection<? extends E> c)
 425   {
 426     int result = 0;
 427     for (E val : c)
 428       {
 429         if (addIfAbsent(val))
 430           ++result;
 431       }
 432     return result;
 433   }
 434
 435   /**
 436    * Serializes this object to the given stream.
 437    *
 438    * @param s
 439    *          the stream to write to
 440    * @throws IOException
 441    *           if the underlying stream fails
 442    * @serialData the size field (int), the length of the backing array (int),
 443    *             followed by its elements (Objects) in proper order.
 444    */
 445   private void writeObject(ObjectOutputStream s) throws IOException
 446   {
 447     // The 'size' field.
 448     s.defaultWriteObject();
 449     // We serialize unused list entries to preserve capacity.
 450     int len = data.length;
 451     s.writeInt(len);
 452     // it would be more efficient to just write "size" items,
 453     // this need readObject read "size" items too.
 454     for (int i = 0; i < data.length; i++)
 455       s.writeObject(data[i]);
 456   }
 457
 458   /**
 459    * Deserializes this object from the given stream.
 460    *
 461    * @param s
 462    *          the stream to read from
 463    * @throws ClassNotFoundException
 464    *           if the underlying stream fails
 465    * @throws IOException
 466    *           if the underlying stream fails
 467    * @serialData the size field (int), the length of the backing array (int),
 468    *             followed by its elements (Objects) in proper order.
 469    */
 470   private void readObject(ObjectInputStream s) throws IOException,
 471       ClassNotFoundException
 472   {
 473     // the `size' field.
 474     s.defaultReadObject();
 475     int capacity = s.readInt();
 476     data = (E[]) new Object[capacity];
 477     for (int i = 0; i < capacity; i++)
 478       data[i] = (E) s.readObject();
 479   }
 480
 481   static final boolean equals(Object o1, Object o2)
 482   {
 483     return o1 == null ? o2 == null : o1.equals(o2);
 484   }
 485
 486   Object[] getArray()
 487   {
 488     return data;
 489   }
 490 }