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

Collaboration diagram for ripple::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? More...

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. More...

const_iterator	lower_bound (uint256 const &id) const
	Find the object with the greatest object id smaller than the input id. More...

void	visitNodes (std::function< bool(SHAMapTreeNode &)> const &function) const
	Visit every node in this SHAMap. More...

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. More...

void	visitLeaves (std::function< void(boost::intrusive_ptr< SHAMapItem const > const &)> const &) const
	Visit every leaf node in this SHAMap. More...

std::vector< std::pair< SHAMapNodeID, uint256 > >	getMissingNodes (int maxNodes, SHAMapSyncFilter *filter)
	Check for nodes in the SHAMap not available. More...

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. More...

void	serializeRoot (Serializer &s) const
	Serializes the root in a format appropriate for sending over the wire. More...

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. More...

int	flushDirty (NodeObjectType t)
	Flush modified nodes to the nodestore and convert them to shared. More...

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. More...

Static Public Attributes
static constexpr unsigned int	branchFactor
	Number of children each non-leaf node has (the 'radix tree' part of the map) More...

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

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

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

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

Private Member Functions
std::shared_ptr< SHAMapTreeNode >	cacheLookup (SHAMapHash const &hash) const

void	canonicalize (SHAMapHash const &hash, std::shared_ptr< SHAMapTreeNode > &) const

std::shared_ptr< SHAMapTreeNode >	fetchNodeFromDB (SHAMapHash const &hash) const

std::shared_ptr< SHAMapTreeNode >	fetchNodeNT (SHAMapHash const &hash) const

std::shared_ptr< SHAMapTreeNode >	fetchNodeNT (SHAMapHash const &hash, SHAMapSyncFilter *filter) const

std::shared_ptr< SHAMapTreeNode >	fetchNode (SHAMapHash const &hash) const

std::shared_ptr< SHAMapTreeNode >	checkFilter (SHAMapHash const &hash, SHAMapSyncFilter *filter) const

void	dirtyUp (SharedPtrNodeStack &stack, uint256 const &target, std::shared_ptr< SHAMapTreeNode > terminal)
	Update hashes up to the root. More...

SHAMapLeafNode *	walkTowardsKey (uint256 const &id, SharedPtrNodeStack *stack=nullptr) const
	Walk towards the specified id, returning the node. More...

SHAMapLeafNode *	findKey (uint256 const &id) const
	Return nullptr if key not found. More...

template<class Node >
std::shared_ptr< Node >	unshareNode (std::shared_ptr< Node >, SHAMapNodeID const &nodeID)
	Unshare the node, allowing it to be modified. More...

template<class Node >
std::shared_ptr< Node >	preFlushNode (std::shared_ptr< Node > node) const
	prepare a node to be modified before flushing More...

std::shared_ptr< SHAMapTreeNode >	writeNode (NodeObjectType t, std::shared_ptr< SHAMapTreeNode > node) const
	write and canonicalize modified node More...

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

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

