diff options
Diffstat (limited to 'immer/detail/hamts')
| -rw-r--r-- | immer/detail/hamts/bits.hpp | 108 | ||||
| -rw-r--r-- | immer/detail/hamts/champ.hpp | 473 | ||||
| -rw-r--r-- | immer/detail/hamts/champ_iterator.hpp | 148 | ||||
| -rw-r--r-- | immer/detail/hamts/node.hpp | 717 |
4 files changed, 1446 insertions, 0 deletions
diff --git a/immer/detail/hamts/bits.hpp b/immer/detail/hamts/bits.hpp new file mode 100644 index 000000000000..b02caf770666 --- /dev/null +++ b/immer/detail/hamts/bits.hpp @@ -0,0 +1,108 @@ +// +// 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 <cstdint> + +#if defined(_MSC_VER) +#include <intrin.h> // __popcnt +#endif + +namespace immer { +namespace detail { +namespace hamts { + +using size_t = std::size_t; +using hash_t = std::size_t; +using bits_t = std::uint32_t; +using count_t = std::uint32_t; +using shift_t = std::uint32_t; + +template <bits_t B> +struct get_bitmap_type +{ + static_assert(B < 6u, "B > 6 is not supported."); + + using type = std::uint32_t; +}; + +template <> +struct get_bitmap_type<6u> +{ + using type = std::uint64_t; +}; + +template <bits_t B, typename T = count_t> +constexpr T branches = T{1u} << B; + +template <bits_t B, typename T = size_t> +constexpr T mask = branches<B, T> - 1u; + +template <bits_t B, typename T = count_t> +constexpr T max_depth = (sizeof(hash_t) * 8u + B - 1u) / B; + +template <bits_t B, typename T = count_t> +constexpr T max_shift = max_depth<B, count_t>* B; + +#define IMMER_HAS_BUILTIN_POPCOUNT 1 + +inline auto popcount_fallback(std::uint32_t x) +{ + // More alternatives: + // https://en.wikipedia.org/wiki/Hamming_weight + // http://wm.ite.pl/articles/sse-popcount.html + // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel + x = x - ((x >> 1) & 0x55555555u); + x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u); + return (((x + (x >> 4u)) & 0xF0F0F0Fu) * 0x1010101u) >> 24u; +} + +inline auto popcount_fallback(std::uint64_t x) +{ + x = x - ((x >> 1) & 0x5555555555555555u); + x = (x & 0x3333333333333333u) + ((x >> 2u) & 0x3333333333333333u); + return (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0Fu) * 0x0101010101010101u) >> + 56u; +} + +inline count_t popcount(std::uint32_t x) +{ +#if IMMER_HAS_BUILTIN_POPCOUNT +#if defined(_MSC_VER) + return __popcnt(x); +#else + return __builtin_popcount(x); +#endif +#else + return popcount_fallback(x); +#endif +} + +inline count_t popcount(std::uint64_t x) +{ +#if IMMER_HAS_BUILTIN_POPCOUNT +#if defined(_MSC_VER) +#if defined(_WIN64) + return __popcnt64(x); +#else + // TODO: benchmark against popcount_fallback(std::uint64_t x) + return popcount(static_cast<std::uint32_t>(x >> 32)) + + popcount(static_cast<std::uint32_t>(x)); +#endif +#else + return __builtin_popcountll(x); +#endif +#else + return popcount_fallback(x); +#endif +} + +} // namespace hamts +} // namespace detail +} // namespace immer diff --git a/immer/detail/hamts/champ.hpp b/immer/detail/hamts/champ.hpp new file mode 100644 index 000000000000..e3b55d397c72 --- /dev/null +++ b/immer/detail/hamts/champ.hpp @@ -0,0 +1,473 @@ +// +// 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/config.hpp> +#include <immer/detail/hamts/node.hpp> + +#include <algorithm> + +namespace immer { +namespace detail { +namespace hamts { + +template <typename T, + typename Hash, + typename Equal, + typename MemoryPolicy, + bits_t B> +struct champ +{ + static constexpr auto bits = B; + + using node_t = node<T, Hash, Equal, MemoryPolicy, B>; + using bitmap_t = typename get_bitmap_type<B>::type; + + static_assert(branches<B> <= sizeof(bitmap_t) * 8, ""); + + node_t* root; + size_t size; + + static const champ& empty() + { + static const champ empty_{ + node_t::make_inner_n(0), + 0, + }; + return empty_; + } + + champ(node_t* r, size_t sz) + : root{r} + , size{sz} + {} + + champ(const champ& other) + : champ{other.root, other.size} + { + inc(); + } + + champ(champ&& other) + : champ{empty()} + { + swap(*this, other); + } + + champ& operator=(const champ& other) + { + auto next = other; + swap(*this, next); + return *this; + } + + champ& operator=(champ&& other) + { + swap(*this, other); + return *this; + } + + friend void swap(champ& x, champ& y) + { + using std::swap; + swap(x.root, y.root); + swap(x.size, y.size); + } + + ~champ() { dec(); } + + void inc() const { root->inc(); } + + void dec() const + { + if (root->dec()) + node_t::delete_deep(root, 0); + } + + template <typename Fn> + void for_each_chunk(Fn&& fn) const + { + for_each_chunk_traversal(root, 0, fn); + } + + template <typename Fn> + void for_each_chunk_traversal(node_t* node, count_t depth, Fn&& fn) const + { + if (depth < max_depth<B>) { + auto datamap = node->datamap(); + if (datamap) + fn(node->values(), node->values() + popcount(datamap)); + auto nodemap = node->nodemap(); + if (nodemap) { + auto fst = node->children(); + auto lst = fst + popcount(nodemap); + for (; fst != lst; ++fst) + for_each_chunk_traversal(*fst, depth + 1, fn); + } + } else { + fn(node->collisions(), + node->collisions() + node->collision_count()); + } + } + + template <typename Project, typename Default, typename K> + decltype(auto) get(const K& k) const + { + auto node = root; + auto hash = Hash{}(k); + for (auto i = count_t{}; i < max_depth<B>; ++i) { + auto bit = bitmap_t{1u} << (hash & mask<B>); + if (node->nodemap() & bit) { + auto offset = popcount(node->nodemap() & (bit - 1)); + node = node->children()[offset]; + hash = hash >> B; + } else if (node->datamap() & bit) { + auto offset = popcount(node->datamap() & (bit - 1)); + auto val = node->values() + offset; + if (Equal{}(*val, k)) + return Project{}(*val); + else + return Default{}(); + } else { + return Default{}(); + } + } + auto fst = node->collisions(); + auto lst = fst + node->collision_count(); + for (; fst != lst; ++fst) + if (Equal{}(*fst, k)) + return Project{}(*fst); + return Default{}(); + } + + std::pair<node_t*, bool> + do_add(node_t* node, T v, hash_t hash, shift_t shift) const + { + if (shift == max_shift<B>) { + auto fst = node->collisions(); + auto lst = fst + node->collision_count(); + for (; fst != lst; ++fst) + if (Equal{}(*fst, v)) + return { + node_t::copy_collision_replace(node, fst, std::move(v)), + false}; + return {node_t::copy_collision_insert(node, std::move(v)), true}; + } else { + auto idx = (hash & (mask<B> << shift)) >> shift; + auto bit = bitmap_t{1u} << idx; + if (node->nodemap() & bit) { + auto offset = popcount(node->nodemap() & (bit - 1)); + auto result = do_add( + node->children()[offset], std::move(v), hash, shift + B); + try { + result.first = + node_t::copy_inner_replace(node, offset, result.first); + return result; + } catch (...) { + node_t::delete_deep_shift(result.first, shift + B); + throw; + } + } else if (node->datamap() & bit) { + auto offset = popcount(node->datamap() & (bit - 1)); + auto val = node->values() + offset; + if (Equal{}(*val, v)) + return {node_t::copy_inner_replace_value( + node, offset, std::move(v)), + false}; + else { + auto child = node_t::make_merged( + shift + B, std::move(v), hash, *val, Hash{}(*val)); + try { + return {node_t::copy_inner_replace_merged( + node, bit, offset, child), + true}; + } catch (...) { + node_t::delete_deep_shift(child, shift + B); + throw; + } + } + } else { + return { + node_t::copy_inner_insert_value(node, bit, std::move(v)), + true}; + } + } + } + + champ add(T v) const + { + auto hash = Hash{}(v); + auto res = do_add(root, std::move(v), hash, 0); + auto new_size = size + (res.second ? 1 : 0); + return {res.first, new_size}; + } + + template <typename Project, + typename Default, + typename Combine, + typename K, + typename Fn> + std::pair<node_t*, bool> + do_update(node_t* node, K&& k, Fn&& fn, hash_t hash, shift_t shift) const + { + if (shift == max_shift<B>) { + auto fst = node->collisions(); + auto lst = fst + node->collision_count(); + for (; fst != lst; ++fst) + if (Equal{}(*fst, k)) + return { + node_t::copy_collision_replace( + node, + fst, + Combine{}(std::forward<K>(k), + std::forward<Fn>(fn)(Project{}(*fst)))), + false}; + return {node_t::copy_collision_insert( + node, + Combine{}(std::forward<K>(k), + std::forward<Fn>(fn)(Default{}()))), + true}; + } else { + auto idx = (hash & (mask<B> << shift)) >> shift; + auto bit = bitmap_t{1u} << idx; + if (node->nodemap() & bit) { + auto offset = popcount(node->nodemap() & (bit - 1)); + auto result = do_update<Project, Default, Combine>( + node->children()[offset], + k, + std::forward<Fn>(fn), + hash, + shift + B); + try { + result.first = + node_t::copy_inner_replace(node, offset, result.first); + return result; + } catch (...) { + node_t::delete_deep_shift(result.first, shift + B); + throw; + } + } else if (node->datamap() & bit) { + auto offset = popcount(node->datamap() & (bit - 1)); + auto val = node->values() + offset; + if (Equal{}(*val, k)) + return { + node_t::copy_inner_replace_value( + node, + offset, + Combine{}(std::forward<K>(k), + std::forward<Fn>(fn)(Project{}(*val)))), + false}; + else { + auto child = node_t::make_merged( + shift + B, + Combine{}(std::forward<K>(k), + std::forward<Fn>(fn)(Default{}())), + hash, + *val, + Hash{}(*val)); + try { + return {node_t::copy_inner_replace_merged( + node, bit, offset, child), + true}; + } catch (...) { + node_t::delete_deep_shift(child, shift + B); + throw; + } + } + } else { + return {node_t::copy_inner_insert_value( + node, + bit, + Combine{}(std::forward<K>(k), + std::forward<Fn>(fn)(Default{}()))), + true}; + } + } + } + + template <typename Project, + typename Default, + typename Combine, + typename K, + typename Fn> + champ update(const K& k, Fn&& fn) const + { + auto hash = Hash{}(k); + auto res = do_update<Project, Default, Combine>( + root, k, std::forward<Fn>(fn), hash, 0); + auto new_size = size + (res.second ? 1 : 0); + return {res.first, new_size}; + } + + // basically: + // variant<monostate_t, T*, node_t*> + // boo bad we are not using... C++17 :'( + struct sub_result + { + enum kind_t + { + nothing, + singleton, + tree + }; + + union data_t + { + T* singleton; + node_t* tree; + }; + + kind_t kind; + data_t data; + + sub_result() + : kind{nothing} {}; + sub_result(T* x) + : kind{singleton} + { + data.singleton = x; + }; + sub_result(node_t* x) + : kind{tree} + { + data.tree = x; + }; + }; + + template <typename K> + sub_result + do_sub(node_t* node, const K& k, hash_t hash, shift_t shift) const + { + if (shift == max_shift<B>) { + auto fst = node->collisions(); + auto lst = fst + node->collision_count(); + for (auto cur = fst; cur != lst; ++cur) + if (Equal{}(*cur, k)) + return node->collision_count() > 2 + ? node_t::copy_collision_remove(node, cur) + : sub_result{fst + (cur == fst)}; + return {}; + } else { + auto idx = (hash & (mask<B> << shift)) >> shift; + auto bit = bitmap_t{1u} << idx; + if (node->nodemap() & bit) { + auto offset = popcount(node->nodemap() & (bit - 1)); + auto result = + do_sub(node->children()[offset], k, hash, shift + B); + switch (result.kind) { + case sub_result::nothing: + return {}; + case sub_result::singleton: + return node->datamap() == 0 && + popcount(node->nodemap()) == 1 && shift > 0 + ? result + : node_t::copy_inner_replace_inline( + node, bit, offset, *result.data.singleton); + case sub_result::tree: + try { + return node_t::copy_inner_replace( + node, offset, result.data.tree); + } catch (...) { + node_t::delete_deep_shift(result.data.tree, shift + B); + throw; + } + } + } else if (node->datamap() & bit) { + auto offset = popcount(node->datamap() & (bit - 1)); + auto val = node->values() + offset; + if (Equal{}(*val, k)) { + auto nv = popcount(node->datamap()); + if (node->nodemap() || nv > 2) + return node_t::copy_inner_remove_value( + node, bit, offset); + else if (nv == 2) { + return shift > 0 ? sub_result{node->values() + !offset} + : node_t::make_inner_n( + 0, + node->datamap() & ~bit, + node->values()[!offset]); + } else { + assert(shift == 0); + return empty().root->inc(); + } + } + } + return {}; + } + } + + template <typename K> + champ sub(const K& k) const + { + auto hash = Hash{}(k); + auto res = do_sub(root, k, hash, 0); + switch (res.kind) { + case sub_result::nothing: + return *this; + case sub_result::tree: + return {res.data.tree, size - 1}; + default: + IMMER_UNREACHABLE; + } + } + + template <typename Eq = Equal> + bool equals(const champ& other) const + { + return size == other.size && equals_tree<Eq>(root, other.root, 0); + } + + template <typename Eq> + static bool equals_tree(const node_t* a, const node_t* b, count_t depth) + { + if (a == b) + return true; + else if (depth == max_depth<B>) { + auto nv = a->collision_count(); + return nv == b->collision_count() && + equals_collisions<Eq>(a->collisions(), b->collisions(), nv); + } else { + if (a->nodemap() != b->nodemap() || a->datamap() != b->datamap()) + return false; + auto n = popcount(a->nodemap()); + for (auto i = count_t{}; i < n; ++i) + if (!equals_tree<Eq>( + a->children()[i], b->children()[i], depth + 1)) + return false; + auto nv = popcount(a->datamap()); + return !nv || equals_values<Eq>(a->values(), b->values(), nv); + } + } + + template <typename Eq> + static bool equals_values(const T* a, const T* b, count_t n) + { + return std::equal(a, a + n, b, Eq{}); + } + + template <typename Eq> + static bool equals_collisions(const T* a, const T* b, count_t n) + { + auto ae = a + n; + auto be = b + n; + for (; a != ae; ++a) { + for (auto fst = b; fst != be; ++fst) + if (Eq{}(*a, *fst)) + goto good; + return false; + good: + continue; + } + return true; + } +}; + +} // namespace hamts +} // namespace detail +} // namespace immer diff --git a/immer/detail/hamts/champ_iterator.hpp b/immer/detail/hamts/champ_iterator.hpp new file mode 100644 index 000000000000..72673b41be03 --- /dev/null +++ b/immer/detail/hamts/champ_iterator.hpp @@ -0,0 +1,148 @@ +// +// 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/detail/hamts/champ.hpp> +#include <immer/detail/iterator_facade.hpp> + +namespace immer { +namespace detail { +namespace hamts { + +template <typename T, typename Hash, typename Eq, typename MP, bits_t B> +struct champ_iterator + : iterator_facade<champ_iterator<T, Hash, Eq, MP, B>, + std::forward_iterator_tag, + T, + const T&, + std::ptrdiff_t, + const T*> +{ + using tree_t = champ<T, Hash, Eq, MP, B>; + using node_t = typename tree_t::node_t; + + struct end_t + {}; + + champ_iterator() = default; + + champ_iterator(const tree_t& v) + : depth_{0} + { + if (v.root->datamap()) { + cur_ = v.root->values(); + end_ = v.root->values() + popcount(v.root->datamap()); + } else { + cur_ = end_ = nullptr; + } + path_[0] = &v.root; + ensure_valid_(); + } + + champ_iterator(const tree_t& v, end_t) + : cur_{nullptr} + , end_{nullptr} + , depth_{0} + { + path_[0] = &v.root; + } + + champ_iterator(const champ_iterator& other) + : cur_{other.cur_} + , end_{other.end_} + , depth_{other.depth_} + { + std::copy(other.path_, other.path_ + depth_ + 1, path_); + } + +private: + friend iterator_core_access; + + T* cur_; + T* end_; + count_t depth_; + node_t* const* path_[max_depth<B> + 1]; + + void increment() + { + ++cur_; + ensure_valid_(); + } + + bool step_down() + { + if (depth_ < max_depth<B>) { + auto parent = *path_[depth_]; + if (parent->nodemap()) { + ++depth_; + path_[depth_] = parent->children(); + auto child = *path_[depth_]; + if (depth_ < max_depth<B>) { + if (child->datamap()) { + cur_ = child->values(); + end_ = cur_ + popcount(child->datamap()); + } + } else { + cur_ = child->collisions(); + end_ = cur_ + child->collision_count(); + } + return true; + } + } + return false; + } + + bool step_right() + { + while (depth_ > 0) { + auto parent = *path_[depth_ - 1]; + auto last = parent->children() + popcount(parent->nodemap()); + auto next = path_[depth_] + 1; + if (next < last) { + path_[depth_] = next; + auto child = *path_[depth_]; + if (depth_ < max_depth<B>) { + if (child->datamap()) { + cur_ = child->values(); + end_ = cur_ + popcount(child->datamap()); + } + } else { + cur_ = child->collisions(); + end_ = cur_ + child->collision_count(); + } + return true; + } + --depth_; + } + return false; + } + + void ensure_valid_() + { + while (cur_ == end_) { + while (step_down()) + if (cur_ != end_) + return; + if (!step_right()) { + // end of sequence + assert(depth_ == 0); + cur_ = end_ = nullptr; + return; + } + } + } + + bool equal(const champ_iterator& other) const { return cur_ == other.cur_; } + + const T& dereference() const { return *cur_; } +}; + +} // namespace hamts +} // namespace detail +} // namespace immer diff --git a/immer/detail/hamts/node.hpp b/immer/detail/hamts/node.hpp new file mode 100644 index 000000000000..216e82b7874f --- /dev/null +++ b/immer/detail/hamts/node.hpp @@ -0,0 +1,717 @@ +// +// 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/detail/combine_standard_layout.hpp> +#include <immer/detail/hamts/bits.hpp> +#include <immer/detail/util.hpp> + +#include <cassert> + +namespace immer { +namespace detail { +namespace hamts { + +template <typename T, + typename Hash, + typename Equal, + typename MemoryPolicy, + bits_t B> +struct node +{ + using node_t = node; + + using memory = MemoryPolicy; + using heap_policy = typename memory::heap; + using heap = typename heap_policy::type; + using transience = typename memory::transience_t; + using refs_t = typename memory::refcount; + using ownee_t = typename transience::ownee; + using edit_t = typename transience::edit; + using value_t = T; + using bitmap_t = typename get_bitmap_type<B>::type; + + enum class kind_t + { + collision, + inner + }; + + struct collision_t + { + count_t count; + aligned_storage_for<T> buffer; + }; + + struct values_data_t + { + aligned_storage_for<T> buffer; + }; + + using values_t = combine_standard_layout_t<values_data_t, refs_t>; + + struct inner_t + { + bitmap_t nodemap; + bitmap_t datamap; + values_t* values; + aligned_storage_for<node_t*> buffer; + }; + + union data_t + { + inner_t inner; + collision_t collision; + }; + + struct impl_data_t + { +#if IMMER_TAGGED_NODE + kind_t kind; +#endif + data_t data; + }; + + using impl_t = combine_standard_layout_t<impl_data_t, refs_t>; + + impl_t impl; + + constexpr static std::size_t sizeof_values_n(count_t count) + { + return std::max(sizeof(values_t), + immer_offsetof(values_t, d.buffer) + + sizeof(values_data_t::buffer) * count); + } + + constexpr static std::size_t sizeof_collision_n(count_t count) + { + return immer_offsetof(impl_t, d.data.collision.buffer) + + sizeof(collision_t::buffer) * count; + } + + constexpr static std::size_t sizeof_inner_n(count_t count) + { + return immer_offsetof(impl_t, d.data.inner.buffer) + + sizeof(inner_t::buffer) * count; + } + +#if IMMER_TAGGED_NODE + kind_t kind() const { return impl.d.kind; } +#endif + + auto values() + { + IMMER_ASSERT_TAGGED(kind() == kind_t::inner); + assert(impl.d.data.inner.values); + return (T*) &impl.d.data.inner.values->d.buffer; + } + + auto values() const + { + IMMER_ASSERT_TAGGED(kind() == kind_t::inner); + assert(impl.d.data.inner.values); + return (const T*) &impl.d.data.inner.values->d.buffer; + } + + auto children() + { + IMMER_ASSERT_TAGGED(kind() == kind_t::inner); + return (node_t**) &impl.d.data.inner.buffer; + } + + auto children() const + { + IMMER_ASSERT_TAGGED(kind() == kind_t::inner); + return (const node_t* const*) &impl.d.data.inner.buffer; + } + + auto datamap() const + { + IMMER_ASSERT_TAGGED(kind() == kind_t::inner); + return impl.d.data.inner.datamap; + } + + auto nodemap() const + { + IMMER_ASSERT_TAGGED(kind() == kind_t::inner); + return impl.d.data.inner.nodemap; + } + + auto collision_count() const + { + IMMER_ASSERT_TAGGED(kind() == kind_t::collision); + return impl.d.data.collision.count; + } + + T* collisions() + { + IMMER_ASSERT_TAGGED(kind() == kind_t::collision); + return (T*) &impl.d.data.collision.buffer; + } + + const T* collisions() const + { + IMMER_ASSERT_TAGGED(kind() == kind_t::collision); + return (const T*) &impl.d.data.collision.buffer; + } + + static refs_t& refs(const values_t* x) + { + return auto_const_cast(get<refs_t>(*x)); + } + static const ownee_t& ownee(const values_t* x) { return get<ownee_t>(*x); } + static ownee_t& ownee(values_t* x) { return get<ownee_t>(*x); } + + static refs_t& refs(const node_t* x) + { + return auto_const_cast(get<refs_t>(x->impl)); + } + static const ownee_t& ownee(const node_t* x) + { + return get<ownee_t>(x->impl); + } + static ownee_t& ownee(node_t* x) { return get<ownee_t>(x->impl); } + + static node_t* make_inner_n(count_t n) + { + assert(n <= branches<B>); + auto m = heap::allocate(sizeof_inner_n(n)); + auto p = new (m) node_t; +#if IMMER_TAGGED_NODE + p->impl.d.kind = node_t::kind_t::inner; +#endif + p->impl.d.data.inner.nodemap = 0; + p->impl.d.data.inner.datamap = 0; + p->impl.d.data.inner.values = nullptr; + return p; + } + + static node_t* make_inner_n(count_t n, values_t* values) + { + auto p = make_inner_n(n); + if (values) { + p->impl.d.data.inner.values = values; + refs(values).inc(); + } + return p; + } + + static node_t* make_inner_n(count_t n, count_t nv) + { + assert(nv <= branches<B>); + auto p = make_inner_n(n); + if (nv) { + try { + p->impl.d.data.inner.values = + new (heap::allocate(sizeof_values_n(nv))) values_t{}; + } catch (...) { + deallocate_inner(p, n); + throw; + } + } + return p; + } + + static node_t* make_inner_n(count_t n, count_t idx, node_t* child) + { + assert(n >= 1); + auto p = make_inner_n(n); + p->impl.d.data.inner.nodemap = bitmap_t{1u} << idx; + p->children()[0] = child; + return p; + } + + static node_t* make_inner_n(count_t n, bitmap_t bitmap, T x) + { + auto p = make_inner_n(n, 1); + p->impl.d.data.inner.datamap = bitmap; + try { + new (p->values()) T{std::move(x)}; + } catch (...) { + deallocate_inner(p, n, 1); + throw; + } + return p; + } + + static node_t* + make_inner_n(count_t n, count_t idx1, T x1, count_t idx2, T x2) + { + assert(idx1 != idx2); + auto p = make_inner_n(n, 2); + p->impl.d.data.inner.datamap = + (bitmap_t{1u} << idx1) | (bitmap_t{1u} << idx2); + auto assign = [&](auto&& x1, auto&& x2) { + auto vp = p->values(); + try { + new (vp) T{std::move(x1)}; + try { + new (vp + 1) T{std::move(x2)}; + } catch (...) { + vp->~T(); + throw; + } + } catch (...) { + deallocate_inner(p, n, 2); + throw; + } + }; + if (idx1 < idx2) + assign(x1, x2); + else + assign(x2, x1); + return p; + } + + static node_t* make_collision_n(count_t n) + { + auto m = heap::allocate(sizeof_collision_n(n)); + auto p = new (m) node_t; +#if IMMER_TAGGED_NODE + p->impl.d.kind = node_t::kind_t::collision; +#endif + p->impl.d.data.collision.count = n; + return p; + } + + static node_t* make_collision(T v1, T v2) + { + auto m = heap::allocate(sizeof_collision_n(2)); + auto p = new (m) node_t; +#if IMMER_TAGGED_NODE + p->impl.d.kind = node_t::kind_t::collision; +#endif + p->impl.d.data.collision.count = 2; + auto cols = p->collisions(); + try { + new (cols) T{std::move(v1)}; + try { + new (cols + 1) T{std::move(v2)}; + } catch (...) { + cols->~T(); + throw; + } + } catch (...) { + deallocate_collision(p, 2); + throw; + } + return p; + } + + static node_t* copy_collision_insert(node_t* src, T v) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::collision); + auto n = src->collision_count(); + auto dst = make_collision_n(n + 1); + auto srcp = src->collisions(); + auto dstp = dst->collisions(); + try { + new (dstp) T{std::move(v)}; + try { + std::uninitialized_copy(srcp, srcp + n, dstp + 1); + } catch (...) { + dstp->~T(); + throw; + } + } catch (...) { + deallocate_collision(dst, n + 1); + throw; + } + return dst; + } + + static node_t* copy_collision_remove(node_t* src, T* v) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::collision); + assert(src->collision_count() > 1); + auto n = src->collision_count(); + auto dst = make_collision_n(n - 1); + auto srcp = src->collisions(); + auto dstp = dst->collisions(); + try { + dstp = std::uninitialized_copy(srcp, v, dstp); + try { + std::uninitialized_copy(v + 1, srcp + n, dstp); + } catch (...) { + destroy(dst->collisions(), dstp); + throw; + } + } catch (...) { + deallocate_collision(dst, n - 1); + throw; + } + return dst; + } + + static node_t* copy_collision_replace(node_t* src, T* pos, T v) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::collision); + auto n = src->collision_count(); + auto dst = make_collision_n(n); + auto srcp = src->collisions(); + auto dstp = dst->collisions(); + assert(pos >= srcp && pos < srcp + n); + try { + new (dstp) T{std::move(v)}; + try { + dstp = std::uninitialized_copy(srcp, pos, dstp + 1); + try { + std::uninitialized_copy(pos + 1, srcp + n, dstp); + } catch (...) { + destroy(dst->collisions(), dstp); + throw; + } + } catch (...) { + dst->collisions()->~T(); + throw; + } + } catch (...) { + deallocate_collision(dst, n); + throw; + } + return dst; + } + + static node_t* + copy_inner_replace(node_t* src, count_t offset, node_t* child) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner); + auto n = popcount(src->nodemap()); + auto dst = make_inner_n(n, src->impl.d.data.inner.values); + auto srcp = src->children(); + auto dstp = dst->children(); + dst->impl.d.data.inner.datamap = src->datamap(); + dst->impl.d.data.inner.nodemap = src->nodemap(); + std::uninitialized_copy(srcp, srcp + n, dstp); + inc_nodes(srcp, n); + srcp[offset]->dec_unsafe(); + dstp[offset] = child; + return dst; + } + + static node_t* copy_inner_replace_value(node_t* src, count_t offset, T v) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner); + assert(offset < popcount(src->datamap())); + auto n = popcount(src->nodemap()); + auto nv = popcount(src->datamap()); + auto dst = make_inner_n(n, nv); + dst->impl.d.data.inner.datamap = src->datamap(); + dst->impl.d.data.inner.nodemap = src->nodemap(); + try { + std::uninitialized_copy( + src->values(), src->values() + nv, dst->values()); + try { + dst->values()[offset] = std::move(v); + } catch (...) { + destroy_n(dst->values(), nv); + throw; + } + } catch (...) { + deallocate_inner(dst, n, nv); + throw; + } + inc_nodes(src->children(), n); + std::uninitialized_copy( + src->children(), src->children() + n, dst->children()); + return dst; + } + + static node_t* copy_inner_replace_merged(node_t* src, + bitmap_t bit, + count_t voffset, + node_t* node) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner); + assert(!(src->nodemap() & bit)); + assert(src->datamap() & bit); + assert(voffset == popcount(src->datamap() & (bit - 1))); + auto n = popcount(src->nodemap()); + auto nv = popcount(src->datamap()); + auto dst = make_inner_n(n + 1, nv - 1); + auto noffset = popcount(src->nodemap() & (bit - 1)); + dst->impl.d.data.inner.datamap = src->datamap() & ~bit; + dst->impl.d.data.inner.nodemap = src->nodemap() | bit; + if (nv > 1) { + try { + std::uninitialized_copy( + src->values(), src->values() + voffset, dst->values()); + try { + std::uninitialized_copy(src->values() + voffset + 1, + src->values() + nv, + dst->values() + voffset); + } catch (...) { + destroy_n(dst->values(), voffset); + throw; + } + } catch (...) { + deallocate_inner(dst, n + 1, nv - 1); + throw; + } + } + inc_nodes(src->children(), n); + std::uninitialized_copy( + src->children(), src->children() + noffset, dst->children()); + std::uninitialized_copy(src->children() + noffset, + src->children() + n, + dst->children() + noffset + 1); + dst->children()[noffset] = node; + return dst; + } + + static node_t* copy_inner_replace_inline(node_t* src, + bitmap_t bit, + count_t noffset, + T value) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner); + assert(!(src->datamap() & bit)); + assert(src->nodemap() & bit); + assert(noffset == popcount(src->nodemap() & (bit - 1))); + auto n = popcount(src->nodemap()); + auto nv = popcount(src->datamap()); + auto dst = make_inner_n(n - 1, nv + 1); + auto voffset = popcount(src->datamap() & (bit - 1)); + dst->impl.d.data.inner.nodemap = src->nodemap() & ~bit; + dst->impl.d.data.inner.datamap = src->datamap() | bit; + try { + if (nv) + std::uninitialized_copy( + src->values(), src->values() + voffset, dst->values()); + try { + new (dst->values() + voffset) T{std::move(value)}; + try { + if (nv) + std::uninitialized_copy(src->values() + voffset, + src->values() + nv, + dst->values() + voffset + 1); + } catch (...) { + dst->values()[voffset].~T(); + throw; + } + } catch (...) { + destroy_n(dst->values(), voffset); + throw; + } + } catch (...) { + deallocate_inner(dst, n - 1, nv + 1); + throw; + } + inc_nodes(src->children(), n); + src->children()[noffset]->dec_unsafe(); + std::uninitialized_copy( + src->children(), src->children() + noffset, dst->children()); + std::uninitialized_copy(src->children() + noffset + 1, + src->children() + n, + dst->children() + noffset); + return dst; + } + + static node_t* + copy_inner_remove_value(node_t* src, bitmap_t bit, count_t voffset) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner); + assert(!(src->nodemap() & bit)); + assert(src->datamap() & bit); + assert(voffset == popcount(src->datamap() & (bit - 1))); + auto n = popcount(src->nodemap()); + auto nv = popcount(src->datamap()); + auto dst = make_inner_n(n, nv - 1); + dst->impl.d.data.inner.datamap = src->datamap() & ~bit; + dst->impl.d.data.inner.nodemap = src->nodemap(); + if (nv > 1) { + try { + std::uninitialized_copy( + src->values(), src->values() + voffset, dst->values()); + try { + std::uninitialized_copy(src->values() + voffset + 1, + src->values() + nv, + dst->values() + voffset); + } catch (...) { + destroy_n(dst->values(), voffset); + throw; + } + } catch (...) { + deallocate_inner(dst, n, nv - 1); + throw; + } + } + inc_nodes(src->children(), n); + std::uninitialized_copy( + src->children(), src->children() + n, dst->children()); + return dst; + } + + static node_t* copy_inner_insert_value(node_t* src, bitmap_t bit, T v) + { + IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner); + auto n = popcount(src->nodemap()); + auto nv = popcount(src->datamap()); + auto offset = popcount(src->datamap() & (bit - 1)); + auto dst = make_inner_n(n, nv + 1); + dst->impl.d.data.inner.datamap = src->datamap() | bit; + dst->impl.d.data.inner.nodemap = src->nodemap(); + try { + if (nv) + std::uninitialized_copy( + src->values(), src->values() + offset, dst->values()); + try { + new (dst->values() + offset) T{std::move(v)}; + try { + if (nv) + std::uninitialized_copy(src->values() + offset, + src->values() + nv, + dst->values() + offset + 1); + } catch (...) { + dst->values()[offset].~T(); + throw; + } + } catch (...) { + destroy_n(dst->values(), offset); + throw; + } + } catch (...) { + deallocate_inner(dst, n, nv + 1); + throw; + } + inc_nodes(src->children(), n); + std::uninitialized_copy( + src->children(), src->children() + n, dst->children()); + return dst; + } + + static node_t* + make_merged(shift_t shift, T v1, hash_t hash1, T v2, hash_t hash2) + { + if (shift < max_shift<B>) { + auto idx1 = hash1 & (mask<B> << shift); + auto idx2 = hash2 & (mask<B> << shift); + if (idx1 == idx2) { + auto merged = make_merged( + shift + B, std::move(v1), hash1, std::move(v2), hash2); + try { + return make_inner_n(1, idx1 >> shift, merged); + } catch (...) { + delete_deep_shift(merged, shift + B); + throw; + } + } else { + return make_inner_n(0, + idx1 >> shift, + std::move(v1), + idx2 >> shift, + std::move(v2)); + } + } else { + return make_collision(std::move(v1), std::move(v2)); + } + } + + node_t* inc() + { + refs(this).inc(); + return this; + } + + const node_t* inc() const + { + refs(this).inc(); + return this; + } + + bool dec() const { return refs(this).dec(); } + void dec_unsafe() const { refs(this).dec_unsafe(); } + + static void inc_nodes(node_t** p, count_t n) + { + for (auto i = p, e = i + n; i != e; ++i) + refs(*i).inc(); + } + + static void delete_values(values_t* p, count_t n) + { + assert(p); + deallocate_values(p, n); + } + + static void delete_inner(node_t* p) + { + assert(p); + IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner); + auto vp = p->impl.d.data.inner.values; + if (vp && refs(vp).dec()) + delete_values(vp, popcount(p->datamap())); + deallocate_inner(p, popcount(p->nodemap())); + } + + static void delete_collision(node_t* p) + { + assert(p); + IMMER_ASSERT_TAGGED(p->kind() == kind_t::collision); + auto n = p->collision_count(); + deallocate_collision(p, n); + } + + static void delete_deep(node_t* p, shift_t s) + { + if (s == max_depth<B>) + delete_collision(p); + else { + auto fst = p->children(); + auto lst = fst + popcount(p->nodemap()); + for (; fst != lst; ++fst) + if ((*fst)->dec()) + delete_deep(*fst, s + 1); + delete_inner(p); + } + } + + static void delete_deep_shift(node_t* p, shift_t s) + { + if (s == max_shift<B>) + delete_collision(p); + else { + auto fst = p->children(); + auto lst = fst + popcount(p->nodemap()); + for (; fst != lst; ++fst) + if ((*fst)->dec()) + delete_deep_shift(*fst, s + B); + delete_inner(p); + } + } + + static void deallocate_values(values_t* p, count_t n) + { + destroy_n((T*) &p->d.buffer, n); + heap::deallocate(node_t::sizeof_values_n(n), p); + } + + static void deallocate_collision(node_t* p, count_t n) + { + destroy_n(p->collisions(), n); + heap::deallocate(node_t::sizeof_collision_n(n), p); + } + + static void deallocate_inner(node_t* p, count_t n) + { + heap::deallocate(node_t::sizeof_inner_n(n), p); + } + + static void deallocate_inner(node_t* p, count_t n, count_t nv) + { + assert(nv); + heap::deallocate(node_t::sizeof_values_n(nv), + p->impl.d.data.inner.values); + heap::deallocate(node_t::sizeof_inner_n(n), p); + } +}; + +} // namespace hamts +} // namespace detail +} // namespace immer |