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 | |
22 | namespace immer { |
23 | namespace detail { |
24 | namespace rbts { |
25 | |
26 | template <typename T> |
27 | struct 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 | |
40 | template <typename T> |
41 | struct 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 | |
55 | template <typename T> |
56 | struct 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 | |
69 | struct 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 | |
85 | struct 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 | |
101 | struct 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 | |
125 | struct 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 | |
149 | struct 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 | |
208 | struct 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 | |
233 | struct 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 | |
258 | struct 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 | |
320 | struct 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 | |
446 | template <typename NodeT> |
447 | struct 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 | |
504 | struct 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 | |
541 | template <typename NodeT> |
542 | void dec_leaf(NodeT* node, count_t n) |
543 | { |
544 | make_leaf_sub_pos(node, n).visit(dec_visitor{}); |
545 | } |
546 | |
547 | template <typename NodeT> |
548 | void dec_inner(NodeT* node, shift_t shift, size_t size) |
549 | { |
550 | visit_maybe_relaxed_sub(node, shift, size, dec_visitor()); |
551 | } |
552 | |
553 | template <typename NodeT> |
554 | void dec_relaxed(NodeT* node, shift_t shift) |
555 | { |
556 | make_relaxed_pos(node, shift, node->relaxed()).visit(dec_visitor()); |
557 | } |
558 | |
559 | template <typename NodeT> |
560 | void dec_regular(NodeT* node, shift_t shift, size_t size) |
561 | { |
562 | make_regular_pos(node, shift, size).visit(dec_visitor()); |
563 | } |
564 | |
565 | template <typename NodeT> |
566 | void dec_empty_regular(NodeT* node) |
567 | { |
568 | make_empty_regular_pos(node).visit(dec_visitor()); |
569 | } |
570 | |
571 | template <typename NodeT> |
572 | struct 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 | |
647 | template <typename NodeT, bool Mutating = true> |
648 | struct 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 | |
749 | template <typename NodeT> |
750 | struct 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 | |
822 | struct 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 | |
854 | template <typename NodeT, bool Collapse=true, bool Mutating=true> |
855 | struct 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 | |
1023 | template <typename NodeT, bool Collapse=true> |
1024 | struct 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 | |
1124 | struct 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 | |
1156 | template <typename NodeT, bool Collapse=true, bool Mutating=true> |
1157 | struct 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 | |
1317 | template <typename NodeT, bool Collapse=true> |
1318 | struct 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 | |
1375 | template <typename Node> |
1376 | struct 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 | |
1456 | template <typename Node> |
1457 | struct 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 | |
1595 | struct 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 | |
1608 | struct 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 | |
1623 | template <bits_t B, bits_t BL> |
1624 | struct 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 = 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 | |
1698 | template <typename Node, typename LPos, typename CPos, typename RPos> |
1699 | concat_center_pos<Node> |
1700 | concat_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 | |
1713 | template <typename Node, typename LPos, typename TPos, typename RPos> |
1714 | concat_center_pos<Node> |
1715 | concat_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 | |
1736 | template <typename Node> |
1737 | struct concat_left_visitor; |
1738 | template <typename Node> |
1739 | struct concat_right_visitor; |
1740 | template <typename Node> |
1741 | struct concat_both_visitor; |
1742 | |
1743 | template <typename Node, typename LPos, typename TPos, typename RPos> |
1744 | concat_center_pos<Node> |
1745 | concat_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 | |
1763 | template <typename Node> |
1764 | struct 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 | |
1779 | template <typename Node> |
1780 | struct 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 | |
1795 | template <typename Node> |
1796 | struct 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 | |
1812 | template <typename Node> |
1813 | struct 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 | |
1824 | template <typename Node> |
1825 | struct 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 | |
1839 | template <typename Node> |
1840 | relaxed_pos<Node> |
1841 | concat_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 | |
1853 | template <typename Node> |
1854 | relaxed_pos<Node> |
1855 | concat_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 | |
1865 | template <typename Node> |
1866 | using concat_center_mut_pos = concat_center_pos<Node>; |
1867 | |
1868 | template <typename Node> |
1869 | struct 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 | |
2055 | struct 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 | |
2070 | template <bits_t B, bits_t BL> |
2071 | struct 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 | |
2105 | template <typename Node, typename LPos, typename CPos, typename RPos> |
2106 | concat_center_pos<Node> |
2107 | concat_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 | |
2117 | template <typename Node, typename LPos, typename TPos, typename RPos> |
2118 | concat_center_mut_pos<Node> |
2119 | concat_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 | |
2142 | template <typename Node> |
2143 | struct concat_left_mut_visitor; |
2144 | template <typename Node> |
2145 | struct concat_right_mut_visitor; |
2146 | template <typename Node> |
2147 | struct concat_both_mut_visitor; |
2148 | |
2149 | template <typename Node, typename LPos, typename TPos, typename RPos> |
2150 | concat_center_mut_pos<Node> |
2151 | concat_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 | |
2182 | template <typename Node> |
2183 | struct 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 | |
2204 | template <typename Node> |
2205 | struct 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 | |
2228 | template <typename Node> |
2229 | struct 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 | |
2252 | template <typename Node> |
2253 | struct 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 | |
2268 | template <typename Node> |
2269 | struct 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 | |
2286 | template <typename Node> |
2287 | relaxed_pos<Node> |
2288 | concat_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 | |
2304 | template <typename Node> |
2305 | relaxed_pos<Node> |
2306 | concat_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 | |