Iterator

package com.javaspeak.designpatterns.go4.behavioural.iterator;

import org.testng.Assert;

import org.testng.TestListenerAdapter;

import org.testng.TestNG;

import org.testng.annotations.Test;

/**

* Text book description:

* <ul>

* Iterator: Sequentially access the elements of a collection. Provide a way to access the

* elements of an aggregate object sequentially without exposing its underlying representation.

* </ul>

* An Iterator has methods like hasNext() and next() which allows the underlying collection to

* be accessed:

*

* while ( snapshotIterator.hasNext() ){

*

* value= snapshotIterator.next();

* }

*

* This example shows an implementation of a concurrent LinkedList which uses Compare And Swap

* operations to add and remove elements. CAS operations make use of CAS features of hardware

* to update fields.

*

* The principle behind a CAS operation is that the value of a field is retrieved; an operation

* is then performed to get a new value for the field; but before updating the old value with the

* new value, a CAS operation is made to check whether the old value is still the same. If the

* old value is the same, it is replaced with the new value. If the old value is not the same

* it means that it has been updated by another thread during the duration of the processing. In

* other words the old value has become stale as the processing could not be completed before

* the old value was updated by another thread. The CAS compareAndSwap() method call will return

* false and the calling code can attempt to perform the operation again until it succeeds.

*

* A snapshot iterator is returned. It is a snapshot of the data since when the Iterator was

* created. While iterating through the elements other threads may add or remove elements in the

* List and the additions or removals will not be reflected in the iterator - hence the name

* "snapshot".

*

* This test, tests add, remove and the usage of an iterator for the ConcurrentLinkedList in a single

* threaded environment.

*

* @author John Dickerson - 21 Feb 2020

*/

public class ConcurrentLinkedListSingleThreadedTest {

@Test

public void testIterator() {

// the values to add

String[] valuesToAdd = { "Hello", "World!", "How", "bling", "blah", "is", "it", "doing?" };

ConcurrentLinkedList<String> linkedList = new ConcurrentLinkedList<String>();

for ( String value : valuesToAdd ) {

// add the values to the list

linkedList.add( value );

}

// remove some values from the list

linkedList.remove( "bling" );

linkedList.remove( "blah" );

// Create a snapshot iterator

SnapshotIterator<String> snapshotIterator = linkedList.getSnapshotIterator();

// Add some further values to the list. These should not be present

// in the iterator as it is snapshot iterator and has been created

// already.

linkedList.add( "Wow" );

// Remove some further values from the list. These should not be

// removed from the iterator as it is a snapshot iterator and has been

// created already.

linkedList.remove( "Hello" );

int i = 0;

String actualValue;

// the expected values to be returned by the iterator (note that bling

// and blah) have been removed from the list

String[] expectedValues = { "Hello", "World!", "How", "is", "it", "doing?" };

while ( snapshotIterator.hasNext() ) {

actualValue = snapshotIterator.next();

System.out.println( actualValue );

Assert.assertEquals( actualValue, expectedValues[i] );

i++;

}

}

public static void main( String args[] ) {

TestListenerAdapter tla = new TestListenerAdapter();

TestNG testng = new TestNG();

testng.setTestClasses( new Class[] { ConcurrentLinkedListSingleThreadedTest.class } );

testng.addListener( tla );

testng.run();

}

}

package com.javaspeak.designpatterns.go4.behavioural.iterator;

import java.util.concurrent.atomic.AtomicReference;

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

/**

* ConcurrentLinkedList uses Compare and Swap (CAS) operations to add and remove elements to the

* list. This is less expensive than traditional blocking synchronisation.

* <p>

* In ConcurrentLinkedList there is a AtomicReference field called

* lastAddedLinkedElementAtomicReference which references a LinkedElement. LinkedElement has a

* field which can references other LinkedElements.

* <p>

* When the first LinkedElement, is added lastAddedLinkedElementAtomicReference references A.

* <p>

* When the next LinkedElement is added lastAddedLinkedElementAtomicReference references B.

* B itself references A. In other words: B ==> A

* <p>

* When the next LinkedElement, C, is added lastAddedLinkedElementAtomicReference references C.

* C itself references B which in turn references A. In other words: C ==> B ==> A

* <p>

* LinkedElement provides a wrapper for the element being added and also has nextLinkedElement

* and previousLinkedElement fields. When an element is added a new LinkedElement is created and

* its nextLinkedElement field is mapped to the LinkedElement currently stored in

* lastAddedLinkedElementAtomicReference. The current LinkedElement is then replaced with the

* new LinkedElement in the lastAddedLinkedElementAtomicReference. The CAS operation only occurs

* on the lastAddedLinkedElementAtomicReference field. The previousLinkedElement fields are not

* updated at this point in time and are used for creating snapshot iterators.

*

* @author John Dickerson - 21 Feb 2020

*/

