/src/immer/immer/detail/rbts/rbtree.hpp

Source
//
// 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/rbts/node.hpp>
#include <immer/detail/rbts/operations.hpp>
#include <immer/detail/rbts/position.hpp>
#include <immer/detail/type_traits.hpp>

#include <cassert>
#include <memory>
#include <numeric>
#include <stdexcept>

namespace immer {
namespace detail {
namespace rbts {

template <typename T, typename MemoryPolicy, bits_t B, bits_t BL>
struct rbtree
{
    using node_t  = node<T, MemoryPolicy, B, BL>;
    using edit_t  = typename node_t::edit_t;
    using owner_t = typename MemoryPolicy::transience_t::owner;

    size_t size;
    shift_t shift;
    node_t* root;
    node_t* tail;

    constexpr static size_t max_size()
    {
        auto S = sizeof(size_t) * 8;
        return (size_t{1} << BL) * ipow(size_t{1} << B, (S - BL) / B);
    }

    static node_t* empty_root()
    {
        static const auto empty_ = node_t::make_inner_n(0u);
        return empty_->inc();
    }

    static node_t* empty_tail()
    {
        static const auto empty_ = node_t::make_leaf_n(0u);
        return empty_->inc();
    }

    template <typename U>
    static auto from_initializer_list(std::initializer_list<U> values)
    {
        auto e      = owner_t{};
        auto result = rbtree{};
        for (auto&& v : values)
            result.push_back_mut(e, v);
        return result;
    }

    template <typename Iter,
              typename Sent,
              std::enable_if_t<compatible_sentinel_v<Iter, Sent>, bool> = true>
    static auto from_range(Iter first, Sent last)
    {
        auto e      = owner_t{};
        auto result = rbtree{};
        for (; first != last; ++first)
            result.push_back_mut(e, *first);
        return result;
    }

    static auto from_fill(size_t n, T v)
    {
        auto e      = owner_t{};
        auto result = rbtree{};
        while (n-- > 0)
            result.push_back_mut(e, v);
        return result;
    }

    rbtree()
        : size{0}
        , shift{BL}
        , root{empty_root()}
        , tail{empty_tail()}
    {
        assert(check_tree());
    }

    rbtree(size_t sz, shift_t sh, node_t* r, node_t* t)
        : size{sz}
        , shift{sh}
        , root{r}
        , tail{t}
    {
        assert(check_tree());
    }

    rbtree(const rbtree& other)
        : rbtree{other.size, other.shift, other.root, other.tail}
    {
        inc();
    }

    rbtree(rbtree&& other)
        : rbtree{}
    {
        swap(*this, other);
    }

    rbtree& operator=(const rbtree& other)
    {
        auto next = other;
        swap(*this, next);
        return *this;
    }

    rbtree& operator=(rbtree&& other)
    {
        swap(*this, other);
        return *this;
    }

    friend void swap(rbtree& x, rbtree& y)
    {
        using std::swap;
        swap(x.size, y.size);
        swap(x.shift, y.shift);
        swap(x.root, y.root);
        swap(x.tail, y.tail);
    }

    ~rbtree() { dec(); }

    void inc() const
    {
        root->inc();
        tail->inc();
    }

    void dec() const { traverse(dec_visitor()); }

    auto tail_size() const { return size ? ((size - 1) & mask<BL>) +1 : 0; }

    auto tail_offset() const { return size ? (size - 1) & ~mask<BL> : 0; }

    template <typename Visitor, typename... Args>
    void traverse(Visitor v, Args&&... args) const
    {
        auto tail_off  = tail_offset();
        auto tail_size = size - tail_off;

        if (tail_off)
            make_regular_sub_pos(root, shift, tail_off).visit(v, args...);
        else
            make_empty_regular_pos(root).visit(v, args...);

        make_leaf_sub_pos(tail, tail_size).visit(v, args...);
    }

    template <typename Visitor, typename... Args>
    void traverse(Visitor v, size_t first, size_t last, Args&&... args) const
    {
        auto tail_off  = tail_offset();
        auto tail_size = size - tail_off;

        if (first < tail_off)
            make_regular_sub_pos(root, shift, tail_off)
                .visit(v, first, last < tail_off ? last : tail_off, args...);
        if (last > tail_off)
            make_leaf_sub_pos(tail, tail_size)
                .visit(v,
                       first > tail_off ? first - tail_off : 0,
                       last - tail_off,
                       args...);
    }

