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 <algorithm>
12#include <memory>
13#include <numeric>
14#include <utility>
15
16#include <immer/config.hpp>
17#include <immer/heap/tags.hpp>
18#include <immer/detail/util.hpp>
19#include <immer/detail/rbts/position.hpp>
20#include <immer/detail/rbts/visitor.hpp>
21
22namespace immer {
23namespace detail {
24namespace rbts {
25
26template <typename T>
27struct array_for_visitor : visitor_base<array_for_visitor<T>>
28{
29 using this_t = array_for_visitor;
30
31 template <typename PosT>
32 static T* visit_inner(PosT&& pos, size_t idx)
33 { return pos.descend(this_t{}, idx); }
34
35 template <typename PosT>
36 static T* visit_leaf(PosT&& pos, size_t)
37 { return pos.node()->leaf(); }
38};
39
40template <typename T>
41struct region_for_visitor : visitor_base<region_for_visitor<T>>
42{
43 using this_t = region_for_visitor;
44 using result_t = std::tuple<T*, size_t, size_t>;
45
46 template <typename PosT>
47 static result_t visit_inner(PosT&& pos, size_t idx)
48 { return pos.towards(this_t{}, idx); }
49
50 template <typename PosT>
51 static result_t visit_leaf(PosT&& pos, size_t idx)
52 { return std::make_tuple( pos.node()->leaf(), pos.index(idx), pos.count() ); }
53};
54
55template <typename T>
56struct get_visitor : visitor_base<get_visitor<T>>
57{
58 using this_t = get_visitor;
59
60 template <typename PosT>
61 static const T& visit_inner(PosT&& pos, size_t idx)
62 { return pos.descend(this_t{}, idx); }
63
64 template <typename PosT>
65 static const T& visit_leaf(PosT&& pos, size_t idx)
66 { return pos.node()->leaf() [pos.index(idx)]; }
67};
68
69struct for_each_chunk_visitor : visitor_base<for_each_chunk_visitor>
70{
71 using this_t = for_each_chunk_visitor;
72
73 template <typename Pos, typename Fn>
74 static void visit_inner(Pos&& pos, Fn&& fn)
75 { pos.each(this_t{}, fn); }
76
77 template <typename Pos, typename Fn>
78 static void visit_leaf(Pos&& pos, Fn&& fn)
79 {
80 auto data = pos.node()->leaf();
81 fn(data, data + pos.count());
82 }
83};
84
85struct for_each_chunk_p_visitor : visitor_base<for_each_chunk_p_visitor>
86{
87 using this_t = for_each_chunk_p_visitor;
88
89 template <typename Pos, typename Fn>
90 static bool visit_inner(Pos&& pos, Fn&& fn)
91 { return pos.each_pred(this_t{}, fn); }
92
93 template <typename Pos, typename Fn>
94 static bool visit_leaf(Pos&& pos, Fn&& fn)
95 {
96 auto data = pos.node()->leaf();
97 return fn(data, data + pos.count());
98 }
99};
100
101struct for_each_chunk_left_visitor : visitor_base<for_each_chunk_left_visitor>
102{
103 using this_t = for_each_chunk_left_visitor;
104
105 template <typename Pos, typename Fn>
106 static void visit_inner(Pos&& pos,
107 size_t last, Fn&& fn)
108 {
109 auto l = pos.index(last);
110 pos.each_left(for_each_chunk_visitor{}, l, fn);
111 pos.towards_oh(this_t{}, last, l, fn);
112 }
113
114 template <typename Pos, typename Fn>
115 static void visit_leaf(Pos&& pos,
116 size_t last,
117 Fn&& fn)
118 {
119 auto data = pos.node()->leaf();
120 auto l = pos.index(last);
121 fn(data, data + l + 1);
122 }
123};
124
125struct for_each_chunk_right_visitor : visitor_base<for_each_chunk_right_visitor>
126{
127 using this_t = for_each_chunk_right_visitor;
128
129 template <typename Pos, typename Fn>
130 static void visit_inner(Pos&& pos,
131 size_t first, Fn&& fn)
132 {
133 auto f = pos.index(first);
134 pos.towards_oh(this_t{}, first, f, fn);
135 pos.each_right(for_each_chunk_visitor{}, f + 1, fn);
136 }
137
138 template <typename Pos, typename Fn>
139 static void visit_leaf(Pos&& pos,
140 size_t first,
141 Fn&& fn)
142 {
143 auto data = pos.node()->leaf();
144 auto f = pos.index(first);
145 fn(data + f, data + pos.count());
146 }
147};
148
149struct for_each_chunk_i_visitor : visitor_base<for_each_chunk_i_visitor>
150{
151 using this_t = for_each_chunk_i_visitor;
152
153 template <typename Pos, typename Fn>
154 static void visit_relaxed(Pos&& pos,
155 size_t first, size_t last,
156 Fn&& fn)
157 {
158 // we are going towards *two* indices, so we need to do the
159 // relaxed as a special case to correct the second index
160 if (first < last) {
161 auto f = pos.index(first);
162 auto l = pos.index(last - 1);
163 if (f == l) {
164 auto sbh = pos.size_before(f);
165 pos.towards_oh_sbh(this_t{}, first, f, sbh, last - sbh, fn);
166 } else {
167 assert(f < l);
168 pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn);
169 pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn);
170 pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn);
171 }
172 }
173 }
174
175 template <typename Pos, typename Fn>
176 static void visit_regular(Pos&& pos,
177 size_t first, size_t last,
178 Fn&& fn)
179 {
180 if (first < last) {
181 auto f = pos.index(first);
182 auto l = pos.index(last - 1);
183 if (f == l)
184 pos.towards_oh(this_t{}, first, f, last, fn);
185 else {
186 assert(f < l);
187 pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn);
188 pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn);
189 pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn);
190 }
191 }
192 }
193
194 template <typename Pos, typename Fn>
195 static void visit_leaf(Pos&& pos,
196 size_t first, size_t last,
197 Fn&& fn)
198 {
199 auto data = pos.node()->leaf();
200 if (first < last) {
201 auto f = pos.index(first);
202 auto l = pos.index(last - 1);
203 fn(data + f, data + l + 1);
204 }
205 }
206};
207
208struct for_each_chunk_p_left_visitor
209 : visitor_base<for_each_chunk_p_left_visitor>
210{
211 using this_t = for_each_chunk_p_left_visitor;
212
213 template <typename Pos, typename Fn>
214 static bool visit_inner(Pos&& pos,
215 size_t last, Fn&& fn)
216 {
217 auto l = pos.index(last);
218 return pos.each_pred_left(for_each_chunk_p_visitor{}, l, fn)
219 && pos.towards_oh(this_t{}, last, l, fn);
220 }
221
222 template <typename Pos, typename Fn>
223 static bool visit_leaf(Pos&& pos,
224 size_t last,
225 Fn&& fn)
226 {
227 auto data = pos.node()->leaf();
228 auto l = pos.index(last);
229 return fn(data, data + l + 1);
230 }
231};
232
233struct for_each_chunk_p_right_visitor
234 : visitor_base<for_each_chunk_p_right_visitor>
235{
236 using this_t = for_each_chunk_p_right_visitor;
237
238 template <typename Pos, typename Fn>
239 static bool visit_inner(Pos&& pos,
240 size_t first, Fn&& fn)
241 {
242 auto f = pos.index(first);
243 return pos.towards_oh(this_t{}, first, f, fn)
244 && pos.each_pred_right(for_each_chunk_p_visitor{}, f + 1, fn);
245 }
246
247 template <typename Pos, typename Fn>
248 static bool visit_leaf(Pos&& pos,
249 size_t first,
250 Fn&& fn)
251 {
252 auto data = pos.node()->leaf();
253 auto f = pos.index(first);
254 return fn(data + f, data + pos.count());
255 }
256};
257
258struct for_each_chunk_p_i_visitor : visitor_base<for_each_chunk_p_i_visitor>
259{
260 using this_t = for_each_chunk_p_i_visitor;
261
262 template <typename Pos, typename Fn>
263 static bool visit_relaxed(Pos&& pos,
264 size_t first, size_t last,
265 Fn&& fn)
266 {
267 // we are going towards *two* indices, so we need to do the
268 // relaxed as a special case to correct the second index
269 if (first < last) {
270 auto f = pos.index(first);
271 auto l = pos.index(last - 1);
272 if (f == l) {
273 auto sbh = pos.size_before(f);
274 return pos.towards_oh_sbh(this_t{}, first, f, sbh, last - sbh, fn);
275 } else {
276 assert(f < l);
277 return pos.towards_oh(for_each_chunk_p_right_visitor{}, first, f, fn)
278 && pos.each_pred_i(for_each_chunk_p_visitor{}, f + 1, l, fn)
279 && pos.towards_oh(for_each_chunk_p_left_visitor{}, last - 1, l, fn);
280 }
281 }
282 return true;
283 }
284
285 template <typename Pos, typename Fn>
286 static bool visit_regular(Pos&& pos,
287 size_t first, size_t last,
288 Fn&& fn)
289 {
290 if (first < last) {
291 auto f = pos.index(first);
292 auto l = pos.index(last - 1);
293 if (f == l)
294 return pos.towards_oh(this_t{}, first, f, last, fn);
295 else {
296 assert(f < l);
297 return pos.towards_oh(for_each_chunk_p_right_visitor{}, first, f, fn)
298 && pos.each_pred_i(for_each_chunk_p_visitor{}, f + 1, l, fn)
299 && pos.towards_oh(for_each_chunk_p_left_visitor{}, last - 1, l, fn);
300 }
301 }
302 return true;
303 }
304
305 template <typename Pos, typename Fn>
306 static bool visit_leaf(Pos&& pos,
307 size_t first, size_t last,
308 Fn&& fn)
309 {
310 auto data = pos.node()->leaf();
311 if (first < last) {
312 auto f = pos.index(first);
313 auto l = pos.index(last - 1);
314 return fn(data + f, data + l + 1);
315 }
316 return true;
317 }
318};
319
320struct equals_visitor : visitor_base<equals_visitor>
321{
322 using this_t = equals_visitor;
323
324 struct this_aux_t : visitor_base<this_aux_t>
325 {
326 template <typename PosR, typename PosL,typename Iter>
327 static bool visit_inner(PosR&& posr,
328 count_t i, PosL&& posl,
329 Iter&& first, size_t idx)
330 { return posl.nth_sub(i, this_t{}, posr, first, idx); }
331
332 template <typename PosR, typename PosL,typename Iter>
333 static bool visit_leaf(PosR&& posr,
334 count_t i, PosL&& posl,
335 Iter&& first, size_t idx)
336 { return posl.nth_sub_leaf(i, this_t{}, posr, first, idx); }
337 };
338
339 struct rrb : visitor_base<rrb>
340 {
341 template <typename PosR, typename Iter, typename Node>
342 static bool visit_node(PosR&& posr, Iter&& first,
343 Node* rootl, shift_t shiftl, size_t sizel)
344 {
345 assert(shiftl <= posr.shift());
346 return shiftl == posr.shift()
347 ? visit_maybe_relaxed_sub(rootl, shiftl, sizel,
348 this_t{}, posr, first, size_t{})
349 : posr.first_sub_inner(rrb{}, first, rootl, shiftl, sizel);
350 }
351 };
352
353 template <typename Iter>
354 static auto equal_chunk_p(Iter&& iter)
355 {
356 return [iter] (auto f, auto e) mutable {
357 if (f == &*iter) {
358 iter += e - f;
359 return true;
360 }
361 for (; f != e; ++f, ++iter)
362 if (*f != *iter)
363 return false;
364 return true;
365 };
366 }
367
368 template <typename PosL, typename PosR, typename Iter>
369 static bool visit_relaxed(PosL&& posl, PosR&& posr,
370 Iter&& first, size_t idx)
371 {
372 auto nl = posl.node();
373 auto nr = posr.node();
374 if (nl == nr)
375 return true;
376 auto cl = posl.count();
377 auto cr = posr.count();
378 assert(cr > 0);
379 auto sbr = size_t{};
380 auto i = count_t{};
381 auto j = count_t{};
382 for (; i < cl; ++i) {
383 auto sbl = posl.size_before(i);
384 for (; j + 1 < cr && (sbr = posr.size_before(j)) < sbl; ++j);
385 auto res = sbl == sbr
386 ? posr.nth_sub(j, this_aux_t{}, i, posl, first, idx + sbl)
387 : posl.nth_sub(i, for_each_chunk_p_visitor{},
388 this_t::equal_chunk_p(first + (idx + sbl)));
389 if (!res) return false;
390 }
391 return true;
392 }
393
394 template <typename PosL, typename PosR, typename Iter>
395 static std::enable_if_t<is_relaxed_v<PosR>, bool>
396 visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
397 {
398 return this_t::visit_relaxed(posl, posr, first, idx);
399 }
400
401 template <typename PosL, typename PosR, typename Iter>
402 static std::enable_if_t<!is_relaxed_v<PosR>, bool>
403 visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
404 {
405 return posl.count() >= posr.count()
406 ? this_t::visit_regular(posl, posr.node())
407 : this_t::visit_regular(posr, posl.node());
408 }
409
410 template <typename PosL, typename PosR, typename Iter>
411 static bool visit_leaf(PosL&& posl,
412 PosR&& posr, Iter&& first, size_t idx)
413 {
414 if (posl.node() == posr.node())
415 return true;
416 auto cl = posl.count();
417 auto cr = posr.count();
418 auto mp = std::min(cl, cr);
419 return
420 std::equal(posl.node()->leaf(),
421 posl.node()->leaf() + mp,
422 posr.node()->leaf()) &&
423 std::equal(posl.node()->leaf() + mp,
424 posl.node()->leaf() + posl.count(),
425 first + (idx + mp));
426 }
427
428 template <typename Pos, typename NodeT>
429 static bool visit_regular(Pos&& pos, NodeT* other)
430 {
431 auto node = pos.node();
432 return node == other
433 || pos.each_pred_zip(this_t{}, other);
434 }
435
436 template <typename Pos, typename NodeT>
437 static bool visit_leaf(Pos&& pos, NodeT* other)
438 {
439 auto node = pos.node();
440 return node == other
441 || std::equal(node->leaf(), node->leaf() + pos.count(),
442 other->leaf());
443 }
444};
445
446template <typename NodeT>
447struct update_visitor : visitor_base<update_visitor<NodeT>>
448{
449 using node_t = NodeT;
450 using this_t = update_visitor;
451
452 template <typename Pos, typename Fn>
453 static node_t* visit_relaxed(Pos&& pos, size_t idx, Fn&& fn)
454 {
455 auto offset = pos.index(idx);
456 auto count = pos.count();
457 auto node = node_t::make_inner_sr_n(count, pos.relaxed());
458 try {
459 auto child = pos.towards_oh(this_t{}, idx, offset, fn);
460 node_t::do_copy_inner_sr(node, pos.node(), count);
461 node->inner()[offset]->dec_unsafe();
462 node->inner()[offset] = child;
463 return node;
464 } catch (...) {
465 node_t::delete_inner_r(node, count);
466 throw;
467 }
468 }
469
470 template <typename Pos, typename Fn>
471 static node_t* visit_regular(Pos&& pos, size_t idx, Fn&& fn)
472 {
473 auto offset = pos.index(idx);
474 auto count = pos.count();
475 auto node = node_t::make_inner_n(count);
476 try {
477 auto child = pos.towards_oh_ch(this_t{}, idx, offset, count, fn);
478 node_t::do_copy_inner(node, pos.node(), count);
479 node->inner()[offset]->dec_unsafe();
480 node->inner()[offset] = child;
481 return node;
482 } catch (...) {
483 node_t::delete_inner(node, count);
484 throw;
485 }
486 }
487
488 template <typename Pos, typename Fn>
489 static node_t* visit_leaf(Pos&& pos, size_t idx, Fn&& fn)
490 {
491 auto offset = pos.index(idx);
492 auto node = node_t::copy_leaf(pos.node(), pos.count());
493 try {
494 node->leaf()[offset] = std::forward<Fn>(fn) (
495 std::move(node->leaf()[offset]));
496 return node;
497 } catch (...) {
498 node_t::delete_leaf(node, pos.count());
499 throw;
500 }
501 }
502};
503
504struct dec_visitor : visitor_base<dec_visitor>
505{
506 using this_t = dec_visitor;
507
508 template <typename Pos>
509 static void visit_relaxed(Pos&& p)
510 {
511 using node_t = node_type<Pos>;
512 auto node = p.node();
513 if (node->dec()) {
514 p.each(this_t{});
515 node_t::delete_inner_r(node, p.count());
516 }
517 }
518
519 template <typename Pos>
520 static void visit_regular(Pos&& p)
521 {
522 using node_t = node_type<Pos>;
523 auto node = p.node();
524 if (node->dec()) {
525 p.each(this_t{});
526 node_t::delete_inner(node, p.count());
527 }
528 }
529
530 template <typename Pos>
531 static void visit_leaf(Pos&& p)
532 {
533 using node_t = node_type<Pos>;
534 auto node = p.node();
535 if (node->dec()) {
536 node_t::delete_leaf(node, p.count());
537 }
538 }
539};
540
541template <typename NodeT>
542void dec_leaf(NodeT* node, count_t n)
543{
544 make_leaf_sub_pos(node, n).visit(dec_visitor{});
545}
546
547template <typename NodeT>
548void dec_inner(NodeT* node, shift_t shift, size_t size)
549{
550 visit_maybe_relaxed_sub(node, shift, size, dec_visitor());
551}
552
553template <typename NodeT>
554void dec_relaxed(NodeT* node, shift_t shift)
555{
556 make_relaxed_pos(node, shift, node->relaxed()).visit(dec_visitor());
557}
558
559template <typename NodeT>
560void dec_regular(NodeT* node, shift_t shift, size_t size)
561{
562 make_regular_pos(node, shift, size).visit(dec_visitor());
563}
564
565template <typename NodeT>
566void dec_empty_regular(NodeT* node)
567{
568 make_empty_regular_pos(node).visit(dec_visitor());
569}
570
571template <typename NodeT>
572struct get_mut_visitor : visitor_base<get_mut_visitor<NodeT>>
573{
574 using node_t = NodeT;
575 using this_t = get_mut_visitor;
576 using value_t = typename NodeT::value_t;
577 using edit_t = typename NodeT::edit_t;
578
579 template <typename Pos>
580 static value_t& visit_relaxed(Pos&& pos, size_t idx,
581 edit_t e, node_t** location)
582 {
583 auto offset = pos.index(idx);
584 auto count = pos.count();
585 auto node = pos.node();
586 if (node->can_mutate(e)) {
587 return pos.towards_oh(this_t{}, idx, offset,
588 e, &node->inner()[offset]);
589 } else {
590 auto new_node = node_t::copy_inner_sr_e(e, node, count);
591 try {
592 auto& res = pos.towards_oh(this_t{}, idx, offset,
593 e, &new_node->inner()[offset]);
594 pos.visit(dec_visitor{});
595 *location = new_node;
596 return res;
597 } catch (...) {
598 dec_relaxed(new_node, pos.shift());
599 throw;
600 }
601 }
602 }
603
604 template <typename Pos>
605 static value_t& visit_regular(Pos&& pos, size_t idx,
606 edit_t e, node_t** location)
607 {
608 assert(pos.node() == *location);
609 auto offset = pos.index(idx);
610 auto count = pos.count();
611 auto node = pos.node();
612 if (node->can_mutate(e)) {
613 return pos.towards_oh_ch(this_t{}, idx, offset, count,
614 e, &node->inner()[offset]);
615 } else {
616 auto new_node = node_t::copy_inner_e(e, node, count);
617 try {
618 auto& res = pos.towards_oh_ch(this_t{}, idx, offset, count,
619 e, &new_node->inner()[offset]);
620 pos.visit(dec_visitor{});
621 *location = new_node;
622 return res;
623 } catch (...) {
624 dec_regular(new_node, pos.shift(), pos.size());
625 throw;
626 }
627 }
628 }
629
630 template <typename Pos>
631 static value_t& visit_leaf(Pos&& pos, size_t idx,
632 edit_t e, node_t** location)
633 {
634 assert(pos.node() == *location);
635 auto node = pos.node();
636 if (node->can_mutate(e)) {
637 return node->leaf() [pos.index(idx)];
638 } else {
639 auto new_node = node_t::copy_leaf_e(e, pos.node(), pos.count());
640 pos.visit(dec_visitor{});
641 *location = new_node;
642 return new_node->leaf() [pos.index(idx)];
643 }
644 }
645};
646
647template <typename NodeT, bool Mutating = true>
648struct push_tail_mut_visitor
649 : visitor_base<push_tail_mut_visitor<NodeT, Mutating>>
650{
651 static constexpr auto B = NodeT::bits;
652 static constexpr auto BL = NodeT::bits_leaf;
653
654 using this_t = push_tail_mut_visitor;
655 using this_no_mut_t = push_tail_mut_visitor<NodeT, false>;
656 using node_t = NodeT;
657 using edit_t = typename NodeT::edit_t;
658
659 template <typename Pos>
660 static node_t* visit_relaxed(Pos&& pos, edit_t e, node_t* tail, count_t ts)
661 {
662 auto node = pos.node();
663 auto level = pos.shift();
664 auto idx = pos.count() - 1;
665 auto children = pos.size(idx);
666 auto new_idx = children == size_t{1} << level || level == BL
667 ? idx + 1 : idx;
668 auto new_child = static_cast<node_t*>(nullptr);
669 auto mutate = Mutating && node->can_mutate(e);
670
671 if (new_idx >= branches<B>)
672 return nullptr;
673 else if (idx == new_idx) {
674 new_child = mutate
675 ? pos.last_oh_csh(this_t{}, idx, children, e, tail, ts)
676 : pos.last_oh_csh(this_no_mut_t{}, idx, children, e, tail, ts);
677 if (!new_child) {
678 if (++new_idx < branches<B>)
679 new_child = node_t::make_path_e(e, level - B, tail);
680 else
681 return nullptr;
682 }
683 } else
684 new_child = node_t::make_path_e(e, level - B, tail);
685
686 if (mutate) {
687 auto count = new_idx + 1;
688 auto relaxed = node->ensure_mutable_relaxed_n(e, new_idx);
689 node->inner()[new_idx] = new_child;
690 relaxed->d.sizes[new_idx] = pos.size() + ts;
691 relaxed->d.count = count;
692 return node;
693 } else {
694 try {
695 auto count = new_idx + 1;
696 auto new_node = node_t::copy_inner_r_e(e, pos.node(), new_idx);
697 auto relaxed = new_node->relaxed();
698 new_node->inner()[new_idx] = new_child;
699 relaxed->d.sizes[new_idx] = pos.size() + ts;
700 relaxed->d.count = count;
701 if (Mutating) pos.visit(dec_visitor{});
702 return new_node;
703 } catch (...) {
704 auto shift = pos.shift();
705 auto size = new_idx == idx ? children + ts : ts;
706 if (shift > BL) {
707 tail->inc();
708 dec_inner(new_child, shift - B, size);
709 }
710 throw;
711 }
712 }
713 }
714
715 template <typename Pos, typename... Args>
716 static node_t* visit_regular(Pos&& pos, edit_t e, node_t* tail, Args&&...)
717 {
718 assert((pos.size() & mask<BL>) == 0);
719 auto node = pos.node();
720 auto idx = pos.index(pos.size() - 1);
721 auto new_idx = pos.index(pos.size() + branches<BL> - 1);
722 auto mutate = Mutating && node->can_mutate(e);
723 if (mutate) {
724 node->inner()[new_idx] =
725 idx == new_idx ? pos.last_oh(this_t{}, idx, e, tail)
726 /* otherwise */ : node_t::make_path_e(e, pos.shift() - B, tail);
727 return node;
728 } else {
729 auto new_parent = node_t::make_inner_e(e);
730 try {
731 new_parent->inner()[new_idx] =
732 idx == new_idx ? pos.last_oh(this_no_mut_t{}, idx, e, tail)
733 /* otherwise */ : node_t::make_path_e(e, pos.shift() - B, tail);
734 node_t::do_copy_inner(new_parent, node, new_idx);
735 if (Mutating) pos.visit(dec_visitor{});
736 return new_parent;
737 } catch (...) {
738 node_t::delete_inner_e(new_parent);
739 throw;
740 }
741 }
742 }
743
744 template <typename Pos, typename... Args>
745 static node_t* visit_leaf(Pos&& pos, edit_t e, node_t* tail, Args&&...)
746 { IMMER_UNREACHABLE; }
747};
748
749template <typename NodeT>
750struct push_tail_visitor : visitor_base<push_tail_visitor<NodeT>>
751{
752 static constexpr auto B = NodeT::bits;
753 static constexpr auto BL = NodeT::bits_leaf;
754
755 using this_t = push_tail_visitor;
756 using node_t = NodeT;
757
758 template <typename Pos>
759 static node_t* visit_relaxed(Pos&& pos, node_t* tail, count_t ts)
760 {
761 auto level = pos.shift();
762 auto idx = pos.count() - 1;
763 auto children = pos.size(idx);
764 auto new_idx = children == size_t{1} << level || level == BL
765 ? idx + 1 : idx;
766 auto new_child = static_cast<node_t*>(nullptr);
767 if (new_idx >= branches<B>)
768 return nullptr;
769 else if (idx == new_idx) {
770 new_child = pos.last_oh_csh(this_t{}, idx, children, tail, ts);
771 if (!new_child) {
772 if (++new_idx < branches<B>)
773 new_child = node_t::make_path(level - B, tail);
774 else
775 return nullptr;
776 }
777 } else
778 new_child = node_t::make_path(level - B, tail);
779 try {
780 auto count = new_idx + 1;
781 auto new_parent = node_t::copy_inner_r_n(count, pos.node(), new_idx);
782 auto new_relaxed = new_parent->relaxed();
783 new_parent->inner()[new_idx] = new_child;
784 new_relaxed->d.sizes[new_idx] = pos.size() + ts;
785 new_relaxed->d.count = count;
786 return new_parent;
787 } catch (...) {
788 auto shift = pos.shift();
789 auto size = new_idx == idx ? children + ts : ts;
790 if (shift > BL) {
791 tail->inc();
792 dec_inner(new_child, shift - B, size);
793 }
794 throw;
795 }
796 }
797
798 template <typename Pos, typename... Args>
799 static node_t* visit_regular(Pos&& pos, node_t* tail, Args&&...)
800 {
801 assert((pos.size() & mask<BL>) == 0);
802 auto idx = pos.index(pos.size() - 1);
803 auto new_idx = pos.index(pos.size() + branches<BL> - 1);
804 auto count = new_idx + 1;
805 auto new_parent = node_t::make_inner_n(count);
806 try {
807 new_parent->inner()[new_idx] =
808 idx == new_idx ? pos.last_oh(this_t{}, idx, tail)
809 /* otherwise */ : node_t::make_path(pos.shift() - B, tail);
810 } catch (...) {
811 node_t::delete_inner(new_parent, count);
812 throw;
813 }
814 return node_t::do_copy_inner(new_parent, pos.node(), new_idx);
815 }
816
817 template <typename Pos, typename... Args>
818 static node_t* visit_leaf(Pos&& pos, node_t* tail, Args&&...)
819 { IMMER_UNREACHABLE; }
820};
821
822struct dec_right_visitor : visitor_base<dec_right_visitor>
823{
824 using this_t = dec_right_visitor;
825 using dec_t = dec_visitor;
826
827 template <typename Pos>
828 static void visit_relaxed(Pos&& p, count_t idx)
829 {
830 using node_t = node_type<Pos>;
831 auto node = p.node();
832 if (node->dec()) {
833 p.each_right(dec_t{}, idx);
834 node_t::delete_inner_r(node, p.count());
835 }
836 }
837
838 template <typename Pos>
839 static void visit_regular(Pos&& p, count_t idx)
840 {
841 using node_t = node_type<Pos>;
842 auto node = p.node();
843 if (node->dec()) {
844 p.each_right(dec_t{}, idx);
845 node_t::delete_inner(node, p.count());
846 }
847 }
848
849 template <typename Pos>
850 static void visit_leaf(Pos&& p, count_t idx)
851 { IMMER_UNREACHABLE; }
852};
853
854template <typename NodeT, bool Collapse=true, bool Mutating=true>
855struct slice_right_mut_visitor
856 : visitor_base<slice_right_mut_visitor<NodeT, Collapse, Mutating>>
857{
858 using node_t = NodeT;
859 using this_t = slice_right_mut_visitor;
860 using edit_t = typename NodeT::edit_t;
861
862 // returns a new shift, new root, the new tail size and the new tail
863 using result_t = std::tuple<shift_t, NodeT*, count_t, NodeT*>;
864 using no_collapse_t = slice_right_mut_visitor<NodeT, false, true>;
865 using no_collapse_no_mut_t = slice_right_mut_visitor<NodeT, false, false>;
866 using no_mut_t = slice_right_mut_visitor<NodeT, Collapse, false>;
867
868 static constexpr auto B = NodeT::bits;
869 static constexpr auto BL = NodeT::bits_leaf;
870
871 template <typename PosT>
872 static result_t visit_relaxed(PosT&& pos, size_t last, edit_t e)
873 {
874 auto idx = pos.index(last);
875 auto node = pos.node();
876 auto mutate = Mutating && node->can_mutate(e);
877 if (Collapse && idx == 0) {
878 auto res = mutate
879 ? pos.towards_oh(this_t{}, last, idx, e)
880 : pos.towards_oh(no_mut_t{}, last, idx, e);
881 if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
882 return res;
883 } else {
884 using std::get;
885 auto subs = mutate
886 ? pos.towards_oh(no_collapse_t{}, last, idx, e)
887 : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e);
888 auto next = get<1>(subs);
889 auto ts = get<2>(subs);
890 auto tail = get<3>(subs);
891 try {
892 if (next) {
893 if (mutate) {
894 auto nodr = node->ensure_mutable_relaxed_n(e, idx);
895 pos.each_right(dec_visitor{}, idx + 1);
896 node->inner()[idx] = next;
897 nodr->d.sizes[idx] = last + 1 - ts;
898 nodr->d.count = idx + 1;
899 return std::make_tuple( pos.shift(), node, ts, tail );
900 } else {
901 auto newn = node_t::copy_inner_r_e(e, node, idx);
902 auto newr = newn->relaxed();
903 newn->inner()[idx] = next;
904 newr->d.sizes[idx] = last + 1 - ts;
905 newr->d.count = idx + 1;
906 if (Mutating) pos.visit(dec_visitor{});
907 return std::make_tuple( pos.shift(), newn, ts, tail );
908 }
909 } else if (idx == 0) {
910 if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
911 return std::make_tuple( pos.shift(), nullptr, ts, tail );
912 } else if (Collapse && idx == 1 && pos.shift() > BL) {
913 auto newn = pos.node()->inner()[0];
914 if (!mutate) newn->inc();
915 if (Mutating) pos.visit(dec_right_visitor{}, count_t{2});
916 return std::make_tuple( pos.shift() - B, newn, ts, tail );
917 } else {
918 if (mutate) {
919 pos.each_right(dec_visitor{}, idx + 1);
920 node->ensure_mutable_relaxed_n(e, idx)->d.count = idx;
921 return std::make_tuple( pos.shift(), node, ts, tail );
922 } else {
923 auto newn = node_t::copy_inner_r_e(e, node, idx);
924 if (Mutating) pos.visit(dec_visitor{});
925 return std::make_tuple( pos.shift(), newn, ts, tail );
926 }
927 }
928 } catch (...) {
929 assert(!mutate);
930 assert(!next || pos.shift() > BL);
931 if (next)
932 dec_inner(next, pos.shift() - B,
933 last + 1 - ts - pos.size_before(idx));
934 dec_leaf(tail, ts);
935 throw;
936 }
937 }
938 }
939
940 template <typename PosT>
941 static result_t visit_regular(PosT&& pos, size_t last, edit_t e)
942 {
943 auto idx = pos.index(last);
944 auto node = pos.node();
945 auto mutate = Mutating && node->can_mutate(e);
946 if (Collapse && idx == 0) {
947 auto res = mutate
948 ? pos.towards_oh(this_t{}, last, idx, e)
949 : pos.towards_oh(no_mut_t{}, last, idx, e);
950 if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
951 return res;
952 } else {
953 using std::get;
954 auto subs = mutate
955 ? pos.towards_oh(no_collapse_t{}, last, idx, e)
956 : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e);
957 auto next = get<1>(subs);
958 auto ts = get<2>(subs);
959 auto tail = get<3>(subs);
960 try {
961 if (next) {
962 if (mutate) {
963 node->inner()[idx] = next;
964 pos.each_right(dec_visitor{}, idx + 1);
965 return std::make_tuple( pos.shift(), node, ts, tail );
966 } else {
967 auto newn = node_t::copy_inner_e(e, node, idx);
968 newn->inner()[idx] = next;
969 if (Mutating) pos.visit(dec_visitor{});
970 return std::make_tuple( pos.shift(), newn, ts, tail );
971 }
972 } else if (idx == 0) {
973 if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
974 return std::make_tuple( pos.shift(), nullptr, ts, tail );
975 } else if (Collapse && idx == 1 && pos.shift() > BL) {
976 auto newn = pos.node()->inner()[0];
977 if (!mutate) newn->inc();
978 if (Mutating) pos.visit(dec_right_visitor{}, count_t{2});
979 return std::make_tuple( pos.shift() - B, newn, ts, tail );
980 } else {
981 if (mutate) {
982 pos.each_right(dec_visitor{}, idx + 1);
983 return std::make_tuple( pos.shift(), node, ts, tail );
984 } else {
985 auto newn = node_t::copy_inner_e(e, node, idx);
986 if (Mutating) pos.visit(dec_visitor{});
987 return std::make_tuple( pos.shift(), newn, ts, tail );
988 }
989 }
990 } catch (...) {
991 assert(!mutate);
992 assert(!next || pos.shift() > BL);
993 assert(tail);
994 if (next) dec_regular(next, pos.shift() - B, last + 1 - ts);
995 dec_leaf(tail, ts);
996 throw;
997 }
998 }
999 }
1000
1001 template <typename PosT>
1002 static result_t visit_leaf(PosT&& pos, size_t last, edit_t e)
1003 {
1004 auto old_tail_size = pos.count();
1005 auto new_tail_size = pos.index(last) + 1;
1006 auto node = pos.node();
1007 auto mutate = Mutating && node->can_mutate(e);
1008 if (new_tail_size == old_tail_size) {
1009 if (!Mutating) node->inc();
1010 return std::make_tuple( 0, nullptr, new_tail_size, node );
1011 } else if (mutate) {
1012 destroy_n(node->leaf() + new_tail_size,
1013 old_tail_size - new_tail_size);
1014 return std::make_tuple( 0, nullptr, new_tail_size, node );
1015 } else {
1016 auto new_tail = node_t::copy_leaf_e(e, node, new_tail_size);
1017 if (Mutating) pos.visit(dec_visitor{});
1018 return std::make_tuple( 0, nullptr, new_tail_size, new_tail );
1019 }
1020 }
1021};
1022
1023template <typename NodeT, bool Collapse=true>
1024struct slice_right_visitor : visitor_base<slice_right_visitor<NodeT, Collapse>>
1025{
1026 using node_t = NodeT;
1027 using this_t = slice_right_visitor;
1028
1029 // returns a new shift, new root, the new tail size and the new tail
1030 using result_t = std::tuple<shift_t, NodeT*, count_t, NodeT*>;
1031 using no_collapse_t = slice_right_visitor<NodeT, false>;
1032
1033 static constexpr auto B = NodeT::bits;
1034 static constexpr auto BL = NodeT::bits_leaf;
1035
1036 template <typename PosT>
1037 static result_t visit_relaxed(PosT&& pos, size_t last)
1038 {
1039 auto idx = pos.index(last);
1040 if (Collapse && idx == 0) {
1041 return pos.towards_oh(this_t{}, last, idx);
1042 } else {
1043 using std::get;
1044 auto subs = pos.towards_oh(no_collapse_t{}, last, idx);
1045 auto next = get<1>(subs);
1046 auto ts = get<2>(subs);
1047 auto tail = get<3>(subs);
1048 try {
1049 if (next) {
1050 auto count = idx + 1;
1051 auto newn = node_t::copy_inner_r_n(count, pos.node(), idx);
1052 auto newr = newn->relaxed();
1053 newn->inner()[idx] = next;
1054 newr->d.sizes[idx] = last + 1 - ts;
1055 newr->d.count = count;
1056 return std::make_tuple( pos.shift(), newn, ts, tail );
1057 } else if (idx == 0) {
1058 return std::make_tuple( pos.shift(), nullptr, ts, tail );
1059 } else if (Collapse && idx == 1 && pos.shift() > BL) {
1060 auto newn = pos.node()->inner()[0];
1061 return std::make_tuple( pos.shift() - B, newn->inc(), ts, tail );
1062 } else {
1063 auto newn = node_t::copy_inner_r(pos.node(), idx);
1064 return std::make_tuple( pos.shift(), newn, ts, tail );
1065 }
1066 } catch (...) {
1067 assert(!next || pos.shift() > BL);
1068 if (next) dec_inner(next, pos.shift() - B,
1069 last + 1 - ts - pos.size_before(idx));
1070 if (tail) dec_leaf(tail, ts);
1071 throw;
1072 }
1073 }
1074 }
1075
1076 template <typename PosT>
1077 static result_t visit_regular(PosT&& pos, size_t last)
1078 {
1079 auto idx = pos.index(last);
1080 if (Collapse && idx == 0) {
1081 return pos.towards_oh(this_t{}, last, idx);
1082 } else {
1083 using std::get;
1084 auto subs = pos.towards_oh(no_collapse_t{}, last, idx);
1085 auto next = get<1>(subs);
1086 auto ts = get<2>(subs);
1087 auto tail = get<3>(subs);
1088 try {
1089 if (next) {
1090 auto newn = node_t::copy_inner_n(idx + 1, pos.node(), idx);
1091 newn->inner()[idx] = next;
1092 return std::make_tuple( pos.shift(), newn, ts, tail );
1093 } else if (idx == 0) {
1094 return std::make_tuple( pos.shift(), nullptr, ts, tail );
1095 } else if (Collapse && idx == 1 && pos.shift() > BL) {
1096 auto newn = pos.node()->inner()[0];
1097 return std::make_tuple( pos.shift() - B, newn->inc(), ts, tail );
1098 } else {
1099 auto newn = node_t::copy_inner_n(idx, pos.node(), idx);
1100 return std::make_tuple( pos.shift(), newn, ts, tail );
1101 }
1102 } catch (...) {
1103 assert(!next || pos.shift() > BL);
1104 assert(tail);
1105 if (next) dec_regular(next, pos.shift() - B, last + 1 - ts);
1106 dec_leaf(tail, ts);
1107 throw;
1108 }
1109 }
1110 }
1111
1112 template <typename PosT>
1113 static result_t visit_leaf(PosT&& pos, size_t last)
1114 {
1115 auto old_tail_size = pos.count();
1116 auto new_tail_size = pos.index(last) + 1;
1117 auto new_tail = new_tail_size == old_tail_size
1118 ? pos.node()->inc()
1119 : node_t::copy_leaf(pos.node(), new_tail_size);
1120 return std::make_tuple( 0, nullptr, new_tail_size, new_tail );
1121 }
1122};
1123
1124struct dec_left_visitor : visitor_base<dec_left_visitor>
1125{
1126 using this_t = dec_left_visitor;
1127 using dec_t = dec_visitor;
1128
1129 template <typename Pos>
1130 static void visit_relaxed(Pos&& p, count_t idx)
1131 {
1132 using node_t = node_type<Pos>;
1133 auto node = p.node();
1134 if (node->dec()) {
1135 p.each_left(dec_t{}, idx);
1136 node_t::delete_inner_r(node, p.count());
1137 }
1138 }
1139
1140 template <typename Pos>
1141 static void visit_regular(Pos&& p, count_t idx)
1142 {
1143 using node_t = node_type<Pos>;
1144 auto node = p.node();
1145 if (node->dec()) {
1146 p.each_left(dec_t{}, idx);
1147 node_t::delete_inner(node, p.count());
1148 }
1149 }
1150
1151 template <typename Pos>
1152 static void visit_leaf(Pos&& p, count_t idx)
1153 { IMMER_UNREACHABLE; }
1154};
1155
1156template <typename NodeT, bool Collapse=true, bool Mutating=true>
1157struct slice_left_mut_visitor
1158 : visitor_base<slice_left_mut_visitor<NodeT, Collapse, Mutating>>
1159{
1160 using node_t = NodeT;
1161 using this_t = slice_left_mut_visitor;
1162 using edit_t = typename NodeT::edit_t;
1163 using value_t = typename NodeT::value_t;
1164 using relaxed_t = typename NodeT::relaxed_t;
1165 // returns a new shift and new root
1166 using result_t = std::tuple<shift_t, NodeT*>;
1167
1168 using no_collapse_t = slice_left_mut_visitor<NodeT, false, true>;
1169 using no_collapse_no_mut_t = slice_left_mut_visitor<NodeT, false, false>;
1170 using no_mut_t = slice_left_mut_visitor<NodeT, Collapse, false>;
1171
1172 static constexpr auto B = NodeT::bits;
1173 static constexpr auto BL = NodeT::bits_leaf;
1174
1175 template <typename PosT>
1176 static result_t visit_relaxed(PosT&& pos, size_t first, edit_t e)
1177 {
1178 auto idx = pos.subindex(first);
1179 auto count = pos.count();
1180 auto node = pos.node();
1181 auto mutate = Mutating && node->can_mutate(e);
1182 auto left_size = pos.size_before(idx);
1183 auto child_size = pos.size_sbh(idx, left_size);
1184 auto dropped_size = first;
1185 auto child_dropped_size = dropped_size - left_size;
1186 if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
1187 auto r = mutate
1188 ? pos.towards_sub_oh(this_t{}, first, idx, e)
1189 : pos.towards_sub_oh(no_mut_t{}, first, idx, e);
1190 if (Mutating) pos.visit(dec_left_visitor{}, idx);
1191 return r;
1192 } else {
1193 using std::get;
1194 auto newn = mutate
1195 ? (node->ensure_mutable_relaxed(e), node)
1196 : node_t::make_inner_r_e(e);
1197 auto newr = newn->relaxed();
1198 auto newcount = count - idx;
1199 auto new_child_size = child_size - child_dropped_size;
1200 try {
1201 auto subs = mutate
1202 ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e)
1203 : pos.towards_sub_oh(no_collapse_no_mut_t{}, first, idx, e);
1204 if (mutate) pos.each_left(dec_visitor{}, idx);
1205 pos.copy_sizes(idx + 1, newcount - 1,
1206 new_child_size, newr->d.sizes + 1);
1207 std::uninitialized_copy(node->inner() + idx + 1,
1208 node->inner() + count,
1209 newn->inner() + 1);
1210 newn->inner()[0] = get<1>(subs);
1211 newr->d.sizes[0] = new_child_size;
1212 newr->d.count = newcount;
1213 if (!mutate) {
1214 node_t::inc_nodes(newn->inner() + 1, newcount - 1);
1215 if (Mutating) pos.visit(dec_visitor{});
1216 }
1217 return std::make_tuple( pos.shift(), newn );
1218 } catch (...) {
1219 if (!mutate) node_t::delete_inner_r_e(newn);
1220 throw;
1221 }
1222 }
1223 }
1224
1225 template <typename PosT>
1226 static result_t visit_regular(PosT&& pos, size_t first, edit_t e)
1227 {
1228 auto idx = pos.subindex(first);
1229 auto count = pos.count();
1230 auto node = pos.node();
1231 auto mutate = Mutating
1232 // this is more restrictive than actually needed because
1233 // it causes the algorithm to also avoid mutating the leaf
1234 // in place
1235 && !node_t::embed_relaxed
1236 && node->can_mutate(e);
1237 auto left_size = pos.size_before(idx);
1238 auto child_size = pos.size_sbh(idx, left_size);
1239 auto dropped_size = first;
1240 auto child_dropped_size = dropped_size - left_size;
1241 if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
1242 auto r = mutate
1243 ? pos.towards_sub_oh(this_t{}, first, idx, e)
1244 : pos.towards_sub_oh(no_mut_t{}, first, idx, e);
1245 if (Mutating) pos.visit(dec_left_visitor{}, idx);
1246 return r;
1247 } else {
1248 using std::get;
1249 // if possible, we convert the node to a relaxed one
1250 // simply by allocating a `relaxed_t` size table for
1251 // it... maybe some of this magic should be moved as a
1252 // `node<...>` static method...
1253 auto newcount = count - idx;
1254 auto newn = mutate
1255 ? (node->impl.d.data.inner.relaxed = new (
1256 node_t::heap::allocate(
1257 node_t::max_sizeof_relaxed,
1258 norefs_tag{})) relaxed_t,
1259 node)
1260 : node_t::make_inner_r_e(e);
1261 auto newr = newn->relaxed();
1262 try {
1263 auto subs = mutate
1264 ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e)
1265 : pos.towards_sub_oh(no_collapse_no_mut_t{}, first, idx, e);
1266 if (mutate) pos.each_left(dec_visitor{}, idx);
1267 newr->d.sizes[0] = child_size - child_dropped_size;
1268 pos.copy_sizes(idx + 1, newcount - 1,
1269 newr->d.sizes[0], newr->d.sizes + 1);
1270 newr->d.count = newcount;
1271 newn->inner()[0] = get<1>(subs);
1272 std::uninitialized_copy(node->inner() + idx + 1,
1273 node->inner() + count,
1274 newn->inner() + 1);
1275 if (!mutate) {
1276 node_t::inc_nodes(newn->inner() + 1, newcount - 1);
1277 if (Mutating) pos.visit(dec_visitor{});
1278 }
1279 return std::make_tuple( pos.shift(), newn );
1280 } catch (...) {
1281 if (!mutate) node_t::delete_inner_r_e(newn);
1282 else {
1283 // restore the regular node that we were
1284 // attempting to relax...
1285 node_t::heap::deallocate(node_t::max_sizeof_relaxed,
1286 node->impl.d.data.inner.relaxed);
1287 node->impl.d.data.inner.relaxed = nullptr;
1288 }
1289 throw;
1290 }
1291 }
1292 }
1293
1294 template <typename PosT>
1295 static result_t visit_leaf(PosT&& pos, size_t first, edit_t e)
1296 {
1297 auto node = pos.node();
1298 auto idx = pos.index(first);
1299 auto count = pos.count();
1300 auto mutate = Mutating
1301 && std::is_nothrow_move_constructible<value_t>::value
1302 && node->can_mutate(e);
1303 if (mutate) {
1304 auto data = node->leaf();
1305 auto newcount = count - idx;
1306 std::move(data + idx, data + count, data);
1307 destroy_n(data + newcount, idx);
1308 return std::make_tuple( 0, node );
1309 } else {
1310 auto newn = node_t::copy_leaf_e(e, node, idx, count);
1311 if (Mutating) pos.visit(dec_visitor{});
1312 return std::make_tuple( 0, newn );
1313 }
1314 }
1315};
1316
1317template <typename NodeT, bool Collapse=true>
1318struct slice_left_visitor : visitor_base<slice_left_visitor<NodeT, Collapse>>
1319{
1320 using node_t = NodeT;
1321 using this_t = slice_left_visitor;
1322
1323 // returns a new shift and new root
1324 using result_t = std::tuple<shift_t, NodeT*>;
1325 using no_collapse_t = slice_left_visitor<NodeT, false>;
1326
1327 static constexpr auto B = NodeT::bits;
1328 static constexpr auto BL = NodeT::bits_leaf;
1329
1330 template <typename PosT>
1331 static result_t visit_inner(PosT&& pos, size_t first)
1332 {
1333 auto idx = pos.subindex(first);
1334 auto count = pos.count();
1335 auto left_size = pos.size_before(idx);
1336 auto child_size = pos.size_sbh(idx, left_size);
1337 auto dropped_size = first;
1338 auto child_dropped_size = dropped_size - left_size;
1339 if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
1340 return pos.towards_sub_oh(this_t{}, first, idx);
1341 } else {
1342 using std::get;
1343 auto n = pos.node();
1344 auto newc = count - idx;
1345 auto newn = node_t::make_inner_r_n(newc);
1346 try {
1347 auto subs = pos.towards_sub_oh(no_collapse_t{}, first, idx);
1348 auto newr = newn->relaxed();
1349 newr->d.count = count - idx;
1350 newr->d.sizes[0] = child_size - child_dropped_size;
1351 pos.copy_sizes(idx + 1, newr->d.count - 1,
1352 newr->d.sizes[0], newr->d.sizes + 1);
1353 assert(newr->d.sizes[newr->d.count - 1] == pos.size() - dropped_size);
1354 newn->inner()[0] = get<1>(subs);
1355 std::uninitialized_copy(n->inner() + idx + 1,
1356 n->inner() + count,
1357 newn->inner() + 1);
1358 node_t::inc_nodes(newn->inner() + 1, newr->d.count - 1);
1359 return std::make_tuple( pos.shift(), newn );
1360 } catch (...) {
1361 node_t::delete_inner_r(newn, newc);
1362 throw;
1363 }
1364 }
1365 }
1366
1367 template <typename PosT>
1368 static result_t visit_leaf(PosT&& pos, size_t first)
1369 {
1370 auto n = node_t::copy_leaf(pos.node(), pos.index(first), pos.count());
1371 return std::make_tuple( 0, n );
1372 }
1373};
1374
1375template <typename Node>
1376struct concat_center_pos
1377{
1378 static constexpr auto B = Node::bits;
1379 static constexpr auto BL = Node::bits_leaf;
1380
1381 static constexpr count_t max_children = 3;
1382
1383 using node_t = Node;
1384 using edit_t = typename Node::edit_t;
1385
1386 shift_t shift_ = 0u;
1387 count_t count_ = 0u;
1388 node_t* nodes_[max_children];
1389 size_t sizes_[max_children];
1390
1391 auto shift() const { return shift_; }
1392
1393 concat_center_pos(shift_t s,
1394 Node* n0, size_t s0)
1395 : shift_{s}, count_{1}, nodes_{n0}, sizes_{s0} {}
1396
1397 concat_center_pos(shift_t s,
1398 Node* n0, size_t s0,
1399 Node* n1, size_t s1)
1400 : shift_{s}, count_{2}, nodes_{n0, n1}, sizes_{s0, s1} {}
1401
1402 concat_center_pos(shift_t s,
1403 Node* n0, size_t s0,
1404 Node* n1, size_t s1,
1405 Node* n2, size_t s2)
1406 : shift_{s}, count_{3}, nodes_{n0, n1, n2}, sizes_{s0, s1, s2} {}
1407
1408 template <typename Visitor, typename... Args>
1409 void each_sub(Visitor v, Args&& ...args)
1410 {
1411 if (shift_ == BL) {
1412 for (auto i = count_t{0}; i < count_; ++i)
1413 make_leaf_sub_pos(nodes_[i], sizes_[i]).visit(v, args...);
1414 } else {
1415 for (auto i = count_t{0}; i < count_; ++i)
1416 make_relaxed_pos(nodes_[i], shift_ - B, nodes_[i]->relaxed()).visit(v, args...);
1417 }
1418 }
1419
1420 relaxed_pos<Node> realize() &&
1421 {
1422 if (count_ > 1) {
1423 try {
1424 auto result = node_t::make_inner_r_n(count_);
1425 auto r = result->relaxed();
1426 r->d.count = count_;
1427 std::copy(nodes_, nodes_ + count_, result->inner());
1428 std::copy(sizes_, sizes_ + count_, r->d.sizes);
1429 return { result, shift_, r };
1430 } catch (...) {
1431 each_sub(dec_visitor{});
1432 throw;
1433 }
1434 } else {
1435 assert(shift_ >= B + BL);
1436 return { nodes_[0], shift_ - B, nodes_[0]->relaxed() };
1437 }
1438 }
1439
1440 relaxed_pos<Node> realize_e(edit_t e)
1441 {
1442 if (count_ > 1) {
1443 auto result = node_t::make_inner_r_e(e);
1444 auto r = result->relaxed();
1445 r->d.count = count_;
1446 std::copy(nodes_, nodes_ + count_, result->inner());
1447 std::copy(sizes_, sizes_ + count_, r->d.sizes);
1448 return { result, shift_, r };
1449 } else {
1450 assert(shift_ >= B + BL);
1451 return { nodes_[0], shift_ - B, nodes_[0]->relaxed() };
1452 }
1453 }
1454};
1455
1456template <typename Node>
1457struct concat_merger
1458{
1459 using node_t = Node;
1460 static constexpr auto B = Node::bits;
1461 static constexpr auto BL = Node::bits_leaf;
1462
1463 using result_t = concat_center_pos<Node>;
1464
1465 count_t* curr_;
1466 count_t n_;
1467 result_t result_;
1468
1469 concat_merger(shift_t shift, count_t* counts, count_t n)
1470 : curr_{counts}
1471 , n_{n}
1472 , result_{shift + B, node_t::make_inner_r_n(std::min(n_, branches<B>)), 0}
1473 {}
1474
1475 node_t* to_ = {};
1476 count_t to_offset_ = {};
1477 size_t to_size_ = {};
1478
1479 void add_child(node_t* p, size_t size)
1480 {
1481 ++curr_;
1482 auto parent = result_.nodes_[result_.count_ - 1];
1483 auto relaxed = parent->relaxed();
1484 if (relaxed->d.count == branches<B>) {
1485 assert(result_.count_ < result_t::max_children);
1486 n_ -= branches<B>;
1487 parent = node_t::make_inner_r_n(std::min(n_, branches<B>));
1488 relaxed = parent->relaxed();
1489 result_.nodes_[result_.count_] = parent;
1490 result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1];
1491 ++result_.count_;
1492 }
1493 auto idx = relaxed->d.count++;
1494 result_.sizes_[result_.count_ - 1] += size;
1495 relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0);
1496 parent->inner() [idx] = p;
1497 };
1498
1499 template <typename Pos>
1500 void merge_leaf(Pos&& p)
1501 {
1502 auto from = p.node();
1503 auto from_size = p.size();
1504 auto from_count = p.count();
1505 assert(from_size);
1506 if (!to_ && *curr_ == from_count) {
1507 add_child(from, from_size);
1508 from->inc();
1509 } else {
1510 auto from_offset = count_t{};
1511 auto from_data = from->leaf();
1512 do {
1513 if (!to_) {
1514 to_ = node_t::make_leaf_n(*curr_);
1515 to_offset_ = 0;
1516 }
1517 auto data = to_->leaf();
1518 auto to_copy = std::min(from_count - from_offset,
1519 *curr_ - to_offset_);
1520 std::uninitialized_copy(from_data + from_offset,
1521 from_data + from_offset + to_copy,
1522 data + to_offset_);
1523 to_offset_ += to_copy;
1524 from_offset += to_copy;
1525 if (*curr_ == to_offset_) {
1526 add_child(to_, to_offset_);
1527 to_ = nullptr;
1528 }
1529 } while (from_offset != from_count);
1530 }
1531 }
1532
1533 template <typename Pos>
1534 void merge_inner(Pos&& p)
1535 {
1536 auto from = p.node();
1537 auto from_size = p.size();
1538 auto from_count = p.count();
1539 assert(from_size);
1540 if (!to_ && *curr_ == from_count) {
1541 add_child(from, from_size);
1542 from->inc();
1543 } else {
1544 auto from_offset = count_t{};
1545 auto from_data = from->inner();
1546 do {
1547 if (!to_) {
1548 to_ = node_t::make_inner_r_n(*curr_);
1549 to_offset_ = 0;
1550 to_size_ = 0;
1551 }
1552 auto data = to_->inner();
1553 auto to_copy = std::min(from_count - from_offset,
1554 *curr_ - to_offset_);
1555 std::uninitialized_copy(from_data + from_offset,
1556 from_data + from_offset + to_copy,
1557 data + to_offset_);
1558 node_t::inc_nodes(from_data + from_offset, to_copy);
1559 auto sizes = to_->relaxed()->d.sizes;
1560 p.copy_sizes(from_offset, to_copy,
1561 to_size_, sizes + to_offset_);
1562 to_offset_ += to_copy;
1563 from_offset += to_copy;
1564 to_size_ = sizes[to_offset_ - 1];
1565 if (*curr_ == to_offset_) {
1566 to_->relaxed()->d.count = to_offset_;
1567 add_child(to_, to_size_);
1568 to_ = nullptr;
1569 }
1570 } while (from_offset != from_count);
1571 }
1572 }
1573
1574 concat_center_pos<Node> finish() const
1575 {
1576 assert(!to_);
1577 return result_;
1578 }
1579
1580 void abort()
1581 {
1582 auto shift = result_.shift_ - B;
1583 if (to_) {
1584 if (shift == BL)
1585 node_t::delete_leaf(to_, to_offset_);
1586 else {
1587 to_->relaxed()->d.count = to_offset_;
1588 dec_relaxed(to_, shift - B);
1589 }
1590 }
1591 result_.each_sub(dec_visitor());
1592 }
1593};
1594
1595struct concat_merger_visitor : visitor_base<concat_merger_visitor>
1596{
1597 using this_t = concat_merger_visitor;
1598
1599 template <typename Pos, typename Merger>
1600 static void visit_inner(Pos&& p, Merger& merger)
1601 { merger.merge_inner(p); }
1602
1603 template <typename Pos, typename Merger>
1604 static void visit_leaf(Pos&& p, Merger& merger)
1605 { merger.merge_leaf(p); }
1606};
1607
1608struct concat_rebalance_plan_fill_visitor
1609 : visitor_base<concat_rebalance_plan_fill_visitor>
1610{
1611 using this_t = concat_rebalance_plan_fill_visitor;
1612
1613 template <typename Pos, typename Plan>
1614 static void visit_node(Pos&& p, Plan& plan)
1615 {
1616 auto count = p.count();
1617 assert(plan.n < Plan::max_children);
1618 plan.counts[plan.n++] = count;
1619 plan.total += count;
1620 }
1621};
1622
1623template <bits_t B, bits_t BL>
1624struct concat_rebalance_plan
1625{
1626 static constexpr auto max_children = 2 * branches<B> + 1;
1627
1628 count_t counts [max_children];
1629 count_t n = 0u;
1630 count_t total = 0u;
1631
1632 template <typename LPos, typename CPos, typename RPos>
1633 void fill(LPos&& lpos, CPos&& cpos, RPos&& rpos)
1634 {
1635 assert(n == 0u);
1636 assert(total == 0u);
1637 using visitor_t = concat_rebalance_plan_fill_visitor;
1638 lpos.each_left_sub(visitor_t{}, *this);
1639 cpos.each_sub(visitor_t{}, *this);
1640 rpos.each_right_sub(visitor_t{}, *this);
1641 }
1642
1643 void shuffle(shift_t shift)
1644 {
1645 // gcc seems to not really understand this code... :(
1646#if !defined(_MSC_VER)
1647#pragma GCC diagnostic push
1648#pragma GCC diagnostic ignored "-Warray-bounds"
1649#endif
1650 constexpr count_t rrb_extras = 2;
1651 constexpr count_t rrb_invariant = 1;
1652 const auto bits = shift == BL ? BL : B;
1653 const auto branches = count_t{1} << bits;
1654 const auto optimal = ((total - 1) >> bits) + 1;
1655 count_t i = 0;
1656 while (n >= optimal + rrb_extras) {
1657 // skip ok nodes
1658 while (counts[i] > branches - rrb_invariant) i++;
1659 // short node, redistribute
1660 auto remaining = counts[i];
1661 do {
1662 auto count = std::min(remaining + counts[i+1], branches);
1663 counts[i] = count;
1664 remaining += counts[i + 1] - count;
1665 ++i;
1666 } while (remaining > 0);
1667 // remove node
1668 std::move(counts + i + 1, counts + n, counts + i);
1669 --n;
1670 --i;
1671 }
1672#if !defined(_MSC_VER)
1673#pragma GCC diagnostic pop
1674#endif
1675 }
1676
1677 template <typename LPos, typename CPos, typename RPos>
1678 concat_center_pos<node_type<CPos>>
1679 merge(LPos&& lpos, CPos&& cpos, RPos&& rpos)
1680 {
1681 using node_t = node_type<CPos>;
1682 using merger_t = concat_merger<node_t>;
1683 using visitor_t = concat_merger_visitor;
1684 auto merger = merger_t{cpos.shift(), counts, n};
1685 try {
1686 lpos.each_left_sub(visitor_t{}, merger);
1687 cpos.each_sub(visitor_t{}, merger);
1688 rpos.each_right_sub(visitor_t{}, merger);
1689 cpos.each_sub(dec_visitor{});
1690 return merger.finish();
1691 } catch (...) {
1692 merger.abort();
1693 throw;
1694 }
1695 }
1696};
1697
1698template <typename Node, typename LPos, typename CPos, typename RPos>
1699concat_center_pos<Node>
1700concat_rebalance(LPos&& lpos, CPos&& cpos, RPos&& rpos)
1701{
1702 auto plan = concat_rebalance_plan<Node::bits, Node::bits_leaf>{};
1703 plan.fill(lpos, cpos, rpos);
1704 plan.shuffle(cpos.shift());
1705 try {
1706 return plan.merge(lpos, cpos, rpos);
1707 } catch (...) {
1708 cpos.each_sub(dec_visitor{});
1709 throw;
1710 }
1711}
1712
1713template <typename Node, typename LPos, typename TPos, typename RPos>
1714concat_center_pos<Node>
1715concat_leafs(LPos&& lpos, TPos&& tpos, RPos&& rpos)
1716{
1717 static_assert(Node::bits >= 2, "");
1718 assert(lpos.shift() == tpos.shift());
1719 assert(lpos.shift() == rpos.shift());
1720 assert(lpos.shift() == 0);
1721 if (tpos.count() > 0)
1722 return {
1723 Node::bits_leaf,
1724 lpos.node()->inc(), lpos.count(),
1725 tpos.node()->inc(), tpos.count(),
1726 rpos.node()->inc(), rpos.count(),
1727 };
1728 else
1729 return {
1730 Node::bits_leaf,
1731 lpos.node()->inc(), lpos.count(),
1732 rpos.node()->inc(), rpos.count(),
1733 };
1734}
1735
1736template <typename Node>
1737struct concat_left_visitor;
1738template <typename Node>
1739struct concat_right_visitor;
1740template <typename Node>
1741struct concat_both_visitor;
1742
1743template <typename Node, typename LPos, typename TPos, typename RPos>
1744concat_center_pos<Node>
1745concat_inners(LPos&& lpos, TPos&& tpos, RPos&& rpos)
1746{
1747 auto lshift = lpos.shift();
1748 auto rshift = rpos.shift();
1749 if (lshift > rshift) {
1750 auto cpos = lpos.last_sub(concat_left_visitor<Node>{}, tpos, rpos);
1751 return concat_rebalance<Node>(lpos, cpos, null_sub_pos{});
1752 } else if (lshift < rshift) {
1753 auto cpos = rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos);
1754 return concat_rebalance<Node>(null_sub_pos{}, cpos, rpos);
1755 } else {
1756 assert(lshift == rshift);
1757 assert(Node::bits_leaf == 0u || lshift > 0);
1758 auto cpos = lpos.last_sub(concat_both_visitor<Node>{}, tpos, rpos);
1759 return concat_rebalance<Node>(lpos, cpos, rpos);
1760 }
1761}
1762
1763template <typename Node>
1764struct concat_left_visitor : visitor_base<concat_left_visitor<Node>>
1765{
1766 using this_t = concat_left_visitor;
1767
1768 template <typename LPos, typename TPos, typename RPos>
1769 static concat_center_pos<Node>
1770 visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos)
1771 { return concat_inners<Node>(lpos, tpos, rpos); }
1772
1773 template <typename LPos, typename TPos, typename RPos>
1774 static concat_center_pos<Node>
1775 visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos)
1776 { IMMER_UNREACHABLE; }
1777};
1778
1779template <typename Node>
1780struct concat_right_visitor : visitor_base<concat_right_visitor<Node>>
1781{
1782 using this_t = concat_right_visitor;
1783
1784 template <typename RPos, typename LPos, typename TPos>
1785 static concat_center_pos<Node>
1786 visit_inner(RPos&& rpos, LPos&& lpos, TPos&& tpos)
1787 { return concat_inners<Node>(lpos, tpos, rpos); }
1788
1789 template <typename RPos, typename LPos, typename TPos>
1790 static concat_center_pos<Node>
1791 visit_leaf(RPos&& rpos, LPos&& lpos, TPos&& tpos)
1792 { return concat_leafs<Node>(lpos, tpos, rpos); }
1793};
1794
1795template <typename Node>
1796struct concat_both_visitor
1797 : visitor_base<concat_both_visitor<Node>>
1798{
1799 using this_t = concat_both_visitor;
1800
1801 template <typename LPos, typename TPos, typename RPos>
1802 static concat_center_pos<Node>
1803 visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos)
1804 { return rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos); }
1805
1806 template <typename LPos, typename TPos, typename RPos>
1807 static concat_center_pos<Node>
1808 visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos)
1809 { return rpos.first_sub_leaf(concat_right_visitor<Node>{}, lpos, tpos); }
1810};
1811
1812template <typename Node>
1813struct concat_trees_right_visitor
1814 : visitor_base<concat_trees_right_visitor<Node>>
1815{
1816 using this_t = concat_trees_right_visitor;
1817
1818 template <typename RPos, typename LPos, typename TPos>
1819 static concat_center_pos<Node>
1820 visit_node(RPos&& rpos, LPos&& lpos, TPos&& tpos)
1821 { return concat_inners<Node>(lpos, tpos, rpos); }
1822};
1823
1824template <typename Node>
1825struct concat_trees_left_visitor
1826 : visitor_base<concat_trees_left_visitor<Node>>
1827{
1828 using this_t = concat_trees_left_visitor;
1829
1830 template <typename LPos, typename TPos, typename... Args>
1831 static concat_center_pos<Node>
1832 visit_node(LPos&& lpos, TPos&& tpos, Args&& ...args)
1833 { return visit_maybe_relaxed_sub(
1834 args...,
1835 concat_trees_right_visitor<Node>{},
1836 lpos, tpos); }
1837};
1838
1839template <typename Node>
1840relaxed_pos<Node>
1841concat_trees(Node* lroot, shift_t lshift, size_t lsize,
1842 Node* ltail, count_t ltcount,
1843 Node* rroot, shift_t rshift, size_t rsize)
1844{
1845 return visit_maybe_relaxed_sub(
1846 lroot, lshift, lsize,
1847 concat_trees_left_visitor<Node>{},
1848 make_leaf_pos(ltail, ltcount),
1849 rroot, rshift, rsize)
1850 .realize();
1851}
1852
1853template <typename Node>
1854relaxed_pos<Node>
1855concat_trees(Node* ltail, count_t ltcount,
1856 Node* rroot, shift_t rshift, size_t rsize)
1857{
1858 return make_singleton_regular_sub_pos(ltail, ltcount).visit(
1859 concat_trees_left_visitor<Node>{},
1860 empty_leaf_pos<Node>{},
1861 rroot, rshift, rsize)
1862 .realize();
1863}
1864
1865template <typename Node>
1866using concat_center_mut_pos = concat_center_pos<Node>;
1867
1868template <typename Node>
1869struct concat_merger_mut
1870{
1871 using node_t = Node;
1872 using edit_t = typename Node::edit_t;
1873
1874 static constexpr auto B = Node::bits;
1875 static constexpr auto BL = Node::bits_leaf;
1876
1877 using result_t = concat_center_pos<Node>;
1878
1879 edit_t ec_ = {};
1880
1881 count_t* curr_;
1882 count_t n_;
1883 result_t result_;
1884 count_t count_ = 0;
1885 node_t* candidate_ = nullptr;
1886 edit_t candidate_e_ = Node::memory::transience_t::noone;
1887
1888 concat_merger_mut(edit_t ec, shift_t shift,
1889 count_t* counts, count_t n,
1890 edit_t candidate_e, node_t* candidate)
1891 : ec_{ec}
1892 , curr_{counts}
1893 , n_{n}
1894 , result_{shift + B, nullptr, 0}
1895 {
1896 if (candidate) {
1897 candidate->ensure_mutable_relaxed_e(candidate_e, ec);
1898 result_.nodes_[0] = candidate;
1899 } else {
1900 result_.nodes_[0] = node_t::make_inner_r_e(ec);
1901 }
1902 }
1903
1904 node_t* to_ = {};
1905 count_t to_offset_ = {};
1906 size_t to_size_ = {};
1907
1908 void set_candidate(edit_t candidate_e, node_t* candidate)
1909 { candidate_ = candidate; candidate_e_ = candidate_e; }
1910
1911 void add_child(node_t* p, size_t size)
1912 {
1913 ++curr_;
1914 auto parent = result_.nodes_[result_.count_ - 1];
1915 auto relaxed = parent->relaxed();
1916 if (count_ == branches<B>) {
1917 parent->relaxed()->d.count = count_;
1918 assert(result_.count_ < result_t::max_children);
1919 n_ -= branches<B>;
1920 if (candidate_) {
1921 parent = candidate_;
1922 parent->ensure_mutable_relaxed_e(candidate_e_, ec_);
1923 candidate_ = nullptr;
1924 } else
1925 parent = node_t::make_inner_r_e(ec_);
1926 count_ = 0;
1927 relaxed = parent->relaxed();
1928 result_.nodes_[result_.count_] = parent;
1929 result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1];
1930 ++result_.count_;
1931 }
1932 auto idx = count_++;
1933 result_.sizes_[result_.count_ - 1] += size;
1934 relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0);
1935 parent->inner() [idx] = p;
1936 };
1937
1938 template <typename Pos>
1939 void merge_leaf(Pos&& p, edit_t e)
1940 {
1941 auto from = p.node();
1942 auto from_size = p.size();
1943 auto from_count = p.count();
1944 assert(from_size);
1945 if (!to_ && *curr_ == from_count) {
1946 add_child(from, from_size);
1947 } else {
1948 auto from_offset = count_t{};
1949 auto from_data = from->leaf();
1950 auto from_mutate = from->can_mutate(e);
1951 do {
1952 if (!to_) {
1953 if (from_mutate) {
1954 node_t::ownee(from) = ec_;
1955 to_ = from->inc();
1956 assert(from_count);
1957 } else {
1958 to_ = node_t::make_leaf_e(ec_);
1959 }
1960 to_offset_ = 0;
1961 }
1962 auto data = to_->leaf();
1963 auto to_copy = std::min(from_count - from_offset,
1964 *curr_ - to_offset_);
1965 if (from == to_) {
1966 if (from_offset != to_offset_)
1967 std::move(from_data + from_offset,
1968 from_data + from_offset + to_copy,
1969 data + to_offset_);
1970 } else {
1971 if (!from_mutate)
1972 std::uninitialized_copy(from_data + from_offset,
1973 from_data + from_offset + to_copy,
1974 data + to_offset_);
1975 else
1976 detail::uninitialized_move(from_data + from_offset,
1977 from_data + from_offset + to_copy,
1978 data + to_offset_);
1979 }
1980 to_offset_ += to_copy;
1981 from_offset += to_copy;
1982 if (*curr_ == to_offset_) {
1983 add_child(to_, to_offset_);
1984 to_ = nullptr;
1985 }
1986 } while (from_offset != from_count);
1987 }
1988 }
1989
1990 template <typename Pos>
1991 void merge_inner(Pos&& p, edit_t e)
1992 {
1993 auto from = p.node();
1994 auto from_size = p.size();
1995 auto from_count = p.count();
1996 assert(from_size);
1997 if (!to_ && *curr_ == from_count) {
1998 add_child(from, from_size);
1999 } else {
2000 auto from_offset = count_t{};
2001 auto from_data = from->inner();
2002 auto from_mutate = from->can_relax() && from->can_mutate(e);
2003 do {
2004 if (!to_) {
2005 if (from_mutate) {
2006 node_t::ownee(from) = ec_;
2007 from->ensure_mutable_relaxed_e(e, ec_);
2008 to_ = from;
2009 } else {
2010 to_ = node_t::make_inner_r_e(ec_);
2011 }
2012 to_offset_ = 0;
2013 to_size_ = 0;
2014 }
2015 auto data = to_->inner();
2016 auto to_copy = std::min(from_count - from_offset,
2017 *curr_ - to_offset_);
2018 auto sizes = to_->relaxed()->d.sizes;
2019 if (from != to_ || from_offset != to_offset_) {
2020 std::copy(from_data + from_offset,
2021 from_data + from_offset + to_copy,
2022 data + to_offset_);
2023 p.copy_sizes(from_offset, to_copy,
2024 to_size_, sizes + to_offset_);
2025 }
2026 to_offset_ += to_copy;
2027 from_offset += to_copy;
2028 to_size_ = sizes[to_offset_ - 1];
2029 if (*curr_ == to_offset_) {
2030 to_->relaxed()->d.count = to_offset_;
2031 add_child(to_, to_size_);
2032 to_ = nullptr;
2033 }
2034 } while (from_offset != from_count);
2035 }
2036 }
2037
2038 concat_center_pos<Node> finish() const
2039 {
2040 assert(!to_);
2041 result_.nodes_[result_.count_ - 1]->relaxed()->d.count = count_;
2042 return result_;
2043 }
2044
2045 void abort()
2046 {
2047 // We may have mutated stuff the tree in place, leaving
2048 // everything in a corrupted state... It should be possible
2049 // to define cleanup properly, but that is a task for some
2050 // other day... ;)
2051 std::terminate();
2052 }
2053};
2054
2055struct concat_merger_mut_visitor : visitor_base<concat_merger_mut_visitor>
2056{
2057 using this_t = concat_merger_mut_visitor;
2058
2059 template <typename Pos, typename Merger>
2060 static void visit_inner(Pos&& p,
2061 Merger& merger, edit_type<Pos> e)
2062 { merger.merge_inner(p, e); }
2063
2064 template <typename Pos, typename Merger>
2065 static void visit_leaf(Pos&& p,
2066 Merger& merger, edit_type<Pos> e)
2067 { merger.merge_leaf(p, e); }
2068};
2069
2070template <bits_t B, bits_t BL>
2071struct concat_rebalance_plan_mut : concat_rebalance_plan<B, BL>
2072{
2073 using this_t = concat_rebalance_plan_mut;
2074
2075 template <typename LPos, typename CPos, typename RPos>
2076 concat_center_mut_pos<node_type<CPos>>
2077 merge(edit_type<CPos> ec,
2078 edit_type<CPos> el, LPos&& lpos, CPos&& cpos,
2079 edit_type<CPos> er, RPos&& rpos)
2080 {
2081 using node_t = node_type<CPos>;
2082 using merger_t = concat_merger_mut<node_t>;
2083 using visitor_t = concat_merger_mut_visitor;
2084 auto lnode = ((node_t*)lpos.node());
2085 auto rnode = ((node_t*)rpos.node());
2086 auto lmut2 = lnode && lnode->can_relax() && lnode->can_mutate(el);
2087 auto rmut2 = rnode && rnode->can_relax() && rnode->can_mutate(er);
2088 auto merger = merger_t{
2089 ec, cpos.shift(), this->counts, this->n,
2090 el, lmut2 ? lnode : nullptr
2091 };
2092 try {
2093 lpos.each_left_sub(visitor_t{}, merger, el);
2094 cpos.each_sub(visitor_t{}, merger, ec);
2095 if (rmut2) merger.set_candidate(er, rnode);
2096 rpos.each_right_sub(visitor_t{}, merger, er);
2097 return merger.finish();
2098 } catch (...) {
2099 merger.abort();
2100 throw;
2101 }
2102 }
2103};
2104
2105template <typename Node, typename LPos, typename CPos, typename RPos>
2106concat_center_pos<Node>
2107concat_rebalance_mut(edit_type<Node> ec,
2108 edit_type<Node> el, LPos&& lpos, CPos&& cpos,
2109 edit_type<Node> er, RPos&& rpos)
2110{
2111 auto plan = concat_rebalance_plan_mut<Node::bits, Node::bits_leaf>{};
2112 plan.fill(lpos, cpos, rpos);
2113 plan.shuffle(cpos.shift());
2114 return plan.merge(ec, el, lpos, cpos, er, rpos);
2115}
2116
2117template <typename Node, typename LPos, typename TPos, typename RPos>
2118concat_center_mut_pos<Node>
2119concat_leafs_mut(edit_type<Node> ec,
2120 edit_type<Node> el, LPos&& lpos, TPos&& tpos,
2121 edit_type<Node> er, RPos&& rpos)
2122{
2123 static_assert(Node::bits >= 2, "");
2124 assert(lpos.shift() == tpos.shift());
2125 assert(lpos.shift() == rpos.shift());
2126 assert(lpos.shift() == 0);
2127 if (tpos.count() > 0)
2128 return {
2129 Node::bits_leaf,
2130 lpos.node(), lpos.count(),
2131 tpos.node(), tpos.count(),
2132 rpos.node(), rpos.count(),
2133 };
2134 else
2135 return {
2136 Node::bits_leaf,
2137 lpos.node(), lpos.count(),
2138 rpos.node(), rpos.count(),
2139 };
2140}
2141
2142template <typename Node>
2143struct concat_left_mut_visitor;
2144template <typename Node>
2145struct concat_right_mut_visitor;
2146template <typename Node>
2147struct concat_both_mut_visitor;
2148
2149template <typename Node, typename LPos, typename TPos, typename RPos>
2150concat_center_mut_pos<Node>
2151concat_inners_mut(edit_type<Node> ec,
2152 edit_type<Node> el, LPos&& lpos, TPos&& tpos,
2153 edit_type<Node> er, RPos&& rpos)
2154{
2155 auto lshift = lpos.shift();
2156 auto rshift = rpos.shift();
2157 // lpos.node() can be null it is a singleton_regular_sub_pos<...>,
2158 // this is, when the tree is just a tail...
2159 if (lshift > rshift) {
2160 auto cpos = lpos.last_sub(concat_left_mut_visitor<Node>{},
2161 ec, el, tpos, er, rpos);
2162 return concat_rebalance_mut<Node>(ec,
2163 el, lpos, cpos,
2164 er, null_sub_pos{});
2165 } else if (lshift < rshift) {
2166 auto cpos = rpos.first_sub(concat_right_mut_visitor<Node>{},
2167 ec, el, lpos, tpos, er);
2168 return concat_rebalance_mut<Node>(ec,
2169 el, null_sub_pos{}, cpos,
2170 er, rpos);
2171 } else {
2172 assert(lshift == rshift);
2173 assert(Node::bits_leaf == 0u || lshift > 0);
2174 auto cpos = lpos.last_sub(concat_both_mut_visitor<Node>{},
2175 ec, el, tpos, er, rpos);
2176 return concat_rebalance_mut<Node>(ec,
2177 el, lpos, cpos,
2178 er, rpos);
2179 }
2180}
2181
2182template <typename Node>
2183struct concat_left_mut_visitor : visitor_base<concat_left_mut_visitor<Node>>
2184{
2185 using this_t = concat_left_mut_visitor;
2186 using edit_t = typename Node::edit_t;
2187
2188 template <typename LPos, typename TPos, typename RPos>
2189 static concat_center_mut_pos<Node>
2190 visit_inner(LPos&& lpos, edit_t ec,
2191 edit_t el, TPos&& tpos,
2192 edit_t er, RPos&& rpos)
2193 { return concat_inners_mut<Node>(
2194 ec, el, lpos, tpos, er, rpos); }
2195
2196 template <typename LPos, typename TPos, typename RPos>
2197 static concat_center_mut_pos<Node>
2198 visit_leaf(LPos&& lpos, edit_t ec,
2199 edit_t el, TPos&& tpos,
2200 edit_t er, RPos&& rpos)
2201 { IMMER_UNREACHABLE; }
2202};
2203
2204template <typename Node>
2205struct concat_right_mut_visitor
2206 : visitor_base<concat_right_mut_visitor<Node>>
2207{
2208 using this_t = concat_right_mut_visitor;
2209 using edit_t = typename Node::edit_t;
2210
2211 template <typename RPos, typename LPos, typename TPos>
2212 static concat_center_mut_pos<Node>
2213 visit_inner(RPos&& rpos, edit_t ec,
2214 edit_t el, LPos&& lpos, TPos&& tpos,
2215 edit_t er)
2216 { return concat_inners_mut<Node>(
2217 ec, el, lpos, tpos, er, rpos); }
2218
2219 template <typename RPos, typename LPos, typename TPos>
2220 static concat_center_mut_pos<Node>
2221 visit_leaf(RPos&& rpos, edit_t ec,
2222 edit_t el, LPos&& lpos, TPos&& tpos,
2223 edit_t er)
2224 { return concat_leafs_mut<Node>(
2225 ec, el, lpos, tpos, er, rpos); }
2226};
2227
2228template <typename Node>
2229struct concat_both_mut_visitor
2230 : visitor_base<concat_both_mut_visitor<Node>>
2231{
2232 using this_t = concat_both_mut_visitor;
2233 using edit_t = typename Node::edit_t;
2234
2235 template <typename LPos, typename TPos, typename RPos>
2236 static concat_center_mut_pos<Node>
2237 visit_inner(LPos&& lpos, edit_t ec,
2238 edit_t el, TPos&& tpos,
2239 edit_t er, RPos&& rpos)
2240 { return rpos.first_sub(concat_right_mut_visitor<Node>{},
2241 ec, el, lpos, tpos, er); }
2242
2243 template <typename LPos, typename TPos, typename RPos>
2244 static concat_center_mut_pos<Node>
2245 visit_leaf(LPos&& lpos, edit_t ec,
2246 edit_t el, TPos&& tpos,
2247 edit_t er, RPos&& rpos)
2248 { return rpos.first_sub_leaf(concat_right_mut_visitor<Node>{},
2249 ec, el, lpos, tpos, er); }
2250};
2251
2252template <typename Node>
2253struct concat_trees_right_mut_visitor
2254 : visitor_base<concat_trees_right_mut_visitor<Node>>
2255{
2256 using this_t = concat_trees_right_mut_visitor;
2257 using edit_t = typename Node::edit_t;
2258
2259 template <typename RPos, typename LPos, typename TPos>
2260 static concat_center_mut_pos<Node>
2261 visit_node(RPos&& rpos, edit_t ec,
2262 edit_t el, LPos&& lpos, TPos&& tpos,
2263 edit_t er)
2264 { return concat_inners_mut<Node>(
2265 ec, el, lpos, tpos, er, rpos); }
2266};
2267
2268template <typename Node>
2269struct concat_trees_left_mut_visitor
2270 : visitor_base<concat_trees_left_mut_visitor<Node>>
2271{
2272 using this_t = concat_trees_left_mut_visitor;
2273 using edit_t = typename Node::edit_t;
2274
2275 template <typename LPos, typename TPos, typename... Args>
2276 static concat_center_mut_pos<Node>
2277 visit_node(LPos&& lpos, edit_t ec,
2278 edit_t el, TPos&& tpos,
2279 edit_t er, Args&& ...args)
2280 { return visit_maybe_relaxed_sub(
2281 args...,
2282 concat_trees_right_mut_visitor<Node>{},
2283 ec, el, lpos, tpos, er); }
2284};
2285
2286template <typename Node>
2287relaxed_pos<Node>
2288concat_trees_mut(edit_type<Node> ec,
2289 edit_type<Node> el,
2290 Node* lroot, shift_t lshift, size_t lsize,
2291 Node* ltail, count_t ltcount,
2292 edit_type<Node> er,
2293 Node* rroot, shift_t rshift, size_t rsize)
2294{
2295 return visit_maybe_relaxed_sub(
2296 lroot, lshift, lsize,
2297 concat_trees_left_mut_visitor<Node>{},
2298 ec,
2299 el, make_leaf_pos(ltail, ltcount),
2300 er, rroot, rshift, rsize)
2301 .realize_e(ec);
2302}
2303
2304template <typename Node>
2305relaxed_pos<Node>
2306concat_trees_mut(edit_type<Node> ec,
2307 edit_type<Node> el,
2308 Node* ltail, count_t ltcount,
2309 edit_type<Node> er,
2310 Node* rroot, shift_t rshift, size_t rsize)
2311{
2312 return make_singleton_regular_sub_pos(ltail, ltcount).visit(
2313 concat_trees_left_mut_visitor<Node>{},
2314 ec,
2315 el, empty_leaf_pos<Node>{},
2316 er, rroot, rshift, rsize)
2317 .realize_e(ec);
2318}
2319
2320} // namespace rbts
2321} // namespace detail
2322} // namespace immer
2323