//
// 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
