读CopyOnWriteArrayList源码_JAVA_编程开发_程序员俱乐部

class="java" name="code">
//在该集合上的写操作都是在原有的副本上进行的操作。这样可以在大量需要遍历的场景下提升性能。这也是一种读写分离思想的体现。
//先看构造函数
public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

  final void setArray(Object[] a) {
        array = a;
    }

 public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
        setArray(elements);
    }

 public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }


//添加元素
  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();
        }
    }

final Object[] getArray() {
        return array;
    }

//在指定位置插入某个元素原有元素向后移
 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;
	    //在len的位置上插入
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            
	    else {
                newElements = new Object[len + 1];
		//将elements数组从0开始的index个元素复制到newElements中。
                System.arraycopy(elements, 0, newElements, 0, index);
		从elements的index位置开始复制numMoved个元素到newElements中(从index+1位置开始)。
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
	    //设置index位置的值为element。
            newElements[index] = element;
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

//从集合中添加元素
public boolean addAll(Collection<? extends E> c) {
        Object[] cs = c.toArray();
        if (cs.length == 0)
            return false;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
	    //复制elemetns到newElements中。
            Object[] newElements = Arrays.copyOf(elements, len + cs.length);
	    //复制cs到newElements(从len位置开始复制)中。
            System.arraycopy(cs, 0, newElements, len, cs.length);
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

//从指定位置开始添加元素，原来位置的元素右移
 public boolean addAll(int index, Collection<? extends E> c) {
        Object[] cs = c.toArray();
        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);
            if (cs.length == 0)
                return false;
            int numMoved = len - index;
            Object[] newElements;
	    //刚好在len位置上插入元素
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + cs.length);
            else {
	        
                newElements = new Object[len + cs.length];
		//从0位置开始复制index个元素到newElements。
                System.arraycopy(elements, 0, newElements, 0, index);
		//从index位置开始复制numMoved个元素到newElements(从index + cs.length位置开始,numMoved个元素)中。
                System.arraycopy(elements, index,
                                 newElements, index + cs.length,
                                 numMoved);
            }
	    //cs的0位置开始复制cs个元素到newElements(从index位置开始,cs.length个元素)中。
            System.arraycopy(cs, 0, newElements, index, cs.length);
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

//如何元素不存在则添加元素
public boolean addIfAbsent(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            // Copy while checking if already present.
            // This wins in the most common case where it is not present
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = new Object[len + 1];
            for (int i = 0; i < len; ++i) {
                if (eq(e, elements[i]))
                    return false; // exit, throwing away copy
                else
                    newElements[i] = elements[i];
            }
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

   private static boolean eq(Object o1, Object o2) {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }

//将集合中不存在于数组中的元素进行插入。
 public int addAllAbsent(Collection<? extends E> c) {
        Object[] cs = c.toArray();
        if (cs.length == 0)
            return 0;
        Object[] uniq = new Object[cs.length];
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            int added = 0;
	    //循环遍历有哪些元素不存在数值中将这些不存在数组中的元素封装到uniq中。
            for (int i = 0; i < cs.length; ++i) { // scan for duplicates
                Object e = cs[i];
		//不在elements中并且不在uniq中。
                if (indexOf(e, elements, 0, len) < 0 &&
		//不在uniq中(防止c中有重复元素)
                    indexOf(e, uniq, 0, added) < 0)
                    uniq[added++] = e;
            }
	    //有值需要插入
            if (added > 0) {
                Object[] newElements = Arrays.copyOf(elements, len + added);
                System.arraycopy(uniq, 0, newElements, len, added);
                setArray(newElements);
            }
            return added;
        } finally {
            lock.unlock();
        }
    }

private static int indexOf(Object o, Object[] elements,
                               int index, int fence) {
        if (o == null) {
            for (int i = index; i < fence; i++)
                if (elements[i] == null)
                    return i;
        } else {
            for (int i = index; i < fence; i++)
                if (o.equals(elements[i]))
                    return i;
        }
        return -1;
    }

 //在指定位置插入元素
 public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);
            //如果插入的值和原来的值不相等
            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                //这里很奇怪元素都没有修改为什么需要setArray()?这主要是为了保证外部非volatile变量的happy-before语义。详见
		//https://stackoverflow.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

private E get(Object[] a, int index) {
        return (E) a[index];
    }

