diff options
Diffstat (limited to 'third_party/immer/immer/detail/hamts')
| -rw-r--r-- | third_party/immer/immer/detail/hamts/bits.hpp | 108 | ||||
| -rw-r--r-- | third_party/immer/immer/detail/hamts/champ.hpp | 473 | ||||
| -rw-r--r-- | third_party/immer/immer/detail/hamts/champ_iterator.hpp | 148 | ||||
| -rw-r--r-- | third_party/immer/immer/detail/hamts/node.hpp | 717 |
4 files changed, 0 insertions, 1446 deletions
diff --git a/third_party/immer/immer/detail/hamts/bits.hpp b/third_party/immer/immer/detail/hamts/bits.hpp deleted file mode 100644 index b02caf7706..0000000000 --- a/third_party/immer/immer/detail/hamts/bits.hpp +++ /dev/null @@ -1,108 +0,0 @@ -// -// 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/third_party/immer/immer/detail/hamts/champ.hpp b/third_party/immer/immer/detail/hamts/champ.hpp deleted file mode 100644 index e3b55d397c..0000000000 --- a/third_party/immer/immer/detail/hamts/champ.hpp +++ /dev/null @@ -1,473 +0,0 @@ -// -// 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/third_party/immer/immer/detail/hamts/champ_iterator.hpp b/third_party/immer/immer/detail/hamts/champ_iterator.hpp deleted file mode 100644 index 72673b41be..0000000000 --- a/third_party/immer/immer/detail/hamts/champ_iterator.hpp +++ /dev/null @@ -1,148 +0,0 @@ -// -// 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/third_party/immer/immer/detail/hamts/node.hpp b/third_party/immer/immer/detail/hamts/node.hpp deleted file mode 100644 index 216e82b787..0000000000 --- a/third_party/immer/immer/detail/hamts/node.hpp +++ /dev/null @@ -1,717 +0,0 @@ -// -// 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 |