copyonwritearraylist.java

来自「SRI international 发布的OAA框架软件」· Java 代码 · 共 1,179 行 · 第 1/3 页

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group.  Adapted and released, under explicit permission,
 * from JDK ArrayList.java which carries the following copyright:
 *
 * Copyright 1997 by Sun Microsystems, Inc.,
 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information
 * of Sun Microsystems, Inc. ("Confidential Information").  You
 * shall not disclose such Confidential Information and shall use
 * it only in accordance with the terms of the license agreement
 * you entered into with Sun.
 */

package edu.emory.mathcs.backport.java.util.concurrent;

import java.util.*;

/**
 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
 * operations (add, set, and so on) are implemented by making a fresh
 * copy of the underlying array.
 *
 * <p> This is ordinarily too costly, but may be <em>more</em> efficient
 * than alternatives when traversal operations vastly outnumber
 * mutations, and is useful when you cannot or don't want to
 * synchronize traversals, yet need to preclude interference among
 * concurrent threads.  The "snapshot" style iterator method uses a
 * reference to the state of the array at the point that the iterator
 * was created. This array never changes during the lifetime of the
 * iterator, so interference is impossible and the iterator is
 * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
 * The iterator will not reflect additions, removals, or changes to
 * the list since the iterator was created.  Element-changing
 * operations on iterators themselves (remove, set, and add) are not
 * supported. These methods throw
 * <tt>UnsupportedOperationException</tt>.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @since 1.5
 * @author Doug Lea
 */
