diff options
Diffstat (limited to 'third_party/immer/immer/detail/rbts/rrbtree.hpp')
| -rw-r--r-- | third_party/immer/immer/detail/rbts/rrbtree.hpp | 1396 |
1 files changed, 0 insertions, 1396 deletions
diff --git a/third_party/immer/immer/detail/rbts/rrbtree.hpp b/third_party/immer/immer/detail/rbts/rrbtree.hpp deleted file mode 100644 index 7bf59e6e92b1..000000000000 --- a/third_party/immer/immer/detail/rbts/rrbtree.hpp +++ /dev/null @@ -1,1396 +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 <immer/config.hpp> -#include <immer/detail/rbts/node.hpp> -#include <immer/detail/rbts/operations.hpp> -#include <immer/detail/rbts/position.hpp> - -#include <immer/detail/type_traits.hpp> - -#include <cassert> -#include <memory> -#include <numeric> - -namespace immer { -namespace detail { -namespace rbts { - -template <typename T, typename MemoryPolicy, bits_t B, bits_t BL> -struct rrbtree_iterator; - -template <typename T, typename MemoryPolicy, bits_t B, bits_t BL> -struct rrbtree -{ - using node_t = node<T, MemoryPolicy, B, BL>; - using edit_t = typename node_t::edit_t; - using owner_t = typename MemoryPolicy::transience_t::owner; - - size_t size; - shift_t shift; - node_t* root; - node_t* tail; - - static const rrbtree& empty() - { - static const rrbtree empty_{ - 0, BL, node_t::make_inner_n(0u), node_t::make_leaf_n(0u)}; - return empty_; - } - - template <typename U> - static auto from_initializer_list(std::initializer_list<U> values) - { - auto e = owner_t{}; - auto result = rrbtree{empty()}; - for (auto&& v : values) - result.push_back_mut(e, v); - return result; - } - - template <typename Iter, - typename Sent, - std::enable_if_t<compatible_sentinel_v<Iter, Sent>, bool> = true> - static auto from_range(Iter first, Sent last) - { - auto e = owner_t{}; - auto result = rrbtree{empty()}; - for (; first != last; ++first) - result.push_back_mut(e, *first); - return result; - } - - static auto from_fill(size_t n, T v) - { - auto e = owner_t{}; - auto result = rrbtree{empty()}; - while (n-- > 0) - result.push_back_mut(e, v); - return result; - } - - rrbtree(size_t sz, shift_t sh, node_t* r, node_t* t) - : size{sz} - , shift{sh} - , root{r} - , tail{t} - { - assert(check_tree()); - } - - rrbtree(const rrbtree& other) - : rrbtree{other.size, other.shift, other.root, other.tail} - { - inc(); - } - - rrbtree(rrbtree&& other) - : rrbtree{empty()} - { - swap(*this, other); - } - - rrbtree& operator=(const rrbtree& other) - { - auto next{other}; - swap(*this, next); - return *this; - } - - rrbtree& operator=(rrbtree&& other) - { - swap(*this, other); - return *this; - } - - friend void swap(rrbtree& x, rrbtree& y) - { - using std::swap; - swap(x.size, y.size); - swap(x.shift, y.shift); - swap(x.root, y.root); - swap(x.tail, y.tail); - } - - ~rrbtree() { dec(); } - - void inc() const - { - root->inc(); - tail->inc(); - } - - void dec() const { traverse(dec_visitor()); } - - auto tail_size() const { return size - tail_offset(); } - - auto tail_offset() const - { - auto r = root->relaxed(); - assert(r == nullptr || r->d.count); - return r ? r->d.sizes[r->d.count - 1] - : size ? (size - 1) & ~mask<BL> - /* otherwise */ : 0; - } - - template <typename Visitor, typename... Args> - void traverse(Visitor v, Args&&... args) const - { - auto tail_off = tail_offset(); - auto tail_size = size - tail_off; - - if (tail_off) - visit_maybe_relaxed_sub(root, shift, tail_off, v, args...); - else - make_empty_regular_pos(root).visit(v, args...); - - if (tail_size) - make_leaf_sub_pos(tail, tail_size).visit(v, args...); - else - make_empty_leaf_pos(tail).visit(v, args...); - } - - template <typename Visitor, typename... Args> - void traverse(Visitor v, size_t first, size_t last, Args&&... args) const - { - auto tail_off = tail_offset(); - auto tail_size = size - tail_off; - - if (first < tail_off) - visit_maybe_relaxed_sub(root, - shift, - tail_off, - v, - first, - last < tail_off ? last : tail_off, - args...); - if (last > tail_off) - make_leaf_sub_pos(tail, tail_size) - .visit(v, - first > tail_off ? first - tail_off : 0, - last - tail_off, - args...); - } - - template <typename Visitor, typename... Args> - bool traverse_p(Visitor v, Args&&... args) const - { - auto tail_off = tail_offset(); - auto tail_size = size - tail_off; - return (tail_off - ? visit_maybe_relaxed_sub(root, shift, tail_off, v, args...) - : make_empty_regular_pos(root).visit(v, args...)) && - (tail_size ? make_leaf_sub_pos(tail, tail_size).visit(v, args...) - : make_empty_leaf_pos(tail).visit(v, args...)); - } - - template <typename Visitor, typename... Args> - bool traverse_p(Visitor v, size_t first, size_t last, Args&&... args) const - { - auto tail_off = tail_offset(); - auto tail_size = size - tail_off; - return (first < tail_off - ? visit_maybe_relaxed_sub(root, - shift, - tail_off, - v, - first, - last < tail_off ? last : tail_off, - args...) - : true) && - (last > tail_off - ? make_leaf_sub_pos(tail, tail_size) - .visit(v, - first > tail_off ? first - tail_off : 0, - last - tail_off, - args...) - : true); - } - - template <typename Visitor> - decltype(auto) descend(Visitor v, size_t idx) const - { - auto tail_off = tail_offset(); - return idx >= tail_off - ? make_leaf_descent_pos(tail).visit(v, idx - tail_off) - : visit_maybe_relaxed_descent(root, shift, v, idx); - } - - template <typename Fn> - void for_each_chunk(Fn&& fn) const - { - traverse(for_each_chunk_visitor{}, std::forward<Fn>(fn)); - } - - template <typename Fn> - void for_each_chunk(size_t first, size_t last, Fn&& fn) const - { - traverse(for_each_chunk_i_visitor{}, first, last, std::forward<Fn>(fn)); - } - - template <typename Fn> - bool for_each_chunk_p(Fn&& fn) const - { - return traverse_p(for_each_chunk_p_visitor{}, std::forward<Fn>(fn)); - } - - template <typename Fn> - bool for_each_chunk_p(size_t first, size_t last, Fn&& fn) const - { - return traverse_p( - for_each_chunk_p_i_visitor{}, first, last, std::forward<Fn>(fn)); - } - - bool equals(const rrbtree& other) const - { - using iter_t = rrbtree_iterator<T, MemoryPolicy, B, BL>; - if (size != other.size) - return false; - if (size == 0) - return true; - auto tail_off = tail_offset(); - auto tail_off_other = other.tail_offset(); - // compare trees - if (tail_off > 0 && tail_off_other > 0) { - // other.shift != shift is a theoretical possibility for - // relaxed trees that sadly we haven't managed to exercise - // in tests yet... - if (other.shift >= shift) { - if (!visit_maybe_relaxed_sub(other.root, - other.shift, - tail_off_other, - equals_visitor::rrb{}, - iter_t{other}, - root, - shift, - tail_off)) - return false; - } else { - if (!visit_maybe_relaxed_sub(root, - shift, - tail_off, - equals_visitor::rrb{}, - iter_t{*this}, - other.root, - other.shift, - tail_off_other)) - return false; - } - } - return tail_off == tail_off_other - ? make_leaf_sub_pos(tail, tail_size()) - .visit(equals_visitor{}, other.tail) - : tail_off > tail_off_other - ? std::equal(tail->leaf(), - tail->leaf() + (size - tail_off), - other.tail->leaf() + - (tail_off - tail_off_other)) - /* otherwise */ - : std::equal(tail->leaf(), - tail->leaf() + (size - tail_off), - iter_t{other} + tail_off); - } - - std::tuple<shift_t, node_t*> push_tail(node_t* root, - shift_t shift, - size_t size, - node_t* tail, - count_t tail_size) const - { - if (auto r = root->relaxed()) { - auto new_root = - make_relaxed_pos(root, shift, r) - .visit(push_tail_visitor<node_t>{}, tail, tail_size); - if (new_root) - return std::make_tuple(shift, new_root); - else { - auto new_root = node_t::make_inner_r_n(2); - try { - auto new_path = node_t::make_path(shift, tail); - new_root->inner()[0] = root->inc(); - new_root->inner()[1] = new_path; - new_root->relaxed()->d.sizes[0] = size; - new_root->relaxed()->d.sizes[1] = size + tail_size; - new_root->relaxed()->d.count = 2u; - } catch (...) { - node_t::delete_inner_r(new_root, 2); - throw; - } - return std::make_tuple(shift + B, new_root); - } - } else if (size == size_t{branches<B>} << shift) { - auto new_root = node_t::make_inner_n(2); - try { - auto new_path = node_t::make_path(shift, tail); - new_root->inner()[0] = root->inc(); - new_root->inner()[1] = new_path; - } catch (...) { - node_t::delete_inner(new_root, 2); - throw; - } - return std::make_tuple(shift + B, new_root); - } else if (size) { - auto new_root = make_regular_sub_pos(root, shift, size) - .visit(push_tail_visitor<node_t>{}, tail); - return std::make_tuple(shift, new_root); - } else { - return std::make_tuple(shift, node_t::make_path(shift, tail)); - } - } - - void - push_tail_mut(edit_t e, size_t tail_off, node_t* tail, count_t tail_size) - { - if (auto r = root->relaxed()) { - auto new_root = - make_relaxed_pos(root, shift, r) - .visit(push_tail_mut_visitor<node_t>{}, e, tail, tail_size); - if (new_root) { - root = new_root; - } else { - auto new_root = node_t::make_inner_r_e(e); - try { - auto new_path = node_t::make_path_e(e, shift, tail); - new_root->inner()[0] = root; - new_root->inner()[1] = new_path; - new_root->relaxed()->d.sizes[0] = tail_off; - new_root->relaxed()->d.sizes[1] = tail_off + tail_size; - new_root->relaxed()->d.count = 2u; - root = new_root; - shift += B; - } catch (...) { - node_t::delete_inner_r_e(new_root); - throw; - } - } - } else if (tail_off == size_t{branches<B>} << shift) { - auto new_root = node_t::make_inner_e(e); - try { - auto new_path = node_t::make_path_e(e, shift, tail); - new_root->inner()[0] = root; - new_root->inner()[1] = new_path; - root = new_root; - shift += B; - } catch (...) { - node_t::delete_inner_e(new_root); - throw; - } - } else if (tail_off) { - auto new_root = - make_regular_sub_pos(root, shift, tail_off) - .visit(push_tail_mut_visitor<node_t>{}, e, tail); - root = new_root; - } else { - auto new_root = node_t::make_path_e(e, shift, tail); - dec_empty_regular(root); - root = new_root; - } - } - - void ensure_mutable_tail(edit_t e, count_t n) - { - if (!tail->can_mutate(e)) { - auto new_tail = node_t::copy_leaf_e(e, tail, n); - dec_leaf(tail, n); - tail = new_tail; - } - } - - void push_back_mut(edit_t e, T value) - { - auto ts = tail_size(); - if (ts < branches<BL>) { - ensure_mutable_tail(e, ts); - new (&tail->leaf()[ts]) T{std::move(value)}; - } else { - using std::get; - auto new_tail = node_t::make_leaf_e(e, std::move(value)); - auto tail_off = tail_offset(); - try { - push_tail_mut(e, tail_off, tail, ts); - tail = new_tail; - } catch (...) { - node_t::delete_leaf(new_tail, 1u); - throw; - } - } - ++size; - } - - rrbtree push_back(T value) const - { - auto ts = tail_size(); - if (ts < branches<BL>) { - auto new_tail = - node_t::copy_leaf_emplace(tail, ts, std::move(value)); - return {size + 1, shift, root->inc(), new_tail}; - } else { - using std::get; - auto new_tail = node_t::make_leaf_n(1u, std::move(value)); - auto tail_off = tail_offset(); - try { - auto new_root = - push_tail(root, shift, tail_off, tail, size - tail_off); - tail->inc(); - return {size + 1, get<0>(new_root), get<1>(new_root), new_tail}; - } catch (...) { - node_t::delete_leaf(new_tail, 1u); - throw; - } - } - } - - std::tuple<const T*, size_t, size_t> region_for(size_t idx) const - { - using std::get; - auto tail_off = tail_offset(); - if (idx >= tail_off) { - return std::make_tuple(tail->leaf(), tail_off, size); - } else { - auto subs = visit_maybe_relaxed_sub( - root, shift, tail_off, region_for_visitor<T>(), idx); - auto first = idx - get<1>(subs); - auto end = first + get<2>(subs); - return std::make_tuple(get<0>(subs), first, end); - } - } - - T& get_mut(edit_t e, size_t idx) - { - auto tail_off = tail_offset(); - if (idx >= tail_off) { - ensure_mutable_tail(e, size - tail_off); - return tail->leaf()[(idx - tail_off) & mask<BL>]; - } else { - return visit_maybe_relaxed_sub(root, - shift, - tail_off, - get_mut_visitor<node_t>{}, - idx, - e, - &root); - } - } - - const T& get(size_t index) const - { - return descend(get_visitor<T>(), index); - } - - const T& get_check(size_t index) const - { - if (index >= size) - throw std::out_of_range{"out of range"}; - return descend(get_visitor<T>(), index); - } - - const T& front() const { return get(0); } - - const T& back() const { return get(size - 1); } - - template <typename FnT> - void update_mut(edit_t e, size_t idx, FnT&& fn) - { - auto& elem = get_mut(e, idx); - elem = std::forward<FnT>(fn)(std::move(elem)); - } - - template <typename FnT> - rrbtree update(size_t idx, FnT&& fn) const - { - auto tail_off = tail_offset(); - if (idx >= tail_off) { - auto tail_size = size - tail_off; - auto new_tail = - make_leaf_sub_pos(tail, tail_size) - .visit(update_visitor<node_t>{}, idx - tail_off, fn); - return {size, shift, root->inc(), new_tail}; - } else { - auto new_root = visit_maybe_relaxed_sub( - root, shift, tail_off, update_visitor<node_t>{}, idx, fn); - return {size, shift, new_root, tail->inc()}; - } - } - - void assoc_mut(edit_t e, size_t idx, T value) - { - update_mut(e, idx, [&](auto&&) { return std::move(value); }); - } - - rrbtree assoc(size_t idx, T value) const - { - return update(idx, [&](auto&&) { return std::move(value); }); - } - - void take_mut(edit_t e, size_t new_size) - { - auto tail_off = tail_offset(); - if (new_size == 0) { - *this = empty(); - } else if (new_size >= size) { - return; - } else if (new_size > tail_off) { - auto ts = size - tail_off; - auto newts = new_size - tail_off; - if (tail->can_mutate(e)) { - destroy_n(tail->leaf() + newts, ts - newts); - } else { - auto new_tail = node_t::copy_leaf_e(e, tail, newts); - dec_leaf(tail, ts); - tail = new_tail; - } - size = new_size; - return; - } else { - using std::get; - auto l = new_size - 1; - auto v = slice_right_mut_visitor<node_t>(); - auto r = visit_maybe_relaxed_sub(root, shift, tail_off, v, l, e); - auto new_shift = get<0>(r); - auto new_root = get<1>(r); - auto new_tail = get<3>(r); - if (new_root) { - root = new_root; - shift = new_shift; - } else { - root = empty().root->inc(); - shift = BL; - } - dec_leaf(tail, size - tail_off); - size = new_size; - tail = new_tail; - return; - } - } - - rrbtree take(size_t new_size) const - { - auto tail_off = tail_offset(); - if (new_size == 0) { - return empty(); - } else if (new_size >= size) { - return *this; - } else if (new_size > tail_off) { - auto new_tail = node_t::copy_leaf(tail, new_size - tail_off); - return {new_size, shift, root->inc(), new_tail}; - } else { - using std::get; - auto l = new_size - 1; - auto v = slice_right_visitor<node_t>(); - auto r = visit_maybe_relaxed_sub(root, shift, tail_off, v, l); - auto new_shift = get<0>(r); - auto new_root = get<1>(r); - auto new_tail = get<3>(r); - if (new_root) { - IMMER_ASSERT_TAGGED(new_root->compute_shift() == get<0>(r)); - assert(new_root->check(new_shift, new_size - get<2>(r))); - return {new_size, new_shift, new_root, new_tail}; - } else { - return {new_size, BL, empty().root->inc(), new_tail}; - } - } - } - - void drop_mut(edit_t e, size_t elems) - { - using std::get; - auto tail_off = tail_offset(); - if (elems == 0) { - return; - } else if (elems >= size) { - *this = empty(); - } else if (elems == tail_off) { - dec_inner(root, shift, tail_off); - shift = BL; - root = empty().root->inc(); - size -= elems; - return; - } else if (elems > tail_off) { - auto v = slice_left_mut_visitor<node_t>(); - tail = get<1>(make_leaf_sub_pos(tail, size - tail_off) - .visit(v, elems - tail_off, e)); - if (root != empty().root) { - dec_inner(root, shift, tail_off); - shift = BL; - root = empty().root->inc(); - } - size -= elems; - return; - } else { - auto v = slice_left_mut_visitor<node_t>(); - auto r = - visit_maybe_relaxed_sub(root, shift, tail_off, v, elems, e); - shift = get<0>(r); - root = get<1>(r); - size -= elems; - return; - } - } - - rrbtree drop(size_t elems) const - { - if (elems == 0) { - return *this; - } else if (elems >= size) { - return empty(); - } else if (elems == tail_offset()) { - return {size - elems, BL, empty().root->inc(), tail->inc()}; - } else if (elems > tail_offset()) { - auto tail_off = tail_offset(); - auto new_tail = - node_t::copy_leaf(tail, elems - tail_off, size - tail_off); - return {size - elems, BL, empty().root->inc(), new_tail}; - } else { - using std::get; - auto v = slice_left_visitor<node_t>(); - auto r = - visit_maybe_relaxed_sub(root, shift, tail_offset(), v, elems); - auto new_root = get<1>(r); - auto new_shift = get<0>(r); - return {size - elems, new_shift, new_root, tail->inc()}; - } - return *this; - } - - rrbtree concat(const rrbtree& r) const - { - assert(r.size < (std::numeric_limits<size_t>::max() - size)); - using std::get; - if (size == 0) - return r; - else if (r.size == 0) - return *this; - else if (r.tail_offset() == 0) { - // just concat the tail, similar to push_back - auto tail_offst = tail_offset(); - auto tail_size = size - tail_offst; - if (tail_size == branches<BL>) { - auto new_root = - push_tail(root, shift, tail_offst, tail, tail_size); - tail->inc(); - return {size + r.size, - get<0>(new_root), - get<1>(new_root), - r.tail->inc()}; - } else if (tail_size + r.size <= branches<BL>) { - auto new_tail = - node_t::copy_leaf(tail, tail_size, r.tail, r.size); - return {size + r.size, shift, root->inc(), new_tail}; - } else { - auto remaining = branches<BL> - tail_size; - auto add_tail = - node_t::copy_leaf(tail, tail_size, r.tail, remaining); - try { - auto new_tail = - node_t::copy_leaf(r.tail, remaining, r.size); - try { - auto new_root = push_tail( - root, shift, tail_offst, add_tail, branches<BL>); - return {size + r.size, - get<0>(new_root), - get<1>(new_root), - new_tail}; - } catch (...) { - node_t::delete_leaf(new_tail, r.size - remaining); - throw; - } - } catch (...) { - node_t::delete_leaf(add_tail, branches<BL>); - throw; - } - } - } else if (tail_offset() == 0) { - auto tail_offst = tail_offset(); - auto tail_size = size - tail_offst; - auto concated = - concat_trees(tail, tail_size, r.root, r.shift, r.tail_offset()); - auto new_shift = concated.shift(); - auto new_root = concated.node(); - IMMER_ASSERT_TAGGED(new_shift == new_root->compute_shift()); - assert(new_root->check(new_shift, size + r.tail_offset())); - return {size + r.size, new_shift, new_root, r.tail->inc()}; - } else { - auto tail_offst = tail_offset(); - auto tail_size = size - tail_offst; - auto concated = concat_trees(root, - shift, - tail_offst, - tail, - tail_size, - r.root, - r.shift, - r.tail_offset()); - auto new_shift = concated.shift(); - auto new_root = concated.node(); - IMMER_ASSERT_TAGGED(new_shift == new_root->compute_shift()); - assert(new_root->check(new_shift, size + r.tail_offset())); - return {size + r.size, new_shift, new_root, r.tail->inc()}; - } - } - - constexpr static bool supports_transient_concat = - !std::is_empty<edit_t>::value; - - friend void concat_mut_l(rrbtree& l, edit_t el, const rrbtree& r) - { - assert(&l != &r); - assert(r.size < (std::numeric_limits<size_t>::max() - l.size)); - using std::get; - if (l.size == 0) - l = r; - else if (r.size == 0) - return; - else if (r.tail_offset() == 0) { - // just concat the tail, similar to push_back - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - if (tail_size == branches<BL>) { - l.push_tail_mut(el, tail_offst, l.tail, tail_size); - l.tail = r.tail->inc(); - l.size += r.size; - return; - } else if (tail_size + r.size <= branches<BL>) { - l.ensure_mutable_tail(el, tail_size); - std::uninitialized_copy(r.tail->leaf(), - r.tail->leaf() + r.size, - l.tail->leaf() + tail_size); - l.size += r.size; - return; - } else { - auto remaining = branches<BL> - tail_size; - l.ensure_mutable_tail(el, tail_size); - std::uninitialized_copy(r.tail->leaf(), - r.tail->leaf() + remaining, - l.tail->leaf() + tail_size); - try { - auto new_tail = - node_t::copy_leaf_e(el, r.tail, remaining, r.size); - try { - l.push_tail_mut(el, tail_offst, l.tail, branches<BL>); - l.tail = new_tail; - l.size += r.size; - return; - } catch (...) { - node_t::delete_leaf(new_tail, r.size - remaining); - throw; - } - } catch (...) { - destroy_n(r.tail->leaf() + tail_size, remaining); - throw; - } - } - } else if (l.tail_offset() == 0) { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = - concat_trees_mut(el, - el, - l.tail, - tail_size, - MemoryPolicy::transience_t::noone, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - l.size += r.size; - l.shift = concated.shift(); - l.root = concated.node(); - l.tail = r.tail; - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees( - l.tail, tail_size, r.root, r.shift, r.tail_offset()); - l = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - return; - } - } else { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = - concat_trees_mut(el, - el, - l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - MemoryPolicy::transience_t::noone, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - l.size += r.size; - l.shift = concated.shift(); - l.root = concated.node(); - l.tail = r.tail; - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees(l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - r.root, - r.shift, - r.tail_offset()); - l = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - } - } - } - - friend void concat_mut_r(const rrbtree& l, rrbtree& r, edit_t er) - { - assert(&l != &r); - assert(r.size < (std::numeric_limits<size_t>::max() - l.size)); - using std::get; - if (r.size == 0) - r = std::move(l); - else if (l.size == 0) - return; - else if (r.tail_offset() == 0) { - // just concat the tail, similar to push_back - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - if (tail_size == branches<BL>) { - // this could be improved by making sure that the - // newly created nodes as part of the `push_tail()` - // are tagged with `er` - auto res = - l.push_tail(l.root, l.shift, tail_offst, l.tail, tail_size); - l.tail->inc(); // note: leak if mutably concatenated - // with itself, but this is forbidden - // by the interface - r = {l.size + r.size, get<0>(res), get<1>(res), r.tail->inc()}; - return; - } else if (tail_size + r.size <= branches<BL>) { - // doing this in a exception way mutating way is very - // tricky while potential performance gains are - // minimal (we need to move every element of the right - // tail anyways to make space for the left tail) - // - // we could however improve this by at least moving the - // elements of the right tail... - auto new_tail = - node_t::copy_leaf(l.tail, tail_size, r.tail, r.size); - r = {l.size + r.size, l.shift, l.root->inc(), new_tail}; - return; - } else { - // like the immutable version - auto remaining = branches<BL> - tail_size; - auto add_tail = node_t::copy_leaf_e( - er, l.tail, tail_size, r.tail, remaining); - try { - auto new_tail = - node_t::copy_leaf_e(er, r.tail, remaining, r.size); - try { - // this could be improved by making sure that the - // newly created nodes as part of the `push_tail()` - // are tagged with `er` - auto new_root = l.push_tail(l.root, - l.shift, - tail_offst, - add_tail, - branches<BL>); - r = {l.size + r.size, - get<0>(new_root), - get<1>(new_root), - new_tail}; - return; - } catch (...) { - node_t::delete_leaf(new_tail, r.size - remaining); - throw; - } - } catch (...) { - node_t::delete_leaf(add_tail, branches<BL>); - throw; - } - return; - } - } else if (l.tail_offset() == 0) { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = - concat_trees_mut(er, - MemoryPolicy::transience_t::noone, - l.tail, - tail_size, - er, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - r.size += l.size; - r.shift = concated.shift(); - r.root = concated.node(); - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees( - l.tail, tail_size, r.root, r.shift, r.tail_offset()); - r = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - return; - } - } else { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = - concat_trees_mut(er, - MemoryPolicy::transience_t::noone, - l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - er, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - r.size += l.size; - r.shift = concated.shift(); - r.root = concated.node(); - return; - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees(l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - r.root, - r.shift, - r.tail_offset()); - r = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - return; - } - } - } - - friend void concat_mut_lr_l(rrbtree& l, edit_t el, rrbtree& r, edit_t er) - { - assert(&l != &r); - assert(r.size < (std::numeric_limits<size_t>::max() - l.size)); - using std::get; - if (l.size == 0) - l = r; - else if (r.size == 0) - return; - else if (r.tail_offset() == 0) { - // just concat the tail, similar to push_back - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - if (tail_size == branches<BL>) { - l.push_tail_mut(el, tail_offst, l.tail, tail_size); - l.tail = r.tail->inc(); - l.size += r.size; - return; - } else if (tail_size + r.size <= branches<BL>) { - l.ensure_mutable_tail(el, tail_size); - if (r.tail->can_mutate(er)) - detail::uninitialized_move(r.tail->leaf(), - r.tail->leaf() + r.size, - l.tail->leaf() + tail_size); - else - std::uninitialized_copy(r.tail->leaf(), - r.tail->leaf() + r.size, - l.tail->leaf() + tail_size); - l.size += r.size; - return; - } else { - auto remaining = branches<BL> - tail_size; - l.ensure_mutable_tail(el, tail_size); - if (r.tail->can_mutate(er)) - detail::uninitialized_move(r.tail->leaf(), - r.tail->leaf() + remaining, - l.tail->leaf() + tail_size); - else - std::uninitialized_copy(r.tail->leaf(), - r.tail->leaf() + remaining, - l.tail->leaf() + tail_size); - try { - auto new_tail = - node_t::copy_leaf_e(el, r.tail, remaining, r.size); - try { - l.push_tail_mut(el, tail_offst, l.tail, branches<BL>); - l.tail = new_tail; - l.size += r.size; - return; - } catch (...) { - node_t::delete_leaf(new_tail, r.size - remaining); - throw; - } - } catch (...) { - destroy_n(r.tail->leaf() + tail_size, remaining); - throw; - } - } - } else if (l.tail_offset() == 0) { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees_mut(el, - el, - l.tail, - tail_size, - er, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - l.size += r.size; - l.shift = concated.shift(); - l.root = concated.node(); - l.tail = r.tail; - r.hard_reset(); - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees( - l.tail, tail_size, r.root, r.shift, r.tail_offset()); - l = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - return; - } - } else { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees_mut(el, - el, - l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - er, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - l.size += r.size; - l.shift = concated.shift(); - l.root = concated.node(); - l.tail = r.tail; - r.hard_reset(); - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees(l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - r.root, - r.shift, - r.tail_offset()); - l = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - } - } - } - - friend void concat_mut_lr_r(rrbtree& l, edit_t el, rrbtree& r, edit_t er) - { - assert(&l != &r); - assert(r.size < (std::numeric_limits<size_t>::max() - l.size)); - using std::get; - if (r.size == 0) - r = l; - else if (l.size == 0) - return; - else if (r.tail_offset() == 0) { - // just concat the tail, similar to push_back - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - if (tail_size == branches<BL>) { - // this could be improved by making sure that the - // newly created nodes as part of the `push_tail()` - // are tagged with `er` - auto res = - l.push_tail(l.root, l.shift, tail_offst, l.tail, tail_size); - r = {l.size + r.size, get<0>(res), get<1>(res), r.tail->inc()}; - return; - } else if (tail_size + r.size <= branches<BL>) { - // doing this in a exception way mutating way is very - // tricky while potential performance gains are - // minimal (we need to move every element of the right - // tail anyways to make space for the left tail) - // - // we could however improve this by at least moving the - // elements of the mutable tails... - auto new_tail = - node_t::copy_leaf(l.tail, tail_size, r.tail, r.size); - r = {l.size + r.size, l.shift, l.root->inc(), new_tail}; - return; - } else { - // like the immutable version. - // we could improve this also by moving elements - // instead of just copying them - auto remaining = branches<BL> - tail_size; - auto add_tail = node_t::copy_leaf_e( - er, l.tail, tail_size, r.tail, remaining); - try { - auto new_tail = - node_t::copy_leaf_e(er, r.tail, remaining, r.size); - try { - // this could be improved by making sure that the - // newly created nodes as part of the `push_tail()` - // are tagged with `er` - auto new_root = l.push_tail(l.root, - l.shift, - tail_offst, - add_tail, - branches<BL>); - r = {l.size + r.size, - get<0>(new_root), - get<1>(new_root), - new_tail}; - return; - } catch (...) { - node_t::delete_leaf(new_tail, r.size - remaining); - throw; - } - } catch (...) { - node_t::delete_leaf(add_tail, branches<BL>); - throw; - } - return; - } - } else if (l.tail_offset() == 0) { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees_mut(er, - el, - l.tail, - tail_size, - er, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - r.size += l.size; - r.shift = concated.shift(); - r.root = concated.node(); - l.hard_reset(); - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees( - l.tail, tail_size, r.root, r.shift, r.tail_offset()); - r = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - return; - } - } else { - if (supports_transient_concat) { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees_mut(er, - el, - l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - er, - r.root, - r.shift, - r.tail_offset()); - IMMER_ASSERT_TAGGED(concated.shift() == - concated.node()->compute_shift()); - assert(concated.node()->check(concated.shift(), - l.size + r.tail_offset())); - r.size += l.size; - r.shift = concated.shift(); - r.root = concated.node(); - l.hard_reset(); - } else { - auto tail_offst = l.tail_offset(); - auto tail_size = l.size - tail_offst; - auto concated = concat_trees(l.root, - l.shift, - tail_offst, - l.tail, - tail_size, - r.root, - r.shift, - r.tail_offset()); - r = {l.size + r.size, - concated.shift(), - concated.node(), - r.tail->inc()}; - } - } - } - - void hard_reset() - { - assert(supports_transient_concat); - auto&& empty_ = empty(); - size = empty_.size; - shift = empty_.shift; - root = empty_.root; - tail = empty_.tail; - } - - bool check_tree() const - { - assert(shift <= sizeof(size_t) * 8 - BL); - assert(shift >= BL); - assert(tail_offset() <= size); - assert(tail_size() <= branches<BL>); -#if IMMER_DEBUG_DEEP_CHECK - assert(check_root()); - assert(check_tail()); -#endif - return true; - } - - bool check_tail() const - { -#if IMMER_DEBUG_DEEP_CHECK - if (tail_size() > 0) - assert(tail->check(endshift<B, BL>, tail_size())); -#endif - return true; - } - - bool check_root() const - { -#if IMMER_DEBUG_DEEP_CHECK - if (tail_offset() > 0) - assert(root->check(shift, tail_offset())); - else { - IMMER_ASSERT_TAGGED(root->kind() == node_t::kind_t::inner); - assert(shift == BL); - } -#endif - return true; - } - -#if IMMER_DEBUG_PRINT - void debug_print(std::ostream& out) const - { - out << "--" << std::endl - << "{" << std::endl - << " size = " << size << std::endl - << " shift = " << shift << std::endl - << " root = " << std::endl; - debug_print_node(out, root, shift, tail_offset()); - out << " tail = " << std::endl; - debug_print_node(out, tail, endshift<B, BL>, tail_size()); - out << "}" << std::endl; - } - - void debug_print_indent(std::ostream& out, unsigned indent) const - { - while (indent-- > 0) - out << ' '; - } - - void debug_print_node(std::ostream& out, - node_t* node, - shift_t shift, - size_t size, - unsigned indent = 8) const - { - const auto indent_step = 4; - - if (shift == endshift<B, BL>) { - debug_print_indent(out, indent); - out << "- {" << size << "} " - << pretty_print_array(node->leaf(), size) << std::endl; - } else if (auto r = node->relaxed()) { - auto count = r->d.count; - debug_print_indent(out, indent); - out << "# {" << size << "} " - << pretty_print_array(r->d.sizes, r->d.count) << std::endl; - auto last_size = size_t{}; - for (auto i = count_t{}; i < count; ++i) { - debug_print_node(out, - node->inner()[i], - shift - B, - r->d.sizes[i] - last_size, - indent + indent_step); - last_size = r->d.sizes[i]; - } - } else { - debug_print_indent(out, indent); - out << "+ {" << size << "}" << std::endl; - auto count = - (size >> shift) + (size - ((size >> shift) << shift) > 0); - if (count) { - for (auto i = count_t{}; i < count - 1; ++i) - debug_print_node(out, - node->inner()[i], - shift - B, - 1 << shift, - indent + indent_step); - debug_print_node(out, - node->inner()[count - 1], - shift - B, - size - ((count - 1) << shift), - indent + indent_step); - } - } - } -#endif // IMMER_DEBUG_PRINT -}; - -} // namespace rbts -} // namespace detail -} // namespace immer |