Jdk1.6 JUC源码解析(23)-CopyOnWriteArrayList、CopyOnWriteArraySet

Jdk1.6 JUC源码解析(23)-CopyOnWriteArrayList、CopyOnWriteArraySet

作者：大飞

 

功能简介：

• CopyOnWriteArrayList是一种线程安全的ArrayList。顾名思义，有写操作时，就会copy一个新的内部数组出来替换掉旧的数组。这样做的好处是，遍历操作不用加锁了，但是遍历的数组不会感知即时变更，只是一个快照。在某些场景下，这要比不用CopyOnWrite，读写都加锁的实现方式要高效一些。CopyOnWriteArrayList一般使用在读多写少的场景。
• CopyOnWriteArraySet由内部的一个CopyOnWriteArrayList来代理实现。

 

源码分析：

• 先看下CopyOnWriteArrayList的内部结构：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;
    /** The lock protecting all mutators */
    transient final ReentrantLock lock = new ReentrantLock();
    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;
    /**
     * Gets the array.  Non-private so as to also be accessible
     * from CopyOnWriteArraySet class.
     */
    final Object[] getArray() {
        return array;
    }
    /**
     * Sets the array.
     */
    final void setArray(Object[] a) {
        array = a;
    }

       内部结构一目了然，一个锁，一个数组。注意数组由volatile修饰。内部数组只能通过getArray和setArray来操作。

 

• 继续看下CopyOnWriteArrayList的"写"系列方法：

    public E set(int index, E element) {
	    final ReentrantLock lock = this.lock;
	    lock.lock();
	    try {
	        Object[] elements = getArray();
	        Object oldValue = elements[index];
            //新值和旧值做对比。
	        if (oldValue != element) {
                //如果不相等，需要从旧数组拷贝一份新数组，然后设置新值，设置为内部数组。
		        int len = elements.length;
		        Object[] newElements = Arrays.copyOf(elements, len);
		        newElements[index] = element;
		        setArray(newElements);
	        } else {
		        //这里保证volatile写的语义。
		        setArray(elements);
	        }
	        return (E)oldValue;
	    } finally {
	        lock.unlock();
	    }
    }

 

    public boolean add(E e) {
	    final ReentrantLock lock = this.lock;
	    lock.lock();
	    try {
	        Object[] elements = getArray();
	        int len = elements.length;
            //拷贝一份新数组，同时增加一个单位的长度，设置新值，设置为内部数组。
	        Object[] newElements = Arrays.copyOf(elements, len + 1);
	        newElements[len] = e;
	        setArray(newElements);
	        return true;
	    } finally {
	        lock.unlock();
	    }
    }

 

    public void add(int index, E element) {
	    final ReentrantLock lock = this.lock;
	    lock.lock();
	    try {
	        Object[] elements = getArray();
	        int len = elements.length;
	        if (index > len || index < 0)
		        throw new IndexOutOfBoundsException("Index: "+index+
						    ", Size: "+len);
	        Object[] newElements;
	        int numMoved = len - index;
	        if (numMoved == 0)//如果是往数组末尾添加元素，直接拷贝，同时增加一个单位的长度。
		        newElements = Arrays.copyOf(elements, len + 1);
	        else {//如果不是往数组末尾插入一个元素，分两段拷贝。
		        newElements = new Object[len + 1];
		        System.arraycopy(elements, 0, newElements, 0, index);
		        System.arraycopy(elements, index, newElements, index + 1, numMoved);
	        }
            //设置新值，设置为内部数组。
	        newElements[index] = element;
	        setArray(newElements);
	    } finally {
	        lock.unlock();
	    }
    }

 

    public E remove(int index) {
	    final ReentrantLock lock = this.lock;
	    lock.lock();
	    try {
	        Object[] elements = getArray();
	        int len = elements.length;
	        Object oldValue = elements[index];
	        int numMoved = len - index - 1;
	        if (numMoved == 0)//如果要删除的是数组末尾的元素，直接拷贝，同时减少一个单位的长度。然后设置为内部数组。
		        setArray(Arrays.copyOf(elements, len - 1));
	        else {//如果不是删除数组末尾的元素，分两段拷贝，然后设置为内部数组。
		        Object[] newElements = new Object[len - 1];
		        System.arraycopy(elements, 0, newElements, 0, index);
		        System.arraycopy(elements, index + 1, newElements, index, numMoved);
		        setArray(newElements);
	        }
	        return (E)oldValue;
	    } finally {
	        lock.unlock();
	    }
    }

 

    public boolean remove(Object o) {
	    final ReentrantLock lock = this.lock;
	    lock.lock();
	    try {
	        Object[] elements = getArray();
	        int len = elements.length;
	        if (len != 0) {
		        // 假设数组中存在o，那么删除后的长度是len - 1，所以先处理len - 1个元素
		        int newlen = len - 1;
                // 建立一个新数组，长度为len - 1
		        Object[] newElements = new Object[newlen];
		        for (int i = 0; i < newlen; ++i) {
		            if (eq(o, elements[i])) {
			            // 发现了目标元素，跳过这个元素拷贝剩下的元素到新数组。
			            for (int k = i + 1; k < len; ++k)
			                newElements[k-1] = elements[k];
			            setArray(newElements);
			            return true;
		            } else
			            newElements[i] = elements[i];
		        }
		        // 如果到这里的话，说明前len - 1个元素中都没找到o，那么看看最后一个元素是否为o。
		        if (eq(o, elements[newlen])) {
                    //如果是，直接设置新数组就可以了，因为最后一个元素不在新数组里。
		            setArray(newElements);
		            return true;
		        }
	        }
	        return false;
	    } finally {
	        lock.unlock();
	    }
    }

       可见，所有的写操作都会拷贝另外一份内部数组出来，然后替换之前的内部数组，这里也会存在一个内存占用的问题，使用的时候应当注意。其他的写操作都很容易看懂，这里不罗嗦了。

 

