TaggedPointer is a combination of a pointer and a mask stored in the lowest two bits. More...

Collaboration diagram for ripple::TaggedPointer:

Classes
struct	RawAllocateTag

Public Member Functions
	TaggedPointer ()=delete

	TaggedPointer (std::uint8_t numChildren)

	TaggedPointer (TaggedPointer &&other, std::uint16_t isBranch, std::uint8_t toAllocate)
	Constructor is used change the number of allocated children. More...

	TaggedPointer (TaggedPointer &&other, std::uint16_t srcBranches, std::uint16_t dstBranches, std::uint8_t toAllocate)
	Given `other` with the specified children in `srcBranches`, create a new TaggedPointer with the allocated number of children and the children specified in `dstBranches`. More...

	TaggedPointer (TaggedPointer const &)=delete

	TaggedPointer (TaggedPointer &&)

TaggedPointer &	operator= (TaggedPointer &&)

	~TaggedPointer ()

std::pair< std::uint8_t, void * >	decode () const
	Decode the tagged pointer into its tag and pointer. More...

std::uint8_t	capacity () const
	Get the number of elements allocated for each array. More...

bool	isDense () const
	Check if the arrays have a dense format. More...

std::tuple< std::uint8_t, SHAMapHash , std::shared_ptr< SHAMapTreeNode > >	getHashesAndChildren () const
	Get the number of elements in each array and a pointer to the start of each array. More...

SHAMapHash *	getHashes () const
	Get the `hashes` array. More...

std::shared_ptr< SHAMapTreeNode > *	getChildren () const
	Get the `children` array. More...

template<class F >
void	iterChildren (std::uint16_t isBranch, F &&f) const
	Call the `f` callback for all 16 (branchFactor) branches - even if the branch is empty. More...

template<class F >
void	iterNonEmptyChildIndexes (std::uint16_t isBranch, F &&f) const
	Call the `f` callback for all non-empty branches. More...

std::optional< int >	getChildIndex (std::uint16_t isBranch, int i) const
	Get the child's index inside the `hashes` or `children` array (which may or may not be sparse). More...

Private Member Functions
void	destroyHashesAndChildren ()
	Deallocate memory and run destructors. More...

	TaggedPointer (RawAllocateTag, std::uint8_t numChildren)
	This constructor allocates space for the hashes and children, but does not run constructors. More...

Private Attributes
std::uintptr_t	tp_ = 0
	Upper bits are the pointer, lowest two bits are the tag A moved-from object will have a tp_ of zero. More...

Static Private Attributes
static constexpr std::uintptr_t	tagMask = 3
	bit-and with this mask to get the tag bits (lowest two bits) More...

static constexpr std::uintptr_t	ptrMask = ~tagMask
	bit-and with this mask to get the pointer bits (mask out the tag) More...

Detailed Description

TaggedPointer is a combination of a pointer and a mask stored in the lowest two bits.

Since pointers do not have arbitrary alignment, the lowest bits in the pointer are guaranteed to be zero. TaggedPointer stores information in these low bits. When dereferencing the pointer, these low "tag" bits are set to zero. When accessing the tag bits, the high "pointer" bits are set to zero.

The "pointer" part points to to the equivalent to an array of SHAMapHash followed immediately by an array of shared_ptr<SHAMapTreeNode>. The sizes of these arrays are determined by the tag. The tag is an index into an array (boundaries, defined in the cpp file) that specifies the size. Both arrays are the same size. Note that the sizes may be smaller than the full 16 elements needed to explicitly store all the children. In this case, the arrays only store the non-empty children. The non-empty children are stored in index order. For example, if only children 2 and 14 are non-empty, a two-element array would store child 2 in array index 0 and child 14 in array index 1. There are functions to convert between a child's tree index and the child's index in a sparse array.

The motivation for this class is saving RAM. A large percentage of inner nodes only store a small number of children. Memory can be saved by storing the inner node's children in sparse arrays. Measurements show that on average a typical SHAMap's inner nodes can be stored using only 25% of the original space.

Definition at line 57 of file TaggedPointer.h.

Constructor & Destructor Documentation

◆ TaggedPointer() [1/7]

ripple::TaggedPointer::TaggedPointer	(	RawAllocateTag	,
		std::uint8_t	numChildren
	)

explicitprivate

This constructor allocates space for the hashes and children, but does not run constructors.

Parameters

RawAllocateTag	used to select overload only
numChildren	allocate space for at least this number of children (must be <= branchFactor)

Note: Since the hashes/children destructors are always run in the TaggedPointer destructor, this means those constructors must be run after this constructor is run. This constructor is private and only used in places where the hashes/children constructor are subsequently run.

◆ TaggedPointer() [2/7]

ripple::TaggedPointer::TaggedPointer ( )

delete

◆ TaggedPointer() [3/7]

ripple::TaggedPointer::TaggedPointer ( std::uint8_t numChildren )

explicit

◆ TaggedPointer() [4/7]

ripple::TaggedPointer::TaggedPointer	(	TaggedPointer &&	other,
		std::uint16_t	isBranch,
		std::uint8_t	toAllocate
	)

explicit

Constructor is used change the number of allocated children.

Existing children from other are copied (toAllocate must be >= the number of children). The motivation for making this a constructor is it saves unneeded copying and zeroing out of hashes if this were implemented directly in the SHAMapInnerNode class.

