gov.nasa.jpf.util

Class SparseClusterArray<E>

java.lang.Object

gov.nasa.jpf.util.SparseClusterArray<E>

All Implemented Interfaces:

java.lang.Iterable<E>

public class SparseClusterArray<E>
extends java.lang.Object
implements java.lang.Iterable<E>

A generic sparse reference array that assumes clusters, and more frequent intra-cluster access. This is motivated by looking for a more suitable ADT to model a heap address space, where reference values consist of segment/offset pairs, we have reasonably dense and very dynamic population inside of well separated segment clusters, and intra-cluster access is more likely than inter-cluster access. An especially important feature is to be able to iterate efficiently over set/unset elements in index intervals (cluster sizes). The result should find a compromise between the fast element access & iteration of a simple, dense array, and the efficient memory storage of a HashMap (if only it could avoid box objects). <2do> so far, we are totally ignorant of population constraints

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	SparseClusterArray.Chunk
protected static class	SparseClusterArray.ChunkNode
protected class	SparseClusterArray.ElementIndexIterator
protected class	SparseClusterArray.ElementIterator<T>
static class	SparseClusterArray.Entry<E>
protected static class	SparseClusterArray.Node this corresponds to a toplevel cluster (e.g.
protected static class	SparseClusterArray.Root
static class	SparseClusterArray.Snapshot<T,E>

Field Summary

Fields

Modifier and Type	Field and Description
protected static int	BM_ENTRIES
protected SparseClusterArray.Entry	changes
protected static int	CHUNK_BASEMASK
static int	CHUNK_BITS
static int	CHUNK_SIZE
protected static int	ELEM_MASK
protected SparseClusterArray.Chunk	head
protected SparseClusterArray.Chunk	lastChunk
protected static int	MAX_BM_INDEX
static int	MAX_CLUSTER_ENTRIES
static int	MAX_CLUSTERS
static int	N_ELEM
static int	N_SEG
protected int	nSet
protected SparseClusterArray.Root	root
static int	S1
static int	S2
static int	S3
static int	SEG_BITS
protected static int	SEG_MASK
protected boolean	trackChanges

Constructor Summary

Constructors

Modifier	Constructor and Description
	SparseClusterArray()
protected	SparseClusterArray(SparseClusterArray base) be careful, this should only be used to get old stored elements during a Snapshot restore

Method Summary

Modifier and Type	Method and Description
int	cardinality()
void	clear()
SparseClusterArray<E>	deepCopy(Cloner<E> elementCloner) deep copy we need to do this depth first, right-to-left, to maintain the Chunk list ordering.
int	firstNullIndex(int i, int length) find first null element within given range [i, i+length[
E	get(int i)
SparseClusterArray.Entry<E>	getChanges()
IndexIterator	getElementIndexIterator()
IndexIterator	getElementIndexIterator(int fromIndex)
<T> SparseClusterArray.Snapshot<E,T>	getSnapshot(Transformer<E,T> transformer) create a snapshot that can be used to restore a certain state of our array This is more suitable than cloning in case the array is very sparse, or the elements contain a lot of transient data we don't want to store
boolean	isTrackingChanges()
java.util.Iterator<E>	iterator()
int	numberOfChunks()
int	numberOfElements()
protected <T> void	populateSnapshot(SparseClusterArray.Snapshot<E,T> snap, Transformer<E,T> transformer)
void	resetChanges()
<T> void	restore(SparseClusterArray.Snapshot<E,T> snap, Transformer<T,E> transformer)
void	revertChanges(SparseClusterArray.Entry<E> changes)
void	set(int i, E e)
void	stopTrackingChanges()
java.lang.String	toString()
void	trackChanges()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

CHUNK_BITS

public static final int CHUNK_BITS

See Also:

Constant Field Values

CHUNK_SIZE

public static final int CHUNK_SIZE

See Also:

Constant Field Values

N_ELEM

public static final int N_ELEM

See Also:

Constant Field Values

ELEM_MASK

protected static final int ELEM_MASK

See Also:

Constant Field Values

BM_ENTRIES

protected static final int BM_ENTRIES

See Also:

Constant Field Values

MAX_BM_INDEX

protected static final int MAX_BM_INDEX

See Also:

Constant Field Values

SEG_BITS

public static final int SEG_BITS

See Also:

Constant Field Values

N_SEG

public static final int N_SEG

See Also:

Constant Field Values

SEG_MASK

protected static final int SEG_MASK

See Also:

Constant Field Values

S1

public static final int S1

See Also:

Constant Field Values

S2

public static final int S2

See Also:

Constant Field Values

S3

public static final int S3

See Also:

Constant Field Values

CHUNK_BASEMASK

protected static final int CHUNK_BASEMASK

See Also:

Constant Field Values

MAX_CLUSTERS

public static final int MAX_CLUSTERS

See Also:

Constant Field Values

MAX_CLUSTER_ENTRIES

public static final int MAX_CLUSTER_ENTRIES

See Also:

Constant Field Values

root

protected SparseClusterArray.Root root

lastChunk

protected SparseClusterArray.Chunk lastChunk

head

protected SparseClusterArray.Chunk head

nSet

protected int nSet

trackChanges

protected boolean trackChanges

changes

protected SparseClusterArray.Entry changes

Constructor Detail

SparseClusterArray

public SparseClusterArray()

SparseClusterArray

protected SparseClusterArray(SparseClusterArray base)

be careful, this should only be used to get old stored elements during a Snapshot restore

Method Detail

get

public E get(int i)

set

public void set(int i,
                E e)

firstNullIndex

public int firstNullIndex(int i,
                          int length)

find first null element within given range [i, i+length[

Returns:

-1 if there is none

deepCopy

public SparseClusterArray<E> deepCopy(Cloner<E> elementCloner)

deep copy we need to do this depth first, right-to-left, to maintain the Chunk list ordering. We also compact during cloning, i.e. remove empty chunks and ChunkNodes/Nodes w/o descendants

getSnapshot

public <T> SparseClusterArray.Snapshot<E,T> getSnapshot(Transformer<E,T> transformer)

create a snapshot that can be used to restore a certain state of our array This is more suitable than cloning in case the array is very sparse, or the elements contain a lot of transient data we don't want to store

populateSnapshot

protected <T> void populateSnapshot(SparseClusterArray.Snapshot<E,T> snap,
                                    Transformer<E,T> transformer)

restore

public <T> void restore(SparseClusterArray.Snapshot<E,T> snap,
                        Transformer<T,E> transformer)

clear

public void clear()

trackChanges

public void trackChanges()

stopTrackingChanges

public void stopTrackingChanges()

isTrackingChanges

public boolean isTrackingChanges()

getChanges

public SparseClusterArray.Entry<E> getChanges()

resetChanges

public void resetChanges()

revertChanges

public void revertChanges(SparseClusterArray.Entry<E> changes)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

numberOfElements

public int numberOfElements()

numberOfChunks

public int numberOfChunks()

getElementIndexIterator

public IndexIterator getElementIndexIterator()

getElementIndexIterator

public IndexIterator getElementIndexIterator(int fromIndex)

iterator

public java.util.Iterator<E> iterator()

Specified by:

iterator in interface java.lang.Iterable<E>

cardinality

public int cardinality()