#include <SHAMap.h>

Collaboration diagram for xrpl::SHAMap:

[legend]

Classes
class	NodePathStack
	A path from the root of the map down to some node, pairing each node with the ID naming its position. More...
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< SHAMapNodeData > &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, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const *filter)
	Add a root node to the SHAMap during synchronization.
SHAMapAddNode	addKnownNode (SHAMapNodeID const &nodeID, SHAMapTreeNodePtr treeNode, SHAMapSyncFilter const *filter)
	Add a known node at a specific position in the SHAMap during synchronization.
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
enum class	BelowDirection { First , Last }
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 (NodePathStack &stack, UInt256 const &target, SHAMapTreeNodePtr terminal)
	Update hashes up to the root.
SHAMapLeafNode *	walkTowardsKey (UInt256 const &id, NodePathStack *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 *	belowHelper (NodePathStack &stack, BelowDirection direction) const
	Returns the first or last item at or below the node already on top of stack, extending stack with the path walked to reach it.
ConstIterator	boundHelper (UInt256 const &id, BelowDirection direction) const
	Returns the nearest item strictly past id, in the given direction.
SHAMapTreeNode *	descend (SHAMapInnerNode *, unsigned int branch) const
SHAMapTreeNode *	descendThrow (SHAMapInnerNode *, unsigned int branch) const
SHAMapTreeNodePtr	descend (SHAMapInnerNode &, unsigned int branch) const
SHAMapTreeNodePtr	descendThrow (SHAMapInnerNode &, unsigned int branch) const
SHAMapTreeNode *	descendAsync (SHAMapInnerNode parent, unsigned int branch, SHAMapSyncFilter const filter, bool &pending, DescendCallback &&) const
std::pair< SHAMapTreeNode *, SHAMapNodeID >	descend (SHAMapInnerNode parent, SHAMapNodeID const &parentID, unsigned int branch, SHAMapSyncFilter const filter) const
SHAMapTreeNodePtr	descendNoStore (SHAMapInnerNode &, unsigned 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 (NodePathStack &stack) const
SHAMapLeafNode const *	peekNextItem (UInt256 const &id, NodePathStack &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

Definition at line 112 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 146 of file SHAMap.h.

◆ Delta

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

Definition at line 148 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 524 of file SHAMap.h.

◆ DescendCallback

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

private

Definition at line 622 of file SHAMap.h.

Member Enumeration Documentation

◆ BelowDirection

enum class xrpl::SHAMap::BelowDirection

strongprivate

Enumerator
First
Last

Definition at line 586 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 libxrpl/shamap/SHAMap.cpp.

◆ SHAMap() [4/5]

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

Definition at line 60 of file libxrpl/shamap/SHAMap.cpp.

◆ SHAMap() [5/5]

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

Definition at line 70 of file libxrpl/shamap/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 166 of file SHAMap.h.

◆ family() [2/2]

Family & xrpl::SHAMap::family ( )

Definition at line 172 of file SHAMap.h.

◆ begin()

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

Definition at line 897 of file SHAMap.h.

◆ end()

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

Definition at line 903 of file SHAMap.h.

◆ snapShot()

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

Definition at line 94 of file libxrpl/shamap/SHAMap.cpp.

◆ setFull()

void xrpl::SHAMap::setFull ( )

Definition at line 742 of file SHAMap.h.

◆ setLedgerSeq()

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

Definition at line 748 of file SHAMap.h.

◆ fetchRoot()

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

Definition at line 848 of file libxrpl/shamap/SHAMap.cpp.

◆ hasItem()

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

Does the tree have an item with the given ID?

Definition at line 631 of file libxrpl/shamap/SHAMap.cpp.

◆ delItem()

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

Definition at line 637 of file libxrpl/shamap/SHAMap.cpp.

◆ addItem()

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

Definition at line 789 of file libxrpl/shamap/SHAMap.cpp.

◆ getHash()

SHAMapHash xrpl::SHAMap::getHash ( ) const

Definition at line 795 of file libxrpl/shamap/SHAMap.cpp.

◆ updateGiveItem()

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

Definition at line 808 of file libxrpl/shamap/SHAMap.cpp.

◆ addGiveItem()

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

Definition at line 720 of file libxrpl/shamap/SHAMap.cpp.

◆ peekItem() [1/2]

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

Definition at line 555 of file libxrpl/shamap/SHAMap.cpp.

◆ peekItem() [2/2]

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

Definition at line 566 of file libxrpl/shamap/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 619 of file libxrpl/shamap/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 625 of file libxrpl/shamap/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 libxrpl/shamap/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 libxrpl/shamap/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 libxrpl/shamap/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 320 of file libxrpl/shamap/SHAMapSync.cpp.

◆ getNodeFat()

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

nodiscard

Definition at line 426 of file libxrpl/shamap/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 794 of file libxrpl/shamap/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 827 of file libxrpl/shamap/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 516 of file libxrpl/shamap/SHAMapSync.cpp.

◆ addRootNode()

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

Add a root node to the SHAMap during synchronization.

This function is used when receiving the root node of a SHAMap from a peer during ledger synchronization. The node must already have been deserialized.

Parameters

hash	The expected hash of the root node.
rootNode	A deserialized root node to add.
filter	Optional sync filter to track received nodes.

Returns: Status indicating whether the node was useful, duplicate, or invalid.

Note: This function expects the rootNode to be a valid, deserialized SHAMapTreeNode. The caller is responsible for deserialization and basic validation before calling this function.

Definition at line 522 of file libxrpl/shamap/SHAMapSync.cpp.

◆ addKnownNode()

SHAMapAddNode xrpl::SHAMap::addKnownNode	(	SHAMapNodeID const &	nodeID,
		SHAMapTreeNodePtr	treeNode,
		SHAMapSyncFilter const *	filter )

Add a known node at a specific position in the SHAMap during synchronization.

This function is used when receiving nodes from peers during ledger synchronization. The node is inserted at the position specified by nodeID. The node must already have been deserialized.

Parameters

nodeID	The position in the tree where this node belongs.
treeNode	A deserialized tree node to add.
filter	Optional sync filter to track received nodes.

Returns: Status indicating whether the node was useful, duplicate, or invalid.

Note: This function expects the treeNode to be a valid, deserialized SHAMapTreeNode. The caller is responsible for deserialization and basic validation before calling this function. This also means that the nodeID must be consistent with the node's content.

Definition at line 565 of file libxrpl/shamap/SHAMapSync.cpp.

◆ setImmutable()

void xrpl::SHAMap::setImmutable ( )

Definition at line 754 of file SHAMap.h.

◆ isSynching()

bool xrpl::SHAMap::isSynching ( ) const

Definition at line 761 of file SHAMap.h.

◆ setSynching()

void xrpl::SHAMap::setSynching ( )

Definition at line 767 of file SHAMap.h.

◆ clearSynching()

void xrpl::SHAMap::clearSynching ( )

Definition at line 773 of file SHAMap.h.

◆ isValid()

bool xrpl::SHAMap::isValid ( ) const

Definition at line 779 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 929 of file libxrpl/shamap/SHAMap.cpp.

◆ flushDirty()

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

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

Definition at line 936 of file libxrpl/shamap/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 661 of file libxrpl/shamap/SHAMapSync.cpp.

◆ setUnbacked()

void xrpl::SHAMap::setUnbacked ( )

Definition at line 785 of file SHAMap.h.

◆ dump()

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

Definition at line 1066 of file libxrpl/shamap/SHAMap.cpp.

◆ invariants()

void xrpl::SHAMap::invariants ( ) const

Definition at line 1131 of file libxrpl/shamap/SHAMap.cpp.

◆ cacheLookup()

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

private

Definition at line 1113 of file libxrpl/shamap/SHAMap.cpp.

◆ canonicalize()

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

private

Definition at line 1121 of file libxrpl/shamap/SHAMap.cpp.

◆ fetchNodeFromDB()

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

private

Definition at line 170 of file libxrpl/shamap/SHAMap.cpp.

◆ fetchNodeNT() [1/2]

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

private

Definition at line 262 of file libxrpl/shamap/SHAMap.cpp.

◆ fetchNodeNT() [2/2]

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

private

Definition at line 239 of file libxrpl/shamap/SHAMap.cpp.

◆ fetchNode()

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

private

Definition at line 274 of file libxrpl/shamap/SHAMap.cpp.

◆ checkFilter()

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

private

Definition at line 213 of file libxrpl/shamap/SHAMap.cpp.

◆ dirtyUp()

void xrpl::SHAMap::dirtyUp	(	NodePathStack &	stack,
		UInt256 const &	target,
		SHAMapTreeNodePtr	terminal )

private

Update hashes up to the root.

Definition at line 100 of file libxrpl/shamap/SHAMap.cpp.

◆ walkTowardsKey()

SHAMapLeafNode * xrpl::SHAMap::walkTowardsKey	(	UInt256 const &	id,
		NodePathStack *	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 129 of file libxrpl/shamap/SHAMap.cpp.

◆ findKey()

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

private

Return nullptr if key not found.

Definition at line 161 of file libxrpl/shamap/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 420 of file libxrpl/shamap/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 913 of file libxrpl/shamap/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 895 of file libxrpl/shamap/SHAMap.cpp.

◆ belowHelper()

SHAMapLeafNode * xrpl::SHAMap::belowHelper	(	NodePathStack &	stack,
		BelowDirection	direction ) const

private

Returns the first or last item at or below the node already on top of stack, extending stack with the path walked to reach it.

Definition at line 436 of file libxrpl/shamap/SHAMap.cpp.

◆ boundHelper()

SHAMap::ConstIterator xrpl::SHAMap::boundHelper	(	UInt256 const &	id,
		BelowDirection	direction ) const

private

Returns the nearest item strictly past id, in the given direction.

Walks back up the path to id. At each inner node the branches beyond the one id takes hold the candidates, so the first non-empty one is the closest and the extreme leaf below it is the answer.

Parameters

id	The key to search from, which need not be in the map.
direction	First to search upwards from id, Last to search downwards.

Returns: An iterator to the item found, or end() if no item lies on that side of id.

Definition at line 578 of file libxrpl/shamap/SHAMap.cpp.

◆ descend() [1/3]

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

private

Definition at line 307 of file libxrpl/shamap/SHAMap.cpp.

◆ descendThrow() [1/2]

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

private

Definition at line 285 of file libxrpl/shamap/SHAMap.cpp.

◆ descend() [2/3]

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

private

Definition at line 322 of file libxrpl/shamap/SHAMap.cpp.

◆ descendThrow() [2/2]

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

private

Definition at line 296 of file libxrpl/shamap/SHAMap.cpp.

◆ descendAsync()

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

private

Definition at line 377 of file libxrpl/shamap/SHAMap.cpp.

◆ descend() [3/3]

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

private

Definition at line 348 of file libxrpl/shamap/SHAMap.cpp.

◆ descendNoStore()

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

private

Definition at line 339 of file libxrpl/shamap/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 473 of file libxrpl/shamap/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 733 of file libxrpl/shamap/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 756 of file libxrpl/shamap/SHAMapSync.cpp.

◆ peekFirstItem()

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

private

Definition at line 512 of file libxrpl/shamap/SHAMap.cpp.

◆ peekNextItem()

SHAMapLeafNode const * xrpl::SHAMap::peekNextItem	(	UInt256 const &	id,
		NodePathStack &	stack ) const

private

Definition at line 526 of file libxrpl/shamap/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 943 of file libxrpl/shamap/SHAMap.cpp.

◆ gmnProcessNodes()

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

private

Definition at line 189 of file libxrpl/shamap/SHAMapSync.cpp.

◆ gmnProcessDeferredReads()

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

staticprivate

Definition at line 273 of file libxrpl/shamap/SHAMapSync.cpp.

◆ finishFetch()

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

private

Definition at line 178 of file libxrpl/shamap/SHAMap.cpp.

Member Data Documentation

◆ f_

Family& xrpl::SHAMap::f_

private

Definition at line 115 of file SHAMap.h.

◆ journal_

beast::Journal xrpl::SHAMap::journal_

private

Definition at line 116 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 121 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 126 of file SHAMap.h.

◆ root_

SHAMapTreeNodePtr xrpl::SHAMap::root_

private

Definition at line 128 of file SHAMap.h.

◆ state_

SHAMapState xrpl::SHAMap::state_

mutableprivate

Definition at line 129 of file SHAMap.h.

◆ type_

SHAMapType const xrpl::SHAMap::type_

private

Definition at line 130 of file SHAMap.h.

◆ backed_

bool xrpl::SHAMap::backed_ = true

private

Definition at line 131 of file SHAMap.h.

◆ full_

bool xrpl::SHAMap::full_ = false

mutableprivate

Definition at line 132 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 139 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 144 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

◆ DeltaRef

◆ DescendCallback

Member Enumeration Documentation

◆ BelowDirection

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()