gov.nasa.jpf.util

Class PSIntMap<V>

java.lang.Object

gov.nasa.jpf.util.PSIntMap<V>

All Implemented Interfaces:

Iterable<V>

public class PSIntMap<V>
extends Object
implements Iterable<V>

Persistent (immutable) associative array that maps integer keys to generic reference values.

PSIntMap is implemented as a bitwise trie which processes key bits in msb order (from left to right) and has the same depth along all paths (i.e. values are only kept at the terminal node level, which corresponds to the rightmost bit block in the key). This particular implementation was chosen to optimize performance for dense key value domains, e.g. keys that are computed from counters. More specifically, PSIntMap was designed to be a suitable basis for JPF Heap implementations with their characteristic usage pattern: .. transition{ ..alloc( n),..alloc(n+1),..alloc(n+2), ..}, garbage-collection{ remove(x),remove(y),..} .. The 32bit keys are broken up into 5bit blocks that represent the trie levels, each 5bit block (0..31) being the index for the respective child node or value. For instance, a key/value pair of 12345->'x' is stored as

   level:     6    5     4     3     2     1     0
   key:       00.00000.00000.00000.01100.00001.11001  = 12345
   block-val:  0     0     0     0    12     1    25
 
       Node0 (level 2 : nodes)
         ... 
         [12] -> Node1 (level 1 : nodes)
                   ...
                   [1] -> Node2 (level 0 : values)
                            ...
                           [25] -> 'x'

The main benefit of using this representation is that existing maps are never modified (are persistent) and hence a previous state can be restored by simply keeping the reference of the respective map. The main drawback is that not only the changed value has to be stored upon add/remove, but everything from the node that contains this value up to the root node. This implementation partitions keys from left (msb) to right, which has the major property that consecutive keys are stored in the same node, which in turn allows for efficient caching of the last modified node. Keeping track of this 'stagingNode' avoids copying anything but the affected node until the next staging node miss, at which point the old stagingNode has to be merged. This merge only requires copying of old stagingNode parents up to the level that already has been copied due to the new key insertion that caused the stagingNode miss). The internal trie representation uses a protected Node type, which uses the bit block values (0..31) as index into an array that stores either child node references (in case this is not a terminal block), or value objects (if this is the terminal level). There are three Node subtypes that get promoted upon population in the following order:

• OneNode - store only a single value/child element. Every node starts as a OneNode
• BitmapNode - stores up to 31 elements (compressed)
• FullNode - stores 32 elements

Removal of keys leads to symmetric demotion of node types. The five major public operations for PersistentIntMaps are

1. set(int key, V value) -> PersistentIntMap : return a new map with an additional value
2. get(int key) -> V : retrieve value
3. remove(int key) -> PersistentIntMap : return a new map without the specified key/value
4. removeAllSatisfying(Predicate predicate) -> PersistentIntMap : return a new map without all values satisfying the specified predicate
5. process(Processor processor) : iterate over all values with specified processor

