Package ghidra.util.database.spatial

Class 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>>

java.lang.Object

ghidra.util.database.spatial.AbstractConstraintsTree<DS,DR,NS,NR,T,Q>

Direct Known Subclasses:

AbstractRStarConstraintsTree

public abstract class 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>>
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	AbstractConstraintsTree.TreeRecordVisitor
protected static enum	AbstractConstraintsTree.VisitResult

Field Summary

Fields

Modifier and Type	Field	Description
protected final Map<Long,Collection<DR>>	cachedDataChildren
protected final Map<Long,Collection<NR>>	cachedNodeChildren
protected final DBCachedObjectStore<DR>	dataStore
protected int	leafLevel
protected final DBCachedObjectStore<NR>	nodeStore
protected NR	root

Constructor Summary

Constructors

Constructor	Description
AbstractConstraintsTree(DBCachedObjectStoreFactory storeFactory, String tableName, Class<DR> dataType, Class<NR> nodeType, boolean upgradable)

Method Summary

Modifier and Type	Method	Description
abstract AbstractConstraintsTreeSpatialMap<DS,DR,NS,T,Q>	asSpatialMap()
protected void	checkDataIntegrity(DR d)	Check the integrity of a single data entry.
void	checkIntegrity()	An integrity checker for use by tree developers and testers.
protected void	checkNodeIntegrity(NR n)	Check the integrity of a single node entry.
protected void	clear(Q query)
protected int	computeLeafLevel()
protected int	count(Q query)
protected abstract DR	createDataEntry(DBCachedObjectStore<DR> store, DBRecord record)
protected abstract NR	createNodeEntry(DBCachedObjectStore<NR> store, DBRecord record)
protected void	destroySubtree(NR node)
protected <R> void	doAddToCachedChildren(long parentKey, R child, Map<Long,Collection<R>> cache)
protected void	doDecrementDataCount(NR node)
protected void	doDeleteEntry(DR data)
protected DR	doFindExact(DS shape, T value, Q query)
protected abstract DR	doInsertData(DS shape, T value)
protected void	doRecomputeBounds(NR node)
protected boolean	doRemoveData(DS shape, T value, Q query)
protected <R> void	doRemoveFromCachedChildren(long parentKey, R child, Map<Long,Collection<R>> cache)
protected <R extends DBTreeRecord<?, ?>> void	doSetParentKey(R child, long key, Map<Long,Collection<R>> cache)
protected void	doUnparentEntry(DR data)	Remove a data record from the tree, but keep the orphaned record in the table
protected void	doUpdateOrDeleteAlongPath(NR node)
protected void	dump(Q query)	Dump the tree to the console, for debugging and testing purposes
protected DR	first(Q query)
protected Collection<? extends DBTreeRecord<?,? extends NS>>	getChildrenOf(NR parent)	Get the children.
DR	getDataByKey(long key)
protected abstract Collection<DR>	getDataChildrenOf(long parentKey)	For leaf nodes, get the children.
protected Collection<DR>	getDataChildrenOf(NR parent)	For leaf nodes, get the children.
protected abstract Comparator<NS>	getDefaultBoundsComparator()
protected abstract Collection<NR>	getNodeChildrenOf(long parentKey)	For non-leaf nodes, get the children.
protected Collection<NR>	getNodeChildrenOf(NR parent)	For non-leaf nodes, get the children.
protected NR	getOrCreateRoot()
protected NR	getParentOf(DBTreeRecord<?,?> n)
<K> DBCachedObjectIndex<K,DR>	getUserIndex(Class<K> fieldClass, DBObjectColumn column)
protected void	init()
void	invalidateCache()
protected boolean	isEmpty(Q query)
protected Iterator<DR>	iterator(NR node, Q query)
protected Iterator<DR>	iterator(Q query)
protected Iterator<DR>	orderedIterator(Q query)
protected void	resyncMetadata(NR node)
protected NS	unionStream(Stream<NS> shapes)
protected AbstractConstraintsTree.VisitResult	visit(NR parent, NR node, Q query, AbstractConstraintsTree<DS,DR,NS,NR,T,Q>.TreeRecordVisitor visitor, boolean ordered)
protected AbstractConstraintsTree.VisitResult	visit(Q query, AbstractConstraintsTree<DS,DR,NS,NR,T,Q>.TreeRecordVisitor visitor, boolean ordered)
protected void	visitAllData(Q query, Consumer<DR> consumer, boolean ordered)

Methods inherited from class java.lang.Object

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

Field Details

dataStore

protected final DBCachedObjectStore<DR extends DBTreeDataRecord<DS,NS,T>> dataStore

nodeStore

protected final DBCachedObjectStore<NR extends DBTreeNodeRecord<NS>> nodeStore

cachedDataChildren

protected final Map<Long,Collection<DR extends DBTreeDataRecord<DS,NS,T>>> cachedDataChildren

cachedNodeChildren

protected final Map<Long,Collection<NR extends DBTreeNodeRecord<NS>>> cachedNodeChildren

root

protected NR extends DBTreeNodeRecord<NS> root

leafLevel

protected int leafLevel

Constructor Details

