xrpl::SHAMapInnerNode Class Reference

#include <SHAMapInnerNode.h>

Inheritance diagram for xrpl::SHAMapInnerNode:

Collaboration diagram for xrpl::SHAMapInnerNode:

Public Member Functions
	SHAMapInnerNode (std::uint32_t cowid, std::uint8_t numAllocatedChildren=2)
	SHAMapInnerNode (SHAMapInnerNode const &)=delete
SHAMapInnerNode &	operator= (SHAMapInnerNode const &)=delete
	~SHAMapInnerNode ()
void	partialDestructor () override
intr_ptr::SharedPtr< SHAMapTreeNode >	clone (std::uint32_t cowid) const override
	Make a copy of this node, setting the owner.
SHAMapNodeType	getType () const override
	Determines the type of node.
bool	isLeaf () const override
	Determines if this is a leaf node.
bool	isInner () const override
	Determines if this is an inner node.
bool	isEmpty () const
bool	isEmptyBranch (int m) const
int	getBranchCount () const
SHAMapHash const &	getChildHash (int m) const
void	setChild (int m, intr_ptr::SharedPtr< SHAMapTreeNode > child)
void	shareChild (int m, intr_ptr::SharedPtr< SHAMapTreeNode > const &child)
SHAMapTreeNode *	getChildPointer (int branch)
intr_ptr::SharedPtr< SHAMapTreeNode >	getChild (int branch)
intr_ptr::SharedPtr< SHAMapTreeNode >	canonicalizeChild (int branch, intr_ptr::SharedPtr< SHAMapTreeNode > node)
bool	isFullBelow (std::uint32_t generation) const
void	setFullBelowGen (std::uint32_t gen)
void	updateHash () override
	Recalculate the hash of this node.
void	updateHashDeep ()
	Recalculate the hash of all children and this node.
void	serializeForWire (Serializer &) const override
	Serialize the node in a format appropriate for sending over the wire.
void	serializeWithPrefix (Serializer &) const override
	Serialize the node in a format appropriate for hashing.
std::string	getString (SHAMapNodeID const &) const override
void	invariants (bool is_root=false) const override
std::uint32_t	cowid () const
	Returns the SHAMap that owns this node.
void	unshare ()
	If this node is shared with another map, mark it as no longer shared.
SHAMapHash const &	getHash () const
	Return the hash of this node.
void	addStrongRef () const noexcept
void	addWeakRef () const noexcept
ReleaseStrongRefAction	releaseStrongRef () const
ReleaseStrongRefAction	addWeakReleaseStrongRef () const
ReleaseWeakRefAction	releaseWeakRef () const
bool	checkoutStrongRefFromWeak () const noexcept
bool	expired () const noexcept
std::size_t	use_count () const noexcept

Static Public Member Functions
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeFullInner (Slice data, SHAMapHash const &hash, bool hashValid)
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeCompressedInner (Slice data)
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeFromPrefix (Slice rawNode, SHAMapHash const &hash)
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeFromWire (Slice rawNode)

Static Public Attributes
static constexpr unsigned int	branchFactor = 16
	Each inner node has 16 children (the 'radix tree' part of the map)

Protected Attributes
SHAMapHash	hash_
std::uint32_t	cowid_
	Determines the owning SHAMap, if any.

Private Types
using	CountType = std::uint16_t
using	FieldType = std::uint32_t

Private Member Functions
void	resizeChildArrays (std::uint8_t toAllocate)
	Convert arrays stored in hashesAndChildren_ so they can store the requested number of children.
std::optional< int >	getChildIndex (int i) const
	Get the child's index inside the hashes or children array (stored in hashesAndChildren_.
template<class F >
void	iterChildren (F &&f) const
	Call the f callback for all 16 (branchFactor) branches - even if the branch is empty.
template<class F >
void	iterNonEmptyChildIndexes (F &&f) const
	Call the f callback for all non-empty branches.

