Class DBTraceAddressSnapRangePropertyMapTree<T, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>>

java.lang.Object

ghidra.util.database.spatial.AbstractConstraintsTree<TraceAddressSnapRange, DR, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

ghidra.util.database.spatial.AbstractRStarConstraintsTree<TraceAddressSnapRange, DR, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

ghidra.util.database.spatial.rect.Abstract2DRStarTree<Address, Long, TraceAddressSnapRange, DR, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

ghidra.trace.database.map.DBTraceAddressSnapRangePropertyMapTree<T,DR>

public class DBTraceAddressSnapRangePropertyMapTree<T, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>>
extends Abstract2DRStarTree<Address, Long, TraceAddressSnapRange, DR, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

Nested Class Summary

Nested Classes

Change	Modifier and Type	Class	Description
	static class	DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>
	static class	DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode
	static interface	DBTraceAddressSnapRangePropertyMapTree.Painter
	static class	DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery

Nested classes/interfaces inherited from class Abstract2DRStarTree

Abstract2DRStarTree.AsSpatialMap<DS,DR,NS,T,Q>, Abstract2DRStarTree.XAxis<X,Y,NS>, Abstract2DRStarTree.YAxis<X,Y,NS>

Nested classes/interfaces inherited from class AbstractRStarConstraintsTree

AbstractRStarConstraintsTree.LeastAreaEnlargementThenLeastArea, AbstractRStarConstraintsTree.LeastDistanceFromCenterToPoint, AbstractRStarConstraintsTree.LeastOverlap, AbstractRStarConstraintsTree.LevelInfo, AbstractRStarConstraintsTree.ReInsertInfo

Nested classes/interfaces inherited from class AbstractConstraintsTree

AbstractConstraintsTree.TreeRecordVisitor, AbstractConstraintsTree.VisitResult

Field Summary

Fields

Change	Modifier and Type	Field	Description
	protected final DBCachedObjectIndex<Long,DR>	dataByParent
	protected final DBTraceAddressSnapRangePropertyMap.DBTraceAddressSnapRangePropertyMapDataFactory<T,DR>	dataFactory
	protected final Comparator<TraceAddressSnapRange>	leftmostComparator
	protected final DBTraceAddressSnapRangePropertyMapSpace<T,DR>	mapSpace
	protected static final int	MAX_CHILDREN	On My Machine (TM), I get the following performance when setting register values, which imply setting state to KNOWN, which is how that involves this tree: MAX_CHILDREN Records / second 3 13,179 10 13,104 15 11,261 20 8,035 50 1,085 62 768
	protected final DBCachedObjectIndex<Long, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode>	nodesByParent

Fields inherited from class Abstract2DRStarTree

axes, space

Fields inherited from class AbstractRStarConstraintsTree

CHEAT_OVERLAP_COUNT, FILL_RATE, MAX_LEVELS, maxChildren, minChildren, REINSERT_RATE, reinsertCount

Fields inherited from class AbstractConstraintsTree

cachedDataChildren, cachedNodeChildren, dataStore, leafLevel, nodeStore, root

Constructor Summary

Constructors

Change	Constructor	Description
	DBTraceAddressSnapRangePropertyMapTree(DBCachedObjectStoreFactory storeFactory, String tableName, DBTraceAddressSnapRangePropertyMapSpace<T,DR> space, Class<DR> dataType, DBTraceAddressSnapRangePropertyMap.DBTraceAddressSnapRangePropertyMapDataFactory<T,DR> dataFactory, boolean upgradable)

Method Summary

Change	Modifier and Type	Method	Description
	protected DR	createDataEntry(DBCachedObjectStore<DR> store, DBRecord record)
	protected DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode	createNodeEntry(DBCachedObjectStore<DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode> store, DBRecord record)
	protected Comparator<TraceAddressSnapRange>	doChooseSplitAxis(List<DBTreeRecord<?, ? extends TraceAddressSnapRange>> children)
	protected int	doChooseSplitIndex(List<DBTreeRecord<?, ? extends TraceAddressSnapRange>> children, Comparator<TraceAddressSnapRange> axis)
	protected void	doDeleteEntry(DR data)
	protected void	doInsertDataEntry(DR entry)
	protected void	doUnparentEntry(DR data)	Remove a data record from the tree, but keep the orphaned record in the table
	protected Collection<? extends DBTreeRecord<?, ? extends TraceAddressSnapRange>>	getChildrenOf(DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode parent)	Get the children.
	protected Collection<DR>	getDataChildrenOf(long parentKey)	For leaf nodes, get the children.
	protected Comparator<TraceAddressSnapRange>	getDefaultBoundsComparator()
	int	getDepth()	For developers and testers.
	protected Rectangle2DDirection	getDirectionOf(DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery query)
	DBTraceAddressSnapRangePropertyMapSpace<T,DR>	getMapSpace()
	protected Collection<DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode>	getNodeChildrenOf(long parentKey)	For non-leaf nodes, get the children.
	TraceAddressSnapRange	getRootBounds()	For developers and testers.
	Collection<? extends DBTreeRecord<?, ? extends TraceAddressSnapRange>>	internalGetChildrenOf(DBTreeNodeRecord<?> rec)	For developers and testers.
	void	paint(DBTraceAddressSnapRangePropertyMapTree.Painter painter, int depth)	For developers and testers.

