Squashed 'third_party/immer/' content from commit ad3e3556d

git-subtree-dir: third_party/immer
git-subtree-split: ad3e3556d38bb75966dd24c61a774970a7c7957e

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