xrpld
Loading...
Searching...
No Matches
xrpl::SHAMap Class Reference

#include <SHAMap.h>

Collaboration diagram for xrpl::SHAMap:

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)
 Take a snapshot of the given map.
 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
 Return a new map that is a snapshot of this one.
void setFull (std::uint32_t ledgerSeq)
 Mark this map as "should be full": the local server wants every node it references in durable storage, so a nodestore miss is a gap to report.
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.
bool setImmutable ()
 Mark this map as immutable, so it can no longer be modified.
bool isSynching () const
bool isImmutable () const
void setSynching ()
 Mark this map as syncing, fixing its hash while still allowing missing nodes to be added.
void clearSynching ()
 Mark this map as no longer syncing, so it can be modified again.
bool isValid () const
 Whether the map can still be the map it claims to be.
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

std::uint32_t ledgerSeq () const
 The sequence of the ledger this map references, read atomically.
SHAMapState state () const
 The current state, read atomically.
void setInvalid ()
 Record that the map is provably not the one it claims to be.
bool trySetState (SHAMapState desired)
 Move the map to a new state, atomically.
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::atomic< std::uint32_t > ledgerSeq_ = 0
 The sequence of the ledger that this map references, if any.
SHAMapTreeNodePtr root_
std::atomic< SHAMapState > state_
 The map's state.
SHAMapType const type_
bool backed_ = true
std::atomic< bool > full_ = false
 Map is believed complete in database.

Detailed Description

Definition at line 114 of file SHAMap.h.

Member Typedef Documentation

◆ DeltaItem

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

Definition at line 174 of file SHAMap.h.

◆ Delta

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

◆ DescendCallback

Definition at line 770 of file SHAMap.h.

Member Enumeration Documentation

◆ BelowDirection

enum class xrpl::SHAMap::BelowDirection
strongprivate
Enumerator
First 
Last 

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

Take a snapshot of the given map.

Parameters
otherThe map to snapshot. An Invalid source yields an Invalid snapshot.
isMutableWhether the snapshot may be modified. Ignored when other is Invalid.

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

◆ SHAMap() [4/5]

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

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

◆ SHAMap() [5/5]

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

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

◆ family() [2/2]

Family & xrpl::SHAMap::family ( )

Definition at line 207 of file SHAMap.h.

◆ begin()

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

Definition at line 1119 of file SHAMap.h.

◆ end()

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

Definition at line 1125 of file SHAMap.h.

◆ snapShot()

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

Return a new map that is a snapshot of this one.

Handles copy on write for mutable snapshots. An invalid map yields an invalid snapshot.

Parameters
isMutableWhether the snapshot may be modified.
Returns
The snapshot.

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

◆ setFull()

void xrpl::SHAMap::setFull ( std::uint32_t ledgerSeq)

Mark this map as "should be full": the local server wants every node it references in durable storage, so a nodestore miss is a gap to report.

Publishes the ledger sequence before the flag. The sequence store is relaxed and the flag store is release, and finishFetch() reads the sequence only after acquiring the flag, so the one miss that withdraws the flag always reports the sequence stored here. Keeping both stores in one place is what makes that order impossible to get wrong.

Parameters
ledgerSeqSequence of the ledger this map belongs to, which the gap report names.

Definition at line 890 of file SHAMap.h.

◆ setLedgerSeq()

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

Definition at line 897 of file SHAMap.h.

◆ fetchRoot()

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

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

◆ delItem()

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

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

◆ addItem()

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

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

◆ getHash()

SHAMapHash xrpl::SHAMap::getHash ( ) const

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

◆ updateGiveItem()

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

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

◆ addGiveItem()

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

Definition at line 737 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 572 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 583 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
idthe identifier of the item.
Note
The item does not need to exist.

Definition at line 636 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
idthe identifier of the item.
Note
The item does not need to exist.

Definition at line 642 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
functioncalled with every node visited. If function returns false, visitNodes exits.

Definition at line 66 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
functioncalled with every node visited. If function returns false, visitDifferences exits.

Definition at line 128 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
functioncalled with every non inner node visited.

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

◆ getMissingNodes()

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

Check for nodes in the SHAMap not available.

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

Only a leaf may occupy a position at or beyond kLeafDepth. A map that breaks that is marked Invalid and the traversal is abandoned, so callers ask isValid() to tell an empty result from a satisfied map.

Parameters
maxNodesThe maximum number of found nodes to return
filterThe filter to use when retrieving nodes
Returns
The nodes known to be missing, or empty if the map is Invalid

Definition at line 349 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 478 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
keykey of the leaf
Returns
the proof path if found

Definition at line 867 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
rootHashroot hash of the map
keykey of the leaf
paththe proof path
Returns
true if verified successfully

Definition at line 900 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 568 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.

A root offered under a hash the map does not hold names another tree and is reported as invalid data. A root matching that hash is a duplicate.

Parameters
hashThe expected hash of the root node.
rootNodeA deserialized root node to add.
filterOptional 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 574 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.

A node that no valid tree can hold makes the map Invalid, which is terminal: the root hash committed to an impossible shape, so no peer can satisfy it.

Parameters
nodeIDThe position in the tree where this node belongs.
treeNodeA deserialized tree node to add.
filterOptional 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 625 of file libxrpl/shamap/SHAMapSync.cpp.

◆ setImmutable()

bool xrpl::SHAMap::setImmutable ( )
nodiscard

Mark this map as immutable, so it can no longer be modified.

Returns
false if the map is Invalid and was left unchanged, true otherwise.

Definition at line 940 of file SHAMap.h.

◆ isSynching()

