paulhuggett/pstore2/hamt__map__types_8hpp_source.html

 //===- include/pstore/core/hamt_map_types.hpp -------------*- mode: C++ -*-===//
 //*  _                     _                             _                          *
 //* | |__   __ _ _ __ ___ | |_   _ __ ___   __ _ _ __   | |_ _   _ _ __   ___  ___  *
 //* | '_ \ / _` | '_ ` _ \| __| | '_ ` _ \ / _` | '_ \  | __| | | | '_ \ / _ \/ __| *
 //* | | | | (_| | | | | | | |_  | | | | | | (_| | |_) | | |_| |_| | |_) |  __/\__ \ *
 //* |_| |_|\__,_|_| |_| |_|\__| |_| |_| |_|\__,_| .__/   \__|\__, | .__/ \___||___/ *
 //*                                             |_|          |___/|_|               *
 //===----------------------------------------------------------------------===//
 //
 // Part of the pstore project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://github.com/SNSystems/pstore/blob/master/LICENSE.txt for license
 // information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//

 #ifndef PSTORE_CORE_HAMT_MAP_TYPES_HPP
 #define PSTORE_CORE_HAMT_MAP_TYPES_HPP

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

 namespace pstore {
     class transaction_base;

     namespace index {
         namespace details {

             using hash_type = std::uint64_t;

             constexpr auto const hash_size = sizeof (hash_type) * 8;

             // TODO: Visual Studio won't allow pop_count to be constexpr. This forces us to have a
             // second implementation that doesn't use the intrinsic.

             template <typename T, typename = typename std::enable_if_t<std::is_unsigned<T>::value>>
             constexpr unsigned cx_pop_count (T const x) noexcept {
                 return x == 0U ? 0U : (x & 1U) + cx_pop_count (x >> 1U);
             }

 #ifdef _MSC_VER
             constexpr unsigned hash_index_bits = cx_pop_count (hash_size - 1);
 #else
             constexpr unsigned hash_index_bits = bit_count::pop_count (hash_size - 1);
             PSTORE_STATIC_ASSERT (bit_count::pop_count (hash_size - 1) ==
                                   cx_pop_count (hash_size - 1));
 #endif

             constexpr unsigned max_hash_bits = (hash_size + 7) / hash_index_bits * hash_index_bits;
             constexpr unsigned hash_index_mask = (1U << hash_index_bits) - 1U;
             constexpr unsigned max_internal_depth = max_hash_bits / hash_index_bits;

             constexpr unsigned max_tree_depth = max_internal_depth + 2U;

             enum : std::uintptr_t {
                 internal_node_bit = 1U << 0U,
                 heap_node_bit = 1U << 1U,
             };

             template <typename S, typename... Types>
             struct is_any_of;
             template <typename S>
             struct is_any_of<S> : std::integral_constant<bool, false> {};
             template <typename S, typename Head, typename... Tail>
             struct is_any_of<S, Head, Tail...>
                     : std::integral_constant<
                           bool, std::is_same<std::remove_cv_t<S>, std::remove_cv_t<Head>>::value ||
                                     is_any_of<S, Tail...>::value> {};

         } // end namespace details

         //*  _                _           _    _         _    *
         //* | |_  ___ __ _ __| |___ _ _  | |__| |___  __| |__ *
         //* | ' \/ -_) _` / _` / -_) '_| | '_ \ / _ \/ _| / / *
         //* |_||_\___\__,_\__,_\___|_|   |_.__/_\___/\__|_\_\ *
         //*                                                   *
         struct header_block {
             std::array<std::uint8_t, 8> signature;
             std::uint64_t size;
             address root;
         };

         PSTORE_STATIC_ASSERT (sizeof (header_block) == 24);
         PSTORE_STATIC_ASSERT (offsetof (header_block, signature) == 0);
         PSTORE_STATIC_ASSERT (offsetof (header_block, size) == 8);
         PSTORE_STATIC_ASSERT (offsetof (header_block, root) == 16);

         namespace details {

             constexpr std::size_t not_found = std::numeric_limits<std::size_t>::max ();

             class internal_node;
             class linear_node;

             constexpr bool depth_is_internal_node (unsigned const shift) noexcept {
                 return shift < details::max_hash_bits;
             }

             struct nchildren {
                 std::size_t n;
             };

             //*  _         _                     _     _            *
             //* (_)_ _  __| |_____ __  _ __  ___(_)_ _| |_ ___ _ _  *
             //* | | ' \/ _` / -_) \ / | '_ \/ _ \ | ' \  _/ -_) '_| *
             //* |_|_||_\__,_\___/_\_\ | .__/\___/_|_||_\__\___|_|   *
             //*                       |_|                           *
             union index_pointer {
                 index_pointer () noexcept
                         : internal_{nullptr} {

                     // A belt-and-braces runtime check for cases where pop_count() can't be
                     // constexpr.
                     assert (hash_index_bits == bit_count::pop_count (hash_size - 1));

                     PSTORE_STATIC_ASSERT (sizeof (index_pointer) == 8);
                     PSTORE_STATIC_ASSERT (alignof (index_pointer) == 8);
                     PSTORE_STATIC_ASSERT (offsetof (index_pointer, addr_) == 0);
                     PSTORE_STATIC_ASSERT (sizeof (internal_) == sizeof (addr_));
                     PSTORE_STATIC_ASSERT (offsetof (index_pointer, internal_) == 0);
                     PSTORE_STATIC_ASSERT (sizeof (linear_) == sizeof (addr_));
                     PSTORE_STATIC_ASSERT (offsetof (index_pointer, linear_) == 0);
                 }
                 constexpr explicit index_pointer (address const a) noexcept
                         : addr_{a} {}
                 constexpr explicit index_pointer (typed_address<internal_node> const a) noexcept
                         : addr_{a.to_address ()} {}
                 constexpr explicit index_pointer (typed_address<linear_node> const a) noexcept
                         : addr_{a.to_address ()} {}
                 explicit index_pointer (internal_node * const p) noexcept
                         : internal_{tag (p)} {}
                 explicit index_pointer (linear_node * const p) noexcept
                         : linear_{tag (p)} {}
                 index_pointer (index_pointer const &) noexcept = default;
                 index_pointer (index_pointer &&) noexcept = default;

                 index_pointer & operator= (index_pointer const &) = default;
                 index_pointer & operator= (index_pointer &&) noexcept = default;
                 index_pointer & operator= (address const & a) noexcept {
                     addr_ = a;
                     return *this;
                 }
                 index_pointer & operator= (typed_address<internal_node> const & a) noexcept {
                     addr_ = a.to_address ();
                     return *this;
                 }
                 index_pointer & operator= (typed_address<linear_node> const & a) noexcept {
                     addr_ = a.to_address ();
                     return *this;
                 }
                 index_pointer & operator= (internal_node * const p) noexcept {
                     internal_ = tag (p);
                     return *this;
                 }
                 index_pointer & operator= (linear_node * const l) noexcept {
                     linear_ = tag (l);
                     return *this;
                 }

                 constexpr bool operator== (index_pointer const & other) const noexcept {
                     return addr_ == other.addr_;
                 }
                 constexpr bool operator!= (index_pointer const & other) const noexcept {
                     return !operator== (other);
                 }

                 constexpr explicit operator bool () const noexcept { return !this->is_empty (); }

                 void clear () noexcept { internal_ = nullptr; }

                 bool is_internal () const noexcept {
                     return (reinterpret_cast<std::uintptr_t> (internal_) & internal_node_bit) != 0;
                 }

                 bool is_linear () const noexcept { return is_internal (); }

                 bool is_leaf () const noexcept { return !is_internal (); }

                 bool is_heap () const noexcept {
                     return (reinterpret_cast<std::uintptr_t> (internal_) & heap_node_bit) != 0U;
                 }

                 bool is_address () const noexcept { return !is_heap (); }

                 constexpr bool is_empty () const noexcept { return internal_ == nullptr; }

                 address to_address () const noexcept {
                     assert (is_address ());
                     return addr_;
                 }

                 template <typename T, typename = typename std::enable_if_t<
                                           is_any_of<T, internal_node, linear_node>::value>>
                 typed_address<T> untag_address () const noexcept {
                     return typed_address<T>::make (to_address ().absolute () & ~internal_node_bit);
                 }

                 template <typename Ptr, typename = typename std::enable_if_t<is_any_of<
                                             typename std::pointer_traits<Ptr>::element_type,
                                             internal_node, linear_node>::value>>
                 Ptr untag () const noexcept {
                     return reinterpret_cast<Ptr> (reinterpret_cast<std::uintptr_t> (internal_) &
                                                   ~internal_node_bit & ~heap_node_bit);
                 }

             private:
                 template <typename Ptr, typename = typename std::enable_if_t<is_any_of<
                                             typename std::pointer_traits<Ptr>::element_type,
                                             internal_node, linear_node>::value>>
                 static Ptr tag (Ptr t) noexcept {
                     return reinterpret_cast<Ptr> (reinterpret_cast<std::uintptr_t> (t) |
                                                   internal_node_bit | heap_node_bit);
                 }
                 address addr_;
                 internal_node * internal_;
                 linear_node * linear_;
             };

             //*                         _     _                   *
             //*  _ __  __ _ _ _ ___ _ _| |_  | |_ _  _ _ __  ___  *
             //* | '_ \/ _` | '_/ -_) ' \  _| |  _| || | '_ \/ -_) *
             //* | .__/\__,_|_| \___|_||_\__|  \__|\_, | .__/\___| *
             //* |_|                               |__/|_|         *
             class parent_type {
             public:
                 parent_type () noexcept = default;

                 explicit parent_type (index_pointer const idx,
                                       std::size_t const pos = not_found) noexcept
                         : node (idx)
                         , position (pos) {}

                 bool operator== (parent_type const & other) const {
                     return position == other.position && node == other.node;
                 }
                 bool operator!= (parent_type const & other) const { return !operator== (other); }

                 index_pointer node;
                 std::size_t position = 0;
             };

             using parent_stack = array_stack<parent_type, max_tree_depth>;


             //*  _ _                                  _      *
             //* | (_)_ _  ___ __ _ _ _   _ _  ___  __| |___  *
             //* | | | ' \/ -_) _` | '_| | ' \/ _ \/ _` / -_) *
             //* |_|_|_||_\___\__,_|_|   |_||_\___/\__,_\___| *
             //*                                              *
             class linear_node {
             public:
                 using iterator = address *;
                 using const_iterator = address const *;

                 void * operator new (std::size_t) = delete;
                 void operator delete (void * p);

                 linear_node (linear_node && rhs) noexcept = delete;

                 ~linear_node () noexcept = default;
                 linear_node & operator= (linear_node const & rhs) = delete;
                 linear_node & operator= (linear_node && rhs) noexcept = delete;


                 static std::unique_ptr<linear_node> allocate_from (linear_node const & orig_node,
                                                                    std::size_t extra_children);

                 static std::unique_ptr<linear_node> allocate_from (database const & db,
                                                                    index_pointer const node,
                                                                    std::size_t extra_children);

                 static std::unique_ptr<linear_node> allocate (address a, address b);

                 static auto get_node (database const & db, index_pointer const node)
                     -> std::pair<std::shared_ptr<linear_node const>, linear_node const *>;

                 address operator[] (std::size_t const i) const noexcept {
                     PSTORE_ASSERT (i < size_);
                     return leaves_[i];
                 }
                 address & operator[] (std::size_t const i) noexcept {
                     PSTORE_ASSERT (i < size_);
                     return leaves_[i];
                 }


                 iterator begin () { return leaves_; }
                 const_iterator begin () const { return leaves_; }
                 const_iterator cbegin () const { return this->begin (); }

                 iterator end () { return leaves_ + size_; }
                 const_iterator end () const { return leaves_ + size_; }
                 const_iterator cend () const { return this->end (); }


                 bool empty () const { return size_ == 0; }
                 std::size_t size () const { return size_; }


                 std::size_t size_bytes () const { return linear_node::size_bytes (this->size ()); }

                 static constexpr std::size_t size_bytes (std::uint64_t const size) {
                     return sizeof (linear_node) - sizeof (linear_node::leaves_) +
                            sizeof (linear_node::leaves_[0]) * size;
                 }

                 address flush (transaction_base & transaction) const;


                 template <typename KeyType, typename OtherKeyType, typename KeyEqual,
                           typename = typename std::enable_if<
                               serialize::is_compatible<KeyType, OtherKeyType>::value>::type>
                 auto lookup (database const & db, OtherKeyType const & key, KeyEqual equal) const
                     -> std::pair<index_pointer const, std::size_t>;

             private:
                 using signature_type = std::array<std::uint8_t, 8>;
                 static signature_type const node_signature_;

                 void * operator new (std::size_t s, nchildren size);
                 // Non-allocating placement allocation functions.
                 void * operator new (std::size_t const size, void * const ptr) noexcept {
                     return ::operator new (size, ptr);
                 }

                 void operator delete (void * p, nchildren size);
                 void operator delete (void * const p, void * const ptr) noexcept {
                     ::operator delete (p, ptr);
                 }

                 explicit linear_node (std::size_t size);
                 linear_node (linear_node const & rhs);

                 static std::unique_ptr<linear_node> allocate (std::size_t num_children,
                                                               linear_node const & from_node);

                 signature_type signature_ = node_signature_;
                 std::uint64_t size_;
                 address leaves_[1];
             };

             // lookup
             // ~~~~~~
             template <typename KeyType, typename OtherKeyType, typename KeyEqual, typename>
             auto linear_node::lookup (database const & db, OtherKeyType const & key,
                                       KeyEqual equal) const
                 -> std::pair<index_pointer const, std::size_t> {
                 // Linear search. TODO: perhaps we should sort the nodes and use a binary
                 // search? This would require a template compare method.
                 std::size_t cnum = 0;
                 for (auto const & child : *this) {
                     KeyType const existing_key =
                         serialize::read<KeyType> (serialize::archive::database_reader{db, child});
                     if (equal (existing_key, key)) {
                         return {index_pointer{child}, cnum};
                     }
                     ++cnum;
                 }
                 // Not found
                 return {index_pointer (), details::not_found};
             }


             //*  _     _                     _                _      *
             //* (_)_ _| |_ ___ _ _ _ _  __ _| |  ___  ___  __| |___  *
             //* | | ' \  _/ -_) '_| ' \/ _` | | |   \/ _ \/ _` / -_) *
             //* |_|_||_\__\___|_| |_||_\__,_|_| |_|\_\___/\__,_\___| *
             //*                                                      *
             class internal_node {
             public:
                 using iterator = index_pointer *;
                 using const_iterator = index_pointer const *;

                 internal_node (index_pointer const & leaf, hash_type hash);
                 internal_node (index_pointer const & existing_leaf, index_pointer const & new_leaf,
                                hash_type existing_hash, hash_type new_hash);

                 internal_node (internal_node const & rhs);
                 internal_node (internal_node && rhs) = delete;

                 ~internal_node () noexcept = default;

                 internal_node & operator= (internal_node const & rhs) = delete;
                 internal_node & operator= (internal_node && rhs) = delete;

                 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) {
                     container->emplace_back (other);
                     // TODO: in C++17 we can use the emplace_back return value.
                     return &container->back ();
                 }

                 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) {
                     container->emplace_back (leaf, hash);
                     // TODO: in C++17 we can use the emplace_back return value.
                     return &container->back ();
                 }

                 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) {
                     container->emplace_back (existing_leaf, new_leaf, existing_hash, new_hash);
                     // TODO: in C++17 we can use the emplace_back return value.
                     return &container->back ();
                 }

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

                 static auto read_node (database const & db, typed_address<internal_node> addr)
                     -> std::shared_ptr<internal_node const>;

                 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) {
                     if (node.is_heap ()) {
                         auto * const inode = node.untag<internal_node *> ();
                         PSTORE_ASSERT (inode->signature_ == node_signature_);
                         return inode;
                     }

                     return allocate (container, internal);
                 }

                 static constexpr std::size_t size_bytes (std::size_t const num_children) noexcept {
                     PSTORE_ASSERT (num_children > 0 && num_children <= hash_size);
                     return sizeof (internal_node) - sizeof (internal_node::children_) +
                            sizeof (decltype (internal_node::children_[0])) * num_children;
                 }

                 unsigned size () const noexcept {
                     PSTORE_ASSERT (this->bitmap_ != hash_type{0});
                     return bit_count::pop_count (this->bitmap_);
                 }

                 static unsigned get_new_index (hash_type const new_hash,
                                                hash_type const existing_hash) noexcept {
                     return static_cast<unsigned> (new_hash >= existing_hash);
                 }

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

                 address flush (transaction_base & transaction, unsigned shifts);


                 index_pointer const & operator[] (std::size_t const i) const {
                     PSTORE_ASSERT (i < size ());
                     return children_[i];
                 }

                 index_pointer & operator[] (std::size_t const i) {
                     PSTORE_ASSERT (i < size ());
                     return children_[i];
                 }

                 hash_type get_bitmap () const noexcept { return bitmap_; }
                 void set_bitmap (hash_type const bm) noexcept { bitmap_ = bm; }


                 iterator begin () noexcept { return &children_[0]; }
                 const_iterator begin () const { return &children_[0]; }
                 const_iterator cbegin () const { return &children_[0]; }

                 iterator end () noexcept { return this->begin () + this->size (); }
                 const_iterator end () const { return this->begin () + this->size (); }
                 const_iterator cend () const { return this->cbegin () + this->size (); }

             private:
                 static bool validate_after_load (internal_node const & internal,
                                                  typed_address<internal_node> const addr);

                 address store_node (transaction_base & transaction) const;

                 using signature_type = std::array<std::uint8_t, 8>;
                 static signature_type const node_signature_;

                 signature_type signature_ = node_signature_;

                 hash_type bitmap_ = 0;

                 index_pointer children_[1U];
             };

             // lookup
             // ~~~~~~
             inline auto internal_node::lookup (hash_type const hash_index) const
                 -> std::pair<index_pointer, std::size_t> {
                 PSTORE_ASSERT (hash_index < (hash_type{1} << hash_index_bits));
                 auto const bit_pos = hash_type{1} << hash_index;
                 if ((bitmap_ & bit_pos) != 0) {
                     std::size_t const index = bit_count::pop_count (bitmap_ & (bit_pos - 1U));
                     return {children_[index], index};
                 }
                 return {index_pointer{}, not_found};
             }


         } // namespace details
     }     // namespace index
 } // namespace pstore

 #endif // PSTORE_CORE_HAMT_MAP_TYPES_HPP
