All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class collections.IncrImpl

java.lang.Object
   |
   +----collections.IncrImpl

public abstract class IncrImpl

extends Object

implements Immutable, Collection

Since it's usually the case that applications use updates rather than their sources, negative deltas are generally more efficient than other schemes. Also, because updates don't point to their sources, when a source becomes unreferenced, it and all of its edit records can be garbage collected. The price you pay for these nice aspects is that reconstruction of old versions is not always all that fast or cheap.

The logic of reconstruction is to work our way to the UpdatableCollection serving as the source of the edits, and then apply each undo operation all the way back up to where we are. Subclasses specialize on the exact edit operation to do at each step.

Reconstruction would be two-line recursive procedure of the form:

 UpdatableCollection reconstruct() {
   if (the lastest version) return a clone of the held UpdatableCollection
   else return edit(nextVersion.reconstruct())
 }
 

1. We need to prevent interference among concurrent reconstructions and/or with operations on the collections themselves. But we cannot afford to hold a lock (synch) on every single node in the chain of edits at once. For long edit chains, it would require too many simultaneous locks. The java runtime could even run out of them.
2. The recursion could get very deep, which is not a good idea in java because of how it uses the stack.

These problems are addressed by:

1. Using a condition variable, that causes each node to lock without holding all of the locks at once. The variable used, prevVersion_ happens to be the same one used for...
2. Putting next-links from each node to the one representing the edit which is to follow. This way we can iterate rather than use recursion.

(All this would be a little prettier if we offloaded work into Edit Command objects. But since these operations must be coordinated with the Collection nodes, it works better to roll them together.)

The code is highly particularized for the operations currently supported in the collections package. It would not be very easy to add subclasses beyond those for the four basic flavors of collection subclasses currently implemented.

Some of the basic ideas for this class are due to Mark Miller and unknown people at Xerox Parc.

ADD_EDIT

firstObjectArg_

Some opportunistic sharing: Subclasses happen to need records of two Object arguments for updates.

nextVersion_

When delta'd, a ref to the collection we generated.

NO_EDIT

op_

We can only handle a known number of undoable operations on collections, encoded into op_

REMOVE_EDIT

REPLACE_EDIT

secondObjectArg_

updatable_

The collection performing the actual work.

IncrImpl(UpdatableCollection)

accessOnly()

Special case of undelta that avoids the pin-check in cases where we are performing only non-mutative operations

assert(boolean)

Implements collections.ImplementationCheckable.assert.

canInclude(Object)

Implements collections.Collection.canInclude.

checkImplementation()

Implements collections.ImplementationCheckable.checkImplementation.

doEdit(UpdatableCollection)

Must implement in subclasses to perform subclass-specific edits

duplicate()

Wrapper for clone()

elements()

Implements collections.Collection.elements.

excluding(Object)

Construct a new Collection that is a clone of self except that it does not include any occurrences of the indicated element.

includes(Object)

Implements collections.Collection.includes.

isEmpty()

Implements collections.Collection.isEmpty.

occurrencesOf(Object)

Implements collections.Collection.occurrencesOf.

pin(IncrCollectionEnumeration)

Pin during a traversal.

removingOneOf(Object)

Construct a new Collection that is a clone of self except that it does not include an occurrence of the indicated element.

replacingAllOf(Object, Object)

Construct a new Collection that is a clone of self except that all occurrences of oldElement are replaced with newElement.

replacingOneOf(Object, Object)

Construct a new Collection that is a clone of self except that one occurrence of oldElement is replaced with newElement.

sameStructure(Collection)

Implements collections.Collection.sameStructure

size()

Implements collections.Collection.size.

toString()

undelta()

Call this as the first statement of EVERY subclass method that performs any kind of constructive update.

 protected UpdatableCollection updatable_

The collection performing the actual work. Null if delta'd

 protected IncrImpl nextVersion_

When delta'd, a ref to the collection we generated. Invariant: exactly one of updatable_ or nextVersion_ are non-null at any given time.

 protected int op_

We can only handle a known number of undoable operations on collections, encoded into op_

 protected static final int NO_EDIT

 protected static final int ADD_EDIT

 protected static final int REMOVE_EDIT

 protected static final int REPLACE_EDIT

 protected Object firstObjectArg_

Some opportunistic sharing: Subclasses happen to need records of two Object arguments for updates.

 protected Object secondObjectArg_

 protected IncrImpl(UpdatableCollection c)

 public Collection duplicate()

Wrapper for clone()

See Also:

clone

 public final synchronized boolean canInclude(Object element)

Implements collections.Collection.canInclude.

See Also:

canInclude

 public final synchronized boolean isEmpty()

Implements collections.Collection.isEmpty.

See Also:

isEmpty

 public final synchronized int size()

Implements collections.Collection.size.

See Also:

size

 public final synchronized boolean includes(Object element)

Implements collections.Collection.includes.

See Also:

includes

 public final synchronized int occurrencesOf(Object element)

Implements collections.Collection.occurrencesOf.

See Also:

occurrencesOf

 public final synchronized boolean sameStructure(Collection c)

Implements collections.Collection.sameStructure

See Also:

sameStructure

 public final synchronized CollectionEnumeration elements()

Implements collections.Collection.elements.

See Also:

elements

 public final synchronized String toString()

Overrides:

toString in class Object

 protected final synchronized void undelta()

Call this as the first statement of EVERY subclass method that performs any kind of constructive update.

 protected final UpdatableCollection accessOnly()

Special case of undelta that avoids the pin-check in cases where we are performing only non-mutative operations

 protected final synchronized void pin(IncrCollectionEnumeration e)

Pin during a traversal. Call from any method constructing an enumeration.

 protected abstract UpdatableCollection doEdit(UpdatableCollection c)

Must implement in subclasses to perform subclass-specific edits

 public void assert(boolean pred) throws ImplementationError

Implements collections.ImplementationCheckable.assert.

See Also:

assert

 public synchronized void checkImplementation() throws ImplementationError

Implements collections.ImplementationCheckable.checkImplementation.

See Also:

checkImplementation

All Packages  Class Hierarchy  This Package  Previous  Next  Index