//删除指定位置的元素,数组中的其他元素前移
 public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
	    //删除的是尾元素。
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
		//从0开始复制index个元素到newElements。
                System.arraycopy(elements, 0, newElements, 0, index);
	        //再从index + 1位置复制numMoved个元素到newElements(从index位置开始接受)中。
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return 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) {
                // Copy while searching for element to remove
                // This wins in the normal case of element being present
                int newlen = len - 1;
                Object[] newElements = new Object[newlen];

                for (int i = 0; i < newlen; ++i) {
	            //找到了
                    if (eq(o, elements[i])) {
                        // found one;  copy remaining and exit
			//从i位置开始复制
                        for (int k = i + 1; k < len; ++k)
                            newElements[k-1] = elements[k];
                        setArray(newElements);
                        return true;
                    } else
		        //没有找到直接复制过去
                        newElements[i] = elements[i];
                }
                //如果删除的元素位于数组尾部
                // special handling for last cell
                if (eq(o, elements[newlen])) {
                    setArray(newElements);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

//从数组中移除包含在c中的元素
   public boolean removeAll(Collection<?> c){
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (len != 0) {
                // temp array holds those elements we know we want to keep
                int newlen = 0;
		//这里面保存最后剩下的元素
                Object[] temp = new Object[len];
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
		    //如果c中不包含当前元素
                    if (!c.contains(element))
                        temp[newlen++] = element;
                }
		//如果长度不相等说明有元素被移除了
                if (newlen != len) {
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

//只保存存在collection中的元素
 public boolean retainAll(Collection<?> c) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (len != 0) {
                // temp array holds those elements we know we want to keep
                int newlen = 0;
                Object[] temp = new Object[len];
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
                    if (c.contains(element))
                        temp[newlen++] = element;
                }
                if (newlen != len) {
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }
//从列表中移除所有元素
public void clear() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            setArray(new Object[0]);
        } finally {
            lock.unlock();
        }
    }

//是否包含某个元素
 public boolean contains(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length) >= 0;
    }


//是否包含指定集合的所有元素
 public boolean containsAll(Collection<?> c) {
        Object[] elements = getArray();
        int len = elements.length;
        for (Object e : c) {
            if (indexOf(e, elements, 0, len) < 0)
                return false;
        }
        return true;
    }

//返回该元素第一次出现的索引
 public int indexOf(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length);
    }
//从指定位置开始搜索该元素第一次出现的索引
 public int indexOf(E e, int index) {
        Object[] elements = getArray();
        return indexOf(e, elements, index, elements.length);
    }
//从尾部开始搜索
public int lastIndexOf(Object o) {
        Object[] elements = getArray();
        return lastIndexOf(o, elements, elements.length - 1);
    }

//返回最后一次出现在列表中的索引
public int lastIndexOf(E e, int index) {
        Object[] elements = getArray();
        return lastIndexOf(e, elements, index);
    }

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

public int size() {
        return getArray().length;
    }

  
    public boolean isEmpty() {
        return size() == 0;
    }

//转化为Object类型的数组
public Object[] toArray() {
        Object[] elements = getArray();
        return Arrays.copyOf(elements, elements.length);
    }

//转化为特定类型的数组
 public <T> T[] toArray(T a[]) {
        Object[] elements = getArray();
        int len = elements.length;
        if (a.length < len)
            return (T[]) Arrays.copyOf(elements, len, a.getClass());
        else {
            System.arraycopy(elements, 0, a, 0, len);
            if (a.length > len)
                a[len] = null;
            return a;
        }
    }

//判断是否相等这个实现有些疑惑为什么不先判断长度？再比较元素？先判断长度效率应该更高
public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        List<?> list = (List<?>)(o);
        Iterator<?> it = list.iterator();
        Object[] elements = getArray();
        int len = elements.length;
        for (int i = 0; i < len; ++i)
	 //如果o的长度小于了队列的长度或者他们的元素不相等返回false
            if (!it.hasNext() || !eq(elements[i], it.next()))
                return false;
	//o的长度大于了队列的长度
        if (it.hasNext())
            return false;
        return true;
    }

 public int hashCode() {
        int hashCode = 1;
        Object[] elements = getArray();
        int len = elements.length;
        for (int i = 0; i < len; ++i) {
            Object obj = elements[i];
            hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
        }
        return hashCode;
    }

//复制
public Object clone() {
        try {
            CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
            c.resetLock();
            return c;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

public String toString() {
        return Arrays.toString(getArray());
    }