ripple::SHAMapInnerNode Class Reference

#include <SHAMapInnerNode.h>

Inheritance diagram for ripple::SHAMapInnerNode:

Collaboration diagram for ripple::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
	Flag that is set when the partialDestroy function has started running (or is about to start running).
static constexpr FieldType	partialDestroyFinishedMask
	Flag that is set when the partialDestroy function has finished running.
static constexpr FieldType	tagMask
	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
	Mask that will zero out everything except the strong count.
static constexpr FieldType	weakMask
	Mask that will zero out everything except the weak count.

Detailed Description

Definition at line 15 of file SHAMapInnerNode.h.

Member Typedef Documentation

CountType

using ripple::IntrusiveRefCounts::CountType = std::uint16_t

privateinherited

Definition at line 101 of file IntrusiveRefCounts.h.

FieldType

using ripple::IntrusiveRefCounts::FieldType = std::uint32_t

privateinherited

Definition at line 104 of file IntrusiveRefCounts.h.

Constructor & Destructor Documentation

SHAMapInnerNode() [1/2]

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

explicit

Definition at line 13 of file SHAMapInnerNode.cpp.

SHAMapInnerNode() [2/2]

ripple::SHAMapInnerNode::SHAMapInnerNode ( SHAMapInnerNode const &  )

delete

~SHAMapInnerNode()

ripple::SHAMapInnerNode::~SHAMapInnerNode ( )

default

Member Function Documentation

resizeChildArrays()

void ripple::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 48 of file SHAMapInnerNode.cpp.

getChildIndex()

std::optional< int > ripple::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 55 of file SHAMapInnerNode.cpp.

iterChildren()

template<class F >

void ripple::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 35 of file SHAMapInnerNode.cpp.

iterNonEmptyChildIndexes()

template<class F >

void ripple::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 42 of file SHAMapInnerNode.cpp.

operator=()

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

delete

partialDestructor()

void ripple::SHAMapInnerNode::partialDestructor ( )

overridevirtual

Reimplemented from ripple::SHAMapTreeNode.

Definition at line 23 of file SHAMapInnerNode.cpp.

clone()

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

overridevirtual

Make a copy of this node, setting the owner.

Implements ripple::SHAMapTreeNode.

Definition at line 61 of file SHAMapInnerNode.cpp.

getType()

SHAMapNodeType ripple::SHAMapInnerNode::getType ( ) const

overridevirtual

Determines the type of node.

Implements ripple::SHAMapTreeNode.

Definition at line 98 of file SHAMapInnerNode.h.

isLeaf()

bool ripple::SHAMapInnerNode::isLeaf ( ) const

overridevirtual

Determines if this is a leaf node.

Implements ripple::SHAMapTreeNode.

Definition at line 104 of file SHAMapInnerNode.h.

isInner()

bool ripple::SHAMapInnerNode::isInner ( ) const

overridevirtual

Determines if this is an inner node.

Implements ripple::SHAMapTreeNode.

Definition at line 110 of file SHAMapInnerNode.h.

isEmpty()

bool ripple::SHAMapInnerNode::isEmpty

(

)

const

Definition at line 176 of file SHAMapInnerNode.h.

isEmptyBranch()

bool ripple::SHAMapInnerNode::isEmptyBranch

(

int

m

)

const

Definition at line 182 of file SHAMapInnerNode.h.

getBranchCount()

int ripple::SHAMapInnerNode::getBranchCount

(

)

const

Definition at line 188 of file SHAMapInnerNode.h.

getChildHash()

SHAMapHash const & ripple::SHAMapInnerNode::getChildHash

(

int

m

)

const

Definition at line 361 of file SHAMapInnerNode.cpp.

setChild()

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

Definition at line 264 of file SHAMapInnerNode.cpp.

shareChild()

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

Definition at line 306 of file SHAMapInnerNode.cpp.

getChildPointer()

SHAMapTreeNode * ripple::SHAMapInnerNode::getChildPointer

(

int

branch

)

Definition at line 327 of file SHAMapInnerNode.cpp.

getChild()

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

(

int

branch

)

Definition at line 344 of file SHAMapInnerNode.cpp.

canonicalizeChild()

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

Definition at line 373 of file SHAMapInnerNode.cpp.

isFullBelow()

bool ripple::SHAMapInnerNode::isFullBelow

(

std::uint32_t

generation

)

const

Definition at line 194 of file SHAMapInnerNode.h.

setFullBelowGen()

void ripple::SHAMapInnerNode::setFullBelowGen

(

std::uint32_t

gen

)

Definition at line 200 of file SHAMapInnerNode.h.

updateHash()

void ripple::SHAMapInnerNode::updateHash ( )

overridevirtual

Recalculate the hash of this node.

Implements ripple::SHAMapTreeNode.

Definition at line 182 of file SHAMapInnerNode.cpp.

updateHashDeep()

void ripple::SHAMapInnerNode::updateHashDeep

(

)

Recalculate the hash of all children and this node.

Definition at line 197 of file SHAMapInnerNode.cpp.

serializeForWire()

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

overridevirtual

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

Implements ripple::SHAMapTreeNode.

Definition at line 212 of file SHAMapInnerNode.cpp.

serializeWithPrefix()

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

overridevirtual

Serialize the node in a format appropriate for hashing.

Implements ripple::SHAMapTreeNode.

Definition at line 237 of file SHAMapInnerNode.cpp.

getString()

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

overridevirtual

Reimplemented from ripple::SHAMapTreeNode.

Definition at line 249 of file SHAMapInnerNode.cpp.

invariants()

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

overridevirtual

Implements ripple::SHAMapTreeNode.

Definition at line 410 of file SHAMapInnerNode.cpp.

makeFullInner()

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

static