Static Private Member Functions
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeTransaction (Slice data, SHAMapHash const &hash, bool hashValid)
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeAccountState (Slice data, SHAMapHash const &hash, bool hashValid)
static intr_ptr::SharedPtr< SHAMapTreeNode >	makeTransactionWithMeta (Slice data, SHAMapHash const &hash, bool hashValid)
static auto &	getCounter () noexcept

Private Attributes
TaggedPointer	hashesAndChildren_
	Opaque type that contains the hashes array (array of type SHAMapHash) and the children array (array of type intr_ptr::SharedPtr<SHAMapInnerNode>).
std::uint32_t	fullBelowGen_ = 0
std::uint16_t	isBranch_ = 0
std::atomic< std::uint16_t >	lock_ = 0
	A bitlock for the children of this node, with one bit per child.
std::atomic< FieldType >	refCounts {strongDelta}
	refCounts consists of four fields that are treated atomically:

Static Private Attributes
static constexpr size_t	StrongCountNumBits = sizeof(CountType) * 8
static constexpr size_t	WeakCountNumBits = StrongCountNumBits - 2
static constexpr size_t	FieldTypeBits = sizeof(FieldType) * 8
static constexpr FieldType	one = 1
static constexpr FieldType	strongDelta = 1
	Amount to change the strong count when adding or releasing a reference.
static constexpr FieldType	weakDelta = (one << StrongCountNumBits)
	Amount to change the weak count when adding or releasing a reference.
static constexpr FieldType	partialDestroyStartedMask = (one << (FieldTypeBits - 1))
	Flag that is set when the partialDestroy function has started running (or is about to start running).
static constexpr FieldType	partialDestroyFinishedMask = (one << (FieldTypeBits - 2))
	Flag that is set when the partialDestroy function has finished running.
static constexpr FieldType	tagMask = partialDestroyStartedMask | partialDestroyFinishedMask
	Mask that will zero out all the count bits and leave the tag bits unchanged.
static constexpr FieldType	valueMask = ~tagMask
	Mask that will zero out the tag bits and leave the count bits unchanged.
static constexpr FieldType	strongMask = ((one << StrongCountNumBits) - 1) & valueMask
	Mask that will zero out everything except the strong count.
static constexpr FieldType	weakMask = (((one << WeakCountNumBits) - 1) << StrongCountNumBits) & valueMask
	Mask that will zero out everything except the weak count.

Detailed Description

Definition at line 14 of file SHAMapInnerNode.h.

Member Typedef Documentation

CountType

using xrpl::IntrusiveRefCounts::CountType = std::uint16_t

privateinherited

Definition at line 100 of file IntrusiveRefCounts.h.

FieldType

using xrpl::IntrusiveRefCounts::FieldType = std::uint32_t

privateinherited

Definition at line 103 of file IntrusiveRefCounts.h.

Constructor & Destructor Documentation

SHAMapInnerNode() [1/2]

xrpl::SHAMapInnerNode::SHAMapInnerNode ( std::uint32_t  cowid, std::uint8_t  numAllocatedChildren = 2  )

explicit

Definition at line 13 of file SHAMapInnerNode.cpp.

SHAMapInnerNode() [2/2]

xrpl::SHAMapInnerNode::SHAMapInnerNode ( SHAMapInnerNode const &  )

delete

~SHAMapInnerNode()

xrpl::SHAMapInnerNode::~SHAMapInnerNode ( )

default

Member Function Documentation

resizeChildArrays()

void xrpl::SHAMapInnerNode::resizeChildArrays ( std::uint8_t  toAllocate )

private

Convert arrays stored in hashesAndChildren_ so they can store the requested number of children.

Parameters

toAllocate

allocate space for at least this number of children (must be <= branchFactor)

Note

the arrays may allocate more than the requested value in toAllocate. This is due to the implementation of TagPointer, which only supports allocating arrays of 4 different sizes.

Definition at line 44 of file SHAMapInnerNode.cpp.

getChildIndex()

std::optional< int > xrpl::SHAMapInnerNode::getChildIndex ( int  i ) const

