This is the 12th day of my participation in the August Text Challenge.More challenges in August

CopyOnWriteArrayList

Classes that belong to JUC

Class declaration

 public class CopyOnWriteArrayList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code

Class variables

 final transient ReentrantLock lock = new ReentrantLock();
 ​
 private transient volatile Object[] array;
Copy the code

Initialize the code block

 private void resetLock() {
     UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
 }
 private static final sun.misc.Unsafe UNSAFE;
 private static final long lockOffset;
 static {
     try {
         UNSAFE = sun.misc.Unsafe.getUnsafe();
         Class<?> k = CopyOnWriteArrayList.class;
         lockOffset = UNSAFE.objectFieldOffset
             (k.getDeclaredField("lock"));
     } catch (Exception e) {
         throw new Error(e);
     }
 }
Copy the code

methods

A constructor

public CopyOnWriteArrayList() { setArray(new Object[0]); } 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); } final void setArray(Object[] a) { array = a; } public CopyOnWriteArrayList(E[] toCopyIn) { setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); }Copy the code

See:

elements = ((CopyOnWriteArrayList<? >)c).getArray(); . setArray(elements); }Copy the code

Obviously there’s a problem:

• If it’s from the sameCopyOnWriteArrayListThen the arrays in both containers refer to the same array: you can write a demo to verify this.

How do YOU ensure that containers created from other CopyonWritearRayLists are available in isolation? 【 answer: Snapshot 】

Basic method

The basic method here refers to:

• get
• set
• add
• remove

And other basic operations that array managed containers should implement.

The get method

 private E get(Object[] a, int index) {
         return (E) a[index];
     }
 ​
 public E get(int index) {
     return get(getArray(), index);
 }
Copy the code

The GET method itself is atomic and does not affect other operations, so no lock and copy operations are done.

Set method

 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

From this code, the set method does the following

• For the container object, the set method is locked.

• The set method compares the old and new values

  • If the old and new values are not equal (**= instead of equals**, which in the case of objects refers to addresses), then:

    • Copy a new array
    • The value at the target index of the new array is changed to the target value
    • Sets the managed array to the new array

  • If not, plug the Elements array back in. The reason:

    • Not quite a no-op; Volatile write semantics is used to ensure volatile write semantics

    • In this blog post, he explains why: To ensure the happens-before principle.
    • This place stuffs the variable back in, ensuring that the external context (where the method was called) will not be reordered by the CPU.

The add method

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(); 8 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 = array.copyof (Elements, len + 1); NewElements = new Object[len + 1]; 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(); }}Copy the code

The add method also does two things to ensure the accuracy of the operation in multi-threading:

• Use ReentrantLock to lock
• Copy the expanded array (length +1) and set the managed array to the new array after setting the last bit of the expanded array as the target object.

The remove method

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(); Public Boolean remove(Object o) {Object[] snapshot = getArray(); int index = indexOf(o, snapshot, 0, snapshot.length); return (index < 0) ? false : remove(o, snapshot, index); } private Boolean remove(Object o, Object[] snapshot, int index) {final ReentrantLock lock = this.lock; lock.lock(); try { Object[] current = getArray(); int len = current.length; if (snapshot ! = current) findIndex: { int prefix = Math.min(index, len); for (int i = 0; i < prefix; i++) { if (current[i] ! = snapshot[i] && eq(o, current[i])) {//--------1 index = i; break findIndex; } } if (index >= len) return false; if (current[index] == o)//------------------2 break findIndex; index = indexOf(o, current, index, len); //---------------3 if (index < 0) return false; } Object[] newElements = new Object[len - 1]; System.arraycopy(current, 0, newElements, 0, index); System.arraycopy(current, index + 1, newElements, index, len - index - 1); setArray(newElements); return true; } finally { lock.unlock(); }} //indexOf is omitted, using a for loop to compare with == (null) /equals (non-null) and return the index positionCopy the code

The remove method does the same as the above two methods:

• locked
• Copy the array

In the method of finding -remove, there is a small detail:

• If it finds it, the remove method is used to lock it and contains a snapshot of the array at the time of the search.

• If the snapshot is different from the current managed array, it is compared:

  • The next step takes place only if the current array contains the element to remove. (1,2,3)

The label code block technique is used to quickly jump out of the judgment.

Enhanced List method

There are also some list-based enhancements, such as:

RemoveRange (int fromIndex, int toIndex) removeRange(int fromIndex, int toIndex) removeRange(int fromIndex, int toIndex) Public Boolean addIfAbsent(E E) {Object[] snapshot = getArray(); return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot); } private boolean addIfAbsent(E e, Object[] snapshot) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] current = getArray(); int len = current.length; if (snapshot ! = current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] ! = snapshot[i] && eq(e, current[i])) return false; if (indexOf(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); }}Copy the code

Iterator

Inner class definition

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; }... }Copy the code

• Also array based, provides forward/backward traversal.

• Do not support delete/set/add operations:

   public void remove() {
       throw new UnsupportedOperationException();
   }
   public void set(E e) {
               throw new UnsupportedOperationException();
           }
   public void add(E e) {
           throw new UnsupportedOperationException();
           }
  Copy the code

SubList

Access method

public List<E> subList(int fromIndex, int toIndex) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; if (fromIndex < 0 || toIndex > len || fromIndex > toIndex) throw new IndexOutOfBoundsException(); return new COWSubList<E>(this, fromIndex, toIndex); } finally { lock.unlock(); }}Copy the code

The class definition

private static class COWSubList<E> extends AbstractList<E> implements RandomAccess { private final CopyOnWriteArrayList<E> l; private final int offset; private int size; private Object[] expectedArray; // only call this holding l's lock COWSubList(CopyOnWriteArrayList<E> list, int fromIndex, int toIndex) { l = list; expectedArray = l.getArray(); offset = fromIndex; size = toIndex - fromIndex; } private void checkForComodification() {if (l.array ()! = expectedArray) throw new ConcurrentModificationException(); }... }Copy the code

SubList operations are described as follows:

• Regardless of the category in CRUD, the flow of operations is:

  • Lock the parent object and lock it
  • Check boundaries to check for asynchronous edits
  • Method to call the parent object
  • unlock

Thread safety

COWArrayList is not completely immune to thread-safety issues.

The reason:

• In the get method, we don’t check the index. We just get the index of the current Array, based on the current Array.

• Remove method: copy array after assignment.

• So there’s a possibility:

  • Thread 1 enters the get method, index = size-1, which has a value.
  • Thread 2 enters the remove method, thread 1 suspends, and changes the array size to size-1.
  • Thread 2 terminates, thread 1 gets the time slice and continues to run. At this time, the index value of thread 1 is invalid and an out-of-bounds error occurs.
  • Of course, the remove method is so much longer than the GET method, and the GET method is not locked. Basically, it is difficult for the remove method to complete the whole process in the time slice acquired when the GET method is suspended. Therefore, this place is also theoretical analysis, and it is unlikely to happen under normal circumstances.

• Although the array is volatile, volatile does not guarantee thread hang in both threads.

• But in the source

  • The comments explicitly indicate that the GET method throws an out-of-bounds exception
  • And because the GET method does not check boundaries, it may have been designed with this in mind, but not as a bug fix, just as a regular list feature.