    template <typename Visitor, typename... Args>
    bool traverse_p(Visitor v, Args&&... args) const
    {
        auto tail_off  = tail_offset();
        auto tail_size = size - tail_off;
        return (tail_off ? make_regular_sub_pos(root, shift, tail_off)
                               .visit(v, args...)
                         : make_empty_regular_pos(root).visit(v, args...)) &&
               make_leaf_sub_pos(tail, tail_size).visit(v, args...);
    }

    template <typename Visitor, typename... Args>
    bool traverse_p(Visitor v, size_t first, size_t last, Args&&... args) const
    {
        auto tail_off  = tail_offset();
        auto tail_size = size - tail_off;

        return (first < tail_off ? make_regular_sub_pos(root, shift, tail_off)
                                       .visit(v,
                                              first,
                                              last < tail_off ? last : tail_off,
                                              args...)
                                 : true) &&
               (last > tail_off
                    ? make_leaf_sub_pos(tail, tail_size)
                          .visit(v,
                                 first > tail_off ? first - tail_off : 0,
                                 last - tail_off,
                                 args...)
                    : true);
    }

    template <typename Visitor>
    decltype(auto) descend(Visitor v, size_t idx) const
    {
        auto tail_off = tail_offset();
        return idx >= tail_off ? make_leaf_descent_pos(tail).visit(v, idx)
                               : visit_regular_descent(root, shift, v, idx);
    }

    template <typename Fn>
    void for_each_chunk(Fn&& fn) const
    {
        traverse(for_each_chunk_visitor{}, std::forward<Fn>(fn));
    }

    template <typename Fn>
    void for_each_chunk(size_t first, size_t last, Fn&& fn) const
    {
        traverse(for_each_chunk_i_visitor{}, first, last, std::forward<Fn>(fn));
    }

    template <typename Fn>
    bool for_each_chunk_p(Fn&& fn) const
    {
        return traverse_p(for_each_chunk_p_visitor{}, std::forward<Fn>(fn));
    }

    template <typename Fn>
    bool for_each_chunk_p(size_t first, size_t last, Fn&& fn) const
    {
        return traverse_p(
            for_each_chunk_p_i_visitor{}, first, last, std::forward<Fn>(fn));
    }

    bool equals(const rbtree& other) const
    {
        if (size != other.size)
            return false;
        if (size == 0)
            return true;
        return (size <= branches<BL> ||
                make_regular_sub_pos(root, shift, tail_offset())
                    .visit(equals_visitor{}, other.root)) &&
               make_leaf_sub_pos(tail, tail_size())
                   .visit(equals_visitor{}, other.tail);
    }

    void ensure_mutable_tail(edit_t e, count_t n)
    {
        if (!tail->can_mutate(e)) {
            auto new_tail = node_t::copy_leaf_e(e, tail, n);
            dec_leaf(tail, n);
            tail = new_tail;
        }
    }

    void push_back_mut(edit_t e, T value)
    {
        auto tail_off = tail_offset();
        auto ts       = size - tail_off;
        if (ts < branches<BL>) {
            ensure_mutable_tail(e, ts);
            new (&tail->leaf()[ts]) T{std::move(value)};
        } else {
            auto new_tail = node_t::make_leaf_e(e, std::move(value));
            IMMER_TRY {
                if (tail_off == size_t{branches<B>} << shift) {
                    auto new_root = node_t::make_inner_e(e);
                    IMMER_TRY {
                        auto path = node_t::make_path_e(e, shift, tail);
                        new_root->inner()[0] = root;
                        new_root->inner()[1] = path;
                        root                 = new_root;
                        tail                 = new_tail;
                        shift += B;
                    }
                    IMMER_CATCH (...) {
                        node_t::delete_inner_e(new_root);
                        IMMER_RETHROW;
                    }
                } else if (tail_off) {
                    auto new_root =
                        make_regular_sub_pos(root, shift, tail_off)
                            .visit(push_tail_mut_visitor<node_t>{}, e, tail);
                    root = new_root;
                    tail = new_tail;
                } else {
                    auto new_root = node_t::make_path_e(e, shift, tail);
                    assert(tail_off == 0);
                    dec_empty_regular(root);
                    root = new_root;
                    tail = new_tail;
                }
            }
            IMMER_CATCH (...) {
                node_t::delete_leaf(new_tail, 1);
                IMMER_RETHROW;
            }
        }
        ++size;
    }

