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 4875 : 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 6758 : constexpr static std::size_t sizeof_values_n(count_t count)
88 : {
89 13516 : return std::max(sizeof(values_t),
90 13516 : immer_offsetof(values_t, d.buffer) +
91 7721 : 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 8772 : constexpr static std::size_t sizeof_inner_n(count_t count)
101 : {
102 8772 : return immer_offsetof(impl_t, d.data.inner.buffer) +
103 8772 : sizeof(inner_t::buffer) * count;
104 : }
105 :
106 : #if IMMER_TAGGED_NODE
107 704512 : kind_t kind() const { return impl.d.kind; }
108 : #endif
109 :
110 41723 : auto values()
111 : {
112 41723 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
113 41723 : assert(impl.d.data.inner.values);
114 41723 : 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 26705 : auto children()
125 : {
126 11944 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
127 13397 : 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 311658 : auto datamap() const
137 : {
138 14314 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
139 275322 : return impl.d.data.inner.datamap;
140 : }
141 :
142 304387 : auto nodemap() const
143 : {
144 281312 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
145 281283 : return impl.d.data.inner.nodemap;
146 : }
147 :
148 17221 : auto data_count() const
149 : {
150 12792 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
151 14163 : return popcount(datamap());
152 : }
153 :
154 17405 : auto data_count(bitmap_t bit) const
155 : {
156 267 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
157 16041 : return popcount(static_cast<bitmap_t>(datamap() & (bit - 1)));
158 : }
159 :
160 16255 : auto children_count() const
161 : {
162 3897 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
163 12358 : return popcount(nodemap());
164 : }
165 :
166 5185 : auto children_count(bitmap_t bit) const
167 : {
168 164 : IMMER_ASSERT_TAGGED(kind() == kind_t::inner);
169 5185 : 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 3888 : static refs_t& refs(const values_t* x)
191 : {
192 4397 : 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 1212973 : static refs_t& refs(const node_t* x)
198 : {
199 1212973 : 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 4875 : static node_t* make_inner_n(count_t n)
208 : {
209 4875 : assert(n <= branches<B>);
210 4875 : auto m = heap::allocate(sizeof_inner_n(n));
211 4875 : auto p = new (m) node_t;
212 : assert(p == (node_t*) m);
213 : #if IMMER_TAGGED_NODE
214 4875 : p->impl.d.kind = node_t::kind_t::inner;
215 : #endif
216 4875 : p->impl.d.data.inner.nodemap = 0;
217 4875 : p->impl.d.data.inner.datamap = 0;
218 4875 : p->impl.d.data.inner.values = nullptr;
219 4875 : return p;
220 : }
221 :
222 514 : static node_t* make_inner_n(count_t n, values_t* values)
223 : {
224 514 : auto p = make_inner_n(n);
225 514 : if (values) {
226 509 : p->impl.d.data.inner.values = values;
227 509 : refs(values).inc();
228 : }
229 514 : return p;
230 : }
231 :
232 3381 : static node_t* make_inner_n(count_t n, count_t nv)
233 : {
234 3381 : assert(nv <= branches<B>);
235 3381 : auto p = make_inner_n(n);
236 3381 : if (nv) {
237 : IMMER_TRY {
238 3379 : p->impl.d.data.inner.values =
239 3379 : 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 3381 : return p;
247 : }
248 :
249 2 : static node_t* make_inner_n(count_t n, count_t idx, node_t* child)
250 : {
251 2 : assert(n >= 1);
252 2 : auto p = make_inner_n(n);
253 2 : p->impl.d.data.inner.nodemap = bitmap_t{1u} << idx;
254 2 : p->children()[0] = child;
255 2 : return p;
256 : }
257 :
258 0 : static node_t* make_inner_n(count_t n, bitmap_t bitmap, T x)
259 : {
260 0 : auto p = make_inner_n(n, 1);
261 0 : p->impl.d.data.inner.datamap = bitmap;
262 : IMMER_TRY {
263 0 : new (p->values()) T{std::move(x)};
264 : }
265 : IMMER_CATCH (...) {
266 : deallocate_inner(p, n, 1);
267 : IMMER_RETHROW;
268 : }
269 0 : return p;
270 : }
271 :
272 : static node_t*
273 323 : make_inner_n(count_t n, count_t idx1, T x1, count_t idx2, T x2)
274 : {
275 323 : assert(idx1 != idx2);
276 323 : auto p = make_inner_n(n, 2);
277 323 : p->impl.d.data.inner.datamap =
278 323 : (bitmap_t{1u} << idx1) | (bitmap_t{1u} << idx2);
279 969 : auto assign = [&](auto&& x1, auto&& x2) {
280 323 : auto vp = p->values();
281 : IMMER_TRY {
282 323 : new (vp) T{std::move(x1)};
283 : IMMER_TRY {
284 323 : 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 323 : if (idx1 < idx2)
297 206 : assign(x1, x2);
298 : else
299 117 : assign(x2, x1);
300 323 : 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 514 : copy_inner_replace(node_t* src, count_t offset, node_t* child)
423 : {
424 514 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
425 514 : auto n = src->children_count();
426 514 : auto dst = make_inner_n(n, src->impl.d.data.inner.values);
427 514 : auto srcp = src->children();
428 514 : auto dstp = dst->children();
429 514 : dst->impl.d.data.inner.datamap = src->datamap();
430 514 : dst->impl.d.data.inner.nodemap = src->nodemap();
431 514 : std::uninitialized_copy(srcp, srcp + n, dstp);
432 514 : inc_nodes(srcp, n);
433 1028 : srcp[offset]->dec_unsafe();
434 514 : dstp[offset] = child;
435 514 : return dst;
436 : }
437 :
438 1342 : static node_t* copy_inner_replace_value(node_t* src, count_t offset, T v)
439 : {
440 1342 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
441 1342 : assert(offset < src->data_count());
442 1342 : auto n = src->children_count();
443 1342 : auto nv = src->data_count();
444 1342 : auto dst = make_inner_n(n, nv);
445 1342 : dst->impl.d.data.inner.datamap = src->datamap();
446 1342 : dst->impl.d.data.inner.nodemap = src->nodemap();
447 : IMMER_TRY {
448 2684 : std::uninitialized_copy(
449 1342 : src->values(), src->values() + nv, dst->values());
450 : IMMER_TRY {
451 2684 : 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 1342 : inc_nodes(src->children(), n);
463 1342 : std::uninitialized_copy(
464 1342 : src->children(), src->children() + n, dst->children());
465 1342 : return dst;
466 : }
467 :
468 323 : static node_t* copy_inner_replace_merged(node_t* src,
469 : bitmap_t bit,
470 : count_t voffset,
471 : node_t* node)
472 : {
473 323 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
474 323 : assert(!(src->nodemap() & bit));
475 323 : assert(src->datamap() & bit);
476 323 : assert(voffset == src->data_count(bit));
477 323 : auto n = src->children_count();
478 323 : auto nv = src->data_count();
479 323 : auto dst = make_inner_n(n + 1, nv - 1);
480 323 : auto noffset = src->children_count(bit);
481 323 : dst->impl.d.data.inner.datamap = src->datamap() & ~bit;
482 323 : dst->impl.d.data.inner.nodemap = src->nodemap() | bit;
483 323 : if (nv > 1) {
484 : IMMER_TRY {
485 321 : std::uninitialized_copy(
486 321 : src->values(), src->values() + voffset, dst->values());
487 : IMMER_TRY {
488 323 : std::uninitialized_copy(src->values() + voffset + 1,
489 321 : src->values() + nv,
490 321 : 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 323 : inc_nodes(src->children(), n);
503 323 : std::uninitialized_copy(
504 323 : src->children(), src->children() + noffset, dst->children());
505 323 : std::uninitialized_copy(src->children() + noffset,
506 323 : src->children() + n,
507 323 : dst->children() + noffset + 1);
508 323 : dst->children()[noffset] = node;
509 323 : return dst;
510 : }
511 :
512 4 : static node_t* copy_inner_replace_inline(node_t* src,
513 : bitmap_t bit,
514 : count_t noffset,
515 : T value)
516 : {
517 4 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
518 4 : assert(!(src->datamap() & bit));
519 4 : assert(src->nodemap() & bit);
520 4 : assert(noffset == src->children_count(bit));
521 4 : auto n = src->children_count();
522 4 : auto nv = src->data_count();
523 4 : auto dst = make_inner_n(n - 1, nv + 1);
524 4 : auto voffset = src->data_count(bit);
525 4 : dst->impl.d.data.inner.nodemap = src->nodemap() & ~bit;
526 4 : dst->impl.d.data.inner.datamap = src->datamap() | bit;
527 : IMMER_TRY {
528 4 : if (nv)
529 8 : std::uninitialized_copy(
530 4 : src->values(), src->values() + voffset, dst->values());
531 : IMMER_TRY {
532 4 : new (dst->values() + voffset) T{std::move(value)};
533 : IMMER_TRY {
534 4 : if (nv)
535 4 : std::uninitialized_copy(src->values() + voffset,
536 4 : src->values() + nv,
537 4 : 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 4 : inc_nodes(src->children(), n);
554 4 : src->children()[noffset]->dec_unsafe();
555 4 : std::uninitialized_copy(
556 4 : src->children(), src->children() + noffset, dst->children());
557 12 : std::uninitialized_copy(src->children() + noffset + 1,
558 4 : src->children() + n,
559 4 : dst->children() + noffset);
560 4 : return dst;
561 : }
562 :
563 : static node_t*
564 25 : copy_inner_remove_value(node_t* src, bitmap_t bit, count_t voffset)
565 : {
566 25 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
567 25 : assert(!(src->nodemap() & bit));
568 25 : assert(src->datamap() & bit);
569 25 : assert(voffset == src->data_count(bit));
570 25 : auto n = src->children_count();
571 25 : auto nv = src->data_count();
572 25 : auto dst = make_inner_n(n, nv - 1);
573 25 : dst->impl.d.data.inner.datamap = src->datamap() & ~bit;
574 25 : dst->impl.d.data.inner.nodemap = src->nodemap();
575 25 : if (nv > 1) {
576 : IMMER_TRY {
577 25 : std::uninitialized_copy(
578 25 : src->values(), src->values() + voffset, dst->values());
579 : IMMER_TRY {
580 25 : std::uninitialized_copy(src->values() + voffset + 1,
581 25 : src->values() + nv,
582 25 : 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 25 : inc_nodes(src->children(), n);
595 25 : std::uninitialized_copy(
596 25 : src->children(), src->children() + n, dst->children());
597 25 : return dst;
598 : }
599 :
600 1364 : static node_t* copy_inner_insert_value(node_t* src, bitmap_t bit, T v)
601 : {
602 1364 : IMMER_ASSERT_TAGGED(src->kind() == kind_t::inner);
603 1364 : auto n = src->children_count();
604 1364 : auto nv = src->data_count();
605 1364 : auto offset = src->data_count(bit);
606 1364 : auto dst = make_inner_n(n, nv + 1);
607 1364 : dst->impl.d.data.inner.datamap = src->datamap() | bit;
608 1364 : dst->impl.d.data.inner.nodemap = src->nodemap();
609 : IMMER_TRY {
610 1364 : if (nv)
611 2609 : std::uninitialized_copy(
612 1245 : src->values(), src->values() + offset, dst->values());
613 : IMMER_TRY {
614 1364 : new (dst->values() + offset) T{std::move(v)};
615 : IMMER_TRY {
616 1364 : if (nv)
617 1364 : std::uninitialized_copy(src->values() + offset,
618 1245 : src->values() + nv,
619 1245 : 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 1364 : inc_nodes(src->children(), n);
636 1364 : std::uninitialized_copy(
637 1364 : src->children(), src->children() + n, dst->children());
638 1364 : return dst;
639 : }
640 :
641 : static node_t*
642 325 : make_merged(shift_t shift, T v1, hash_t hash1, T v2, hash_t hash2)
643 : {
644 325 : if (shift < max_shift<B>) {
645 325 : auto idx1 = hash1 & (mask<B> << shift);
646 325 : auto idx2 = hash2 & (mask<B> << shift);
647 325 : if (idx1 == idx2) {
648 4 : auto merged = make_merged(
649 2 : shift + B, std::move(v1), hash1, std::move(v2), hash2);
650 : IMMER_TRY {
651 2 : 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 323 : return make_inner_n(0,
659 323 : idx1 >> shift,
660 323 : std::move(v1),
661 323 : idx2 >> shift,
662 323 : std::move(v2));
663 : }
664 : } else {
665 0 : return make_collision(std::move(v1), std::move(v2));
666 : }
667 : }
668 :
669 596119 : node_t* inc()
670 : {
671 596119 : refs(this).inc();
672 49860 : return this;
673 : }
674 :
675 : const node_t* inc() const
676 : {
677 : refs(this).inc();
678 : return this;
679 : }
680 :
681 607917 : bool dec() const { return refs(this).dec(); }
682 518 : void dec_unsafe() const { refs(this).dec_unsafe(); }
683 :
684 3572 : static void inc_nodes(node_t** p, count_t n)
685 : {
686 11991 : for (auto i = p, e = i + n; i != e; ++i)
687 8419 : refs(*i).inc();
688 3572 : }
689 :
690 3379 : static void delete_values(values_t* p, count_t n)
691 : {
692 3379 : assert(p);
693 3379 : deallocate_values(p, n);
694 3379 : }
695 :
696 3897 : static void delete_inner(node_t* p)
697 : {
698 3897 : assert(p);
699 3897 : IMMER_ASSERT_TAGGED(p->kind() == kind_t::inner);
700 3897 : auto vp = p->impl.d.data.inner.values;
701 3897 : if (vp && refs(vp).dec())
702 3379 : delete_values(vp, p->data_count());
703 7794 : deallocate_inner(p, p->children_count());
704 3897 : }
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 3897 : static void delete_deep(node_t* p, shift_t s)
715 : {
716 3897 : if (s == max_depth<B>)
717 0 : delete_collision(p);
718 : else {
719 3897 : auto fst = p->children();
720 3897 : auto lst = fst + p->children_count();
721 12637 : for (; fst != lst; ++fst)
722 8740 : if ((*fst)->dec())
723 839 : delete_deep(*fst, s + 1);
724 3897 : delete_inner(p);
725 : }
726 3897 : }
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 3379 : static void deallocate_values(values_t* p, count_t n)
743 : {
744 3379 : destroy_n((T*) &p->d.buffer, n);
745 3379 : heap::deallocate(node_t::sizeof_values_n(n), p);
746 3379 : }
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 3897 : static void deallocate_inner(node_t* p, count_t n)
755 : {
756 3897 : 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
|
