Represents a compact patricia tree. More...

Collaboration diagram for catapult::tree::PatriciaTree< TEncoder, TDataSource >:

[legend]

Classes
struct	PathValuePairRef

Public Types
using	KeyType = typename TEncoder::KeyType

using	ValueType = typename TEncoder::ValueType

Public Member Functions
	PatriciaTree (TDataSource &dataSource)
	Creates a tree around a dataSource. More...

Hash256	root () const
	Gets the root hash that uniquely identifies this tree. More...

void	set (const KeyType &key, const ValueType &value)
	Sets key to value in the tree. More...

bool	unset (const KeyType &key)
	Removes the value associated with key from the tree. More...

std::pair< Hash256, bool >	lookup (const KeyType &key, std::vector< TreeNode > &nodePath) const
	Tries to find the value associated with key in the tree and stores proof of existence or not in nodePath. More...

bool	tryLoad (const Hash256 &rootHash)
	Loads the node with hash rootHash and sets it as the root node. More...

void	setRoot (const TreeNode &rootNode)
	Sets the root to rootNode. More...

void	clear ()
	Clears the tree. More...

void	saveAll ()
	Saves all tree nodes to the underlying data source. More...

Private Member Functions
TreeNode	set (const TreeNode &node, const PathValuePairRef &newPair)

LeafTreeNode	createLeaf (const PathValuePairRef &pair)

BranchTreeNode	branchLeafNode (const LeafTreeNode &leafNode, const PathValuePairRef &newPair)

BranchTreeNode	updateBranchLink (BranchTreeNode &&branchNode, const PathValuePairRef &newPair)

BranchTreeNode	insertNewPairIntoBranch (BranchTreeNode &branchNode, const TreeNodePath &branchPath, size_t differenceIndex, const PathValuePairRef &newPair)

bool	unset (const TreeNode &node, const TreeNodePath &keyPath, TreeNode &updatedNode, bool &canMerge)

TreeNode	unsetBranchLink (BranchTreeNode &&branchNode, size_t linkIndex)

TreeNode	updateBranchLink (BranchTreeNode &&branchNode, size_t linkIndex, const TreeNode &linkedNode)

std::pair< Hash256, bool >	lookup (const TreeNode &node, const TreeNodePath &keyPath, std::vector< TreeNode > &nodePath) const

void	save (const TreeNode &node)

void	saveAll (const TreeNode &node)

std::unique_ptr< const TreeNode >	getLinkedNode (const BranchTreeNode &branchNode, size_t index) const

void	setLink (BranchTreeNode &branchNode, const TreeNode &node, size_t index)

template<typename TNode >
void	setLink (BranchTreeNode &branchNode, const TNode &node, size_t index)

Static Private Member Functions
static std::pair< Hash256, bool >	LookupNotFoundResult ()

Private Attributes
TDataSource &	m_dataSource

TreeNode	m_rootNode

Detailed Description

template<typename TEncoder, typename TDataSource>
class catapult::tree::PatriciaTree< TEncoder, TDataSource >

Represents a compact patricia tree.

Member Typedef Documentation

◆ KeyType

template<typename TEncoder, typename TDataSource>

using catapult::tree::PatriciaTree< TEncoder, TDataSource >::KeyType = typename TEncoder::KeyType

◆ ValueType

template<typename TEncoder, typename TDataSource>

using catapult::tree::PatriciaTree< TEncoder, TDataSource >::ValueType = typename TEncoder::ValueType

Constructor & Destructor Documentation

◆ PatriciaTree()

template<typename TEncoder, typename TDataSource>

catapult::tree::PatriciaTree< TEncoder, TDataSource >::PatriciaTree ( TDataSource & dataSource )

inlineexplicit

Creates a tree around a dataSource.

Member Function Documentation

◆ branchLeafNode()

template<typename TEncoder, typename TDataSource>

BranchTreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::branchLeafNode	(	const LeafTreeNode &	leafNode,
		const PathValuePairRef &	newPair
	)

inlineprivate

Here is the caller graph for this function:

◆ clear()

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::clear ( )

inline

Clears the tree.

◆ createLeaf()

template<typename TEncoder, typename TDataSource>

LeafTreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::createLeaf ( const PathValuePairRef & pair )

inlineprivate

Here is the caller graph for this function:

◆ getLinkedNode()

template<typename TEncoder, typename TDataSource>

std::unique_ptr<const TreeNode> catapult::tree::PatriciaTree< TEncoder, TDataSource >::getLinkedNode	(	const BranchTreeNode &	branchNode,
		size_t	index
	)		const

inlineprivate

Here is the caller graph for this function:

◆ insertNewPairIntoBranch()

template<typename TEncoder, typename TDataSource>

BranchTreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::insertNewPairIntoBranch	(	BranchTreeNode &	branchNode,
		const TreeNodePath &	branchPath,
		size_t	differenceIndex,
		const PathValuePairRef &	newPair
	)

inlineprivate

Here is the caller graph for this function:

◆ lookup() [1/2]

template<typename TEncoder, typename TDataSource>

std::pair<Hash256, bool> catapult::tree::PatriciaTree< TEncoder, TDataSource >::lookup	(	const KeyType &	key,
		std::vector< TreeNode > &	nodePath
	)		const

inline

Tries to find the value associated with key in the tree and stores proof of existence or not in nodePath.

Here is the caller graph for this function:

◆ lookup() [2/2]

