pstore::index::details::internal_node Class Reference

An internal trie node. More...

#include <hamt_map_types.hpp>

Public Types
using	iterator = index_pointer *
using	const_iterator = index_pointer const *

Public Member Functions
	internal_node (index_pointer const &leaf, hash_type hash)
	Construct an internal node with a child.
	internal_node (index_pointer const &existing_leaf, index_pointer const &new_leaf, hash_type existing_hash, hash_type new_hash)
	Construct the internal node with two children. More...
	internal_node (internal_node const &rhs)
	internal_node (internal_node &&rhs)=delete
internal_node &	operator= (internal_node const &rhs)=delete
internal_node &	operator= (internal_node &&rhs)=delete
unsigned	size () const noexcept
	Returns the number of children contained by this node.
std::pair< index_pointer, std::size_t >	lookup (hash_type hash_index) const
void	insert_child (hash_type const hash, index_pointer const leaf, gsl::not_null< parent_stack *> parents)
	Insert a child into the internal node (this). More...
address	flush (transaction_base &transaction, unsigned shifts)
	Write an internal node and its children into a store.
index_pointer const &	operator[] (std::size_t const i) const
index_pointer &	operator[] (std::size_t const i)
hash_type	get_bitmap () const noexcept
void	set_bitmap (hash_type const bm) noexcept
	A function for deliberately creating illegal internal nodes in the unit test. More...
Iterators
iterator	begin () noexcept
const_iterator	begin () const
const_iterator	cbegin () const
iterator	end () noexcept
const_iterator	end () const
const_iterator	cend () const

Static Public Member Functions
template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>
static internal_node *	allocate (SequenceContainer *const container, internal_node const &other)
	Construct an internal node from existing internal-node instance. More...
template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>
static internal_node *	allocate (SequenceContainer *container, index_pointer const &leaf, hash_type const hash)
	Construct an internal node with a single child. More...
template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>
static internal_node *	allocate (SequenceContainer *container, index_pointer const &existing_leaf, index_pointer const &new_leaf, hash_type const existing_hash, hash_type const new_hash)
	Construct an internal node with two children. More...
static auto	get_node (database const &db, index_pointer node) -> std::pair< std::shared_ptr< internal_node const >, internal_node const *>
	Return a pointer to an internal node. More...
static auto	read_node (database const &db, typed_address< internal_node > addr) -> std::shared_ptr< internal_node const >
	Load an internal node from the store. More...
template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>
static internal_node *	make_writable (SequenceContainer *const container, index_pointer const node, internal_node const &internal)
	Returns a writable reference to an internal node. More...
static constexpr std::size_t	size_bytes (std::size_t const num_children) noexcept
	Returns the number of bytes occupied by an in-store internal node with the given number of child nodes. More...
static unsigned	get_new_index (hash_type const new_hash, hash_type const existing_hash) noexcept
	Return the new leaf child index number.

Detailed Description

An internal trie node.

Constructor & Destructor Documentation

internal_node()

pstore::index::details::internal_node::internal_node	(	index_pointer const &	existing_leaf,
		index_pointer const &	new_leaf,
		hash_type	existing_hash,
		hash_type	new_hash
	)

Construct the internal node with two children.

OCLINT(PH - bitwise in conditional is ok)

OCLINT(PH - bitwise in conditional is ok)

Member Function Documentation

allocate() [1/3]

template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>

static internal_node* pstore::index::details::internal_node::allocate ( SequenceContainer *const  container, internal_node const &  other  )

inlinestatic

Construct an internal node from existing internal-node instance.

This may be used, for example, when copying an in-store node into memory in preparation for modifying it.

Template Parameters

SequenceContainer

A container of internal_node instances which supports emplace_back().

Parameters

container	Points to the container which will own the new internal node instance.
other	A existing internal_node whose contents are copied into the newly allocated instance.

Returns

A new instance of internal_node which is owned by *container.

allocate() [2/3]

template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>

static internal_node* pstore::index::details::internal_node::allocate ( SequenceContainer *  container, index_pointer const &  leaf, hash_type const  hash  )

inlinestatic

Construct an internal node with a single child.

Template Parameters

SequenceContainer

