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

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.

◆ SharedPtrNodeStack

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

private

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

◆ descendCallback

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

private

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

◆ end()

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

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

◆ setLedgerSeq()

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

Definition at line 641 of file SHAMap.h.

◆ fetchRoot()

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

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

◆ delItem()

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

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

◆ addItem()

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

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

◆ getHash()

SHAMapHash xrpl::SHAMap::getHash ( ) const

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

◆ updateGiveItem()

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

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

◆ addGiveItem()

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

Definition at line 761 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 581 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 592 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 604 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 637 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 306 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 412 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 771 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 804 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 502 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 508 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 551 of file libxrpl/shamap/SHAMapSync.cpp.

◆ setImmutable()

void xrpl::SHAMap::setImmutable ( )

Definition at line 647 of file SHAMap.h.

◆ isSynching()

bool xrpl::SHAMap::isSynching ( ) const

Definition at line 654 of file SHAMap.h.

◆ setSynching()

void xrpl::SHAMap::setSynching ( )

Definition at line 660 of file SHAMap.h.

◆ clearSynching()

void xrpl::SHAMap::clearSynching ( )

Definition at line 666 of file SHAMap.h.

◆ isValid()

bool xrpl::SHAMap::isValid ( ) const

Definition at line 672 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 970 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 977 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 649 of file libxrpl/shamap/SHAMapSync.cpp.

◆ setUnbacked()

void xrpl::SHAMap::setUnbacked ( )

Definition at line 678 of file SHAMap.h.

◆ dump()

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

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

◆ invariants()

void xrpl::SHAMap::invariants ( ) const

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

◆ cacheLookup()

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

private

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

◆ canonicalize()

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

private

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

◆ fetchNodeFromDB()

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

private

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

◆ fetchNodeNT() [1/2]

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

private

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

◆ fetchNodeNT() [2/2]

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

private

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

◆ fetchNode()

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

private

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

◆ checkFilter()

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

private

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

◆ findKey()

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

private

Return nullptr if key not found.

Definition at line 157 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 417 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 954 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 936 of file libxrpl/shamap/SHAMap.cpp.

◆ firstBelow()

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

private

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

◆ lastBelow()

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

private

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

◆ descend() [1/3]

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

private

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

◆ descendThrow() [1/2]

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

private

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

◆ descend() [2/3]

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

private

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

◆ descendThrow() [2/2]

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

private

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

◆ descendNoStore()

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

private

Definition at line 335 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 499 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 721 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 744 of file libxrpl/shamap/SHAMapSync.cpp.

◆ peekFirstItem()

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

private

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

◆ peekNextItem()

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

private

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

◆ gmnProcessNodes()

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

private

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

◆ gmnProcessDeferredReads()

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

staticprivate

Definition at line 259 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 174 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

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