private

Get the child's index inside the hashes or children array (stored in hashesAndChildren_.

These arrays may or may not be sparse). The optional will be empty is an empty branch is requested and the arrays are sparse.

Parameters

i	index of the requested child

Definition at line 50 of file SHAMapInnerNode.cpp.

iterChildren()

template<class F >

void xrpl::SHAMapInnerNode::iterChildren ( F &&  f ) const

private

Call the f callback for all 16 (branchFactor) branches - even if the branch is empty.

Parameters

f	a one parameter callback function. The parameter is the child's hash.

Definition at line 31 of file SHAMapInnerNode.cpp.

iterNonEmptyChildIndexes()

template<class F >

void xrpl::SHAMapInnerNode::iterNonEmptyChildIndexes ( F &&  f ) const

private

Call the f callback for all non-empty branches.

Parameters

f	a two parameter callback function. The first parameter is the branch number, the second parameter is the index into the array. For dense formats these are the same, for sparse they may be different.

Definition at line 38 of file SHAMapInnerNode.cpp.

operator=()

SHAMapInnerNode & xrpl::SHAMapInnerNode::operator= ( SHAMapInnerNode const &  )

delete

partialDestructor()

void xrpl::SHAMapInnerNode::partialDestructor ( )

overridevirtual

Reimplemented from xrpl::SHAMapTreeNode.

Definition at line 21 of file SHAMapInnerNode.cpp.

clone()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapInnerNode::clone ( std::uint32_t  cowid ) const

overridevirtual

Make a copy of this node, setting the owner.

Implements xrpl::SHAMapTreeNode.

Definition at line 56 of file SHAMapInnerNode.cpp.

getType()

SHAMapNodeType xrpl::SHAMapInnerNode::getType ( ) const

overridevirtual

Determines the type of node.

Implements xrpl::SHAMapTreeNode.

Definition at line 94 of file SHAMapInnerNode.h.

isLeaf()

bool xrpl::SHAMapInnerNode::isLeaf ( ) const

overridevirtual

Determines if this is a leaf node.

Implements xrpl::SHAMapTreeNode.

Definition at line 100 of file SHAMapInnerNode.h.

isInner()

bool xrpl::SHAMapInnerNode::isInner ( ) const

overridevirtual

Determines if this is an inner node.

Implements xrpl::SHAMapTreeNode.

Definition at line 106 of file SHAMapInnerNode.h.

isEmpty()

bool xrpl::SHAMapInnerNode::isEmpty

(

)

const

Definition at line 172 of file SHAMapInnerNode.h.

isEmptyBranch()

bool xrpl::SHAMapInnerNode::isEmptyBranch

(

int

m

)

const

Definition at line 178 of file SHAMapInnerNode.h.

getBranchCount()

int xrpl::SHAMapInnerNode::getBranchCount

(

)

const

Definition at line 184 of file SHAMapInnerNode.h.

getChildHash()

SHAMapHash const & xrpl::SHAMapInnerNode::getChildHash

(

int

m

)

const

Definition at line 316 of file SHAMapInnerNode.cpp.

setChild()

void xrpl::SHAMapInnerNode::setChild	(	int	m,
		intr_ptr::SharedPtr< SHAMapTreeNode >	child
	)

Definition at line 242 of file SHAMapInnerNode.cpp.

shareChild()

void xrpl::SHAMapInnerNode::shareChild	(	int	m,
		intr_ptr::SharedPtr< SHAMapTreeNode > const &	child
	)

Definition at line 278 of file SHAMapInnerNode.cpp.

getChildPointer()

SHAMapTreeNode * xrpl::SHAMapInnerNode::getChildPointer

(

int

branch

)

Definition at line 290 of file SHAMapInnerNode.cpp.

getChild()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapInnerNode::getChild

(

int

branch

)

Definition at line 303 of file SHAMapInnerNode.cpp.

canonicalizeChild()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapInnerNode::canonicalizeChild	(	int	branch,
		intr_ptr::SharedPtr< SHAMapTreeNode >	node
	)

