JAVA and contract: CopyOnWriteArrayList

CopyOnWriteArrayList implements the List interface. You can see from its name that it copies an array when writing data.

CopyOnWriteArrayList is an array structure. Data writing can be described as obtaining lock first, copying the data of old array to new array, inserting data into new array, and replacing the array of list with new array. Reading data will not be locked, directly reading the data of the array.

Let's understand it from the code level.

1, Basic code structure

The following code shows that CopyOnWriteArrayList is the data structure of an array

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /** Reentry lock is used to modify data */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array that holds data is decorated with volatile because it can be used in concurrent environment */
    private transient volatile Object[] array;

    /** Set array to replace old array and initialize */
    final void setArray(Object[] a) {
        array = a;
    }

    /** The constructor creates an empty array */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
}    

2, Insert data

  1. Add (e e e) method
    From the following method, we can see that every time an object is added, the lock needs to be acquired and the array needs to be copied once. If there are too many write operations, it will consume performance.
	public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        // Acquire reentry lock
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            // Copy old data to new array
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // Add an object to the new array
            newElements[len] = e;
            // Replace the old array maintained by list with the new array
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
  1. add(int index, E element) method
    When inserting data at a specified location, you may need to copy the array twice, which is more performance consuming.
	public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        // Lock up
        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;
            // Insert the last part of the array, or if the array is empty, you only need to copy the array once, otherwise you need to copy twice
            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();
        }
    }

3, Get data

Generally, get method is used to get data. From the following code, we can see that it is very simple. It directly takes the object with specified subscript from the array. Note that if the subscript is out of bounds, IndexOutOfBoundsException will be thrown.

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

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

4, Delete data

Similar to the add(int index, E element) method, you may need to copy the array twice.

	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();
        }
    }

Five, traversal

As you can see from the following code, traversal is to take a snapshot of the array, and then operate the snapshot to traverse the data. We see that add, remove and other modification operations are not allowed in the iterator. In addition, if you call the external methods add, remove and other operations to modify the data, because the modification is to copy the data of the old array to the new array, and then operate the new array, the external modification will not affect the iterator's traversal, that is, the traversal ensures that the ConcurrentModificationException will not be thrown.

	public Iterator<E> iterator() {
        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() {
            return cursor < snapshot.length;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }
		/** Iterator does not allow modification */
	 	public void remove() {
            throw new UnsupportedOperationException();
        }

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

Six, summary

From the above analysis of CopyOnWriteArrayList, we can draw the following conclusions:

  1. Data structure: array.
  2. Concurrent lock adding: the modification operation needs to increase the input lock, and the reading operation does not need to increase the lock.
  3. Modify logic: copy array data and produce new array.
  4. Traversal: use array snapshot to ensure that no ConcurrentModificationException is thrown.
  5. Whether null data can be inserted: null object can be inserted.
  6. Usage scenario: concurrent environment, read more and write less.
Published 60 original articles, won praise 7, visited 8370
Private letter follow

Tags: snapshot Java less

Posted on Tue, 04 Feb 2020 22:13:49 -0800 by irishprogrammin