Being a persistent data structure, the main property of PersistentIntMaps is that all add/remove operations (set,remove,removeAllSatisfying) have to return new PersistenIntMap instances, no destructive update is allowed. Normal usage patterns therefore look like this:

   PSIntMap map = PSIntMap();
   ..
   map = map.set(42, "fortytwo"); // returns a new map
   ..
   map = map.remove(42); // returns a new map
   ..
   map = map.removeAllSatisfying( new Predicate(){ // returns a new map
     public boolean isTrue (String val){ 
       return val.endsWith("two");
     });
     
   map.process( new Processor(){
     public void process (String val){
       System.out.println(val);
     });
 

NOTE: bitwise tries are inherently recursive data structures, which would naturally lend itself to implementations using recursive methods (over nodes). However, the recursion is always bounded (finite number of key bits), and we need to keep track of the terminal (value) node that was modified, which means we would have to return two values from every recursion level (new current level node and new (terminal) stagingNode), thus requiring additional allocation per map operation ( e.g. 'result' object to keep track of transient state, as in "node = node.assoc(..key, value, result)") or per recursive call ( result: {node,stagingNode}, as in "result = node.assoc( ..key, value)"). The first solution would allow to create/store a result object on the caller site, but this could compromise map consistency in case of concurrent map operations. Both solutions are counter-productive in a sense that PSIntMap is optimized to minimize allocation count, which is the crux of persistent data structures. The approach that is taken here is to manually unroll the recursion by means of explicit operand stacks, which leads to methods with large number of local variables (to avoid array allocation) and large switch statements to set respective fields. The resulting programming style should only be acceptable for critical runtime optimizations.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	PSIntMap.BitmapNode<E> A node that holds between 2 and 31 elements.
protected static class	PSIntMap.FullNode<E> newElements node with 32 elements, for which we don't need newElements bitmap.
protected static class	PSIntMap.Node<E> Abstract root class for all node types.
protected static class	PSIntMap.OneNode<E> Node that has only one element and hence does not need an array.
protected class	PSIntMap.ValueIterator this is less efficient than using map.process(processor), but required to use PSIntMaps in lieu of ordinary containers Since PSIntMaps are bounded recursive data structures, we have to model newElements stack explicitly, but at least we know it is not exceeding newElements depth of 6 (5 bit index blocks) Note - there are no empty nodes.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	rootLevel
protected PSIntMap.Node	rootNode
protected int	size
protected PSIntMap.Node<V>	stagingNode
protected int	stagingNodeMask
protected PSIntMap.Node	targetNode

Constructor Summary

Constructors

Modifier	Constructor and Description
	PSIntMap() the only public constructor
protected	PSIntMap(int size, int rootLevel, PSIntMap.Node rootNode, PSIntMap.Node<V> stagingNode, PSIntMap.Node<V> targetNode, int stagingNodeMask)

Method Summary

Methods

Modifier and Type	Method and Description
protected int	countSize(int level, PSIntMap.Node node)
V	get(int key)
Iterator<V>	iterator()
String	keyDescription(int key)
protected PSIntMap.Node	mergeStagingNode()
protected void	mergeStagingNode(int key, int newRootLevel, PSIntMap.Node newRootNode) this relies on that all nodes from the new staging node to the newRootNode have been copied and can be modified without cloning.
void	printOn(PrintStream ps)
void	process(Processor<V> p)
PSIntMap<V>	remove(int key)
protected PSIntMap.Node	removeAllSatisfying(int level, PSIntMap.Node node, Predicate<V> pred)
PSIntMap<V>	removeAllSatisfying(Predicate<V> pred)
PSIntMap<V>	set(int key, V value) this either replaces or adds newElements new value
protected PSIntMap<V>	setInCurrentRootLevel(int key, V value) that's ugly, but if we use recursion we need newElements result object to obtain the new stagingNode and the size change, which means there would be an additional allocation per set() or newElements non-persistent, transient object that would need synchronization
protected PSIntMap<V>	setInNewRootLevel(int newRootLevel, int key, V value)
int	size()
V[]	values()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

size

protected final int size

rootLevel

protected final int rootLevel

rootNode

protected final PSIntMap.Node rootNode

stagingNode

protected final PSIntMap.Node<V> stagingNode

stagingNodeMask

protected final int stagingNodeMask

targetNode

protected final PSIntMap.Node targetNode

Constructor Detail

PSIntMap

public PSIntMap()

the only public constructor

PSIntMap

protected PSIntMap(int size,
        int rootLevel,
        PSIntMap.Node rootNode,
        PSIntMap.Node<V> stagingNode,
        PSIntMap.Node<V> targetNode,
        int stagingNodeMask)

Method Detail

iterator

public Iterator<V> iterator()

Specified by:

iterator in interface Iterable<V>

size

public int size()

get

public V get(int key)

mergeStagingNode

protected PSIntMap.Node mergeStagingNode()

mergeStagingNode

protected void mergeStagingNode(int key,
                    int newRootLevel,
                    PSIntMap.Node newRootNode)

this relies on that all nodes from the new staging node to the newRootNode have been copied and can be modified without cloning. The modification does not change the node type since the old staging/target node was in the trie The first node where new and old staging indices differ is the mergeNode that needs to be modified (old staging path node replaced). This has to be level 1..6 Everything above the mergeNode is not modified (the newRootNode does not have to be copied as it is new) All nodes between the old stagingNode and the mergeNode have to be copied The old stagingNode itself does not need to be cloned.

remove

public PSIntMap<V> remove(int key)

set

public PSIntMap<V> set(int key,
              V value)

this either replaces or adds newElements new value

setInNewRootLevel

protected PSIntMap<V> setInNewRootLevel(int newRootLevel,
                            int key,
                            V value)

setInCurrentRootLevel

protected PSIntMap<V> setInCurrentRootLevel(int key,
                                V value)

that's ugly, but if we use recursion we need newElements result object to obtain the new stagingNode and the size change, which means there would be an additional allocation per set() or newElements non-persistent, transient object that would need synchronization

process

public void process(Processor<V> p)

removeAllSatisfying

protected final PSIntMap.Node removeAllSatisfying(int level,
                                PSIntMap.Node node,
                                Predicate<V> pred)

removeAllSatisfying

public PSIntMap<V> removeAllSatisfying(Predicate<V> pred)

countSize

protected final int countSize(int level,
            PSIntMap.Node node)

values

public V[] values()

printOn

public void printOn(PrintStream ps)

keyDescription

public String keyDescription(int key)