Definition at line 326 of file SHAMapInnerNode.cpp.

isFullBelow()

bool xrpl::SHAMapInnerNode::isFullBelow

(

std::uint32_t

generation

)

const

Definition at line 190 of file SHAMapInnerNode.h.

setFullBelowGen()

void xrpl::SHAMapInnerNode::setFullBelowGen

(

std::uint32_t

gen

)

Definition at line 196 of file SHAMapInnerNode.h.

updateHash()

void xrpl::SHAMapInnerNode::updateHash ( )

overridevirtual

Recalculate the hash of this node.

Implements xrpl::SHAMapTreeNode.

Definition at line 166 of file SHAMapInnerNode.cpp.

updateHashDeep()

void xrpl::SHAMapInnerNode::updateHashDeep

(

)

Recalculate the hash of all children and this node.

Definition at line 181 of file SHAMapInnerNode.cpp.

serializeForWire()

void xrpl::SHAMapInnerNode::serializeForWire ( Serializer &  ) const

overridevirtual

Serialize the node in a format appropriate for sending over the wire.

Implements xrpl::SHAMapTreeNode.

Definition at line 195 of file SHAMapInnerNode.cpp.

serializeWithPrefix()

void xrpl::SHAMapInnerNode::serializeWithPrefix ( Serializer &  ) const

overridevirtual

Serialize the node in a format appropriate for hashing.

Implements xrpl::SHAMapTreeNode.

Definition at line 218 of file SHAMapInnerNode.cpp.

getString()

std::string xrpl::SHAMapInnerNode::getString ( SHAMapNodeID const &  id ) const

overridevirtual

Reimplemented from xrpl::SHAMapTreeNode.

Definition at line 227 of file SHAMapInnerNode.cpp.

invariants()

void xrpl::SHAMapInnerNode::invariants ( bool  is_root = false ) const

overridevirtual

Implements xrpl::SHAMapTreeNode.

Definition at line 355 of file SHAMapInnerNode.cpp.

makeFullInner()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapInnerNode::makeFullInner ( Slice  data, SHAMapHash const &  hash, bool  hashValid  )

static

Definition at line 100 of file SHAMapInnerNode.cpp.

makeCompressedInner()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapInnerNode::makeCompressedInner ( Slice  data )

static

Definition at line 131 of file SHAMapInnerNode.cpp.

getHash()

SHAMapHash const & xrpl::SHAMapTreeNode::getHash ( ) const

inherited

Return the hash of this node.

Definition at line 121 of file SHAMapTreeNode.h.

makeFromPrefix()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapTreeNode::makeFromPrefix ( Slice  rawNode, SHAMapHash const &  hash  )

staticinherited

Definition at line 109 of file SHAMapTreeNode.cpp.

makeFromWire()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapTreeNode::makeFromWire ( Slice  rawNode )

staticinherited

Definition at line 78 of file SHAMapTreeNode.cpp.

makeTransaction()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapTreeNode::makeTransaction ( Slice  data, SHAMapHash const &  hash, bool  hashValid  )

staticprivateinherited

Definition at line 16 of file SHAMapTreeNode.cpp.

makeAccountState()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapTreeNode::makeAccountState ( Slice  data, SHAMapHash const &  hash, bool  hashValid  )

staticprivateinherited

Definition at line 51 of file SHAMapTreeNode.cpp.

makeTransactionWithMeta()

intr_ptr::SharedPtr< SHAMapTreeNode > xrpl::SHAMapTreeNode::makeTransactionWithMeta ( Slice  data, SHAMapHash const &  hash, bool  hashValid  )

staticprivateinherited

Definition at line 27 of file SHAMapTreeNode.cpp.

addStrongRef()

void xrpl::IntrusiveRefCounts::addStrongRef ( ) const

noexceptinherited

Definition at line 224 of file IntrusiveRefCounts.h.

addWeakRef()

void xrpl::IntrusiveRefCounts::addWeakRef ( ) const

