class region_map_impl

Declaration

template <typename ValueType, int Dims>
class region_map_impl { /* full declaration omitted */ };

Description

The region map is implemented as a customized R-Tree [Guttman 1984]. In order to maintain performance over time, entries with compatible boxes and equal values will be merged. The implementation logic is split between this class, which acts as a wrapper around the root node, as well as inner_node, which implements the recursive tree operations. This class is responsible for dispatching the recursive calls as well as handling the merging of entries and reinsertion of orphaned entries/nodes after update operations. It is also responsible for merging the final list of query results. TODO PERF: Try to minimize the number of value copies we do during intermediate steps (e.g. when merging) TODO PERF: Look into bulk-loading algorithms for updating multiple boxes at once

Declared at: include/region_map.h:831

Template Parameters

ValueType

int Dims

Member Variables

static const size_t dimensions = Dims

box<Dims> m_extent

std::unique_ptr<typename types::inner_node_type> m_root

std::vector<typename types::update_action> m_update_actions

std::vector<typename types::entry> m_merge_candidates

std::vector<typename types::entry> m_updated_nodes

std::vector<typename types::orphan> m_erase_orphans

std::vector<typename types::entry> m_query_results_raw

std::vector<typename types::entry> m_query_results_clamped

Member Aliases

• using value_type = ValueType;
• using types = region_map_types<ValueType, Dims>;

Member Function Overview

• template <typename Functor>
  apply_to_values(const Functor & f) → void
• format_to(fmt::format_context::iterator out) const → auto
• get_extent() const → range<Dims>
• get_region_values(const box<Dims> & request) const → std::vector<typename types::entry>
• operator=(const region_map_impl<ValueType, Dims> &) → region_map_impl<ValueType, Dims> &
• operator=(region_map_impl<ValueType, Dims> &&) noexcept → region_map_impl<ValueType, Dims> &
• region_map_impl(const box<Dims> & extent, const ValueType & default_value = ValueType{})
• region_map_impl(const region_map_impl<ValueType, Dims> &)
• region_map_impl(region_map_impl<ValueType, Dims> &&) noexcept
• update_box(const box<Dims> & box, const ValueType & value) → void
• ~region_map_impl()
• can_merge(const box<Dims> & box_a, const box<Dims> & box_b) const → bool
• erase(const box<Dims> & box) → void
• template <typename Callback>
  for_each(const Callback & cb) const → void
• insert(const box<Dims> & box, const ValueType & value) → void
• insert_subtree(const box<Dims> & box, typename types::unique_inner_node_ptr && subtree) → void
• reroot(typename types::insert_result new_sibling) → void
• try_merge(std::vector<typename types::entry> && merge_candidates) → void

Member Functions

¶template <typename Functor>
void apply_to_values(const Functor& f)

Description

Applies the provided functor to all values and attempts to merge all entries that had their values changed.

Declared at: include/region_map.h:932

Template Parameters

Functor

Parameters

const Functor& f

---

¶auto format_to(
    fmt::format_context::iterator out) const

Declared at: include/region_map.h:1023

Parameters

fmt::format_context::iterator out

---

¶range<Dims> get_extent() const

Declared at: include/region_map.h:1028

---

¶std::vector<typename types::entry>
get_region_values(const box<Dims>& request) const

Description

Finds all entries intersecting with request, clamps them to the extent and merges them. TODO PERF: In most cases we are unlikely to store the returned values, and the copy is unnecessary. Return const reference instead?

Declared at: include/region_map.h:953

Parameters

const box<Dims>& request

---

¶region_map_impl<ValueType, Dims>& operator=(
    const region_map_impl<ValueType, Dims>&)

Declared at: include/region_map.h:848

Parameters

const region_map_impl<ValueType, Dims>&

---

¶region_map_impl<ValueType, Dims>& operator=(
    region_map_impl<ValueType, Dims>&&) noexcept

Declared at: include/region_map.h:849

Parameters

region_map_impl<ValueType, Dims>&&

---

¶region_map_impl(
    const box<Dims>& extent,
    const ValueType& default_value = ValueType{})

Declared at: include/region_map.h:839

Parameters

const box<Dims>& extent

const ValueType& default_value = ValueType{}

---

¶region_map_impl(
    const region_map_impl<ValueType, Dims>&)

Declared at: include/region_map.h:846

Parameters

const region_map_impl<ValueType, Dims>&

---

¶region_map_impl(
    region_map_impl<ValueType, Dims>&&) noexcept

Declared at: include/region_map.h:847

Parameters

region_map_impl<ValueType, Dims>&&

---

¶void update_box(const box<Dims>& box,
                const ValueType& value)

Description

Updates the value for the provided box within the tree. This operation consists of roughly three steps: 1) Prepare the tree by creating a "hole" for the new box. This usually means splitting existing boxes within the tree. The required set of operations is propagated back up the tree. In some situations an in-place or localized update can be performed, in this case step 2 is skipped (see inner_node::update_box). 2) Perform all erase and insert operations calculated in step 1. 3) Attempt to merge the box as well as any other newly created boxes with their surrounding entries.

Declared at: include/region_map.h:864

Parameters

const box<Dims>& box

const ValueType& value

---

¶~region_map_impl()

Declared at: include/region_map.h:844

---

¶bool can_merge(const box<Dims>& box_a,
               const box<Dims>& box_b) const

Description

Calculates whether two boxes can be merged. In order to be mergeable, the two boxes have to touch in one dimension and match exactly in all remaining dimensions.

Declared at: include/region_map.h:1107

Parameters

const box<Dims>& box_a

const box<Dims>& box_b

---

¶void erase(const box<Dims>& box)

Description

Erases a box from the tree. If the parent box becomes underfull it is dissolved and its children are reinserted.

Declared at: include/region_map.h:1084

Parameters

const box<Dims>& box

---

¶template <typename Callback>
void for_each(const Callback& cb) const

Description

Invokes the provided callback for every entry (box/value pair) within the region map, for debugging / testing / instrumentation.

Declared at: include/region_map.h:1209

Template Parameters

Callback

Parameters

const Callback& cb

---

¶void insert(const box<Dims>& box,
            const ValueType& value)

Description

Inserts a new entry into the tree. Precondition: The insert location must be empty.

Declared at: include/region_map.h:1054

Parameters

const box<Dims>& box

const ValueType& value

---

¶void insert_subtree(
    const box<Dims>& box,
    typename types::unique_inner_node_ptr&&
        subtree)

Description

Inserts a subtree (either from a dissolved parent or after a split) into the tree.

Declared at: include/region_map.h:1062

Parameters

const box<Dims>& box

typename types::unique_inner_node_ptr&& subtree

---

¶void reroot(
    typename types::insert_result new_sibling)

Description

Creates a new root node that is parent to the current root node and new_sibling, increasing the tree's height by 1.

Declared at: include/region_map.h:1071

Parameters

typename types::insert_result new_sibling

---

¶void try_merge(
    std::vector<typename types::entry>&&
        merge_candidates)

Description

Try to merge a list of candidate entries with their neighbors within the tree.

Declared at: include/region_map.h:1128

Parameters

std::vector<typename types::entry>&& merge_candidates

---