Methods inherited from class Abstract2DRStarTree

asSpatialMap, getShapeSpace, getSplitAxes

Methods inherited from class AbstractRStarConstraintsTree

checkNodeIntegrity, computeOverlap, doChooseSubtree, doInsert, doInsertData, doOverflowTreatment, doReInsert, doSplit, findChildByMinimumEnlargementCost, findChildByNearlyMinimumOverlapCost, reRoot

Methods inherited from class AbstractConstraintsTree

checkDataIntegrity, checkIntegrity, clear, computeLeafLevel, count, destroySubtree, doAddToCachedChildren, doDecrementDataCount, doFindExact, doRecomputeBounds, doRemoveData, doRemoveFromCachedChildren, doSetParentKey, doUpdateOrDeleteAlongPath, dump, first, getDataByKey, getDataChildrenOf, getNodeChildrenOf, getOrCreateRoot, getParentOf, getUserIndex, init, invalidateCache, isEmpty, iterator, iterator, orderedIterator, resyncMetadata, stream, unionStream, visit, visit, visitAllData, visitDirectory, visitLeaf

Methods inherited from class Object

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

Field Details

MAX_CHILDREN MODIFIED

protected static final int MAX_CHILDREN

constant: 50 → 15

-static int MAX_CHILDREN

+static int MAX_CHILDREN

On My Machine (TM), I get the following performance when setting register values, which imply setting state to KNOWN, which is how that involves this tree:

MAX_CHILDREN	Records / second
3	13,179
10	13,104
15	11,261
20	8,035
50	1,085
62	768

These were measured after setting 100,000 records total. Note MAX_CHILDREN must be less than 64, because of DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode.CHILD_COUNT_MASK. There's definitely a tradeoff in storage, since a lower child count will increase the value of log_{childCount}(recordCount). Similarly, I expect a longer query time, but it's unclear what actual impact that will have given the caches. I have yet to measure that, but for now, I'll set this at 15 and see how things go. It was 50....

See Also:

• Constant Field Values

dataFactory

protected final DBTraceAddressSnapRangePropertyMap.DBTraceAddressSnapRangePropertyMapDataFactory<T, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>> dataFactory

mapSpace

protected final DBTraceAddressSnapRangePropertyMapSpace<T, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>> mapSpace

nodesByParent

protected final DBCachedObjectIndex<Long, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode> nodesByParent

dataByParent

protected final DBCachedObjectIndex<Long, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>> dataByParent

leftmostComparator

protected final Comparator<TraceAddressSnapRange> leftmostComparator

Constructor Details

DBTraceAddressSnapRangePropertyMapTree

public DBTraceAddressSnapRangePropertyMapTree(DBCachedObjectStoreFactory storeFactory,
 String tableName,
 DBTraceAddressSnapRangePropertyMapSpace<T,DR> space,
 Class<DR> dataType,
 DBTraceAddressSnapRangePropertyMap.DBTraceAddressSnapRangePropertyMapDataFactory<T,DR> dataFactory,
 boolean upgradable)
                                       throws VersionException,
IOException

Throws:

VersionException

IOException

Method Details

getDefaultBoundsComparator

protected Comparator<TraceAddressSnapRange> getDefaultBoundsComparator()

Specified by:

getDefaultBoundsComparator in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

createDataEntry

protected DR createDataEntry(DBCachedObjectStore<DR> store,
 DBRecord record)

Specified by:

createDataEntry in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

createNodeEntry

protected DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode createNodeEntry(DBCachedObjectStore<DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode> store,
 DBRecord record)

Specified by:

createNodeEntry in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

getDirectionOf

protected Rectangle2DDirection getDirectionOf(DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery query)

getNodeChildrenOf

