#include <SHAMapTreeNode.h>

Inheritance diagram for xrpl::SHAMapTreeNode:

[legend]

Collaboration diagram for xrpl::SHAMapTreeNode:

[legend]

Public Member Functions
	~SHAMapTreeNode () noexcept override=default
	SHAMapTreeNode (SHAMapTreeNode const &)=delete
SHAMapTreeNode &	operator= (SHAMapTreeNode const &)=delete
virtual void	partialDestructor ()
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.
virtual SHAMapTreeNodePtr	clone (std::uint32_t cowid) const =0
	Make a copy of this node, setting the owner.
virtual void	updateHash ()=0
	Recalculate the hash of this node.
SHAMapHash const &	getHash () const
	Return the hash of this node.
virtual SHAMapNodeType	getType () const =0
	Determines the type of node.
virtual bool	isLeaf () const =0
	Determines if this is a leaf node.
virtual bool	isInner () const =0
	Determines if this is an inner node.
virtual void	serializeForWire (Serializer &) const =0
	Serialize the node in a format appropriate for sending over the wire.
virtual void	serializeWithPrefix (Serializer &) const =0
	Serialize the node in a format appropriate for hashing.
virtual std::string	getString (SHAMapNodeID const &) const
virtual void	invariants (bool isRoot=false) const =0
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	makeFromPrefix (Slice rawNode, SHAMapHash const &hash)
static SHAMapTreeNodePtr	makeFromWire (Slice rawNode)

Protected Member Functions

	SHAMapTreeNode (std::uint32_t cowid) noexcept
	Construct a node.
	SHAMapTreeNode (std::uint32_t cowid, SHAMapHash const &hash) noexcept

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

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)

Private Attributes
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 37 of file SHAMapTreeNode.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

◆ SHAMapTreeNode() [1/3]

xrpl::SHAMapTreeNode::SHAMapTreeNode ( std::uint32_t cowid )

explicitprotectednoexcept

Construct a node.

Parameters

cowid	The identifier of a SHAMap. For more, see cowid_
hash	The hash associated with this node, if any.

Definition at line 56 of file SHAMapTreeNode.h.

◆ SHAMapTreeNode() [2/3]

xrpl::SHAMapTreeNode::SHAMapTreeNode	(	std::uint32_t	cowid,
		SHAMapHash const &	hash )

explicitprotectednoexcept

Definition at line 60 of file SHAMapTreeNode.h.

◆ ~SHAMapTreeNode()

xrpl::SHAMapTreeNode::~SHAMapTreeNode ( )

overridedefaultnoexcept

◆ SHAMapTreeNode() [3/3]

xrpl::SHAMapTreeNode::SHAMapTreeNode ( SHAMapTreeNode const & )

delete

Member Function Documentation

◆ operator=()

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

delete

◆ partialDestructor()

virtual void xrpl::SHAMapTreeNode::partialDestructor ( )

virtual

Reimplemented in xrpl::SHAMapInnerNode.

Definition at line 75 of file SHAMapTreeNode.h.

◆ updateHash()

virtual void xrpl::SHAMapTreeNode::updateHash ( )

pure virtual

Recalculate the hash of this node.

Implemented in xrpl::SHAMapAccountStateLeafNode, xrpl::SHAMapInnerNode, xrpl::SHAMapTxLeafNode, and xrpl::SHAMapTxPlusMetaLeafNode.

◆ getHash()

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

Return the hash of this node.

Definition at line 128 of file SHAMapTreeNode.h.

◆ getType()

virtual SHAMapNodeType xrpl::SHAMapTreeNode::getType ( ) const

pure virtual

Determines the type of node.

Implemented in xrpl::SHAMapAccountStateLeafNode, xrpl::SHAMapInnerNode, xrpl::SHAMapTxLeafNode, and xrpl::SHAMapTxPlusMetaLeafNode.

◆ isLeaf()

virtual bool xrpl::SHAMapTreeNode::isLeaf ( ) const

pure virtual

Determines if this is a leaf node.

Implemented in xrpl::SHAMapInnerNode, and xrpl::SHAMapLeafNode.

◆ isInner()

virtual bool xrpl::SHAMapTreeNode::isInner ( ) const

pure virtual

Determines if this is an inner node.

