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
class	const_iterator

struct	MissingNodes

Public Types
using	DeltaItem = std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > >

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

const_iterator	begin () const

const_iterator	end () const

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

void	setFull ()

void	setLedgerSeq (std::uint32_t lseq)

bool	fetchRoot (SHAMapHash const &hash, SHAMapSyncFilter *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

const_iterator	upper_bound (uint256 const &id) const
	Find the first item after the given item.

const_iterator	lower_bound (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 *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 *filter)

SHAMapAddNode	addKnownNode (SHAMapNodeID const &nodeID, Slice const &rawNode, SHAMapSyncFilter *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	branchFactor = SHAMapInnerNode::branchFactor
	Number of children each non-leaf node has (the 'radix tree' part of the map)

static constexpr unsigned int	leafDepth = 64
	The depth of the hash map: data is only present in the leaves.

Private Types
using	SharedPtrNodeStack = std::stack< std::pair< intr_ptr::SharedPtr< SHAMapTreeNode >, SHAMapNodeID > >

using	DeltaRef = std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > >

using	descendCallback = std::function< void(intr_ptr::SharedPtr< SHAMapTreeNode >, SHAMapHash const &)>

Private Member Functions
intr_ptr::SharedPtr< SHAMapTreeNode >	cacheLookup (SHAMapHash const &hash) const

void	canonicalize (SHAMapHash const &hash, intr_ptr::SharedPtr< SHAMapTreeNode > &) const

intr_ptr::SharedPtr< SHAMapTreeNode >	fetchNodeFromDB (SHAMapHash const &hash) const

intr_ptr::SharedPtr< SHAMapTreeNode >	fetchNodeNT (SHAMapHash const &hash) const

intr_ptr::SharedPtr< SHAMapTreeNode >	fetchNodeNT (SHAMapHash const &hash, SHAMapSyncFilter *filter) const

intr_ptr::SharedPtr< SHAMapTreeNode >	fetchNode (SHAMapHash const &hash) const

intr_ptr::SharedPtr< SHAMapTreeNode >	checkFilter (SHAMapHash const &hash, SHAMapSyncFilter *filter) const

void	dirtyUp (SharedPtrNodeStack &stack, uint256 const &target, intr_ptr::SharedPtr< SHAMapTreeNode > 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

intr_ptr::SharedPtr< SHAMapTreeNode >	writeNode (NodeObjectType t, intr_ptr::SharedPtr< SHAMapTreeNode > node) const
	write and canonicalize modified node

SHAMapLeafNode *	firstBelow (intr_ptr::SharedPtr< SHAMapTreeNode >, SharedPtrNodeStack &stack, int branch=0) const

SHAMapLeafNode *	lastBelow (intr_ptr::SharedPtr< SHAMapTreeNode > node, SharedPtrNodeStack &stack, int branch=branchFactor) const

SHAMapLeafNode *	belowHelper (intr_ptr::SharedPtr< SHAMapTreeNode > 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

intr_ptr::SharedPtr< SHAMapTreeNode >	descend (SHAMapInnerNode &, int branch) const

intr_ptr::SharedPtr< SHAMapTreeNode >	descendThrow (SHAMapInnerNode &, int branch) const

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

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

intr_ptr::SharedPtr< SHAMapTreeNode >	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	gmn_ProcessNodes (MissingNodes &, MissingNodes::StackEntry &node)

void	gmn_ProcessDeferredReads (MissingNodes &)

intr_ptr::SharedPtr< SHAMapTreeNode >	finishFetch (SHAMapHash const &hash, std::shared_ptr< NodeObject > const &object) const

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.

intr_ptr::SharedPtr< SHAMapTreeNode >	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 = std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const> >

Definition at line 102 of file SHAMap.h.

◆ Delta

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

Definition at line 103 of file SHAMap.h.

◆ SharedPtrNodeStack

using xrpl::SHAMap::SharedPtrNodeStack = std::stack<std::pair<intr_ptr::SharedPtr<SHAMapTreeNode>, SHAMapNodeID> >

private

Definition at line 328 of file SHAMap.h.

◆ DeltaRef

using xrpl::SHAMap::DeltaRef = std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const> >

private

Definition at line 329 of file SHAMap.h.

◆ descendCallback

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

private

Definition at line 406 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 44 of file SHAMap.cpp.

◆ SHAMap() [4/5]

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

Definition at line 29 of file SHAMap.cpp.

◆ SHAMap() [5/5]

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

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

◆ family() [2/2]

Family & xrpl::SHAMap::family ( )

Definition at line 127 of file SHAMap.h.

◆ begin()

SHAMap::const_iterator xrpl::SHAMap::begin ( ) const

Definition at line 668 of file SHAMap.h.

◆ end()

SHAMap::const_iterator xrpl::SHAMap::end ( ) const

Definition at line 674 of file SHAMap.h.

◆ snapShot()

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

Definition at line 62 of file SHAMap.cpp.

◆ setFull()

void xrpl::SHAMap::setFull ( )

Definition at line 511 of file SHAMap.h.

◆ setLedgerSeq()

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

Definition at line 517 of file SHAMap.h.

◆ fetchRoot()

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

Definition at line 833 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 625 of file SHAMap.cpp.

◆ delItem()

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

Definition at line 631 of file SHAMap.cpp.

◆ addItem()

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

Definition at line 775 of file SHAMap.cpp.

◆ getHash()

SHAMapHash xrpl::SHAMap::getHash ( ) const

Definition at line 781 of file SHAMap.cpp.

◆ updateGiveItem()

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

Definition at line 793 of file SHAMap.cpp.

◆ addGiveItem()

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

Definition at line 708 of file SHAMap.cpp.

◆ peekItem() [1/2]

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

Definition at line 534 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 545 of file SHAMap.cpp.

◆ upper_bound()

SHAMap::const_iterator xrpl::SHAMap::upper_bound ( 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 557 of file SHAMap.cpp.

◆ lower_bound()

SHAMap::const_iterator xrpl::SHAMap::lower_bound ( 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 590 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 19 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 79 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 9 of file SHAMapSync.cpp.

◆ getMissingNodes()

std::vector< std::pair< SHAMapNodeID, uint256 > > xrpl::SHAMap::getMissingNodes	(	int	max,
		SHAMapSyncFilter *	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 273 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 375 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 728 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 761 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 464 of file SHAMapSync.cpp.

◆ addRootNode()

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

Definition at line 470 of file SHAMapSync.cpp.

◆ addKnownNode()

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

Definition at line 504 of file SHAMapSync.cpp.

◆ setImmutable()

void xrpl::SHAMap::setImmutable ( )

Definition at line 523 of file SHAMap.h.

◆ isSynching()

bool xrpl::SHAMap::isSynching ( ) const

Definition at line 530 of file SHAMap.h.

◆ setSynching()

void xrpl::SHAMap::setSynching ( )

Definition at line 536 of file SHAMap.h.

◆ clearSynching()

void xrpl::SHAMap::clearSynching ( )

Definition at line 542 of file SHAMap.h.

◆ isValid()

bool xrpl::SHAMap::isValid ( ) const

Definition at line 548 of file SHAMap.h.

◆ compare()

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

Definition at line 100 of file SHAMapDelta.cpp.

◆ unshare()

int xrpl::SHAMap::unshare ( )

Convert any modified nodes to shared.

Definition at line 913 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 920 of file SHAMap.cpp.

◆ walkMap()

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

Definition at line 206 of file SHAMapDelta.cpp.

◆ walkMapParallel()

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

Definition at line 244 of file SHAMapDelta.cpp.

◆ deepCompare()

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

Definition at line 608 of file SHAMapSync.cpp.

◆ setUnbacked()

void xrpl::SHAMap::setUnbacked ( )

Definition at line 554 of file SHAMap.h.

◆ dump()

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

Definition at line 1053 of file SHAMap.cpp.

◆ invariants()

void xrpl::SHAMap::invariants ( ) const

Definition at line 1115 of file SHAMap.cpp.

◆ cacheLookup()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::cacheLookup ( SHAMapHash const & hash ) const

private

Definition at line 1097 of file SHAMap.cpp.

◆ canonicalize()

void xrpl::SHAMap::canonicalize	(	SHAMapHash const &	hash,
		intr_ptr::SharedPtr< SHAMapTreeNode > &	node
	)		const

private

Definition at line 1105 of file SHAMap.cpp.

◆ fetchNodeFromDB()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::fetchNodeFromDB ( SHAMapHash const & hash ) const

private

Definition at line 132 of file SHAMap.cpp.

◆ fetchNodeNT() [1/2]

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::fetchNodeNT ( SHAMapHash const & hash ) const

private

Definition at line 224 of file SHAMap.cpp.

◆ fetchNodeNT() [2/2]

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::fetchNodeNT	(	SHAMapHash const &	hash,
		SHAMapSyncFilter *	filter
	)		const

private

Definition at line 201 of file SHAMap.cpp.

◆ fetchNode()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::fetchNode ( SHAMapHash const & hash ) const

private

Definition at line 236 of file SHAMap.cpp.

◆ checkFilter()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::checkFilter	(	SHAMapHash const &	hash,
		SHAMapSyncFilter *	filter
	)		const

private

Definition at line 175 of file SHAMap.cpp.

◆ dirtyUp()

void xrpl::SHAMap::dirtyUp	(	SharedPtrNodeStack &	stack,
		uint256 const &	target,
		intr_ptr::SharedPtr< SHAMapTreeNode >	terminal
	)

private

Update hashes up to the root.

Definition at line 68 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 97 of file SHAMap.cpp.

◆ findKey()

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

private

Return nullptr if key not found.

Definition at line 123 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 377 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 897 of file SHAMap.cpp.

◆ writeNode()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::writeNode	(	NodeObjectType	t,
		intr_ptr::SharedPtr< SHAMapTreeNode >	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 879 of file SHAMap.cpp.

◆ firstBelow()

SHAMapLeafNode * xrpl::SHAMap::firstBelow	(	intr_ptr::SharedPtr< SHAMapTreeNode >	node,
		SharedPtrNodeStack &	stack,
		int	branch = `0`
	)		const

private

Definition at line 442 of file SHAMap.cpp.

◆ lastBelow()

SHAMapLeafNode * xrpl::SHAMap::lastBelow	(	intr_ptr::SharedPtr< SHAMapTreeNode >	node,
		SharedPtrNodeStack &	stack,
		int	branch = `branchFactor`
	)		const

private

Definition at line 433 of file SHAMap.cpp.

◆ belowHelper()

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

private

Definition at line 393 of file SHAMap.cpp.

◆ descend() [1/3]

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

private

Definition at line 269 of file SHAMap.cpp.

◆ descendThrow() [1/2]

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

private

Definition at line 247 of file SHAMap.cpp.

◆ descend() [2/3]

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::descend	(	SHAMapInnerNode &	parent,
		int	branch
	)		const

private

Definition at line 284 of file SHAMap.cpp.

◆ descendThrow() [2/2]

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::descendThrow	(	SHAMapInnerNode &	parent,
		int	branch
	)		const

private

Definition at line 258 of file SHAMap.cpp.

◆ descendAsync()

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

private

Definition at line 334 of file SHAMap.cpp.

◆ descend() [3/3]

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

private

Definition at line 310 of file SHAMap.cpp.

◆ descendNoStore()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMap::descendNoStore	(	SHAMapInnerNode &	parent,
		int	branch
	)		const

private

Definition at line 301 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 453 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 679 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 701 of file SHAMapSync.cpp.

◆ peekFirstItem()

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

private

Definition at line 491 of file SHAMap.cpp.

◆ peekNextItem()

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

private

Definition at line 505 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 20 of file SHAMapDelta.cpp.

◆ walkSubTree()

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

private

Definition at line 927 of file SHAMap.cpp.

◆ gmn_ProcessNodes()

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

private

Definition at line 143 of file SHAMapSync.cpp.

◆ gmn_ProcessDeferredReads()

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

private

Definition at line 227 of file SHAMapSync.cpp.

◆ finishFetch()

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

private

Definition at line 140 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_

intr_ptr::SharedPtr<SHAMapTreeNode> 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.

◆ branchFactor

constexpr unsigned int xrpl::SHAMap::branchFactor = SHAMapInnerNode::branchFactor

staticconstexpr

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

Definition at line 97 of file SHAMap.h.

◆ leafDepth

constexpr unsigned int xrpl::SHAMap::leafDepth = 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

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]

◆ upper_bound()

◆ lower_bound()

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

◆ firstBelow()