bool xrpl::SHAMap::isSynching ( ) const
nodiscard
Returns
Whether the map is being synced against a hash it was given, so its hash is fixed while nodes may still be added.

Definition at line 947 of file SHAMap.h.

◆ isImmutable()

bool xrpl::SHAMap::isImmutable ( ) const
nodiscard
Returns
Whether the map is settled, with its hash and nodes fixed.

Definition at line 953 of file SHAMap.h.

◆ setSynching()

void xrpl::SHAMap::setSynching ( )

Mark this map as syncing, fixing its hash while still allowing missing nodes to be added.

The map must be freshly constructed. The body asserts that the map is not Invalid, so a caller that ignores the precondition stops a build with assertions enabled.

Definition at line 959 of file SHAMap.h.

◆ clearSynching()

void xrpl::SHAMap::clearSynching ( )

Mark this map as no longer syncing, so it can be modified again.

Moves only a Synching map. An Immutable map stays settled, a Modifying map has nothing to clear, and Invalid is terminal.

Definition at line 972 of file SHAMap.h.

◆ isValid()

bool xrpl::SHAMap::isValid ( ) const
nodiscard

Whether the map can still be the map it claims to be.

A map that is merely missing nodes is valid, and stays valid until something proves the tree it is syncing against cannot exist.

Returns
Whether the map has not been proven impossible.

Definition at line 994 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 946 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 953 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 734 of file libxrpl/shamap/SHAMapSync.cpp.

◆ setUnbacked()

void xrpl::SHAMap::setUnbacked ( )

Definition at line 1007 of file SHAMap.h.

◆ dump()

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

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

◆ invariants()

void xrpl::SHAMap::invariants ( ) const

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

◆ ledgerSeq()

std::uint32_t xrpl::SHAMap::ledgerSeq ( ) const
nodiscardprivate

The sequence of the ledger this map references, read atomically.

Returns
The sequence, or zero if the map references no ledger.

Definition at line 903 of file SHAMap.h.

◆ state()

SHAMapState xrpl::SHAMap::state ( ) const
nodiscardprivate

The current state, read atomically.

Orders state_ alone. The tree's nodes carry no ordering guarantees.

Returns
The state as of the call, which a concurrent walk may already have moved past.

Definition at line 909 of file SHAMap.h.

◆ setInvalid()

void xrpl::SHAMap::setInvalid ( )
private

Record that the map is provably not the one it claims to be.

Private because only the map itself can prove that, from a node that contradicts the hashes it is syncing against. Cannot fail, since Invalid outranks every other state; see trySetState().

Definition at line 1000 of file SHAMap.h.

◆ trySetState()

bool xrpl::SHAMap::trySetState ( SHAMapState desired)
private

Move the map to a new state, atomically.

With clearSynching(), the only writer of state_ past construction, so the order between the states lives in one place: Invalid outranks all of them and is always stored, while every other transition is refused once the map is Invalid, which is what makes that verdict terminal. clearSynching() is narrower and moves only Synching.

Parameters
desiredThe state to move to.
Returns
false if the map is Invalid and the requested state is not, leaving it unchanged; true otherwise.

Definition at line 915 of file SHAMap.h.

◆ cacheLookup()

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

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

◆ canonicalize()

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

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

◆ fetchNodeFromDB()

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

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

◆ fetchNodeNT() [1/2]

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

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

◆ fetchNodeNT() [2/2]

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

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

◆ fetchNode()

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

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

◆ checkFilter()

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

Definition at line 230 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 110 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 139 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 171 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 437 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 930 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 912 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 453 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
idThe key to search from, which need not be in the map.
directionFirst 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 595 of file libxrpl/shamap/SHAMap.cpp.

◆ descend() [1/3]

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

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

◆ descendThrow() [1/2]

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

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

◆ descend() [2/3]

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

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

◆ descendThrow() [2/2]

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

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

◆ descendNoStore()

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

Definition at line 356 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 490 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 806 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 829 of file libxrpl/shamap/SHAMapSync.cpp.

◆ peekFirstItem()

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

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

◆ peekNextItem()

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

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

◆ gmnProcessNodes()

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

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

◆ gmnProcessDeferredReads()

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

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

Member Data Documentation

◆ f_

Family& xrpl::SHAMap::f_
private

Definition at line 117 of file SHAMap.h.

◆ journal_

beast::Journal xrpl::SHAMap::journal_
private

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

◆ ledgerSeq_

std::atomic<std::uint32_t> xrpl::SHAMap::ledgerSeq_ = 0
private

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

Written when a map's ledger sequence is established (Ledger::setFull(), InboundLedger) while a nodestore reader thread reads it. Relaxed either way: it serves as a lookup hint for a nodestore keyed by hash.

Definition at line 138 of file SHAMap.h.

◆ root_

SHAMapTreeNodePtr xrpl::SHAMap::root_
private

Definition at line 140 of file SHAMap.h.

◆ state_

std::atomic<SHAMapState> xrpl::SHAMap::state_
mutableprivate

The map's state.

A getMissingNodes() walk writes it, through setInvalid() and clearSynching(), while whatever drives the acquisition reads it. The walk runs with the acquisition's lock released, so this is atomic rather than guarded.

Definition at line 150 of file SHAMap.h.

◆ type_

SHAMapType const xrpl::SHAMap::type_
private

Definition at line 151 of file SHAMap.h.

◆ backed_

bool xrpl::SHAMap::backed_ = true
private

Definition at line 152 of file SHAMap.h.

◆ full_

std::atomic<bool> xrpl::SHAMap::full_ = false
mutableprivate

Map is believed complete in database.

Atomic because finishFetch() clears it on any nodestore reader thread, several of which can run at once.

Definition at line 160 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 167 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 172 of file SHAMap.h.