rippled
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Private Types | Private Member Functions | Private Attributes | List of all members
ripple::SHAMap Class Reference

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

#include <SHAMap.h>

Collaboration diagram for ripple::SHAMap:
Collaboration graph
[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
 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:

  1. The key for a node is represented by the node's position in the tree (the "prefix property").
  2. 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 96 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 123 of file SHAMap.h.

◆ Delta

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

Definition at line 126 of file SHAMap.h.

◆ SharedPtrNodeStack

using ripple::SHAMap::SharedPtrNodeStack = std::stack< std::pair<intr_ptr::SharedPtr<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 372 of file SHAMap.h.

◆ descendCallback

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

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

◆ SHAMap() [4/5]

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

Definition at line 54 of file SHAMap.cpp.

◆ SHAMap() [5/5]

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

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

◆ family() [2/2]

Family & ripple::SHAMap::family ( )

Definition at line 150 of file SHAMap.h.

◆ begin()

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

Definition at line 755 of file SHAMap.h.

◆ end()

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

Definition at line 761 of file SHAMap.h.

◆ snapShot()

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

Definition at line 89 of file SHAMap.cpp.

◆ setFull()

void ripple::SHAMap::setFull ( )

Definition at line 590 of file SHAMap.h.

◆ setLedgerSeq()

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

Definition at line 596 of file SHAMap.h.

◆ fetchRoot()

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

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

◆ delItem()

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

Definition at line 721 of file SHAMap.cpp.

◆ addItem()

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

Definition at line 882 of file SHAMap.cpp.

◆ getHash()

SHAMapHash ripple::SHAMap::getHash ( ) const

Definition at line 890 of file SHAMap.cpp.

◆ updateGiveItem()

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

Definition at line 902 of file SHAMap.cpp.

◆ addGiveItem()

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

Definition at line 803 of file SHAMap.cpp.

◆ peekItem() [1/2]

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

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

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

Definition at line 677 of file SHAMap.cpp.

◆ visitNodes()

void ripple::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 40 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
functioncalled with every node visited. If function returns false, visitDifferences exits.

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

Definition at line 28 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
maxNodesThe maximum number of found nodes to return
filterThe filter to use when retrieving nodes
returnThe nodes known to be missing

The filter can hold alternate sources of nodes that are not permanently stored locally

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

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

Definition at line 862 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 529 of file SHAMapSync.cpp.

◆ addRootNode()

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

Definition at line 535 of file SHAMapSync.cpp.

◆ addKnownNode()

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

Definition at line 579 of file SHAMapSync.cpp.

◆ setImmutable()

void ripple::SHAMap::setImmutable ( )

Definition at line 602 of file SHAMap.h.

◆ isSynching()

bool ripple::SHAMap::isSynching ( ) const

Definition at line 611 of file SHAMap.h.

◆ setSynching()

void ripple::SHAMap::setSynching ( )

Definition at line 617 of file SHAMap.h.

◆ clearSynching()

void ripple::SHAMap::clearSynching ( )

Definition at line 623 of file SHAMap.h.

◆ isValid()

bool ripple::SHAMap::isValid ( ) const

Definition at line 629 of file SHAMap.h.

◆ compare()

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

Definition at line 125 of file SHAMapDelta.cpp.

◆ unshare()

int ripple::SHAMap::unshare ( )

Convert any modified nodes to shared.

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

◆ walkMap()

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

Definition at line 245 of file SHAMapDelta.cpp.

◆ walkMapParallel()

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

Definition at line 287 of file SHAMapDelta.cpp.

◆ deepCompare()

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

Definition at line 702 of file SHAMapSync.cpp.

◆ setUnbacked()

void ripple::SHAMap::setUnbacked ( )

Definition at line 635 of file SHAMap.h.

◆ dump()

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

Definition at line 1178 of file SHAMap.cpp.

◆ invariants()

void ripple::SHAMap::invariants ( ) const

Definition at line 1248 of file SHAMap.cpp.

◆ cacheLookup()

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

Definition at line 1223 of file SHAMap.cpp.

◆ canonicalize()

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

Definition at line 1233 of file SHAMap.cpp.

◆ fetchNodeFromDB()

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

Definition at line 169 of file SHAMap.cpp.

◆ fetchNodeNT() [1/2]

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

Definition at line 272 of file SHAMap.cpp.

◆ fetchNodeNT() [2/2]

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

Definition at line 249 of file SHAMap.cpp.

◆ fetchNode()

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

Definition at line 284 of file SHAMap.cpp.

◆ checkFilter()

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

Definition at line 216 of file SHAMap.cpp.

◆ dirtyUp()

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

Update hashes up to the root.

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

◆ findKey()

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

Return nullptr if key not found.

Definition at line 160 of file SHAMap.cpp.

◆ unshareNode()

template<class Node >
intr_ptr::SharedPtr< Node > ripple::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 SHAMap.cpp.

◆ preFlushNode()

template<class Node >
intr_ptr::SharedPtr< Node > ripple::SHAMap::preFlushNode ( intr_ptr::SharedPtr< Node >  node) const
private

prepare a node to be modified before flushing

Definition at line 1016 of file SHAMap.cpp.

◆ writeNode()

intr_ptr::SharedPtr< SHAMapTreeNode > ripple::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 995 of file SHAMap.cpp.

◆ firstBelow()

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

Definition at line 512 of file SHAMap.cpp.

◆ lastBelow()

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

Definition at line 500 of file SHAMap.cpp.

◆ belowHelper()

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

◆ descend() [1/3]

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

Definition at line 317 of file SHAMap.cpp.

◆ descendThrow() [1/2]

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

Definition at line 295 of file SHAMap.cpp.

◆ descend() [2/3]

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

Definition at line 333 of file SHAMap.cpp.

◆ descendThrow() [2/2]

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

Definition at line 306 of file SHAMap.cpp.

◆ descendAsync()

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

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

◆ descendNoStore()

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

Definition at line 350 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 526 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 774 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 798 of file SHAMapSync.cpp.

◆ peekFirstItem()

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

Definition at line 566 of file SHAMap.cpp.

◆ peekNextItem()

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

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

◆ walkSubTree()

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

Definition at line 1047 of file SHAMap.cpp.

◆ gmn_ProcessNodes()

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

Definition at line 174 of file SHAMapSync.cpp.

◆ gmn_ProcessDeferredReads()

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

Definition at line 266 of file SHAMapSync.cpp.

◆ finishFetch()

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

Definition at line 177 of file SHAMap.cpp.

Member Data Documentation

◆ f_

Family& ripple::SHAMap::f_
private

Definition at line 99 of file SHAMap.h.

◆ journal_

beast::Journal ripple::SHAMap::journal_
private

Definition at line 100 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 103 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 106 of file SHAMap.h.

◆ root_

intr_ptr::SharedPtr<SHAMapTreeNode> ripple::SHAMap::root_
private

Definition at line 108 of file SHAMap.h.

◆ state_

SHAMapState ripple::SHAMap::state_
mutableprivate

Definition at line 109 of file SHAMap.h.

◆ type_

SHAMapType const ripple::SHAMap::type_
private

Definition at line 110 of file SHAMap.h.

◆ backed_

bool ripple::SHAMap::backed_ = true
private

Definition at line 111 of file SHAMap.h.

◆ full_

bool ripple::SHAMap::full_ = false
mutableprivate

Definition at line 112 of file SHAMap.h.

◆ branchFactor

constexpr unsigned int ripple::SHAMap::branchFactor
staticconstexpr
Initial value:
=
SHAMapInnerNode::branchFactor
ripple::SHAMapInnerNode::branchFactor
static constexpr unsigned int branchFactor
Each inner node has 16 children (the 'radix tree' part of the map)
Definition SHAMapInnerNode.h:39

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

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

Generated by doxygen 1.9.8