    rbtree push_back(T value) const
    {
        auto tail_off = tail_offset();
        auto ts       = size - tail_off;
        if (ts < branches<BL>) {
            auto new_tail =
                node_t::copy_leaf_emplace(tail, ts, std::move(value));
            return {size + 1, shift, root->inc(), new_tail};
        } else {
            auto new_tail = node_t::make_leaf_n(1, std::move(value));
            IMMER_TRY {
                if (tail_off == size_t{branches<B>} << shift) {
                    auto new_root = node_t::make_inner_n(2);
                    IMMER_TRY {
                        auto path            = node_t::make_path(shift, tail);
                        new_root->inner()[0] = root;
                        new_root->inner()[1] = path;
                        root->inc();
                        tail->inc();
                        return {size + 1, shift + B, new_root, new_tail};
                    }
                    IMMER_CATCH (...) {
                        node_t::delete_inner(new_root, 2);
                        IMMER_RETHROW;
                    }
                } else if (tail_off) {
                    auto new_root =
                        make_regular_sub_pos(root, shift, tail_off)
                            .visit(push_tail_visitor<node_t>{}, tail);
                    tail->inc();
                    return {size + 1, shift, new_root, new_tail};
                } else {
                    auto new_root = node_t::make_path(shift, tail);
                    tail->inc();
                    return {size + 1, shift, new_root, new_tail};
                }
            }
            IMMER_CATCH (...) {
                node_t::delete_leaf(new_tail, 1);
                IMMER_RETHROW;
            }
        }
    }

    const T* array_for(size_t index) const
    {
        return descend(array_for_visitor<T>(), index);
    }

    T& get_mut(edit_t e, size_t idx)
    {
        auto tail_off = tail_offset();
        if (idx >= tail_off) {
            ensure_mutable_tail(e, size - tail_off);
            return tail->leaf()[idx & mask<BL>];
        } else {
            return make_regular_sub_pos(root, shift, tail_off)
                .visit(get_mut_visitor<node_t>{}, idx, e, &root);
        }
    }

    const T& get(size_t index) const
    {
        return descend(get_visitor<T>(), index);
    }

    const T& get_check(size_t index) const
    {
        if (index >= size)
            IMMER_THROW(std::out_of_range{"index out of range"});
        return descend(get_visitor<T>(), index);
    }

    const T& front() const { return get(0); }

    const T& back() const { return tail->leaf()[(size - 1) & mask<BL>]; }

    template <typename FnT>
    void update_mut(edit_t e, size_t idx, FnT&& fn)
    {
        auto& elem = get_mut(e, idx);
        elem       = std::forward<FnT>(fn)(std::move(elem));
    }

    template <typename FnT>
    rbtree update(size_t idx, FnT&& fn) const
    {
        auto tail_off = tail_offset();
        if (idx >= tail_off) {
            auto tail_size = size - tail_off;
            auto new_tail =
                make_leaf_sub_pos(tail, tail_size)
                    .visit(update_visitor<node_t>{}, idx - tail_off, fn);
            return {size, shift, root->inc(), new_tail};
        } else {
            auto new_root = make_regular_sub_pos(root, shift, tail_off)
                                .visit(update_visitor<node_t>{}, idx, fn);
            return {size, shift, new_root, tail->inc()};
        }
    }

    void assoc_mut(edit_t e, size_t idx, T value)
    {
        update_mut(e, idx, [&](auto&&) { return std::move(value); });
    }

    rbtree assoc(size_t idx, T value) const
    {
        return update(idx, [&](auto&&) { return std::move(value); });
    }

    rbtree take(size_t new_size) const
    {
        auto tail_off = tail_offset();
        if (new_size == 0) {
            return {};
        } else if (new_size >= size) {
            return *this;
        } else if (new_size > tail_off) {
            auto new_tail = node_t::copy_leaf(tail, new_size - tail_off);
            return {new_size, shift, root->inc(), new_tail};
        } else {
            using std::get;
            auto l = new_size - 1;
            auto v = slice_right_visitor<node_t>();
            auto r = make_regular_sub_pos(root, shift, tail_off).visit(v, l);
            auto new_shift = get<0>(r);
            auto new_root  = get<1>(r);
            auto new_tail  = get<3>(r);
            if (new_root) {
                IMMER_ASSERT_TAGGED(new_root->compute_shift() == get<0>(r));
                assert(new_root->check(new_shift, new_size - get<2>(r)));
                return {new_size, new_shift, new_root, new_tail};
            } else {
                return {new_size, BL, empty_root(), new_tail};
            }
        }
    }