• 读操作很简答：

    public E get(int index) {
        return (E)(getArray()[index]);
    }

 

• 再看下迭代器相关：

    public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

    public ListIterator<E> listIterator() {
        return new COWIterator<E>(getArray(), 0);
    }
    private static class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array **/
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;
        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
        public boolean hasNext() {
            return cursor < snapshot.length;
        }
        public boolean hasPrevious() {
            return cursor > 0;
        }
        public E next() {
	    if (! hasNext())
                throw new NoSuchElementException();
	    return (E) snapshot[cursor++];
        }
        public E previous() {
	    if (! hasPrevious())
                throw new NoSuchElementException();
	    return (E) snapshot[--cursor];
        }
        public int nextIndex() {
            return cursor;
        }
        public int previousIndex() {
            return cursor-1;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public void set(E e) {
            throw new UnsupportedOperationException();
        }

        public void add(E e) {
            throw new UnsupportedOperationException();
        }
    }

       注意创建迭代器的时候将当时的array赋予迭代器内部的域，相当于是获取了一个快照，所以遍历的时候不需要加锁，但不支持迭代器上的写操作(写方法都会抛出异常)。

 

• 没有涉及到的部分，代码都比较容易理解，这里不说了。最后看下CopyOnWriteArraySet，代码很简单：

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;
    private final CopyOnWriteArrayList<E> al;

    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    public CopyOnWriteArraySet(Collection<? extends E> c) {
        al = new CopyOnWriteArrayList<E>();
        al.addAllAbsent(c);
    }

    public int size() {
	    return al.size();
    }

    public boolean isEmpty() {
	    return al.isEmpty();
    }

    public boolean contains(Object o) {
	    return al.contains(o);
    }

    public Object[] toArray() {
	    return al.toArray();
    }

    public <T> T[] toArray(T[] a) {
	    return al.toArray(a);
    }

    public void clear() {
        al.clear();
    }

    public boolean remove(Object o) {
	    return al.remove(o);
    }

    public boolean add(E e) {
	    return al.addIfAbsent(e);
    }
    ...

       内部一个CopyOnWriteArrayList，方法都由内部的CopyOnWriteArrayList来实现。

 

 

       ok，代码解析完毕！ 

 

       

       参见：Jdk1.6 JUC源码解析(7)-locks-ReentrantLock