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/hamts/node.hpp>
13 :
14 : #include <algorithm>
15 :
16 : namespace immer {
17 : namespace detail {
18 : namespace hamts {
19 :
20 : template <typename T,
21 : typename Hash,
22 : typename Equal,
23 : typename MemoryPolicy,
24 : bits_t B>
25 : struct champ
26 : {
27 : static constexpr auto bits = B;
28 :
29 : using node_t = node<T, Hash, Equal, MemoryPolicy, B>;
30 : using bitmap_t = typename get_bitmap_type<B>::type;
31 :
32 : static_assert(branches<B> <= sizeof(bitmap_t) * 8, "");
33 :
34 : node_t* root;
35 : size_t size;
36 :
37 1548205 : static node_t* empty()
38 : {
39 1548205 : static const auto node = node_t::make_inner_n(0);
40 1548205 : return node->inc();
41 : }
42 :
43 6 : champ(node_t* r, size_t sz = 0)
44 : : root{r}
45 415727 : , size{sz}
46 447 : {}
47 :
48 271962 : champ(const champ& other)
49 271962 : : champ{other.root, other.size}
50 : {
51 271962 : inc();
52 0 : }
53 :
54 29011 : champ(champ&& other)
55 29011 : : champ{empty()}
56 : {
57 29011 : swap(*this, other);
58 : }
59 :
60 271962 : champ& operator=(const champ& other)
61 : {
62 543924 : auto next = other;
63 271962 : swap(*this, next);
64 543924 : return *this;
65 : }
66 :
67 : champ& operator=(champ&& other)
68 : {
69 56455 : swap(*this, other);
70 : return *this;
71 : }
72 :
73 357428 : friend void swap(champ& x, champ& y)
74 : {
75 : using std::swap;
76 357428 : swap(x.root, y.root);
77 56449 : swap(x.size, y.size);
78 : }
79 :
80 329990 : ~champ() { dec(); }
81 :
82 271962 : void inc() const { root->inc(); }
83 :
84 2150126 : void dec() const
85 : {
86 2150126 : if (root->dec())
87 28972 : node_t::delete_deep(root, 0);
88 2150126 : }
89 :
90 : template <typename Fn>
91 : void for_each_chunk(Fn&& fn) const
92 : {
93 : for_each_chunk_traversal(root, 0, fn);
94 : }
95 :
96 : template <typename Fn>
97 : void for_each_chunk_traversal(node_t* node, count_t depth, Fn&& fn) const
98 : {
99 : if (depth < max_depth<B>) {
100 : auto datamap = node->datamap();
101 : if (datamap)
102 : fn(node->values(), node->values() + node->data_count());
103 : auto nodemap = node->nodemap();
104 : if (nodemap) {
105 : auto fst = node->children();
106 : auto lst = fst + node->children_count();
107 : for (; fst != lst; ++fst)
108 : for_each_chunk_traversal(*fst, depth + 1, fn);
109 : }
110 : } else {
111 : fn(node->collisions(),
112 : node->collisions() + node->collision_count());
113 : }
114 : }
115 :
116 : template <typename Project, typename Default, typename K>
117 766921 : decltype(auto) get(const K& k) const
118 : {
119 766921 : auto node = root;
120 766921 : auto hash = Hash{}(k);
121 831627 : for (auto i = count_t{}; i < max_depth<B>; ++i) {
122 831627 : auto bit = bitmap_t{1u} << (hash & mask<B>);
123 831627 : if (node->nodemap() & bit) {
124 64706 : auto offset = node->children_count(bit);
125 64706 : node = node->children()[offset];
126 64706 : hash = hash >> B;
127 766921 : } else if (node->datamap() & bit) {
128 227828 : auto offset = node->data_count(bit);
129 227828 : auto val = node->values() + offset;
130 227828 : if (Equal{}(*val, k))
131 226217 : return Project{}(*val);
132 : else
133 : return Default{}();
134 : } else {
135 : return Default{}();
136 : }
137 : }
138 0 : auto fst = node->collisions();
139 0 : auto lst = fst + node->collision_count();
140 0 : for (; fst != lst; ++fst)
141 0 : if (Equal{}(*fst, k))
142 29629 : return Project{}(*fst);
143 : return Default{}();
144 : }
145 :
146 : std::pair<node_t*, bool>
147 33700 : do_add(node_t* node, T v, hash_t hash, shift_t shift) const
148 : {
149 33700 : assert(node);
150 33700 : if (shift == max_shift<B>) {
151 0 : auto fst = node->collisions();
152 0 : auto lst = fst + node->collision_count();
153 0 : for (; fst != lst; ++fst)
154 0 : if (Equal{}(*fst, v))
155 : return {
156 0 : node_t::copy_collision_replace(node, fst, std::move(v)),
157 0 : false};
158 0 : return {node_t::copy_collision_insert(node, std::move(v)), true};
159 : } else {
160 33700 : auto idx = (hash & (mask<B> << shift)) >> shift;
161 33700 : auto bit = bitmap_t{1u} << idx;
162 33700 : if (node->nodemap() & bit) {
163 5136 : auto offset = node->children_count(bit);
164 5136 : assert(node->children()[offset]);
165 5136 : auto result = do_add(
166 5136 : node->children()[offset], std::move(v), hash, shift + B);
167 : IMMER_TRY {
168 5136 : result.first =
169 5136 : node_t::copy_inner_replace(node, offset, result.first);
170 5136 : return result;
171 : }
172 0 : IMMER_CATCH (...) {
173 0 : node_t::delete_deep_shift(result.first, shift + B);
174 0 : IMMER_RETHROW;
175 : }
176 28564 : } else if (node->datamap() & bit) {
177 23310 : auto offset = node->data_count(bit);
178 23310 : auto val = node->values() + offset;
179 23310 : if (Equal{}(*val, v))
180 21974 : return {node_t::copy_inner_replace_value(
181 21974 : node, offset, std::move(v)),
182 21974 : false};
183 : else {
184 1336 : auto child = node_t::make_merged(
185 1336 : shift + B, std::move(v), hash, *val, Hash{}(*val));
186 : IMMER_TRY {
187 1336 : return {node_t::copy_inner_replace_merged(
188 : node, bit, offset, child),
189 1336 : true};
190 : }
191 0 : IMMER_CATCH (...) {
192 0 : node_t::delete_deep_shift(child, shift + B);
193 0 : IMMER_RETHROW;
194 : }
195 : }
196 : } else {
197 : return {
198 5254 : node_t::copy_inner_insert_value(node, bit, std::move(v)),
199 5254 : true};
200 : }
201 : }
202 : }
203 :
204 28564 : champ add(T v) const
205 : {
206 28564 : auto hash = Hash{}(v);
207 28564 : auto res = do_add(root, std::move(v), hash, 0);
208 28564 : auto new_size = size + (res.second ? 1 : 0);
209 28564 : return {res.first, new_size};
210 : }
211 :
212 : template <typename Project,
213 : typename Default,
214 : typename Combine,
215 : typename K,
216 : typename Fn>
217 : std::pair<node_t*, bool>
218 : do_update(node_t* node, K&& k, Fn&& fn, hash_t hash, shift_t shift) const
219 : {
220 : if (shift == max_shift<B>) {
221 : auto fst = node->collisions();
222 : auto lst = fst + node->collision_count();
223 : for (; fst != lst; ++fst)
224 : if (Equal{}(*fst, k))
225 : return {
226 : node_t::copy_collision_replace(
227 : node,
228 : fst,
229 : Combine{}(std::forward<K>(k),
230 : std::forward<Fn>(fn)(Project{}(*fst)))),
231 : false};
232 : return {node_t::copy_collision_insert(
233 : node,
234 : Combine{}(std::forward<K>(k),
235 : std::forward<Fn>(fn)(Default{}()))),
236 : true};
237 : } else {
238 : auto idx = (hash & (mask<B> << shift)) >> shift;
239 : auto bit = bitmap_t{1u} << idx;
240 : if (node->nodemap() & bit) {
241 : auto offset = node->children_count(bit);
242 : auto result = do_update<Project, Default, Combine>(
243 : node->children()[offset],
244 : k,
245 : std::forward<Fn>(fn),
246 : hash,
247 : shift + B);
248 : IMMER_TRY {
249 : result.first =
250 : node_t::copy_inner_replace(node, offset, result.first);
251 : return result;
252 : }
253 : IMMER_CATCH (...) {
254 : node_t::delete_deep_shift(result.first, shift + B);
255 : IMMER_RETHROW;
256 : }
257 : } else if (node->datamap() & bit) {
258 : auto offset = node->data_count(bit);
259 : auto val = node->values() + offset;
260 : if (Equal{}(*val, k))
261 : return {
262 : node_t::copy_inner_replace_value(
263 : node,
264 : offset,
265 : Combine{}(std::forward<K>(k),
266 : std::forward<Fn>(fn)(Project{}(*val)))),
267 : false};
268 : else {
269 : auto child = node_t::make_merged(
270 : shift + B,
271 : Combine{}(std::forward<K>(k),
272 : std::forward<Fn>(fn)(Default{}())),
273 : hash,
274 : *val,
275 : Hash{}(*val));
276 : IMMER_TRY {
277 : return {node_t::copy_inner_replace_merged(
278 : node, bit, offset, child),
279 : true};
280 : }
281 : IMMER_CATCH (...) {
282 : node_t::delete_deep_shift(child, shift + B);
283 : IMMER_RETHROW;
284 : }
285 : }
286 : } else {
287 : return {node_t::copy_inner_insert_value(
288 : node,
289 : bit,
290 : Combine{}(std::forward<K>(k),
291 : std::forward<Fn>(fn)(Default{}()))),
292 : true};
293 : }
294 : }
295 : }
296 :
297 : template <typename Project,
298 : typename Default,
299 : typename Combine,
300 : typename K,
301 : typename Fn>
302 : champ update(const K& k, Fn&& fn) const
303 : {
304 : auto hash = Hash{}(k);
305 : auto res = do_update<Project, Default, Combine>(
306 : root, k, std::forward<Fn>(fn), hash, 0);
307 : auto new_size = size + (res.second ? 1 : 0);
308 : return {res.first, new_size};
309 : }
310 :
311 : // basically:
312 : // variant<monostate_t, T*, node_t*>
313 : // boo bad we are not using... C++17 :'(
314 : struct sub_result
315 : {
316 : enum kind_t
317 : {
318 : nothing,
319 : singleton,
320 : tree
321 : };
322 :
323 : union data_t
324 : {
325 : T* singleton;
326 : node_t* tree;
327 : };
328 :
329 : kind_t kind;
330 : data_t data;
331 :
332 0 : sub_result()
333 0 : : kind{nothing} {};
334 92 : sub_result(T* x)
335 92 : : kind{singleton}
336 : {
337 92 : data.singleton = x;
338 75 : };
339 516 : sub_result(node_t* x)
340 516 : : kind{tree}
341 : {
342 516 : data.tree = x;
343 88 : };
344 : };
345 :
346 : template <typename K>
347 : sub_result
348 608 : do_sub(node_t* node, const K& k, hash_t hash, shift_t shift) const
349 : {
350 608 : if (shift == max_shift<B>) {
351 0 : auto fst = node->collisions();
352 0 : auto lst = fst + node->collision_count();
353 0 : for (auto cur = fst; cur != lst; ++cur)
354 0 : if (Equal{}(*cur, k))
355 0 : return node->collision_count() > 2
356 : ? node_t::copy_collision_remove(node, cur)
357 64 : : sub_result{fst + (cur == fst)};
358 0 : return {};
359 : } else {
360 608 : auto idx = (hash & (mask<B> << shift)) >> shift;
361 608 : auto bit = bitmap_t{1u} << idx;
362 608 : if (node->nodemap() & bit) {
363 161 : auto offset = node->children_count(bit);
364 161 : auto result =
365 161 : do_sub(node->children()[offset], k, hash, shift + B);
366 161 : switch (result.kind) {
367 0 : case sub_result::nothing:
368 0 : return {};
369 92 : case sub_result::singleton:
370 92 : return node->datamap() == 0 &&
371 0 : node->children_count() == 1 && shift > 0
372 92 : ? result
373 : : node_t::copy_inner_replace_inline(
374 195 : node, bit, offset, *result.data.singleton);
375 69 : case sub_result::tree:
376 : IMMER_TRY {
377 : return node_t::copy_inner_replace(
378 69 : node, offset, result.data.tree);
379 : }
380 0 : IMMER_CATCH (...) {
381 0 : node_t::delete_deep_shift(result.data.tree, shift + B);
382 0 : IMMER_RETHROW;
383 : }
384 : }
385 447 : } else if (node->datamap() & bit) {
386 447 : auto offset = node->data_count(bit);
387 447 : auto val = node->values() + offset;
388 447 : if (Equal{}(*val, k)) {
389 447 : auto nv = node->data_count();
390 447 : if (node->nodemap() || nv > 2)
391 : return node_t::copy_inner_remove_value(
392 303 : node, bit, offset);
393 144 : else if (nv == 2) {
394 92 : return shift > 0 ? sub_result{node->values() + !offset}
395 : : node_t::make_inner_n(
396 : 0,
397 13 : node->datamap() & ~bit,
398 666 : node->values()[!offset]);
399 : } else {
400 39 : assert(shift == 0);
401 39 : return empty();
402 : }
403 : }
404 : }
405 0 : return {};
406 : }
407 : }
408 :
409 : template <typename K>
410 447 : champ sub(const K& k) const
411 : {
412 447 : auto hash = Hash{}(k);
413 447 : auto res = do_sub(root, k, hash, 0);
414 447 : switch (res.kind) {
415 0 : case sub_result::nothing:
416 447 : return *this;
417 447 : case sub_result::tree:
418 447 : return {res.data.tree, size - 1};
419 0 : default:
420 0 : IMMER_UNREACHABLE;
421 : }
422 : }
423 :
424 : template <typename Eq = Equal>
425 : bool equals(const champ& other) const
426 : {
427 : return size == other.size && equals_tree<Eq>(root, other.root, 0);
428 : }
429 :
430 : template <typename Eq>
431 : static bool equals_tree(const node_t* a, const node_t* b, count_t depth)
432 : {
433 : if (a == b)
434 : return true;
435 : else if (depth == max_depth<B>) {
436 : auto nv = a->collision_count();
437 : return nv == b->collision_count() &&
438 : equals_collisions<Eq>(a->collisions(), b->collisions(), nv);
439 : } else {
440 : if (a->nodemap() != b->nodemap() || a->datamap() != b->datamap())
441 : return false;
442 : auto n = a->children_count();
443 : for (auto i = count_t{}; i < n; ++i)
444 : if (!equals_tree<Eq>(
445 : a->children()[i], b->children()[i], depth + 1))
446 : return false;
447 : auto nv = a->data_count();
448 : return !nv || equals_values<Eq>(a->values(), b->values(), nv);
449 : }
450 : }
451 :
452 : template <typename Eq>
453 : static bool equals_values(const T* a, const T* b, count_t n)
454 : {
455 : return std::equal(a, a + n, b, Eq{});
456 : }
457 :
458 : template <typename Eq>
459 : static bool equals_collisions(const T* a, const T* b, count_t n)
460 : {
461 : auto ae = a + n;
462 : auto be = b + n;
463 : for (; a != ae; ++a) {
464 : for (auto fst = b; fst != be; ++fst)
465 : if (Eq{}(*a, *fst))
466 : goto good;
467 : return false;
468 : good:
469 : continue;
470 : }
471 : return true;
472 : }
473 : };
474 :
475 : } // namespace hamts
476 : } // namespace detail
477 : } // namespace immer
|
