CODEWITHSUNDEEP
java
Farhan stands with Palestine
Farhan stands with Palestine

Reputation: 14126

Iterators for the copy-on-write collections

An abstract from JCIP

Iterators for the copy-on-write collections retain a reference to the backing array that was current at the start of iteration, and since this will never change, they need to synchronize only briefly to ensure visibility of the array contents.

The iterators returned by the copy-on-write collections do not throw ConcurrentModificationException and return the elements exactly as they were at the time the iterator was created, regardless of subsequent modifications

Looking at the source code at #CopyOnWriteArrayList.iterator()

956         public Iterator<E> iterator() {
957              return new COWIterator<E>(getArray(), 0); // call to private constructor
958         }

993         private final Object[] snapshot;

994 
995         private int cursor;
996 
997         private COWIterator(Object[] elements, int initialCursor) {
998             cursor = initialCursor;
999             snapshot = elements;  
1000        }

You see that the snapshot points to the array returned by getArray() and since the array reference returned is volatile, any change on the reference variable is guaranteed to be reflected. (Making the array reference volatile doesn't makes the elements at each index location volatile)

where the change on the array is done inside-

386     public E More ...set(int index, E element) {
387         final ReentrantLock lock = this.lock;
388         lock.lock();
389         try {
390             Object[] elements = getArray();
391             E oldValue = get(elements, index);
392 
393             if (oldValue != element) {
394                 int len = elements.length;
395                 Object[] newElements = Arrays.copyOf(elements, len);
396                 newElements[index] = element;
397                 setArray(newElements);
398             } else {
399                 // Not quite a no-op; ensures volatile write semantics
400                 setArray(elements);
401             }
402             return oldValue;
403         } finally {
404             lock.unlock();
405         }
406     }

i.e setArray(newElements); as seen in the method.

where getArray() 

92      final Object[] More ...getArray() {
93          return array;
94      }

& setArray(...)

final void More ...setArray(Object[] a) {
100         array = a;
101     }

are operations on this volatile array

private volatile transient Object[] array;

Clearly, the iterator is returning the array which (if) has been modified, and not the one created at the start of the iteration process.

So, what does the author mean-

return the elements exactly as they were at the time the iterator was created, regardless of subsequent modifications.

Upvotes: 0

Views: 823

Answers (3)

Dev Amitabh
Dev Amitabh

Reputation: 185

The code that you've pasted here has these lines (not copied a few lines in between) : Object[] elements = getArray(); Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element;

Line 1 refers to the existing array that backs this collection. If you try to get an iterator before the collection is updated, then this is the array (referred to as snapshot) iterator gets.

Line 2 is a new array being created by copying (hence the COW) and then new item being added to it as seen in line 3.

This newElements array is then assigned to volatile array reference. Iterator is already referring to older snapshot array, so it doesn't even know about the array being updated.

Hope that explains.

Upvotes: 0

Spotted
Spotted

Reputation: 4091

Let's say you instanciate a CopyOnWriteArrayList, now elements is referencing an array:

elements -> [0, 1, 2]

Now you create a COWIterator, snapshot is referencing the same array:

elements -> [0, 1, 2] <- snapshot

Now you add a new element to the CopyOnWriteArrayList, a new array is created and the reference is updated to the new array:

snapshot -> [0, 1, 2]

elements -> [0, 1, 3]

So, snapshot still points to the initial array !

Upvotes: 1

M A
M A

Reputation: 72854

since the array returned is volatile, any change on the reference variable is guaranteed to be reflected.

This has nothing to do with volatile semantics. The reference to the array is created when the COWIterator constructor is called (when the iterator is created). Creating a new copy of the array and assigning its reference to the array field will keep the snapshot of the iterator pointing to the same old reference.

Upvotes: 4

Related Questions