noexceptinherited

Definition at line 230 of file IntrusiveRefCounts.h.

releaseStrongRef()

ReleaseStrongRefAction xrpl::IntrusiveRefCounts::releaseStrongRef ( ) const

inherited

Definition at line 236 of file IntrusiveRefCounts.h.

addWeakReleaseStrongRef()

ReleaseStrongRefAction xrpl::IntrusiveRefCounts::addWeakReleaseStrongRef ( ) const

inherited

Definition at line 284 of file IntrusiveRefCounts.h.

releaseWeakRef()

ReleaseWeakRefAction xrpl::IntrusiveRefCounts::releaseWeakRef ( ) const

inherited

Definition at line 337 of file IntrusiveRefCounts.h.

checkoutStrongRefFromWeak()

bool xrpl::IntrusiveRefCounts::checkoutStrongRefFromWeak ( ) const

noexceptinherited

Definition at line 364 of file IntrusiveRefCounts.h.

expired()

bool xrpl::IntrusiveRefCounts::expired ( ) const

noexceptinherited

Definition at line 381 of file IntrusiveRefCounts.h.

use_count()

std::size_t xrpl::IntrusiveRefCounts::use_count ( ) const

noexceptinherited

Definition at line 388 of file IntrusiveRefCounts.h.

getCounter()

static auto & xrpl::CountedObject< SHAMapInnerNode >::getCounter ( )

staticprivatenoexceptinherited

Definition at line 109 of file CountedObject.h.

Member Data Documentation

branchFactor

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

staticconstexpr

Each inner node has 16 children (the 'radix tree' part of the map)

Definition at line 18 of file SHAMapInnerNode.h.

hashesAndChildren_

TaggedPointer xrpl::SHAMapInnerNode::hashesAndChildren_

private

Opaque type that contains the hashes array (array of type SHAMapHash) and the children array (array of type intr_ptr::SharedPtr<SHAMapInnerNode>).

Definition at line 25 of file SHAMapInnerNode.h.

fullBelowGen_

std::uint32_t xrpl::SHAMapInnerNode::fullBelowGen_ = 0

private

Definition at line 27 of file SHAMapInnerNode.h.

isBranch_

std::uint16_t xrpl::SHAMapInnerNode::isBranch_ = 0

private

Definition at line 28 of file SHAMapInnerNode.h.

lock_

std::atomic<std::uint16_t> xrpl::SHAMapInnerNode::lock_ = 0

mutableprivate

A bitlock for the children of this node, with one bit per child.

Definition at line 31 of file SHAMapInnerNode.h.

hash_

SHAMapHash xrpl::SHAMapTreeNode::hash_

protectedinherited

Definition at line 33 of file SHAMapTreeNode.h.

cowid_

std::uint32_t xrpl::SHAMapTreeNode::cowid_

protectedinherited

Determines the owning SHAMap, if any.

Used for copy-on-write semantics.

If this value is 0, the node is not dirty and does not need to be flushed. It is eligible for sharing and may be included multiple SHAMap instances.

Definition at line 41 of file SHAMapTreeNode.h.

StrongCountNumBits

constexpr size_t xrpl::IntrusiveRefCounts::StrongCountNumBits = sizeof(CountType) * 8

staticconstexprprivateinherited

Definition at line 101 of file IntrusiveRefCounts.h.

WeakCountNumBits

constexpr size_t xrpl::IntrusiveRefCounts::WeakCountNumBits = StrongCountNumBits - 2

staticconstexprprivateinherited

Definition at line 102 of file IntrusiveRefCounts.h.

FieldTypeBits

constexpr size_t xrpl::IntrusiveRefCounts::FieldTypeBits = sizeof(FieldType) * 8

staticconstexprprivateinherited

Definition at line 104 of file IntrusiveRefCounts.h.

one

constexpr FieldType xrpl::IntrusiveRefCounts::one = 1

staticconstexprprivateinherited

Definition at line 105 of file IntrusiveRefCounts.h.

refCounts

