diff options
Diffstat (limited to 'immer/experimental/detail/dvektor_impl.hpp')
| -rw-r--r-- | immer/experimental/detail/dvektor_impl.hpp | 498 |
1 files changed, 498 insertions, 0 deletions
diff --git a/immer/experimental/detail/dvektor_impl.hpp b/immer/experimental/detail/dvektor_impl.hpp new file mode 100644 index 000000000000..81dbbc59f5f3 --- /dev/null +++ b/immer/experimental/detail/dvektor_impl.hpp @@ -0,0 +1,498 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/heap/heap_policy.hpp> +#include <immer/refcount/enable_intrusive_ptr.hpp> +#include <immer/refcount/refcount_policy.hpp> + +#include <boost/intrusive_ptr.hpp> +#include <boost/iterator/iterator_facade.hpp> +#include <boost/smart_ptr/intrusive_ref_counter.hpp> + +#include <cassert> +#include <limits> + +namespace immer { +namespace detail { +namespace dvektor { + +constexpr auto fast_log2(std::size_t x) +{ + return x == 0 ? 0 : sizeof(std::size_t) * 8 - 1 - __builtin_clzl(x); +} + +template <int B, typename T = std::size_t> +constexpr T branches = T{1} << B; + +template <int B, typename T = std::size_t> +constexpr T mask = branches<B, T> - 1; + +template <int B, typename T = std::size_t> +constexpr auto + max_depth = fast_log2(std::numeric_limits<std::size_t>::max()) / B; + +template <typename T, int B, typename MP> +struct node; + +template <typename T, int B, typename MP> +using node_ptr = boost::intrusive_ptr<node<T, B, MP>>; + +template <typename T, int B> +using leaf_node = std::array<T, 1 << B>; + +template <typename T, int B, typename MP> +using inner_node = std::array<node_ptr<T, B, MP>, 1 << B>; + +template <typename T, int B, typename MP> +struct node + : enable_intrusive_ptr<node<T, B, MP>, typename MP::refcount> + , enable_optimized_heap_policy<node<T, B, MP>, typename MP::heap> +{ + using leaf_node_t = leaf_node<T, B>; + using inner_node_t = inner_node<T, B, MP>; + + enum + { + leaf_kind, + inner_kind + } kind; + + union data_t + { + leaf_node_t leaf; + inner_node_t inner; + data_t(leaf_node_t n) + : leaf(std::move(n)) + {} + data_t(inner_node_t n) + : inner(std::move(n)) + {} + ~data_t() {} + } data; + + ~node() + { + switch (kind) { + case leaf_kind: + data.leaf.~leaf_node_t(); + break; + case inner_kind: + data.inner.~inner_node_t(); + break; + } + } + + node(leaf_node<T, B> n) + : kind{leaf_kind} + , data{std::move(n)} + {} + + node(inner_node<T, B, MP> n) + : kind{inner_kind} + , data{std::move(n)} + {} + + inner_node_t& inner() & + { + assert(kind == inner_kind); + return data.inner; + } + const inner_node_t& inner() const& + { + assert(kind == inner_kind); + return data.inner; + } + inner_node_t&& inner() && + { + assert(kind == inner_kind); + return std::move(data.inner); + } + + leaf_node_t& leaf() & + { + assert(kind == leaf_kind); + return data.leaf; + } + const leaf_node_t& leaf() const& + { + assert(kind == leaf_kind); + return data.leaf; + } + leaf_node_t&& leaf() && + { + assert(kind == leaf_kind); + return std::move(data.leaf); + } +}; + +template <typename T, int B, typename MP, typename... Ts> +auto make_node(Ts&&... xs) -> boost::intrusive_ptr<node<T, B, MP>> +{ + return new node<T, B, MP>(std::forward<Ts>(xs)...); +} + +template <typename T, int B, typename MP> +struct ref +{ + using inner_t = inner_node<T, B, MP>; + using leaf_t = leaf_node<T, B>; + using node_t = node<T, B, MP>; + using node_ptr_t = node_ptr<T, B, MP>; + + unsigned depth; + std::array<node_ptr_t, max_depth<B>> display; + + template <typename... Ts> + static auto make_node(Ts&&... xs) + { + return dvektor::make_node<T, B, MP>(std::forward<Ts>(xs)...); + } + + const T& get_elem(std::size_t index, std::size_t xr) const + { + auto display_idx = fast_log2(xr) / B; + auto node = display[display_idx].get(); + auto shift = display_idx * B; + while (display_idx--) { + node = node->inner()[(index >> shift) & mask<B>].get(); + shift -= B; + } + return node->leaf()[index & mask<B>]; + } + + node_ptr_t null_slot_and_copy_inner(node_ptr_t& node, std::size_t idx) + { + auto& n = node->inner(); + auto x = node_ptr_t{}; + x.swap(n[idx]); + return copy_of_inner(x); + } + + node_ptr_t null_slot_and_copy_leaf(node_ptr_t& node, std::size_t idx) + { + auto& n = node->inner(); + auto x = node_ptr_t{}; + x.swap(n[idx]); + return copy_of_leaf(x); + } + + node_ptr_t copy_of_inner(const node_ptr_t& n) + { + return make_node(n->inner()); + } + + node_ptr_t copy_of_leaf(const node_ptr_t& n) + { + return make_node(n->leaf()); + } + + void stabilize(std::size_t index) + { + auto shift = B; + for (auto i = 1u; i < depth; ++i) { + display[i] = copy_of_inner(display[i]); + display[i]->inner()[(index >> shift) & mask<B>] = display[i - 1]; + shift += B; + } + } + + void goto_pos_writable_from_clean(std::size_t old_index, + std::size_t index, + std::size_t xr) + { + assert(depth); + auto d = depth - 1; + if (d == 0) { + display[0] = copy_of_leaf(display[0]); + } else { + IMMER_UNREACHABLE; + display[d] = copy_of_inner(display[d]); + auto shift = B * d; + while (--d) { + display[d] = null_slot_and_copy_inner( + display[d + 1], (index >> shift) & mask<B>); + shift -= B; + } + display[0] = + null_slot_and_copy_leaf(display[1], (index >> B) & mask<B>); + } + } + + void goto_pos_writable_from_dirty(std::size_t old_index, + std::size_t new_index, + std::size_t xr) + { + assert(depth); + if (xr < (1 << B)) { + display[0] = copy_of_leaf(display[0]); + } else { + auto display_idx = fast_log2(xr) / B; + auto shift = B; + for (auto i = 1u; i <= display_idx; ++i) { + display[i] = copy_of_inner(display[i]); + display[i]->inner()[(old_index >> shift) & mask<B>] = + display[i - 1]; + shift += B; + } + for (auto i = display_idx - 1; i > 0; --i) { + shift -= B; + display[i] = null_slot_and_copy_inner( + display[i + 1], (new_index >> shift) & mask<B>); + } + display[0] = + null_slot_and_copy_leaf(display[1], (new_index >> B) & mask<B>); + } + } + + void goto_fresh_pos_writable_from_clean(std::size_t old_index, + std::size_t new_index, + std::size_t xr) + { + auto display_idx = fast_log2(xr) / B; + if (display_idx > 0) { + auto shift = display_idx * B; + if (display_idx == depth) { + display[display_idx] = make_node(inner_t{}); + display[display_idx]->inner()[(old_index >> shift) & mask<B>] = + display[display_idx - 1]; + ++depth; + } + while (--display_idx) { + auto node = display[display_idx + 1] + ->inner()[(new_index >> shift) & mask<B>]; + display[display_idx] = + node ? std::move(node) : make_node(inner_t{}); + } + display[0] = make_node(leaf_t{}); + } + } + + void goto_fresh_pos_writable_from_dirty(std::size_t old_index, + std::size_t new_index, + std::size_t xr) + { + stabilize(old_index); + goto_fresh_pos_writable_from_clean(old_index, new_index, xr); + } + + void goto_next_block_start(std::size_t index, std::size_t xr) + { + auto display_idx = fast_log2(xr) / B; + auto shift = display_idx * B; + if (display_idx > 0) { + display[display_idx - 1] = + display[display_idx]->inner()[(index >> shift) & mask<B>]; + while (--display_idx) + display[display_idx - 1] = display[display_idx]->inner()[0]; + } + } + + void goto_pos(std::size_t index, std::size_t xr) + { + auto display_idx = fast_log2(xr) / B; + auto shift = display_idx * B; + if (display_idx) { + do { + display[display_idx - 1] = + display[display_idx]->inner()[(index >> shift) & mask<B>]; + shift -= B; + } while (--display_idx); + } + } +}; + +template <typename T, int B, typename MP> +struct impl +{ + using inner_t = inner_node<T, B, MP>; + using leaf_t = leaf_node<T, B>; + using node_t = node<T, B, MP>; + using node_ptr_t = node_ptr<T, B, MP>; + using ref_t = ref<T, B, MP>; + + std::size_t size; + std::size_t focus; + bool dirty; + ref_t p; + + template <typename... Ts> + static auto make_node(Ts&&... xs) + { + return dvektor::make_node<T, B, MP>(std::forward<Ts>(xs)...); + } + + void goto_pos_writable(std::size_t old_index, + std::size_t new_index, + std::size_t xr) + { + if (dirty) { + p.goto_pos_writable_from_dirty(old_index, new_index, xr); + } else { + p.goto_pos_writable_from_clean(old_index, new_index, xr); + dirty = true; + } + } + + void goto_fresh_pos_writable(std::size_t old_index, + std::size_t new_index, + std::size_t xr) + { + if (dirty) { + p.goto_fresh_pos_writable_from_dirty(old_index, new_index, xr); + } else { + p.goto_fresh_pos_writable_from_clean(old_index, new_index, xr); + dirty = true; + } + } + + impl push_back(T value) const + { + if (size) { + auto block_index = size & ~mask<B>; + auto lo = size & mask<B>; + if (size != block_index) { + auto s = impl{size + 1, block_index, dirty, p}; + s.goto_pos_writable(focus, block_index, focus ^ block_index); + s.p.display[0]->leaf()[lo] = std::move(value); + return s; + } else { + auto s = impl{size + 1, block_index, dirty, p}; + s.goto_fresh_pos_writable( + focus, block_index, focus ^ block_index); + s.p.display[0]->leaf()[lo] = std::move(value); + return s; + } + } else { + return impl{ + 1, 0, false, {1, {{make_node(leaf_t{{std::move(value)}})}}}}; + } + } + + const T& get(std::size_t index) const + { + return p.get_elem(index, index ^ focus); + } + + template <typename FnT> + impl update(std::size_t idx, FnT&& fn) const + { + auto s = impl{size, idx, dirty, p}; + s.goto_pos_writable(focus, idx, focus ^ idx); + auto& v = s.p.display[0]->leaf()[idx & mask<B>]; + v = fn(std::move(v)); + return s; + } + + impl assoc(std::size_t idx, T value) const + { + return update(idx, [&](auto&&) { return std::move(value); }); + } +}; + +template <typename T, int B, typename MP> +const impl<T, B, MP> empty = {0, 0, false, ref<T, B, MP>{1, {}}}; + +template <typename T, int B, typename MP> +struct iterator + : boost::iterator_facade<iterator<T, B, MP>, + T, + boost::random_access_traversal_tag, + const T&> +{ + struct end_t + {}; + + iterator() = default; + + iterator(const impl<T, B, MP>& v) + : p_{v.p} + , i_{0} + , base_{0} + { + if (v.dirty) + p_.stabilize(v.focus); + p_.goto_pos(0, 0 ^ v.focus); + curr_ = p_.display[0]->leaf().begin(); + } + + iterator(const impl<T, B, MP>& v, end_t) + : p_{v.p} + , i_{v.size} + , base_{(v.size - 1) & ~mask<B>} + { + if (v.dirty) + p_.stabilize(v.focus); + p_.goto_pos(base_, base_ ^ v.focus); + curr_ = p_.display[0]->leaf().begin() + (i_ - base_); + } + +private: + friend class boost::iterator_core_access; + using leaf_iterator = typename leaf_node<T, B>::const_iterator; + + ref<T, B, MP> p_; + std::size_t i_; + std::size_t base_; + leaf_iterator curr_; + + void increment() + { + ++i_; + if (i_ - base_ < branches<B>) { + ++curr_; + } else { + auto new_base = base_ + branches<B>; + p_.goto_next_block_start(new_base, base_ ^ new_base); + base_ = new_base; + curr_ = p_.display[0]->leaf().begin(); + } + } + + void decrement() + { + assert(i_ > 0); + --i_; + if (i_ >= base_) { + --curr_; + } else { + auto new_base = base_ - branches<B>; + p_.goto_pos(new_base, base_ ^ new_base); + base_ = new_base; + curr_ = std::prev(p_.display[0]->leaf().end()); + } + } + + void advance(std::ptrdiff_t n) + { + i_ += n; + if (i_ <= base_ && i_ - base_ < branches<B>) { + curr_ += n; + } else { + auto new_base = i_ & ~mask<B>; + p_.goto_pos(new_base, base_ ^ new_base); + base_ = new_base; + curr_ = p_.display[0]->leaf().begin() + (i_ - base_); + } + } + + bool equal(const iterator& other) const { return i_ == other.i_; } + + std::ptrdiff_t distance_to(const iterator& other) const + { + return other.i_ > i_ ? static_cast<std::ptrdiff_t>(other.i_ - i_) + : -static_cast<std::ptrdiff_t>(i_ - other.i_); + } + + const T& dereference() const { return *curr_; } +}; + +} /* namespace dvektor */ +} /* namespace detail */ +} /* namespace immer */ |