Immutable Collection

Problem

How can you concurrently walk over and modify a collection?

Context

It is often necessary to support modification of a collection while the collection is being "walked over", by an Enumeration object or by member functions written to UseClosuresNotEnumerations.

Or, multiple threads might want to concurrently walk over and modify the collection and you want to avoid synchronisation overhead and the IteratorInvalidationProblem.

Therefore

Use a data structure that is immutable and used in the style of FunctionalProgramming. Methods that would modify an immutable data structure instead create a new data structure representing the modifications and return that to the caller.

Objects that contain an ImmutableCollection replace their reference to the ImmutableCollection with the modified version whenever they change the contents of the collection. This calculation and assignment must be atomic to avoid concurrent modifications causing lost updates, and must therefore be performed within a synchronized block. However, concurrent enumerations of the data structure can still be in progress (or even be initiated) while such a modification is in progress. For example:

	private volatile ImmutableList list = ImmutableList.EMPTY;
	private final Object listLock = new Object();

	public Enumeration enumerateChildren() {
	    return list.elements();
	}
	public void addChild( Object child ) {
	    synchronized(listLock) {
	        list = list.add(child);
	    }
	}

Resulting Context

More objects are allocated than with a mutable collection. However, allocations can be minimised by sharing portions of the data structure between collections. Because the collections are immutable, it doesn't matter how many collections each node is part of. In some memory management systems (such as Java v1.2 and above), allocating and collecting short-lived objects is very cheap.

A single thread can modify the collection while it is walking over it.

Multiple concurrent reads can be performed, although only one modification can occur at any time. This gives you a form of read/write locking, a synchronisation strategy that is not supported by Java's built in synchronisation mechanisms.

If the collection reference is initialised to null, the operations to modify and walk over the collection must be static functions. This is how the java.awt.AWTEventMulticaster class is implemented. However, if you implement the empty collection as NullObject, operations can be implemented as member functions which makes the programming interface more concise.

It is impossible to construct immutable data structures that contain cycles in a language with eager evaluation. See http://nat.truemesh.com/archives/000195.html.

Known Uses

The class java.awt.AWTEventMulticaster is implemented this style.

NatPryce has written an ImmutableList class in this style also.

A complete library of immutable collection types is at: http://www.waterken.com/dev/ADT/

Related Patterns

ImmutableCollection s work very well when implemented to UseClosuresNotEnumerations. The resultant Java code has the same structure as Haskell (but is significantly more verbose). For example, one can work in terms of higher order functions such as map and fold.

An ImmutableCollection is a form of ValueObject, and has the same advantages.

You can return an ImmutableCollection if you want to ReturnImmutablesFromAccessorMethods. However, you might prefer to ReturnEnumerationsNotCollections. Alternatively, you could define an abstract interface through which you could UseClosuresNotEnumerations and return a reference to that interface instead.

Defining an empty collection as a NullObject makes the implementation far more elegant, IMHO.

I've heard this referred to as CopyOnWrite. The counterpart, CopyOnRead?, makes the copy in the enumerateChildren() call, which makes sense if you do more writes than reads -- BillKayser

I've never seen CopyOnRead? used in practice. Do you have any examples of its use? Also CopyOnRead? requires synchronisation for reading and writing in multithreaded code while an ImmutableCollection does not require synchronisation for reading, due to Java's guarantees about the atomicity of object reference variables between threads.

I like it Nat, this is like an Object version of CopyOnWrite. However, is it possible you chould replace the hard tabs in this and ImmutableList with spaces? On my machine, the each indent in the source turns out to be something like 8 spaces!!! Actually, I'll do it myself as long as you don't mind. -- RobertDiFalco

Go ahead. And feel free to change the coding convention to the normal Java one too, while you're about it. --NatPryce.

This is not an idiom, because it is perfectly transparent.

This is not unique to Java, because it is used in any and all languages. Most of the page happens to use Java as the implementation language, that's all.

It's a DesignPattern.

A question implied by the discussion on ValueObjectHypotheses: Above it says that an ImmutableCollection is a ValueObject. What if the objects contained within the collection are ReferenceObjects? According to the discussion on ValueObjectHypotheses, this ought to be a no-no; ValueObjects should only contain other ValueObjects.

There's no problem with an immutable collection holding references to mutable objects. The collection contains the references. The references are treated as values, not the mutable objects that they reference. If you want a collection of references to objects that change, it's no problem. If you don't want a collection of references to objects that change, don't create one.

This page mirrored in JavaIdioms as of April 29, 2006