    void take_mut(edit_t e, size_t new_size)
    {
        auto tail_off = tail_offset();
        if (new_size == 0) {
            // todo: more efficient?
            *this = {};
        } else if (new_size >= size) {
            return;
        } else if (new_size > tail_off) {
            auto ts    = size - tail_off;
            auto newts = new_size - tail_off;
            if (tail->can_mutate(e)) {
                detail::destroy_n(tail->leaf() + newts, ts - newts);
            } else {
                auto new_tail = node_t::copy_leaf_e(e, tail, newts);
                dec_leaf(tail, ts);
                tail = new_tail;
            }
            size = new_size;
            return;
        } else {
            using std::get;
            auto l = new_size - 1;
            auto v = slice_right_mut_visitor<node_t>();
            auto r = make_regular_sub_pos(root, shift, tail_off).visit(v, l, e);
            auto new_shift = get<0>(r);
            auto new_root  = get<1>(r);
            auto new_tail  = get<3>(r);
            if (new_root) {
                root  = new_root;
                shift = new_shift;
            } else {
                root  = empty_root();
                shift = BL;
            }
            dec_leaf(tail, size - tail_off);
            size = new_size;
            tail = new_tail;
            return;
        }
    }

    bool check_tree() const
    {
#if IMMER_DEBUG_DEEP_CHECK
        assert(shift >= BL);
        assert(tail_offset() <= size);
        assert(check_root());
        assert(check_tail());
#endif
        return true;
    }

    bool check_tail() const
    {
#if IMMER_DEBUG_DEEP_CHECK
        if (tail_size() > 0)
            assert(tail->check(endshift<B, BL>, tail_size()));
#endif
        return true;
    }

    bool check_root() const
    {
#if IMMER_DEBUG_DEEP_CHECK
        if (tail_offset() > 0)
            assert(root->check(shift, tail_offset()));
        else {
            IMMER_ASSERT_TAGGED(root->kind() == node_t::kind_t::inner);
            assert(shift == BL);
        }
#endif
        return true;
    }
};

} // namespace rbts
} // namespace detail
} // namespace immer

Coverage Report

Created: 2025-11-24 06:11

