about summary refs log tree commit diff
path: root/immer/detail/rbts/node.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'immer/detail/rbts/node.hpp')
-rw-r--r--immer/detail/rbts/node.hpp932
1 files changed, 932 insertions, 0 deletions
diff --git a/immer/detail/rbts/node.hpp b/immer/detail/rbts/node.hpp
new file mode 100644
index 000000000000..e54e569636ac
--- /dev/null
+++ b/immer/detail/rbts/node.hpp
@@ -0,0 +1,932 @@
+//
+// 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/rbts/bits.hpp>
+#include <immer/detail/util.hpp>
+#include <immer/heap/tags.hpp>
+
+#include <cassert>
+#include <cstddef>
+#include <memory>
+#include <type_traits>
+
+namespace immer {
+namespace detail {
+namespace rbts {
+
+template <typename T, typename MemoryPolicy, bits_t B, bits_t BL>
+struct node
+{
+    static constexpr auto bits      = B;
+    static constexpr auto bits_leaf = BL;
+
+    using node_t      = node;
+    using memory      = MemoryPolicy;
+    using heap_policy = typename memory::heap;
+    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;
+
+    static constexpr bool embed_relaxed = memory::prefer_fewer_bigger_objects;
+
+    enum class kind_t
+    {
+        leaf,
+        inner
+    };
+
+    struct relaxed_data_t
+    {
+        count_t count;
+        size_t sizes[branches<B>];
+    };
+
+    using relaxed_data_with_meta_t =
+        combine_standard_layout_t<relaxed_data_t, refs_t, ownee_t>;
+
+    using relaxed_data_no_meta_t = combine_standard_layout_t<relaxed_data_t>;
+
+    using relaxed_t = std::conditional_t<embed_relaxed,
+                                         relaxed_data_no_meta_t,
+                                         relaxed_data_with_meta_t>;
+
+    struct leaf_t
+    {
+        aligned_storage_for<T> buffer;
+    };
+
+    struct inner_t
+    {
+        relaxed_t* relaxed;
+        aligned_storage_for<node_t*> buffer;
+    };
+
+    union data_t
+    {
+        inner_t inner;
+        leaf_t leaf;
+    };
+
+    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, ownee_t>;
+
+    impl_t impl;
+
+    // assume that we need to keep headroom space in the node when we
+    // are doing reference counting, since any node may become
+    // transient when it has only one reference
+    constexpr static bool keep_headroom = !std::is_empty<refs_t>{};
+
+    constexpr static std::size_t sizeof_packed_leaf_n(count_t count)
+    {
+        return immer_offsetof(impl_t, d.data.leaf.buffer) +
+               sizeof(leaf_t::buffer) * count;
+    }
+
+    constexpr static std::size_t sizeof_packed_inner_n(count_t count)
+    {
+        return immer_offsetof(impl_t, d.data.inner.buffer) +
+               sizeof(inner_t::buffer) * count;
+    }
+
+    constexpr static std::size_t sizeof_packed_relaxed_n(count_t count)
+    {
+        return immer_offsetof(relaxed_t, d.sizes) + sizeof(size_t) * count;
+    }
+
+    constexpr static std::size_t sizeof_packed_inner_r_n(count_t count)
+    {
+        return embed_relaxed ? sizeof_packed_inner_n(count) +
+                                   sizeof_packed_relaxed_n(count)
+                             : sizeof_packed_inner_n(count);
+    }
+
+    constexpr static std::size_t max_sizeof_leaf =
+        sizeof_packed_leaf_n(branches<BL>);
+
+    constexpr static std::size_t max_sizeof_inner =
+        sizeof_packed_inner_n(branches<B>);
+
+    constexpr static std::size_t max_sizeof_relaxed =
+        sizeof_packed_relaxed_n(branches<B>);
+
+    constexpr static std::size_t max_sizeof_inner_r =
+        sizeof_packed_inner_r_n(branches<B>);
+
+    constexpr static std::size_t sizeof_inner_n(count_t n)
+    {
+        return keep_headroom ? max_sizeof_inner : sizeof_packed_inner_n(n);
+    }
+
+    constexpr static std::size_t sizeof_inner_r_n(count_t n)
+    {
+        return keep_headroom ? max_sizeof_inner_r : sizeof_packed_inner_r_n(n);
+    }
+
+    constexpr static std::size_t sizeof_relaxed_n(count_t n)
+    {
+        return keep_headroom ? max_sizeof_relaxed : sizeof_packed_relaxed_n(n);
+    }
+
+    constexpr static std::size_t sizeof_leaf_n(count_t n)
+    {
+        return keep_headroom ? max_sizeof_leaf : sizeof_packed_leaf_n(n);
+    }
+
+    using heap =
+        typename heap_policy::template optimized<max_sizeof_inner>::type;
+
+#if IMMER_TAGGED_NODE
+    kind_t kind() const { return impl.d.kind; }
+#endif
+
+    relaxed_t* relaxed()
+    {
+        IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
+        return impl.d.data.inner.relaxed;
+    }
+
+    const relaxed_t* relaxed() const
+    {
+        IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
+        return impl.d.data.inner.relaxed;
+    }
+
+    node_t** inner()
+    {
+        IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
+        return reinterpret_cast<node_t**>(&impl.d.data.inner.buffer);
+    }
+
+    T* leaf()
+    {
+        IMMER_ASSERT_TAGGED(kind() == kind_t::leaf);
+        return reinterpret_cast<T*>(&impl.d.data.leaf.buffer);
+    }
+
+    static refs_t& refs(const relaxed_t* x)
+    {
+        return auto_const_cast(get<refs_t>(*x));
+    }
+    static const ownee_t& ownee(const relaxed_t* x) { return get<ownee_t>(*x); }
+    static ownee_t& ownee(relaxed_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;
+        p->impl.d.data.inner.relaxed = nullptr;
+#if IMMER_TAGGED_NODE
+        p->impl.d.kind = node_t::kind_t::inner;
+#endif
+        return p;
+    }
+
+    static node_t* make_inner_e(edit_t e)
+    {
+        auto m                       = heap::allocate(max_sizeof_inner);
+        auto p                       = new (m) node_t;
+        ownee(p)                     = e;
+        p->impl.d.data.inner.relaxed = nullptr;
+#if IMMER_TAGGED_NODE
+        p->impl.d.kind = node_t::kind_t::inner;
+#endif
+        return p;
+    }
+
+    static node_t* make_inner_r_n(count_t n)
+    {
+        assert(n <= branches<B>);
+        auto mp = heap::allocate(sizeof_inner_r_n(n));
+        auto mr = static_cast<void*>(nullptr);
+        if (embed_relaxed) {
+            mr = reinterpret_cast<unsigned char*>(mp) + sizeof_inner_n(n);
+        } else {
+            try {
+                mr = heap::allocate(sizeof_relaxed_n(n), norefs_tag{});
+            } catch (...) {
+                heap::deallocate(sizeof_inner_r_n(n), mp);
+                throw;
+            }
+        }
+        auto p                       = new (mp) node_t;
+        auto r                       = new (mr) relaxed_t;
+        r->d.count                   = 0;
+        p->impl.d.data.inner.relaxed = r;
+#if IMMER_TAGGED_NODE
+        p->impl.d.kind = node_t::kind_t::inner;
+#endif
+        return p;
+    }
+
+    static node_t* make_inner_sr_n(count_t n, relaxed_t* r)
+    {
+        return static_if<embed_relaxed, node_t*>(
+            [&](auto) { return node_t::make_inner_r_n(n); },
+            [&](auto) {
+                auto p =
+                    new (heap::allocate(node_t::sizeof_inner_r_n(n))) node_t;
+                assert(r->d.count >= n);
+                node_t::refs(r).inc();
+                p->impl.d.data.inner.relaxed = r;
+#if IMMER_TAGGED_NODE
+                p->impl.d.kind = node_t::kind_t::inner;
+#endif
+                return p;
+            });
+    }
+
+    static node_t* make_inner_r_e(edit_t e)
+    {
+        auto mp = heap::allocate(max_sizeof_inner_r);
+        auto mr = static_cast<void*>(nullptr);
+        if (embed_relaxed) {
+            mr = reinterpret_cast<unsigned char*>(mp) + max_sizeof_inner;
+        } else {
+            try {
+                mr = heap::allocate(max_sizeof_relaxed, norefs_tag{});
+            } catch (...) {
+                heap::deallocate(max_sizeof_inner_r, mp);
+                throw;
+            }
+        }
+        auto p   = new (mp) node_t;
+        auto r   = new (mr) relaxed_t;
+        ownee(p) = e;
+        static_if<!embed_relaxed>([&](auto) { node_t::ownee(r) = e; });
+        r->d.count                   = 0;
+        p->impl.d.data.inner.relaxed = r;
+#if IMMER_TAGGED_NODE
+        p->impl.d.kind = node_t::kind_t::inner;
+#endif
+        return p;
+    }
+
+    static node_t* make_inner_sr_e(edit_t e, relaxed_t* r)
+    {
+        return static_if<embed_relaxed, node_t*>(
+            [&](auto) { return node_t::make_inner_r_e(e); },
+            [&](auto) {
+                auto p =
+                    new (heap::allocate(node_t::max_sizeof_inner_r)) node_t;
+                node_t::refs(r).inc();
+                p->impl.d.data.inner.relaxed = r;
+                node_t::ownee(p)             = e;
+#if IMMER_TAGGED_NODE
+                p->impl.d.kind = node_t::kind_t::inner;
+#endif
+                return p;
+            });
+    }
+
+    static node_t* make_leaf_n(count_t n)
+    {
+        assert(n <= branches<BL>);
+        auto p = new (heap::allocate(sizeof_leaf_n(n))) node_t;
+#if IMMER_TAGGED_NODE
+        p->impl.d.kind = node_t::kind_t::leaf;
+#endif
+        return p;
+    }
+
+    static node_t* make_leaf_e(edit_t e)
+    {
+        auto p   = new (heap::allocate(max_sizeof_leaf)) node_t;
+        ownee(p) = e;
+#if IMMER_TAGGED_NODE
+        p->impl.d.kind = node_t::kind_t::leaf;
+#endif
+        return p;
+    }
+
+    static node_t* make_inner_n(count_t n, node_t* x)
+    {
+        assert(n >= 1);
+        auto p        = make_inner_n(n);
+        p->inner()[0] = x;
+        return p;
+    }
+
+    static node_t* make_inner_n(edit_t n, node_t* x)
+    {
+        assert(n >= 1);
+        auto p        = make_inner_n(n);
+        p->inner()[0] = x;
+        return p;
+    }
+
+    static node_t* make_inner_n(count_t n, node_t* x, node_t* y)
+    {
+        assert(n >= 2);
+        auto p        = make_inner_n(n);
+        p->inner()[0] = x;
+        p->inner()[1] = y;
+        return p;
+    }
+
+    static node_t* make_inner_r_n(count_t n, node_t* x)
+    {
+        assert(n >= 1);
+        auto p        = make_inner_r_n(n);
+        auto r        = p->relaxed();
+        p->inner()[0] = x;
+        r->d.count    = 1;
+        return p;
+    }
+
+    static node_t* make_inner_r_n(count_t n, node_t* x, size_t xs)
+    {
+        assert(n >= 1);
+        auto p        = make_inner_r_n(n);
+        auto r        = p->relaxed();
+        p->inner()[0] = x;
+        r->d.sizes[0] = xs;
+        r->d.count    = 1;
+        return p;
+    }
+
+    static node_t* make_inner_r_n(count_t n, node_t* x, node_t* y)
+    {
+        assert(n >= 2);
+        auto p        = make_inner_r_n(n);
+        auto r        = p->relaxed();
+        p->inner()[0] = x;
+        p->inner()[1] = y;
+        r->d.count    = 2;
+        return p;
+    }
+
+    static node_t* make_inner_r_n(count_t n, node_t* x, size_t xs, node_t* y)
+    {
+        assert(n >= 2);
+        auto p        = make_inner_r_n(n);
+        auto r        = p->relaxed();
+        p->inner()[0] = x;
+        p->inner()[1] = y;
+        r->d.sizes[0] = xs;
+        r->d.count    = 2;
+        return p;
+    }
+
+    static node_t*
+    make_inner_r_n(count_t n, node_t* x, size_t xs, node_t* y, size_t ys)
+    {
+        assert(n >= 2);
+        auto p        = make_inner_r_n(n);
+        auto r        = p->relaxed();
+        p->inner()[0] = x;
+        p->inner()[1] = y;
+        r->d.sizes[0] = xs;
+        r->d.sizes[1] = xs + ys;
+        r->d.count    = 2;
+        return p;
+    }
+
+    static node_t* make_inner_r_n(count_t n,
+                                  node_t* x,
+                                  size_t xs,
+                                  node_t* y,
+                                  size_t ys,
+                                  node_t* z,
+                                  size_t zs)
+    {
+        assert(n >= 3);
+        auto p        = make_inner_r_n(n);
+        auto r        = p->relaxed();
+        p->inner()[0] = x;
+        p->inner()[1] = y;
+        p->inner()[2] = z;
+        r->d.sizes[0] = xs;
+        r->d.sizes[1] = xs + ys;
+        r->d.sizes[2] = xs + ys + zs;
+        r->d.count    = 3;
+        return p;
+    }
+
+    template <typename U>
+    static node_t* make_leaf_n(count_t n, U&& x)
+    {
+        assert(n >= 1);
+        auto p = make_leaf_n(n);
+        try {
+            new (p->leaf()) T{std::forward<U>(x)};
+        } catch (...) {
+            heap::deallocate(node_t::sizeof_leaf_n(n), p);
+            throw;
+        }
+        return p;
+    }
+
+    template <typename U>
+    static node_t* make_leaf_e(edit_t e, U&& x)
+    {
+        auto p = make_leaf_e(e);
+        try {
+            new (p->leaf()) T{std::forward<U>(x)};
+        } catch (...) {
+            heap::deallocate(node_t::max_sizeof_leaf, p);
+            throw;
+        }
+        return p;
+    }
+
+    static node_t* make_path(shift_t shift, node_t* node)
+    {
+        IMMER_ASSERT_TAGGED(node->kind() == kind_t::leaf);
+        if (shift == endshift<B, BL>)
+            return node;
+        else {
+            auto n = node_t::make_inner_n(1);
+            try {
+                n->inner()[0] = make_path(shift - B, node);
+            } catch (...) {
+                heap::deallocate(node_t::sizeof_inner_n(1), n);
+                throw;
+            }
+            return n;
+        }
+    }
+
+    static node_t* make_path_e(edit_t e, shift_t shift, node_t* node)
+    {
+        IMMER_ASSERT_TAGGED(node->kind() == kind_t::leaf);
+        if (shift == endshift<B, BL>)
+            return node;
+        else {
+            auto n = node_t::make_inner_e(e);
+            try {
+                n->inner()[0] = make_path_e(e, shift - B, node);
+            } catch (...) {
+                heap::deallocate(node_t::max_sizeof_inner, n);
+                throw;
+            }
+            return n;
+        }
+    }
+
+    static node_t* copy_inner(node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_n(n);
+        inc_nodes(src->inner(), n);
+        std::uninitialized_copy(src->inner(), src->inner() + n, dst->inner());
+        return dst;
+    }
+
+    static node_t* copy_inner_n(count_t allocn, node_t* src, count_t n)
+    {
+        assert(allocn >= n);
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_n(allocn);
+        return do_copy_inner(dst, src, n);
+    }
+
+    static node_t* copy_inner_e(edit_t e, node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_e(e);
+        return do_copy_inner(dst, src, n);
+    }
+
+    static node_t* do_copy_inner(node_t* dst, node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(dst->kind() == kind_t::inner);
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto p = src->inner();
+        inc_nodes(p, n);
+        std::uninitialized_copy(p, p + n, dst->inner());
+        return dst;
+    }
+
+    static node_t* copy_inner_r(node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_r_n(n);
+        return do_copy_inner_r(dst, src, n);
+    }
+
+    static node_t* copy_inner_r_n(count_t allocn, node_t* src, count_t n)
+    {
+        assert(allocn >= n);
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_r_n(allocn);
+        return do_copy_inner_r(dst, src, n);
+    }
+
+    static node_t* copy_inner_r_e(edit_t e, node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_r_e(e);
+        return do_copy_inner_r(dst, src, n);
+    }
+
+    static node_t* copy_inner_sr_e(edit_t e, node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto dst = make_inner_sr_e(e, src->relaxed());
+        return do_copy_inner_sr(dst, src, n);
+    }
+
+    static node_t* do_copy_inner_r(node_t* dst, node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(dst->kind() == kind_t::inner);
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
+        auto src_r = src->relaxed();
+        auto dst_r = dst->relaxed();
+        inc_nodes(src->inner(), n);
+        std::copy(src->inner(), src->inner() + n, dst->inner());
+        std::copy(src_r->d.sizes, src_r->d.sizes + n, dst_r->d.sizes);
+        dst_r->d.count = n;
+        return dst;
+    }
+
+    static node_t* do_copy_inner_sr(node_t* dst, node_t* src, count_t n)
+    {
+        if (embed_relaxed)
+            return do_copy_inner_r(dst, src, n);
+        else {
+            inc_nodes(src->inner(), n);
+            std::copy(src->inner(), src->inner() + n, dst->inner());
+            return dst;
+        }
+    }
+
+    static node_t* copy_leaf(node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::leaf);
+        auto dst = make_leaf_n(n);
+        try {
+            std::uninitialized_copy(src->leaf(), src->leaf() + n, dst->leaf());
+        } catch (...) {
+            heap::deallocate(node_t::sizeof_leaf_n(n), dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static node_t* copy_leaf_e(edit_t e, node_t* src, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::leaf);
+        auto dst = make_leaf_e(e);
+        try {
+            std::uninitialized_copy(src->leaf(), src->leaf() + n, dst->leaf());
+        } catch (...) {
+            heap::deallocate(node_t::max_sizeof_leaf, dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static node_t* copy_leaf_n(count_t allocn, node_t* src, count_t n)
+    {
+        assert(allocn >= n);
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::leaf);
+        auto dst = make_leaf_n(allocn);
+        try {
+            std::uninitialized_copy(src->leaf(), src->leaf() + n, dst->leaf());
+        } catch (...) {
+            heap::deallocate(node_t::sizeof_leaf_n(allocn), dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static node_t* copy_leaf(node_t* src1, count_t n1, node_t* src2, count_t n2)
+    {
+        IMMER_ASSERT_TAGGED(src1->kind() == kind_t::leaf);
+        IMMER_ASSERT_TAGGED(src2->kind() == kind_t::leaf);
+        auto dst = make_leaf_n(n1 + n2);
+        try {
+            std::uninitialized_copy(
+                src1->leaf(), src1->leaf() + n1, dst->leaf());
+        } catch (...) {
+            heap::deallocate(node_t::sizeof_leaf_n(n1 + n2), dst);
+            throw;
+        }
+        try {
+            std::uninitialized_copy(
+                src2->leaf(), src2->leaf() + n2, dst->leaf() + n1);
+        } catch (...) {
+            destroy_n(dst->leaf(), n1);
+            heap::deallocate(node_t::sizeof_leaf_n(n1 + n2), dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static node_t*
+    copy_leaf_e(edit_t e, node_t* src1, count_t n1, node_t* src2, count_t n2)
+    {
+        IMMER_ASSERT_TAGGED(src1->kind() == kind_t::leaf);
+        IMMER_ASSERT_TAGGED(src2->kind() == kind_t::leaf);
+        auto dst = make_leaf_e(e);
+        try {
+            std::uninitialized_copy(
+                src1->leaf(), src1->leaf() + n1, dst->leaf());
+        } catch (...) {
+            heap::deallocate(max_sizeof_leaf, dst);
+            throw;
+        }
+        try {
+            std::uninitialized_copy(
+                src2->leaf(), src2->leaf() + n2, dst->leaf() + n1);
+        } catch (...) {
+            destroy_n(dst->leaf(), n1);
+            heap::deallocate(max_sizeof_leaf, dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static node_t* copy_leaf_e(edit_t e, node_t* src, count_t idx, count_t last)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::leaf);
+        auto dst = make_leaf_e(e);
+        try {
+            std::uninitialized_copy(
+                src->leaf() + idx, src->leaf() + last, dst->leaf());
+        } catch (...) {
+            heap::deallocate(max_sizeof_leaf, dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static node_t* copy_leaf(node_t* src, count_t idx, count_t last)
+    {
+        IMMER_ASSERT_TAGGED(src->kind() == kind_t::leaf);
+        auto dst = make_leaf_n(last - idx);
+        try {
+            std::uninitialized_copy(
+                src->leaf() + idx, src->leaf() + last, dst->leaf());
+        } catch (...) {
+            heap::deallocate(node_t::sizeof_leaf_n(last - idx), dst);
+            throw;
+        }
+        return dst;
+    }
+
+    template <typename U>
+    static node_t* copy_leaf_emplace(node_t* src, count_t n, U&& x)
+    {
+        auto dst = copy_leaf_n(n + 1, src, n);
+        try {
+            new (dst->leaf() + n) T{std::forward<U>(x)};
+        } catch (...) {
+            destroy_n(dst->leaf(), n);
+            heap::deallocate(node_t::sizeof_leaf_n(n + 1), dst);
+            throw;
+        }
+        return dst;
+    }
+
+    static void delete_inner(node_t* p, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner);
+        assert(!p->relaxed());
+        heap::deallocate(ownee(p).owned() ? node_t::max_sizeof_inner
+                                          : node_t::sizeof_inner_n(n),
+                         p);
+    }
+
+    static void delete_inner_e(node_t* p)
+    {
+        IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner);
+        assert(!p->relaxed());
+        heap::deallocate(node_t::max_sizeof_inner, p);
+    }
+
+    static void delete_inner_any(node_t* p, count_t n)
+    {
+        if (p->relaxed())
+            delete_inner_r(p, n);
+        else
+            delete_inner(p, n);
+    }
+
+    static void delete_inner_r(node_t* p, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner);
+        auto r = p->relaxed();
+        assert(r);
+        static_if<!embed_relaxed>([&](auto) {
+            if (node_t::refs(r).dec())
+                heap::deallocate(node_t::ownee(r).owned()
+                                     ? node_t::max_sizeof_relaxed
+                                     : node_t::sizeof_relaxed_n(n),
+                                 r);
+        });
+        heap::deallocate(ownee(p).owned() ? node_t::max_sizeof_inner_r
+                                          : node_t::sizeof_inner_r_n(n),
+                         p);
+    }
+
+    static void delete_inner_r_e(node_t* p)
+    {
+        IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner);
+        auto r = p->relaxed();
+        assert(r);
+        static_if<!embed_relaxed>([&](auto) {
+            if (node_t::refs(r).dec())
+                heap::deallocate(node_t::max_sizeof_relaxed, r);
+        });
+        heap::deallocate(node_t::max_sizeof_inner_r, p);
+    }
+
+    static void delete_leaf(node_t* p, count_t n)
+    {
+        IMMER_ASSERT_TAGGED(p->kind() == kind_t::leaf);
+        destroy_n(p->leaf(), n);
+        heap::deallocate(ownee(p).owned() ? node_t::max_sizeof_leaf
+                                          : node_t::sizeof_leaf_n(n),
+                         p);
+    }
+
+    bool can_mutate(edit_t e) const
+    {
+        return refs(this).unique() || ownee(this).can_mutate(e);
+    }
+
+    bool can_relax() const { return !embed_relaxed || relaxed(); }
+
+    relaxed_t* ensure_mutable_relaxed(edit_t e)
+    {
+        auto src_r = relaxed();
+        return static_if<embed_relaxed, relaxed_t*>(
+            [&](auto) { return src_r; },
+            [&](auto) {
+                if (node_t::refs(src_r).unique() ||
+                    node_t::ownee(src_r).can_mutate(e))
+                    return src_r;
+                else {
+                    if (src_r)
+                        node_t::refs(src_r).dec_unsafe();
+                    auto dst_r = impl.d.data.inner.relaxed =
+                        new (heap::allocate(max_sizeof_relaxed)) relaxed_t;
+                    node_t::ownee(dst_r) = e;
+                    return dst_r;
+                }
+            });
+    }
+
+    relaxed_t* ensure_mutable_relaxed_e(edit_t e, edit_t ec)
+    {
+        auto src_r = relaxed();
+        return static_if<embed_relaxed, relaxed_t*>(
+            [&](auto) { return src_r; },
+            [&](auto) {
+                if (src_r && (node_t::refs(src_r).unique() ||
+                              node_t::ownee(src_r).can_mutate(e))) {
+                    node_t::ownee(src_r) = ec;
+                    return src_r;
+                } else {
+                    if (src_r)
+                        node_t::refs(src_r).dec_unsafe();
+                    auto dst_r = impl.d.data.inner.relaxed =
+                        new (heap::allocate(max_sizeof_relaxed)) relaxed_t;
+                    node_t::ownee(dst_r) = ec;
+                    return dst_r;
+                }
+            });
+    }
+
+    relaxed_t* ensure_mutable_relaxed_n(edit_t e, count_t n)
+    {
+        auto src_r = relaxed();
+        return static_if<embed_relaxed, relaxed_t*>(
+            [&](auto) { return src_r; },
+            [&](auto) {
+                if (node_t::refs(src_r).unique() ||
+                    node_t::ownee(src_r).can_mutate(e))
+                    return src_r;
+                else {
+                    if (src_r)
+                        node_t::refs(src_r).dec_unsafe();
+                    auto dst_r =
+                        new (heap::allocate(max_sizeof_relaxed)) relaxed_t;
+                    std::copy(
+                        src_r->d.sizes, src_r->d.sizes + n, dst_r->d.sizes);
+                    node_t::ownee(dst_r)             = e;
+                    return impl.d.data.inner.relaxed = dst_r;
+                }
+            });
+    }
+
+    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();
+    }
+
+#if IMMER_TAGGED_NODE
+    shift_t compute_shift()
+    {
+        if (kind() == kind_t::leaf)
+            return endshift<B, BL>;
+        else
+            return B + inner()[0]->compute_shift();
+    }
+#endif
+
+    bool check(shift_t shift, size_t size)
+    {
+#if IMMER_DEBUG_DEEP_CHECK
+        assert(size > 0);
+        if (shift == endshift<B, BL>) {
+            IMMER_ASSERT_TAGGED(kind() == kind_t::leaf);
+            assert(size <= branches<BL>);
+        } else if (auto r = relaxed()) {
+            auto count = r->d.count;
+            assert(count > 0);
+            assert(count <= branches<B>);
+            if (r->d.sizes[count - 1] != size) {
+                IMMER_TRACE_F("check");
+                IMMER_TRACE_E(r->d.sizes[count - 1]);
+                IMMER_TRACE_E(size);
+            }
+            assert(r->d.sizes[count - 1] == size);
+            for (auto i = 1; i < count; ++i)
+                assert(r->d.sizes[i - 1] < r->d.sizes[i]);
+            auto last_size = size_t{};
+            for (auto i = 0; i < count; ++i) {
+                assert(inner()[i]->check(shift - B, r->d.sizes[i] - last_size));
+                last_size = r->d.sizes[i];
+            }
+        } else {
+            assert(size <= branches<B> << shift);
+            auto count =
+                (size >> shift) + (size - ((size >> shift) << shift) > 0);
+            assert(count <= branches<B>);
+            if (count) {
+                for (auto i = 1; i < count - 1; ++i)
+                    assert(inner()[i]->check(shift - B, 1 << shift));
+                assert(inner()[count - 1]->check(
+                    shift - B, size - ((count - 1) << shift)));
+            }
+        }
+#endif // IMMER_DEBUG_DEEP_CHECK
+        return true;
+    }
+};
+
+template <typename T, typename MP, bits_t B>
+constexpr bits_t derive_bits_leaf_aux()
+{
+    using node_t               = node<T, MP, B, B>;
+    constexpr auto sizeof_elem = sizeof(T);
+    constexpr auto space =
+        node_t::max_sizeof_inner - node_t::sizeof_packed_leaf_n(0);
+    constexpr auto full_elems = space / sizeof_elem;
+    constexpr auto BL         = log2(full_elems);
+    return BL;
+}
+
+template <typename T, typename MP, bits_t B>
+constexpr bits_t derive_bits_leaf = derive_bits_leaf_aux<T, MP, B>();
+
+} // namespace rbts
+} // namespace detail
+} // namespace immer