This is the 21st day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The only concurrent List in the package is CopyOnWriteArrayList, which is a thread-safe ArrayList. Changes to it are made on an underlying copy array, using a copy-on-write strategy. Each CopyOnWriteArrayList object has an array object to hold specific elements, and RenntrantLock is used to ensure that only one thread can modify the array at the same time.

Let’s take a look at the source of CopyOnWriteArrayList’s main method

The constructor

No parameter constructor

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

The entry parameter is set, and the elements in the set are copied to the list

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if(c.getClass() == CopyOnWriteArrayList.class) elements = ((CopyOnWriteArrayList<? >)c).getArray();else {
        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); }Copy the code

Create a list whose inner elements are copies of the entry parameter toCopyIn

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

Add elements

Add (E E)add(int index, Element) addIfAbsent(E E) addAllAbsent(Collection<? Extents E> c>), their principle is similar, this article uses add(E E) as an example to explain.

public boolean add(E e) {
    final ReentrantLock lock = this.lock; / / code 1
    lock.lock();
    try {
        Object[] elements = getArray(); / / code 2
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e; / / code 3
        setArray(newElements);
        return true;/ / code 4
    } finally {
    5 / / codelock.unlock(); }}Copy the code

In the code above, the thread calling add first acquires an exclusive lock. When multiple threads call ADD, only one thread acquires the lock, and the other threads block until the lock is released. So one thread acquiring the lock ensures that no other thread will modify the array while the thread is adding elements.

After the lock is obtained in code 1, getArray() is executed in code 2 to obtain the array, and then array.copyof copies the array (the new array is the size of the original array +1). Then, at code 3, add the new element to the new array and replace the original array at code 4. Finally, release the resource from the source of code 5.

Gets the element at the specified position

Use E get (int index) to obtain the subscript as the index of the element, if the element does not exist the thrown IndexOutOfBoundsException anomalies.

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

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

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

Copy the code

In the code above, when thread X calls the get method to get the element at the specified position, it first retrieves the array array, and then retrieves the element at the corresponding position by accessing the array with the subscript index.

But if thread X gets the array and doesn’t get the array element value, another thread Y deletes the element. This is when thread X gets the wrong value. This is the problem of weak consistency caused by the copy-on-write strategy.

Modify the specified element

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(elements);
        }
        return oldValue;
    } finally{ lock.unlock(); }}Copy the code

Use E set(int index,E Element) to modify the value of the specified element in the list. Throw an IndexOutOfBoundException if the element at the specified position does not exist. In the code above, we first acquire an exclusive lock, preventing other threads from modifying the array array, then obtain the current array and call the GET method to get the element at the specified location. If the value of the element at the specified location is different from that of the mind, a new array is created to modify the value of the element and replace the old array. If the new and old values also need to be replaced, this is required to ensure volatile semantics.

Remove elements

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];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally{ lock.unlock(); }}Copy the code

In the code above, the main point is to see if the deleted element is last. If the element to be deleted is the last one, use array.copyof () to get the first n-1 data, but if not, split it into two parts to copy. First calculate the length of the second half numMoved, then copy the elements into the new array using system.arrayCopy ().