Line	Count	Source
1		//
2		// immer: immutable data structures for C++
3		// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4		//
5		// This software is distributed under the Boost Software License, Version 1.0.
6		// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7		//
8
9		#pragma once
10
11		#include <immer/config.hpp>
12		#include <immer/detail/rbts/node.hpp>
13		#include <immer/detail/rbts/operations.hpp>
14		#include <immer/detail/rbts/position.hpp>
15		#include <immer/detail/type_traits.hpp>
16
17		#include <cassert>
18		#include <memory>
19		#include <numeric>
20		#include <stdexcept>
21
22		namespace immer {
23		namespace detail {
24		namespace rbts {
25
26		template <typename T, typename MemoryPolicy, bits_t B, bits_t BL>
27		struct rbtree
28		{
29		using node_t = node<T, MemoryPolicy, B, BL>;
30		using edit_t = typename node_t::edit_t;
31		using owner_t = typename MemoryPolicy::transience_t::owner;
32
33		size_t size;
34		shift_t shift;
35		node_t* root;
36		node_t* tail;
37
38		constexpr static size_t max_size()
39		{
40		auto S = sizeof(size_t) * 8;
41		return (size_t{1} << BL) * ipow(size_t{1} << B, (S - BL) / B);
42		}
43
44		static node_t* empty_root()
45	1.20M	{
46	1.20M	static const auto empty_ = node_t::make_inner_n(0u);
47	1.20M	return empty_->inc();
48	1.20M	}
49
50		static node_t* empty_tail()
51	1.19M	{
52	1.19M	static const auto empty_ = node_t::make_leaf_n(0u);
53	1.19M	return empty_->inc();
54	1.19M	}
55
56		template <typename U>
57		static auto from_initializer_list(std::initializer_list<U> values)
58		{
59		auto e = owner_t{};
60		auto result = rbtree{};
61		for (auto&& v : values)
62		result.push_back_mut(e, v);
63		return result;
64		}
65
66		template <typename Iter,
67		typename Sent,
68		std::enable_if_t<compatible_sentinel_v<Iter, Sent>, bool> = true>
69		static auto from_range(Iter first, Sent last)
70		{
71		auto e = owner_t{};
72		auto result = rbtree{};
73		for (; first != last; ++first)
74		result.push_back_mut(e, *first);
75		return result;
76		}
77
78		static auto from_fill(size_t n, T v)
79		{
80		auto e = owner_t{};
81		auto result = rbtree{};
82		while (n-- > 0)
83		result.push_back_mut(e, v);
84		return result;
85		}
86
87		rbtree()
88	1.19M	: size{0}
89	1.19M	, shift{BL}
90	1.19M	, root{empty_root()}
91	1.19M	, tail{empty_tail()}
92	1.19M	{
93	1.19M	assert(check_tree());
94	1.19M	}
95
96		rbtree(size_t sz, shift_t sh, node_t* r, node_t* t)
97	1.17M	: size{sz}
98	1.17M	, shift{sh}
99	1.17M	, root{r}
100	1.17M	, tail{t}
101	1.17M	{
102	1.17M	assert(check_tree());
103	1.17M	}
104
105		rbtree(const rbtree& other)
106	884	: rbtree{other.size, other.shift, other.root, other.tail}
107	884	{
108	884	inc();
109	884	}
110
111		rbtree(rbtree&& other)
112	1.17M	: rbtree{}
113	1.17M	{
114	1.17M	swap(*this, other);
115	1.17M	}
116
117		rbtree& operator=(const rbtree& other)
118		{
119		auto next = other;
120		swap(*this, next);
121		return *this;
122		}
123
124		rbtree& operator=(rbtree&& other)
125	1.41M	{
126	1.41M	swap(*this, other);
127	1.41M	return *this;
128	1.41M	}
129
130		friend void swap(rbtree& x, rbtree& y)
131	2.59M	{
132	2.59M	using std::swap;
133	2.59M	swap(x.size, y.size);
134	2.59M	swap(x.shift, y.shift);
135	2.59M	swap(x.root, y.root);
136	2.59M	swap(x.tail, y.tail);
137	2.59M	}
138
139	2.36M	~rbtree() { dec(); }
140
141		void inc() const
142	884	{
143	884	root->inc();
144	884	tail->inc();
145	884	}
146
147	2.36M	void dec() const { traverse(dec_visitor()); }
148
149		auto tail_size() const { return size ? ((size - 1) & mask<BL>) +1 : 0; }
150
151	3.78M	auto tail_offset() const { return size ? (size - 1) & ~mask<BL> : 0; }
152
153		template <typename Visitor, typename... Args>
154		void traverse(Visitor v, Args&&... args) const
155	2.36M	{
156	2.36M	auto tail_off = tail_offset();
157	2.36M	auto tail_size = size - tail_off;
158
159	2.36M	if (tail_off)
160	1.14M	make_regular_sub_pos(root, shift, tail_off).visit(v, args...);
161	1.22M	else
162	1.22M	make_empty_regular_pos(root).visit(v, args...);
163
164	2.36M	make_leaf_sub_pos(tail, tail_size).visit(v, args...);
165	2.36M	}
166
167		template <typename Visitor, typename... Args>
168		void traverse(Visitor v, size_t first, size_t last, Args&&... args) const
169		{
170		auto tail_off = tail_offset();
171		auto tail_size = size - tail_off;
172
173		if (first < tail_off)
174		make_regular_sub_pos(root, shift, tail_off)
175		.visit(v, first, last < tail_off ? last : tail_off, args...);
176		if (last > tail_off)
177		make_leaf_sub_pos(tail, tail_size)
178		.visit(v,
179		first > tail_off ? first - tail_off : 0,
180		last - tail_off,
181		args...);
182		}
183
184		template <typename Visitor, typename... Args>
185		bool traverse_p(Visitor v, Args&&... args) const
186		{
187		auto tail_off = tail_offset();
188		auto tail_size = size - tail_off;
189		return (tail_off ? make_regular_sub_pos(root, shift, tail_off)
190		.visit(v, args...)
191		: make_empty_regular_pos(root).visit(v, args...)) &&
192		make_leaf_sub_pos(tail, tail_size).visit(v, args...);
193		}
194
195		template <typename Visitor, typename... Args>
196		bool traverse_p(Visitor v, size_t first, size_t last, Args&&... args) const
197		{
198		auto tail_off = tail_offset();
199		auto tail_size = size - tail_off;
200
201		return (first < tail_off ? make_regular_sub_pos(root, shift, tail_off)
202		.visit(v,
203		first,
204		last < tail_off ? last : tail_off,
205		args...)
206		: true) &&
207		(last > tail_off
208		? make_leaf_sub_pos(tail, tail_size)
209		.visit(v,
210		first > tail_off ? first - tail_off : 0,
211		last - tail_off,
212		args...)
213		: true);
214		}
215
216		template <typename Visitor>
217		decltype(auto) descend(Visitor v, size_t idx) const
218		{
219		auto tail_off = tail_offset();
220		return idx >= tail_off ? make_leaf_descent_pos(tail).visit(v, idx)
221		: visit_regular_descent(root, shift, v, idx);
222		}
223
224		template <typename Fn>
225		void for_each_chunk(Fn&& fn) const
226		{
227		traverse(for_each_chunk_visitor{}, std::forward<Fn>(fn));
228		}
229
230		template <typename Fn>
231		void for_each_chunk(size_t first, size_t last, Fn&& fn) const
232		{
233		traverse(for_each_chunk_i_visitor{}, first, last, std::forward<Fn>(fn));
234		}
235
236		template <typename Fn>
237		bool for_each_chunk_p(Fn&& fn) const
238		{
239		return traverse_p(for_each_chunk_p_visitor{}, std::forward<Fn>(fn));
240		}
241
242		template <typename Fn>
243		bool for_each_chunk_p(size_t first, size_t last, Fn&& fn) const
244		{
245		return traverse_p(
246		for_each_chunk_p_i_visitor{}, first, last, std::forward<Fn>(fn));
247		}
248
249		bool equals(const rbtree& other) const
250		{
251		if (size != other.size)
252		return false;
253		if (size == 0)
254		return true;
255		return (size <= branches<BL> \|\|
256		make_regular_sub_pos(root, shift, tail_offset())
257		.visit(equals_visitor{}, other.root)) &&
258		make_leaf_sub_pos(tail, tail_size())
259		.visit(equals_visitor{}, other.tail);
260		}
261
262		void ensure_mutable_tail(edit_t e, count_t n)
263	146k	{
264	146k	if (!tail->can_mutate(e)) {
265	2.32k	auto new_tail = node_t::copy_leaf_e(e, tail, n);
266	2.32k	dec_leaf(tail, n);
267	2.32k	tail = new_tail;
268	2.32k	}
269	146k	}
270
271		void push_back_mut(edit_t e, T value)
272	195k	{
273	195k	auto tail_off = tail_offset();
274	195k	auto ts = size - tail_off;
275	195k	if (ts < branches<BL>) {
276	145k	ensure_mutable_tail(e, ts);
277	145k	new (&tail->leaf()[ts]) T{std::move(value)};
278	145k	} else {
279	50.5k	auto new_tail = node_t::make_leaf_e(e, std::move(value));
280	50.5k	IMMER_TRY {
281	50.5k	if (tail_off == size_t{branches<B>} << shift) {
282	800	auto new_root = node_t::make_inner_e(e);
283	800	IMMER_TRY {
284	800	auto path = node_t::make_path_e(e, shift, tail);
285	800	new_root->inner()[0] = root;
286	800	new_root->inner()[1] = path;
287	800	root = new_root;
288	800	tail = new_tail;
289	800	shift += B;
290	800	}
291	800	IMMER_CATCH (...) {
292	0	node_t::delete_inner_e(new_root);
293	0	IMMER_RETHROW;
294	0	}
295	49.7k	} else if (tail_off) {
296	49.2k	auto new_root =
297	49.2k	make_regular_sub_pos(root, shift, tail_off)
298	49.2k	.visit(push_tail_mut_visitor<node_t>{}, e, tail);
299	49.2k	root = new_root;
300	49.2k	tail = new_tail;
301	49.2k	} else {
302	447	auto new_root = node_t::make_path_e(e, shift, tail);
303	447	assert(tail_off == 0);
304	447	dec_empty_regular(root);
305	447	root = new_root;
306	447	tail = new_tail;
307	447	}
308	50.5k	}
309	50.5k	IMMER_CATCH (...) {
310	0	node_t::delete_leaf(new_tail, 1);
311	0	IMMER_RETHROW;
312	0	}
313	50.5k	}
314	195k	++size;
315	195k	}
316
317		rbtree push_back(T value) const
318	1.13M	{
319	1.13M	auto tail_off = tail_offset();
320	1.13M	auto ts = size - tail_off;
321	1.13M	if (ts < branches<BL>) {
322	849k	auto new_tail =
323	849k	node_t::copy_leaf_emplace(tail, ts, std::move(value));
324	849k	return {size + 1, shift, root->inc(), new_tail};
325	849k	} else {
326	288k	auto new_tail = node_t::make_leaf_n(1, std::move(value));
327	288k	IMMER_TRY {
328	288k	if (tail_off == size_t{branches<B>} << shift) {
329	8.62k	auto new_root = node_t::make_inner_n(2);
330	8.62k	IMMER_TRY {
331	8.62k	auto path = node_t::make_path(shift, tail);
332	8.62k	new_root->inner()[0] = root;
333	8.62k	new_root->inner()[1] = path;
334	8.62k	root->inc();
335	8.62k	tail->inc();
336	8.62k	return {size + 1, shift + B, new_root, new_tail};
337	8.62k	}
338	8.62k	IMMER_CATCH (...) {
339	0	node_t::delete_inner(new_root, 2);
340	0	IMMER_RETHROW;
341	0	}
342	279k	} else if (tail_off) {
343	274k	auto new_root =
344	274k	make_regular_sub_pos(root, shift, tail_off)
345	274k	.visit(push_tail_visitor<node_t>{}, tail);
346	274k	tail->inc();
347	274k	return {size + 1, shift, new_root, new_tail};
348	274k	} else {
349	5.21k	auto new_root = node_t::make_path(shift, tail);
350	5.21k	tail->inc();
351	5.21k	return {size + 1, shift, new_root, new_tail};
352	5.21k	}
353	288k	}
354	288k	IMMER_CATCH (...) {
355	0	node_t::delete_leaf(new_tail, 1);
356	0	IMMER_RETHROW;
357	0	}
358	288k	}
359	1.13M	}
360
361		const T* array_for(size_t index) const
362		{
363		return descend(array_for_visitor<T>(), index);
364		}
365
366		T& get_mut(edit_t e, size_t idx)
367	6.11k	{
368	6.11k	auto tail_off = tail_offset();
369	6.11k	if (idx >= tail_off) {
370	982	ensure_mutable_tail(e, size - tail_off);
371	982	return tail->leaf()[idx & mask<BL>];
372	5.13k	} else {
373	5.13k	return make_regular_sub_pos(root, shift, tail_off)
374	5.13k	.visit(get_mut_visitor<node_t>{}, idx, e, &root);
375	5.13k	}
376	6.11k	}
377
378		const T& get(size_t index) const
379		{
380		return descend(get_visitor<T>(), index);
381		}
382
383		const T& get_check(size_t index) const
384		{
385		if (index >= size)
386		IMMER_THROW(std::out_of_range{"index out of range"});
387		return descend(get_visitor<T>(), index);
388		}
389
390		const T& front() const { return get(0); }
391
392		const T& back() const { return tail->leaf()[(size - 1) & mask<BL>]; }
393
394		template <typename FnT>
395		void update_mut(edit_t e, size_t idx, FnT&& fn)
396	6.11k	{
397	6.11k	auto& elem = get_mut(e, idx);
398	6.11k	elem = std::forward<FnT>(fn)(std::move(elem));
399	6.11k	}
400
401		template <typename FnT>
402		rbtree update(size_t idx, FnT&& fn) const
403	22.9k	{
404	22.9k	auto tail_off = tail_offset();
405	22.9k	if (idx >= tail_off) {
406	1.20k	auto tail_size = size - tail_off;
407	1.20k	auto new_tail =
408	1.20k	make_leaf_sub_pos(tail, tail_size)
409	1.20k	.visit(update_visitor<node_t>{}, idx - tail_off, fn);
410	1.20k	return {size, shift, root->inc(), new_tail};
411	21.7k	} else {
412	21.7k	auto new_root = make_regular_sub_pos(root, shift, tail_off)
413	21.7k	.visit(update_visitor<node_t>{}, idx, fn);
414	21.7k	return {size, shift, new_root, tail->inc()};
415	21.7k	}
416	22.9k	}
417
418		void assoc_mut(edit_t e, size_t idx, T value)
419		{
420		update_mut(e, idx, [&](auto&&) { return std::move(value); });
421		}
422
423		rbtree assoc(size_t idx, T value) const
424		{
425		return update(idx, [&](auto&&) { return std::move(value); });
426		}
427
428		rbtree take(size_t new_size) const
429	17.7k	{
430	17.7k	auto tail_off = tail_offset();
431	17.7k	if (new_size == 0) {
432	3.38k	return {};
433	14.3k	} else if (new_size >= size) {
434	884	return *this;
435	13.4k	} else if (new_size > tail_off) {
436	2.24k	auto new_tail = node_t::copy_leaf(tail, new_size - tail_off);
437	2.24k	return {new_size, shift, root->inc(), new_tail};
438	11.2k	} else {
439	11.2k	using std::get;
440	11.2k	auto l = new_size - 1;
441	11.2k	auto v = slice_right_visitor<node_t>();
442	11.2k	auto r = make_regular_sub_pos(root, shift, tail_off).visit(v, l);
443	11.2k	auto new_shift = get<0>(r);
444	11.2k	auto new_root = get<1>(r);
445	11.2k	auto new_tail = get<3>(r);
446	11.2k	if (new_root) {
447	9.15k	IMMER_ASSERT_TAGGED(new_root->compute_shift() == get<0>(r));
448	9.15k	assert(new_root->check(new_shift, new_size - get<2>(r)));
449	9.15k	return {new_size, new_shift, new_root, new_tail};
450	9.15k	} else {
451	2.06k	return {new_size, BL, empty_root(), new_tail};
452	2.06k	}
453	11.2k	}
454	17.7k	}
455
456		void take_mut(edit_t e, size_t new_size)
457	36.4k	{
458	36.4k	auto tail_off = tail_offset();
459	36.4k	if (new_size == 0) {
460		// todo: more efficient?
461	1.04k	*this = {};
462	35.3k	} else if (new_size >= size) {
463	755	return;
464	34.6k	} else if (new_size > tail_off) {
465	1.50k	auto ts = size - tail_off;
466	1.50k	auto newts = new_size - tail_off;
467	1.50k	if (tail->can_mutate(e)) {
468	1.13k	detail::destroy_n(tail->leaf() + newts, ts - newts);
469	1.13k	} else {
470	375	auto new_tail = node_t::copy_leaf_e(e, tail, newts);
471	375	dec_leaf(tail, ts);
472	375	tail = new_tail;
473	375	}
474	1.50k	size = new_size;
475	1.50k	return;
476	33.1k	} else {
477	33.1k	using std::get;
478	33.1k	auto l = new_size - 1;
479	33.1k	auto v = slice_right_mut_visitor<node_t>();
480	33.1k	auto r = make_regular_sub_pos(root, shift, tail_off).visit(v, l, e);
481	33.1k	auto new_shift = get<0>(r);
482	33.1k	auto new_root = get<1>(r);
483	33.1k	auto new_tail = get<3>(r);
484	33.1k	if (new_root) {
485	24.5k	root = new_root;
486	24.5k	shift = new_shift;
487	24.5k	} else {
488	8.58k	root = empty_root();
489	8.58k	shift = BL;
490	8.58k	}
491	33.1k	dec_leaf(tail, size - tail_off);
492	33.1k	size = new_size;
493	33.1k	tail = new_tail;
494	33.1k	return;
495	33.1k	}
496	36.4k	}
497
498		bool check_tree() const
499	2.36M	{
500		#if IMMER_DEBUG_DEEP_CHECK
501		assert(shift >= BL);
502		assert(tail_offset() <= size);
503		assert(check_root());
504		assert(check_tail());
505		#endif
506	2.36M	return true;
507	2.36M	}
508
509		bool check_tail() const
510		{
511		#if IMMER_DEBUG_DEEP_CHECK
512		if (tail_size() > 0)
513		assert(tail->check(endshift<B, BL>, tail_size()));
514		#endif
515		return true;
516		}
517
518		bool check_root() const
519		{
520		#if IMMER_DEBUG_DEEP_CHECK
521		if (tail_offset() > 0)
522		assert(root->check(shift, tail_offset()));
523		else {
524		IMMER_ASSERT_TAGGED(root->kind() == node_t::kind_t::inner);
525		assert(shift == BL);
526		}
527		#endif
528		return true;
529		}
530		};
531
532		} // namespace rbts
533		} // namespace detail
534		} // namespace immer