template<typename TEncoder, typename TDataSource>

std::pair<Hash256, bool> catapult::tree::PatriciaTree< TEncoder, TDataSource >::lookup	(	const TreeNode &	node,
		const TreeNodePath &	keyPath,
		std::vector< TreeNode > &	nodePath
	)		const

inlineprivate

◆ LookupNotFoundResult()

template<typename TEncoder, typename TDataSource>

static std::pair<Hash256, bool> catapult::tree::PatriciaTree< TEncoder, TDataSource >::LookupNotFoundResult ( )

inlinestaticprivate

Here is the caller graph for this function:

◆ root()

template<typename TEncoder, typename TDataSource>

Hash256 catapult::tree::PatriciaTree< TEncoder, TDataSource >::root ( ) const

inline

Gets the root hash that uniquely identifies this tree.

◆ save()

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::save ( const TreeNode & node )

inlineprivate

Here is the caller graph for this function:

◆ saveAll() [1/2]

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::saveAll ( )

inline

Saves all tree nodes to the underlying data source.

Here is the caller graph for this function:

◆ saveAll() [2/2]

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::saveAll ( const TreeNode & node )

inlineprivate

◆ set() [1/2]

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::set	(	const KeyType &	key,
		const ValueType &	value
	)

inline

Sets key to value in the tree.

Here is the caller graph for this function:

◆ set() [2/2]

template<typename TEncoder, typename TDataSource>

TreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::set	(	const TreeNode &	node,
		const PathValuePairRef &	newPair
	)

inlineprivate

◆ setLink() [1/2]

template<typename TEncoder, typename TDataSource>

template<typename TNode >

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::setLink	(	BranchTreeNode &	branchNode,
		const TNode &	node,
		size_t	index
	)

inlineprivate

◆ setLink() [2/2]

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::setLink	(	BranchTreeNode &	branchNode,
		const TreeNode &	node,
		size_t	index
	)

inlineprivate

Here is the caller graph for this function:

◆ setRoot()

template<typename TEncoder, typename TDataSource>

void catapult::tree::PatriciaTree< TEncoder, TDataSource >::setRoot ( const TreeNode & rootNode )

inline

Sets the root to rootNode.

◆ tryLoad()

template<typename TEncoder, typename TDataSource>

bool catapult::tree::PatriciaTree< TEncoder, TDataSource >::tryLoad ( const Hash256 & rootHash )

inline

Loads the node with hash rootHash and sets it as the root node.

◆ unset() [1/2]

template<typename TEncoder, typename TDataSource>

bool catapult::tree::PatriciaTree< TEncoder, TDataSource >::unset ( const KeyType & key )

inline

Removes the value associated with key from the tree.

Here is the caller graph for this function:

◆ unset() [2/2]

template<typename TEncoder, typename TDataSource>

bool catapult::tree::PatriciaTree< TEncoder, TDataSource >::unset	(	const TreeNode &	node,
		const TreeNodePath &	keyPath,
		TreeNode &	updatedNode,
		bool &	canMerge
	)

inlineprivate

◆ unsetBranchLink()

template<typename TEncoder, typename TDataSource>

TreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::unsetBranchLink	(	BranchTreeNode &&	branchNode,
		size_t	linkIndex
	)

inlineprivate

Here is the caller graph for this function:

◆ updateBranchLink() [1/2]

template<typename TEncoder, typename TDataSource>

BranchTreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::updateBranchLink	(	BranchTreeNode &&	branchNode,
		const PathValuePairRef &	newPair
	)

inlineprivate

Here is the caller graph for this function:

◆ updateBranchLink() [2/2]

template<typename TEncoder, typename TDataSource>

TreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::updateBranchLink	(	BranchTreeNode &&	branchNode,
		size_t	linkIndex,
		const TreeNode &	linkedNode
	)

inlineprivate

Member Data Documentation

◆ m_dataSource

template<typename TEncoder, typename TDataSource>

TDataSource& catapult::tree::PatriciaTree< TEncoder, TDataSource >::m_dataSource

private

◆ m_rootNode

template<typename TEncoder, typename TDataSource>

TreeNode catapult::tree::PatriciaTree< TEncoder, TDataSource >::m_rootNode

private

The documentation for this class was generated from the following file:

PatriciaTree.h

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

template<typename TEncoder, typename TDataSource> class catapult::tree::PatriciaTree< TEncoder, TDataSource >

Member Typedef Documentation

◆ KeyType

◆ ValueType

Constructor & Destructor Documentation

◆ PatriciaTree()

Member Function Documentation

◆ branchLeafNode()

◆ clear()

◆ createLeaf()

◆ getLinkedNode()

◆ insertNewPairIntoBranch()

◆ lookup() [1/2]

◆ lookup() [2/2]

◆ LookupNotFoundResult()

◆ root()

◆ save()

◆ saveAll() [1/2]

◆ saveAll() [2/2]

◆ set() [1/2]

◆ set() [2/2]

◆ setLink() [1/2]

◆ setLink() [2/2]

◆ setRoot()

◆ tryLoad()

◆ unset() [1/2]

◆ unset() [2/2]

◆ unsetBranchLink()

◆ updateBranchLink() [1/2]

◆ updateBranchLink() [2/2]

Member Data Documentation

◆ m_dataSource

◆ m_rootNode

template<typename TEncoder, typename TDataSource>
class catapult::tree::PatriciaTree< TEncoder, TDataSource >