Line data Source code
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/combine_standard_layout.hpp>
13 : #include <immer/detail/hamts/bits.hpp>
14 : #include <immer/detail/util.hpp>
15 :
16 : #include <cassert>
17 : #include <cstddef>
18 :
19 : namespace immer {
20 : namespace detail {
21 : namespace hamts {
22 :
23 : template <typename T,
24 : typename Hash,
25 : typename Equal,
26 : typename MemoryPolicy,
27 : bits_t B>
28 36715 : struct node
29 : {
30 : using node_t = node;
31 :
32 : using memory = MemoryPolicy;
33 : using heap_policy = typename memory::heap;
34 : using heap = typename heap_policy::type;
35 : using transience = typename memory::transience_t;
36 : using refs_t = typename memory::refcount;
37 : using ownee_t = typename transience::ownee;
38 : using edit_t = typename transience::edit;
39 : using value_t = T;
40 : using bitmap_t = typename get_bitmap_type<B>::type;
41 :
42 : enum class kind_t
43 : {
44 : collision,
45 : inner
46 : };
47 :
48 : struct collision_t
49 : {
50 : count_t count;
51 : aligned_storage_for<T> buffer;
52 : };
53 :
54 : struct values_data_t
55 : {
56 : aligned_storage_for<T> buffer;
57 : };
58 :
59 : using values_t = combine_standard_layout_t<values_data_t, refs_t>;
60 :
61 : struct inner_t
62 : {
63 : bitmap_t nodemap;
64 : bitmap_t datamap;
65 : values_t* values;
66 : aligned_storage_for<node_t*> buffer;
67 : };
68 :
69 : union data_t
70 : {
71 : inner_t inner;
72 : collision_t collision;
73 : };
74 :
75 : struct impl_data_t
76 : {
77 : #if IMMER_TAGGED_NODE
78 : kind_t kind;
79 : #endif
80 : data_t data;
81 : };
82 :
83 : using impl_t = combine_standard_layout_t<impl_data_t, refs_t>;
84 :
85 : impl_t impl;
86 :
87 60478 : constexpr static std::size_t sizeof_values_n(count_t count)
88 : {
89 120956 : return std::max(sizeof(values_t),
90 120956 : immer_offsetof(values_t, d.buffer) +
91 72329 : sizeof(values_data_t::buffer) * count);
92 : }
93 :
94 0 : constexpr static std::size_t sizeof_collision_n(count_t count)
95 : {
96 : return immer_offsetof(impl_t, d.data.collision.buffer) +
97 0 : sizeof(collision_t::buffer) * count;
98 : }
99 :
100 72266 : constexpr static std::size_t sizeof_inner_n(count_t count)
101 : {
102 72266 : return immer_offsetof(impl_t, d.data.inner.buffer) +
103 72266 : sizeof(inner_t::buffer) * count;
104 : }
105 :
106 : #if IMMER_TAGGED_NODE
107 3567019 : kind_t kind() const { return impl.d.kind; }
108 : #endif
109 :
110 518279 : auto values()
111 : {
112 518279 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
113 518279 : assert(impl.d.data.inner.values);
114 518279 : return (T*) &impl.d.data.inner.values->d.buffer;
115 : }
116 :
117 : auto values() const
118 : {
119 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
120 : assert(impl.d.data.inner.values);
121 : return (const T*) &impl.d.data.inner.values->d.buffer;
122 : }
123 :
124 239601 : auto children()
125 : {
126 103736 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
127 133986 : return (node_t**) &impl.d.data.inner.buffer;
128 : }
129 :
130 : auto children() const
131 : {
132 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
133 : return (const node_t* const*) &impl.d.data.inner.buffer;
134 : }
135 :
136 1383572 : auto datamap() const
137 : {
138 119526 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
139 911832 : return impl.d.data.inner.datamap;
140 : }
141 :
142 1228179 : auto nodemap() const
143 : {
144 983164 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
145 982717 : return impl.d.data.inner.nodemap;
146 : }
147 :
148 183408 : auto data_count() const
149 : {
150 132028 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
151 154449 : return popcount(datamap());
152 : }
153 :
154 258570 : auto data_count(bitmap_t bit) const
155 : {
156 728 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
157 253316 : return popcount(static_cast<bitmap_t>(datamap() & (bit - 1)));
158 : }
159 :
160 140893 : auto children_count() const
161 : {
162 35551 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
163 105342 : return popcount(nodemap());
164 : }
165 :
166 71431 : auto children_count(bitmap_t bit) const
167 : {
168 292 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
169 71431 : return popcount(static_cast<bitmap_t>(nodemap() & (bit - 1)));
170 : }
171 :
172 0 : auto collision_count() const
173 : {
174 0 : IMMER_ASSERT_TAGGED(kind() == kind_t::collision);
175 0 : return impl.d.data.collision.count;
176 : }
177 :
178 0 : T* collisions()
179 : {
180 0 : IMMER_ASSERT_TAGGED(kind() == kind_t::collision);
181 0 : return (T*) &impl.d.data.collision.buffer;
182 : }
183 :
184 : const T* collisions() const
185 : {
186 : IMMER_ASSERT_TAGGED(kind() == kind_t::collision);
187 : return (const T*) &impl.d.data.collision.buffer;
188 : }
189 :
190 35321 : static refs_t& refs(const values_t* x)
191 : {
192 40403 : return auto_const_cast(get<refs_t>(*x));
193 : }
194 : static const ownee_t& ownee(const values_t* x) { return get<ownee_t>(*x); }
195 : static ownee_t& ownee(values_t* x) { return get<ownee_t>(*x); }
196 :
197 4338053 : static refs_t& refs(const node_t* x)
198 : {
199 4338053 : return auto_const_cast(get<refs_t>(x->impl));
200 : }
201 : static const ownee_t& ownee(const node_t* x)
202 : {
203 : return get<ownee_t>(x->impl);
204 : }
205 : static ownee_t& ownee(node_t* x) { return get<ownee_t>(x->impl); }
206 :
207 36715 : static node_t* make_inner_n(count_t n)
208 : {
209 36715 : assert(n <= branches<B>);
210 36715 : auto m = heap::allocate(sizeof_inner_n(n));
211 36715 : auto p = new (m) node_t;
212 : assert(p == (node_t*) m);
213 : #if IMMER_TAGGED_NODE
214 36715 : p->impl.d.kind = node_t::kind_t::inner;
215 : #endif
216 36715 : p->impl.d.data.inner.nodemap = 0;
217 36715 : p->impl.d.data.inner.datamap = 0;
218 36715 : p->impl.d.data.inner.values = nullptr;
219 36715 : return p;
220 : }
221 :
222 5205 : static node_t* make_inner_n(count_t n, values_t* values)
223 : {
224 5205 : auto p = make_inner_n(n);
225 5205 : if (values) {
226 5082 : p->impl.d.data.inner.values = values;
227 5082 : refs(values).inc();
228 : }
229 5205 : return p;
230 : }
231 :
232 30308 : static node_t* make_inner_n(count_t n, count_t nv)
233 : {
234 30308 : assert(nv <= branches<B>);
235 30308 : auto p = make_inner_n(n);
236 30308 : if (nv) {
237 : IMMER_TRY {
238 30239 : p->impl.d.data.inner.values =
239 30239 : new (heap::allocate(sizeof_values_n(nv))) values_t{};
240 : }
241 0 : IMMER_CATCH (...) {
242 0 : deallocate_inner(p, n);
243 0 : IMMER_RETHROW;
244 : }
245 : }
246 30308 : return p;
247 : }
248 :
249 38 : static node_t* make_inner_n(count_t n, count_t idx, node_t* child)
250 : {
251 38 : assert(n >= 1);
252 38 : auto p = make_inner_n(n);
253 38 : p->impl.d.data.inner.nodemap = bitmap_t{1u} << idx;
254 38 : p->children()[0] = child;
255 38 : return p;
256 : }
257 :
258 13 : static node_t* make_inner_n(count_t n, bitmap_t bitmap, T x)
259 : {
260 13 : auto p = make_inner_n(n, 1);
261 13 : p->impl.d.data.inner.datamap = bitmap;
262 : IMMER_TRY {
263 13 : new (p->values()) T{std::move(x)};
264 : }
265 : IMMER_CATCH (...) {
266 : deallocate_inner(p, n, 1);
267 : IMMER_RETHROW;
268 : }
269 13 : return p;
270 : }
271 :
272 : static node_t*
273 1336 : make_inner_n(count_t n, count_t idx1, T x1, count_t idx2, T x2)
274 : {
275 1336 : assert(idx1 != idx2);
276 1336 : auto p = make_inner_n(n, 2);
277 1336 : p->impl.d.data.inner.datamap =
278 1336 : (bitmap_t{1u} << idx1) | (bitmap_t{1u} << idx2);
279 4008 : auto assign = [&](auto&& x1, auto&& x2) {
280 1336 : auto vp = p->values();
281 : IMMER_TRY {
282 1336 : new (vp) T{std::move(x1)};
283 : IMMER_TRY {
284 1336 : new (vp + 1) T{std::move(x2)};
285 : }
286 : IMMER_CATCH (...) {
287 : vp->~T();
288 : IMMER_RETHROW;
289 : }
290 : }
291 : IMMER_CATCH (...) {
292 : deallocate_inner(p, n, 2);
293 : IMMER_RETHROW;
294 : }
295 : };
296 1336 : if (idx1 < idx2)
297 794 : assign(x1, x2);
298 : else
299 542 : assign(x2, x1);
300 1336 : return p;
301 : }
302 :
303 0 : static node_t* make_collision_n(count_t n)
304 : {
305 0 : auto m = heap::allocate(sizeof_collision_n(n));
306 0 : auto p = new (m) node_t;
307 : #if IMMER_TAGGED_NODE
308 0 : p->impl.d.kind = node_t::kind_t::collision;
309 : #endif
310 0 : p->impl.d.data.collision.count = n;
311 0 : return p;
312 : }
313 :
314 0 : static node_t* make_collision(T v1, T v2)
315 : {
316 0 : auto m = heap::allocate(sizeof_collision_n(2));
317 0 : auto p = new (m) node_t;
318 : #if IMMER_TAGGED_NODE
319 0 : p->impl.d.kind = node_t::kind_t::collision;
320 : #endif
321 0 : p->impl.d.data.collision.count = 2;
322 0 : auto cols = p->collisions();
323 : IMMER_TRY {
324 0 : new (cols) T{std::move(v1)};
325 : IMMER_TRY {
326 0 : new (cols + 1) T{std::move(v2)};
327 : }
328 : IMMER_CATCH (...) {
329 : cols->~T();
330 : IMMER_RETHROW;
331 : }
332 : }
333 : IMMER_CATCH (...) {
334 : deallocate_collision(p, 2);
335 : IMMER_RETHROW;
336 : }
337 0 : return p;
338 : }
339 :
340 0 : static node_t* copy_collision_insert(node_t* src, T v)
341 : {
342 0 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::collision);
343 0 : auto n = src->collision_count();
344 0 : auto dst = make_collision_n(n + 1);
345 0 : auto srcp = src->collisions();
346 0 : auto dstp = dst->collisions();
347 : IMMER_TRY {
348 0 : new (dstp) T{std::move(v)};
349 : IMMER_TRY {
350 0 : std::uninitialized_copy(srcp, srcp + n, dstp + 1);
351 : }
352 : IMMER_CATCH (...) {
353 : dstp->~T();
354 : IMMER_RETHROW;
355 : }
356 : }
357 : IMMER_CATCH (...) {
358 : deallocate_collision(dst, n + 1);
359 : IMMER_RETHROW;
360 : }
361 0 : return dst;
362 : }
363 :
364 0 : static node_t* copy_collision_remove(node_t* src, T* v)
365 : {
366 0 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::collision);
367 0 : assert(src->collision_count() > 1);
368 0 : auto n = src->collision_count();
369 0 : auto dst = make_collision_n(n - 1);
370 0 : auto srcp = src->collisions();
371 0 : auto dstp = dst->collisions();
372 : IMMER_TRY {
373 0 : dstp = std::uninitialized_copy(srcp, v, dstp);
374 : IMMER_TRY {
375 0 : std::uninitialized_copy(v + 1, srcp + n, dstp);
376 : }
377 : IMMER_CATCH (...) {
378 : destroy(dst->collisions(), dstp);
379 : IMMER_RETHROW;
380 : }
381 : }
382 : IMMER_CATCH (...) {
383 : deallocate_collision(dst, n - 1);
384 : IMMER_RETHROW;
385 : }
386 0 : return dst;
387 : }
388 :
389 0 : static node_t* copy_collision_replace(node_t* src, T* pos, T v)
390 : {
391 0 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::collision);
392 0 : auto n = src->collision_count();
393 0 : auto dst = make_collision_n(n);
394 0 : auto srcp = src->collisions();
395 0 : auto dstp = dst->collisions();
396 0 : assert(pos >= srcp && pos < srcp + n);
397 : IMMER_TRY {
398 0 : new (dstp) T{std::move(v)};
399 : IMMER_TRY {
400 0 : dstp = std::uninitialized_copy(srcp, pos, dstp + 1);
401 : IMMER_TRY {
402 0 : std::uninitialized_copy(pos + 1, srcp + n, dstp);
403 : }
404 : IMMER_CATCH (...) {
405 : destroy(dst->collisions(), dstp);
406 : IMMER_RETHROW;
407 : }
408 : }
409 : IMMER_CATCH (...) {
410 : dst->collisions()->~T();
411 : IMMER_RETHROW;
412 : }
413 : }
414 : IMMER_CATCH (...) {
415 : deallocate_collision(dst, n);
416 : IMMER_RETHROW;
417 : }
418 0 : return dst;
419 : }
420 :
421 : static node_t*
422 5205 : copy_inner_replace(node_t* src, count_t offset, node_t* child)
423 : {
424 5205 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
425 5205 : auto n = src->children_count();
426 5205 : auto dst = make_inner_n(n, src->impl.d.data.inner.values);
427 5205 : auto srcp = src->children();
428 5205 : auto dstp = dst->children();
429 5205 : dst->impl.d.data.inner.datamap = src->datamap();
430 5205 : dst->impl.d.data.inner.nodemap = src->nodemap();
431 5205 : std::uninitialized_copy(srcp, srcp + n, dstp);
432 5205 : inc_nodes(srcp, n);
433 10410 : srcp[offset]->dec_unsafe();
434 5205 : dstp[offset] = child;
435 5205 : return dst;
436 : }
437 :
438 21974 : static node_t* copy_inner_replace_value(node_t* src, count_t offset, T v)
439 : {
440 21974 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
441 21974 : assert(offset < src->data_count());
442 21974 : auto n = src->children_count();
443 21974 : auto nv = src->data_count();
444 21974 : auto dst = make_inner_n(n, nv);
445 21974 : dst->impl.d.data.inner.datamap = src->datamap();
446 21974 : dst->impl.d.data.inner.nodemap = src->nodemap();
447 : IMMER_TRY {
448 43948 : std::uninitialized_copy(
449 21974 : src->values(), src->values() + nv, dst->values());
450 : IMMER_TRY {
451 43948 : dst->values()[offset] = std::move(v);
452 : }
453 : IMMER_CATCH (...) {
454 : destroy_n(dst->values(), nv);
455 : IMMER_RETHROW;
456 : }
457 : }
458 : IMMER_CATCH (...) {
459 : deallocate_inner(dst, n, nv);
460 : IMMER_RETHROW;
461 : }
462 21974 : inc_nodes(src->children(), n);
463 21974 : std::uninitialized_copy(
464 21974 : src->children(), src->children() + n, dst->children());
465 21974 : return dst;
466 : }
467 :
468 1336 : static node_t* copy_inner_replace_merged(node_t* src,
469 : bitmap_t bit,
470 : count_t voffset,
471 : node_t* node)
472 : {
473 1336 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
474 1336 : assert(!(src->nodemap() & bit));
475 1336 : assert(src->datamap() & bit);
476 1336 : assert(voffset == src->data_count(bit));
477 1336 : auto n = src->children_count();
478 1336 : auto nv = src->data_count();
479 1336 : auto dst = make_inner_n(n + 1, nv - 1);
480 1336 : auto noffset = src->children_count(bit);
481 1336 : dst->impl.d.data.inner.datamap = src->datamap() & ~bit;
482 1336 : dst->impl.d.data.inner.nodemap = src->nodemap() | bit;
483 1336 : if (nv > 1) {
484 : IMMER_TRY {
485 1267 : std::uninitialized_copy(
486 1267 : src->values(), src->values() + voffset, dst->values());
487 : IMMER_TRY {
488 1336 : std::uninitialized_copy(src->values() + voffset + 1,
489 1267 : src->values() + nv,
490 1267 : dst->values() + voffset);
491 : }
492 : IMMER_CATCH (...) {
493 : destroy_n(dst->values(), voffset);
494 : IMMER_RETHROW;
495 : }
496 : }
497 : IMMER_CATCH (...) {
498 : deallocate_inner(dst, n + 1, nv - 1);
499 : IMMER_RETHROW;
500 : }
501 : }
502 1336 : inc_nodes(src->children(), n);
503 1336 : std::uninitialized_copy(
504 1336 : src->children(), src->children() + noffset, dst->children());
505 1336 : std::uninitialized_copy(src->children() + noffset,
506 1336 : src->children() + n,
507 1336 : dst->children() + noffset + 1);
508 1336 : dst->children()[noffset] = node;
509 1336 : return dst;
510 : }
511 :
512 92 : static node_t* copy_inner_replace_inline(node_t* src,
513 : bitmap_t bit,
514 : count_t noffset,
515 : T value)
516 : {
517 92 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
518 92 : assert(!(src->datamap() & bit));
519 92 : assert(src->nodemap() & bit);
520 92 : assert(noffset == src->children_count(bit));
521 92 : auto n = src->children_count();
522 92 : auto nv = src->data_count();
523 92 : auto dst = make_inner_n(n - 1, nv + 1);
524 92 : auto voffset = src->data_count(bit);
525 92 : dst->impl.d.data.inner.nodemap = src->nodemap() & ~bit;
526 92 : dst->impl.d.data.inner.datamap = src->datamap() | bit;
527 : IMMER_TRY {
528 92 : if (nv)
529 184 : std::uninitialized_copy(
530 92 : src->values(), src->values() + voffset, dst->values());
531 : IMMER_TRY {
532 92 : new (dst->values() + voffset) T{std::move(value)};
533 : IMMER_TRY {
534 92 : if (nv)
535 92 : std::uninitialized_copy(src->values() + voffset,
536 92 : src->values() + nv,
537 92 : dst->values() + voffset + 1);
538 : }
539 : IMMER_CATCH (...) {
540 : dst->values()[voffset].~T();
541 : IMMER_RETHROW;
542 : }
543 : }
544 : IMMER_CATCH (...) {
545 : destroy_n(dst->values(), voffset);
546 : IMMER_RETHROW;
547 : }
548 : }
549 : IMMER_CATCH (...) {
550 : deallocate_inner(dst, n - 1, nv + 1);
551 : IMMER_RETHROW;
552 : }
553 92 : inc_nodes(src->children(), n);
554 92 : src->children()[noffset]->dec_unsafe();
555 92 : std::uninitialized_copy(
556 92 : src->children(), src->children() + noffset, dst->children());
557 276 : std::uninitialized_copy(src->children() + noffset + 1,
558 92 : src->children() + n,
559 92 : dst->children() + noffset);
560 92 : return dst;
561 : }
562 :
563 : static node_t*
564 303 : copy_inner_remove_value(node_t* src, bitmap_t bit, count_t voffset)
565 : {
566 303 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
567 303 : assert(!(src->nodemap() & bit));
568 303 : assert(src->datamap() & bit);
569 303 : assert(voffset == src->data_count(bit));
570 303 : auto n = src->children_count();
571 303 : auto nv = src->data_count();
572 303 : auto dst = make_inner_n(n, nv - 1);
573 303 : dst->impl.d.data.inner.datamap = src->datamap() & ~bit;
574 303 : dst->impl.d.data.inner.nodemap = src->nodemap();
575 303 : if (nv > 1) {
576 : IMMER_TRY {
577 303 : std::uninitialized_copy(
578 303 : src->values(), src->values() + voffset, dst->values());
579 : IMMER_TRY {
580 303 : std::uninitialized_copy(src->values() + voffset + 1,
581 303 : src->values() + nv,
582 303 : dst->values() + voffset);
583 : }
584 : IMMER_CATCH (...) {
585 : destroy_n(dst->values(), voffset);
586 : IMMER_RETHROW;
587 : }
588 : }
589 : IMMER_CATCH (...) {
590 : deallocate_inner(dst, n, nv - 1);
591 : IMMER_RETHROW;
592 : }
593 : }
594 303 : inc_nodes(src->children(), n);
595 303 : std::uninitialized_copy(
596 303 : src->children(), src->children() + n, dst->children());
597 303 : return dst;
598 : }
599 :
600 5254 : static node_t* copy_inner_insert_value(node_t* src, bitmap_t bit, T v)
601 : {
602 5254 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
603 5254 : auto n = src->children_count();
604 5254 : auto nv = src->data_count();
605 5254 : auto offset = src->data_count(bit);
606 5254 : auto dst = make_inner_n(n, nv + 1);
607 5254 : dst->impl.d.data.inner.datamap = src->datamap() | bit;
608 5254 : dst->impl.d.data.inner.nodemap = src->nodemap();
609 : IMMER_TRY {
610 5254 : if (nv)
611 9872 : std::uninitialized_copy(
612 4618 : src->values(), src->values() + offset, dst->values());
613 : IMMER_TRY {
614 5254 : new (dst->values() + offset) T{std::move(v)};
615 : IMMER_TRY {
616 5254 : if (nv)
617 5254 : std::uninitialized_copy(src->values() + offset,
618 4618 : src->values() + nv,
619 4618 : dst->values() + offset + 1);
620 : }
621 : IMMER_CATCH (...) {
622 : dst->values()[offset].~T();
623 : IMMER_RETHROW;
624 : }
625 : }
626 : IMMER_CATCH (...) {
627 : destroy_n(dst->values(), offset);
628 : IMMER_RETHROW;
629 : }
630 : }
631 : IMMER_CATCH (...) {
632 : deallocate_inner(dst, n, nv + 1);
633 : IMMER_RETHROW;
634 : }
635 5254 : inc_nodes(src->children(), n);
636 5254 : std::uninitialized_copy(
637 5254 : src->children(), src->children() + n, dst->children());
638 5254 : return dst;
639 : }
640 :
641 : static node_t*
642 1374 : make_merged(shift_t shift, T v1, hash_t hash1, T v2, hash_t hash2)
643 : {
644 1374 : if (shift < max_shift<B>) {
645 1374 : auto idx1 = hash1 & (mask<B> << shift);
646 1374 : auto idx2 = hash2 & (mask<B> << shift);
647 1374 : if (idx1 == idx2) {
648 74 : auto merged = make_merged(
649 38 : shift + B, std::move(v1), hash1, std::move(v2), hash2);
650 : IMMER_TRY {
651 38 : return make_inner_n(1, idx1 >> shift, merged);
652 : }
653 0 : IMMER_CATCH (...) {
654 0 : delete_deep_shift(merged, shift + B);
655 0 : IMMER_RETHROW;
656 : }
657 : } else {
658 1336 : return make_inner_n(0,
659 1336 : idx1 >> shift,
660 1336 : std::move(v1),
661 1336 : idx2 >> shift,
662 1336 : std::move(v2));
663 : }
664 : } else {
665 0 : return make_collision(std::move(v1), std::move(v2));
666 : }
667 : }
668 :
669 2121159 : node_t* inc()
670 : {
671 2121159 : refs(this).inc();
672 572949 : return this;
673 : }
674 :
675 : const node_t* inc() const
676 : {
677 : refs(this).inc();
678 : return this;
679 : }
680 :
681 2181504 : bool dec() const { return refs(this).dec(); }
682 5297 : void dec_unsafe() const { refs(this).dec_unsafe(); }
683 :
684 34164 : static void inc_nodes(node_t** p, count_t n)
685 : {
686 64260 : for (auto i = p, e = i + n; i != e; ++i)
687 30096 : refs(*i).inc();
688 34164 : }
689 :
690 30239 : static void delete_values(values_t* p, count_t n)
691 : {
692 30239 : assert(p);
693 30239 : deallocate_values(p, n);
694 30239 : }
695 :
696 35551 : static void delete_inner(node_t* p)
697 : {
698 35551 : assert(p);
699 35551 : IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner);
700 35551 : auto vp = p->impl.d.data.inner.values;
701 35551 : if (vp && refs(vp).dec())
702 30239 : delete_values(vp, p->data_count());
703 71102 : deallocate_inner(p, p->children_count());
704 35551 : }
705 :
706 0 : static void delete_collision(node_t* p)
707 : {
708 0 : assert(p);
709 0 : IMMER_ASSERT_TAGGED(p->kind() == kind_t::collision);
710 0 : auto n = p->collision_count();
711 0 : deallocate_collision(p, n);
712 0 : }
713 :
714 35551 : static void delete_deep(node_t* p, shift_t s)
715 : {
716 35551 : if (s == max_depth<B>)
717 0 : delete_collision(p);
718 : else {
719 35551 : auto fst = p->children();
720 35551 : auto lst = fst + p->children_count();
721 66929 : for (; fst != lst; ++fst)
722 31378 : if ((*fst)->dec())
723 6579 : delete_deep(*fst, s + 1);
724 35551 : delete_inner(p);
725 : }
726 35551 : }
727 :
728 0 : static void delete_deep_shift(node_t* p, shift_t s)
729 : {
730 0 : if (s == max_shift<B>)
731 0 : delete_collision(p);
732 : else {
733 0 : auto fst = p->children();
734 0 : auto lst = fst + p->children_count();
735 0 : for (; fst != lst; ++fst)
736 0 : if ((*fst)->dec())
737 0 : delete_deep_shift(*fst, s + B);
738 0 : delete_inner(p);
739 : }
740 0 : }
741 :
742 30239 : static void deallocate_values(values_t* p, count_t n)
743 : {
744 30239 : destroy_n((T*) &p->d.buffer, n);
745 30239 : heap::deallocate(node_t::sizeof_values_n(n), p);
746 30239 : }
747 :
748 0 : static void deallocate_collision(node_t* p, count_t n)
749 : {
750 0 : destroy_n(p->collisions(), n);
751 0 : heap::deallocate(node_t::sizeof_collision_n(n), p);
752 0 : }
753 :
754 35551 : static void deallocate_inner(node_t* p, count_t n)
755 : {
756 35551 : heap::deallocate(node_t::sizeof_inner_n(n), p);
757 : }
758 :
759 : static void deallocate_inner(node_t* p, count_t n, count_t nv)
760 : {
761 : assert(nv);
762 : heap::deallocate(node_t::sizeof_values_n(nv),
763 : p->impl.d.data.inner.values);
764 : heap::deallocate(node_t::sizeof_inner_n(n), p);
765 : }
766 : };
767 :
768 : } // namespace hamts
769 : } // namespace detail
770 : } // namespace immer
|
