diff options
Diffstat (limited to 'third_party/immer/immer/detail/rbts/operations.hpp')
| -rw-r--r-- | third_party/immer/immer/detail/rbts/operations.hpp | 2461 |
1 files changed, 0 insertions, 2461 deletions
diff --git a/third_party/immer/immer/detail/rbts/operations.hpp b/third_party/immer/immer/detail/rbts/operations.hpp deleted file mode 100644 index ff703e892b..0000000000 --- a/third_party/immer/immer/detail/rbts/operations.hpp +++ /dev/null @@ -1,2461 +0,0 @@ -// -// immer: immutable data structures for C++ -// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente -// -// This software is distributed under the Boost Software License, Version 1.0. -// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt -// - -#pragma once - -#include <algorithm> -#include <memory> -#include <numeric> -#include <utility> - -#include <immer/config.hpp> -#include <immer/detail/rbts/position.hpp> -#include <immer/detail/rbts/visitor.hpp> -#include <immer/detail/util.hpp> -#include <immer/heap/tags.hpp> - -namespace immer { -namespace detail { -namespace rbts { - -template <typename T> -struct array_for_visitor : visitor_base<array_for_visitor<T>> -{ - using this_t = array_for_visitor; - - template <typename PosT> - static T* visit_inner(PosT&& pos, size_t idx) - { - return pos.descend(this_t{}, idx); - } - - template <typename PosT> - static T* visit_leaf(PosT&& pos, size_t) - { - return pos.node()->leaf(); - } -}; - -template <typename T> -struct region_for_visitor : visitor_base<region_for_visitor<T>> -{ - using this_t = region_for_visitor; - using result_t = std::tuple<T*, size_t, size_t>; - - template <typename PosT> - static result_t visit_inner(PosT&& pos, size_t idx) - { - return pos.towards(this_t{}, idx); - } - - template <typename PosT> - static result_t visit_leaf(PosT&& pos, size_t idx) - { - return std::make_tuple(pos.node()->leaf(), pos.index(idx), pos.count()); - } -}; - -template <typename T> -struct get_visitor : visitor_base<get_visitor<T>> -{ - using this_t = get_visitor; - - template <typename PosT> - static const T& visit_inner(PosT&& pos, size_t idx) - { - return pos.descend(this_t{}, idx); - } - - template <typename PosT> - static const T& visit_leaf(PosT&& pos, size_t idx) - { - return pos.node()->leaf()[pos.index(idx)]; - } -}; - -struct for_each_chunk_visitor : visitor_base<for_each_chunk_visitor> -{ - using this_t = for_each_chunk_visitor; - - template <typename Pos, typename Fn> - static void visit_inner(Pos&& pos, Fn&& fn) - { - pos.each(this_t{}, fn); - } - - template <typename Pos, typename Fn> - static void visit_leaf(Pos&& pos, Fn&& fn) - { - auto data = pos.node()->leaf(); - fn(data, data + pos.count()); - } -}; - -struct for_each_chunk_p_visitor : visitor_base<for_each_chunk_p_visitor> -{ - using this_t = for_each_chunk_p_visitor; - - template <typename Pos, typename Fn> - static bool visit_inner(Pos&& pos, Fn&& fn) - { - return pos.each_pred(this_t{}, fn); - } - - template <typename Pos, typename Fn> - static bool visit_leaf(Pos&& pos, Fn&& fn) - { - auto data = pos.node()->leaf(); - return fn(data, data + pos.count()); - } -}; - -struct for_each_chunk_left_visitor : visitor_base<for_each_chunk_left_visitor> -{ - using this_t = for_each_chunk_left_visitor; - - template <typename Pos, typename Fn> - static void visit_inner(Pos&& pos, size_t last, Fn&& fn) - { - auto l = pos.index(last); - pos.each_left(for_each_chunk_visitor{}, l, fn); - pos.towards_oh(this_t{}, last, l, fn); - } - - template <typename Pos, typename Fn> - static void visit_leaf(Pos&& pos, size_t last, Fn&& fn) - { - auto data = pos.node()->leaf(); - auto l = pos.index(last); - fn(data, data + l + 1); - } -}; - -struct for_each_chunk_right_visitor : visitor_base<for_each_chunk_right_visitor> -{ - using this_t = for_each_chunk_right_visitor; - - template <typename Pos, typename Fn> - static void visit_inner(Pos&& pos, size_t first, Fn&& fn) - { - auto f = pos.index(first); - pos.towards_oh(this_t{}, first, f, fn); - pos.each_right(for_each_chunk_visitor{}, f + 1, fn); - } - - template <typename Pos, typename Fn> - static void visit_leaf(Pos&& pos, size_t first, Fn&& fn) - { - auto data = pos.node()->leaf(); - auto f = pos.index(first); - fn(data + f, data + pos.count()); - } -}; - -struct for_each_chunk_i_visitor : visitor_base<for_each_chunk_i_visitor> -{ - using this_t = for_each_chunk_i_visitor; - - template <typename Pos, typename Fn> - static void visit_relaxed(Pos&& pos, size_t first, size_t last, Fn&& fn) - { - // we are going towards *two* indices, so we need to do the - // relaxed as a special case to correct the second index - if (first < last) { - auto f = pos.index(first); - auto l = pos.index(last - 1); - if (f == l) { - auto sbh = pos.size_before(f); - pos.towards_oh_sbh(this_t{}, first, f, sbh, last - sbh, fn); - } else { - assert(f < l); - pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn); - pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn); - pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn); - } - } - } - - template <typename Pos, typename Fn> - static void visit_regular(Pos&& pos, size_t first, size_t last, Fn&& fn) - { - if (first < last) { - auto f = pos.index(first); - auto l = pos.index(last - 1); - if (f == l) - pos.towards_oh(this_t{}, first, f, last, fn); - else { - assert(f < l); - pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn); - pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn); - pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn); - } - } - } - - template <typename Pos, typename Fn> - static void visit_leaf(Pos&& pos, size_t first, size_t last, Fn&& fn) - { - auto data = pos.node()->leaf(); - if (first < last) { - auto f = pos.index(first); - auto l = pos.index(last - 1); - fn(data + f, data + l + 1); - } - } -}; - -struct for_each_chunk_p_left_visitor - : visitor_base<for_each_chunk_p_left_visitor> -{ - using this_t = for_each_chunk_p_left_visitor; - - template <typename Pos, typename Fn> - static bool visit_inner(Pos&& pos, size_t last, Fn&& fn) - { - auto l = pos.index(last); - return pos.each_pred_left(for_each_chunk_p_visitor{}, l, fn) && - pos.towards_oh(this_t{}, last, l, fn); - } - - template <typename Pos, typename Fn> - static bool visit_leaf(Pos&& pos, size_t last, Fn&& fn) - { - auto data = pos.node()->leaf(); - auto l = pos.index(last); - return fn(data, data + l + 1); - } -}; - -struct for_each_chunk_p_right_visitor - : visitor_base<for_each_chunk_p_right_visitor> -{ - using this_t = for_each_chunk_p_right_visitor; - - template <typename Pos, typename Fn> - static bool visit_inner(Pos&& pos, size_t first, Fn&& fn) - { - auto f = pos.index(first); - return pos.towards_oh(this_t{}, first, f, fn) && - pos.each_pred_right(for_each_chunk_p_visitor{}, f + 1, fn); - } - - template <typename Pos, typename Fn> - static bool visit_leaf(Pos&& pos, size_t first, Fn&& fn) - { - auto data = pos.node()->leaf(); - auto f = pos.index(first); - return fn(data + f, data + pos.count()); - } -}; - -struct for_each_chunk_p_i_visitor : visitor_base<for_each_chunk_p_i_visitor> -{ - using this_t = for_each_chunk_p_i_visitor; - - template <typename Pos, typename Fn> - static bool visit_relaxed(Pos&& pos, size_t first, size_t last, Fn&& fn) - { - // we are going towards *two* indices, so we need to do the - // relaxed as a special case to correct the second index - if (first < last) { - auto f = pos.index(first); - auto l = pos.index(last - 1); - if (f == l) { - auto sbh = pos.size_before(f); - return pos.towards_oh_sbh( - this_t{}, first, f, sbh, last - sbh, fn); - } else { - assert(f < l); - return pos.towards_oh( - for_each_chunk_p_right_visitor{}, first, f, fn) && - pos.each_pred_i( - for_each_chunk_p_visitor{}, f + 1, l, fn) && - pos.towards_oh( - for_each_chunk_p_left_visitor{}, last - 1, l, fn); - } - } - return true; - } - - template <typename Pos, typename Fn> - static bool visit_regular(Pos&& pos, size_t first, size_t last, Fn&& fn) - { - if (first < last) { - auto f = pos.index(first); - auto l = pos.index(last - 1); - if (f == l) - return pos.towards_oh(this_t{}, first, f, last, fn); - else { - assert(f < l); - return pos.towards_oh( - for_each_chunk_p_right_visitor{}, first, f, fn) && - pos.each_pred_i( - for_each_chunk_p_visitor{}, f + 1, l, fn) && - pos.towards_oh( - for_each_chunk_p_left_visitor{}, last - 1, l, fn); - } - } - return true; - } - - template <typename Pos, typename Fn> - static bool visit_leaf(Pos&& pos, size_t first, size_t last, Fn&& fn) - { - auto data = pos.node()->leaf(); - if (first < last) { - auto f = pos.index(first); - auto l = pos.index(last - 1); - return fn(data + f, data + l + 1); - } - return true; - } -}; - -struct equals_visitor : visitor_base<equals_visitor> -{ - using this_t = equals_visitor; - - struct this_aux_t : visitor_base<this_aux_t> - { - template <typename PosR, typename PosL, typename Iter> - static bool visit_inner( - PosR&& posr, count_t i, PosL&& posl, Iter&& first, size_t idx) - { - return posl.nth_sub(i, this_t{}, posr, first, idx); - } - - template <typename PosR, typename PosL, typename Iter> - static bool visit_leaf( - PosR&& posr, count_t i, PosL&& posl, Iter&& first, size_t idx) - { - return posl.nth_sub_leaf(i, this_t{}, posr, first, idx); - } - }; - - struct rrb : visitor_base<rrb> - { - template <typename PosR, typename Iter, typename Node> - static bool visit_node(PosR&& posr, - Iter&& first, - Node* rootl, - shift_t shiftl, - size_t sizel) - { - assert(shiftl <= posr.shift()); - return shiftl == posr.shift() - ? visit_maybe_relaxed_sub(rootl, - shiftl, - sizel, - this_t{}, - posr, - first, - size_t{}) - : posr.first_sub_inner( - rrb{}, first, rootl, shiftl, sizel); - } - }; - - template <typename Iter> - static auto equal_chunk_p(Iter&& iter) - { - return [iter](auto f, auto e) mutable { - if (f == &*iter) { - iter += e - f; - return true; - } - for (; f != e; ++f, ++iter) - if (*f != *iter) - return false; - return true; - }; - } - - template <typename PosL, typename PosR, typename Iter> - static bool - visit_relaxed(PosL&& posl, PosR&& posr, Iter&& first, size_t idx) - { - auto nl = posl.node(); - auto nr = posr.node(); - if (nl == nr) - return true; - auto cl = posl.count(); - auto cr = posr.count(); - assert(cr > 0); - auto sbr = size_t{}; - auto i = count_t{}; - auto j = count_t{}; - for (; i < cl; ++i) { - auto sbl = posl.size_before(i); - for (; j + 1 < cr && (sbr = posr.size_before(j)) < sbl; ++j) - ; - auto res = - sbl == sbr - ? posr.nth_sub(j, this_aux_t{}, i, posl, first, idx + sbl) - : posl.nth_sub(i, - for_each_chunk_p_visitor{}, - this_t::equal_chunk_p(first + (idx + sbl))); - if (!res) - return false; - } - return true; - } - - template <typename PosL, typename PosR, typename Iter> - static std::enable_if_t<is_relaxed_v<PosR>, bool> - visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx) - { - return this_t::visit_relaxed(posl, posr, first, idx); - } - - template <typename PosL, typename PosR, typename Iter> - static std::enable_if_t<!is_relaxed_v<PosR>, bool> - visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx) - { - return posl.count() >= posr.count() - ? this_t::visit_regular(posl, posr.node()) - : this_t::visit_regular(posr, posl.node()); - } - - template <typename PosL, typename PosR, typename Iter> - static bool visit_leaf(PosL&& posl, PosR&& posr, Iter&& first, size_t idx) - { - if (posl.node() == posr.node()) - return true; - auto cl = posl.count(); - auto cr = posr.count(); - auto mp = std::min(cl, cr); - return std::equal(posl.node()->leaf(), - posl.node()->leaf() + mp, - posr.node()->leaf()) && - std::equal(posl.node()->leaf() + mp, - posl.node()->leaf() + posl.count(), - first + (idx + mp)); - } - - template <typename Pos, typename NodeT> - static bool visit_regular(Pos&& pos, NodeT* other) - { - auto node = pos.node(); - return node == other || pos.each_pred_zip(this_t{}, other); - } - - template <typename Pos, typename NodeT> - static bool visit_leaf(Pos&& pos, NodeT* other) - { - auto node = pos.node(); - return node == other || std::equal(node->leaf(), - node->leaf() + pos.count(), - other->leaf()); - } -}; - -template <typename NodeT> -struct update_visitor : visitor_base<update_visitor<NodeT>> -{ - using node_t = NodeT; - using this_t = update_visitor; - - template <typename Pos, typename Fn> - static node_t* visit_relaxed(Pos&& pos, size_t idx, Fn&& fn) - { - auto offset = pos.index(idx); - auto count = pos.count(); - auto node = node_t::make_inner_sr_n(count, pos.relaxed()); - try { - auto child = pos.towards_oh(this_t{}, idx, offset, fn); - node_t::do_copy_inner_sr(node, pos.node(), count); - node->inner()[offset]->dec_unsafe(); - node->inner()[offset] = child; - return node; - } catch (...) { - node_t::delete_inner_r(node, count); - throw; - } - } - - template <typename Pos, typename Fn> - static node_t* visit_regular(Pos&& pos, size_t idx, Fn&& fn) - { - auto offset = pos.index(idx); - auto count = pos.count(); - auto node = node_t::make_inner_n(count); - try { - auto child = pos.towards_oh_ch(this_t{}, idx, offset, count, fn); - node_t::do_copy_inner(node, pos.node(), count); - node->inner()[offset]->dec_unsafe(); - node->inner()[offset] = child; - return node; - } catch (...) { - node_t::delete_inner(node, count); - throw; - } - } - - template <typename Pos, typename Fn> - static node_t* visit_leaf(Pos&& pos, size_t idx, Fn&& fn) - { - auto offset = pos.index(idx); - auto node = node_t::copy_leaf(pos.node(), pos.count()); - try { - node->leaf()[offset] = - std::forward<Fn>(fn)(std::move(node->leaf()[offset])); - return node; - } catch (...) { - node_t::delete_leaf(node, pos.count()); - throw; - } - } -}; - -struct dec_visitor : visitor_base<dec_visitor> -{ - using this_t = dec_visitor; - - template <typename Pos> - static void visit_relaxed(Pos&& p) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - p.each(this_t{}); - node_t::delete_inner_r(node, p.count()); - } - } - - template <typename Pos> - static void visit_regular(Pos&& p) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - p.each(this_t{}); - node_t::delete_inner(node, p.count()); - } - } - - template <typename Pos> - static void visit_leaf(Pos&& p) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - node_t::delete_leaf(node, p.count()); - } - } -}; - -template <typename NodeT> -void dec_leaf(NodeT* node, count_t n) -{ - make_leaf_sub_pos(node, n).visit(dec_visitor{}); -} - -template <typename NodeT> -void dec_inner(NodeT* node, shift_t shift, size_t size) -{ - visit_maybe_relaxed_sub(node, shift, size, dec_visitor()); -} - -template <typename NodeT> -void dec_relaxed(NodeT* node, shift_t shift) -{ - make_relaxed_pos(node, shift, node->relaxed()).visit(dec_visitor()); -} - -template <typename NodeT> -void dec_regular(NodeT* node, shift_t shift, size_t size) -{ - make_regular_pos(node, shift, size).visit(dec_visitor()); -} - -template <typename NodeT> -void dec_empty_regular(NodeT* node) -{ - make_empty_regular_pos(node).visit(dec_visitor()); -} - -template <typename NodeT> -struct get_mut_visitor : visitor_base<get_mut_visitor<NodeT>> -{ - using node_t = NodeT; - using this_t = get_mut_visitor; - using value_t = typename NodeT::value_t; - using edit_t = typename NodeT::edit_t; - - template <typename Pos> - static value_t& - visit_relaxed(Pos&& pos, size_t idx, edit_t e, node_t** location) - { - auto offset = pos.index(idx); - auto count = pos.count(); - auto node = pos.node(); - if (node->can_mutate(e)) { - return pos.towards_oh( - this_t{}, idx, offset, e, &node->inner()[offset]); - } else { - auto new_node = node_t::copy_inner_sr_e(e, node, count); - try { - auto& res = pos.towards_oh( - this_t{}, idx, offset, e, &new_node->inner()[offset]); - pos.visit(dec_visitor{}); - *location = new_node; - return res; - } catch (...) { - dec_relaxed(new_node, pos.shift()); - throw; - } - } - } - - template <typename Pos> - static value_t& - visit_regular(Pos&& pos, size_t idx, edit_t e, node_t** location) - { - assert(pos.node() == *location); - auto offset = pos.index(idx); - auto count = pos.count(); - auto node = pos.node(); - if (node->can_mutate(e)) { - return pos.towards_oh_ch( - this_t{}, idx, offset, count, e, &node->inner()[offset]); - } else { - auto new_node = node_t::copy_inner_e(e, node, count); - try { - auto& res = pos.towards_oh_ch(this_t{}, - idx, - offset, - count, - e, - &new_node->inner()[offset]); - pos.visit(dec_visitor{}); - *location = new_node; - return res; - } catch (...) { - dec_regular(new_node, pos.shift(), pos.size()); - throw; - } - } - } - - template <typename Pos> - static value_t& - visit_leaf(Pos&& pos, size_t idx, edit_t e, node_t** location) - { - assert(pos.node() == *location); - auto node = pos.node(); - if (node->can_mutate(e)) { - return node->leaf()[pos.index(idx)]; - } else { - auto new_node = node_t::copy_leaf_e(e, pos.node(), pos.count()); - pos.visit(dec_visitor{}); - *location = new_node; - return new_node->leaf()[pos.index(idx)]; - } - } -}; - -template <typename NodeT, bool Mutating = true> -struct push_tail_mut_visitor - : visitor_base<push_tail_mut_visitor<NodeT, Mutating>> -{ - static constexpr auto B = NodeT::bits; - static constexpr auto BL = NodeT::bits_leaf; - - using this_t = push_tail_mut_visitor; - using this_no_mut_t = push_tail_mut_visitor<NodeT, false>; - using node_t = NodeT; - using edit_t = typename NodeT::edit_t; - - template <typename Pos> - static node_t* visit_relaxed(Pos&& pos, edit_t e, node_t* tail, count_t ts) - { - auto node = pos.node(); - auto level = pos.shift(); - auto idx = pos.count() - 1; - auto children = pos.size(idx); - auto new_idx = - children == size_t{1} << level || level == BL ? idx + 1 : idx; - auto new_child = static_cast<node_t*>(nullptr); - auto mutate = Mutating && node->can_mutate(e); - - if (new_idx >= branches<B>) - return nullptr; - else if (idx == new_idx) { - new_child = - mutate ? pos.last_oh_csh(this_t{}, idx, children, e, tail, ts) - : pos.last_oh_csh( - this_no_mut_t{}, idx, children, e, tail, ts); - if (!new_child) { - if (++new_idx < branches<B>) - new_child = node_t::make_path_e(e, level - B, tail); - else - return nullptr; - } - } else - new_child = node_t::make_path_e(e, level - B, tail); - - if (mutate) { - auto count = new_idx + 1; - auto relaxed = node->ensure_mutable_relaxed_n(e, new_idx); - node->inner()[new_idx] = new_child; - relaxed->d.sizes[new_idx] = pos.size() + ts; - relaxed->d.count = count; - return node; - } else { - try { - auto count = new_idx + 1; - auto new_node = node_t::copy_inner_r_e(e, pos.node(), new_idx); - auto relaxed = new_node->relaxed(); - new_node->inner()[new_idx] = new_child; - relaxed->d.sizes[new_idx] = pos.size() + ts; - relaxed->d.count = count; - if (Mutating) - pos.visit(dec_visitor{}); - return new_node; - } catch (...) { - auto shift = pos.shift(); - auto size = new_idx == idx ? children + ts : ts; - if (shift > BL) { - tail->inc(); - dec_inner(new_child, shift - B, size); - } - throw; - } - } - } - - template <typename Pos, typename... Args> - static node_t* visit_regular(Pos&& pos, edit_t e, node_t* tail, Args&&...) - { - assert((pos.size() & mask<BL>) == 0); - auto node = pos.node(); - auto idx = pos.index(pos.size() - 1); - auto new_idx = pos.index(pos.size() + branches<BL> - 1); - auto mutate = Mutating && node->can_mutate(e); - if (mutate) { - node->inner()[new_idx] = - idx == new_idx ? pos.last_oh(this_t{}, idx, e, tail) - /* otherwise */ - : node_t::make_path_e(e, pos.shift() - B, tail); - return node; - } else { - auto new_parent = node_t::make_inner_e(e); - try { - new_parent->inner()[new_idx] = - idx == new_idx - ? pos.last_oh(this_no_mut_t{}, idx, e, tail) - /* otherwise */ - : node_t::make_path_e(e, pos.shift() - B, tail); - node_t::do_copy_inner(new_parent, node, new_idx); - if (Mutating) - pos.visit(dec_visitor{}); - return new_parent; - } catch (...) { - node_t::delete_inner_e(new_parent); - throw; - } - } - } - - template <typename Pos, typename... Args> - static node_t* visit_leaf(Pos&& pos, edit_t e, node_t* tail, Args&&...) - { - IMMER_UNREACHABLE; - } -}; - -template <typename NodeT> -struct push_tail_visitor : visitor_base<push_tail_visitor<NodeT>> -{ - static constexpr auto B = NodeT::bits; - static constexpr auto BL = NodeT::bits_leaf; - - using this_t = push_tail_visitor; - using node_t = NodeT; - - template <typename Pos> - static node_t* visit_relaxed(Pos&& pos, node_t* tail, count_t ts) - { - auto level = pos.shift(); - auto idx = pos.count() - 1; - auto children = pos.size(idx); - auto new_idx = - children == size_t{1} << level || level == BL ? idx + 1 : idx; - auto new_child = static_cast<node_t*>(nullptr); - if (new_idx >= branches<B>) - return nullptr; - else if (idx == new_idx) { - new_child = pos.last_oh_csh(this_t{}, idx, children, tail, ts); - if (!new_child) { - if (++new_idx < branches<B>) - new_child = node_t::make_path(level - B, tail); - else - return nullptr; - } - } else - new_child = node_t::make_path(level - B, tail); - try { - auto count = new_idx + 1; - auto new_parent = - node_t::copy_inner_r_n(count, pos.node(), new_idx); - auto new_relaxed = new_parent->relaxed(); - new_parent->inner()[new_idx] = new_child; - new_relaxed->d.sizes[new_idx] = pos.size() + ts; - new_relaxed->d.count = count; - return new_parent; - } catch (...) { - auto shift = pos.shift(); - auto size = new_idx == idx ? children + ts : ts; - if (shift > BL) { - tail->inc(); - dec_inner(new_child, shift - B, size); - } - throw; - } - } - - template <typename Pos, typename... Args> - static node_t* visit_regular(Pos&& pos, node_t* tail, Args&&...) - { - assert((pos.size() & mask<BL>) == 0); - auto idx = pos.index(pos.size() - 1); - auto new_idx = pos.index(pos.size() + branches<BL> - 1); - auto count = new_idx + 1; - auto new_parent = node_t::make_inner_n(count); - try { - new_parent->inner()[new_idx] = - idx == new_idx ? pos.last_oh(this_t{}, idx, tail) - /* otherwise */ - : node_t::make_path(pos.shift() - B, tail); - } catch (...) { - node_t::delete_inner(new_parent, count); - throw; - } - return node_t::do_copy_inner(new_parent, pos.node(), new_idx); - } - - template <typename Pos, typename... Args> - static node_t* visit_leaf(Pos&& pos, node_t* tail, Args&&...) - { - IMMER_UNREACHABLE; - } -}; - -struct dec_right_visitor : visitor_base<dec_right_visitor> -{ - using this_t = dec_right_visitor; - using dec_t = dec_visitor; - - template <typename Pos> - static void visit_relaxed(Pos&& p, count_t idx) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - p.each_right(dec_t{}, idx); - node_t::delete_inner_r(node, p.count()); - } - } - - template <typename Pos> - static void visit_regular(Pos&& p, count_t idx) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - p.each_right(dec_t{}, idx); - node_t::delete_inner(node, p.count()); - } - } - - template <typename Pos> - static void visit_leaf(Pos&& p, count_t idx) - { - IMMER_UNREACHABLE; - } -}; - -template <typename NodeT, bool Collapse = true, bool Mutating = true> -struct slice_right_mut_visitor - : visitor_base<slice_right_mut_visitor<NodeT, Collapse, Mutating>> -{ - using node_t = NodeT; - using this_t = slice_right_mut_visitor; - using edit_t = typename NodeT::edit_t; - - // returns a new shift, new root, the new tail size and the new tail - using result_t = std::tuple<shift_t, NodeT*, count_t, NodeT*>; - using no_collapse_t = slice_right_mut_visitor<NodeT, false, true>; - using no_collapse_no_mut_t = slice_right_mut_visitor<NodeT, false, false>; - using no_mut_t = slice_right_mut_visitor<NodeT, Collapse, false>; - - static constexpr auto B = NodeT::bits; - static constexpr auto BL = NodeT::bits_leaf; - - template <typename PosT> - static result_t visit_relaxed(PosT&& pos, size_t last, edit_t e) - { - auto idx = pos.index(last); - auto node = pos.node(); - auto mutate = Mutating && node->can_mutate(e); - if (Collapse && idx == 0) { - auto res = mutate ? pos.towards_oh(this_t{}, last, idx, e) - : pos.towards_oh(no_mut_t{}, last, idx, e); - if (Mutating) - pos.visit(dec_right_visitor{}, count_t{1}); - return res; - } else { - using std::get; - auto subs = - mutate ? pos.towards_oh(no_collapse_t{}, last, idx, e) - : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e); - auto next = get<1>(subs); - auto ts = get<2>(subs); - auto tail = get<3>(subs); - try { - if (next) { - if (mutate) { - auto nodr = node->ensure_mutable_relaxed_n(e, idx); - pos.each_right(dec_visitor{}, idx + 1); - node->inner()[idx] = next; - nodr->d.sizes[idx] = last + 1 - ts; - nodr->d.count = idx + 1; - return std::make_tuple(pos.shift(), node, ts, tail); - } else { - auto newn = node_t::copy_inner_r_e(e, node, idx); - auto newr = newn->relaxed(); - newn->inner()[idx] = next; - newr->d.sizes[idx] = last + 1 - ts; - newr->d.count = idx + 1; - if (Mutating) - pos.visit(dec_visitor{}); - return std::make_tuple(pos.shift(), newn, ts, tail); - } - } else if (idx == 0) { - if (Mutating) - pos.visit(dec_right_visitor{}, count_t{1}); - return std::make_tuple(pos.shift(), nullptr, ts, tail); - } else if (Collapse && idx == 1 && pos.shift() > BL) { - auto newn = pos.node()->inner()[0]; - if (!mutate) - newn->inc(); - if (Mutating) - pos.visit(dec_right_visitor{}, count_t{2}); - return std::make_tuple(pos.shift() - B, newn, ts, tail); - } else { - if (mutate) { - pos.each_right(dec_visitor{}, idx + 1); - node->ensure_mutable_relaxed_n(e, idx)->d.count = idx; - return std::make_tuple(pos.shift(), node, ts, tail); - } else { - auto newn = node_t::copy_inner_r_e(e, node, idx); - if (Mutating) - pos.visit(dec_visitor{}); - return std::make_tuple(pos.shift(), newn, ts, tail); - } - } - } catch (...) { - assert(!mutate); - assert(!next || pos.shift() > BL); - if (next) - dec_inner(next, - pos.shift() - B, - last + 1 - ts - pos.size_before(idx)); - dec_leaf(tail, ts); - throw; - } - } - } - - template <typename PosT> - static result_t visit_regular(PosT&& pos, size_t last, edit_t e) - { - auto idx = pos.index(last); - auto node = pos.node(); - auto mutate = Mutating && node->can_mutate(e); - if (Collapse && idx == 0) { - auto res = mutate ? pos.towards_oh(this_t{}, last, idx, e) - : pos.towards_oh(no_mut_t{}, last, idx, e); - if (Mutating) - pos.visit(dec_right_visitor{}, count_t{1}); - return res; - } else { - using std::get; - auto subs = - mutate ? pos.towards_oh(no_collapse_t{}, last, idx, e) - : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e); - auto next = get<1>(subs); - auto ts = get<2>(subs); - auto tail = get<3>(subs); - try { - if (next) { - if (mutate) { - node->inner()[idx] = next; - pos.each_right(dec_visitor{}, idx + 1); - return std::make_tuple(pos.shift(), node, ts, tail); - } else { - auto newn = node_t::copy_inner_e(e, node, idx); - newn->inner()[idx] = next; - if (Mutating) - pos.visit(dec_visitor{}); - return std::make_tuple(pos.shift(), newn, ts, tail); - } - } else if (idx == 0) { - if (Mutating) - pos.visit(dec_right_visitor{}, count_t{1}); - return std::make_tuple(pos.shift(), nullptr, ts, tail); - } else if (Collapse && idx == 1 && pos.shift() > BL) { - auto newn = pos.node()->inner()[0]; - if (!mutate) - newn->inc(); - if (Mutating) - pos.visit(dec_right_visitor{}, count_t{2}); - return std::make_tuple(pos.shift() - B, newn, ts, tail); - } else { - if (mutate) { - pos.each_right(dec_visitor{}, idx + 1); - return std::make_tuple(pos.shift(), node, ts, tail); - } else { - auto newn = node_t::copy_inner_e(e, node, idx); - if (Mutating) - pos.visit(dec_visitor{}); - return std::make_tuple(pos.shift(), newn, ts, tail); - } - } - } catch (...) { - assert(!mutate); - assert(!next || pos.shift() > BL); - assert(tail); - if (next) - dec_regular(next, pos.shift() - B, last + 1 - ts); - dec_leaf(tail, ts); - throw; - } - } - } - - template <typename PosT> - static result_t visit_leaf(PosT&& pos, size_t last, edit_t e) - { - auto old_tail_size = pos.count(); - auto new_tail_size = pos.index(last) + 1; - auto node = pos.node(); - auto mutate = Mutating && node->can_mutate(e); - if (new_tail_size == old_tail_size) { - if (!Mutating) - node->inc(); - return std::make_tuple(0, nullptr, new_tail_size, node); - } else if (mutate) { - destroy_n(node->leaf() + new_tail_size, - old_tail_size - new_tail_size); - return std::make_tuple(0, nullptr, new_tail_size, node); - } else { - auto new_tail = node_t::copy_leaf_e(e, node, new_tail_size); - if (Mutating) - pos.visit(dec_visitor{}); - return std::make_tuple(0, nullptr, new_tail_size, new_tail); - } - } -}; - -template <typename NodeT, bool Collapse = true> -struct slice_right_visitor : visitor_base<slice_right_visitor<NodeT, Collapse>> -{ - using node_t = NodeT; - using this_t = slice_right_visitor; - - // returns a new shift, new root, the new tail size and the new tail - using result_t = std::tuple<shift_t, NodeT*, count_t, NodeT*>; - using no_collapse_t = slice_right_visitor<NodeT, false>; - - static constexpr auto B = NodeT::bits; - static constexpr auto BL = NodeT::bits_leaf; - - template <typename PosT> - static result_t visit_relaxed(PosT&& pos, size_t last) - { - auto idx = pos.index(last); - if (Collapse && idx == 0) { - return pos.towards_oh(this_t{}, last, idx); - } else { - using std::get; - auto subs = pos.towards_oh(no_collapse_t{}, last, idx); - auto next = get<1>(subs); - auto ts = get<2>(subs); - auto tail = get<3>(subs); - try { - if (next) { - auto count = idx + 1; - auto newn = node_t::copy_inner_r_n(count, pos.node(), idx); - auto newr = newn->relaxed(); - newn->inner()[idx] = next; - newr->d.sizes[idx] = last + 1 - ts; - newr->d.count = count; - return std::make_tuple(pos.shift(), newn, ts, tail); - } else if (idx == 0) { - return std::make_tuple(pos.shift(), nullptr, ts, tail); - } else if (Collapse && idx == 1 && pos.shift() > BL) { - auto newn = pos.node()->inner()[0]; - return std::make_tuple( - pos.shift() - B, newn->inc(), ts, tail); - } else { - auto newn = node_t::copy_inner_r(pos.node(), idx); - return std::make_tuple(pos.shift(), newn, ts, tail); - } - } catch (...) { - assert(!next || pos.shift() > BL); - if (next) - dec_inner(next, - pos.shift() - B, - last + 1 - ts - pos.size_before(idx)); - if (tail) - dec_leaf(tail, ts); - throw; - } - } - } - - template <typename PosT> - static result_t visit_regular(PosT&& pos, size_t last) - { - auto idx = pos.index(last); - if (Collapse && idx == 0) { - return pos.towards_oh(this_t{}, last, idx); - } else { - using std::get; - auto subs = pos.towards_oh(no_collapse_t{}, last, idx); - auto next = get<1>(subs); - auto ts = get<2>(subs); - auto tail = get<3>(subs); - try { - if (next) { - auto newn = node_t::copy_inner_n(idx + 1, pos.node(), idx); - newn->inner()[idx] = next; - return std::make_tuple(pos.shift(), newn, ts, tail); - } else if (idx == 0) { - return std::make_tuple(pos.shift(), nullptr, ts, tail); - } else if (Collapse && idx == 1 && pos.shift() > BL) { - auto newn = pos.node()->inner()[0]; - return std::make_tuple( - pos.shift() - B, newn->inc(), ts, tail); - } else { - auto newn = node_t::copy_inner_n(idx, pos.node(), idx); - return std::make_tuple(pos.shift(), newn, ts, tail); - } - } catch (...) { - assert(!next || pos.shift() > BL); - assert(tail); - if (next) - dec_regular(next, pos.shift() - B, last + 1 - ts); - dec_leaf(tail, ts); - throw; - } - } - } - - template <typename PosT> - static result_t visit_leaf(PosT&& pos, size_t last) - { - auto old_tail_size = pos.count(); - auto new_tail_size = pos.index(last) + 1; - auto new_tail = new_tail_size == old_tail_size - ? pos.node()->inc() - : node_t::copy_leaf(pos.node(), new_tail_size); - return std::make_tuple(0, nullptr, new_tail_size, new_tail); - } -}; - -struct dec_left_visitor : visitor_base<dec_left_visitor> -{ - using this_t = dec_left_visitor; - using dec_t = dec_visitor; - - template <typename Pos> - static void visit_relaxed(Pos&& p, count_t idx) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - p.each_left(dec_t{}, idx); - node_t::delete_inner_r(node, p.count()); - } - } - - template <typename Pos> - static void visit_regular(Pos&& p, count_t idx) - { - using node_t = node_type<Pos>; - auto node = p.node(); - if (node->dec()) { - p.each_left(dec_t{}, idx); - node_t::delete_inner(node, p.count()); - } - } - - template <typename Pos> - static void visit_leaf(Pos&& p, count_t idx) - { - IMMER_UNREACHABLE; - } -}; - -template <typename NodeT, bool Collapse = true, bool Mutating = true> -struct slice_left_mut_visitor - : visitor_base<slice_left_mut_visitor<NodeT, Collapse, Mutating>> -{ - using node_t = NodeT; - using this_t = slice_left_mut_visitor; - using edit_t = typename NodeT::edit_t; - using value_t = typename NodeT::value_t; - using relaxed_t = typename NodeT::relaxed_t; - // returns a new shift and new root - using result_t = std::tuple<shift_t, NodeT*>; - - using no_collapse_t = slice_left_mut_visitor<NodeT, false, true>; - using no_collapse_no_mut_t = slice_left_mut_visitor<NodeT, false, false>; - using no_mut_t = slice_left_mut_visitor<NodeT, Collapse, false>; - - static constexpr auto B = NodeT::bits; - static constexpr auto BL = NodeT::bits_leaf; - - template <typename PosT> - static result_t visit_relaxed(PosT&& pos, size_t first, edit_t e) - { - auto idx = pos.subindex(first); - auto count = pos.count(); - auto node = pos.node(); - auto mutate = Mutating && node->can_mutate(e); - auto left_size = pos.size_before(idx); - auto child_size = pos.size_sbh(idx, left_size); - auto dropped_size = first; - auto child_dropped_size = dropped_size - left_size; - if (Collapse && pos.shift() > BL && idx == pos.count() - 1) { - auto r = mutate ? pos.towards_sub_oh(this_t{}, first, idx, e) - : pos.towards_sub_oh(no_mut_t{}, first, idx, e); - if (Mutating) - pos.visit(dec_left_visitor{}, idx); - return r; - } else { - using std::get; - auto newn = mutate ? (node->ensure_mutable_relaxed(e), node) - : node_t::make_inner_r_e(e); - auto newr = newn->relaxed(); - auto newcount = count - idx; - auto new_child_size = child_size - child_dropped_size; - try { - auto subs = - mutate ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e) - : pos.towards_sub_oh( - no_collapse_no_mut_t{}, first, idx, e); - if (mutate) - pos.each_left(dec_visitor{}, idx); - pos.copy_sizes( - idx + 1, newcount - 1, new_child_size, newr->d.sizes + 1); - std::uninitialized_copy(node->inner() + idx + 1, - node->inner() + count, - newn->inner() + 1); - newn->inner()[0] = get<1>(subs); - newr->d.sizes[0] = new_child_size; - newr->d.count = newcount; - if (!mutate) { - node_t::inc_nodes(newn->inner() + 1, newcount - 1); - if (Mutating) - pos.visit(dec_visitor{}); - } - return std::make_tuple(pos.shift(), newn); - } catch (...) { - if (!mutate) - node_t::delete_inner_r_e(newn); - throw; - } - } - } - - template <typename PosT> - static result_t visit_regular(PosT&& pos, size_t first, edit_t e) - { - auto idx = pos.subindex(first); - auto count = pos.count(); - auto node = pos.node(); - auto mutate = Mutating - // this is more restrictive than actually needed because - // it causes the algorithm to also avoid mutating the leaf - // in place - && !node_t::embed_relaxed && node->can_mutate(e); - auto left_size = pos.size_before(idx); - auto child_size = pos.size_sbh(idx, left_size); - auto dropped_size = first; - auto child_dropped_size = dropped_size - left_size; - if (Collapse && pos.shift() > BL && idx == pos.count() - 1) { - auto r = mutate ? pos.towards_sub_oh(this_t{}, first, idx, e) - : pos.towards_sub_oh(no_mut_t{}, first, idx, e); - if (Mutating) - pos.visit(dec_left_visitor{}, idx); - return r; - } else { - using std::get; - // if possible, we convert the node to a relaxed one - // simply by allocating a `relaxed_t` size table for - // it... maybe some of this magic should be moved as a - // `node<...>` static method... - auto newcount = count - idx; - auto newn = - mutate ? (node->impl.d.data.inner.relaxed = new ( - node_t::heap::allocate(node_t::max_sizeof_relaxed, - norefs_tag{})) relaxed_t, - node) - : node_t::make_inner_r_e(e); - auto newr = newn->relaxed(); - try { - auto subs = - mutate ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e) - : pos.towards_sub_oh( - no_collapse_no_mut_t{}, first, idx, e); - if (mutate) - pos.each_left(dec_visitor{}, idx); - newr->d.sizes[0] = child_size - child_dropped_size; - pos.copy_sizes( - idx + 1, newcount - 1, newr->d.sizes[0], newr->d.sizes + 1); - newr->d.count = newcount; - newn->inner()[0] = get<1>(subs); - std::uninitialized_copy(node->inner() + idx + 1, - node->inner() + count, - newn->inner() + 1); - if (!mutate) { - node_t::inc_nodes(newn->inner() + 1, newcount - 1); - if (Mutating) - pos.visit(dec_visitor{}); - } - return std::make_tuple(pos.shift(), newn); - } catch (...) { - if (!mutate) - node_t::delete_inner_r_e(newn); - else { - // restore the regular node that we were - // attempting to relax... - node_t::heap::deallocate(node_t::max_sizeof_relaxed, - node->impl.d.data.inner.relaxed); - node->impl.d.data.inner.relaxed = nullptr; - } - throw; - } - } - } - - template <typename PosT> - static result_t visit_leaf(PosT&& pos, size_t first, edit_t e) - { - auto node = pos.node(); - auto idx = pos.index(first); - auto count = pos.count(); - auto mutate = Mutating && - std::is_nothrow_move_constructible<value_t>::value && - node->can_mutate(e); - if (mutate) { - auto data = node->leaf(); - auto newcount = count - idx; - std::move(data + idx, data + count, data); - destroy_n(data + newcount, idx); - return std::make_tuple(0, node); - } else { - auto newn = node_t::copy_leaf_e(e, node, idx, count); - if (Mutating) - pos.visit(dec_visitor{}); - return std::make_tuple(0, newn); - } - } -}; - -template <typename NodeT, bool Collapse = true> -struct slice_left_visitor : visitor_base<slice_left_visitor<NodeT, Collapse>> -{ - using node_t = NodeT; - using this_t = slice_left_visitor; - - // returns a new shift and new root - using result_t = std::tuple<shift_t, NodeT*>; - using no_collapse_t = slice_left_visitor<NodeT, false>; - - static constexpr auto B = NodeT::bits; - static constexpr auto BL = NodeT::bits_leaf; - - template <typename PosT> - static result_t visit_inner(PosT&& pos, size_t first) - { - auto idx = pos.subindex(first); - auto count = pos.count(); - auto left_size = pos.size_before(idx); - auto child_size = pos.size_sbh(idx, left_size); - auto dropped_size = first; - auto child_dropped_size = dropped_size - left_size; - if (Collapse && pos.shift() > BL && idx == pos.count() - 1) { - return pos.towards_sub_oh(this_t{}, first, idx); - } else { - using std::get; - auto n = pos.node(); - auto newc = count - idx; - auto newn = node_t::make_inner_r_n(newc); - try { - auto subs = pos.towards_sub_oh(no_collapse_t{}, first, idx); - auto newr = newn->relaxed(); - newr->d.count = count - idx; - newr->d.sizes[0] = child_size - child_dropped_size; - pos.copy_sizes(idx + 1, - newr->d.count - 1, - newr->d.sizes[0], - newr->d.sizes + 1); - assert(newr->d.sizes[newr->d.count - 1] == - pos.size() - dropped_size); - newn->inner()[0] = get<1>(subs); - std::uninitialized_copy(n->inner() + idx + 1, - n->inner() + count, - newn->inner() + 1); - node_t::inc_nodes(newn->inner() + 1, newr->d.count - 1); - return std::make_tuple(pos.shift(), newn); - } catch (...) { - node_t::delete_inner_r(newn, newc); - throw; - } - } - } - - template <typename PosT> - static result_t visit_leaf(PosT&& pos, size_t first) - { - auto n = node_t::copy_leaf(pos.node(), pos.index(first), pos.count()); - return std::make_tuple(0, n); - } -}; - -template <typename Node> -struct concat_center_pos -{ - static constexpr auto B = Node::bits; - static constexpr auto BL = Node::bits_leaf; - - static constexpr count_t max_children = 3; - - using node_t = Node; - using edit_t = typename Node::edit_t; - - shift_t shift_ = 0u; - count_t count_ = 0u; - node_t* nodes_[max_children]; - size_t sizes_[max_children]; - - auto shift() const { return shift_; } - - concat_center_pos(shift_t s, Node* n0, size_t s0) - : shift_{s} - , count_{1} - , nodes_{n0} - , sizes_{s0} - {} - - concat_center_pos(shift_t s, Node* n0, size_t s0, Node* n1, size_t s1) - : shift_{s} - , count_{2} - , nodes_{n0, n1} - , sizes_{s0, s1} - {} - - concat_center_pos(shift_t s, - Node* n0, - size_t s0, - Node* n1, - size_t s1, - Node* n2, - size_t s2) - : shift_{s} - , count_{3} - , nodes_{n0, n1, n2} - , sizes_{s0, s1, s2} - {} - - template <typename Visitor, typename... Args> - void each_sub(Visitor v, Args&&... args) - { - if (shift_ == BL) { - for (auto i = count_t{0}; i < count_; ++i) - make_leaf_sub_pos(nodes_[i], sizes_[i]).visit(v, args...); - } else { - for (auto i = count_t{0}; i < count_; ++i) - make_relaxed_pos(nodes_[i], shift_ - B, nodes_[i]->relaxed()) - .visit(v, args...); - } - } - - relaxed_pos<Node> realize() && - { - if (count_ > 1) { - try { - auto result = node_t::make_inner_r_n(count_); - auto r = result->relaxed(); - r->d.count = count_; - std::copy(nodes_, nodes_ + count_, result->inner()); - std::copy(sizes_, sizes_ + count_, r->d.sizes); - return {result, shift_, r}; - } catch (...) { - each_sub(dec_visitor{}); - throw; - } - } else { - assert(shift_ >= B + BL); - return {nodes_[0], shift_ - B, nodes_[0]->relaxed()}; - } - } - - relaxed_pos<Node> realize_e(edit_t e) - { - if (count_ > 1) { - auto result = node_t::make_inner_r_e(e); - auto r = result->relaxed(); - r->d.count = count_; - std::copy(nodes_, nodes_ + count_, result->inner()); - std::copy(sizes_, sizes_ + count_, r->d.sizes); - return {result, shift_, r}; - } else { - assert(shift_ >= B + BL); - return {nodes_[0], shift_ - B, nodes_[0]->relaxed()}; - } - } -}; - -template <typename Node> -struct concat_merger -{ - using node_t = Node; - static constexpr auto B = Node::bits; - static constexpr auto BL = Node::bits_leaf; - - using result_t = concat_center_pos<Node>; - - count_t* curr_; - count_t n_; - result_t result_; - - concat_merger(shift_t shift, count_t* counts, count_t n) - : curr_{counts} - , n_{n} - , result_{ - shift + B, node_t::make_inner_r_n(std::min(n_, branches<B>)), 0} - {} - - node_t* to_ = {}; - count_t to_offset_ = {}; - size_t to_size_ = {}; - - void add_child(node_t* p, size_t size) - { - ++curr_; - auto parent = result_.nodes_[result_.count_ - 1]; - auto relaxed = parent->relaxed(); - if (relaxed->d.count == branches<B>) { - assert(result_.count_ < result_t::max_children); - n_ -= branches<B>; - parent = node_t::make_inner_r_n(std::min(n_, branches<B>)); - relaxed = parent->relaxed(); - result_.nodes_[result_.count_] = parent; - result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1]; - ++result_.count_; - } - auto idx = relaxed->d.count++; - result_.sizes_[result_.count_ - 1] += size; - relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0); - parent->inner()[idx] = p; - }; - - template <typename Pos> - void merge_leaf(Pos&& p) - { - auto from = p.node(); - auto from_size = p.size(); - auto from_count = p.count(); - assert(from_size); - if (!to_ && *curr_ == from_count) { - add_child(from, from_size); - from->inc(); - } else { - auto from_offset = count_t{}; - auto from_data = from->leaf(); - do { - if (!to_) { - to_ = node_t::make_leaf_n(*curr_); - to_offset_ = 0; - } - auto data = to_->leaf(); - auto to_copy = - std::min(from_count - from_offset, *curr_ - to_offset_); - std::uninitialized_copy(from_data + from_offset, - from_data + from_offset + to_copy, - data + to_offset_); - to_offset_ += to_copy; - from_offset += to_copy; - if (*curr_ == to_offset_) { - add_child(to_, to_offset_); - to_ = nullptr; - } - } while (from_offset != from_count); - } - } - - template <typename Pos> - void merge_inner(Pos&& p) - { - auto from = p.node(); - auto from_size = p.size(); - auto from_count = p.count(); - assert(from_size); - if (!to_ && *curr_ == from_count) { - add_child(from, from_size); - from->inc(); - } else { - auto from_offset = count_t{}; - auto from_data = from->inner(); - do { - if (!to_) { - to_ = node_t::make_inner_r_n(*curr_); - to_offset_ = 0; - to_size_ = 0; - } - auto data = to_->inner(); - auto to_copy = - std::min(from_count - from_offset, *curr_ - to_offset_); - std::uninitialized_copy(from_data + from_offset, - from_data + from_offset + to_copy, - data + to_offset_); - node_t::inc_nodes(from_data + from_offset, to_copy); - auto sizes = to_->relaxed()->d.sizes; - p.copy_sizes( - from_offset, to_copy, to_size_, sizes + to_offset_); - to_offset_ += to_copy; - from_offset += to_copy; - to_size_ = sizes[to_offset_ - 1]; - if (*curr_ == to_offset_) { - to_->relaxed()->d.count = to_offset_; - add_child(to_, to_size_); - to_ = nullptr; - } - } while (from_offset != from_count); - } - } - - concat_center_pos<Node> finish() const - { - assert(!to_); - return result_; - } - - void abort() - { - auto shift = result_.shift_ - B; - if (to_) { - if (shift == BL) - node_t::delete_leaf(to_, to_offset_); - else { - to_->relaxed()->d.count = to_offset_; - dec_relaxed(to_, shift - B); - } - } - result_.each_sub(dec_visitor()); - } -}; - -struct concat_merger_visitor : visitor_base<concat_merger_visitor> -{ - using this_t = concat_merger_visitor; - - template <typename Pos, typename Merger> - static void visit_inner(Pos&& p, Merger& merger) - { - merger.merge_inner(p); - } - - template <typename Pos, typename Merger> - static void visit_leaf(Pos&& p, Merger& merger) - { - merger.merge_leaf(p); - } -}; - -struct concat_rebalance_plan_fill_visitor - : visitor_base<concat_rebalance_plan_fill_visitor> -{ - using this_t = concat_rebalance_plan_fill_visitor; - - template <typename Pos, typename Plan> - static void visit_node(Pos&& p, Plan& plan) - { - auto count = p.count(); - assert(plan.n < Plan::max_children); - plan.counts[plan.n++] = count; - plan.total += count; - } -}; - -template <bits_t B, bits_t BL> -struct concat_rebalance_plan -{ - static constexpr auto max_children = 2 * branches<B> + 1; - - count_t counts[max_children]; - count_t n = 0u; - count_t total = 0u; - - template <typename LPos, typename CPos, typename RPos> - void fill(LPos&& lpos, CPos&& cpos, RPos&& rpos) - { - assert(n == 0u); - assert(total == 0u); - using visitor_t = concat_rebalance_plan_fill_visitor; - lpos.each_left_sub(visitor_t{}, *this); - cpos.each_sub(visitor_t{}, *this); - rpos.each_right_sub(visitor_t{}, *this); - } - - void shuffle(shift_t shift) - { - // gcc seems to not really understand this code... :( -#if !defined(_MSC_VER) -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Warray-bounds" -#endif - constexpr count_t rrb_extras = 2; - constexpr count_t rrb_invariant = 1; - const auto bits = shift == BL ? BL : B; - const auto branches = count_t{1} << bits; - const auto optimal = ((total - 1) >> bits) + 1; - count_t i = 0; - while (n >= optimal + rrb_extras) { - // skip ok nodes - while (counts[i] > branches - rrb_invariant) - i++; - // short node, redistribute - auto remaining = counts[i]; - do { - auto count = std::min(remaining + counts[i + 1], branches); - counts[i] = count; - remaining += counts[i + 1] - count; - ++i; - } while (remaining > 0); - // remove node - std::move(counts + i + 1, counts + n, counts + i); - --n; - --i; - } -#if !defined(_MSC_VER) -#pragma GCC diagnostic pop -#endif - } - - template <typename LPos, typename CPos, typename RPos> - concat_center_pos<node_type<CPos>> - merge(LPos&& lpos, CPos&& cpos, RPos&& rpos) - { - using node_t = node_type<CPos>; - using merger_t = concat_merger<node_t>; - using visitor_t = concat_merger_visitor; - auto merger = merger_t{cpos.shift(), counts, n}; - try { - lpos.each_left_sub(visitor_t{}, merger); - cpos.each_sub(visitor_t{}, merger); - rpos.each_right_sub(visitor_t{}, merger); - cpos.each_sub(dec_visitor{}); - return merger.finish(); - } catch (...) { - merger.abort(); - throw; - } - } -}; - -template <typename Node, typename LPos, typename CPos, typename RPos> -concat_center_pos<Node> concat_rebalance(LPos&& lpos, CPos&& cpos, RPos&& rpos) -{ - auto plan = concat_rebalance_plan<Node::bits, Node::bits_leaf>{}; - plan.fill(lpos, cpos, rpos); - plan.shuffle(cpos.shift()); - try { - return plan.merge(lpos, cpos, rpos); - } catch (...) { - cpos.each_sub(dec_visitor{}); - throw; - } -} - -template <typename Node, typename LPos, typename TPos, typename RPos> -concat_center_pos<Node> concat_leafs(LPos&& lpos, TPos&& tpos, RPos&& rpos) -{ - static_assert(Node::bits >= 2, ""); - assert(lpos.shift() == tpos.shift()); - assert(lpos.shift() == rpos.shift()); - assert(lpos.shift() == 0); - if (tpos.count() > 0) - return { - Node::bits_leaf, - lpos.node()->inc(), - lpos.count(), - tpos.node()->inc(), - tpos.count(), - rpos.node()->inc(), - rpos.count(), - }; - else - return { - Node::bits_leaf, - lpos.node()->inc(), - lpos.count(), - rpos.node()->inc(), - rpos.count(), - }; -} - -template <typename Node> -struct concat_left_visitor; -template <typename Node> -struct concat_right_visitor; -template <typename Node> -struct concat_both_visitor; - -template <typename Node, typename LPos, typename TPos, typename RPos> -concat_center_pos<Node> concat_inners(LPos&& lpos, TPos&& tpos, RPos&& rpos) -{ - auto lshift = lpos.shift(); - auto rshift = rpos.shift(); - if (lshift > rshift) { - auto cpos = lpos.last_sub(concat_left_visitor<Node>{}, tpos, rpos); - return concat_rebalance<Node>(lpos, cpos, null_sub_pos{}); - } else if (lshift < rshift) { - auto cpos = rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos); - return concat_rebalance<Node>(null_sub_pos{}, cpos, rpos); - } else { - assert(lshift == rshift); - assert(Node::bits_leaf == 0u || lshift > 0); - auto cpos = lpos.last_sub(concat_both_visitor<Node>{}, tpos, rpos); - return concat_rebalance<Node>(lpos, cpos, rpos); - } -} - -template <typename Node> -struct concat_left_visitor : visitor_base<concat_left_visitor<Node>> -{ - using this_t = concat_left_visitor; - - template <typename LPos, typename TPos, typename RPos> - static concat_center_pos<Node> - visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos) - { - return concat_inners<Node>(lpos, tpos, rpos); - } - - template <typename LPos, typename TPos, typename RPos> - static concat_center_pos<Node> - visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos) - { - IMMER_UNREACHABLE; - } -}; - -template <typename Node> -struct concat_right_visitor : visitor_base<concat_right_visitor<Node>> -{ - using this_t = concat_right_visitor; - - template <typename RPos, typename LPos, typename TPos> - static concat_center_pos<Node> - visit_inner(RPos&& rpos, LPos&& lpos, TPos&& tpos) - { - return concat_inners<Node>(lpos, tpos, rpos); - } - - template <typename RPos, typename LPos, typename TPos> - static concat_center_pos<Node> - visit_leaf(RPos&& rpos, LPos&& lpos, TPos&& tpos) - { - return concat_leafs<Node>(lpos, tpos, rpos); - } -}; - -template <typename Node> -struct concat_both_visitor : visitor_base<concat_both_visitor<Node>> -{ - using this_t = concat_both_visitor; - - template <typename LPos, typename TPos, typename RPos> - static concat_center_pos<Node> - visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos) - { - return rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos); - } - - template <typename LPos, typename TPos, typename RPos> - static concat_center_pos<Node> - visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos) - { - return rpos.first_sub_leaf(concat_right_visitor<Node>{}, lpos, tpos); - } -}; - -template <typename Node> -struct concat_trees_right_visitor - : visitor_base<concat_trees_right_visitor<Node>> -{ - using this_t = concat_trees_right_visitor; - - template <typename RPos, typename LPos, typename TPos> - static concat_center_pos<Node> - visit_node(RPos&& rpos, LPos&& lpos, TPos&& tpos) - { - return concat_inners<Node>(lpos, tpos, rpos); - } -}; - -template <typename Node> -struct concat_trees_left_visitor : visitor_base<concat_trees_left_visitor<Node>> -{ - using this_t = concat_trees_left_visitor; - - template <typename LPos, typename TPos, typename... Args> - static concat_center_pos<Node> - visit_node(LPos&& lpos, TPos&& tpos, Args&&... args) - { - return visit_maybe_relaxed_sub( - args..., concat_trees_right_visitor<Node>{}, lpos, tpos); - } -}; - -template <typename Node> -relaxed_pos<Node> concat_trees(Node* lroot, - shift_t lshift, - size_t lsize, - Node* ltail, - count_t ltcount, - Node* rroot, - shift_t rshift, - size_t rsize) -{ - return visit_maybe_relaxed_sub(lroot, - lshift, - lsize, - concat_trees_left_visitor<Node>{}, - make_leaf_pos(ltail, ltcount), - rroot, - rshift, - rsize) - .realize(); -} - -template <typename Node> -relaxed_pos<Node> concat_trees( - Node* ltail, count_t ltcount, Node* rroot, shift_t rshift, size_t rsize) -{ - return make_singleton_regular_sub_pos(ltail, ltcount) - .visit(concat_trees_left_visitor<Node>{}, - empty_leaf_pos<Node>{}, - rroot, - rshift, - rsize) - .realize(); -} - -template <typename Node> -using concat_center_mut_pos = concat_center_pos<Node>; - -template <typename Node> -struct concat_merger_mut -{ - using node_t = Node; - using edit_t = typename Node::edit_t; - - static constexpr auto B = Node::bits; - static constexpr auto BL = Node::bits_leaf; - - using result_t = concat_center_pos<Node>; - - edit_t ec_ = {}; - - count_t* curr_; - count_t n_; - result_t result_; - count_t count_ = 0; - node_t* candidate_ = nullptr; - edit_t candidate_e_ = Node::memory::transience_t::noone; - - concat_merger_mut(edit_t ec, - shift_t shift, - count_t* counts, - count_t n, - edit_t candidate_e, - node_t* candidate) - : ec_{ec} - , curr_{counts} - , n_{n} - , result_{shift + B, nullptr, 0} - { - if (candidate) { - candidate->ensure_mutable_relaxed_e(candidate_e, ec); - result_.nodes_[0] = candidate; - } else { - result_.nodes_[0] = node_t::make_inner_r_e(ec); - } - } - - node_t* to_ = {}; - count_t to_offset_ = {}; - size_t to_size_ = {}; - - void set_candidate(edit_t candidate_e, node_t* candidate) - { - candidate_ = candidate; - candidate_e_ = candidate_e; - } - - void add_child(node_t* p, size_t size) - { - ++curr_; - auto parent = result_.nodes_[result_.count_ - 1]; - auto relaxed = parent->relaxed(); - if (count_ == branches<B>) { - parent->relaxed()->d.count = count_; - assert(result_.count_ < result_t::max_children); - n_ -= branches<B>; - if (candidate_) { - parent = candidate_; - parent->ensure_mutable_relaxed_e(candidate_e_, ec_); - candidate_ = nullptr; - } else - parent = node_t::make_inner_r_e(ec_); - count_ = 0; - relaxed = parent->relaxed(); - result_.nodes_[result_.count_] = parent; - result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1]; - ++result_.count_; - } - auto idx = count_++; - result_.sizes_[result_.count_ - 1] += size; - relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0); - parent->inner()[idx] = p; - }; - - template <typename Pos> - void merge_leaf(Pos&& p, edit_t e) - { - auto from = p.node(); - auto from_size = p.size(); - auto from_count = p.count(); - assert(from_size); - if (!to_ && *curr_ == from_count) { - add_child(from, from_size); - } else { - auto from_offset = count_t{}; - auto from_data = from->leaf(); - auto from_mutate = from->can_mutate(e); - do { - if (!to_) { - if (from_mutate) { - node_t::ownee(from) = ec_; - to_ = from->inc(); - assert(from_count); - } else { - to_ = node_t::make_leaf_e(ec_); - } - to_offset_ = 0; - } - auto data = to_->leaf(); - auto to_copy = - std::min(from_count - from_offset, *curr_ - to_offset_); - if (from == to_) { - if (from_offset != to_offset_) - std::move(from_data + from_offset, - from_data + from_offset + to_copy, - data + to_offset_); - } else { - if (!from_mutate) - std::uninitialized_copy(from_data + from_offset, - from_data + from_offset + - to_copy, - data + to_offset_); - else - detail::uninitialized_move(from_data + from_offset, - from_data + from_offset + - to_copy, - data + to_offset_); - } - to_offset_ += to_copy; - from_offset += to_copy; - if (*curr_ == to_offset_) { - add_child(to_, to_offset_); - to_ = nullptr; - } - } while (from_offset != from_count); - } - } - - template <typename Pos> - void merge_inner(Pos&& p, edit_t e) - { - auto from = p.node(); - auto from_size = p.size(); - auto from_count = p.count(); - assert(from_size); - if (!to_ && *curr_ == from_count) { - add_child(from, from_size); - } else { - auto from_offset = count_t{}; - auto from_data = from->inner(); - auto from_mutate = from->can_relax() && from->can_mutate(e); - do { - if (!to_) { - if (from_mutate) { - node_t::ownee(from) = ec_; - from->ensure_mutable_relaxed_e(e, ec_); - to_ = from; - } else { - to_ = node_t::make_inner_r_e(ec_); - } - to_offset_ = 0; - to_size_ = 0; - } - auto data = to_->inner(); - auto to_copy = - std::min(from_count - from_offset, *curr_ - to_offset_); - auto sizes = to_->relaxed()->d.sizes; - if (from != to_ || from_offset != to_offset_) { - std::copy(from_data + from_offset, - from_data + from_offset + to_copy, - data + to_offset_); - p.copy_sizes( - from_offset, to_copy, to_size_, sizes + to_offset_); - } - to_offset_ += to_copy; - from_offset += to_copy; - to_size_ = sizes[to_offset_ - 1]; - if (*curr_ == to_offset_) { - to_->relaxed()->d.count = to_offset_; - add_child(to_, to_size_); - to_ = nullptr; - } - } while (from_offset != from_count); - } - } - - concat_center_pos<Node> finish() const - { - assert(!to_); - result_.nodes_[result_.count_ - 1]->relaxed()->d.count = count_; - return result_; - } - - void abort() - { - // We may have mutated stuff the tree in place, leaving - // everything in a corrupted state... It should be possible - // to define cleanup properly, but that is a task for some - // other day... ;) - std::terminate(); - } -}; - -struct concat_merger_mut_visitor : visitor_base<concat_merger_mut_visitor> -{ - using this_t = concat_merger_mut_visitor; - - template <typename Pos, typename Merger> - static void visit_inner(Pos&& p, Merger& merger, edit_type<Pos> e) - { - merger.merge_inner(p, e); - } - - template <typename Pos, typename Merger> - static void visit_leaf(Pos&& p, Merger& merger, edit_type<Pos> e) - { - merger.merge_leaf(p, e); - } -}; - -template <bits_t B, bits_t BL> -struct concat_rebalance_plan_mut : concat_rebalance_plan<B, BL> -{ - using this_t = concat_rebalance_plan_mut; - - template <typename LPos, typename CPos, typename RPos> - concat_center_mut_pos<node_type<CPos>> merge(edit_type<CPos> ec, - edit_type<CPos> el, - LPos&& lpos, - CPos&& cpos, - edit_type<CPos> er, - RPos&& rpos) - { - using node_t = node_type<CPos>; - using merger_t = concat_merger_mut<node_t>; - using visitor_t = concat_merger_mut_visitor; - auto lnode = ((node_t*) lpos.node()); - auto rnode = ((node_t*) rpos.node()); - auto lmut2 = lnode && lnode->can_relax() && lnode->can_mutate(el); - auto rmut2 = rnode && rnode->can_relax() && rnode->can_mutate(er); - auto merger = merger_t{ec, - cpos.shift(), - this->counts, - this->n, - el, - lmut2 ? lnode : nullptr}; - try { - lpos.each_left_sub(visitor_t{}, merger, el); - cpos.each_sub(visitor_t{}, merger, ec); - if (rmut2) - merger.set_candidate(er, rnode); - rpos.each_right_sub(visitor_t{}, merger, er); - return merger.finish(); - } catch (...) { - merger.abort(); - throw; - } - } -}; - -template <typename Node, typename LPos, typename CPos, typename RPos> -concat_center_pos<Node> concat_rebalance_mut(edit_type<Node> ec, - edit_type<Node> el, - LPos&& lpos, - CPos&& cpos, - edit_type<Node> er, - RPos&& rpos) -{ - auto plan = concat_rebalance_plan_mut<Node::bits, Node::bits_leaf>{}; - plan.fill(lpos, cpos, rpos); - plan.shuffle(cpos.shift()); - return plan.merge(ec, el, lpos, cpos, er, rpos); -} - -template <typename Node, typename LPos, typename TPos, typename RPos> -concat_center_mut_pos<Node> concat_leafs_mut(edit_type<Node> ec, - edit_type<Node> el, - LPos&& lpos, - TPos&& tpos, - edit_type<Node> er, - RPos&& rpos) -{ - static_assert(Node::bits >= 2, ""); - assert(lpos.shift() == tpos.shift()); - assert(lpos.shift() == rpos.shift()); - assert(lpos.shift() == 0); - if (tpos.count() > 0) - return { - Node::bits_leaf, - lpos.node(), - lpos.count(), - tpos.node(), - tpos.count(), - rpos.node(), - rpos.count(), - }; - else - return { - Node::bits_leaf, - lpos.node(), - lpos.count(), - rpos.node(), - rpos.count(), - }; -} - -template <typename Node> -struct concat_left_mut_visitor; -template <typename Node> -struct concat_right_mut_visitor; -template <typename Node> -struct concat_both_mut_visitor; - -template <typename Node, typename LPos, typename TPos, typename RPos> -concat_center_mut_pos<Node> concat_inners_mut(edit_type<Node> ec, - edit_type<Node> el, - LPos&& lpos, - TPos&& tpos, - edit_type<Node> er, - RPos&& rpos) -{ - auto lshift = lpos.shift(); - auto rshift = rpos.shift(); - // lpos.node() can be null it is a singleton_regular_sub_pos<...>, - // this is, when the tree is just a tail... - if (lshift > rshift) { - auto cpos = lpos.last_sub( - concat_left_mut_visitor<Node>{}, ec, el, tpos, er, rpos); - return concat_rebalance_mut<Node>( - ec, el, lpos, cpos, er, null_sub_pos{}); - } else if (lshift < rshift) { - auto cpos = rpos.first_sub( - concat_right_mut_visitor<Node>{}, ec, el, lpos, tpos, er); - return concat_rebalance_mut<Node>( - ec, el, null_sub_pos{}, cpos, er, rpos); - } else { - assert(lshift == rshift); - assert(Node::bits_leaf == 0u || lshift > 0); - auto cpos = lpos.last_sub( - concat_both_mut_visitor<Node>{}, ec, el, tpos, er, rpos); - return concat_rebalance_mut<Node>(ec, el, lpos, cpos, er, rpos); - } -} - -template <typename Node> -struct concat_left_mut_visitor : visitor_base<concat_left_mut_visitor<Node>> -{ - using this_t = concat_left_mut_visitor; - using edit_t = typename Node::edit_t; - - template <typename LPos, typename TPos, typename RPos> - static concat_center_mut_pos<Node> visit_inner( - LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos) - { - return concat_inners_mut<Node>(ec, el, lpos, tpos, er, rpos); - } - - template <typename LPos, typename TPos, typename RPos> - static concat_center_mut_pos<Node> visit_leaf( - LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos) - { - IMMER_UNREACHABLE; - } -}; - -template <typename Node> -struct concat_right_mut_visitor : visitor_base<concat_right_mut_visitor<Node>> -{ - using this_t = concat_right_mut_visitor; - using edit_t = typename Node::edit_t; - - template <typename RPos, typename LPos, typename TPos> - static concat_center_mut_pos<Node> visit_inner( - RPos&& rpos, edit_t ec, edit_t el, LPos&& lpos, TPos&& tpos, edit_t er) - { - return concat_inners_mut<Node>(ec, el, lpos, tpos, er, rpos); - } - - template <typename RPos, typename LPos, typename TPos> - static concat_center_mut_pos<Node> visit_leaf( - RPos&& rpos, edit_t ec, edit_t el, LPos&& lpos, TPos&& tpos, edit_t er) - { - return concat_leafs_mut<Node>(ec, el, lpos, tpos, er, rpos); - } -}; - -template <typename Node> -struct concat_both_mut_visitor : visitor_base<concat_both_mut_visitor<Node>> -{ - using this_t = concat_both_mut_visitor; - using edit_t = typename Node::edit_t; - - template <typename LPos, typename TPos, typename RPos> - static concat_center_mut_pos<Node> visit_inner( - LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos) - { - return rpos.first_sub( - concat_right_mut_visitor<Node>{}, ec, el, lpos, tpos, er); - } - - template <typename LPos, typename TPos, typename RPos> - static concat_center_mut_pos<Node> visit_leaf( - LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos) - { - return rpos.first_sub_leaf( - concat_right_mut_visitor<Node>{}, ec, el, lpos, tpos, er); - } -}; - -template <typename Node> -struct concat_trees_right_mut_visitor - : visitor_base<concat_trees_right_mut_visitor<Node>> -{ - using this_t = concat_trees_right_mut_visitor; - using edit_t = typename Node::edit_t; - - template <typename RPos, typename LPos, typename TPos> - static concat_center_mut_pos<Node> visit_node( - RPos&& rpos, edit_t ec, edit_t el, LPos&& lpos, TPos&& tpos, edit_t er) - { - return concat_inners_mut<Node>(ec, el, lpos, tpos, er, rpos); - } -}; - -template <typename Node> -struct concat_trees_left_mut_visitor - : visitor_base<concat_trees_left_mut_visitor<Node>> -{ - using this_t = concat_trees_left_mut_visitor; - using edit_t = typename Node::edit_t; - - template <typename LPos, typename TPos, typename... Args> - static concat_center_mut_pos<Node> visit_node(LPos&& lpos, - edit_t ec, - edit_t el, - TPos&& tpos, - edit_t er, - Args&&... args) - { - return visit_maybe_relaxed_sub(args..., - concat_trees_right_mut_visitor<Node>{}, - ec, - el, - lpos, - tpos, - er); - } -}; - -template <typename Node> -relaxed_pos<Node> concat_trees_mut(edit_type<Node> ec, - edit_type<Node> el, - Node* lroot, - shift_t lshift, - size_t lsize, - Node* ltail, - count_t ltcount, - edit_type<Node> er, - Node* rroot, - shift_t rshift, - size_t rsize) -{ - return visit_maybe_relaxed_sub(lroot, - lshift, - lsize, - concat_trees_left_mut_visitor<Node>{}, - ec, - el, - make_leaf_pos(ltail, ltcount), - er, - rroot, - rshift, - rsize) - .realize_e(ec); -} - -template <typename Node> -relaxed_pos<Node> concat_trees_mut(edit_type<Node> ec, - edit_type<Node> el, - Node* ltail, - count_t ltcount, - edit_type<Node> er, - Node* rroot, - shift_t rshift, - size_t rsize) -{ - return make_singleton_regular_sub_pos(ltail, ltcount) - .visit(concat_trees_left_mut_visitor<Node>{}, - ec, - el, - empty_leaf_pos<Node>{}, - er, - rroot, - rshift, - rsize) - .realize_e(ec); -} - -} // namespace rbts -} // namespace detail -} // namespace immer |