A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree. More...

#include <SHAMap.h>

Collaboration diagram for xrpl::SHAMap:

[legend]

Classes
struct	MissingNodes
class	ConstIterator

Public Types
using	DeltaItem
using	Delta = std::map<uint256, DeltaItem>

Public Member Functions
	SHAMap ()=delete
	SHAMap (SHAMap const &)=delete
SHAMap &	operator= (SHAMap const &)=delete
	SHAMap (SHAMap const &other, bool isMutable)
	SHAMap (SHAMapType t, Family &f)
	SHAMap (SHAMapType t, uint256 const &hash, Family &f)
	~SHAMap ()=default
Family const &	family () const
Family &	family ()
ConstIterator	begin () const
ConstIterator	end () const
std::shared_ptr< SHAMap >	snapShot (bool isMutable) const
void	setFull ()
void	setLedgerSeq (std::uint32_t lseq)
bool	fetchRoot (SHAMapHash const &hash, SHAMapSyncFilter const *filter)
bool	hasItem (uint256 const &id) const
	Does the tree have an item with the given ID?
bool	delItem (uint256 const &id)
bool	addItem (SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
SHAMapHash	getHash () const
bool	updateGiveItem (SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
bool	addGiveItem (SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
boost::intrusive_ptr< SHAMapItem const > const &	peekItem (uint256 const &id) const
boost::intrusive_ptr< SHAMapItem const > const &	peekItem (uint256 const &id, SHAMapHash &hash) const
ConstIterator	upperBound (uint256 const &id) const
	Find the first item after the given item.
ConstIterator	lowerBound (uint256 const &id) const
	Find the object with the greatest object id smaller than the input id.
void	visitNodes (std::function< bool(SHAMapTreeNode &)> const &function) const
	Visit every node in this SHAMap.
void	visitDifferences (SHAMap const *have, std::function< bool(SHAMapTreeNode const &)> const &) const
	Visit every node in this SHAMap that is not present in the specified SHAMap.
void	visitLeaves (std::function< void(boost::intrusive_ptr< SHAMapItem const > const &)> const &) const
	Visit every leaf node in this SHAMap.
std::vector< std::pair< SHAMapNodeID, uint256 > >	getMissingNodes (int maxNodes, SHAMapSyncFilter const *filter)
	Check for nodes in the SHAMap not available.
bool	getNodeFat (SHAMapNodeID const &wanted, std::vector< std::pair< SHAMapNodeID, Blob > > &data, bool fatLeaves, std::uint32_t depth) const
std::optional< std::vector< Blob > >	getProofPath (uint256 const &key) const
	Get the proof path of the key.
void	serializeRoot (Serializer &s) const
	Serializes the root in a format appropriate for sending over the wire.
SHAMapAddNode	addRootNode (SHAMapHash const &hash, Slice const &rootNode, SHAMapSyncFilter const *filter)
SHAMapAddNode	addKnownNode (SHAMapNodeID const &nodeID, Slice const &rawNode, SHAMapSyncFilter const *filter)
void	setImmutable ()
bool	isSynching () const
void	setSynching ()
void	clearSynching ()
bool	isValid () const
bool	compare (SHAMap const &otherMap, Delta &differences, int maxCount) const
int	unshare ()
	Convert any modified nodes to shared.
int	flushDirty (NodeObjectType t)
	Flush modified nodes to the nodestore and convert them to shared.
void	walkMap (std::vector< SHAMapMissingNode > &missingNodes, int maxMissing) const
bool	walkMapParallel (std::vector< SHAMapMissingNode > &missingNodes, int maxMissing) const
bool	deepCompare (SHAMap &other) const
void	setUnbacked ()
void	dump (bool withHashes=false) const
void	invariants () const

Static Public Member Functions
static bool	verifyProofPath (uint256 const &rootHash, uint256 const &key, std::vector< Blob > const &path)
	Verify the proof path.

Static Public Attributes
static constexpr unsigned int	kBranchFactor = SHAMapInnerNode::kBranchFactor
	Number of children each non-leaf node has (the 'radix tree' part of the map).
static constexpr unsigned int	kLeafDepth = 64
	The depth of the hash map: data is only present in the leaves.

Private Types
using	SharedPtrNodeStack = std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>>
using	DeltaRef
using	descendCallback = std::function<void(SHAMapTreeNodePtr, SHAMapHash const&)>

Private Member Functions
SHAMapTreeNodePtr	cacheLookup (SHAMapHash const &hash) const
void	canonicalize (SHAMapHash const &hash, SHAMapTreeNodePtr &) const
SHAMapTreeNodePtr	fetchNodeFromDB (SHAMapHash const &hash) const
SHAMapTreeNodePtr	fetchNodeNT (SHAMapHash const &hash) const
SHAMapTreeNodePtr	fetchNodeNT (SHAMapHash const &hash, SHAMapSyncFilter const *filter) const
SHAMapTreeNodePtr	fetchNode (SHAMapHash const &hash) const
SHAMapTreeNodePtr	checkFilter (SHAMapHash const &hash, SHAMapSyncFilter const *filter) const
void	dirtyUp (SharedPtrNodeStack &stack, uint256 const &target, SHAMapTreeNodePtr terminal)
	Update hashes up to the root.
SHAMapLeafNode *	walkTowardsKey (uint256 const &id, SharedPtrNodeStack *stack=nullptr) const
	Walk towards the specified id, returning the node.
SHAMapLeafNode *	findKey (uint256 const &id) const
	Return nullptr if key not found.
template<class Node>
intr_ptr::SharedPtr< Node >	unshareNode (intr_ptr::SharedPtr< Node >, SHAMapNodeID const &nodeID)
	Unshare the node, allowing it to be modified.
template<class Node>
intr_ptr::SharedPtr< Node >	preFlushNode (intr_ptr::SharedPtr< Node > node) const
	prepare a node to be modified before flushing
SHAMapTreeNodePtr	writeNode (NodeObjectType t, SHAMapTreeNodePtr node) const
	write and canonicalize modified node
SHAMapLeafNode *	firstBelow (SHAMapTreeNodePtr node, SharedPtrNodeStack &stack, int branch=0) const
SHAMapLeafNode *	lastBelow (SHAMapTreeNodePtr node, SharedPtrNodeStack &stack, int branch=kBranchFactor) const
SHAMapLeafNode *	belowHelper (SHAMapTreeNodePtr node, SharedPtrNodeStack &stack, int branch, std::tuple< int, std::function< bool(int)>, std::function< void(int &)> > const &loopParams) const
SHAMapTreeNode *	descend (SHAMapInnerNode *, int branch) const
SHAMapTreeNode *	descendThrow (SHAMapInnerNode *, int branch) const
SHAMapTreeNodePtr	descend (SHAMapInnerNode &, int branch) const
SHAMapTreeNodePtr	descendThrow (SHAMapInnerNode &, int branch) const
SHAMapTreeNode *	descendAsync (SHAMapInnerNode parent, int branch, SHAMapSyncFilter const filter, bool &pending, descendCallback &&) const
std::pair< SHAMapTreeNode *, SHAMapNodeID >	descend (SHAMapInnerNode parent, SHAMapNodeID const &parentID, int branch, SHAMapSyncFilter const filter) const
SHAMapTreeNodePtr	descendNoStore (SHAMapInnerNode &, int branch) const
boost::intrusive_ptr< SHAMapItem const > const &	onlyBelow (SHAMapTreeNode *) const
	If there is only one leaf below this node, get its contents.
bool	hasInnerNode (SHAMapNodeID const &nodeID, SHAMapHash const &hash) const
	Does this map have this inner node?
bool	hasLeafNode (uint256 const &tag, SHAMapHash const &hash) const
	Does this map have this leaf node?
SHAMapLeafNode const *	peekFirstItem (SharedPtrNodeStack &stack) const
SHAMapLeafNode const *	peekNextItem (uint256 const &id, SharedPtrNodeStack &stack) const
bool	walkBranch (SHAMapTreeNode *node, boost::intrusive_ptr< SHAMapItem const > const &otherMapItem, bool isFirstMap, Delta &differences, int &maxCount) const
int	walkSubTree (bool doWrite, NodeObjectType t)
void	gmnProcessNodes (MissingNodes &, MissingNodes::StackEntry &node)
SHAMapTreeNodePtr	finishFetch (SHAMapHash const &hash, std::shared_ptr< NodeObject > const &object) const

Static Private Member Functions
static void	gmnProcessDeferredReads (MissingNodes &)

Private Attributes
Family &	f_
beast::Journal	journal_
std::uint32_t	cowid_ = 1
	ID to distinguish this map for all others we're sharing nodes with.
std::uint32_t	ledgerSeq_ = 0
	The sequence of the ledger that this map references, if any.
SHAMapTreeNodePtr	root_
SHAMapState	state_
SHAMapType const	type_
bool	backed_ = true
bool	full_ = false

Detailed Description

A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.

A radix tree is a tree with two properties:

The key for a node is represented by the node's position in the tree (the "prefix property").
A node with only one child is merged with that child (the "merge property")

These properties result in a significantly smaller memory footprint for a radix tree.

A fan-out of 16 means that each node in the tree has at most 16 children. See https://en.wikipedia.org/wiki/Radix_tree

A Merkle tree is a tree where each non-leaf node is labelled with the hash of the combined labels of its children nodes.

A key property of a Merkle tree is that testing for node inclusion is O(log(N)) where N is the number of nodes in the tree.

See https://en.wikipedia.org/wiki/Merkle_tree

Definition at line 76 of file SHAMap.h.

Member Typedef Documentation

◆ DeltaItem

using xrpl::SHAMap::DeltaItem

Initial value:

std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>

std::pair

Definition at line 102 of file SHAMap.h.

◆ Delta

using xrpl::SHAMap::Delta = std::map<uint256, DeltaItem>

Definition at line 104 of file SHAMap.h.

◆ SharedPtrNodeStack

using xrpl::SHAMap::SharedPtrNodeStack = std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>>

private

Definition at line 329 of file SHAMap.h.

◆ DeltaRef

using xrpl::SHAMap::DeltaRef

private

Initial value:

std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>

Definition at line 330 of file SHAMap.h.

◆ descendCallback

using xrpl::SHAMap::descendCallback = std::function<void(SHAMapTreeNodePtr, SHAMapHash const&)>

private

Definition at line 409 of file SHAMap.h.

Constructor & Destructor Documentation

◆ SHAMap() [1/5]

xrpl::SHAMap::SHAMap ( )

delete

◆ SHAMap() [2/5]

xrpl::SHAMap::SHAMap ( SHAMap const & )

delete

◆ SHAMap() [3/5]

xrpl::SHAMap::SHAMap	(	SHAMap const &	other,
		bool	isMutable )

Definition at line 76 of file SHAMap.cpp.

◆ SHAMap() [4/5]

xrpl::SHAMap::SHAMap	(	SHAMapType	t,
		Family &	f )

Definition at line 60 of file SHAMap.cpp.

◆ SHAMap() [5/5]

xrpl::SHAMap::SHAMap	(	SHAMapType	t,
		uint256 const &	hash,
		Family &	f )

Definition at line 70 of file SHAMap.cpp.

◆ ~SHAMap()

xrpl::SHAMap::~SHAMap ( )

default

Member Function Documentation

◆ operator=()

SHAMap & xrpl::SHAMap::operator= ( SHAMap const & )

delete

◆ family() [1/2]

Family const & xrpl::SHAMap::family ( ) const

Definition at line 122 of file SHAMap.h.

◆ family() [2/2]

Family & xrpl::SHAMap::family ( )

Definition at line 128 of file SHAMap.h.

◆ begin()

SHAMap::ConstIterator xrpl::SHAMap::begin ( ) const

Definition at line 691 of file SHAMap.h.

◆ end()

SHAMap::ConstIterator xrpl::SHAMap::end ( ) const

Definition at line 697 of file SHAMap.h.

◆ snapShot()

std::shared_ptr< SHAMap > xrpl::SHAMap::snapShot ( bool isMutable ) const

Definition at line 94 of file SHAMap.cpp.

◆ setFull()

void xrpl::SHAMap::setFull ( )

Definition at line 527 of file SHAMap.h.

◆ setLedgerSeq()

void xrpl::SHAMap::setLedgerSeq ( std::uint32_t lseq )

Definition at line 533 of file SHAMap.h.

◆ fetchRoot()

bool xrpl::SHAMap::fetchRoot	(	SHAMapHash const &	hash,
		SHAMapSyncFilter const *	filter )

Definition at line 888 of file SHAMap.cpp.

◆ hasItem()

bool xrpl::SHAMap::hasItem ( uint256 const & id ) const

Does the tree have an item with the given ID?

Definition at line 672 of file SHAMap.cpp.

◆ delItem()

bool xrpl::SHAMap::delItem ( uint256 const & id )

Definition at line 678 of file SHAMap.cpp.

◆ addItem()

bool xrpl::SHAMap::addItem	(	SHAMapNodeType	type,
		boost::intrusive_ptr< SHAMapItem const >	item )

Definition at line 830 of file SHAMap.cpp.

◆ getHash()

SHAMapHash xrpl::SHAMap::getHash ( ) const

Definition at line 836 of file SHAMap.cpp.

◆ updateGiveItem()

bool xrpl::SHAMap::updateGiveItem	(	SHAMapNodeType	type,
		boost::intrusive_ptr< SHAMapItem const >	item )

Definition at line 848 of file SHAMap.cpp.

◆ addGiveItem()

bool xrpl::SHAMap::addGiveItem	(	SHAMapNodeType	type,
		boost::intrusive_ptr< SHAMapItem const >	item )

Definition at line 761 of file SHAMap.cpp.

◆ peekItem() [1/2]

boost::intrusive_ptr< SHAMapItem const > const & xrpl::SHAMap::peekItem ( uint256 const & id ) const

Definition at line 581 of file SHAMap.cpp.

◆ peekItem() [2/2]

boost::intrusive_ptr< SHAMapItem const > const & xrpl::SHAMap::peekItem	(	uint256 const &	id,
		SHAMapHash &	hash ) const

Definition at line 592 of file SHAMap.cpp.

◆ upperBound()

SHAMap::ConstIterator xrpl::SHAMap::upperBound ( uint256 const & id ) const

Find the first item after the given item.

Parameters

id	the identifier of the item.

Note: The item does not need to exist.

Definition at line 604 of file SHAMap.cpp.

◆ lowerBound()

SHAMap::ConstIterator xrpl::SHAMap::lowerBound ( uint256 const & id ) const

Find the object with the greatest object id smaller than the input id.

Parameters

id	the identifier of the item.

Note: The item does not need to exist.

Definition at line 637 of file SHAMap.cpp.

◆ visitNodes()

void xrpl::SHAMap::visitNodes ( std::function< bool(SHAMapTreeNode &)> const & function ) const

Visit every node in this SHAMap.

Parameters

function called with every node visited. If function returns false, visitNodes exits.

Definition at line 47 of file SHAMapSync.cpp.

◆ visitDifferences()

void xrpl::SHAMap::visitDifferences	(	SHAMap const *	have,
		std::function< bool(SHAMapTreeNode const &)> const &	function ) const

Visit every node in this SHAMap that is not present in the specified SHAMap.

Parameters

function called with every node visited. If function returns false, visitDifferences exits.

Definition at line 109 of file SHAMapSync.cpp.

◆ visitLeaves()

void xrpl::SHAMap::visitLeaves ( std::function< void(boost::intrusive_ptr< SHAMapItem const > const &)> const & ) const

Visit every leaf node in this SHAMap.

Parameters

function called with every non inner node visited.

Definition at line 35 of file SHAMapSync.cpp.

◆ getMissingNodes()

std::vector< std::pair< SHAMapNodeID, uint256 > > xrpl::SHAMap::getMissingNodes	(	int	max,
		SHAMapSyncFilter const *	filter )

Check for nodes in the SHAMap not available.

Get a list of node IDs and hashes for nodes that are part of this SHAMap but not available locally.

Traverse the SHAMap efficiently, maximizing I/O concurrency, to discover nodes referenced in the SHAMap but not available locally.

Parameters

maxNodes	The maximum number of found nodes to return
filter	The filter to use when retrieving nodes
return	The nodes known to be missing

The filter can hold alternate sources of nodes that are not permanently stored locally

Definition at line 308 of file SHAMapSync.cpp.

◆ getNodeFat()

bool xrpl::SHAMap::getNodeFat	(	SHAMapNodeID const &	wanted,
		std::vector< std::pair< SHAMapNodeID, Blob > > &	data,
		bool	fatLeaves,
		std::uint32_t	depth ) const

Definition at line 414 of file SHAMapSync.cpp.

◆ getProofPath()

std::optional< std::vector< Blob > > xrpl::SHAMap::getProofPath ( uint256 const & key ) const

Get the proof path of the key.

The proof path is every node on the path from leaf to root. Sibling hashes are stored in the parent nodes.

Parameters

key	key of the leaf

Returns: the proof path if found

Definition at line 775 of file SHAMapSync.cpp.

◆ verifyProofPath()

bool xrpl::SHAMap::verifyProofPath	(	uint256 const &	rootHash,
		uint256 const &	key,
		std::vector< Blob > const &	path )

static

Verify the proof path.

Parameters

rootHash	root hash of the map
key	key of the leaf
path	the proof path

Returns: true if verified successfully

Definition at line 808 of file SHAMapSync.cpp.

◆ serializeRoot()

void xrpl::SHAMap::serializeRoot ( Serializer & s ) const

Serializes the root in a format appropriate for sending over the wire.

Definition at line 504 of file SHAMapSync.cpp.

◆ addRootNode()

SHAMapAddNode xrpl::SHAMap::addRootNode	(	SHAMapHash const &	hash,
		Slice const &	rootNode,
		SHAMapSyncFilter const *	filter )

Definition at line 510 of file SHAMapSync.cpp.

◆ addKnownNode()

SHAMapAddNode xrpl::SHAMap::addKnownNode	(	SHAMapNodeID const &	nodeID,
		Slice const &	rawNode,
		SHAMapSyncFilter const *	filter )

Definition at line 545 of file SHAMapSync.cpp.

◆ setImmutable()

void xrpl::SHAMap::setImmutable ( )

Definition at line 539 of file SHAMap.h.

◆ isSynching()

bool xrpl::SHAMap::isSynching ( ) const

Definition at line 546 of file SHAMap.h.

◆ setSynching()

void xrpl::SHAMap::setSynching ( )

Definition at line 552 of file SHAMap.h.

◆ clearSynching()

void xrpl::SHAMap::clearSynching ( )

Definition at line 558 of file SHAMap.h.

◆ isValid()

bool xrpl::SHAMap::isValid ( ) const

Definition at line 564 of file SHAMap.h.

◆ compare()

bool xrpl::SHAMap::compare	(	SHAMap const &	otherMap,
		Delta &	differences,
		int	maxCount ) const

Definition at line 130 of file SHAMapDelta.cpp.

◆ unshare()

int xrpl::SHAMap::unshare ( )

Convert any modified nodes to shared.

Definition at line 968 of file SHAMap.cpp.

◆ flushDirty()

int xrpl::SHAMap::flushDirty ( NodeObjectType t )

Flush modified nodes to the nodestore and convert them to shared.

Definition at line 975 of file SHAMap.cpp.

◆ walkMap()

void xrpl::SHAMap::walkMap	(	std::vector< SHAMapMissingNode > &	missingNodes,
		int	maxMissing ) const

Definition at line 245 of file SHAMapDelta.cpp.

◆ walkMapParallel()

bool xrpl::SHAMap::walkMapParallel	(	std::vector< SHAMapMissingNode > &	missingNodes,
		int	maxMissing ) const

Definition at line 283 of file SHAMapDelta.cpp.

◆ deepCompare()

bool xrpl::SHAMap::deepCompare ( SHAMap & other ) const

Definition at line 655 of file SHAMapSync.cpp.

◆ setUnbacked()

void xrpl::SHAMap::setUnbacked ( )

Definition at line 570 of file SHAMap.h.

◆ dump()

void xrpl::SHAMap::dump ( bool withHashes = false ) const

Definition at line 1105 of file SHAMap.cpp.

◆ invariants()

void xrpl::SHAMap::invariants ( ) const

Definition at line 1170 of file SHAMap.cpp.

◆ cacheLookup()

SHAMapTreeNodePtr xrpl::SHAMap::cacheLookup ( SHAMapHash const & hash ) const

private

Definition at line 1152 of file SHAMap.cpp.

◆ canonicalize()

void xrpl::SHAMap::canonicalize	(	SHAMapHash const &	hash,
		SHAMapTreeNodePtr &	node ) const

private

Definition at line 1160 of file SHAMap.cpp.

◆ fetchNodeFromDB()

SHAMapTreeNodePtr xrpl::SHAMap::fetchNodeFromDB ( SHAMapHash const & hash ) const

private

Definition at line 166 of file SHAMap.cpp.

◆ fetchNodeNT() [1/2]

SHAMapTreeNodePtr xrpl::SHAMap::fetchNodeNT ( SHAMapHash const & hash ) const

private

Definition at line 258 of file SHAMap.cpp.

◆ fetchNodeNT() [2/2]

SHAMapTreeNodePtr xrpl::SHAMap::fetchNodeNT	(	SHAMapHash const &	hash,
		SHAMapSyncFilter const *	filter ) const

private

Definition at line 235 of file SHAMap.cpp.

◆ fetchNode()

SHAMapTreeNodePtr xrpl::SHAMap::fetchNode ( SHAMapHash const & hash ) const

private

Definition at line 270 of file SHAMap.cpp.

◆ checkFilter()

SHAMapTreeNodePtr xrpl::SHAMap::checkFilter	(	SHAMapHash const &	hash,
		SHAMapSyncFilter const *	filter ) const

private

Definition at line 209 of file SHAMap.cpp.

◆ dirtyUp()

void xrpl::SHAMap::dirtyUp	(	SharedPtrNodeStack &	stack,
		uint256 const &	target,
		SHAMapTreeNodePtr	terminal )

private

Update hashes up to the root.

Definition at line 100 of file SHAMap.cpp.

◆ walkTowardsKey()

SHAMapLeafNode * xrpl::SHAMap::walkTowardsKey	(	uint256 const &	id,
		SharedPtrNodeStack *	stack = nullptr ) const

private

Walk towards the specified id, returning the node.

Caller must check if the return is nullptr, and if not, if the node->peekItem()->key() == id

Definition at line 130 of file SHAMap.cpp.

◆ findKey()

SHAMapLeafNode * xrpl::SHAMap::findKey ( uint256 const & id ) const

private

Return nullptr if key not found.

Definition at line 157 of file SHAMap.cpp.

◆ unshareNode()

template<class Node>

intr_ptr::SharedPtr< Node > xrpl::SHAMap::unshareNode	(	intr_ptr::SharedPtr< Node >	node,
		SHAMapNodeID const &	nodeID )

private

Unshare the node, allowing it to be modified.

Definition at line 417 of file SHAMap.cpp.

◆ preFlushNode()

template<class Node>

intr_ptr::SharedPtr< Node > xrpl::SHAMap::preFlushNode ( intr_ptr::SharedPtr< Node > node ) const

private

prepare a node to be modified before flushing

Definition at line 952 of file SHAMap.cpp.

◆ writeNode()

SHAMapTreeNodePtr xrpl::SHAMap::writeNode	(	NodeObjectType	t,
		SHAMapTreeNodePtr	node ) const

private

write and canonicalize modified node

Replace a node with a shareable node.

This code handles two cases:

1) An unshared, unshareable node needs to be made shareable so immutable SHAMap's can have references to it. 2) An unshareable node is shared. This happens when you make a mutable snapshot of a mutable SHAMap.

Note: The node must have already been unshared by having the caller first call SHAMapTreeNode::unshare().

Definition at line 934 of file SHAMap.cpp.

◆ firstBelow()

SHAMapLeafNode * xrpl::SHAMap::firstBelow	(	SHAMapTreeNodePtr	node,
		SharedPtrNodeStack &	stack,
		int	branch = 0 ) const

private

Definition at line 488 of file SHAMap.cpp.

◆ lastBelow()

SHAMapLeafNode * xrpl::SHAMap::lastBelow	(	SHAMapTreeNodePtr	node,
		SharedPtrNodeStack &	stack,
		int	branch = kBranchFactor ) const

private

Definition at line 479 of file SHAMap.cpp.

◆ belowHelper()

SHAMapLeafNode * xrpl::SHAMap::belowHelper	(	SHAMapTreeNodePtr	node,
		SharedPtrNodeStack &	stack,
		int	branch,
		std::tuple< int, std::function< bool(int)>, std::function< void(int &)> > const &	loopParams ) const

private

Definition at line 433 of file SHAMap.cpp.

◆ descend() [1/3]

SHAMapTreeNode * xrpl::SHAMap::descend	(	SHAMapInnerNode *	parent,
		int	branch ) const

private

Definition at line 303 of file SHAMap.cpp.

◆ descendThrow() [1/2]

SHAMapTreeNode * xrpl::SHAMap::descendThrow	(	SHAMapInnerNode *	parent,
		int	branch ) const

private

Definition at line 281 of file SHAMap.cpp.

◆ descend() [2/3]

SHAMapTreeNodePtr xrpl::SHAMap::descend	(	SHAMapInnerNode &	parent,
		int	branch ) const

private

Definition at line 318 of file SHAMap.cpp.

◆ descendThrow() [2/2]

SHAMapTreeNodePtr xrpl::SHAMap::descendThrow	(	SHAMapInnerNode &	parent,
		int	branch ) const

private

Definition at line 292 of file SHAMap.cpp.

◆ descendAsync()

SHAMapTreeNode * xrpl::SHAMap::descendAsync	(	SHAMapInnerNode *	parent,
		int	branch,
		SHAMapSyncFilter const *	filter,
		bool &	pending,
		descendCallback &&	callback ) const

private

Definition at line 374 of file SHAMap.cpp.

◆ descend() [3/3]

std::pair< SHAMapTreeNode *, SHAMapNodeID > xrpl::SHAMap::descend	(	SHAMapInnerNode *	parent,
		SHAMapNodeID const &	parentID,
		int	branch,
		SHAMapSyncFilter const *	filter ) const

private

Definition at line 344 of file SHAMap.cpp.

◆ descendNoStore()

SHAMapTreeNodePtr xrpl::SHAMap::descendNoStore	(	SHAMapInnerNode &	parent,
		int	branch ) const

private

Definition at line 335 of file SHAMap.cpp.

◆ onlyBelow()

boost::intrusive_ptr< SHAMapItem const > const & xrpl::SHAMap::onlyBelow ( SHAMapTreeNode * node ) const

private

If there is only one leaf below this node, get its contents.

Definition at line 499 of file SHAMap.cpp.

◆ hasInnerNode()

bool xrpl::SHAMap::hasInnerNode	(	SHAMapNodeID const &	nodeID,
		SHAMapHash const &	hash ) const

private

Does this map have this inner node?

Definition at line 726 of file SHAMapSync.cpp.

◆ hasLeafNode()

bool xrpl::SHAMap::hasLeafNode	(	uint256 const &	tag,
		SHAMapHash const &	hash ) const

private

Does this map have this leaf node?

Definition at line 748 of file SHAMapSync.cpp.

◆ peekFirstItem()

SHAMapLeafNode const * xrpl::SHAMap::peekFirstItem ( SharedPtrNodeStack & stack ) const

private

Definition at line 538 of file SHAMap.cpp.

◆ peekNextItem()

SHAMapLeafNode const * xrpl::SHAMap::peekNextItem	(	uint256 const &	id,
		SharedPtrNodeStack &	stack ) const

private

Definition at line 552 of file SHAMap.cpp.

◆ walkBranch()

bool xrpl::SHAMap::walkBranch	(	SHAMapTreeNode *	node,
		boost::intrusive_ptr< SHAMapItem const > const &	otherMapItem,
		bool	isFirstMap,
		Delta &	differences,
		int &	maxCount ) const

private

Definition at line 34 of file SHAMapDelta.cpp.

◆ walkSubTree()

int xrpl::SHAMap::walkSubTree	(	bool	doWrite,
		NodeObjectType	t )

private

Definition at line 982 of file SHAMap.cpp.

◆ gmnProcessNodes()

void xrpl::SHAMap::gmnProcessNodes	(	MissingNodes &	mn,
		MissingNodes::StackEntry &	node )

private

Definition at line 178 of file SHAMapSync.cpp.

◆ gmnProcessDeferredReads()

void xrpl::SHAMap::gmnProcessDeferredReads ( MissingNodes & mn )

staticprivate

Definition at line 262 of file SHAMapSync.cpp.

◆ finishFetch()

SHAMapTreeNodePtr xrpl::SHAMap::finishFetch	(	SHAMapHash const &	hash,
		std::shared_ptr< NodeObject > const &	object ) const

private

Definition at line 174 of file SHAMap.cpp.

Member Data Documentation

◆ f_

Family& xrpl::SHAMap::f_

private

Definition at line 79 of file SHAMap.h.

◆ journal_

beast::Journal xrpl::SHAMap::journal_

private

Definition at line 80 of file SHAMap.h.

◆ cowid_

std::uint32_t xrpl::SHAMap::cowid_ = 1

private

ID to distinguish this map for all others we're sharing nodes with.

Definition at line 83 of file SHAMap.h.

◆ ledgerSeq_

std::uint32_t xrpl::SHAMap::ledgerSeq_ = 0

private

The sequence of the ledger that this map references, if any.

Definition at line 86 of file SHAMap.h.

◆ root_

SHAMapTreeNodePtr xrpl::SHAMap::root_

private

Definition at line 88 of file SHAMap.h.

◆ state_

SHAMapState xrpl::SHAMap::state_

mutableprivate

Definition at line 89 of file SHAMap.h.

◆ type_

SHAMapType const xrpl::SHAMap::type_

private

Definition at line 90 of file SHAMap.h.

◆ backed_

bool xrpl::SHAMap::backed_ = true

private

Definition at line 91 of file SHAMap.h.

◆ full_

bool xrpl::SHAMap::full_ = false

mutableprivate

Definition at line 92 of file SHAMap.h.

◆ kBranchFactor

unsigned int xrpl::SHAMap::kBranchFactor = SHAMapInnerNode::kBranchFactor

staticconstexpr

Number of children each non-leaf node has (the 'radix tree' part of the map).

Definition at line 97 of file SHAMap.h.

◆ kLeafDepth

unsigned int xrpl::SHAMap::kLeafDepth = 64

staticconstexpr

The depth of the hash map: data is only present in the leaves.

Definition at line 100 of file SHAMap.h.

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ DeltaItem

◆ Delta

◆ SharedPtrNodeStack

◆ DeltaRef

◆ descendCallback

Constructor & Destructor Documentation

◆ SHAMap() [1/5]

◆ SHAMap() [2/5]

◆ SHAMap() [3/5]

◆ SHAMap() [4/5]

◆ SHAMap() [5/5]

◆ ~SHAMap()

Member Function Documentation

◆ operator=()

◆ family() [1/2]

◆ family() [2/2]

◆ begin()

◆ end()

◆ snapShot()

◆ setFull()

◆ setLedgerSeq()

◆ fetchRoot()

◆ hasItem()

◆ delItem()

◆ addItem()

◆ getHash()

◆ updateGiveItem()

◆ addGiveItem()

◆ peekItem() [1/2]

◆ peekItem() [2/2]

◆ upperBound()

◆ lowerBound()

◆ visitNodes()

◆ visitDifferences()

◆ visitLeaves()

◆ getMissingNodes()

◆ getNodeFat()

◆ getProofPath()

◆ verifyProofPath()

◆ serializeRoot()

◆ addRootNode()

◆ addKnownNode()

◆ setImmutable()

◆ isSynching()

◆ setSynching()

◆ clearSynching()

◆ isValid()

◆ compare()

◆ unshare()

◆ flushDirty()

◆ walkMap()

◆ walkMapParallel()

◆ deepCompare()

◆ setUnbacked()

◆ dump()

◆ invariants()

◆ cacheLookup()

◆ canonicalize()

◆ fetchNodeFromDB()

◆ fetchNodeNT() [1/2]

◆ fetchNodeNT() [2/2]

◆ fetchNode()

◆ checkFilter()

◆ dirtyUp()

◆ walkTowardsKey()

◆ findKey()

◆ unshareNode()

◆ preFlushNode()

◆ writeNode()