public class CopyOnWriteArrayList
        implements List, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /**
     * The held array. Directly accessed only within synchronized
     *  methods
     */
    private volatile transient Object[] array;

    /**
     * Accessor to the array intended to be called from
     * within unsynchronized read-only methods
     **/
    private Object[] array() { return array; }

    /**
     * Creates an empty list.
     */
    public CopyOnWriteArrayList() {
        array = (Object[]) new Object[0];
    }

    /**
     * Creates a list containing the elements of the specified
     * Collection, in the order they are returned by the Collection's
     * iterator.
     * @param c the collection of initially held elements
     */
    public CopyOnWriteArrayList(Collection c) {
        array = (Object[]) new Object[c.size()];
        Iterator i = c.iterator();
        int size = 0;
        while (i.hasNext())
            array[size++] = i.next();
    }

    /**
     * Create a new CopyOnWriteArrayList holding a copy of given array.
     *
     * @param toCopyIn the array (a copy of this array is used as the
     *        internal array)
     **/
    public CopyOnWriteArrayList(Object[] toCopyIn) {
        copyIn(toCopyIn, 0, toCopyIn.length);
    }

    /**
     * Replace the held array with a copy of the <tt>n</tt> elements
     * of the provided array, starting at position <tt>first</tt>.  To
     * copy an entire array, call with arguments (array, 0,
     * array.length).
     * @param toCopyIn the array. A copy of the indicated elements of
     * this array is used as the internal array.
     * @param first The index of first position of the array to
     * start copying from.
     * @param n the number of elements to copy. This will be the new size of
     * the list.
     **/
    private synchronized void copyIn(Object[] toCopyIn, int first, int n) {
        array  = (Object[]) new Object[n];
        System.arraycopy(toCopyIn, first, array, 0, n);
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return  the number of elements in this list.
     */
    public int size() {
        return array().length;
    }

    /**
     * Tests if this list has no elements.
     *
     * @return  <tt>true</tt> if this list has no elements;
     *          <tt>false</tt> otherwise.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Returns <tt>true</tt> if this list contains the specified element.
     *
     * @param elem element whose presence in this List is to be tested.
     * @return  <code>true</code> if the specified element is present;
     *          <code>false</code> otherwise.
     */
    public boolean contains(Object elem) {
        Object[] elementData = array();
        int len = elementData.length;
        return indexOf(elem, elementData, len) >= 0;
    }

    /**
     * Searches for the first occurrence of the given argument, testing
     * for equality using the <tt>equals</tt> method.
     *
     * @param   elem   an object.
     * @return  the index of the first occurrence of the argument in this
     *          list; returns <tt>-1</tt> if the object is not found.
     * @see     Object#equals(Object)
     */
    public int indexOf(Object elem) {
        Object[] elementData = array();
        int len = elementData.length;
        return indexOf(elem, elementData, len);
    }

    /**
     * static version allows repeated call without needed
     * to grab lock for array each time
     **/
    private static int indexOf(Object elem, Object[] elementData, int len) {
        if (elem == null) {
            for (int i = 0; i < len; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < len; i++)
                if (elem.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * Searches for the first occurrence of the given argument, beginning
     * the search at <tt>index</tt>, and testing for equality using
     * the <tt>equals</tt> method.
     *
     * @param   elem    an object.
     * @param   index   the index to start searching from.
     * @return  the index of the first occurrence of the object argument in
     *          this List at position <tt>index</tt> or later in the
     *          List; returns <tt>-1</tt> if the object is not found.
     * @see     Object#equals(Object)
     */
    public int indexOf(Object elem, int index) {
        Object[] elementData = array();
        int elementCount = elementData.length;

        if (elem == null) {
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index ; i < elementCount ; i++)
                if (elem.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * Returns the index of the last occurrence of the specified object in
     * this list.
     *
     * @param   elem   the desired element.
     * @return  the index of the last occurrence of the specified object in
     *          this list; returns -1 if the object is not found.
     */
    public int lastIndexOf(Object elem) {
        Object[] elementData = array();
        int len = elementData.length;
        return lastIndexOf(elem, elementData, len);
    }

    private static int lastIndexOf(Object elem, Object[] elementData, int len) {
        if (elem == null) {
            for (int i = len-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = len-1; i >= 0; i--)
                if (elem.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * Searches backwards for the specified object, starting from the
     * specified index, and returns an index to it.
     *
     * @param  elem    the desired element.
     * @param  index   the index to start searching from.
     * @return the index of the last occurrence of the specified object in this
     *          List at position less than index in the List;
     *          -1 if the object is not found.
     */
    public int lastIndexOf(Object elem, int index) {
        // needed in order to compile on 1.2b3
        Object[] elementData = array();
        if (elem == null) {
            for (int i = index; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index; i >= 0; i--)
                if (elem.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * Returns a shallow copy of this list.  (The elements themselves
     * are not copied.)
     *
     * @return  a clone of this list.
     */
    public Object clone() {
        try {
            Object[] elementData = array();
            CopyOnWriteArrayList v = (CopyOnWriteArrayList)super.clone();
            v.array = (Object[]) new Object[elementData.length];
            System.arraycopy(elementData, 0, v.array, 0, elementData.length);
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

    /**
     * Returns an array containing all of the elements in this list
     * in the correct order.
     * @return an array containing all of the elements in this list
     *         in the correct order.
     */
    public Object[] toArray() {
        Object[] elementData = array();
        Object[] result = new Object[elementData.length];
        System.arraycopy(elementData, 0, result, 0, elementData.length);
        return result;
    }

    /**
     * Returns an array containing all of the elements in this list in the
     * correct order.  The runtime type of the returned array is that of the
     * specified array.  If the list fits in the specified array, it is
     * returned therein.  Otherwise, a new array is allocated with the runtime
     * type of the specified array and the size of this list.
     * <p>
     * If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list),
     * the element in the array immediately following the end of the
     * collection is set to null.  This is useful in determining the length
     * of the list <em>only</em> if the caller knows that the list
     * does not contain any null elements.
     *
     * @param a the array into which the elements of the list are to
     *            be stored, if it is big enough; otherwise, a new array of the
     *            same runtime type is allocated for this purpose.
     * @return an array containing the elements of the list.
     * @throws ArrayStoreException the runtime type of a is not a supertype
     * of the runtime type of every element in this list.
     */
    public Object[] toArray(Object[] a) {
        Object[] elementData = array();

        if (a.length < elementData.length)
            a = (Object[])
            java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
            elementData.length);

        System.arraycopy(elementData, 0, a, 0, elementData.length);

        if (a.length > elementData.length)
            a[elementData.length] = null;

        return a;
    }

    // Positional Access Operations

    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of element to return.
     * @return the element at the specified position in this list.
     * @throws    IndexOutOfBoundsException if index is out of range <tt>(index
     *            &lt; 0 || index &gt;= size())</tt>.
     */
    public Object get(int index) {
        Object[] elementData = array();
        rangeCheck(index, elementData.length);
        return elementData[index];
    }

    /**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of element to replace.
     * @param element element to be stored at the specified position.
     * @return the element previously at the specified position.
     * @throws    IndexOutOfBoundsException if index out of range
     *            <tt>(index &lt; 0 || index &gt;= size())</tt>.
     */
    public synchronized Object set(int index, Object element) {
        int len = array.length;
        rangeCheck(index, len);
        Object oldValue = array[index];

        boolean same = (oldValue == element ||
        (element != null && element.equals(oldValue)));
        if (!same) {
            Object[] newArray = (Object[]) new Object[len];
            System.arraycopy(array, 0, newArray, 0, len);
            newArray[index] = element;
            array = newArray;
        }
        return oldValue;
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * @param element element to be appended to this list.
     * @return true (as per the general contract of Collection.add).
     */
    public synchronized boolean add(Object element) {
        int len = array.length;
        Object[] newArray = (Object[]) new Object[len+1];
        System.arraycopy(array, 0, newArray, 0, len);
        newArray[len] = element;
        array = newArray;
        return true;
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted.
     * @param element element to be inserted.
     * @throws    IndexOutOfBoundsException if index is out of range
     *            <tt>(index &lt; 0 || index &gt; size())</tt>.
     */
    public synchronized void add(int index, Object element) {
        int len = array.length;