Parameters

other	children and hashes are moved from this param
isBranch	bitset of non-empty children in `other`
toAllocate	allocate space for at least this number of children (must be <= branchFactor)

◆ TaggedPointer() [5/7]

ripple::TaggedPointer::TaggedPointer	(	TaggedPointer &&	other,
		std::uint16_t	srcBranches,
		std::uint16_t	dstBranches,
		std::uint8_t	toAllocate
	)

explicit

Given other with the specified children in srcBranches, create a new TaggedPointer with the allocated number of children and the children specified in dstBranches.

Parameters

other	children and hashes are moved from this param
srcBranches	bitset of non-empty children in `other`
dstBranches	bitset of children to copy from `other` (or space to leave in a sparse array - see note below)
toAllocate	allocate space for at least this number of children (must be <= branchFactor)

Note: a child may be absent in srcBranches but present in dstBranches (if dst has a sparse representation, space for the new child will be left in the sparse array). Typically, srcBranches and dstBranches will differ by at most one bit. The function works correctly if they differ by more, but there are likely more efficient algorithms to consider if this becomes a common use-case.

◆ TaggedPointer() [6/7]

ripple::TaggedPointer::TaggedPointer ( TaggedPointer const & )

delete

◆ TaggedPointer() [7/7]

ripple::TaggedPointer::TaggedPointer ( TaggedPointer && )

◆ ~TaggedPointer()

ripple::TaggedPointer::~TaggedPointer ( )

Member Function Documentation

◆ destroyHashesAndChildren()

void ripple::TaggedPointer::destroyHashesAndChildren ( )

private

Deallocate memory and run destructors.

◆ operator=()

TaggedPointer& ripple::TaggedPointer::operator= ( TaggedPointer && )

◆ decode()

std::pair<std::uint8_t, void*> ripple::TaggedPointer::decode ( ) const

Decode the tagged pointer into its tag and pointer.

◆ capacity()

std::uint8_t ripple::TaggedPointer::capacity ( ) const

Get the number of elements allocated for each array.

◆ isDense()

bool ripple::TaggedPointer::isDense ( ) const

Check if the arrays have a dense format.

Note: The dense format is when there is an array element for all 16 (branchFactor) possible children.

◆ getHashesAndChildren()

std:: tuple<std::uint8_t, SHAMapHash*, std::shared_ptr<SHAMapTreeNode>*> ripple::TaggedPointer::getHashesAndChildren ( ) const

Get the number of elements in each array and a pointer to the start of each array.

◆ getHashes()

SHAMapHash* ripple::TaggedPointer::getHashes ( ) const

Get the hashes array.

◆ getChildren()

std::shared_ptr<SHAMapTreeNode>* ripple::TaggedPointer::getChildren ( ) const

Get the children array.

◆ iterChildren()

template<class F >

void ripple::TaggedPointer::iterChildren	(	std::uint16_t	isBranch,
		F &&	f
	)		const

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

Parameters

isBranch	bitset of non-empty children
f	a one parameter callback function. The parameter is the child's hash.

◆ iterNonEmptyChildIndexes()

template<class F >

void ripple::TaggedPointer::iterNonEmptyChildIndexes	(	std::uint16_t	isBranch,
		F &&	f
	)		const

Call the f callback for all non-empty branches.

Parameters

isBranch	bitset of non-empty children
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.

◆ getChildIndex()

std::optional<int> ripple::TaggedPointer::getChildIndex	(	std::uint16_t	isBranch,
		int	i
	)		const

Get the child's index inside the hashes or children array (which may or may not be sparse).

The optional will be empty if an empty branch is requested and the children are sparse.

Parameters

isBranch	bitset of non-empty children
i	index of the requested child

Member Data Documentation

◆ tp_

std::uintptr_t ripple::TaggedPointer::tp_ = 0

private

Upper bits are the pointer, lowest two bits are the tag A moved-from object will have a tp_ of zero.

Definition at line 65 of file TaggedPointer.h.

◆ tagMask

constexpr std::uintptr_t ripple::TaggedPointer::tagMask = 3

staticconstexprprivate

bit-and with this mask to get the tag bits (lowest two bits)

Definition at line 67 of file TaggedPointer.h.

◆ ptrMask

constexpr std::uintptr_t ripple::TaggedPointer::ptrMask = ~tagMask

staticconstexprprivate

bit-and with this mask to get the pointer bits (mask out the tag)

Definition at line 69 of file TaggedPointer.h.

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ TaggedPointer() [1/7]

◆ TaggedPointer() [2/7]

◆ TaggedPointer() [3/7]

◆ TaggedPointer() [4/7]

◆ TaggedPointer() [5/7]

◆ TaggedPointer() [6/7]

◆ TaggedPointer() [7/7]

◆ ~TaggedPointer()

Member Function Documentation

◆ destroyHashesAndChildren()

◆ operator=()

◆ decode()

◆ capacity()

◆ isDense()

◆ getHashesAndChildren()

◆ getHashes()

◆ getChildren()

◆ iterChildren()

◆ iterNonEmptyChildIndexes()

◆ getChildIndex()

Member Data Documentation

◆ tp_

◆ tagMask

◆ ptrMask