db_archive.hpp
Provides the database_reader and database_writer class which enable the serializer to read and write ...

pstore::index::details::linear_node::size_bytes
std::size_t size_bytes() const
Returns the number of bytes of storage required for the node.
Definition: hamt_map_types.hpp:406

pstore::index::details::linear_node::size_bytes
static constexpr std::size_t size_bytes(std::uint64_t const size)
Returns the number of bytes of storage required for a linear node with &#39;size&#39; children.
Definition: hamt_map_types.hpp:410

pstore::index::details::heap_node_bit
Using LSB for marking internal nodes.
Definition: hamt_map_types.hpp:71

pstore::serialize::archive::database_reader
An archive-reader which reads data from a database.
Definition: db_archive.hpp:102

pstore::index::details::index_pointer::is_internal
bool is_internal() const noexcept
Returns true if the index_pointer is pointing to an internal node, false otherwise.
Definition: hamt_map_types.hpp:198

pstore::address
Definition: address.hpp:81

pstore::index::details::is_any_of
Provides the member constant value which is equal to true, if S the same as any of the types (after r...
Definition: hamt_map_types.hpp:78

pstore::index::details::nchildren
Definition: hamt_map_types.hpp:120

pstore::index::details::parent_type::parent_type
parent_type(index_pointer const idx, std::size_t const pos=not_found) noexcept
Constructs a parent type object.
Definition: hamt_map_types.hpp:273

pstore::index::details::linear_node::empty
bool empty() const
Checks whether the container is empty.
Definition: hamt_map_types.hpp:397

pstore::begin
transaction< transaction_lock > begin(database &db, transaction_lock &lock)
Creates a new transaction. Every operation performed on a transaction instance can be potentially und...
Definition: transaction.hpp:311

pstore::utf::index
auto index(gsl::czstring str, std::size_t pos) -> gsl::czstring
Returns a pointer to the beginning of the pos&#39;th UTF-8 codepoint in the buffer at str or nullptr if e...
Definition: utf.cpp:49

pstore::index::details::linear_node
A linear node.
Definition: hamt_map_types.hpp:298

pstore::index::details::cx_pop_count
constexpr unsigned cx_pop_count(T const x) noexcept
A function to compute the number of set bits in a value.
Definition: hamt_map_types.hpp:49

pstore::index::details::internal_node::size_bytes
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 node...
Definition: hamt_map_types.hpp:646

pstore::index::details::parent_type
A class used to keep the pointer to parent node and the child slot.
Definition: hamt_map_types.hpp:264

pstore::index::details::index_pointer::is_empty
constexpr bool is_empty() const noexcept
Returns true if the pointer is equivalent to "null".
Definition: hamt_map_types.hpp:224

pstore::transaction
Definition: transaction.hpp:191

pstore::typed_address
Definition: address.hpp:231

pstore::index::details::hash_size
constexpr auto const hash_size
The number of bits in hash_type.
Definition: hamt_map_types.hpp:36

pstore::array_stack
A simple wrapper for std::array which provides the functionality of a stack, specifically a FILO (fir...
Definition: array_stack.hpp:39

pstore::gsl::not_null
Definition: gsl.hpp:589

pstore::index::details::internal_node::make_writable
static internal_node * make_writable(SequenceContainer *const container, index_pointer const node, internal_node const &internal)
Returns a writable reference to an internal node.
Definition: hamt_map_types.hpp:626

pstore::index::details::index_pointer::is_address
bool is_address() const noexcept
Returns true if the index_pointer is pointing to a store node, false otherwise.
Definition: hamt_map_types.hpp:221

pstore::index::details::index_pointer::is_heap
bool is_heap() const noexcept
Returns true if the index_pointer is pointing to a heap node, false otherwise.
Definition: hamt_map_types.hpp:215

pstore::index::details::index_pointer::is_leaf
bool is_leaf() const noexcept
Returns true if the index_pointer contains the address of a value in the store, false otherwise...
Definition: hamt_map_types.hpp:211

details
Definition: print.cpp:18

pstore::index::header_block
The address of an instance of this type is passed to the hamt_map ctor to load an existing index...
Definition: hamt_map_types.hpp:96

chunked_sequence.hpp
Defines the chunked_sequence<> container.

pstore::index::details::internal_node::allocate
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.
Definition: hamt_map_types.hpp:582

pstore::index::details::internal_node::set_bitmap
void set_bitmap(hash_type const bm) noexcept
A function for deliberately creating illegal internal nodes in the unit test.
Definition: hamt_map_types.hpp:687

pstore::index::details::internal_node
An internal trie node.
Definition: hamt_map_types.hpp:508

pstore::index::details::internal_node::allocate
static internal_node * allocate(SequenceContainer *container, index_pointer const &leaf, hash_type const hash)
Construct an internal node with a single child.
Definition: hamt_map_types.hpp:560

pstore
Definition: nonpod2.cpp:40

pstore::database
Definition: database.hpp:40

pstore::index::details::index_pointer::is_linear
bool is_linear() const noexcept
Returns true if the index_pointer is pointing to a linear node, false otherwise.
Definition: hamt_map_types.hpp:206

array_stack.hpp
array_stack is a simple container which provides an interface very similar to std::stack, but based on std::array.

pstore::index::details::linear_node::size
std::size_t size() const
Returns the number of elements.
Definition: hamt_map_types.hpp:399

pstore::index::details::internal_node::lookup
std::pair< index_pointer, std::size_t > lookup(hash_type hash_index) const
Definition: hamt_map_types.hpp:728

pstore::index::details::linear_node::lookup
auto lookup(database const &db, OtherKeyType const &key, KeyEqual equal) const -> std::pair< index_pointer const, std::size_t >
Search the linear node and return the child slot if the key exists.
Definition: hamt_map_types.hpp:483

pstore::index::details::max_tree_depth
constexpr unsigned max_tree_depth
The max depth of the hash trees include several levels internal nodes (max_internal_depth), one linear node and one leaf node.
Definition: hamt_map_types.hpp:67

pstore::serialize::is_compatible
If the two types T1 and T2 have a compatible representation when serialized, provides the member cons...
Definition: types.hpp:321

pstore::index::details::internal_node::get_new_index
static unsigned get_new_index(hash_type const new_hash, hash_type const existing_hash) noexcept
Return the new leaf child index number.
Definition: hamt_map_types.hpp:659

pstore::index::details::internal_node::allocate
static internal_node * allocate(SequenceContainer *const container, internal_node const &other)
Construct an internal node from existing internal-node instance.
Definition: hamt_map_types.hpp:541

pstore::index::header_block::size
std::uint64_t size
The number of keys stored in the tree.
Definition: hamt_map_types.hpp:99

pstore::index::details::index_pointer
An index pointer is either a database address or a pointer to volatile RAM.
Definition: hamt_map_types.hpp:132

pstore::index::header_block::root
address root
The store address of the tree&#39;s root node.
Definition: hamt_map_types.hpp:101

pstore::index::details::internal_node::size
unsigned size() const noexcept
Returns the number of children contained by this node.
Definition: hamt_map_types.hpp:653

pstore::transaction_base
The database transaction class.
Definition: transaction.hpp:43