protected Collection<DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode> getNodeChildrenOf(long parentKey)

Description copied from class: AbstractConstraintsTree

For non-leaf nodes, get the children.

For leaf nodes, the behavior is undefined. Note that the query should not filter the children, only order them. Filtering is performed by AbstractConstraintsTree<DS extends BoundedShape<NS>, DR extends DBTreeDataRecord<DS,NS,T>, NS extends BoundingShape<NS>, NR extends DBTreeNodeRecord<NS>, T, Q extends Query<DS,NS>>.TreeRecordVisitor.

Specified by:

getNodeChildrenOf in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

Parameters:

parentKey - the key of the parent whose children to get

Returns:

an iterable of the children

getDataChildrenOf

protected Collection<DR> getDataChildrenOf(long parentKey)

Description copied from class: AbstractConstraintsTree

For leaf nodes, get the children.

For non-leaf nodes, the behavior is undefined. Note that the query should not filter the children, only order them, or else the collection will return an incorrect Collection.size(). Filtering is performed by AbstractConstraintsTree<DS extends BoundedShape<NS>, DR extends DBTreeDataRecord<DS,NS,T>, NS extends BoundingShape<NS>, NR extends DBTreeNodeRecord<NS>, T, Q extends Query<DS,NS>>.TreeRecordVisitor.

Specified by:

getDataChildrenOf in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

Parameters:

parentKey - the key of the parent whose children to get

Returns:

an iterable of the children

doUnparentEntry

protected void doUnparentEntry(DR data)

Description copied from class: AbstractConstraintsTree

Remove a data record from the tree, but keep the orphaned record in the table

Note that at most one orphaned record should be in the table at any time, otherwise behavior is undefined. It is up to the implementor to provide a means of inserting orphaned data records back into the tree. This is useful for implementations which allow a data record's shape to be mutated: Orphan the record, adjust its shape, re-insert the orphan.

Overrides:

doUnparentEntry in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

Parameters:

data - the data record

doDeleteEntry

protected void doDeleteEntry(DR data)

Overrides:

doDeleteEntry in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

doInsertDataEntry

protected void doInsertDataEntry(DR entry)

getMapSpace

public DBTraceAddressSnapRangePropertyMapSpace<T,DR> getMapSpace()

paint NEW

public void paint(DBTraceAddressSnapRangePropertyMapTree.Painter painter,
 int depth)

For developers and testers.

getDepth NEW

public int getDepth()

For developers and testers.

getRootBounds NEW

public TraceAddressSnapRange getRootBounds()

For developers and testers.

internalGetChildrenOf

public Collection<? extends DBTreeRecord<?, ? extends TraceAddressSnapRange>> internalGetChildrenOf(DBTreeNodeRecord<?> rec)

For developers and testers.

doChooseSplitAxis

protected Comparator<TraceAddressSnapRange> doChooseSplitAxis(List<DBTreeRecord<?, ? extends TraceAddressSnapRange>> children)

Overrides:

doChooseSplitAxis in class AbstractRStarConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

doChooseSplitIndex

protected int doChooseSplitIndex(List<DBTreeRecord<?, ? extends TraceAddressSnapRange>> children,
 Comparator<TraceAddressSnapRange> axis)

Overrides:

doChooseSplitIndex in class AbstractRStarConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

getChildrenOf NEW

protected Collection<? extends DBTreeRecord<?, ? extends TraceAddressSnapRange>> getChildrenOf(DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode parent)

Description copied from class: AbstractConstraintsTree

Get the children.

Because the children may be either nodes or data, the exact type is not known. The only guarantee is that it is a tree record, which permits access to its bounds and parent. Note that the query should not filter the children, only order them, or else the collection will return an incorrect Collection.size(). Filtering is performed by AbstractConstraintsTree<DS extends BoundedShape<NS>, DR extends DBTreeDataRecord<DS,NS,T>, NS extends BoundingShape<NS>, NR extends DBTreeNodeRecord<NS>, T, Q extends Query<DS,NS>>.TreeRecordVisitor.

Overrides:

getChildrenOf in class AbstractConstraintsTree<TraceAddressSnapRange, DR extends DBTraceAddressSnapRangePropertyMapTree.AbstractDBTraceAddressSnapRangePropertyMapData<T>, TraceAddressSnapRange, DBTraceAddressSnapRangePropertyMapTree.DBTraceAddressSnapRangePropertyMapNode, T, DBTraceAddressSnapRangePropertyMapTree.TraceAddressSnapRangeQuery>

Parameters:

parent - the parent node

Returns:

a collection of the children