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