public class ConcurrentLinkedList<E> implements SnapshotIterable<E> {

// references the last added LinkedElement. New LinkedElements are created

// and updated in this AtomicReference using a CAS operation.

private AtomicReference<LinkedElement<E>> lastAddedLinkedElementAtomicReference =

new AtomicReference<LinkedElement<E>>();

/**

* This AtomicReferenceFieldUpdater is used to update the nextLinkedElement volatile field of

* a LinkedElement with another LinkedElement. AtomicReferenceFieldUpdater uses CAS hardware

* support to update the field. AtomicReferenceFieldUpdater is more efficient in updating

* fields that using AtomicReference when there are many instances to update. If it is not used

* then multiple AtomicReference would need to be used, one for each instance which could be

* quite expensive on memory resources.

*/

@SuppressWarnings( "rawtypes" )

private AtomicReferenceFieldUpdater<LinkedElement, LinkedElement> nextLinkedElementUpdater =

AtomicReferenceFieldUpdater.newUpdater(

LinkedElement.class, LinkedElement.class, "nextLinkedElement" );

/**

* A non expensive CAS operation is used to update a reference in

* lastAddedLinkedElementAtomicReferencein to the last added LinkedElement.

* <p>

* The newly added LinkedElement references the LinkedElements already in the chain.

* <p>

* LinkedElements are used to wrap the element being added and to provide a reference to the

* next LinkedElement in the chain.

* <p>

* The LinkedElement placed at the beginning of the chain is always the last LinkedElement

* added.

*

* @param object

* Element to add

*/

public void add( E object ) {

LinkedElement<E> linkedElement = new LinkedElement<E>( object );

// Keep trying to update the reference to the new LinkedElement being added using a CAS

// operation until it succeeds. CAS operations avoid the expense of traditional

// synchronization. Instead of blocking all other threads until the current thread

// releases the lock, CAS operations read the current value of a field, do some processing

// and before replacing the current value with a new value, check that the old value has

// not changed in the meantime. If the old value has changed that means the old value

// was changed by another thread and the operation is repeated until successful. CAS

// methods make use of CAS functionality in the hardware.

while ( true ) {

linkedElement.nextLinkedElement =

lastAddedLinkedElementAtomicReference.get();

// if the old value from lastAddedLinkedElementAtomicReference has not changed replace

// it with the new reference in a CAS operation.

if ( lastAddedLinkedElementAtomicReference.compareAndSet(

linkedElement.nextLinkedElement, linkedElement ) ) {

break;

}

}

}

/***

* Recursively looks for the element to remove in the chain of LinkedElement and returns true

* if the CAS operation to remove the element was successful. Given the chain A ==> B ==> C

* removing B entails joining A with C as follows: A ==> C

*

* @param linkedElement

* LinkedElement

*

* @param nextLinkedElement

* nextLinkedElement of linkedElement

*

* @param objectToRemove

* Object to remove

*/

private boolean removeObject(

LinkedElement<E> linkedElement, LinkedElement<E> nextLinkedElement, E objectToRemove ) {

if ( nextLinkedElement == null ) {

throw new RuntimeException( "Cannot find element to remove" );

}

LinkedElement<E> nextNextLinkedElement = nextLinkedElement.nextLinkedElement;

if ( nextLinkedElement.object.equals( objectToRemove ) ) {

return nextLinkedElementUpdater.compareAndSet(

linkedElement, linkedElement.nextLinkedElement, nextNextLinkedElement );

}

else {

return removeObject( nextLinkedElement, nextNextLinkedElement, objectToRemove );

}

}

/**

* This method is called to populate the cloned copy of the LinkedElement in

* lastAddedLinkedElementAtomicReference so that all LinkedElements in the chain have the

* previousLinkedElement populated. The Last element in the chain is returned. The last

* element in the chain is the first element that was added to ConcurrentLinkedList.

*

* @param linkedElementIn

* The linkedElement to populate its chain of LinkedElements with the previousLinkedElement

*

* @return

* the last element in the chain.

*/

private LinkedElement<E> populatePreviousLinks(

LinkedElement<E> linkedElementIn ) {

LinkedElement<E> linkedElement = linkedElementIn;

LinkedElement<E> nextLinkedElement;

while ( ( nextLinkedElement = linkedElement.nextLinkedElement ) != null ) {

nextLinkedElement.previousLinkedElement = linkedElement;

linkedElement = nextLinkedElement;

}

return linkedElement;

}

/**

* Uses CAS to remove the element. The remove method will be continuously executed until the

* remove succeeds.

*

* @param objectToRemove

* Object to remove

*/

public void remove( E objectToRemove ){

while ( true ){

LinkedElement<E> lastAddedLinkedElement = lastAddedLinkedElementAtomicReference.get();

if ( lastAddedLinkedElement == null ){

throw new RuntimeException( "Cannot find element to remove" );

}

LinkedElement<E> nextLinkedElement = lastAddedLinkedElement.nextLinkedElement;

// If lastAddedLinkedElement contains the object set it to reference the next element

// in the chain instead.

if ( lastAddedLinkedElement.object.equals( objectToRemove ) ){

lastAddedLinkedElementAtomicReference.set( nextLinkedElement );

break;

}

else {

// recursively look for the object to remove. If the CAS operation fails try the

// whole remove operation again

if ( removeObject( lastAddedLinkedElement, nextLinkedElement, objectToRemove ) ) {

break;

}

}

}

}

@Override

public SnapshotIterator<E> getSnapshotIterator() {

LinkedElement<E> linkedElement = lastAddedLinkedElementAtomicReference.get();

try {

// clone the LinkedElement we wish to create the iterator for

LinkedElement<E> clonedLinkedElement = ( LinkedElement<E> )linkedElement.clone();

// look through the chain of LinkedElements and populate the previousLinkedElement

// fields. Return the last LinkedElement in the chain. The last LinkedElement is the

// first element that was added

LinkedElement<E> lastLinkedElement = populatePreviousLinks( clonedLinkedElement );

// Create the iterator

SnapshotIterator<E> snapshotIterator = new SnapshotIteratorImpl<E>( lastLinkedElement );

return snapshotIterator;

}

catch ( CloneNotSupportedException e ) {

throw new RuntimeException( e );

}

}

}

