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 () override
void	partialDestructor () override
SHAMapTreeNodePtr	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, SHAMapTreeNodePtr child)
void	shareChild (int m, SHAMapTreeNodePtr const &child)
SHAMapTreeNode *	getChildPointer (int branch)
SHAMapTreeNodePtr	getChild (int branch)
SHAMapTreeNodePtr	canonicalizeChild (int branch, SHAMapTreeNodePtr 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 isRoot=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	useCount () const noexcept

Static Public Member Functions
static SHAMapTreeNodePtr	makeFullInner (Slice data, SHAMapHash const &hash, bool hashValid)
static SHAMapTreeNodePtr	makeCompressedInner (Slice data)
static SHAMapTreeNodePtr	makeFromPrefix (Slice rawNode, SHAMapHash const &hash)
static SHAMapTreeNodePtr	makeFromWire (Slice rawNode)

Public Attributes
friend	Object

Static Public Attributes
static constexpr unsigned int	kBranchFactor = 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 SHAMapTreeNodePtr	makeTransaction (Slice data, SHAMapHash const &hash, bool hashValid)
static SHAMapTreeNodePtr	makeAccountState (Slice data, SHAMapHash const &hash, bool hashValid)
static SHAMapTreeNodePtr	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_ {kStrongDelta}
	refCounts consists of four fields that are treated atomically:

Static Private Attributes
static constexpr size_t	kStrongCountNumBits = sizeof(CountType) * 8
static constexpr size_t	kWeakCountNumBits = kStrongCountNumBits - 2
static constexpr size_t	kFieldTypeBits = sizeof(FieldType) * 8
static constexpr FieldType	kOne = 1
static constexpr FieldType	kStrongDelta = 1
	Amount to change the strong count when adding or releasing a reference.
static constexpr FieldType	kWeakDelta = (kOne << kStrongCountNumBits)
	Amount to change the weak count when adding or releasing a reference.
static constexpr FieldType	kPartialDestroyStartedMask = (kOne << (kFieldTypeBits - 1))
	Flag that is set when the partialDestroy function has started running (or is about to start running).
static constexpr FieldType	kPartialDestroyFinishedMask = (kOne << (kFieldTypeBits - 2))
	Flag that is set when the partialDestroy function has finished running.
static constexpr FieldType	kTagMask = kPartialDestroyStartedMask | kPartialDestroyFinishedMask
	Mask that will zero out all the count bits and leave the tag bits unchanged.
static constexpr FieldType	kValueMask = ~kTagMask
	Mask that will zero out the tag bits and leave the count bits unchanged.
static constexpr FieldType	kStrongMask = ((kOne << kStrongCountNumBits) - 1) & kValueMask
	Mask that will zero out everything except the strong count.
static constexpr FieldType	kWeakMask
	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 30 of file SHAMapInnerNode.cpp.

SHAMapInnerNode() [2/2]

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

delete

~SHAMapInnerNode()

xrpl::SHAMapInnerNode::~SHAMapInnerNode ( )

overridedefault

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 61 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 67 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 48 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 55 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 38 of file SHAMapInnerNode.cpp.

clone()

SHAMapTreeNodePtr xrpl::SHAMapInnerNode::clone ( std::uint32_t cowid ) const

overridevirtual

Make a copy of this node, setting the owner.

Implements xrpl::SHAMapTreeNode.

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

setChild()

void xrpl::SHAMapInnerNode::setChild	(	int	m,
		SHAMapTreeNodePtr	child )

Definition at line 270 of file SHAMapInnerNode.cpp.

shareChild()

void xrpl::SHAMapInnerNode::shareChild	(	int	m,
		SHAMapTreeNodePtr const &	child )

Definition at line 312 of file SHAMapInnerNode.cpp.

getChildPointer()

SHAMapTreeNode * xrpl::SHAMapInnerNode::getChildPointer

(

int

branch

)

Definition at line 326 of file SHAMapInnerNode.cpp.

getChild()

SHAMapTreeNodePtr xrpl::SHAMapInnerNode::getChild

(

int

branch

)

Definition at line 343 of file SHAMapInnerNode.cpp.

canonicalizeChild()

SHAMapTreeNodePtr xrpl::SHAMapInnerNode::canonicalizeChild	(	int	branch,
		SHAMapTreeNodePtr	node )

Definition at line 371 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 194 of file SHAMapInnerNode.cpp.

updateHashDeep()

void xrpl::SHAMapInnerNode::updateHashDeep

(

)

Recalculate the hash of all children and this node.

Definition at line 209 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 223 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 246 of file SHAMapInnerNode.cpp.

getString()

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

overridevirtual

Reimplemented from xrpl::SHAMapTreeNode.

Definition at line 255 of file SHAMapInnerNode.cpp.

invariants()

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

overridevirtual

Implements xrpl::SHAMapTreeNode.

Definition at line 405 of file SHAMapInnerNode.cpp.

makeFullInner()

SHAMapTreeNodePtr xrpl::SHAMapInnerNode::makeFullInner ( Slice data, SHAMapHash const & hash, bool hashValid )

static

Definition at line 124 of file SHAMapInnerNode.cpp.

makeCompressedInner()

SHAMapTreeNodePtr xrpl::SHAMapInnerNode::makeCompressedInner ( Slice data )

static

Definition at line 159 of file SHAMapInnerNode.cpp.

getHash()

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

inherited

Return the hash of this node.

Definition at line 128 of file SHAMapTreeNode.h.

makeFromPrefix()

SHAMapTreeNodePtr xrpl::SHAMapTreeNode::makeFromPrefix ( Slice rawNode, SHAMapHash const & hash )

staticinherited

Definition at line 159 of file SHAMapTreeNode.cpp.

makeFromWire()

SHAMapTreeNodePtr xrpl::SHAMapTreeNode::makeFromWire ( Slice rawNode )

staticinherited

Definition at line 128 of file SHAMapTreeNode.cpp.

makeTransaction()

SHAMapTreeNodePtr xrpl::SHAMapTreeNode::makeTransaction ( Slice data, SHAMapHash const & hash, bool hashValid )

staticprivateinherited

Definition at line 29 of file SHAMapTreeNode.cpp.

makeAccountState()

SHAMapTreeNodePtr xrpl::SHAMapTreeNode::makeAccountState ( Slice data, SHAMapHash const & hash, bool hashValid )

staticprivateinherited

Definition at line 87 of file SHAMapTreeNode.cpp.

makeTransactionWithMeta()

SHAMapTreeNodePtr xrpl::SHAMapTreeNode::makeTransactionWithMeta ( Slice data, SHAMapHash const & hash, bool hashValid )

staticprivateinherited

Definition at line 47 of file SHAMapTreeNode.cpp.

addStrongRef()

void xrpl::IntrusiveRefCounts::addStrongRef ( ) const

noexceptinherited

Definition at line 227 of file IntrusiveRefCounts.h.

addWeakRef()

void xrpl::IntrusiveRefCounts::addWeakRef ( ) const

noexceptinherited

Definition at line 233 of file IntrusiveRefCounts.h.

releaseStrongRef()

ReleaseStrongRefAction xrpl::IntrusiveRefCounts::releaseStrongRef ( ) const

inherited

Definition at line 239 of file IntrusiveRefCounts.h.

addWeakReleaseStrongRef()

ReleaseStrongRefAction xrpl::IntrusiveRefCounts::addWeakReleaseStrongRef ( ) const

inherited

Definition at line 287 of file IntrusiveRefCounts.h.

releaseWeakRef()

ReleaseWeakRefAction xrpl::IntrusiveRefCounts::releaseWeakRef ( ) const

inherited

Definition at line 340 of file IntrusiveRefCounts.h.

checkoutStrongRefFromWeak()

bool xrpl::IntrusiveRefCounts::checkoutStrongRefFromWeak ( ) const

noexceptinherited

Definition at line 367 of file IntrusiveRefCounts.h.

expired()

bool xrpl::IntrusiveRefCounts::expired ( ) const

noexceptinherited

Definition at line 384 of file IntrusiveRefCounts.h.

useCount()

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

noexceptinherited

Definition at line 391 of file IntrusiveRefCounts.h.

getCounter()

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

staticprivatenoexceptinherited

Definition at line 109 of file CountedObject.h.

Member Data Documentation

kBranchFactor

unsigned int xrpl::SHAMapInnerNode::kBranchFactor = 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 40 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 48 of file SHAMapTreeNode.h.

kStrongCountNumBits

size_t xrpl::IntrusiveRefCounts::kStrongCountNumBits = sizeof(CountType) * 8

staticconstexprprivateinherited

Definition at line 101 of file IntrusiveRefCounts.h.

kWeakCountNumBits

size_t xrpl::IntrusiveRefCounts::kWeakCountNumBits = kStrongCountNumBits - 2

staticconstexprprivateinherited

Definition at line 102 of file IntrusiveRefCounts.h.

kFieldTypeBits

size_t xrpl::IntrusiveRefCounts::kFieldTypeBits = sizeof(FieldType) * 8

staticconstexprprivateinherited

Definition at line 104 of file IntrusiveRefCounts.h.

kOne

FieldType xrpl::IntrusiveRefCounts::kOne = 1

staticconstexprprivateinherited

Definition at line 105 of file IntrusiveRefCounts.h.

refCounts_

std::atomic<FieldType> xrpl::IntrusiveRefCounts::refCounts_ {kStrongDelta}

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.

kStrongDelta

FieldType xrpl::IntrusiveRefCounts::kStrongDelta = 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.

kWeakDelta

FieldType xrpl::IntrusiveRefCounts::kWeakDelta = (kOne << kStrongCountNumBits)

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.

kPartialDestroyStartedMask

FieldType xrpl::IntrusiveRefCounts::kPartialDestroyStartedMask = (kOne << (kFieldTypeBits - 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.

kPartialDestroyFinishedMask

FieldType xrpl::IntrusiveRefCounts::kPartialDestroyFinishedMask = (kOne << (kFieldTypeBits - 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.

kTagMask

FieldType xrpl::IntrusiveRefCounts::kTagMask = kPartialDestroyStartedMask | kPartialDestroyFinishedMask

staticconstexprprivateinherited

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

Definition at line 174 of file IntrusiveRefCounts.h.

kValueMask

FieldType xrpl::IntrusiveRefCounts::kValueMask = ~kTagMask

staticconstexprprivateinherited

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

Definition at line 179 of file IntrusiveRefCounts.h.

kStrongMask

FieldType xrpl::IntrusiveRefCounts::kStrongMask = ((kOne << kStrongCountNumBits) - 1) & kValueMask

staticconstexprprivateinherited

Mask that will zero out everything except the strong count.

Definition at line 183 of file IntrusiveRefCounts.h.

kWeakMask

FieldType xrpl::IntrusiveRefCounts::kWeakMask

staticconstexprprivateinherited

Initial value:

                                 =
(((kOne << kWeakCountNumBits) - 1) << kStrongCountNumBits) & kValueMask

Mask that will zero out everything except the weak count.

Definition at line 187 of file IntrusiveRefCounts.h.

Object

friend xrpl::CountedObject< SHAMapInnerNode >::SHAMapInnerNode

inherited

Definition at line 134 of file CountedObject.h.