std::atomic<FieldType> xrpl::IntrusiveRefCounts::refCounts {strongDelta}

mutableprivateinherited

refCounts consists of four fields that are treated atomically:

1. Strong count. This is a count of the number of shared pointers that hold a reference to this object. When the strong counts goes to zero, if the weak count is zero, the destructor is run. If the weak count is non-zero when the strong count goes to zero then the partialDestructor is run.
2. Weak count. This is a count of the number of weak pointer that hold a reference to this object. When the weak count goes to zero and the strong count is also zero, then the destructor is run.
3. Partial destroy started bit. This bit is set if the partialDestructor function has been started (or is about to be started). This is used to prevent the destructor from running concurrently with the partial destructor. This can easily happen when the last strong pointer release its reference in one thread and starts the partialDestructor, while in another thread the last weak pointer goes out of scope and starts the destructor while the partialDestructor is still running. Both a start and finished bit is needed to handle a corner-case where the last strong pointer goes out of scope, then then last weakPointer goes out of scope, but this happens before the partialDestructor bit is set. It would be possible to use a single bit if it could also be set atomically when the strong count goes to zero and the weak count is non-zero, but that would add complexity (and likely slow down common cases as well).
4. Partial destroy finished bit. This bit is set when the partialDestructor has finished running. See (3) above for more information.

Definition at line 140 of file IntrusiveRefCounts.h.

strongDelta

constexpr FieldType xrpl::IntrusiveRefCounts::strongDelta = 1

staticconstexprprivateinherited

Amount to change the strong count when adding or releasing a reference.

Note: The strong count is stored in the low StrongCountNumBits bits of refCounts

Definition at line 147 of file IntrusiveRefCounts.h.

weakDelta

constexpr FieldType xrpl::IntrusiveRefCounts::weakDelta = (one << StrongCountNumBits)

staticconstexprprivateinherited

Amount to change the weak count when adding or releasing a reference.

Note: The weak count is stored in the high WeakCountNumBits bits of refCounts

Definition at line 154 of file IntrusiveRefCounts.h.

partialDestroyStartedMask

constexpr FieldType xrpl::IntrusiveRefCounts::partialDestroyStartedMask = (one << (FieldTypeBits - 1))

staticconstexprprivateinherited

Flag that is set when the partialDestroy function has started running (or is about to start running).

See description of the refCounts field for a fuller description of this field.

Definition at line 162 of file IntrusiveRefCounts.h.

partialDestroyFinishedMask

constexpr FieldType xrpl::IntrusiveRefCounts::partialDestroyFinishedMask = (one << (FieldTypeBits - 2))

staticconstexprprivateinherited

Flag that is set when the partialDestroy function has finished running.

See description of the refCounts field for a fuller description of this field.

Definition at line 169 of file IntrusiveRefCounts.h.

tagMask

constexpr FieldType xrpl::IntrusiveRefCounts::tagMask = partialDestroyStartedMask | partialDestroyFinishedMask

staticconstexprprivateinherited

Mask that will zero out all the count bits and leave the tag bits unchanged.

Definition at line 174 of file IntrusiveRefCounts.h.

valueMask

constexpr FieldType xrpl::IntrusiveRefCounts::valueMask = ~tagMask

staticconstexprprivateinherited

Mask that will zero out the tag bits and leave the count bits unchanged.

Definition at line 179 of file IntrusiveRefCounts.h.

strongMask

constexpr FieldType xrpl::IntrusiveRefCounts::strongMask = ((one << StrongCountNumBits) - 1) & valueMask

staticconstexprprivateinherited

Mask that will zero out everything except the strong count.

Definition at line 183 of file IntrusiveRefCounts.h.

weakMask

constexpr FieldType xrpl::IntrusiveRefCounts::weakMask = (((one << WeakCountNumBits) - 1) << StrongCountNumBits) & valueMask

staticconstexprprivateinherited

Mask that will zero out everything except the weak count.

Definition at line 187 of file IntrusiveRefCounts.h.