package com.javaspeak.designpatterns.go4.behavioural.iterator;

/**

* @author John Dickerson - 21 Feb 2020

*/

public class LinkedElement<E> implements Cloneable {

// This is not populated by add or remove method. It is used for post processing such as when

// creating an SnapshotIterator

LinkedElement<E> previousLinkedElement;

// In ConcurrentLinkedList there is a an AtomicReferenceFieldUpdater which is used to update

// this volatile field using CAS

volatile LinkedElement<E> nextLinkedElement;

// The object

E object;

public LinkedElement( E object ) {

this.object = object;

}

@Override

protected LinkedElement<E> clone() throws CloneNotSupportedException {

// This method is used to clone a chain of LinkedElement to create a Snapshot Iterator

LinkedElement<E> clonedLinkedElement = new LinkedElement<E>( object );

if ( nextLinkedElement != null ) {

clonedLinkedElement.nextLinkedElement = nextLinkedElement.clone();

}

return clonedLinkedElement;

}

}

package com.javaspeak.designpatterns.go4.behavioural.iterator;

/**

* @author John Dickerson - 21 Feb 2020

*/

public interface SnapshotIterable<E> {

SnapshotIterator<E> getSnapshotIterator();

}

package com.javaspeak.designpatterns.go4.behavioural.iterator;

/**

* @author John Dickerson - 21 Feb 2020

*/

public interface SnapshotIterator<E> {

/**

* Checks whether there are further values that have not had next() called on.

*

* @return boolean

* Returns true if next() will result in returning another value in the list

*/

public boolean hasNext();

/**

* Returns the next value in the list

*

* @return next

* Next value in list

*/

public E next();

}

package com.javaspeak.designpatterns.go4.behavioural.iterator;

/**

* @author John Dickerson - 21 Feb 2020

*/

public class SnapshotIteratorImpl<E> implements SnapshotIterator<E> {

private LinkedElement<E> linkedElement;

/**

* Constructor

* <p>

* The LinkedElement passed through this constructor is the first LinkedElement that was added

* by a user. It is also the element that is at the end of the chain of LinkedElements.

* <p>

* As new elements are added at the beginning of the chain of LinkedElements, this last

* LinkedElement in the chain represents the first element that was added to the

* ConcurrentLinkedList.

* <p>

* To navigate through the linkedElements the field previousLinkedElement is used in the

* LinkedElements.

*

* @param last element in the linkedElement chain

*/

public SnapshotIteratorImpl( LinkedElement<E> linkedElement ) {

this.linkedElement = linkedElement;

}

@Override

public boolean hasNext() {

if ( linkedElement != null ) {

return true;

}

return false;

}

@Override

public E next() {

// as the

E objectToReturn;

if ( linkedElement != null ) {

objectToReturn = linkedElement.object;

linkedElement = linkedElement.previousLinkedElement;

return objectToReturn;

}

return null;

}

}