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 | |
18 | namespace immer { |
19 | namespace detail { |
20 | namespace rbts { |
21 | |
22 | template <typename Pos> |
23 | constexpr auto bits = std::decay_t<Pos>::node_t::bits; |
24 | |
25 | template <typename Pos> |
26 | constexpr auto bits_leaf = std::decay_t<Pos>::node_t::bits_leaf; |
27 | |
28 | template <typename Pos> |
29 | using node_type = typename std::decay<Pos>::type::node_t; |
30 | |
31 | template <typename Pos> |
32 | using edit_type = typename std::decay<Pos>::type::node_t::edit_t; |
33 | |
34 | template <typename NodeT> |
35 | struct 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 | |
57 | template <typename NodeT> |
58 | empty_regular_pos<NodeT> make_empty_regular_pos(NodeT* node) |
59 | { |
60 | return {node}; |
61 | } |
62 | |
63 | template <typename NodeT> |
64 | struct 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 | |
81 | template <typename NodeT> |
82 | empty_leaf_pos<NodeT> make_empty_leaf_pos(NodeT* node) |
83 | { |
84 | assert(node); |
85 | return {node}; |
86 | } |
87 | |
88 | template <typename NodeT> |
89 | struct 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 | |
112 | template <typename NodeT> |
113 | leaf_pos<NodeT> make_leaf_pos(NodeT* node, size_t size) |
114 | { |
115 | assert(node); |
116 | assert(size > 0); |
117 | return {node, size}; |
118 | } |
119 | |
120 | template <typename NodeT> |
121 | struct 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 | |
144 | template <typename NodeT> |
145 | leaf_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 | |
152 | template <typename NodeT> |
153 | struct 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 | |
175 | template <typename NodeT> |
176 | leaf_descent_pos<NodeT> make_leaf_descent_pos(NodeT* node) |
177 | { |
178 | assert(node); |
179 | return {node}; |
180 | } |
181 | |
182 | template <typename NodeT> |
183 | struct 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 | |
205 | template <typename NodeT> |
206 | full_leaf_pos<NodeT> make_full_leaf_pos(NodeT* node) |
207 | { |
208 | assert(node); |
209 | return {node}; |
210 | } |
211 | |
212 | template <typename NodeT> |
213 | struct 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 | |
301 | template <typename Pos, typename Visitor, typename... Args> |
302 | void 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 | |
323 | template <typename Pos, typename Visitor, typename... Args> |
324 | bool 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 | |
347 | template <typename Pos, typename Visitor, typename... Args> |
348 | bool 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 | |
374 | template <typename Pos, typename Visitor, typename... Args> |
375 | bool 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 | |
425 | template <typename Pos, typename Visitor, typename... Args> |
426 | bool 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 | |
450 | template <typename Pos, typename Visitor, typename... Args> |
451 | bool 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 | |
485 | template <typename Pos, typename Visitor, typename... Args> |
486 | void 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 | |
529 | template <typename Pos, typename Visitor, typename... Args> |
530 | void 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 | |
551 | template <typename Pos, typename Visitor, typename... Args> |
552 | void 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 | |
581 | template <typename Pos, typename Visitor, typename... Args> |
582 | decltype(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 | |
603 | template <typename Pos, typename Visitor, typename... Args> |
604 | decltype(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 | |
629 | template <typename Pos, typename Visitor, typename... Args> |
630 | decltype(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 | |
644 | template <typename NodeT> |
645 | regular_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 | |
655 | struct 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 | |
669 | template <typename NodeT> |
670 | struct 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 | |
710 | template <typename NodeT> |
711 | auto 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 | |
719 | template <typename NodeT> |
720 | struct 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 | |
949 | template <typename NodeT> |
950 | regular_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 | |
961 | template <typename NodeT, shift_t Shift, |
962 | bits_t B = NodeT::bits, |
963 | bits_t BL = NodeT::bits_leaf> |
964 | struct 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 | |
999 | template <typename NodeT, bits_t B, bits_t BL> |
1000 | struct 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 | |
1024 | template <typename NodeT, typename Visitor> |
1025 | decltype(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 | |
1049 | template <typename NodeT> |
1050 | struct 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 | |
1292 | template <typename NodeT> |
1293 | full_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 | |
1300 | template <typename NodeT> |
1301 | struct 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 | |
1679 | template <typename Pos> |
1680 | using is_relaxed = std::is_same<relaxed_pos<typename std::decay_t<Pos>::node_t>, |
1681 | std::decay_t<Pos>>; |
1682 | |
1683 | template <typename Pos> |
1684 | constexpr auto is_relaxed_v = is_relaxed<Pos>::value; |
1685 | |
1686 | template <typename NodeT> |
1687 | relaxed_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 | |
1697 | template <typename NodeT, typename Visitor, typename... Args> |
1698 | decltype(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 | |
1713 | template <typename NodeT, shift_t Shift, |
1714 | bits_t B = NodeT::bits, |
1715 | bits_t BL = NodeT::bits_leaf> |
1716 | struct 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 | |
1765 | template <typename NodeT, bits_t B, bits_t BL> |
1766 | struct 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 | |
1802 | template <typename NodeT, typename Visitor, typename... Args> |
1803 | decltype(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 | |