Implemented in xrpl::SHAMapInnerNode, and xrpl::SHAMapLeafNode.

◆ serializeForWire()

virtual void xrpl::SHAMapTreeNode::serializeForWire ( Serializer & ) const

pure virtual

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

Implemented in xrpl::SHAMapAccountStateLeafNode, xrpl::SHAMapInnerNode, xrpl::SHAMapTxLeafNode, and xrpl::SHAMapTxPlusMetaLeafNode.

◆ serializeWithPrefix()

virtual void xrpl::SHAMapTreeNode::serializeWithPrefix ( Serializer & ) const

pure virtual

Serialize the node in a format appropriate for hashing.

Implemented in xrpl::SHAMapAccountStateLeafNode, xrpl::SHAMapInnerNode, xrpl::SHAMapTxLeafNode, and xrpl::SHAMapTxPlusMetaLeafNode.

◆ getString()

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

virtual

Reimplemented in xrpl::SHAMapInnerNode, and xrpl::SHAMapLeafNode.

Definition at line 192 of file SHAMapTreeNode.cpp.

◆ invariants()

virtual void xrpl::SHAMapTreeNode::invariants ( bool isRoot = false ) const

pure virtual

Implemented in xrpl::SHAMapInnerNode, and xrpl::SHAMapLeafNode.

◆ makeFromPrefix()

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

static

Definition at line 159 of file SHAMapTreeNode.cpp.

◆ makeFromWire()

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

static

Definition at line 128 of file SHAMapTreeNode.cpp.

◆ makeTransaction()

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

staticprivate

Definition at line 29 of file SHAMapTreeNode.cpp.

◆ makeAccountState()

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

staticprivate

Definition at line 87 of file SHAMapTreeNode.cpp.

◆ makeTransactionWithMeta()

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

staticprivate

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.

Member Data Documentation

◆ hash_

SHAMapHash xrpl::SHAMapTreeNode::hash_

protected

Definition at line 40 of file SHAMapTreeNode.h.

◆ cowid_

std::uint32_t xrpl::SHAMapTreeNode::cowid_

protected

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:

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.
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.
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).
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

xrpl::IntrusiveRefCounts::kWeakCountNumBits

static constexpr size_t kWeakCountNumBits

Definition IntrusiveRefCounts.h:102

xrpl::IntrusiveRefCounts::kValueMask

static constexpr FieldType kValueMask

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

Definition IntrusiveRefCounts.h:179

xrpl::IntrusiveRefCounts::kOne

static constexpr FieldType kOne

Definition IntrusiveRefCounts.h:105

xrpl::IntrusiveRefCounts::kStrongCountNumBits

static constexpr size_t kStrongCountNumBits

Definition IntrusiveRefCounts.h:101

Mask that will zero out everything except the weak count.

Definition at line 187 of file IntrusiveRefCounts.h.

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Private Types

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ CountType

◆ FieldType

Constructor & Destructor Documentation

◆ SHAMapTreeNode() [1/3]

◆ SHAMapTreeNode() [2/3]

◆ ~SHAMapTreeNode()

◆ SHAMapTreeNode() [3/3]

Member Function Documentation

◆ operator=()

◆ partialDestructor()

◆ updateHash()

◆ getHash()

◆ getType()

◆ isLeaf()

◆ isInner()

◆ serializeForWire()

◆ serializeWithPrefix()

◆ getString()

◆ invariants()

◆ makeFromPrefix()

◆ makeFromWire()

◆ makeTransaction()

◆ makeAccountState()

◆ makeTransactionWithMeta()

◆ addStrongRef()

◆ addWeakRef()

◆ releaseStrongRef()

◆ addWeakReleaseStrongRef()

◆ releaseWeakRef()

◆ checkoutStrongRefFromWeak()

◆ expired()

◆ useCount()

Member Data Documentation

◆ hash_

◆ cowid_

◆ kStrongCountNumBits

◆ kWeakCountNumBits

◆ kFieldTypeBits

◆ kOne

◆ refCounts_

◆ kStrongDelta

◆ kWeakDelta

◆ kPartialDestroyStartedMask

◆ kPartialDestroyFinishedMask

◆ kTagMask

◆ kValueMask

◆ kStrongMask

◆ kWeakMask