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/bits.hpp>
13
14#include <cassert>
15#include <utility>
16#include <type_traits>
17
18namespace immer {
19namespace detail {
20namespace rbts {
21
22template <typename Pos>
23constexpr auto bits = std::decay_t<Pos>::node_t::bits;
24
25template <typename Pos>
26constexpr auto bits_leaf = std::decay_t<Pos>::node_t::bits_leaf;
27
28template <typename Pos>
29using node_type = typename std::decay<Pos>::type::node_t;
30
31template <typename Pos>
32using edit_type = typename std::decay<Pos>::type::node_t::edit_t;
33
34template <typename NodeT>
35struct empty_regular_pos
36{
37 using node_t = NodeT;
38 node_t* node_;
39
40 count_t count() const { return 0; }
41 node_t* node() const { return node_; }
42 shift_t shift() const { return 0; }
43 size_t size() const { return 0; }
44
45 template <typename Visitor, typename... Args>
46 void each(Visitor, Args&&...) {}
47 template <typename Visitor, typename... Args>
48 bool each_pred(Visitor, Args&&...) { return true; }
49
50 template <typename Visitor, typename... Args>
51 decltype(auto) visit(Visitor v, Args&& ...args)
52 {
53 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
54 }
55};
56
57template <typename NodeT>
58empty_regular_pos<NodeT> make_empty_regular_pos(NodeT* node)
59{
60 return {node};
61}
62
63template <typename NodeT>
64struct empty_leaf_pos
65{
66 using node_t = NodeT;
67 node_t* node_;
68
69 count_t count() const { return 0; }
70 node_t* node() const { return node_; }
71 shift_t shift() const { return 0; }
72 size_t size() const { return 0; }
73
74 template <typename Visitor, typename ...Args>
75 decltype(auto) visit(Visitor v, Args&& ...args)
76 {
77 return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
78 }
79};
80
81template <typename NodeT>
82empty_leaf_pos<NodeT> make_empty_leaf_pos(NodeT* node)
83{
84 assert(node);
85 return {node};
86}
87
88template <typename NodeT>
89struct leaf_pos
90{
91 static constexpr auto B = NodeT::bits;
92 static constexpr auto BL = NodeT::bits_leaf;
93
94 using node_t = NodeT;
95 node_t* node_;
96 size_t size_;
97
98 count_t count() const { return index(size_ - 1) + 1; }
99 node_t* node() const { return node_; }
100 size_t size() const { return size_; }
101 shift_t shift() const { return 0; }
102 count_t index(size_t idx) const { return idx & mask<BL>; }
103 count_t subindex(size_t idx) const { return idx; }
104
105 template <typename Visitor, typename ...Args>
106 decltype(auto) visit(Visitor v, Args&& ...args)
107 {
108 return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
109 }
110};
111
112template <typename NodeT>
113leaf_pos<NodeT> make_leaf_pos(NodeT* node, size_t size)
114{
115 assert(node);
116 assert(size > 0);
117 return {node, size};
118}
119
120template <typename NodeT>
121struct leaf_sub_pos
122{
123 static constexpr auto B = NodeT::bits;
124 static constexpr auto BL = NodeT::bits_leaf;
125
126 using node_t = NodeT;
127 node_t* node_;
128 count_t count_;
129
130 count_t count() const { return count_; }
131 node_t* node() const { return node_; }
132 size_t size() const { return count_; }
133 shift_t shift() const { return 0; }
134 count_t index(size_t idx) const { return idx & mask<BL>; }
135 count_t subindex(size_t idx) const { return idx; }
136
137 template <typename Visitor, typename ...Args>
138 decltype(auto) visit(Visitor v, Args&& ...args)
139 {
140 return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
141 }
142};
143
144template <typename NodeT>
145leaf_sub_pos<NodeT> make_leaf_sub_pos(NodeT* node, count_t count)
146{
147 assert(node);
148 assert(count <= branches<NodeT::bits_leaf>);
149 return {node, count};
150}
151
152template <typename NodeT>
153struct leaf_descent_pos
154{
155 static constexpr auto B = NodeT::bits;
156 static constexpr auto BL = NodeT::bits_leaf;
157
158 using node_t = NodeT;
159 node_t* node_;
160
161 node_t* node() const { return node_; }
162 shift_t shift() const { return 0; }
163 count_t index(size_t idx) const { return idx & mask<BL>; }
164
165 template <typename... Args>
166 decltype(auto) descend(Args&&...) {}
167
168 template <typename Visitor, typename ...Args>
169 decltype(auto) visit(Visitor v, Args&& ...args)
170 {
171 return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
172 }
173};
174
175template <typename NodeT>
176leaf_descent_pos<NodeT> make_leaf_descent_pos(NodeT* node)
177{
178 assert(node);
179 return {node};
180}
181
182template <typename NodeT>
183struct full_leaf_pos
184{
185 static constexpr auto B = NodeT::bits;
186 static constexpr auto BL = NodeT::bits_leaf;
187
188 using node_t = NodeT;
189 node_t* node_;
190
191 count_t count() const { return branches<BL>; }
192 node_t* node() const { return node_; }
193 size_t size() const { return branches<BL>; }
194 shift_t shift() const { return 0; }
195 count_t index(size_t idx) const { return idx & mask<BL>; }
196 count_t subindex(size_t idx) const { return idx; }
197
198 template <typename Visitor, typename ...Args>
199 decltype(auto) visit(Visitor v, Args&& ...args)
200 {
201 return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
202 }
203};
204
205template <typename NodeT>
206full_leaf_pos<NodeT> make_full_leaf_pos(NodeT* node)
207{
208 assert(node);
209 return {node};
210}
211
212template <typename NodeT>
213struct regular_pos
214{
215 static constexpr auto B = NodeT::bits;
216 static constexpr auto BL = NodeT::bits_leaf;
217
218 using node_t = NodeT;
219 node_t* node_;
220 shift_t shift_;
221 size_t size_;
222
223 count_t count() const { return index(size_ - 1) + 1; }
224 node_t* node() const { return node_; }
225 size_t size() const { return size_; }
226 shift_t shift() const { return shift_; }
227 count_t index(size_t idx) const { return (idx >> shift_) & mask<B>; }
228 count_t subindex(size_t idx) const { return idx >> shift_; }
229 size_t this_size() const { return ((size_ - 1) & ~(~size_t{} << (shift_ + B))) + 1; }
230
231 template <typename Visitor, typename... Args>
232 void each(Visitor v, Args&&... args)
233 { return each_regular(*this, v, args...); }
234
235 template <typename Visitor, typename... Args>
236 bool each_pred(Visitor v, Args&&... args)
237 { return each_pred_regular(*this, v, args...); }
238
239 template <typename Visitor, typename... Args>
240 bool each_pred_zip(Visitor v, node_t* other, Args&&... args)
241 { return each_pred_zip_regular(*this, v, other, args...); }
242
243 template <typename Visitor, typename... Args>
244 bool each_pred_i(Visitor v, count_t i, count_t n, Args&&... args)
245 { return each_pred_i_regular(*this, v, i, n, args...); }
246
247 template <typename Visitor, typename... Args>
248 bool each_pred_right(Visitor v, count_t start, Args&&... args)
249 { return each_pred_right_regular(*this, v, start, args...); }
250
251 template <typename Visitor, typename... Args>
252 bool each_pred_left(Visitor v, count_t n, Args&&... args)
253 { return each_pred_left_regular(*this, v, n, args...); }
254
255 template <typename Visitor, typename... Args>
256 void each_i(Visitor v, count_t i, count_t n, Args&&... args)
257 { return each_i_regular(*this, v, i, n, args...); }
258
259 template <typename Visitor, typename... Args>
260 void each_right(Visitor v, count_t start, Args&&... args)
261 { return each_right_regular(*this, v, start, args...); }
262
263 template <typename Visitor, typename... Args>
264 void each_left(Visitor v, count_t n, Args&&... args)
265 { return each_left_regular(*this, v, n, args...); }
266
267 template <typename Visitor, typename... Args>
268 decltype(auto) towards(Visitor v, size_t idx, Args&&... args)
269 { return towards_oh_ch_regular(*this, v, idx, index(idx), count(), args...); }
270
271 template <typename Visitor, typename... Args>
272 decltype(auto) towards_oh(Visitor v, size_t idx,
273 count_t offset_hint,
274 Args&&... args)
275 { return towards_oh_ch_regular(*this, v, idx, offset_hint, count(), args...); }
276
277 template <typename Visitor, typename... Args>
278 decltype(auto) towards_oh_ch(Visitor v, size_t idx,
279 count_t offset_hint,
280 count_t count_hint,
281 Args&&... args)
282 { return towards_oh_ch_regular(*this, v, idx, offset_hint, count(), args...); }
283
284 template <typename Visitor, typename... Args>
285 decltype(auto) towards_sub_oh(Visitor v, size_t idx,
286 count_t offset_hint,
287 Args&&... args)
288 { return towards_sub_oh_regular(*this, v, idx, offset_hint, args...); }
289
290 template <typename Visitor, typename... Args>
291 decltype(auto) last_oh(Visitor v, count_t offset_hint, Args&&... args)
292 { return last_oh_regular(*this, v, offset_hint, args...); }
293
294 template <typename Visitor, typename ...Args>
295 decltype(auto) visit(Visitor v, Args&& ...args)
296 {
297 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
298 }
299};
300
301template <typename Pos, typename Visitor, typename... Args>
302void each_regular(Pos&& p, Visitor v, Args&&... args)
303{
304 constexpr auto B = bits<Pos>;
305 constexpr auto BL = bits_leaf<Pos>;
306 auto n = p.node()->inner();
307 auto last = p.count() - 1;
308 auto e = n + last;
309 if (p.shift() == BL) {
310 for (; n != e; ++n) {
311 IMMER_PREFETCH(n + 1);
312 make_full_leaf_pos(*n).visit(v, args...);
313 }
314 make_leaf_pos(*n, p.size()).visit(v, args...);
315 } else {
316 auto ss = p.shift() - B;
317 for (; n != e; ++n)
318 make_full_pos(*n, ss).visit(v, args...);
319 make_regular_pos(*n, ss, p.size()).visit(v, args...);
320 }
321}
322
323template <typename Pos, typename Visitor, typename... Args>
324bool each_pred_regular(Pos&& p, Visitor v, Args&&... args)
325{
326 constexpr auto B = bits<Pos>;
327 constexpr auto BL = bits_leaf<Pos>;
328 auto n = p.node()->inner();
329 auto last = p.count() - 1;
330 auto e = n + last;
331 if (p.shift() == BL) {
332 for (; n != e; ++n) {
333 IMMER_PREFETCH(n + 1);
334 if (!make_full_leaf_pos(*n).visit(v, args...))
335 return false;
336 }
337 return make_leaf_pos(*n, p.size()).visit(v, args...);
338 } else {
339 auto ss = p.shift() - B;
340 for (; n != e; ++n)
341 if (!make_full_pos(*n, ss).visit(v, args...))
342 return false;
343 return make_regular_pos(*n, ss, p.size()).visit(v, args...);
344 }
345}
346
347template <typename Pos, typename Visitor, typename... Args>
348bool each_pred_zip_regular(Pos&& p, Visitor v, node_type<Pos>* other, Args&&... args)
349{
350 constexpr auto B = bits<Pos>;
351 constexpr auto BL = bits_leaf<Pos>;
352
353 auto n = p.node()->inner();
354 auto n2 = other->inner();
355 auto last = p.count() - 1;
356 auto e = n + last;
357 if (p.shift() == BL) {
358 for (; n != e; ++n, ++n2) {
359 IMMER_PREFETCH(n + 1);
360 IMMER_PREFETCH(n2 + 1);
361 if (!make_full_leaf_pos(*n).visit(v, *n2, args...))
362 return false;
363 }
364 return make_leaf_pos(*n, p.size()).visit(v, *n2, args...);
365 } else {
366 auto ss = p.shift() - B;
367 for (; n != e; ++n, ++n2)
368 if (!make_full_pos(*n, ss).visit(v, *n2, args...))
369 return false;
370 return make_regular_pos(*n, ss, p.size()).visit(v, *n2, args...);
371 }
372}
373
374template <typename Pos, typename Visitor, typename... Args>
375bool each_pred_i_regular(Pos&& p, Visitor v, count_t f, count_t l, Args&&... args)
376{
377 constexpr auto B = bits<Pos>;
378 constexpr auto BL = bits_leaf<Pos>;
379
380 if (p.shift() == BL) {
381 if (l > f) {
382 if (l < p.count()) {
383 auto n = p.node()->inner() + f;
384 auto e = p.node()->inner() + l;
385 for (; n < e; ++n) {
386 IMMER_PREFETCH(n + 1);
387 if (!make_full_leaf_pos(*n).visit(v, args...))
388 return false;
389 }
390 } else {
391 auto n = p.node()->inner() + f;
392 auto e = p.node()->inner() + l - 1;
393 for (; n < e; ++n) {
394 IMMER_PREFETCH(n + 1);
395 if (!make_full_leaf_pos(*n).visit(v, args...))
396 return false;
397 }
398 if (!make_leaf_pos(*n, p.size()).visit(v, args...))
399 return false;
400 }
401 }
402 } else {
403 if (l > f) {
404 auto ss = p.shift() - B;
405 if (l < p.count()) {
406 auto n = p.node()->inner() + f;
407 auto e = p.node()->inner() + l;
408 for (; n < e; ++n)
409 if (!make_full_pos(*n, ss).visit(v, args...))
410 return false;
411 } else {
412 auto n = p.node()->inner() + f;
413 auto e = p.node()->inner() + l - 1;
414 for (; n < e; ++n)
415 if (!make_full_pos(*n, ss).visit(v, args...))
416 return false;
417 if (!make_regular_pos(*n, ss, p.size()).visit(v, args...))
418 return false;
419 }
420 }
421 }
422 return true;
423}
424
425template <typename Pos, typename Visitor, typename... Args>
426bool each_pred_left_regular(Pos&& p, Visitor v, count_t last, Args&&... args)
427{
428 constexpr auto B = bits<Pos>;
429 constexpr auto BL = bits_leaf<Pos>;
430 assert(last < p.count());
431 if (p.shift() == BL) {
432 auto n = p.node()->inner();
433 auto e = n + last;
434 for (; n != e; ++n) {
435 IMMER_PREFETCH(n + 1);
436 if (!make_full_leaf_pos(*n).visit(v, args...))
437 return false;
438 }
439 } else {
440 auto n = p.node()->inner();
441 auto e = n + last;
442 auto ss = p.shift() - B;
443 for (; n != e; ++n)
444 if (!make_full_pos(*n, ss).visit(v, args...))
445 return false;
446 }
447 return true;
448}
449
450template <typename Pos, typename Visitor, typename... Args>
451bool each_pred_right_regular(Pos&& p, Visitor v, count_t start, Args&&... args)
452{
453 constexpr auto B = bits<Pos>;
454 constexpr auto BL = bits_leaf<Pos>;
455
456 if (p.shift() == BL) {
457 auto n = p.node()->inner() + start;
458 auto last = p.count() - 1;
459 auto e = p.node()->inner() + last;
460 if (n <= e) {
461 for (; n != e; ++n) {
462 IMMER_PREFETCH(n + 1);
463 if (!make_full_leaf_pos(*n).visit(v, args...))
464 return false;
465 }
466 if (!make_leaf_pos(*n, p.size()).visit(v, args...))
467 return false;
468 }
469 } else {
470 auto n = p.node()->inner() + start;
471 auto last = p.count() - 1;
472 auto e = p.node()->inner() + last;
473 auto ss = p.shift() - B;
474 if (n <= e) {
475 for (; n != e; ++n)
476 if (!make_full_pos(*n, ss).visit(v, args...))
477 return false;
478 if (!make_regular_pos(*n, ss, p.size()).visit(v, args...))
479 return false;
480 }
481 }
482 return true;
483}
484
485template <typename Pos, typename Visitor, typename... Args>
486void each_i_regular(Pos&& p, Visitor v, count_t f, count_t l, Args&&... args)
487{
488 constexpr auto B = bits<Pos>;
489 constexpr auto BL = bits_leaf<Pos>;
490
491 if (p.shift() == BL) {
492 if (l > f) {
493 if (l < p.count()) {
494 auto n = p.node()->inner() + f;
495 auto e = p.node()->inner() + l;
496 for (; n < e; ++n) {
497 IMMER_PREFETCH(n + 1);
498 make_full_leaf_pos(*n).visit(v, args...);
499 }
500 } else {
501 auto n = p.node()->inner() + f;
502 auto e = p.node()->inner() + l - 1;
503 for (; n < e; ++n) {
504 IMMER_PREFETCH(n + 1);
505 make_full_leaf_pos(*n).visit(v, args...);
506 }
507 make_leaf_pos(*n, p.size()).visit(v, args...);
508 }
509 }
510 } else {
511 if (l > f) {
512 auto ss = p.shift() - B;
513 if (l < p.count()) {
514 auto n = p.node()->inner() + f;
515 auto e = p.node()->inner() + l;
516 for (; n < e; ++n)
517 make_full_pos(*n, ss).visit(v, args...);
518 } else {
519 auto n = p.node()->inner() + f;
520 auto e = p.node()->inner() + l - 1;
521 for (; n < e; ++n)
522 make_full_pos(*n, ss).visit(v, args...);
523 make_regular_pos(*n, ss, p.size()).visit(v, args...);
524 }
525 }
526 }
527}
528
529template <typename Pos, typename Visitor, typename... Args>
530void each_left_regular(Pos&& p, Visitor v, count_t last, Args&&... args)
531{
532 constexpr auto B = bits<Pos>;
533 constexpr auto BL = bits_leaf<Pos>;
534 assert(last < p.count());
535 if (p.shift() == BL) {
536 auto n = p.node()->inner();
537 auto e = n + last;
538 for (; n != e; ++n) {
539 IMMER_PREFETCH(n + 1);
540 make_full_leaf_pos(*n).visit(v, args...);
541 }
542 } else {
543 auto n = p.node()->inner();
544 auto e = n + last;
545 auto ss = p.shift() - B;
546 for (; n != e; ++n)
547 make_full_pos(*n, ss).visit(v, args...);
548 }
549}
550
551template <typename Pos, typename Visitor, typename... Args>
552void each_right_regular(Pos&& p, Visitor v, count_t start, Args&&... args)
553{
554 constexpr auto B = bits<Pos>;
555 constexpr auto BL = bits_leaf<Pos>;
556
557 if (p.shift() == BL) {
558 auto n = p.node()->inner() + start;
559 auto last = p.count() - 1;
560 auto e = p.node()->inner() + last;
561 if (n <= e) {
562 for (; n != e; ++n) {
563 IMMER_PREFETCH(n + 1);
564 make_full_leaf_pos(*n).visit(v, args...);
565 }
566 make_leaf_pos(*n, p.size()).visit(v, args...);
567 }
568 } else {
569 auto n = p.node()->inner() + start;
570 auto last = p.count() - 1;
571 auto e = p.node()->inner() + last;
572 auto ss = p.shift() - B;
573 if (n <= e) {
574 for (; n != e; ++n)
575 make_full_pos(*n, ss).visit(v, args...);
576 make_regular_pos(*n, ss, p.size()).visit(v, args...);
577 }
578 }
579}
580
581template <typename Pos, typename Visitor, typename... Args>
582decltype(auto) towards_oh_ch_regular(Pos&& p, Visitor v, size_t idx,
583 count_t offset_hint,
584 count_t count_hint,
585 Args&&... args)
586{
587 constexpr auto B = bits<Pos>;
588 constexpr auto BL = bits_leaf<Pos>;
589 assert(offset_hint == p.index(idx));
590 assert(count_hint == p.count());
591 auto is_leaf = p.shift() == BL;
592 auto child = p.node()->inner() [offset_hint];
593 auto is_full = offset_hint + 1 != count_hint;
594 return is_full
595 ? (is_leaf
596 ? make_full_leaf_pos(child).visit(v, idx, args...)
597 : make_full_pos(child, p.shift() - B).visit(v, idx, args...))
598 : (is_leaf
599 ? make_leaf_pos(child, p.size()).visit(v, idx, args...)
600 : make_regular_pos(child, p.shift() - B, p.size()).visit(v, idx, args...));
601}
602
603template <typename Pos, typename Visitor, typename... Args>
604decltype(auto) towards_sub_oh_regular(Pos&& p, Visitor v, size_t idx,
605 count_t offset_hint,
606 Args&&... args)
607{
608 constexpr auto B = bits<Pos>;
609 constexpr auto BL = bits_leaf<Pos>;
610 assert(offset_hint == p.index(idx));
611 auto is_leaf = p.shift() == BL;
612 auto child = p.node()->inner() [offset_hint];
613 auto lsize = offset_hint << p.shift();
614 auto size = p.this_size();
615 auto is_full = (size - lsize) >= (size_t{1} << p.shift());
616 return is_full
617 ? (is_leaf
618 ? make_full_leaf_pos(child).visit(
619 v, idx - lsize, args...)
620 : make_full_pos(child, p.shift() - B).visit(
621 v, idx - lsize, args...))
622 : (is_leaf
623 ? make_leaf_sub_pos(child, size - lsize).visit(
624 v, idx - lsize, args...)
625 : make_regular_sub_pos(child, p.shift() - B, size - lsize).visit(
626 v, idx - lsize, args...));
627}
628
629template <typename Pos, typename Visitor, typename... Args>
630decltype(auto) last_oh_regular(Pos&& p, Visitor v,
631 count_t offset_hint,
632 Args&&... args)
633{
634 assert(offset_hint == p.count() - 1);
635 constexpr auto B = bits<Pos>;
636 constexpr auto BL = bits_leaf<Pos>;
637 auto child = p.node()->inner() [offset_hint];
638 auto is_leaf = p.shift() == BL;
639 return is_leaf
640 ? make_leaf_pos(child, p.size()).visit(v, args...)
641 : make_regular_pos(child, p.shift() - B, p.size()).visit(v, args...);
642}
643
644template <typename NodeT>
645regular_pos<NodeT> make_regular_pos(NodeT* node,
646 shift_t shift,
647 size_t size)
648{
649 assert(node);
650 assert(shift >= NodeT::bits_leaf);
651 assert(size > 0);
652 return {node, shift, size};
653}
654
655struct null_sub_pos
656{
657 auto node() const { return nullptr; }
658
659 template <typename Visitor, typename... Args>
660 void each_sub(Visitor, Args&&...) {}
661 template <typename Visitor, typename... Args>
662 void each_right_sub(Visitor, Args&&...) {}
663 template <typename Visitor, typename... Args>
664 void each_left_sub(Visitor, Args&&...) {}
665 template <typename Visitor, typename... Args>
666 void visit(Visitor, Args&&...) {}
667};
668
669template <typename NodeT>
670struct singleton_regular_sub_pos
671{
672 // this is a fake regular pos made out of a single child... useful
673 // to treat a single leaf node as a whole tree
674
675 static constexpr auto B = NodeT::bits;
676 static constexpr auto BL = NodeT::bits_leaf;
677
678 using node_t = NodeT;
679 node_t* leaf_;
680 count_t count_;
681
682 count_t count() const { return 1; }
683 node_t* node() const { return nullptr; }
684 size_t size() const { return count_; }
685 shift_t shift() const { return BL; }
686 count_t index(size_t idx) const { return 0; }
687 count_t subindex(size_t idx) const { return 0; }
688 size_t size_before(count_t offset) const { return 0; }
689 size_t this_size() const { return count_; }
690 size_t size(count_t offset) { return count_; }
691
692 template <typename Visitor, typename... Args>
693 void each_left_sub(Visitor v, Args&&... args) {}
694 template <typename Visitor, typename... Args>
695 void each(Visitor v, Args&&... args) {}
696
697 template <typename Visitor, typename... Args>
698 decltype(auto) last_sub(Visitor v, Args&&... args)
699 {
700 return make_leaf_sub_pos(leaf_, count_).visit(v, args...);
701 }
702
703 template <typename Visitor, typename ...Args>
704 decltype(auto) visit(Visitor v, Args&& ...args)
705 {
706 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
707 }
708};
709
710template <typename NodeT>
711auto make_singleton_regular_sub_pos(NodeT* leaf, count_t count)
712{
713 assert(leaf);
714 IMMER_ASSERT_TAGGED(leaf->kind() == NodeT::kind_t::leaf);
715 assert(count > 0);
716 return singleton_regular_sub_pos<NodeT>{leaf, count};
717}
718
719template <typename NodeT>
720struct regular_sub_pos
721{
722 static constexpr auto B = NodeT::bits;
723 static constexpr auto BL = NodeT::bits_leaf;
724
725 using node_t = NodeT;
726 node_t* node_;
727 shift_t shift_;
728 size_t size_;
729
730 count_t count() const { return subindex(size_ - 1) + 1; }
731 node_t* node() const { return node_; }
732 size_t size() const { return size_; }
733 shift_t shift() const { return shift_; }
734 count_t index(size_t idx) const { return (idx >> shift_) & mask<B>; }
735 count_t subindex(size_t idx) const { return idx >> shift_; }
736 size_t size_before(count_t offset) const { return offset << shift_; }
737 size_t this_size() const { return size_; }
738
739 auto size(count_t offset)
740 {
741 return offset == subindex(size_ - 1)
742 ? size_ - size_before(offset)
743 : size_t{1} << shift_;
744 }
745
746 auto size_sbh(count_t offset, size_t size_before_hint)
747 {
748 assert(size_before_hint == size_before(offset));
749 return offset == subindex(size_ - 1)
750 ? size_ - size_before_hint
751 : size_t{1} << shift_;
752 }
753
754 void copy_sizes(count_t offset,
755 count_t n,
756 size_t init,
757 size_t* sizes)
758 {
759 if (n) {
760 auto last = offset + n - 1;
761 auto e = sizes + n - 1;
762 for (; sizes != e; ++sizes)
763 init = *sizes = init + (size_t{1} << shift_);
764 *sizes = init + size(last);
765 }
766 }
767
768 template <typename Visitor, typename... Args>
769 void each(Visitor v, Args&& ...args)
770 { return each_regular(*this, v, args...); }
771
772 template <typename Visitor, typename... Args>
773 bool each_pred(Visitor v, Args&& ...args)
774 { return each_pred_regular(*this, v, args...); }
775
776 template <typename Visitor, typename... Args>
777 bool each_pred_zip(Visitor v, node_t* other, Args&&... args)
778 { return each_pred_zip_regular(*this, v, other, args...); }
779
780 template <typename Visitor, typename... Args>
781 bool each_pred_i(Visitor v, count_t i, count_t n, Args&& ...args)
782 { return each_pred_i_regular(*this, v, i, n, args...); }
783
784 template <typename Visitor, typename... Args>
785 bool each_pred_right(Visitor v, count_t start, Args&& ...args)
786 { return each_pred_right_regular(*this, v, start, args...); }
787
788 template <typename Visitor, typename... Args>
789 bool each_pred_left(Visitor v, count_t last, Args&& ...args)
790 { return each_pred_left_regular(*this, v, last, args...); }
791
792 template <typename Visitor, typename... Args>
793 void each_i(Visitor v, count_t i, count_t n, Args&& ...args)
794 { return each_i_regular(*this, v, i, n, args...); }
795
796 template <typename Visitor, typename... Args>
797 void each_right(Visitor v, count_t start, Args&& ...args)
798 { return each_right_regular(*this, v, start, args...); }
799
800 template <typename Visitor, typename... Args>
801 void each_left(Visitor v, count_t last, Args&& ...args)
802 { return each_left_regular(*this, v, last, args...); }
803
804 template <typename Visitor, typename... Args>
805 void each_right_sub_(Visitor v, count_t i, Args&& ...args)
806 {
807 auto last = count() - 1;
808 auto lsize = size_ - (last << shift_);
809 auto n = node()->inner() + i;
810 auto e = node()->inner() + last;
811 if (shift() == BL) {
812 for (; n != e; ++n) {
813 IMMER_PREFETCH(n + 1);
814 make_full_leaf_pos(*n).visit(v, args...);
815 }
816 make_leaf_sub_pos(*n, lsize).visit(v, args...);
817 } else {
818 auto ss = shift_ - B;
819 for (; n != e; ++n)
820 make_full_pos(*n, ss).visit(v, args...);
821 make_regular_sub_pos(*n, ss, lsize).visit(v, args...);
822 }
823 }
824
825 template <typename Visitor, typename... Args>
826 void each_sub(Visitor v, Args&& ...args)
827 { each_right_sub_(v, 0, args...); }
828
829 template <typename Visitor, typename... Args>
830 void each_right_sub(Visitor v, Args&& ...args)
831 { if (count() > 1) each_right_sub_(v, 1, args...); }
832
833 template <typename Visitor, typename... Args>
834 void each_left_sub(Visitor v, Args&& ...args)
835 { each_left(v, count() - 1, args...); }
836
837 template <typename Visitor, typename... Args>
838 decltype(auto) towards(Visitor v, size_t idx, Args&&... args)
839 { return towards_oh_ch_regular(*this, v, idx, index(idx), count(), args...); }
840
841 template <typename Visitor, typename... Args>
842 decltype(auto) towards_oh(Visitor v, size_t idx,
843 count_t offset_hint,
844 Args&&... args)
845 { return towards_oh_ch_regular(*this, v, idx, offset_hint, count(), args...); }
846
847 template <typename Visitor, typename... Args>
848 decltype(auto) towards_oh_ch(Visitor v, size_t idx,
849 count_t offset_hint,
850 count_t count_hint,
851 Args&&... args)
852 { return towards_oh_ch_regular(*this, v, idx, offset_hint, count(), args...); }
853
854 template <typename Visitor, typename... Args>
855 decltype(auto) towards_sub_oh(Visitor v, size_t idx,
856 count_t offset_hint,
857 Args&& ...args)
858 { return towards_sub_oh_regular(*this, v, idx, offset_hint, args...); }
859
860 template <typename Visitor, typename... Args>
861 decltype(auto) last_oh(Visitor v, count_t offset_hint, Args&&... args)
862 { return last_oh_regular(*this, v, offset_hint, args...); }
863
864 template <typename Visitor, typename... Args>
865 decltype(auto) last_sub(Visitor v, Args&&... args)
866 {
867 auto offset = count() - 1;
868 auto child = node_->inner() [offset];
869 auto is_leaf = shift_ == BL;
870 auto lsize = size_ - (offset << shift_);
871 return is_leaf
872 ? make_leaf_sub_pos(child, lsize).visit(v, args...)
873 : make_regular_sub_pos(child, shift_ - B, lsize).visit(v, args...);
874 }
875
876 template <typename Visitor, typename... Args>
877 decltype(auto) first_sub(Visitor v, Args&&... args)
878 {
879 auto is_leaf = shift_ == BL;
880 auto child = node_->inner() [0];
881 auto is_full = size_ >= (size_t{1} << shift_);
882 return is_full
883 ? (is_leaf
884 ? make_full_leaf_pos(child).visit(v, args...)
885 : make_full_pos(child, shift_ - B).visit(v, args...))
886 : (is_leaf
887 ? make_leaf_sub_pos(child, size_).visit(v, args...)
888 : make_regular_sub_pos(child, shift_ - B, size_).visit(v, args...));
889 }
890
891 template <typename Visitor, typename... Args>
892 decltype(auto) first_sub_leaf(Visitor v, Args&&... args)
893 {
894 assert(shift_ == BL);
895 auto child = node_->inner() [0];
896 auto is_full = size_ >= branches<BL>;
897 return is_full
898 ? make_full_leaf_pos(child).visit(v, args...)
899 : make_leaf_sub_pos(child, size_).visit(v, args...);
900 }
901
902 template <typename Visitor, typename... Args>
903 decltype(auto) first_sub_inner(Visitor v, Args&&... args)
904 {
905 assert(shift_ >= BL);
906 auto child = node_->inner() [0];
907 auto is_full = size_ >= branches<BL>;
908 return is_full
909 ? make_full_pos(child, shift_ - B).visit(v, args...)
910 : make_regular_sub_pos(child, shift_ - B, size_).visit(v, args...);
911 }
912
913 template <typename Visitor, typename... Args>
914 decltype(auto) nth_sub(count_t idx, Visitor v, Args&&... args)
915 {
916 assert(idx < count());
917 auto is_leaf = shift_ == BL;
918 auto child = node_->inner() [idx];
919 auto lsize = size(idx);
920 auto is_full = idx + 1 < count();
921 return is_full
922 ? (is_leaf
923 ? make_full_leaf_pos(child).visit(v, args...)
924 : make_full_pos(child, shift_ - B).visit(v, args...))
925 : (is_leaf
926 ? make_leaf_sub_pos(child, lsize).visit(v, args...)
927 : make_regular_sub_pos(child, shift_ - B, lsize).visit(v, args...));
928 }
929
930 template <typename Visitor, typename... Args>
931 decltype(auto) nth_sub_leaf(count_t idx, Visitor v, Args&&... args)
932 {
933 assert(shift_ == BL);
934 auto child = node_->inner() [idx];
935 auto lsize = size(idx);
936 auto is_full = idx + 1 < count();
937 return is_full
938 ? make_full_leaf_pos(child).visit(v, args...)
939 : make_leaf_sub_pos(child, lsize).visit(v, args...);
940 }
941
942 template <typename Visitor, typename ...Args>
943 decltype(auto) visit(Visitor v, Args&& ...args)
944 {
945 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
946 }
947};
948
949template <typename NodeT>
950regular_sub_pos<NodeT> make_regular_sub_pos(NodeT* node,
951 shift_t shift,
952 size_t size)
953{
954 assert(node);
955 assert(shift >= NodeT::bits_leaf);
956 assert(size > 0);
957 assert(size <= (branches<NodeT::bits, size_t> << shift));
958 return {node, shift, size};
959}
960
961template <typename NodeT, shift_t Shift,
962 bits_t B = NodeT::bits,
963 bits_t BL = NodeT::bits_leaf>
964struct regular_descent_pos
965{
966 static_assert(Shift > 0, "not leaf...");
967
968 using node_t = NodeT;
969 node_t* node_;
970
971 node_t* node() const { return node_; }
972 shift_t shift() const { return Shift; }
973 count_t index(size_t idx) const {
974#if !defined(_MSC_VER)
975#pragma GCC diagnostic push
976#pragma GCC diagnostic ignored "-Wshift-count-overflow"
977#endif
978 return (idx >> Shift) & mask<B>;
979#if !defined(_MSC_VER)
980#pragma GCC diagnostic pop
981#endif
982 }
983
984 template <typename Visitor>
985 decltype(auto) descend(Visitor v, size_t idx)
986 {
987 auto offset = index(idx);
988 auto child = node_->inner()[offset];
989 return regular_descent_pos<NodeT, Shift - B>{child}.visit(v, idx);
990 }
991
992 template <typename Visitor, typename ...Args>
993 decltype(auto) visit(Visitor v, Args&& ...args)
994 {
995 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
996 }
997};
998
999template <typename NodeT, bits_t B, bits_t BL>
1000struct regular_descent_pos<NodeT, BL, B, BL>
1001{
1002 using node_t = NodeT;
1003 node_t* node_;
1004
1005 node_t* node() const { return node_; }
1006 shift_t shift() const { return BL; }
1007 count_t index(size_t idx) const { return (idx >> BL) & mask<B>; }
1008
1009 template <typename Visitor>
1010 decltype(auto) descend(Visitor v, size_t idx)
1011 {
1012 auto offset = index(idx);
1013 auto child = node_->inner()[offset];
1014 return make_leaf_descent_pos(child).visit(v, idx);
1015 }
1016
1017 template <typename Visitor, typename ...Args>
1018 decltype(auto) visit(Visitor v, Args&& ...args)
1019 {
1020 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
1021 }
1022};
1023
1024template <typename NodeT, typename Visitor>
1025decltype(auto) visit_regular_descent(NodeT* node, shift_t shift, Visitor v,
1026 size_t idx)
1027{
1028 constexpr auto B = NodeT::bits;
1029 constexpr auto BL = NodeT::bits_leaf;
1030 assert(node);
1031 assert(shift >= BL);
1032 switch (shift) {
1033 case BL + B * 0: return regular_descent_pos<NodeT, BL + B * 0>{node}.visit(v, idx);
1034 case BL + B * 1: return regular_descent_pos<NodeT, BL + B * 1>{node}.visit(v, idx);
1035 case BL + B * 2: return regular_descent_pos<NodeT, BL + B * 2>{node}.visit(v, idx);
1036 case BL + B * 3: return regular_descent_pos<NodeT, BL + B * 3>{node}.visit(v, idx);
1037 case BL + B * 4: return regular_descent_pos<NodeT, BL + B * 4>{node}.visit(v, idx);
1038 case BL + B * 5: return regular_descent_pos<NodeT, BL + B * 5>{node}.visit(v, idx);
1039#if IMMER_DESCENT_DEEP
1040 default:
1041 for (auto level = shift; level != endshift<B, BL>; level -= B)
1042 node = node->inner() [(idx >> level) & mask<B>];
1043 return make_leaf_descent_pos(node).visit(v, idx);
1044#endif // IMMER_DEEP_DESCENT
1045 }
1046 IMMER_UNREACHABLE;
1047}
1048
1049template <typename NodeT>
1050struct full_pos
1051{
1052 static constexpr auto B = NodeT::bits;
1053 static constexpr auto BL = NodeT::bits_leaf;
1054
1055 using node_t = NodeT;
1056 node_t* node_;
1057 shift_t shift_;
1058
1059 count_t count() const { return branches<B>; }
1060 node_t* node() const { return node_; }
1061 size_t size() const { return branches<B> << shift_; }
1062 shift_t shift() const { return shift_; }
1063 count_t index(size_t idx) const { return (idx >> shift_) & mask<B>; }
1064 count_t subindex(size_t idx) const { return idx >> shift_; }
1065 size_t size(count_t offset) const { return size_t{1} << shift_; }
1066 size_t size_sbh(count_t offset, size_t) const { return size_t{1} << shift_; }
1067 size_t size_before(count_t offset) const { return offset << shift_; }
1068
1069 void copy_sizes(count_t offset,
1070 count_t n,
1071 size_t init,
1072 size_t* sizes)
1073 {
1074 auto e = sizes + n;
1075 for (; sizes != e; ++sizes)
1076 init = *sizes = init + (size_t{1} << shift_);
1077 }
1078
1079 template <typename Visitor, typename... Args>
1080 void each(Visitor v, Args&&... args)
1081 {
1082 auto p = node_->inner();
1083 auto e = p + branches<B>;
1084 if (shift_ == BL) {
1085 for (; p != e; ++p) {
1086 IMMER_PREFETCH(p + 1);
1087 make_full_leaf_pos(*p).visit(v, args...);
1088 }
1089 } else {
1090 auto ss = shift_ - B;
1091 for (; p != e; ++p)
1092 make_full_pos(*p, ss).visit(v, args...);
1093 }
1094 }
1095
1096 template <typename Visitor, typename... Args>
1097 bool each_pred(Visitor v, Args&&... args)
1098 {
1099 auto p = node_->inner();
1100 auto e = p + branches<B>;
1101 if (shift_ == BL) {
1102 for (; p != e; ++p) {
1103 IMMER_PREFETCH(p + 1);
1104 if (!make_full_leaf_pos(*p).visit(v, args...))
1105 return false;
1106 }
1107 } else {
1108 auto ss = shift_ - B;
1109 for (; p != e; ++p)
1110 if (!make_full_pos(*p, ss).visit(v, args...))
1111 return false;
1112 }
1113 return true;
1114 }
1115
1116 template <typename Visitor, typename... Args>
1117 bool each_pred_zip(Visitor v, node_t* other, Args&&... args)
1118 {
1119 auto p = node_->inner();
1120 auto p2 = other->inner();
1121 auto e = p + branches<B>;
1122 if (shift_ == BL) {
1123 for (; p != e; ++p, ++p2) {
1124 IMMER_PREFETCH(p + 1);
1125 if (!make_full_leaf_pos(*p).visit(v, *p2, args...))
1126 return false;
1127 }
1128 } else {
1129 auto ss = shift_ - B;
1130 for (; p != e; ++p, ++p2)
1131 if (!make_full_pos(*p, ss).visit(v, *p2, args...))
1132 return false;
1133 }
1134 return true;
1135 }
1136
1137 template <typename Visitor, typename... Args>
1138 bool each_pred_i(Visitor v, count_t i, count_t n, Args&&... args)
1139 {
1140 auto p = node_->inner() + i;
1141 auto e = node_->inner() + n;
1142 if (shift_ == BL) {
1143 for (; p != e; ++p) {
1144 IMMER_PREFETCH(p + 1);
1145 if (!make_full_leaf_pos(*p).visit(v, args...))
1146 return false;
1147 }
1148 } else {
1149 auto ss = shift_ - B;
1150 for (; p != e; ++p)
1151 if (!make_full_pos(*p, ss).visit(v, args...))
1152 return false;
1153 }
1154 return true;
1155 }
1156
1157 template <typename Visitor, typename... Args>
1158 void each_i(Visitor v, count_t i, count_t n, Args&&... args)
1159 {
1160 auto p = node_->inner() + i;
1161 auto e = node_->inner() + n;
1162 if (shift_ == BL) {
1163 for (; p != e; ++p) {
1164 IMMER_PREFETCH(p + 1);
1165 make_full_leaf_pos(*p).visit(v, args...);
1166 }
1167 } else {
1168 auto ss = shift_ - B;
1169 for (; p != e; ++p)
1170 make_full_pos(*p, ss).visit(v, args...);
1171 }
1172 }
1173
1174 template <typename Visitor, typename... Args>
1175 bool each_pred_right(Visitor v, count_t start, Args&&... args)
1176 { return each_pred_i(v, start, branches<B>, args...); }
1177
1178 template <typename Visitor, typename... Args>
1179 bool each_pred_left(Visitor v, count_t last, Args&&... args)
1180 { return each_pred_i(v, 0, last, args...); }
1181
1182 template <typename Visitor, typename... Args>
1183 void each_sub(Visitor v, Args&&... args)
1184 { each(v, args...); }
1185
1186 template <typename Visitor, typename... Args>
1187 void each_left_sub(Visitor v, Args&&... args)
1188 { each_i(v, 0, branches<B> - 1, args...); }
1189
1190 template <typename Visitor, typename... Args>
1191 void each_right_sub(Visitor v, Args&&... args)
1192 { each_i(v, 1, branches<B>, args...); }
1193
1194 template <typename Visitor, typename... Args>
1195 void each_right(Visitor v, count_t start, Args&&... args)
1196 { each_i(v, start, branches<B>, args...); }
1197
1198 template <typename Visitor, typename... Args>
1199 void each_left(Visitor v, count_t last, Args&&... args)
1200 { each_i(v, 0, last, args...); }
1201
1202 template <typename Visitor, typename... Args>
1203 decltype(auto) towards(Visitor v, size_t idx, Args&&... args)
1204 { return towards_oh(v, idx, index(idx), args...); }
1205
1206 template <typename Visitor, typename... Args>
1207 decltype(auto) towards_oh_ch(Visitor v, size_t idx,
1208 count_t offset_hint, count_t,
1209 Args&&... args)
1210 { return towards_oh(v, idx, offset_hint, args...); }
1211
1212 template <typename Visitor, typename... Args>
1213 decltype(auto) towards_oh(Visitor v, size_t idx,
1214 count_t offset_hint,
1215 Args&&... args)
1216 {
1217 assert(offset_hint == index(idx));
1218 auto is_leaf = shift_ == BL;
1219 auto child = node_->inner() [offset_hint];
1220 return is_leaf
1221 ? make_full_leaf_pos(child).visit(v, idx, args...)
1222 : make_full_pos(child, shift_ - B).visit(v, idx, args...);
1223 }
1224
1225 template <typename Visitor, typename... Args>
1226 decltype(auto) towards_sub_oh(Visitor v, size_t idx,
1227 count_t offset_hint,
1228 Args&&... args)
1229 {
1230 assert(offset_hint == index(idx));
1231 auto is_leaf = shift_ == BL;
1232 auto child = node_->inner() [offset_hint];
1233 auto lsize = offset_hint << shift_;
1234 return is_leaf
1235 ? make_full_leaf_pos(child).visit(v, idx - lsize, args...)
1236 : make_full_pos(child, shift_ - B).visit(v, idx - lsize, args...);
1237 }
1238
1239 template <typename Visitor, typename... Args>
1240 decltype(auto) first_sub(Visitor v, Args&&... args)
1241 {
1242 auto is_leaf = shift_ == BL;
1243 auto child = node_->inner() [0];
1244 return is_leaf
1245 ? make_full_leaf_pos(child).visit(v, args...)
1246 : make_full_pos(child, shift_ - B).visit(v, args...);
1247 }
1248
1249 template <typename Visitor, typename... Args>
1250 decltype(auto) first_sub_leaf(Visitor v, Args&&... args)
1251 {
1252 assert(shift_ == BL);
1253 auto child = node_->inner() [0];
1254 return make_full_leaf_pos(child).visit(v, args...);
1255 }
1256
1257 template <typename Visitor, typename... Args>
1258 decltype(auto) first_sub_inner(Visitor v, Args&&... args)
1259 {
1260 assert(shift_ >= BL);
1261 auto child = node_->inner() [0];
1262 return make_full_pos(child, shift_ - B).visit(v, args...);
1263 }
1264
1265 template <typename Visitor, typename... Args>
1266 decltype(auto) nth_sub(count_t idx, Visitor v, Args&&... args)
1267 {
1268 assert(idx < count());
1269 auto is_leaf = shift_ == BL;
1270 auto child = node_->inner() [idx];
1271 return is_leaf
1272 ? make_full_leaf_pos(child).visit(v, args...)
1273 : make_full_pos(child, shift_ - B).visit(v, args...);
1274 }
1275
1276 template <typename Visitor, typename... Args>
1277 decltype(auto) nth_sub_leaf(count_t idx, Visitor v, Args&&... args)
1278 {
1279 assert(shift_ == BL);
1280 assert(idx < count());
1281 auto child = node_->inner() [idx];
1282 return make_full_leaf_pos(child).visit(v, args...);
1283 }
1284
1285 template <typename Visitor, typename ...Args>
1286 decltype(auto) visit(Visitor v, Args&& ...args)
1287 {
1288 return Visitor::visit_regular(*this, std::forward<Args>(args)...);
1289 }
1290};
1291
1292template <typename NodeT>
1293full_pos<NodeT> make_full_pos(NodeT* node, shift_t shift)
1294{
1295 assert(node);
1296 assert(shift >= NodeT::bits_leaf);
1297 return {node, shift};
1298}
1299
1300template <typename NodeT>
1301struct relaxed_pos
1302{
1303 static constexpr auto B = NodeT::bits;
1304 static constexpr auto BL = NodeT::bits_leaf;
1305
1306 using node_t = NodeT;
1307 using relaxed_t = typename NodeT::relaxed_t;
1308 node_t* node_;
1309 shift_t shift_;
1310 relaxed_t* relaxed_;
1311
1312 count_t count() const { return relaxed_->d.count; }
1313 node_t* node() const { return node_; }
1314 size_t size() const { return relaxed_->d.sizes[relaxed_->d.count - 1]; }
1315 shift_t shift() const { return shift_; }
1316 count_t subindex(size_t idx) const { return index(idx); }
1317 relaxed_t* relaxed() const { return relaxed_; }
1318
1319 size_t size_before(count_t offset) const
1320 { return offset ? relaxed_->d.sizes[offset - 1] : 0; }
1321
1322 size_t size(count_t offset) const
1323 { return size_sbh(offset, size_before(offset)); }
1324
1325 size_t size_sbh(count_t offset, size_t size_before_hint) const
1326 {
1327 assert(size_before_hint == size_before(offset));
1328 return relaxed_->d.sizes[offset] - size_before_hint;
1329 }
1330
1331 count_t index(size_t idx) const
1332 {
1333 auto offset = idx >> shift_;
1334 while (relaxed_->d.sizes[offset] <= idx) ++offset;
1335 return offset;
1336 }
1337
1338 void copy_sizes(count_t offset,
1339 count_t n,
1340 size_t init,
1341 size_t* sizes)
1342 {
1343 auto e = sizes + n;
1344 auto prev = size_before(offset);
1345 auto these = relaxed_->d.sizes + offset;
1346 for (; sizes != e; ++sizes, ++these) {
1347 auto this_size = *these;
1348 init = *sizes = init + (this_size - prev);
1349 prev = this_size;
1350 }
1351 }
1352
1353 template <typename Visitor, typename... Args>
1354 void each(Visitor v, Args&&... args)
1355 { each_left(v, relaxed_->d.count, args...); }
1356
1357 template <typename Visitor, typename... Args>
1358 bool each_pred(Visitor v, Args&&... args)
1359 {
1360 auto p = node_->inner();
1361 auto s = size_t{};
1362 auto n = count();
1363 if (shift_ == BL) {
1364 for (auto i = count_t{0}; i < n; ++i) {
1365 IMMER_PREFETCH(p + i + 1);
1366 if (!make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1367 .visit(v, args...))
1368 return false;
1369 s = relaxed_->d.sizes[i];
1370 }
1371 } else {
1372 auto ss = shift_ - B;
1373 for (auto i = count_t{0}; i < n; ++i) {
1374 if (!visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1375 v, args...))
1376 return false;
1377 s = relaxed_->d.sizes[i];
1378 }
1379 }
1380 return true;
1381 }
1382
1383 template <typename Visitor, typename... Args>
1384 bool each_pred_i(Visitor v, count_t i, count_t n, Args&&... args)
1385 {
1386 if (shift_ == BL) {
1387 auto p = node_->inner();
1388 auto s = i > 0 ? relaxed_->d.sizes[i - 1] : 0;
1389 for (; i < n; ++i) {
1390 IMMER_PREFETCH(p + i + 1);
1391 if (!make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1392 .visit(v, args...))
1393 return false;
1394 s = relaxed_->d.sizes[i];
1395 }
1396 } else {
1397 auto p = node_->inner();
1398 auto s = i > 0 ? relaxed_->d.sizes[i - 1] : 0;
1399 auto ss = shift_ - B;
1400 for (; i < n; ++i) {
1401 if (!visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1402 v, args...))
1403 return false;
1404 s = relaxed_->d.sizes[i];
1405 }
1406 }
1407 return true;
1408 }
1409
1410 template <typename Visitor, typename... Args>
1411 bool each_pred_left(Visitor v, count_t n, Args&&... args)
1412 {
1413 auto p = node_->inner();
1414 auto s = size_t{};
1415 if (shift_ == BL) {
1416 for (auto i = count_t{0}; i < n; ++i) {
1417 IMMER_PREFETCH(p + i + 1);
1418 if (!make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1419 .visit(v, args...))
1420 return false;
1421 s = relaxed_->d.sizes[i];
1422 }
1423 } else {
1424 auto ss = shift_ - B;
1425 for (auto i = count_t{0}; i < n; ++i) {
1426 if (!visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1427 v, args...))
1428 return false;
1429 s = relaxed_->d.sizes[i];
1430 }
1431 }
1432 return true;
1433 }
1434
1435 template <typename Visitor, typename... Args>
1436 bool each_pred_right(Visitor v, count_t start, Args&&... args)
1437 {
1438 assert(start > 0);
1439 assert(start <= relaxed_->d.count);
1440 auto s = relaxed_->d.sizes[start - 1];
1441 auto p = node_->inner();
1442 if (shift_ == BL) {
1443 for (auto i = start; i < relaxed_->d.count; ++i) {
1444 IMMER_PREFETCH(p + i + 1);
1445 if (!make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1446 .visit(v, args...))
1447 return false;
1448 s = relaxed_->d.sizes[i];
1449 }
1450 } else {
1451 auto ss = shift_ - B;
1452 for (auto i = start; i < relaxed_->d.count; ++i) {
1453 if (!visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1454 v, args...))
1455 return false;
1456 s = relaxed_->d.sizes[i];
1457 }
1458 }
1459 return true;
1460 }
1461
1462 template <typename Visitor, typename... Args>
1463 void each_i(Visitor v, count_t i, count_t n, Args&&... args)
1464 {
1465 if (shift_ == BL) {
1466 auto p = node_->inner();
1467 auto s = i > 0 ? relaxed_->d.sizes[i - 1] : 0;
1468 for (; i < n; ++i) {
1469 IMMER_PREFETCH(p + i + 1);
1470 make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1471 .visit(v, args...);
1472 s = relaxed_->d.sizes[i];
1473 }
1474 } else {
1475 auto p = node_->inner();
1476 auto s = i > 0 ? relaxed_->d.sizes[i - 1] : 0;
1477 auto ss = shift_ - B;
1478 for (; i < n; ++i) {
1479 visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1480 v, args...);
1481 s = relaxed_->d.sizes[i];
1482 }
1483 }
1484 }
1485
1486 template <typename Visitor, typename... Args>
1487 void each_sub(Visitor v, Args&&... args)
1488 { each_left(v, relaxed_->d.count, args...); }
1489
1490 template <typename Visitor, typename... Args>
1491 void each_left_sub(Visitor v, Args&&... args)
1492 { each_left(v, relaxed_->d.count - 1, args...); }
1493
1494 template <typename Visitor, typename... Args>
1495 void each_left(Visitor v, count_t n, Args&&... args)
1496 {
1497 auto p = node_->inner();
1498 auto s = size_t{};
1499 if (shift_ == BL) {
1500 for (auto i = count_t{0}; i < n; ++i) {
1501 IMMER_PREFETCH(p + i + 1);
1502 make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1503 .visit(v, args...);
1504 s = relaxed_->d.sizes[i];
1505 }
1506 } else {
1507 auto ss = shift_ - B;
1508 for (auto i = count_t{0}; i < n; ++i) {
1509 visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1510 v, args...);
1511 s = relaxed_->d.sizes[i];
1512 }
1513 }
1514 }
1515
1516 template <typename Visitor, typename... Args>
1517 void each_right_sub(Visitor v, Args&&... args)
1518 { each_right(v, 1, std::forward<Args>(args)...); }
1519
1520 template <typename Visitor, typename... Args>
1521 void each_right(Visitor v, count_t start, Args&&... args)
1522 {
1523 assert(start > 0);
1524 assert(start <= relaxed_->d.count);
1525 auto s = relaxed_->d.sizes[start - 1];
1526 auto p = node_->inner();
1527 if (shift_ == BL) {
1528 for (auto i = start; i < relaxed_->d.count; ++i) {
1529 IMMER_PREFETCH(p + i + 1);
1530 make_leaf_sub_pos(p[i], relaxed_->d.sizes[i] - s)
1531 .visit(v, args...);
1532 s = relaxed_->d.sizes[i];
1533 }
1534 } else {
1535 auto ss = shift_ - B;
1536 for (auto i = start; i < relaxed_->d.count; ++i) {
1537 visit_maybe_relaxed_sub(p[i], ss, relaxed_->d.sizes[i] - s,
1538 v, args...);
1539 s = relaxed_->d.sizes[i];
1540 }
1541 }
1542 }
1543
1544 template <typename Visitor, typename... Args>
1545 decltype(auto) towards(Visitor v, size_t idx, Args&&... args)
1546 { return towards_oh(v, idx, subindex(idx), args...); }
1547
1548 template <typename Visitor, typename... Args>
1549 decltype(auto) towards_oh(Visitor v, size_t idx,
1550 count_t offset_hint,
1551 Args&&... args)
1552 {
1553 assert(offset_hint == index(idx));
1554 auto left_size = offset_hint ? relaxed_->d.sizes[offset_hint - 1] : 0;
1555 return towards_oh_sbh(v, idx, offset_hint, left_size, args...);
1556 }
1557
1558 template <typename Visitor, typename... Args>
1559 decltype(auto) towards_oh_sbh(Visitor v, size_t idx,
1560 count_t offset_hint,
1561 size_t left_size_hint,
1562 Args&&... args)
1563 { return towards_sub_oh_sbh(v, idx, offset_hint, left_size_hint, args...); }
1564
1565 template <typename Visitor, typename... Args>
1566 decltype(auto) towards_sub_oh(Visitor v, size_t idx,
1567 count_t offset_hint,
1568 Args&&... args)
1569 {
1570 assert(offset_hint == index(idx));
1571 auto left_size = offset_hint ? relaxed_->d.sizes[offset_hint - 1] : 0;
1572 return towards_sub_oh_sbh(v, idx, offset_hint, left_size, args...);
1573 }
1574
1575 template <typename Visitor, typename... Args>
1576 decltype(auto) towards_sub_oh_sbh(Visitor v, size_t idx,
1577 count_t offset_hint,
1578 size_t left_size_hint,
1579 Args&&... args)
1580 {
1581 assert(offset_hint == index(idx));
1582 assert(left_size_hint ==
1583 (offset_hint ? relaxed_->d.sizes[offset_hint - 1] : 0));
1584 auto child = node_->inner() [offset_hint];
1585 auto is_leaf = shift_ == BL;
1586 auto next_size = relaxed_->d.sizes[offset_hint] - left_size_hint;
1587 auto next_idx = idx - left_size_hint;
1588 return is_leaf
1589 ? make_leaf_sub_pos(child, next_size).visit(
1590 v, next_idx, args...)
1591 : visit_maybe_relaxed_sub(child, shift_ - B, next_size,
1592 v, next_idx, args...);
1593 }
1594
1595 template <typename Visitor, typename... Args>
1596 decltype(auto) last_oh_csh(Visitor v,
1597 count_t offset_hint,
1598 size_t child_size_hint,
1599 Args&&... args)
1600 {
1601 assert(offset_hint == count() - 1);
1602 assert(child_size_hint == size(offset_hint));
1603 auto child = node_->inner() [offset_hint];
1604 auto is_leaf = shift_ == BL;
1605 return is_leaf
1606 ? make_leaf_sub_pos(child, child_size_hint).visit(v, args...)
1607 : visit_maybe_relaxed_sub(child, shift_ - B, child_size_hint,
1608 v, args...);
1609 }
1610
1611 template <typename Visitor, typename... Args>
1612 decltype(auto) last_sub(Visitor v, Args&&... args)
1613 {
1614 auto offset = relaxed_->d.count - 1;
1615 auto child = node_->inner() [offset];
1616 auto child_size = size(offset);
1617 auto is_leaf = shift_ == BL;
1618 return is_leaf
1619 ? make_leaf_sub_pos(child, child_size).visit(v, args...)
1620 : visit_maybe_relaxed_sub(child, shift_ - B, child_size, v, args...);
1621 }
1622
1623 template <typename Visitor, typename... Args>
1624 decltype(auto) first_sub(Visitor v, Args&&... args)
1625 {
1626 auto child = node_->inner() [0];
1627 auto child_size = relaxed_->d.sizes[0];
1628 auto is_leaf = shift_ == BL;
1629 return is_leaf
1630 ? make_leaf_sub_pos(child, child_size).visit(v, args...)
1631 : visit_maybe_relaxed_sub(child, shift_ - B, child_size, v, args...);
1632 }
1633
1634 template <typename Visitor, typename... Args>
1635 decltype(auto) first_sub_leaf(Visitor v, Args&&... args)
1636 {
1637 assert(shift_ == BL);
1638 auto child = node_->inner() [0];
1639 auto child_size = relaxed_->d.sizes[0];
1640 return make_leaf_sub_pos(child, child_size).visit(v, args...);
1641 }
1642
1643 template <typename Visitor, typename... Args>
1644 decltype(auto) first_sub_inner(Visitor v, Args&&... args)
1645 {
1646 assert(shift_ > BL);
1647 auto child = node_->inner() [0];
1648 auto child_size = relaxed_->d.sizes[0];
1649 return visit_maybe_relaxed_sub(child, shift_ - B, child_size, v, args...);
1650 }
1651
1652 template <typename Visitor, typename... Args>
1653 decltype(auto) nth_sub(count_t offset, Visitor v, Args&&... args)
1654 {
1655 auto child = node_->inner() [offset];
1656 auto child_size = size(offset);
1657 auto is_leaf = shift_ == BL;
1658 return is_leaf
1659 ? make_leaf_sub_pos(child, child_size).visit(v, args...)
1660 : visit_maybe_relaxed_sub(child, shift_ - B, child_size, v, args...);
1661 }
1662
1663 template <typename Visitor, typename... Args>
1664 decltype(auto) nth_sub_leaf(count_t offset, Visitor v, Args&&... args)
1665 {
1666 assert(shift_ == BL);
1667 auto child = node_->inner() [offset];
1668 auto child_size = size(offset);
1669 return make_leaf_sub_pos(child, child_size).visit(v, args...);
1670 }
1671
1672 template <typename Visitor, typename ...Args>
1673 decltype(auto) visit(Visitor v, Args&& ...args)
1674 {
1675 return Visitor::visit_relaxed(*this, std::forward<Args>(args)...);
1676 }
1677};
1678
1679template <typename Pos>
1680using is_relaxed = std::is_same<relaxed_pos<typename std::decay_t<Pos>::node_t>,
1681 std::decay_t<Pos>>;
1682
1683template <typename Pos>
1684constexpr auto is_relaxed_v = is_relaxed<Pos>::value;
1685
1686template <typename NodeT>
1687relaxed_pos<NodeT> make_relaxed_pos(NodeT* node,
1688 shift_t shift,
1689 typename NodeT::relaxed_t* relaxed)
1690{
1691 assert(node);
1692 assert(relaxed);
1693 assert(shift >= NodeT::bits_leaf);
1694 return {node, shift, relaxed};
1695}
1696
1697template <typename NodeT, typename Visitor, typename... Args>
1698decltype(auto) visit_maybe_relaxed_sub(NodeT* node, shift_t shift, size_t size,
1699 Visitor v, Args&& ...args)
1700{
1701 assert(node);
1702 auto relaxed = node->relaxed();
1703 if (relaxed) {
1704 assert(size == relaxed->d.sizes[relaxed->d.count - 1]);
1705 return make_relaxed_pos(node, shift, relaxed)
1706 .visit(v, std::forward<Args>(args)...);
1707 } else {
1708 return make_regular_sub_pos(node, shift, size)
1709 .visit(v, std::forward<Args>(args)...);
1710 }
1711}
1712
1713template <typename NodeT, shift_t Shift,
1714 bits_t B = NodeT::bits,
1715 bits_t BL = NodeT::bits_leaf>
1716struct relaxed_descent_pos
1717{
1718 static_assert(Shift > 0, "not leaf...");
1719
1720 using node_t = NodeT;
1721 using relaxed_t = typename NodeT::relaxed_t;
1722 node_t* node_;
1723 relaxed_t* relaxed_;
1724
1725 count_t count() const { return relaxed_->d.count; }
1726 node_t* node() const { return node_; }
1727 shift_t shift() const { return Shift; }
1728 size_t size() const { return relaxed_->d.sizes[relaxed_->d.count - 1]; }
1729
1730 count_t index(size_t idx) const
1731 {
1732 // make gcc happy
1733#if !defined(_MSC_VER)
1734#pragma GCC diagnostic push
1735#pragma GCC diagnostic ignored "-Wshift-count-overflow"
1736#endif
1737 auto offset = idx >> Shift;
1738#if !defined(_MSC_VER)
1739#pragma GCC diagnostic pop
1740#endif
1741 while (relaxed_->d.sizes[offset] <= idx) ++offset;
1742 return offset;
1743 }
1744
1745 template <typename Visitor>
1746 decltype(auto) descend(Visitor v, size_t idx)
1747 {
1748 auto offset = index(idx);
1749 auto child = node_->inner() [offset];
1750 auto left_size = offset ? relaxed_->d.sizes[offset - 1] : 0;
1751 auto next_idx = idx - left_size;
1752 auto r = child->relaxed();
1753 return r
1754 ? relaxed_descent_pos<NodeT, Shift - B>{child, r}.visit(v, next_idx)
1755 : regular_descent_pos<NodeT, Shift - B>{child}.visit(v, next_idx);
1756 }
1757
1758 template <typename Visitor, typename ...Args>
1759 decltype(auto) visit(Visitor v, Args&& ...args)
1760 {
1761 return Visitor::visit_relaxed(*this, std::forward<Args>(args)...);
1762 }
1763};
1764
1765template <typename NodeT, bits_t B, bits_t BL>
1766struct relaxed_descent_pos<NodeT, BL, B, BL>
1767{
1768 using node_t = NodeT;
1769 using relaxed_t = typename NodeT::relaxed_t;
1770 node_t* node_;
1771 relaxed_t* relaxed_;
1772
1773 count_t count() const { return relaxed_->d.count; }
1774 node_t* node() const { return node_; }
1775 shift_t shift() const { return BL; }
1776 size_t size() const { return relaxed_->d.sizes[relaxed_->d.count - 1]; }
1777
1778 count_t index(size_t idx) const
1779 {
1780 auto offset = (idx >> BL) & mask<B>;
1781 while (relaxed_->d.sizes[offset] <= idx) ++offset;
1782 return offset;
1783 }
1784
1785 template <typename Visitor>
1786 decltype(auto) descend(Visitor v, size_t idx)
1787 {
1788 auto offset = index(idx);
1789 auto child = node_->inner() [offset];
1790 auto left_size = offset ? relaxed_->d.sizes[offset - 1] : 0;
1791 auto next_idx = idx - left_size;
1792 return leaf_descent_pos<NodeT>{child}.visit(v, next_idx);
1793 }
1794
1795 template <typename Visitor, typename ...Args>
1796 decltype(auto) visit(Visitor v, Args&& ...args)
1797 {
1798 return Visitor::visit_relaxed(*this, std::forward<Args>(args)...);
1799 }
1800};
1801
1802template <typename NodeT, typename Visitor, typename... Args>
1803decltype(auto) visit_maybe_relaxed_descent(NodeT* node, shift_t shift,
1804 Visitor v, size_t idx)
1805{
1806 constexpr auto B = NodeT::bits;
1807 constexpr auto BL = NodeT::bits_leaf;
1808 assert(node);
1809 assert(shift >= BL);
1810 auto r = node->relaxed();
1811 if (r) {
1812 switch (shift) {
1813 case BL + B * 0: return relaxed_descent_pos<NodeT, BL + B * 0>{node, r}.visit(v, idx);
1814 case BL + B * 1: return relaxed_descent_pos<NodeT, BL + B * 1>{node, r}.visit(v, idx);
1815 case BL + B * 2: return relaxed_descent_pos<NodeT, BL + B * 2>{node, r}.visit(v, idx);
1816 case BL + B * 3: return relaxed_descent_pos<NodeT, BL + B * 3>{node, r}.visit(v, idx);
1817 case BL + B * 4: return relaxed_descent_pos<NodeT, BL + B * 4>{node, r}.visit(v, idx);
1818 case BL + B * 5: return relaxed_descent_pos<NodeT, BL + B * 5>{node, r}.visit(v, idx);
1819#if IMMER_DESCENT_DEEP
1820 default:
1821 for (auto level = shift; level != endshift<B, BL>; level -= B) {
1822 auto r = node->relaxed();
1823 if (r) {
1824 auto node_idx = (idx >> level) & mask<B>;
1825 while (r->d.sizes[node_idx] <= idx) ++node_idx;
1826 if (node_idx) idx -= r->d.sizes[node_idx - 1];
1827 node = node->inner() [node_idx];
1828 } else {
1829 do {
1830 node = node->inner() [(idx >> level) & mask<B>];
1831 } while ((level -= B) != endshift<B, BL>);
1832 return make_leaf_descent_pos(node).visit(v, idx);
1833 }
1834 }
1835 return make_leaf_descent_pos(node).visit(v, idx);
1836#endif // IMMER_DESCENT_DEEP
1837 }
1838 IMMER_UNREACHABLE;
1839 } else {
1840 return visit_regular_descent(node, shift, v, idx);
1841 }
1842}
1843
1844} // namespace rbts
1845} // namespace detail
1846} // namespace immer
1847