AbstractConstraintsTree

public AbstractConstraintsTree(DBCachedObjectStoreFactory storeFactory,
 String tableName,
 Class<DR> dataType,
 Class<NR> nodeType,
 boolean upgradable)
                        throws VersionException,
IOException

Throws:

VersionException

IOException

Method Details

createDataEntry

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

createNodeEntry

protected abstract NR createNodeEntry(DBCachedObjectStore<NR> store,
 DBRecord record)

init

protected void init()

getDefaultBoundsComparator

protected abstract Comparator<NS> getDefaultBoundsComparator()

getNodeChildrenOf

protected abstract Collection<NR> getNodeChildrenOf(long parentKey)

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.

Parameters:

parentKey - the key of the parent whose children to get

Returns:

an iterable of the children

getNodeChildrenOf

protected Collection<NR> getNodeChildrenOf(NR parent)

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, 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.

Parameters:

parent - the parent node

Returns:

a collection of the children

getDataChildrenOf

protected abstract Collection<DR> getDataChildrenOf(long parentKey)

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.

Parameters:

parentKey - the key of the parent whose children to get

Returns:

an iterable of the children

getDataChildrenOf

protected Collection<DR> getDataChildrenOf(NR parent)

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.

Parameters:

parent - the parent node

Returns:

a collection of the children

getChildrenOf

protected Collection<? extends DBTreeRecord<?,? extends NS>> getChildrenOf(NR parent)

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.

Parameters:

parent - the parent node

Returns:

a collection of the children

getParentOf

protected NR getParentOf(DBTreeRecord<?,?> n)

getOrCreateRoot

protected NR getOrCreateRoot()

computeLeafLevel

protected int computeLeafLevel()

doInsertData

protected abstract DR doInsertData(DS shape,
 T value)

visit

protected AbstractConstraintsTree.VisitResult visit(Q query,
 AbstractConstraintsTree<DS,DR,NS,NR,T,Q>.TreeRecordVisitor visitor,
 boolean ordered)

visit

protected AbstractConstraintsTree.VisitResult visit(NR parent,
 NR node,
 Q query,
 AbstractConstraintsTree<DS,DR,NS,NR,T,Q>.TreeRecordVisitor visitor,
 boolean ordered)

iterator

protected Iterator<DR> iterator(Q query)

iterator

protected Iterator<DR> iterator(NR node,
 Q query)

orderedIterator

protected Iterator<DR> orderedIterator(Q query)

count

protected int count(Q query)

isEmpty

protected boolean isEmpty(Q query)

first

protected DR first(Q query)

visitAllData

protected void visitAllData(Q query,
 Consumer<DR> consumer,
 boolean ordered)

doFindExact

protected DR doFindExact(DS shape,
 T value,
 Q query)

doUpdateOrDeleteAlongPath

protected void doUpdateOrDeleteAlongPath(NR node)

doDecrementDataCount

protected void doDecrementDataCount(NR node)

unionStream

protected NS unionStream(Stream<NS> shapes)

doRecomputeBounds

protected void doRecomputeBounds(NR node)

doRemoveFromCachedChildren

protected <R> void doRemoveFromCachedChildren(long parentKey,
 R child,
 Map<Long,Collection<R>> cache)

doAddToCachedChildren

protected <R> void doAddToCachedChildren(long parentKey,
 R child,
 Map<Long,Collection<R>> cache)

doSetParentKey

protected <R extends DBTreeRecord<?,
?>> void doSetParentKey(R child,
 long key,
 Map<Long,Collection<R>> cache)

doUnparentEntry

protected void doUnparentEntry(DR data)

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.

Parameters:

data - the data record

doDeleteEntry

protected void doDeleteEntry(DR data)

doRemoveData

protected boolean doRemoveData(DS shape,
 T value,
 Q query)

destroySubtree

protected void destroySubtree(NR node)

resyncMetadata

protected void resyncMetadata(NR node)

clear

protected void clear(Q query)

dump

protected void dump(Q query)

Dump the tree to the console, for debugging and testing purposes

Parameters:

query - optionally include only those portions matching a query

checkNodeIntegrity

protected void checkNodeIntegrity(NR n)

Check the integrity of a single node entry.

This method is for tree developers and testers. Override this method if you have additional integrity checks.

Parameters:

n - the entry to check

checkDataIntegrity

protected void checkDataIntegrity(DR d)

Check the integrity of a single data entry.

This method is for tree developers and testers. Override this method if you have additional integrity checks.

Parameters:

d - the entry to check

checkIntegrity

public void checkIntegrity()

An integrity checker for use by tree developers and testers.

To incorporate additional checks, please prefer to override checkNodeIntegrity(DBTreeNodeRecord) and/or checkDataIntegrity(DBTreeDataRecord) instead of this method.

asSpatialMap

public abstract AbstractConstraintsTreeSpatialMap<DS,DR,NS,T,Q> asSpatialMap()

getDataByKey

public DR getDataByKey(long key)

getUserIndex

public <K> DBCachedObjectIndex<K,DR> getUserIndex(Class<K> fieldClass,
 DBObjectColumn column)

invalidateCache

public void invalidateCache()