Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

CopyOnWriteArrayList is a thread-safe ArrayList. This section analyzes the source of CopyOnWriteArrayList, based on JDK1.8.

Class structure

CopyOnWriteArrayList class diagram:

CopyOnWriteArrayList implements all the methods of the List interface and contains the following two member variables:

// Reentrant lock, used to lock write operations
final transient ReentrantLock lock = new ReentrantLock();

// An array of type Object that stores data and is volatile so that changes made to the field by one thread are immediately visible to another thread
private transient volatile Object[] array;
Copy the code

CopyOnWriteArrayList has no capacity-related properties or constants, and we’ll look at some common methods to see why.

Method resolution

The constructor

CopyOnWriteArrayList() null argument constructor:

public CopyOnWriteArrayList(a) {
    setArray(new Object[0]);
}

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

The no-argument constructor directly creates an Object array of length 0.

CopyOnWriteArrayList(Collection
c) :

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        // If the collection type is CopyOnWriteArrayList, its array is assigned directly to the current CopyOnWriteArrayListelements = ((CopyOnWriteArrayList<? >)c).getArray();else {
        // If not CopyOnWriteArrayList, then the collection is converted to an array
        elements = c.toArray();
        // As described in the ArrayList source code analysis, the return type of c. toarray () is not necessarily Object[].class, so it needs to be converted
        if(elements.getClass() ! = Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); }// Set the array value
    setArray(elements);
}
Copy the code

CopyOnWriteArrayList [] toCopyIn (E) :

public CopyOnWriteArrayList(E[] toCopyIn) {
    // Copy a copy of the assignment to array
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
Copy the code

add(E e)

Add (E E) to add elements to the end of CopyOnWriteArrayList:

public boolean add(E e) {
    // Get a reentrant lock
    final ReentrantLock lock = this.lock;
    // Only one thread can enter at a time
    lock.lock();
    try {
        // Gets the current array property value
        Object[] elements = getArray();
        // Get the length of the current array
        int len = elements.length;
        // Copy a new array with the current array length +1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // Add elements to the end of the new array
        newElements[len] = e;
        // Assign the new array to the array property
        setArray(newElements);
        return true;
    } finally {
        / / release the locklock.unlock(); }}final Object[] getArray() {
    return array;
}
Copy the code

As you can see, the Add operation ensures thread-safety through ReentrantLock. The basic idea behind CopyOnWriteArrayList is to copy a new array just long enough to hold the elements you want to add. Operate in a new array; Finally, the new array is assigned to the array property, replacing the old array. This idea is also called “copy-on-write,” so it’s called CopyOnWriteArrayList.

In addition, we can see that CopyOnWriteArrayList has no expansion operations for grow method similar to ArrayList.

add(int index, E element)

Add (int index, E element)

public void add(int index, E element) {
    // Get a reentrant lock
    final ReentrantLock lock = this.lock;
    // Only one thread can enter at a time
    lock.lock();
    try {
        // Gets the current array property value
        Object[] elements = getArray();
         // Get the length of the current array
        int len = elements.length;
        // subscript check
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            // numMoved is 0, indicating that the numMoved is added at the end. The process is the same as the add(E, E) method
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // Otherwise create a new array with the old array length value +1
            newElements = new Object[len + 1];
            // Copy the elements before index and after index+1 into the new array
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1, numMoved);
        }
        // Add the specified element to the index position of the new array
        newElements[index] = element;
        // Assign the new array to the array property, replacing the old array
        setArray(newElements);
    } finally {
        / / release the locklock.unlock(); }}Copy the code

set(int index, E element)

Set (int index, E element) sets the value of the specified position:

public E set(int index, E element) {
    // Get a reentrant lock
    final ReentrantLock lock = this.lock;
    // Only one thread can enter at a time
    lock.lock();
    try {
    	// Gets the current array property value
        Object[] elements = getArray();
        // Gets the index subscript of the current array
        E oldValue = get(elements, index);
        if(oldValue ! = element) {// If the new value is not equal to the old value
            int len = elements.length;
            // Copy a new array of the same length as the old one
            Object[] newElements = Arrays.copyOf(elements, len);
            // Change the subscript value of the new array index
            newElements[index] = element;
            // Assign the new array to the array property, replacing the old array
            setArray(newElements);
        } else {
            // Even if the new value is the same as the old value, array needs to be reset to ensure volatile semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
    	/ / releases the locklock.unlock(); }}private E get(Object[] a, int index) {
    return (E) a[index];
}
Copy the code

remove(int index)

Remove (int index) removes the specified subscript element:

public E remove(int index) {
    // Get a reentrant lock
    final ReentrantLock lock = this.lock;
    // Only one thread can enter at a time
    try {
    	// Gets the current array property value
        Object[] elements = getArray();
        // Gets the current array length
        int len = elements.length;
        // Get the old value
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
        	// If the last element is deleted, the current array is set to the new array
        	// The length of the new array is -1, which cuts off the last element
            setArray(Arrays.copyOf(elements, len - 1));
        else {
        	// Copy the elements before index and after index+1 into the new array
        	// The length of the new array is -1
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);
            / / set the array
            setArray(newElements);
        }
        return oldValue;
    } finally {
    	/ / release the locklock.unlock(); }}Copy the code

As you can see, the add, delete, and change operations in CopyOnWriteArrayList are performed in the new array, and only one thread is locked at a time to ensure that the operation is performed. After the operation, the array property is assigned to replace the old array, which loses its reference and is eventually reclaimed by the GC.

get(int index)

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}
Copy the code

As you can see, the get(int index) operation takes place in two steps:

  1. throughgetArray()Get the array property value.
  2. Get array array index subscript value.

This process is not locked, so the following situations can occur in a concurrent environment:

  1. Thread 1 callget(int index)Method to get the value, passed internallygetArray()Method gets the array property value;
  2. Thread 2 calls the add, delete, or change method of CopyOnWriteArrayList, which passes internallysetArrayThe array method modifies the value of the array property.
  3. Thread 1 is still being evaluated from the old array array.

So the GET method is weakly consistent.

size()

public int size(a) {
    return getArray().length;
}
Copy the code

The size() method returns the length of the current array property, because the array in CopyOnWriteArrayList will fit all the elements in each copy, unlike ArrayList, which reserves space. So CopyOnWriteArrayList has no size property, the number of elements is equal to the length of the array.

The iterator

public Iterator<E> iterator(a) {
    return new COWIterator<E>(getArray(), 0);
}
static final 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(a) {
        returncursor < snapshot.length; }... }Copy the code

As you can see, iterators are also weakly consistent and do not take place in locks. If another thread does not add, subtract, or delete CopyOnWriteArrayList, the snapshot will still be the array that was acquired when the iterator was created. However, if another thread adds, subtract, or delete CopyOnWriteArrayList, the old array will be replaced by the new array. But snapshot is still a reference to the old array:

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("hello");
Iterator<String> iterator = list.iterator();
list.add("world");
while (iterator.hasNext()){
    System.out.println(iterator.next());
}
Copy the code

The output is only Hello.

conclusion

  1. CopyOnWriteArrayList reflects the idea of copying while writing, adding, deleting, and modifying all operations are done in the copied new array;
  2. The value method of CopyOnWriteArrayList is weakly consistent and cannot ensure that the latest data is fetched in real time.
  3. CopyOnWriteArrayList’s add, delete, and change methods ensure thread safety through reentrant locks;
  4. CopyOnWriteArrayList thread safety is reflected in the multi-thread add, delete and change will not throwjava.util.ConcurrentModificationExceptionExceptions cannot ensure strong consistency of data;
  5. Only one thread can add, delete, or modify a copy of CopyOnWriteArrayList at a time, and there is no limit to the number of read operations. Besides, CopyOnWriteArrayList requires copying a new array, which increases memory consumption. So CopyOnWriteArrayList is good for reading too much and writing too little.