1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#pragma once
10
11#include <immer/config.hpp>
12#include <immer/detail/rbts/node.hpp>
13#include <immer/detail/rbts/position.hpp>
14#include <immer/detail/rbts/operations.hpp>
15
16#include <immer/detail/type_traits.hpp>
17
18#include <cassert>
19#include <memory>
20#include <numeric>
21
22namespace immer {
23namespace detail {
24namespace rbts {
25
26template <typename T,
27 typename MemoryPolicy,
28 bits_t B,
29 bits_t BL>
30struct rrbtree_iterator;
31
32template <typename T,
33 typename MemoryPolicy,
34 bits_t B,
35 bits_t BL>
36struct rrbtree
37{
38 using node_t = node<T, MemoryPolicy, B, BL>;
39 using edit_t = typename node_t::edit_t;
40 using owner_t = typename MemoryPolicy::transience_t::owner;
41
42 size_t size;
43 shift_t shift;
44 node_t* root;
45 node_t* tail;
46
47 static const rrbtree& empty()
48 {
49 static const rrbtree empty_ {
50 0,
51 BL,
52 node_t::make_inner_n(0u),
53 node_t::make_leaf_n(0u)
54 };
55 return empty_;
56 }
57
58 template <typename U>
59 static auto from_initializer_list(std::initializer_list<U> values)
60 {
61 auto e = owner_t{};
62 auto result = rrbtree{empty()};
63 for (auto&& v : values)
64 result.push_back_mut(e, v);
65 return result;
66 }
67
68 template <typename Iter, typename Sent,
69 std::enable_if_t
70 <compatible_sentinel_v<Iter, Sent>, bool> = true>
71 static auto from_range(Iter first, Sent last)
72 {
73 auto e = owner_t{};
74 auto result = rrbtree{empty()};
75 for (; first != last; ++first)
76 result.push_back_mut(e, *first);
77 return result;
78 }
79
80 static auto from_fill(size_t n, T v)
81 {
82 auto e = owner_t{};
83 auto result = rrbtree{empty()};
84 while (n --> 0)
85 result.push_back_mut(e, v);
86 return result;
87 }
88
89 rrbtree(size_t sz, shift_t sh, node_t* r, node_t* t)
90 : size{sz}, shift{sh}, root{r}, tail{t}
91 {
92 assert(check_tree());
93 }
94
95 rrbtree(const rrbtree& other)
96 : rrbtree{other.size, other.shift, other.root, other.tail}
97 {
98 inc();
99 }
100
101 rrbtree(rrbtree&& other)
102 : rrbtree{empty()}
103 {
104 swap(*this, other);
105 }
106
107 rrbtree& operator=(const rrbtree& other)
108 {
109 auto next{other};
110 swap(*this, next);
111 return *this;
112 }
113
114 rrbtree& operator=(rrbtree&& other)
115 {
116 swap(*this, other);
117 return *this;
118 }
119
120 friend void swap(rrbtree& x, rrbtree& y)
121 {
122 using std::swap;
123 swap(x.size, y.size);
124 swap(x.shift, y.shift);
125 swap(x.root, y.root);
126 swap(x.tail, y.tail);
127 }
128
129 ~rrbtree()
130 {
131 dec();
132 }
133
134 void inc() const
135 {
136 root->inc();
137 tail->inc();
138 }
139
140 void dec() const
141 {
142 traverse(dec_visitor());
143 }
144
145 auto tail_size() const
146 {
147 return size - tail_offset();
148 }
149
150 auto tail_offset() const
151 {
152 auto r = root->relaxed();
153 assert(r == nullptr || r->d.count);
154 return
155 r ? r->d.sizes[r->d.count - 1] :
156 size ? (size - 1) & ~mask<BL>
157 /* otherwise */ : 0;
158 }
159
160 template <typename Visitor, typename... Args>
161 void traverse(Visitor v, Args&&... args) const
162 {
163 auto tail_off = tail_offset();
164 auto tail_size = size - tail_off;
165
166 if (tail_off) visit_maybe_relaxed_sub(root, shift, tail_off, v, args...);
167 else make_empty_regular_pos(root).visit(v, args...);
168
169 if (tail_size) make_leaf_sub_pos(tail, tail_size).visit(v, args...);
170 else make_empty_leaf_pos(tail).visit(v, args...);
171 }
172
173 template <typename Visitor, typename... Args>
174 void traverse(Visitor v, size_t first, size_t last, Args&&... args) const
175 {
176 auto tail_off = tail_offset();
177 auto tail_size = size - tail_off;
178
179 if (first < tail_off)
180 visit_maybe_relaxed_sub(root, shift, tail_off, v,
181 first,
182 last < tail_off ? last : tail_off,
183 args...);
184 if (last > tail_off)
185 make_leaf_sub_pos(tail, tail_size).visit(
186 v,
187 first > tail_off ? first - tail_off : 0,
188 last - tail_off,
189 args...);
190 }
191
192 template <typename Visitor, typename... Args>
193 bool traverse_p(Visitor v, Args&&... args) const
194 {
195 auto tail_off = tail_offset();
196 auto tail_size = size - tail_off;
197 return (tail_off
198 ? visit_maybe_relaxed_sub(root, shift, tail_off, v, args...)
199 : make_empty_regular_pos(root).visit(v, args...))
200 && (tail_size
201 ? make_leaf_sub_pos(tail, tail_size).visit(v, args...)
202 : make_empty_leaf_pos(tail).visit(v, args...));
203 }
204
205 template <typename Visitor, typename... Args>
206 bool traverse_p(Visitor v, size_t first, size_t last, Args&&... args) const
207 {
208 auto tail_off = tail_offset();
209 auto tail_size = size - tail_off;
210 return
211 (first < tail_off
212 ? visit_maybe_relaxed_sub(root, shift, tail_off, v,
213 first,
214 last < tail_off ? last : tail_off,
215 args...)
216 : true)
217 && (last > tail_off
218 ? make_leaf_sub_pos(tail, tail_size).visit(
219 v,
220 first > tail_off ? first - tail_off : 0,
221 last - tail_off,
222 args...)
223 : true);
224 }
225
226 template <typename Visitor>
227 decltype(auto) descend(Visitor v, size_t idx) const
228 {
229 auto tail_off = tail_offset();
230 return idx >= tail_off
231 ? make_leaf_descent_pos(tail).visit(v, idx - tail_off)
232 : visit_maybe_relaxed_descent(root, shift, v, idx);
233 }
234
235 template <typename Fn>
236 void for_each_chunk(Fn&& fn) const
237 {
238 traverse(for_each_chunk_visitor{}, std::forward<Fn>(fn));
239 }
240
241 template <typename Fn>
242 void for_each_chunk(size_t first, size_t last, Fn&& fn) const
243 {
244 traverse(for_each_chunk_i_visitor{}, first, last, std::forward<Fn>(fn));
245 }
246
247 template <typename Fn>
248 bool for_each_chunk_p(Fn&& fn) const
249 {
250 return traverse_p(for_each_chunk_p_visitor{}, std::forward<Fn>(fn));
251 }
252
253 template <typename Fn>
254 bool for_each_chunk_p(size_t first, size_t last, Fn&& fn) const
255 {
256 return traverse_p(for_each_chunk_p_i_visitor{}, first, last, std::forward<Fn>(fn));
257 }
258
259 bool equals(const rrbtree& other) const
260 {
261 using iter_t = rrbtree_iterator<T, MemoryPolicy, B, BL>;
262 if (size != other.size) return false;
263 if (size == 0) return true;
264 auto tail_off = tail_offset();
265 auto tail_off_other = other.tail_offset();
266 // compare trees
267 if (tail_off > 0 && tail_off_other > 0) {
268 // other.shift != shift is a theoretical possibility for
269 // relaxed trees that sadly we haven't managed to exercise
270 // in tests yet...
271 if (other.shift >= shift) {
272 if (!visit_maybe_relaxed_sub(
273 other.root, other.shift, tail_off_other,
274 equals_visitor::rrb{}, iter_t{other},
275 root, shift, tail_off))
276 return false;
277 } else {
278 if (!visit_maybe_relaxed_sub(
279 root, shift, tail_off,
280 equals_visitor::rrb{}, iter_t{*this},
281 other.root, other.shift, tail_off_other))
282 return false;
283 }
284 }
285 return
286 tail_off == tail_off_other ? make_leaf_sub_pos(
287 tail, tail_size()).visit(
288 equals_visitor{}, other.tail) :
289 tail_off > tail_off_other ? std::equal(
290 tail->leaf(), tail->leaf() + (size - tail_off),
291 other.tail->leaf() + (tail_off - tail_off_other))
292 /* otherwise */ : std::equal(
293 tail->leaf(), tail->leaf() + (size - tail_off),
294 iter_t{other} + tail_off);
295 }
296
297 std::tuple<shift_t, node_t*>
298 push_tail(node_t* root, shift_t shift, size_t size,
299 node_t* tail, count_t tail_size) const
300 {
301 if (auto r = root->relaxed()) {
302 auto new_root = make_relaxed_pos(root, shift, r)
303 .visit(push_tail_visitor<node_t>{}, tail, tail_size);
304 if (new_root)
305 return std::make_tuple( shift, new_root );
306 else {
307 auto new_root = node_t::make_inner_r_n(2);
308 try {
309 auto new_path = node_t::make_path(shift, tail);
310 new_root->inner() [0] = root->inc();
311 new_root->inner() [1] = new_path;
312 new_root->relaxed()->d.sizes [0] = size;
313 new_root->relaxed()->d.sizes [1] = size + tail_size;
314 new_root->relaxed()->d.count = 2u;
315 } catch (...) {
316 node_t::delete_inner_r(new_root, 2);
317 throw;
318 }
319 return std::make_tuple( shift + B, new_root );
320 }
321 } else if (size == size_t{branches<B>} << shift) {
322 auto new_root = node_t::make_inner_n(2);
323 try {
324 auto new_path = node_t::make_path(shift, tail);
325 new_root->inner() [0] = root->inc();
326 new_root->inner() [1] = new_path;
327 } catch (...) {
328 node_t::delete_inner(new_root, 2);
329 throw;
330 }
331 return std::make_tuple( shift + B, new_root );
332 } else if (size) {
333 auto new_root = make_regular_sub_pos(root, shift, size)
334 .visit(push_tail_visitor<node_t>{}, tail);
335 return std::make_tuple( shift, new_root );
336 } else {
337 return std::make_tuple( shift, node_t::make_path(shift, tail) );
338 }
339 }
340
341 void push_tail_mut(edit_t e, size_t tail_off,
342 node_t* tail, count_t tail_size)
343 {
344 if (auto r = root->relaxed()) {
345 auto new_root = make_relaxed_pos(root, shift, r)
346 .visit(push_tail_mut_visitor<node_t>{}, e, tail, tail_size);
347 if (new_root) {
348 root = new_root;
349 } else {
350 auto new_root = node_t::make_inner_r_e(e);
351 try {
352 auto new_path = node_t::make_path_e(e, shift, tail);
353 new_root->inner() [0] = root;
354 new_root->inner() [1] = new_path;
355 new_root->relaxed()->d.sizes [0] = tail_off;
356 new_root->relaxed()->d.sizes [1] = tail_off + tail_size;
357 new_root->relaxed()->d.count = 2u;
358 root = new_root;
359 shift += B;
360 } catch (...) {
361 node_t::delete_inner_r_e(new_root);
362 throw;
363 }
364 }
365 } else if (tail_off == size_t{branches<B>} << shift) {
366 auto new_root = node_t::make_inner_e(e);
367 try {
368 auto new_path = node_t::make_path_e(e, shift, tail);
369 new_root->inner() [0] = root;
370 new_root->inner() [1] = new_path;
371 root = new_root;
372 shift += B;
373 } catch (...) {
374 node_t::delete_inner_e(new_root);
375 throw;
376 }
377 } else if (tail_off) {
378 auto new_root = make_regular_sub_pos(root, shift, tail_off)
379 .visit(push_tail_mut_visitor<node_t>{}, e, tail);
380 root = new_root;
381 } else {
382 auto new_root = node_t::make_path_e(e, shift, tail);
383 dec_empty_regular(root);
384 root = new_root;
385 }
386 }
387
388 void ensure_mutable_tail(edit_t e, count_t n)
389 {
390 if (!tail->can_mutate(e)) {
391 auto new_tail = node_t::copy_leaf_e(e, tail, n);
392 dec_leaf(tail, n);
393 tail = new_tail;
394 }
395 }
396
397 void push_back_mut(edit_t e, T value)
398 {
399 auto ts = tail_size();
400 if (ts < branches<BL>) {
401 ensure_mutable_tail(e, ts);
402 new (&tail->leaf()[ts]) T{std::move(value)};
403 } else {
404 using std::get;
405 auto new_tail = node_t::make_leaf_e(e, std::move(value));
406 auto tail_off = tail_offset();
407 try {
408 push_tail_mut(e, tail_off, tail, ts);
409 tail = new_tail;
410 } catch (...) {
411 node_t::delete_leaf(new_tail, 1u);
412 throw;
413 }
414 }
415 ++size;
416 }
417
418 rrbtree push_back(T value) const
419 {
420 auto ts = tail_size();
421 if (ts < branches<BL>) {
422 auto new_tail = node_t::copy_leaf_emplace(tail, ts,
423 std::move(value));
424 return { size + 1, shift, root->inc(), new_tail };
425 } else {
426 using std::get;
427 auto new_tail = node_t::make_leaf_n(1u, std::move(value));
428 auto tail_off = tail_offset();
429 try {
430 auto new_root = push_tail(root, shift, tail_off,
431 tail, size - tail_off);
432 tail->inc();
433 return { size + 1, get<0>(new_root), get<1>(new_root), new_tail };
434 } catch (...) {
435 node_t::delete_leaf(new_tail, 1u);
436 throw;
437 }
438 }
439 }
440
441 std::tuple<const T*, size_t, size_t>
442 region_for(size_t idx) const
443 {
444 using std::get;
445 auto tail_off = tail_offset();
446 if (idx >= tail_off) {
447 return std::make_tuple( tail->leaf(), tail_off, size );
448 } else {
449 auto subs = visit_maybe_relaxed_sub(
450 root, shift, tail_off,
451 region_for_visitor<T>(), idx);
452 auto first = idx - get<1>(subs);
453 auto end = first + get<2>(subs);
454 return std::make_tuple( get<0>(subs), first, end );
455 }
456 }
457
458 T& get_mut(edit_t e, size_t idx)
459 {
460 auto tail_off = tail_offset();
461 if (idx >= tail_off) {
462 ensure_mutable_tail(e, size - tail_off);
463 return tail->leaf() [(idx - tail_off) & mask<BL>];
464 } else {
465 return visit_maybe_relaxed_sub(
466 root, shift, tail_off,
467 get_mut_visitor<node_t>{}, idx, e, &root);
468 }
469 }
470
471 const T& get(size_t index) const
472 {
473 return descend(get_visitor<T>(), index);
474 }
475
476 const T& get_check(size_t index) const
477 {
478 if (index >= size)
479 throw std::out_of_range{"out of range"};
480 return descend(get_visitor<T>(), index);
481 }
482
483 const T& front() const
484 {
485 return get(0);
486 }
487
488 const T& back() const
489 {
490 return get(size - 1);
491 }
492
493 template <typename FnT>
494 void update_mut(edit_t e, size_t idx, FnT&& fn)
495 {
496 auto& elem = get_mut(e, idx);
497 elem = std::forward<FnT>(fn) (std::move(elem));
498 }
499
500 template <typename FnT>
501 rrbtree update(size_t idx, FnT&& fn) const
502 {
503 auto tail_off = tail_offset();
504 if (idx >= tail_off) {
505 auto tail_size = size - tail_off;
506 auto new_tail = make_leaf_sub_pos(tail, tail_size)
507 .visit(update_visitor<node_t>{}, idx - tail_off, fn);
508 return { size, shift, root->inc(), new_tail };
509 } else {
510 auto new_root = visit_maybe_relaxed_sub(
511 root, shift, tail_off,
512 update_visitor<node_t>{}, idx, fn);
513 return { size, shift, new_root, tail->inc() };
514 }
515 }
516
517 void assoc_mut(edit_t e, size_t idx, T value)
518 {
519 update_mut(e, idx, [&] (auto&&) {
520 return std::move(value);
521 });
522 }
523
524 rrbtree assoc(size_t idx, T value) const
525 {
526 return update(idx, [&] (auto&&) {
527 return std::move(value);
528 });
529 }
530
531 void take_mut(edit_t e, size_t new_size)
532 {
533 auto tail_off = tail_offset();
534 if (new_size == 0) {
535 *this = empty();
536 } else if (new_size >= size) {
537 return;
538 } else if (new_size > tail_off) {
539 auto ts = size - tail_off;
540 auto newts = new_size - tail_off;
541 if (tail->can_mutate(e)) {
542 destroy_n(tail->leaf() + newts, ts - newts);
543 } else {
544 auto new_tail = node_t::copy_leaf_e(e, tail, newts);
545 dec_leaf(tail, ts);
546 tail = new_tail;
547 }
548 size = new_size;
549 return;
550 } else {
551 using std::get;
552 auto l = new_size - 1;
553 auto v = slice_right_mut_visitor<node_t>();
554 auto r = visit_maybe_relaxed_sub(root, shift, tail_off, v, l, e);
555 auto new_shift = get<0>(r);
556 auto new_root = get<1>(r);
557 auto new_tail = get<3>(r);
558 if (new_root) {
559 root = new_root;
560 shift = new_shift;
561 } else {
562 root = empty().root->inc();
563 shift = BL;
564 }
565 dec_leaf(tail, size - tail_off);
566 size = new_size;
567 tail = new_tail;
568 return;
569 }
570 }
571
572 rrbtree take(size_t new_size) const
573 {
574 auto tail_off = tail_offset();
575 if (new_size == 0) {
576 return empty();
577 } else if (new_size >= size) {
578 return *this;
579 } else if (new_size > tail_off) {
580 auto new_tail = node_t::copy_leaf(tail, new_size - tail_off);
581 return { new_size, shift, root->inc(), new_tail };
582 } else {
583 using std::get;
584 auto l = new_size - 1;
585 auto v = slice_right_visitor<node_t>();
586 auto r = visit_maybe_relaxed_sub(root, shift, tail_off, v, l);
587 auto new_shift = get<0>(r);
588 auto new_root = get<1>(r);
589 auto new_tail = get<3>(r);
590 if (new_root) {
591 IMMER_ASSERT_TAGGED(new_root->compute_shift() == get<0>(r));
592 assert(new_root->check(new_shift, new_size - get<2>(r)));
593 return { new_size, new_shift, new_root, new_tail };
594 } else {
595 return { new_size, BL, empty().root->inc(), new_tail };
596 }
597 }
598 }
599
600 void drop_mut(edit_t e, size_t elems)
601 {
602 using std::get;
603 auto tail_off = tail_offset();
604 if (elems == 0) {
605 return;
606 } else if (elems >= size) {
607 *this = empty();
608 } else if (elems == tail_off) {
609 dec_inner(root, shift, tail_off);
610 shift = BL;
611 root = empty().root->inc();
612 size -= elems;
613 return;
614 } else if (elems > tail_off) {
615 auto v = slice_left_mut_visitor<node_t>();
616 tail = get<1>(make_leaf_sub_pos(tail, size - tail_off).visit(
617 v, elems - tail_off, e));
618 if (root != empty().root) {
619 dec_inner(root, shift, tail_off);
620 shift = BL;
621 root = empty().root->inc();
622 }
623 size -= elems;
624 return;
625 } else {
626 auto v = slice_left_mut_visitor<node_t>();
627 auto r = visit_maybe_relaxed_sub(root, shift, tail_off, v, elems, e);
628 shift = get<0>(r);
629 root = get<1>(r);
630 size -= elems;
631 return;
632 }
633 }
634
635 rrbtree drop(size_t elems) const
636 {
637 if (elems == 0) {
638 return *this;
639 } else if (elems >= size) {
640 return empty();
641 } else if (elems == tail_offset()) {
642 return { size - elems, BL, empty().root->inc(), tail->inc() };
643 } else if (elems > tail_offset()) {
644 auto tail_off = tail_offset();
645 auto new_tail = node_t::copy_leaf(tail, elems - tail_off,
646 size - tail_off);
647 return { size - elems, BL, empty().root->inc(), new_tail };
648 } else {
649 using std::get;
650 auto v = slice_left_visitor<node_t>();
651 auto r = visit_maybe_relaxed_sub(root, shift, tail_offset(), v, elems);
652 auto new_root = get<1>(r);
653 auto new_shift = get<0>(r);
654 return { size - elems, new_shift, new_root, tail->inc() };
655 }
656 return *this;
657 }
658
659 rrbtree concat(const rrbtree& r) const
660 {
661 assert(r.size < (std::numeric_limits<size_t>::max() - size));
662 using std::get;
663 if (size == 0)
664 return r;
665 else if (r.size == 0)
666 return *this;
667 else if (r.tail_offset() == 0) {
668 // just concat the tail, similar to push_back
669 auto tail_offst = tail_offset();
670 auto tail_size = size - tail_offst;
671 if (tail_size == branches<BL>) {
672 auto new_root = push_tail(root, shift, tail_offst,
673 tail, tail_size);
674 tail->inc();
675 return { size + r.size, get<0>(new_root), get<1>(new_root),
676 r.tail->inc() };
677 } else if (tail_size + r.size <= branches<BL>) {
678 auto new_tail = node_t::copy_leaf(tail, tail_size,
679 r.tail, r.size);
680 return { size + r.size, shift, root->inc(), new_tail };
681 } else {
682 auto remaining = branches<BL> - tail_size;
683 auto add_tail = node_t::copy_leaf(tail, tail_size,
684 r.tail, remaining);
685 try {
686 auto new_tail = node_t::copy_leaf(r.tail, remaining, r.size);
687 try {
688 auto new_root = push_tail(root, shift, tail_offst,
689 add_tail, branches<BL>);
690 return { size + r.size,
691 get<0>(new_root), get<1>(new_root),
692 new_tail };
693 } catch (...) {
694 node_t::delete_leaf(new_tail, r.size - remaining);
695 throw;
696 }
697 } catch (...) {
698 node_t::delete_leaf(add_tail, branches<BL>);
699 throw;
700 }
701 }
702 } else if (tail_offset() == 0) {
703 auto tail_offst = tail_offset();
704 auto tail_size = size - tail_offst;
705 auto concated = concat_trees(tail, tail_size,
706 r.root, r.shift, r.tail_offset());
707 auto new_shift = concated.shift();
708 auto new_root = concated.node();
709 IMMER_ASSERT_TAGGED(new_shift == new_root->compute_shift());
710 assert(new_root->check(new_shift, size + r.tail_offset()));
711 return { size + r.size, new_shift, new_root, r.tail->inc() };
712 } else {
713 auto tail_offst = tail_offset();
714 auto tail_size = size - tail_offst;
715 auto concated = concat_trees(root, shift, tail_offst,
716 tail, tail_size,
717 r.root, r.shift, r.tail_offset());
718 auto new_shift = concated.shift();
719 auto new_root = concated.node();
720 IMMER_ASSERT_TAGGED(new_shift == new_root->compute_shift());
721 assert(new_root->check(new_shift, size + r.tail_offset()));
722 return { size + r.size, new_shift, new_root, r.tail->inc() };
723 }
724 }
725
726 constexpr static bool supports_transient_concat =
727 !std::is_empty<edit_t>::value;
728
729 friend void concat_mut_l(rrbtree& l, edit_t el, const rrbtree& r)
730 {
731 assert(&l != &r);
732 assert(r.size < (std::numeric_limits<size_t>::max() - l.size));
733 using std::get;
734 if (l.size == 0)
735 l = r;
736 else if (r.size == 0)
737 return;
738 else if (r.tail_offset() == 0) {
739 // just concat the tail, similar to push_back
740 auto tail_offst = l.tail_offset();
741 auto tail_size = l.size - tail_offst;
742 if (tail_size == branches<BL>) {
743 l.push_tail_mut(el, tail_offst, l.tail, tail_size);
744 l.tail = r.tail->inc();
745 l.size += r.size;
746 return;
747 } else if (tail_size + r.size <= branches<BL>) {
748 l.ensure_mutable_tail(el, tail_size);
749 std::uninitialized_copy(r.tail->leaf(),
750 r.tail->leaf() + r.size,
751 l.tail->leaf() + tail_size);
752 l.size += r.size;
753 return;
754 } else {
755 auto remaining = branches<BL> - tail_size;
756 l.ensure_mutable_tail(el, tail_size);
757 std::uninitialized_copy(r.tail->leaf(),
758 r.tail->leaf() + remaining,
759 l.tail->leaf() + tail_size);
760 try {
761 auto new_tail = node_t::copy_leaf_e(el, r.tail, remaining, r.size);
762 try {
763 l.push_tail_mut(el, tail_offst, l.tail, branches<BL>);
764 l.tail = new_tail;
765 l.size += r.size;
766 return;
767 } catch (...) {
768 node_t::delete_leaf(new_tail, r.size - remaining);
769 throw;
770 }
771 } catch (...) {
772 destroy_n(r.tail->leaf() + tail_size, remaining);
773 throw;
774 }
775 }
776 } else if (l.tail_offset() == 0) {
777 if (supports_transient_concat) {
778 auto tail_offst = l.tail_offset();
779 auto tail_size = l.size - tail_offst;
780 auto concated = concat_trees_mut(
781 el,
782 el, l.tail, tail_size,
783 MemoryPolicy::transience_t::noone,
784 r.root, r.shift, r.tail_offset());
785 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
786 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
787 l.size += r.size;
788 l.shift = concated.shift();
789 l.root = concated.node();
790 l.tail = r.tail;
791 } else {
792 auto tail_offst = l.tail_offset();
793 auto tail_size = l.size - tail_offst;
794 auto concated = concat_trees(l.tail, tail_size,
795 r.root, r.shift, r.tail_offset());
796 l = { l.size + r.size, concated.shift(),
797 concated.node(), r.tail->inc() };
798 return;
799 }
800 } else {
801 if (supports_transient_concat) {
802 auto tail_offst = l.tail_offset();
803 auto tail_size = l.size - tail_offst;
804 auto concated = concat_trees_mut(
805 el,
806 el, l.root, l.shift, tail_offst, l.tail, tail_size,
807 MemoryPolicy::transience_t::noone,
808 r.root, r.shift, r.tail_offset());
809 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
810 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
811 l.size += r.size;
812 l.shift = concated.shift();
813 l.root = concated.node();
814 l.tail = r.tail;
815 } else {
816 auto tail_offst = l.tail_offset();
817 auto tail_size = l.size - tail_offst;
818 auto concated = concat_trees(l.root, l.shift, tail_offst,
819 l.tail, tail_size,
820 r.root, r.shift, r.tail_offset());
821 l = { l.size + r.size, concated.shift(),
822 concated.node(), r.tail->inc() };
823 }
824 }
825 }
826
827 friend void concat_mut_r(const rrbtree& l, rrbtree& r, edit_t er)
828 {
829 assert(&l != &r);
830 assert(r.size < (std::numeric_limits<size_t>::max() - l.size));
831 using std::get;
832 if (r.size == 0)
833 r = std::move(l);
834 else if (l.size == 0)
835 return;
836 else if (r.tail_offset() == 0) {
837 // just concat the tail, similar to push_back
838 auto tail_offst = l.tail_offset();
839 auto tail_size = l.size - tail_offst;
840 if (tail_size == branches<BL>) {
841 // this could be improved by making sure that the
842 // newly created nodes as part of the `push_tail()`
843 // are tagged with `er`
844 auto res = l.push_tail(l.root, l.shift, tail_offst,
845 l.tail, tail_size);
846 l.tail->inc(); // note: leak if mutably concatenated
847 // with itself, but this is forbidden
848 // by the interface
849 r = { l.size + r.size, get<0>(res), get<1>(res),
850 r.tail->inc() };
851 return;
852 } else if (tail_size + r.size <= branches<BL>) {
853 // doing this in a exception way mutating way is very
854 // tricky while potential performance gains are
855 // minimal (we need to move every element of the right
856 // tail anyways to make space for the left tail)
857 //
858 // we could however improve this by at least moving the
859 // elements of the right tail...
860 auto new_tail = node_t::copy_leaf(l.tail, tail_size,
861 r.tail, r.size);
862 r = { l.size + r.size, l.shift, l.root->inc(), new_tail };
863 return;
864 } else {
865 // like the immutable version
866 auto remaining = branches<BL> - tail_size;
867 auto add_tail = node_t::copy_leaf_e(er,
868 l.tail, tail_size,
869 r.tail, remaining);
870 try {
871 auto new_tail = node_t::copy_leaf_e(er, r.tail, remaining, r.size);
872 try {
873 // this could be improved by making sure that the
874 // newly created nodes as part of the `push_tail()`
875 // are tagged with `er`
876 auto new_root = l.push_tail(l.root, l.shift, tail_offst,
877 add_tail, branches<BL>);
878 r = { l.size + r.size,
879 get<0>(new_root), get<1>(new_root),
880 new_tail };
881 return;
882 } catch (...) {
883 node_t::delete_leaf(new_tail, r.size - remaining);
884 throw;
885 }
886 } catch (...) {
887 node_t::delete_leaf(add_tail, branches<BL>);
888 throw;
889 }
890 return;
891 }
892 } else if (l.tail_offset() == 0) {
893 if (supports_transient_concat) {
894 auto tail_offst = l.tail_offset();
895 auto tail_size = l.size - tail_offst;
896 auto concated = concat_trees_mut(
897 er,
898 MemoryPolicy::transience_t::noone, l.tail, tail_size,
899 er,r.root, r.shift, r.tail_offset());
900 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
901 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
902 r.size += l.size;
903 r.shift = concated.shift();
904 r.root = concated.node();
905 } else {
906 auto tail_offst = l.tail_offset();
907 auto tail_size = l.size - tail_offst;
908 auto concated = concat_trees(l.tail, tail_size,
909 r.root, r.shift, r.tail_offset());
910 r = { l.size + r.size, concated.shift(),
911 concated.node(), r.tail->inc() };
912 return;
913 }
914 } else {
915 if (supports_transient_concat) {
916 auto tail_offst = l.tail_offset();
917 auto tail_size = l.size - tail_offst;
918 auto concated = concat_trees_mut(
919 er,
920 MemoryPolicy::transience_t::noone,
921 l.root, l.shift, tail_offst, l.tail, tail_size,
922 er, r.root, r.shift, r.tail_offset());
923 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
924 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
925 r.size += l.size;
926 r.shift = concated.shift();
927 r.root = concated.node();
928 return;
929 } else {
930 auto tail_offst = l.tail_offset();
931 auto tail_size = l.size - tail_offst;
932 auto concated = concat_trees(l.root, l.shift, tail_offst,
933 l.tail, tail_size,
934 r.root, r.shift, r.tail_offset());
935 r = { l.size + r.size, concated.shift(),
936 concated.node(), r.tail->inc() };
937 return;
938 }
939 }
940 }
941
942 friend void concat_mut_lr_l(rrbtree& l, edit_t el, rrbtree& r, edit_t er)
943 {
944 assert(&l != &r);
945 assert(r.size < (std::numeric_limits<size_t>::max() - l.size));
946 using std::get;
947 if (l.size == 0)
948 l = r;
949 else if (r.size == 0)
950 return;
951 else if (r.tail_offset() == 0) {
952 // just concat the tail, similar to push_back
953 auto tail_offst = l.tail_offset();
954 auto tail_size = l.size - tail_offst;
955 if (tail_size == branches<BL>) {
956 l.push_tail_mut(el, tail_offst, l.tail, tail_size);
957 l.tail = r.tail->inc();
958 l.size += r.size;
959 return;
960 } else if (tail_size + r.size <= branches<BL>) {
961 l.ensure_mutable_tail(el, tail_size);
962 if (r.tail->can_mutate(er))
963 detail::uninitialized_move(r.tail->leaf(),
964 r.tail->leaf() + r.size,
965 l.tail->leaf() + tail_size);
966 else
967 std::uninitialized_copy(r.tail->leaf(),
968 r.tail->leaf() + r.size,
969 l.tail->leaf() + tail_size);
970 l.size += r.size;
971 return;
972 } else {
973 auto remaining = branches<BL> - tail_size;
974 l.ensure_mutable_tail(el, tail_size);
975 if (r.tail->can_mutate(er))
976 detail::uninitialized_move(r.tail->leaf(),
977 r.tail->leaf() + remaining,
978 l.tail->leaf() + tail_size);
979 else
980 std::uninitialized_copy(r.tail->leaf(),
981 r.tail->leaf() + remaining,
982 l.tail->leaf() + tail_size);
983 try {
984 auto new_tail = node_t::copy_leaf_e(el, r.tail, remaining, r.size);
985 try {
986 l.push_tail_mut(el, tail_offst, l.tail, branches<BL>);
987 l.tail = new_tail;
988 l.size += r.size;
989 return;
990 } catch (...) {
991 node_t::delete_leaf(new_tail, r.size - remaining);
992 throw;
993 }
994 } catch (...) {
995 destroy_n(r.tail->leaf() + tail_size, remaining);
996 throw;
997 }
998 }
999 } else if (l.tail_offset() == 0) {
1000 if (supports_transient_concat) {
1001 auto tail_offst = l.tail_offset();
1002 auto tail_size = l.size - tail_offst;
1003 auto concated = concat_trees_mut(
1004 el,
1005 el, l.tail, tail_size,
1006 er, r.root, r.shift, r.tail_offset());
1007 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
1008 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
1009 l.size += r.size;
1010 l.shift = concated.shift();
1011 l.root = concated.node();
1012 l.tail = r.tail;
1013 r.hard_reset();
1014 } else {
1015 auto tail_offst = l.tail_offset();
1016 auto tail_size = l.size - tail_offst;
1017 auto concated = concat_trees(l.tail, tail_size,
1018 r.root, r.shift, r.tail_offset());
1019 l = { l.size + r.size, concated.shift(),
1020 concated.node(), r.tail->inc() };
1021 return;
1022 }
1023 } else {
1024 if (supports_transient_concat) {
1025 auto tail_offst = l.tail_offset();
1026 auto tail_size = l.size - tail_offst;
1027 auto concated = concat_trees_mut(
1028 el,
1029 el, l.root, l.shift, tail_offst, l.tail, tail_size,
1030 er, r.root, r.shift, r.tail_offset());
1031 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
1032 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
1033 l.size += r.size;
1034 l.shift = concated.shift();
1035 l.root = concated.node();
1036 l.tail = r.tail;
1037 r.hard_reset();
1038 } else {
1039 auto tail_offst = l.tail_offset();
1040 auto tail_size = l.size - tail_offst;
1041 auto concated = concat_trees(l.root, l.shift, tail_offst,
1042 l.tail, tail_size,
1043 r.root, r.shift, r.tail_offset());
1044 l = { l.size + r.size, concated.shift(),
1045 concated.node(), r.tail->inc() };
1046 }
1047 }
1048 }
1049
1050 friend void concat_mut_lr_r(rrbtree& l, edit_t el, rrbtree& r, edit_t er)
1051 {
1052 assert(&l != &r);
1053 assert(r.size < (std::numeric_limits<size_t>::max() - l.size));
1054 using std::get;
1055 if (r.size == 0)
1056 r = l;
1057 else if (l.size == 0)
1058 return;
1059 else if (r.tail_offset() == 0) {
1060 // just concat the tail, similar to push_back
1061 auto tail_offst = l.tail_offset();
1062 auto tail_size = l.size - tail_offst;
1063 if (tail_size == branches<BL>) {
1064 // this could be improved by making sure that the
1065 // newly created nodes as part of the `push_tail()`
1066 // are tagged with `er`
1067 auto res = l.push_tail(l.root, l.shift, tail_offst,
1068 l.tail, tail_size);
1069 r = { l.size + r.size, get<0>(res), get<1>(res),
1070 r.tail->inc() };
1071 return;
1072 } else if (tail_size + r.size <= branches<BL>) {
1073 // doing this in a exception way mutating way is very
1074 // tricky while potential performance gains are
1075 // minimal (we need to move every element of the right
1076 // tail anyways to make space for the left tail)
1077 //
1078 // we could however improve this by at least moving the
1079 // elements of the mutable tails...
1080 auto new_tail = node_t::copy_leaf(l.tail, tail_size,
1081 r.tail, r.size);
1082 r = { l.size + r.size, l.shift, l.root->inc(), new_tail };
1083 return;
1084 } else {
1085 // like the immutable version.
1086 // we could improve this also by moving elements
1087 // instead of just copying them
1088 auto remaining = branches<BL> - tail_size;
1089 auto add_tail = node_t::copy_leaf_e(er,
1090 l.tail, tail_size,
1091 r.tail, remaining);
1092 try {
1093 auto new_tail = node_t::copy_leaf_e(er, r.tail, remaining, r.size);
1094 try {
1095 // this could be improved by making sure that the
1096 // newly created nodes as part of the `push_tail()`
1097 // are tagged with `er`
1098 auto new_root = l.push_tail(l.root, l.shift, tail_offst,
1099 add_tail, branches<BL>);
1100 r = { l.size + r.size,
1101 get<0>(new_root), get<1>(new_root),
1102 new_tail };
1103 return;
1104 } catch (...) {
1105 node_t::delete_leaf(new_tail, r.size - remaining);
1106 throw;
1107 }
1108 } catch (...) {
1109 node_t::delete_leaf(add_tail, branches<BL>);
1110 throw;
1111 }
1112 return;
1113 }
1114 } else if (l.tail_offset() == 0) {
1115 if (supports_transient_concat) {
1116 auto tail_offst = l.tail_offset();
1117 auto tail_size = l.size - tail_offst;
1118 auto concated = concat_trees_mut(
1119 er,
1120 el, l.tail, tail_size,
1121 er,r.root, r.shift, r.tail_offset());
1122 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
1123 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
1124 r.size += l.size;
1125 r.shift = concated.shift();
1126 r.root = concated.node();
1127 l.hard_reset();
1128 } else {
1129 auto tail_offst = l.tail_offset();
1130 auto tail_size = l.size - tail_offst;
1131 auto concated = concat_trees(l.tail, tail_size,
1132 r.root, r.shift, r.tail_offset());
1133 r = { l.size + r.size, concated.shift(),
1134 concated.node(), r.tail->inc() };
1135 return;
1136 }
1137 } else {
1138 if (supports_transient_concat) {
1139 auto tail_offst = l.tail_offset();
1140 auto tail_size = l.size - tail_offst;
1141 auto concated = concat_trees_mut(
1142 er,
1143 el, l.root, l.shift, tail_offst, l.tail, tail_size,
1144 er, r.root, r.shift, r.tail_offset());
1145 IMMER_ASSERT_TAGGED(concated.shift() == concated.node()->compute_shift());
1146 assert(concated.node()->check(concated.shift(), l.size + r.tail_offset()));
1147 r.size += l.size;
1148 r.shift = concated.shift();
1149 r.root = concated.node();
1150 l.hard_reset();
1151 } else {
1152 auto tail_offst = l.tail_offset();
1153 auto tail_size = l.size - tail_offst;
1154 auto concated = concat_trees(l.root, l.shift, tail_offst,
1155 l.tail, tail_size,
1156 r.root, r.shift, r.tail_offset());
1157 r = { l.size + r.size, concated.shift(),
1158 concated.node(), r.tail->inc() };
1159 }
1160 }
1161 }
1162
1163 void hard_reset()
1164 {
1165 assert(supports_transient_concat);
1166 auto&& empty_ = empty();
1167 size = empty_.size;
1168 shift = empty_.shift;
1169 root = empty_.root;
1170 tail = empty_.tail;
1171 }
1172
1173 bool check_tree() const
1174 {
1175 assert(shift <= sizeof(size_t) * 8 - BL);
1176 assert(shift >= BL);
1177 assert(tail_offset() <= size);
1178 assert(tail_size() <= branches<BL>);
1179#if IMMER_DEBUG_DEEP_CHECK
1180 assert(check_root());
1181 assert(check_tail());
1182#endif
1183 return true;
1184 }
1185
1186 bool check_tail() const
1187 {
1188#if IMMER_DEBUG_DEEP_CHECK
1189 if (tail_size() > 0)
1190 assert(tail->check(endshift<B, BL>, tail_size()));
1191#endif
1192 return true;
1193 }
1194
1195 bool check_root() const
1196 {
1197#if IMMER_DEBUG_DEEP_CHECK
1198 if (tail_offset() > 0)
1199 assert(root->check(shift, tail_offset()));
1200 else {
1201 IMMER_ASSERT_TAGGED(root->kind() == node_t::kind_t::inner);
1202 assert(shift == BL);
1203 }
1204#endif
1205 return true;
1206 }
1207
1208#if IMMER_DEBUG_PRINT
1209 void debug_print(std::ostream& out) const
1210 {
1211 out
1212 << "--" << std::endl
1213 << "{" << std::endl
1214 << " size = " << size << std::endl
1215 << " shift = " << shift << std::endl
1216 << " root = " << std::endl;
1217 debug_print_node(out, root, shift, tail_offset());
1218 out << " tail = " << std::endl;
1219 debug_print_node(out, tail, endshift<B, BL>, tail_size());
1220 out << "}" << std::endl;
1221 }
1222
1223 void debug_print_indent(std::ostream& out, unsigned indent) const
1224 {
1225 while (indent --> 0)
1226 out << ' ';
1227 }
1228
1229 void debug_print_node(std::ostream& out,
1230 node_t* node,
1231 shift_t shift,
1232 size_t size,
1233 unsigned indent = 8) const
1234 {
1235 const auto indent_step = 4;
1236
1237 if (shift == endshift<B, BL>) {
1238 debug_print_indent(out, indent);
1239 out << "- {" << size << "} "
1240 << pretty_print_array(node->leaf(), size)
1241 << std::endl;
1242 } else if (auto r = node->relaxed()) {
1243 auto count = r->d.count;
1244 debug_print_indent(out, indent);
1245 out << "# {" << size << "} "
1246 << pretty_print_array(r->d.sizes, r->d.count)
1247 << std::endl;
1248 auto last_size = size_t{};
1249 for (auto i = count_t{}; i < count; ++i) {
1250 debug_print_node(out,
1251 node->inner()[i],
1252 shift - B,
1253 r->d.sizes[i] - last_size,
1254 indent + indent_step);
1255 last_size = r->d.sizes[i];
1256 }
1257 } else {
1258 debug_print_indent(out, indent);
1259 out << "+ {" << size << "}" << std::endl;
1260 auto count = (size >> shift)
1261 + (size - ((size >> shift) << shift) > 0);
1262 if (count) {
1263 for (auto i = count_t{}; i < count - 1; ++i)
1264 debug_print_node(out,
1265 node->inner()[i],
1266 shift - B,
1267 1 << shift,
1268 indent + indent_step);
1269 debug_print_node(out,
1270 node->inner()[count - 1],
1271 shift - B,
1272 size - ((count - 1) << shift),
1273 indent + indent_step);
1274 }
1275 }
1276 }
1277#endif // IMMER_DEBUG_PRINT
1278};
1279
1280} // namespace rbts
1281} // namespace detail
1282} // namespace immer
1283