SHAMapLeafNode *	belowHelper (std::shared_ptr< 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

std::shared_ptr< SHAMapTreeNode >	descend (std::shared_ptr< SHAMapInnerNode > const &, int branch) const

std::shared_ptr< SHAMapTreeNode >	descendThrow (std::shared_ptr< SHAMapInnerNode > const &, 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

std::shared_ptr< SHAMapTreeNode >	descendNoStore (std::shared_ptr< SHAMapInnerNode > const &, int branch) const

boost::intrusive_ptr< SHAMapItem const > const &	onlyBelow (SHAMapTreeNode *) const
	If there is only one leaf below this node, get its contents. More...

bool	hasInnerNode (SHAMapNodeID const &nodeID, SHAMapHash const &hash) const
	Does this map have this inner node? More...

bool	hasLeafNode (uint256 const &tag, SHAMapHash const &hash) const
	Does this map have this leaf node? More...

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

std::shared_ptr< 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. More...

std::uint32_t	ledgerSeq_ = 0
	The sequence of the ledger that this map references, if any. More...

std::shared_ptr< SHAMapTreeNode >	root_

SHAMapState	state_

const SHAMapType	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 95 of file SHAMap.h.

Member Typedef Documentation

◆ DeltaItem

using ripple::SHAMap::DeltaItem = std::pair< boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const> >

Definition at line 124 of file SHAMap.h.

◆ Delta

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

Definition at line 125 of file SHAMap.h.

◆ SharedPtrNodeStack

using ripple::SHAMap::SharedPtrNodeStack = std::stack<std::pair<std::shared_ptr<SHAMapTreeNode>, SHAMapNodeID> >

private

Definition at line 370 of file SHAMap.h.

◆ DeltaRef

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

private

Definition at line 373 of file SHAMap.h.

◆ descendCallback

using ripple::SHAMap::descendCallback = std::function<void(std::shared_ptr<SHAMapTreeNode>, SHAMapHash const&)>

private

Definition at line 464 of file SHAMap.h.

Constructor & Destructor Documentation

◆ SHAMap() [1/5]

ripple::SHAMap::SHAMap ( )

delete

◆ SHAMap() [2/5]

ripple::SHAMap::SHAMap ( SHAMap const & )

delete

◆ SHAMap() [3/5]

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

Definition at line 69 of file SHAMap.cpp.

◆ SHAMap() [4/5]

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

Definition at line 53 of file SHAMap.cpp.

◆ SHAMap() [5/5]

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

Definition at line 63 of file SHAMap.cpp.

◆ ~SHAMap()

ripple::SHAMap::~SHAMap ( )

default

Member Function Documentation

◆ operator=()

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

delete

◆ family() [1/2]

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

Definition at line 143 of file SHAMap.h.

◆ family() [2/2]

Family& ripple::SHAMap::family ( )

Definition at line 149 of file SHAMap.h.

◆ begin()

SHAMap::const_iterator ripple::SHAMap::begin ( ) const

Definition at line 746 of file SHAMap.h.

◆ end()

SHAMap::const_iterator ripple::SHAMap::end ( ) const

Definition at line 752 of file SHAMap.h.

◆ snapShot()

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

Definition at line 88 of file SHAMap.cpp.

◆ setFull()

void ripple::SHAMap::setFull ( )

Definition at line 588 of file SHAMap.h.

◆ setLedgerSeq()

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

Definition at line 594 of file SHAMap.h.

◆ fetchRoot()

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

Definition at line 904 of file SHAMap.cpp.

◆ hasItem()

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

Does the tree have an item with the given ID?

Definition at line 690 of file SHAMap.cpp.

◆ delItem()

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

Definition at line 696 of file SHAMap.cpp.

◆ addItem()

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

Definition at line 844 of file SHAMap.cpp.

◆ getHash()

SHAMapHash ripple::SHAMap::getHash ( ) const

Definition at line 852 of file SHAMap.cpp.

◆ updateGiveItem()

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

Definition at line 864 of file SHAMap.cpp.

◆ addGiveItem()

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

Definition at line 774 of file SHAMap.cpp.

◆ peekItem() [1/2]

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

Definition at line 592 of file SHAMap.cpp.

◆ peekItem() [2/2]

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

Definition at line 603 of file SHAMap.cpp.

◆ upper_bound()

SHAMap::const_iterator ripple::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 615 of file SHAMap.cpp.

◆ lower_bound()

SHAMap::const_iterator ripple::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 652 of file SHAMap.cpp.

◆ visitNodes()

void ripple::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 39 of file SHAMapSync.cpp.

◆ visitDifferences()

void ripple::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 100 of file SHAMapSync.cpp.

◆ visitLeaves()

void ripple::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 27 of file SHAMapSync.cpp.

◆ getMissingNodes()

std::vector< std::pair< SHAMapNodeID, uint256 > > ripple::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 317 of file SHAMapSync.cpp.

◆ getNodeFat()

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

Definition at line 427 of file SHAMapSync.cpp.

◆ getProofPath()

std::optional< std::vector< Blob > > ripple::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 791 of file SHAMapSync.cpp.

◆ verifyProofPath()

bool ripple::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 826 of file SHAMapSync.cpp.

◆ serializeRoot()

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

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

Definition at line 522 of file SHAMapSync.cpp.

◆ addRootNode()

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

Definition at line 528 of file SHAMapSync.cpp.

◆ addKnownNode()

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

Definition at line 570 of file SHAMapSync.cpp.

◆ setImmutable()

void ripple::SHAMap::setImmutable ( )

Definition at line 600 of file SHAMap.h.

◆ isSynching()

bool ripple::SHAMap::isSynching ( ) const

Definition at line 607 of file SHAMap.h.

◆ setSynching()

void ripple::SHAMap::setSynching ( )

Definition at line 613 of file SHAMap.h.

◆ clearSynching()

void ripple::SHAMap::clearSynching ( )

Definition at line 619 of file SHAMap.h.

◆ isValid()

bool ripple::SHAMap::isValid ( ) const

Definition at line 625 of file SHAMap.h.

◆ compare()

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

Definition at line 124 of file SHAMapDelta.cpp.

◆ unshare()

int ripple::SHAMap::unshare ( )

Convert any modified nodes to shared.

Definition at line 985 of file SHAMap.cpp.

◆ flushDirty()

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

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

Definition at line 992 of file SHAMap.cpp.

◆ walkMap()

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

Definition at line 236 of file SHAMapDelta.cpp.

◆ walkMapParallel()

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

Definition at line 278 of file SHAMapDelta.cpp.

◆ deepCompare()

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

Definition at line 667 of file SHAMapSync.cpp.

◆ setUnbacked()

void ripple::SHAMap::setUnbacked ( )

Definition at line 631 of file SHAMap.h.

◆ dump()

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

Definition at line 1124 of file SHAMap.cpp.

◆ invariants()

void ripple::SHAMap::invariants ( ) const

Definition at line 1188 of file SHAMap.cpp.

◆ cacheLookup()

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::cacheLookup ( SHAMapHash const & hash ) const

private

Definition at line 1167 of file SHAMap.cpp.

◆ canonicalize()

void ripple::SHAMap::canonicalize	(	SHAMapHash const &	hash,
		std::shared_ptr< SHAMapTreeNode > &	node
	)		const

private

Definition at line 1175 of file SHAMap.cpp.

◆ fetchNodeFromDB()

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::fetchNodeFromDB ( SHAMapHash const & hash ) const

private

Definition at line 163 of file SHAMap.cpp.

◆ fetchNodeNT() [1/2]

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::fetchNodeNT ( SHAMapHash const & hash ) const

private

Definition at line 266 of file SHAMap.cpp.

◆ fetchNodeNT() [2/2]

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::fetchNodeNT	(	SHAMapHash const &	hash,
		SHAMapSyncFilter *	filter
	)		const

private

Definition at line 243 of file SHAMap.cpp.

◆ fetchNode()

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::fetchNode ( SHAMapHash const & hash ) const

private

Definition at line 278 of file SHAMap.cpp.

◆ checkFilter()

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::checkFilter	(	SHAMapHash const &	hash,
		SHAMapSyncFilter *	filter
	)		const

private

Definition at line 210 of file SHAMap.cpp.

◆ dirtyUp()

void ripple::SHAMap::dirtyUp	(	SharedPtrNodeStack &	stack,
		uint256 const &	target,
		std::shared_ptr< SHAMapTreeNode >	terminal
	)

private

Update hashes up to the root.

Definition at line 94 of file SHAMap.cpp.

◆ walkTowardsKey()

SHAMapLeafNode * ripple::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 128 of file SHAMap.cpp.

◆ findKey()

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

private

Return nullptr if key not found.

Definition at line 154 of file SHAMap.cpp.

◆ unshareNode()

template<class Node >

std::shared_ptr< Node > ripple::SHAMap::unshareNode	(	std::shared_ptr< Node >	node,
		SHAMapNodeID const &	nodeID
	)

private

Unshare the node, allowing it to be modified.

Definition at line 430 of file SHAMap.cpp.

◆ preFlushNode()

template<class Node >

std::shared_ptr< Node > ripple::SHAMap::preFlushNode ( std::shared_ptr< Node > node ) const

private

prepare a node to be modified before flushing

Definition at line 969 of file SHAMap.cpp.

◆ writeNode()

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::writeNode	(	NodeObjectType	t,
		std::shared_ptr< 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 950 of file SHAMap.cpp.

◆ firstBelow()

SHAMapLeafNode * ripple::SHAMap::firstBelow	(	std::shared_ptr< SHAMapTreeNode >	node,
		SharedPtrNodeStack &	stack,
		int	branch = `0`
	)		const

private

Definition at line 499 of file SHAMap.cpp.

◆ lastBelow()

SHAMapLeafNode * ripple::SHAMap::lastBelow	(	std::shared_ptr< SHAMapTreeNode >	node,
		SharedPtrNodeStack &	stack,
		int	branch = `branchFactor`
	)		const

private

Definition at line 487 of file SHAMap.cpp.

◆ belowHelper()

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

private

Definition at line 446 of file SHAMap.cpp.

◆ descend() [1/3]

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

private

Definition at line 312 of file SHAMap.cpp.

◆ descendThrow() [1/2]

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

private

Definition at line 289 of file SHAMap.cpp.

◆ descend() [2/3]

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::descend	(	std::shared_ptr< SHAMapInnerNode > const &	parent,
		int	branch
	)		const

private

Definition at line 328 of file SHAMap.cpp.

◆ descendThrow() [2/2]

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::descendThrow	(	std::shared_ptr< SHAMapInnerNode > const &	parent,
		int	branch
	)		const

private

Definition at line 300 of file SHAMap.cpp.

◆ descendAsync()

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

private

Definition at line 386 of file SHAMap.cpp.

◆ descend() [3/3]

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

private

Definition at line 357 of file SHAMap.cpp.

◆ descendNoStore()

std::shared_ptr< SHAMapTreeNode > ripple::SHAMap::descendNoStore	(	std::shared_ptr< SHAMapInnerNode > const &	parent,
		int	branch
	)		const

private

Definition at line 346 of file SHAMap.cpp.

◆ onlyBelow()

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

private

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

Definition at line 513 of file SHAMap.cpp.

◆ hasInnerNode()

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

private

Does this map have this inner node?

Definition at line 739 of file SHAMapSync.cpp.

◆ hasLeafNode()

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

private

Does this map have this leaf node?

Definition at line 763 of file SHAMapSync.cpp.

◆ peekFirstItem()

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

private

Definition at line 549 of file SHAMap.cpp.

◆ peekNextItem()

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

private

Definition at line 563 of file SHAMap.cpp.

◆ walkBranch()

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

private

Definition at line 38 of file SHAMapDelta.cpp.

◆ walkSubTree()

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

private

Definition at line 999 of file SHAMap.cpp.

◆ gmn_ProcessNodes()

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

private

Definition at line 172 of file SHAMapSync.cpp.

◆ gmn_ProcessDeferredReads()

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

private

Definition at line 265 of file SHAMapSync.cpp.

◆ finishFetch()

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

private

Definition at line 171 of file SHAMap.cpp.

Member Data Documentation

◆ f_

Family& ripple::SHAMap::f_

private

Definition at line 98 of file SHAMap.h.

◆ journal_

beast::Journal ripple::SHAMap::journal_

private

Definition at line 99 of file SHAMap.h.

◆ cowid_

std::uint32_t ripple::SHAMap::cowid_ = 1

private

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

Definition at line 102 of file SHAMap.h.

◆ ledgerSeq_

std::uint32_t ripple::SHAMap::ledgerSeq_ = 0

private

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

Definition at line 105 of file SHAMap.h.

◆ root_

std::shared_ptr<SHAMapTreeNode> ripple::SHAMap::root_

private

Definition at line 107 of file SHAMap.h.

◆ state_

SHAMapState ripple::SHAMap::state_

mutableprivate

Definition at line 108 of file SHAMap.h.

◆ type_

const SHAMapType ripple::SHAMap::type_

private

Definition at line 109 of file SHAMap.h.

◆ backed_

bool ripple::SHAMap::backed_ = true

private

Definition at line 110 of file SHAMap.h.

◆ full_

bool ripple::SHAMap::full_ = false

mutableprivate

Definition at line 111 of file SHAMap.h.

◆ branchFactor

constexpr unsigned int ripple::SHAMap::branchFactor

staticconstexpr

Initial value:

=

SHAMapInnerNode::branchFactor

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

Definition at line 116 of file SHAMap.h.

◆ leafDepth

constexpr unsigned int ripple::SHAMap::leafDepth = 64

staticconstexpr

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

Definition at line 120 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()