persistent_map.ipp

Go to the documentation of this file.

 
 
#pragma once
 
#include "persistent_map.hpp"
 
#include <tuple>
#include <utility>
 
namespace datastructures {
 
// ==== Constructors & Assigments ====
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::persistent_map()
    : persistent_map(key_compare{}) {}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::persistent_map(
    const key_compare &comparator, const allocator_type &allocator)
    : comparator(comparator), value_comparator(comparator),
      tree(value_comparator, allocator) {}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::persistent_map(
    const allocator_type &allocator)
    : persistent_map(key_compare{}, allocator) {}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::persistent_map(
    const persistent_map &other)
    : comparator(other.comparator), value_comparator(other.comparator),
      tree(other.tree) {}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc> &
persistent_map<TKey, TValue, TKeyComp, TAlloc>::operator=(
    const persistent_map &other) {
    comparator = other.comparator;
    value_comparator = other.comparator;
    tree = other.tree;
    return *this;
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::persistent_map(
    persistent_map &&other) noexcept
    : comparator(std::move(other.comparator)),
      value_comparator(std::move(other.comparator)),
      tree(std::move(other.tree)) {}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc> &
persistent_map<TKey, TValue, TKeyComp, TAlloc>::operator=(
    persistent_map &&other) noexcept {
    comparator = std::move(other.comparator);
    value_comparator = std::move(other.comparator);
    tree = std::move(other.tree);
    return *this;
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::~persistent_map() noexcept {
    // the tree will be deleted in the `avl_tree::~avl_tree`.
}
 
// ==== Observers & Allocator getter ====
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::allocator_type
persistent_map<TKey, TValue, TKeyComp, TAlloc>::get_allocator() const noexcept {
    return tree.get_allocator();
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::key_compare
persistent_map<TKey, TValue, TKeyComp, TAlloc>::key_comp() const noexcept {
    return comparator;
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::value_compare
persistent_map<TKey, TValue, TKeyComp, TAlloc>::value_comp() const noexcept {
    return value_comparator;
}
 
// ==== Access Functions ====
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
std::vector<const typename persistent_map<TKey, TValue, TKeyComp,
                                          TAlloc>::mapped_type *>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::list_in_order(
    version_type version) const noexcept {
    auto nodes = tree.list_in_order(version);
    std::vector<const mapped_type *> values;
    for (auto node : nodes) {
        values.push_back(&node->item.second);
    }
    return values;
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
const typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::mapped_type *
persistent_map<TKey, TValue, TKeyComp, TAlloc>::find(
    const key_type &key, version_type version) const noexcept {
    typename tree_type::node_ptr node = tree.find(key, version);
    if (node == nullptr) {
        return nullptr;
    }
    return &node->item.second;
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
bool persistent_map<TKey, TValue, TKeyComp, TAlloc>::contains(
    const key_type &key, version_type version) const noexcept {
    typename tree_type::node_ptr node = tree.find(key, version);
    return node != nullptr;
}
 
// ==== Size Queries ====
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
bool persistent_map<TKey, TValue, TKeyComp, TAlloc>::empty(
    version_type version) const noexcept {
    return tree.size(version) == 0;
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::size_type
persistent_map<TKey, TValue, TKeyComp, TAlloc>::size(
    version_type version) const noexcept {
    return tree.size(version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
int persistent_map<TKey, TValue, TKeyComp, TAlloc>::get_height(
    version_type version) const noexcept {
    return tree.get_height(version);
}
 
// ==== Update Operations ====
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
void persistent_map<TKey, TValue, TKeyComp, TAlloc>::clear() noexcept {
    tree.clear_all();
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::insert(const value_type &item,
                                                       version_type version) {
    auto [node, inserted] =
        tree.insert(item.first, [&]() { return item; }, version, false);
 
    return std::make_pair(inserted, node->version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::insert(value_type &&item,
                                                       version_type version) {
    auto [node, inserted] = tree.insert(
        item.first, [&]() { return std::move(item); }, version, false);
 
    return std::make_pair(inserted, node->version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
template <class TMapped>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::insert_or_assign(
    const key_type &key, TMapped &&value, version_type version) {
    auto [node, inserted] = tree.insert(
        key, [&]() { return value_type(key, std::forward<TMapped>(value)); },
        version, true);
 
    return std::make_pair(inserted, node->version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
template <class TMapped>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::insert_or_assign(
    key_type &&key, TMapped &&value, version_type version) {
    auto [node, inserted] = tree.insert(
        key,
        [&]() {
            return value_type(std::move(key), std::forward<TMapped>(value));
        },
        version, true);
 
    return std::make_pair(inserted, node->version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
template <class... Args>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::try_emplace(
    const key_type &key, version_type version, Args &&...args) {
 
    auto insert_callback = [&]() {
        return value_type(std::piecewise_construct, std::forward_as_tuple(key),
                          std::forward_as_tuple(std::forward<Args>(args)...));
    };
 
    auto [node, inserted] = tree.insert(key, insert_callback, version, false);
 
    return std::make_pair(inserted, node->version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
template <class... Args>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::try_emplace(
    key_type &&key, version_type version, Args &&...args) {
 
    auto insert_callback = [&]() {
        return value_type(std::piecewise_construct,
                          std::forward_as_tuple(std::move(key)),
                          std::forward_as_tuple(std::forward<Args>(args)...));
    };
 
    auto [node, inserted] = tree.insert(key, insert_callback, version, false);
 
    return std::make_pair(inserted, node->version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
std::pair<bool,
          typename persistent_map<TKey, TValue, TKeyComp, TAlloc>::version_type>
persistent_map<TKey, TValue, TKeyComp, TAlloc>::erase(
    const key_type &key, version_type version) noexcept {
    return tree.erase(key, version);
}
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
void persistent_map<TKey, TValue, TKeyComp, TAlloc>::swap(
    persistent_map &other) noexcept {
    std::swap(tree, other.tree);
    std::swap(comparator, other.comparator);
    std::swap(value_comparator, other.value_comparator);
}
 
} // namespace datastructures