Definition at line 112 of file SHAMapInnerNode.cpp.

makeCompressedInner()

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

static

Definition at line 146 of file SHAMapInnerNode.cpp.

getHash()

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

inherited

Return the hash of this node.

Definition at line 125 of file SHAMapTreeNode.h.

makeFromPrefix()

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

staticinherited

Definition at line 126 of file SHAMapTreeNode.cpp.

makeFromWire()

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

staticinherited

Definition at line 94 of file SHAMapTreeNode.cpp.

makeTransaction()

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

staticprivateinherited

Definition at line 16 of file SHAMapTreeNode.cpp.

makeAccountState()

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

staticprivateinherited

Definition at line 61 of file SHAMapTreeNode.cpp.

makeTransactionWithMeta()

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

staticprivateinherited

Definition at line 32 of file SHAMapTreeNode.cpp.

addStrongRef()

void ripple::IntrusiveRefCounts::addStrongRef ( ) const

noexceptinherited

Definition at line 232 of file IntrusiveRefCounts.h.

addWeakRef()

void ripple::IntrusiveRefCounts::addWeakRef ( ) const

noexceptinherited

Definition at line 238 of file IntrusiveRefCounts.h.

releaseStrongRef()

ReleaseStrongRefAction ripple::IntrusiveRefCounts::releaseStrongRef ( ) const

inherited

Definition at line 244 of file IntrusiveRefCounts.h.

addWeakReleaseStrongRef()

ReleaseStrongRefAction ripple::IntrusiveRefCounts::addWeakReleaseStrongRef ( ) const

inherited

Definition at line 293 of file IntrusiveRefCounts.h.

releaseWeakRef()

ReleaseWeakRefAction ripple::IntrusiveRefCounts::releaseWeakRef ( ) const

inherited

Definition at line 347 of file IntrusiveRefCounts.h.

checkoutStrongRefFromWeak()

bool ripple::IntrusiveRefCounts::checkoutStrongRefFromWeak ( ) const

noexceptinherited

Definition at line 374 of file IntrusiveRefCounts.h.

expired()

bool ripple::IntrusiveRefCounts::expired ( ) const

noexceptinherited

Definition at line 392 of file IntrusiveRefCounts.h.

use_count()

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

noexceptinherited

Definition at line 399 of file IntrusiveRefCounts.h.

getCounter()

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

staticprivatenoexceptinherited

Definition at line 110 of file CountedObject.h.

Member Data Documentation

branchFactor

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

staticconstexpr

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

Definition at line 20 of file SHAMapInnerNode.h.

hashesAndChildren_

TaggedPointer ripple::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 27 of file SHAMapInnerNode.h.

fullBelowGen_

std::uint32_t ripple::SHAMapInnerNode::fullBelowGen_ = 0

private

Definition at line 29 of file SHAMapInnerNode.h.

isBranch_

std::uint16_t ripple::SHAMapInnerNode::isBranch_ = 0

private

Definition at line 30 of file SHAMapInnerNode.h.

lock_

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

mutableprivate

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

Definition at line 33 of file SHAMapInnerNode.h.

hash_

SHAMapHash ripple::SHAMapTreeNode::hash_

protectedinherited

Definition at line 34 of file SHAMapTreeNode.h.

cowid_

std::uint32_t ripple::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 42 of file SHAMapTreeNode.h.

StrongCountNumBits

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

staticconstexprprivateinherited

Definition at line 102 of file IntrusiveRefCounts.h.

WeakCountNumBits

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

staticconstexprprivateinherited

Definition at line 103 of file IntrusiveRefCounts.h.

FieldTypeBits

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

staticconstexprprivateinherited

Definition at line 105 of file IntrusiveRefCounts.h.

one

constexpr FieldType ripple::IntrusiveRefCounts::one = 1

staticconstexprprivateinherited

Definition at line 106 of file IntrusiveRefCounts.h.

refCounts

std::atomic<FieldType> ripple::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 141 of file IntrusiveRefCounts.h.

strongDelta

constexpr FieldType ripple::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 148 of file IntrusiveRefCounts.h.

weakDelta

constexpr FieldType ripple::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 155 of file IntrusiveRefCounts.h.

partialDestroyStartedMask

constexpr FieldType ripple::IntrusiveRefCounts::partialDestroyStartedMask

staticconstexprprivateinherited

Initial value:

=
        (one << (FieldTypeBits - 1))

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 163 of file IntrusiveRefCounts.h.

partialDestroyFinishedMask

constexpr FieldType ripple::IntrusiveRefCounts::partialDestroyFinishedMask

staticconstexprprivateinherited

Initial value:

=
        (one << (FieldTypeBits - 2))

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 171 of file IntrusiveRefCounts.h.

tagMask

constexpr FieldType ripple::IntrusiveRefCounts::tagMask

staticconstexprprivateinherited

Initial value:

=
        partialDestroyStartedMask | partialDestroyFinishedMask

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

Definition at line 177 of file IntrusiveRefCounts.h.

valueMask

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

staticconstexprprivateinherited

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

Definition at line 183 of file IntrusiveRefCounts.h.

strongMask

constexpr FieldType ripple::IntrusiveRefCounts::strongMask

staticconstexprprivateinherited

Initial value:

=
        ((one << StrongCountNumBits) - 1) & valueMask

Mask that will zero out everything except the strong count.

Definition at line 187 of file IntrusiveRefCounts.h.

weakMask

constexpr FieldType ripple::IntrusiveRefCounts::weakMask

staticconstexprprivateinherited

Initial value:

=
        (((one << WeakCountNumBits) - 1) << StrongCountNumBits) & valueMask

Mask that will zero out everything except the weak count.

Definition at line 192 of file IntrusiveRefCounts.h.