    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

Base class for Immutable Collection implementations. using `negative deltas'. That is, they update an internally held Collection and set it as the internal Collection for the Immutable Collection serving as the result, but also keep a record of how to undo this change on a copy of the update, so as to reconstruct the original 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())
     }

Except for two problems:

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.

##

updatable_

     protected UpdatableCollection updatable_

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

nextVersion_

     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.

op_

     protected int op_

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

NO_EDIT

     protected static final int NO_EDIT

ADD_EDIT

     protected static final int ADD_EDIT

REMOVE_EDIT

     protected static final int REMOVE_EDIT

REPLACE_EDIT

     protected static final int REPLACE_EDIT

firstObjectArg_

     protected Object firstObjectArg_

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

secondObjectArg_

     protected Object secondObjectArg_

##

IncrImpl

     protected IncrImpl(UpdatableCollection c)

##

duplicate

     public Collection duplicate()

  Wrapper for clone()

  See Also:
    clone

canInclude

     public final synchronized boolean canInclude(Object element)

  Implements collections.Collection.canInclude.

  See Also:
    canInclude

isEmpty

     public final synchronized boolean isEmpty()

  Implements collections.Collection.isEmpty.

  See Also:
    isEmpty

size

     public final synchronized int size()

  Implements collections.Collection.size.

  See Also:
    size

includes

     public final synchronized boolean includes(Object element)

  Implements collections.Collection.includes.

  See Also:
    includes

occurrencesOf

     public final synchronized int occurrencesOf(Object element)

  Implements collections.Collection.occurrencesOf.

  See Also:
    occurrencesOf

sameStructure

     public final synchronized boolean sameStructure(Collection c)

  Implements collections.Collection.sameStructure

  See Also:
    sameStructure

elements

     public final synchronized CollectionEnumeration elements()

  Implements collections.Collection.elements.

  See Also:
    elements

toString

     public final synchronized String toString()

  Overrides:
    toString in class Object

undelta

     protected final synchronized void undelta()

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

accessOnly

     protected final UpdatableCollection accessOnly()

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

pin

     protected final synchronized void pin(IncrCollectionEnumeration e)

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

doEdit

     protected abstract UpdatableCollection doEdit(UpdatableCollection c)

  Must implement in subclasses to perform subclass-specific edits

assert

     public void assert(boolean pred) throws ImplementationError

  Implements collections.ImplementationCheckable.assert.

  See Also:
    assert

checkImplementation

     public synchronized void checkImplementation() throws ImplementationError

  Implements collections.ImplementationCheckable.checkImplementation.

  See Also:
    checkImplementation

    All Packages  Class Hierarchy  This Package  Previous  Next  Index