Types used by the HAMT index. More...

#include "pstore/adt/chunked_sequence.hpp"
#include "pstore/core/array_stack.hpp"
#include "pstore/core/db_archive.hpp"

Include dependency graph for hamt_map_types.hpp:

This graph shows which files directly or indirectly include this file:

Classes
struct	pstore::index::details::is_any_of< S, Types >
	Provides the member constant `value` which is equal to true, if S the same as any of the types (after removing const and/or volatile) in the Types list. More...

struct	pstore::index::details::is_any_of< S >

struct	pstore::index::details::is_any_of< S, Head, Tail... >

struct	pstore::index::header_block
	The address of an instance of this type is passed to the hamt_map ctor to load an existing index, and it is returned by a call to hamt_map::flush(). More...

struct	pstore::index::details::nchildren

union	pstore::index::details::index_pointer
	An index pointer is either a database address or a pointer to volatile RAM. More...

class	pstore::index::details::parent_type
	A class used to keep the pointer to parent node and the child slot. More...

class	pstore::index::details::linear_node
	A linear node. More...

class	pstore::index::details::internal_node
	An internal trie node. More...

Typedefs
using	pstore::index::details::hash_type = std::uint64_t

using	pstore::index::details::parent_stack = array_stack< parent_type, max_tree_depth >

Enumerations
enum	: std::uintptr_t { internal_node_bit = 1U << 0U, pstore::index::details::heap_node_bit = 1U << 1U }

Functions
template<typename T , typename = typename std::enable_if_t<std::is_unsigned<T>::value>>
constexpr unsigned	pstore::index::details::cx_pop_count (T const x) noexcept
	A function to compute the number of set bits in a value. More...

	pstore::index::details::PSTORE_STATIC_ASSERT (bit_count::pop_count(hash_size - 1)==cx_pop_count(hash_size - 1))

	pstore::index::PSTORE_STATIC_ASSERT (sizeof(header_block)==24)

	pstore::index::PSTORE_STATIC_ASSERT (offsetof(header_block, signature)==0)

	pstore::index::PSTORE_STATIC_ASSERT (offsetof(header_block, size)==8)

	pstore::index::PSTORE_STATIC_ASSERT (offsetof(header_block, root)==16)

constexpr bool	pstore::index::details::depth_is_internal_node (unsigned const shift) noexcept

Variables
constexpr auto const	pstore::index::details::hash_size = sizeof (hash_type) * 8
	The number of bits in hash_type. More...

constexpr unsigned	pstore::index::details::hash_index_bits = bit_count::pop_count (hash_size - 1)

constexpr unsigned	pstore::index::details::max_hash_bits = (hash_size + 7) / hash_index_bits * hash_index_bits

constexpr unsigned	pstore::index::details::hash_index_mask = (1U << hash_index_bits) - 1U

constexpr unsigned	pstore::index::details::max_internal_depth = max_hash_bits / hash_index_bits

constexpr unsigned	pstore::index::details::max_tree_depth = max_internal_depth + 2U
	The max depth of the hash trees include several levels internal nodes (max_internal_depth), one linear node and one leaf node. More...

constexpr std::size_t	pstore::index::details::not_found = std::numeric_limits<std::size_t>::max ()

Detailed Description

Types used by the HAMT index.

Enumeration Type Documentation

anonymous enum : std::uintptr_t

Enumerator
heap_node_bit	Using LSB for marking internal nodes.

template<typename T , typename = typename std::enable_if_t<std::is_unsigned<T>::value>>

constexpr unsigned pstore::index::details::cx_pop_count ( T const x )

noexcept

A function to compute the number of set bits in a value.

An alternative to the bit_count::pop_count() function that is normally used because some versions of that implementation may not be constexpr.

Template Parameters

T	An unsigned integer type.

Parameters

x	A value whose population count is to be returned.

constexpr auto const pstore::index::details::hash_size = sizeof (hash_type) * 8

The number of bits in hash_type.

This is the maximum number of children that an internal-node can carry.

constexpr unsigned pstore::index::details::max_tree_depth = max_internal_depth + 2U

The max depth of the hash trees include several levels internal nodes (max_internal_depth), one linear node and one leaf node.