A container of internal_node instances which supports emplace_back().

Parameters

container	Points to the container which will own the new internal node instance.
leaf	The child of the newly allocated internal node.
hash	The hash associated with the child node.

Returns

A new instance of internal_node which is owned by *container.

allocate() [3/3]

template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>

static internal_node* pstore::index::details::internal_node::allocate ( SequenceContainer *  container, index_pointer const &  existing_leaf, index_pointer const &  new_leaf, hash_type const  existing_hash, hash_type const  new_hash  )

inlinestatic

Construct an internal node with two children.

Template Parameters

SequenceContainer

A container of internal_node instances which supports emplace_back().

Parameters

container	Points to the container which will own the new internal node instance.
existing_leaf	One of the two child nodes of the new internal node.
new_leaf	One of the two child nodes of the new internal node.
existing_hash	The hash associated with the existing_leaf node.
new_hash	The hash associated with the new_leaf node.

Returns

A new instance of internal_node which is owned by *container.

get_node()

auto pstore::index::details::internal_node::get_node ( database const &  db, index_pointer  node  ) -> std::pair<std::shared_ptr<internal_node const>, internal_node const *>

static

Return a pointer to an internal node.

If the node is in-store, it is loaded and the internal heap node pointer if node is a heap internal node. Otherwise return the pointer which is pointed to the store node.

Parameters

db	The database containing the node.
node	The node's location: either in-store or in-heap.

Returns

A pair of which the first element is a in-store pointer to the node body. This may be null if called on a heap-resident node. The second element is the raw node pointer, that is, the address of a heap node or the result of calling .get() on the store-pointer.

insert_child()

void pstore::index::details::internal_node::insert_child	(	hash_type const	hash,
		index_pointer const	leaf,
		gsl::not_null< parent_stack *>	parents
	)

Insert a child into the internal node (this).

OCLINT(PH - bitwise in conditional)

lookup()

auto pstore::index::details::internal_node::lookup ( hash_type  hash_index ) const

inline

OCLINT(PH - bitwise in conditional is ok)

make_writable()

template<typename SequenceContainer , typename = typename std::enable_if<std::is_same< typename SequenceContainer::value_type, internal_node>::value>::type>

static internal_node* pstore::index::details::internal_node::make_writable ( SequenceContainer *const  container, index_pointer const  node, internal_node const &  internal  )

inlinestatic

Returns a writable reference to an internal node.

If the node parameter references an in-heap node, then this pointer is returned otherwise a copy of the internal parameter is placed in heap-allocated memory.

Note

It is expected that both node and internal are references to the same node.

Template Parameters

SequenceContainer

A container of internal_node instances which supports emplace_back().

Parameters

container	Points to the container which will own the new internal node instance.
node	A reference to an internal node. This may be either in-store on the heap. If on the heap the returned value is the underlying pointer.
internal	A read-only instance of an internal node. If the node parameter is in-store then a copy of this value is placed on the heap.

Returns

See above.

read_node()

auto pstore::index::details::internal_node::read_node ( database const &  db, typed_address< internal_node >  addr  ) -> std::shared_ptr<internal_node const>

static

Load an internal node from the store.

Sadly, loading an internal_node needs to done in three stages:

1. Load the basic structure
2. Calculate the actual size of the child pointer array
3. Load the complete structure along with its child pointer array

set_bitmap()

void pstore::index::details::internal_node::set_bitmap ( hash_type const  bm )

inlinenoexcept

A function for deliberately creating illegal internal nodes in the unit test.

DO NOT USE except for that purpose!

size_bytes()

static constexpr std::size_t pstore::index::details::internal_node::size_bytes ( std::size_t const  num_children )

inlinestaticnoexcept

Returns the number of bytes occupied by an in-store internal node with the given number of child nodes.

Note that the storage occupied by an in-heap internal node with the same number of children may be greater.

Parameters

num_children

The number of children to assume for the purpose of computing the number of bytes occupied.

Returns

The number of bytes occupied by an in-store internal node with the given number of child nodes.

---

The documentation for this class was generated from the following files:

• include/pstore/core/hamt_map_types.hpp
• lib/core/hamt_map_types.cpp