about summary refs log tree commit diff
path: root/immer/detail/hamts/champ.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'immer/detail/hamts/champ.hpp')
-rw-r--r--immer/detail/hamts/champ.hpp473
1 files changed, 473 insertions, 0 deletions
diff --git a/immer/detail/hamts/champ.hpp b/immer/detail/hamts/champ.hpp
new file mode 100644
index 000000000000..e3b55d397c72
--- /dev/null
+++ b/immer/detail/hamts/champ.hpp
@@ -0,0 +1,473 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#pragma once
+
+#include <immer/config.hpp>
+#include <immer/detail/hamts/node.hpp>
+
+#include <algorithm>
+
+namespace immer {
+namespace detail {
+namespace hamts {
+
+template <typename T,
+          typename Hash,
+          typename Equal,
+          typename MemoryPolicy,
+          bits_t B>
+struct champ
+{
+    static constexpr auto bits = B;
+
+    using node_t   = node<T, Hash, Equal, MemoryPolicy, B>;
+    using bitmap_t = typename get_bitmap_type<B>::type;
+
+    static_assert(branches<B> <= sizeof(bitmap_t) * 8, "");
+
+    node_t* root;
+    size_t size;
+
+    static const champ& empty()
+    {
+        static const champ empty_{
+            node_t::make_inner_n(0),
+            0,
+        };
+        return empty_;
+    }
+
+    champ(node_t* r, size_t sz)
+        : root{r}
+        , size{sz}
+    {}
+
+    champ(const champ& other)
+        : champ{other.root, other.size}
+    {
+        inc();
+    }
+
+    champ(champ&& other)
+        : champ{empty()}
+    {
+        swap(*this, other);
+    }
+
+    champ& operator=(const champ& other)
+    {
+        auto next = other;
+        swap(*this, next);
+        return *this;
+    }
+
+    champ& operator=(champ&& other)
+    {
+        swap(*this, other);
+        return *this;
+    }
+
+    friend void swap(champ& x, champ& y)
+    {
+        using std::swap;
+        swap(x.root, y.root);
+        swap(x.size, y.size);
+    }
+
+    ~champ() { dec(); }
+
+    void inc() const { root->inc(); }
+
+    void dec() const
+    {
+        if (root->dec())
+            node_t::delete_deep(root, 0);
+    }
+
+    template <typename Fn>
+    void for_each_chunk(Fn&& fn) const
+    {
+        for_each_chunk_traversal(root, 0, fn);
+    }
+
+    template <typename Fn>
+    void for_each_chunk_traversal(node_t* node, count_t depth, Fn&& fn) const
+    {
+        if (depth < max_depth<B>) {
+            auto datamap = node->datamap();
+            if (datamap)
+                fn(node->values(), node->values() + popcount(datamap));
+            auto nodemap = node->nodemap();
+            if (nodemap) {
+                auto fst = node->children();
+                auto lst = fst + popcount(nodemap);
+                for (; fst != lst; ++fst)
+                    for_each_chunk_traversal(*fst, depth + 1, fn);
+            }
+        } else {
+            fn(node->collisions(),
+               node->collisions() + node->collision_count());
+        }
+    }
+
+    template <typename Project, typename Default, typename K>
+    decltype(auto) get(const K& k) const
+    {
+        auto node = root;
+        auto hash = Hash{}(k);
+        for (auto i = count_t{}; i < max_depth<B>; ++i) {
+            auto bit = bitmap_t{1u} << (hash & mask<B>);
+            if (node->nodemap() & bit) {
+                auto offset = popcount(node->nodemap() & (bit - 1));
+                node        = node->children()[offset];
+                hash        = hash >> B;
+            } else if (node->datamap() & bit) {
+                auto offset = popcount(node->datamap() & (bit - 1));
+                auto val    = node->values() + offset;
+                if (Equal{}(*val, k))
+                    return Project{}(*val);
+                else
+                    return Default{}();
+            } else {
+                return Default{}();
+            }
+        }
+        auto fst = node->collisions();
+        auto lst = fst + node->collision_count();
+        for (; fst != lst; ++fst)
+            if (Equal{}(*fst, k))
+                return Project{}(*fst);
+        return Default{}();
+    }
+
+    std::pair<node_t*, bool>
+    do_add(node_t* node, T v, hash_t hash, shift_t shift) const
+    {
+        if (shift == max_shift<B>) {
+            auto fst = node->collisions();
+            auto lst = fst + node->collision_count();
+            for (; fst != lst; ++fst)
+                if (Equal{}(*fst, v))
+                    return {
+                        node_t::copy_collision_replace(node, fst, std::move(v)),
+                        false};
+            return {node_t::copy_collision_insert(node, std::move(v)), true};
+        } else {
+            auto idx = (hash & (mask<B> << shift)) >> shift;
+            auto bit = bitmap_t{1u} << idx;
+            if (node->nodemap() & bit) {
+                auto offset = popcount(node->nodemap() & (bit - 1));
+                auto result = do_add(
+                    node->children()[offset], std::move(v), hash, shift + B);
+                try {
+                    result.first =
+                        node_t::copy_inner_replace(node, offset, result.first);
+                    return result;
+                } catch (...) {
+                    node_t::delete_deep_shift(result.first, shift + B);
+                    throw;
+                }
+            } else if (node->datamap() & bit) {
+                auto offset = popcount(node->datamap() & (bit - 1));
+                auto val    = node->values() + offset;
+                if (Equal{}(*val, v))
+                    return {node_t::copy_inner_replace_value(
+                                node, offset, std::move(v)),
+                            false};
+                else {
+                    auto child = node_t::make_merged(
+                        shift + B, std::move(v), hash, *val, Hash{}(*val));
+                    try {
+                        return {node_t::copy_inner_replace_merged(
+                                    node, bit, offset, child),
+                                true};
+                    } catch (...) {
+                        node_t::delete_deep_shift(child, shift + B);
+                        throw;
+                    }
+                }
+            } else {
+                return {
+                    node_t::copy_inner_insert_value(node, bit, std::move(v)),
+                    true};
+            }
+        }
+    }
+
+    champ add(T v) const
+    {
+        auto hash     = Hash{}(v);
+        auto res      = do_add(root, std::move(v), hash, 0);
+        auto new_size = size + (res.second ? 1 : 0);
+        return {res.first, new_size};
+    }
+
+    template <typename Project,
+              typename Default,
+              typename Combine,
+              typename K,
+              typename Fn>
+    std::pair<node_t*, bool>
+    do_update(node_t* node, K&& k, Fn&& fn, hash_t hash, shift_t shift) const
+    {
+        if (shift == max_shift<B>) {
+            auto fst = node->collisions();
+            auto lst = fst + node->collision_count();
+            for (; fst != lst; ++fst)
+                if (Equal{}(*fst, k))
+                    return {
+                        node_t::copy_collision_replace(
+                            node,
+                            fst,
+                            Combine{}(std::forward<K>(k),
+                                      std::forward<Fn>(fn)(Project{}(*fst)))),
+                        false};
+            return {node_t::copy_collision_insert(
+                        node,
+                        Combine{}(std::forward<K>(k),
+                                  std::forward<Fn>(fn)(Default{}()))),
+                    true};
+        } else {
+            auto idx = (hash & (mask<B> << shift)) >> shift;
+            auto bit = bitmap_t{1u} << idx;
+            if (node->nodemap() & bit) {
+                auto offset = popcount(node->nodemap() & (bit - 1));
+                auto result = do_update<Project, Default, Combine>(
+                    node->children()[offset],
+                    k,
+                    std::forward<Fn>(fn),
+                    hash,
+                    shift + B);
+                try {
+                    result.first =
+                        node_t::copy_inner_replace(node, offset, result.first);
+                    return result;
+                } catch (...) {
+                    node_t::delete_deep_shift(result.first, shift + B);
+                    throw;
+                }
+            } else if (node->datamap() & bit) {
+                auto offset = popcount(node->datamap() & (bit - 1));
+                auto val    = node->values() + offset;
+                if (Equal{}(*val, k))
+                    return {
+                        node_t::copy_inner_replace_value(
+                            node,
+                            offset,
+                            Combine{}(std::forward<K>(k),
+                                      std::forward<Fn>(fn)(Project{}(*val)))),
+                        false};
+                else {
+                    auto child = node_t::make_merged(
+                        shift + B,
+                        Combine{}(std::forward<K>(k),
+                                  std::forward<Fn>(fn)(Default{}())),
+                        hash,
+                        *val,
+                        Hash{}(*val));
+                    try {
+                        return {node_t::copy_inner_replace_merged(
+                                    node, bit, offset, child),
+                                true};
+                    } catch (...) {
+                        node_t::delete_deep_shift(child, shift + B);
+                        throw;
+                    }
+                }
+            } else {
+                return {node_t::copy_inner_insert_value(
+                            node,
+                            bit,
+                            Combine{}(std::forward<K>(k),
+                                      std::forward<Fn>(fn)(Default{}()))),
+                        true};
+            }
+        }
+    }
+
+    template <typename Project,
+              typename Default,
+              typename Combine,
+              typename K,
+              typename Fn>
+    champ update(const K& k, Fn&& fn) const
+    {
+        auto hash = Hash{}(k);
+        auto res  = do_update<Project, Default, Combine>(
+            root, k, std::forward<Fn>(fn), hash, 0);
+        auto new_size = size + (res.second ? 1 : 0);
+        return {res.first, new_size};
+    }
+
+    // basically:
+    //      variant<monostate_t, T*, node_t*>
+    // boo bad we are not using... C++17 :'(
+    struct sub_result
+    {
+        enum kind_t
+        {
+            nothing,
+            singleton,
+            tree
+        };
+
+        union data_t
+        {
+            T* singleton;
+            node_t* tree;
+        };
+
+        kind_t kind;
+        data_t data;
+
+        sub_result()
+            : kind{nothing} {};
+        sub_result(T* x)
+            : kind{singleton}
+        {
+            data.singleton = x;
+        };
+        sub_result(node_t* x)
+            : kind{tree}
+        {
+            data.tree = x;
+        };
+    };
+
+    template <typename K>
+    sub_result
+    do_sub(node_t* node, const K& k, hash_t hash, shift_t shift) const
+    {
+        if (shift == max_shift<B>) {
+            auto fst = node->collisions();
+            auto lst = fst + node->collision_count();
+            for (auto cur = fst; cur != lst; ++cur)
+                if (Equal{}(*cur, k))
+                    return node->collision_count() > 2
+                               ? node_t::copy_collision_remove(node, cur)
+                               : sub_result{fst + (cur == fst)};
+            return {};
+        } else {
+            auto idx = (hash & (mask<B> << shift)) >> shift;
+            auto bit = bitmap_t{1u} << idx;
+            if (node->nodemap() & bit) {
+                auto offset = popcount(node->nodemap() & (bit - 1));
+                auto result =
+                    do_sub(node->children()[offset], k, hash, shift + B);
+                switch (result.kind) {
+                case sub_result::nothing:
+                    return {};
+                case sub_result::singleton:
+                    return node->datamap() == 0 &&
+                                   popcount(node->nodemap()) == 1 && shift > 0
+                               ? result
+                               : node_t::copy_inner_replace_inline(
+                                     node, bit, offset, *result.data.singleton);
+                case sub_result::tree:
+                    try {
+                        return node_t::copy_inner_replace(
+                            node, offset, result.data.tree);
+                    } catch (...) {
+                        node_t::delete_deep_shift(result.data.tree, shift + B);
+                        throw;
+                    }
+                }
+            } else if (node->datamap() & bit) {
+                auto offset = popcount(node->datamap() & (bit - 1));
+                auto val    = node->values() + offset;
+                if (Equal{}(*val, k)) {
+                    auto nv = popcount(node->datamap());
+                    if (node->nodemap() || nv > 2)
+                        return node_t::copy_inner_remove_value(
+                            node, bit, offset);
+                    else if (nv == 2) {
+                        return shift > 0 ? sub_result{node->values() + !offset}
+                                         : node_t::make_inner_n(
+                                               0,
+                                               node->datamap() & ~bit,
+                                               node->values()[!offset]);
+                    } else {
+                        assert(shift == 0);
+                        return empty().root->inc();
+                    }
+                }
+            }
+            return {};
+        }
+    }
+
+    template <typename K>
+    champ sub(const K& k) const
+    {
+        auto hash = Hash{}(k);
+        auto res  = do_sub(root, k, hash, 0);
+        switch (res.kind) {
+        case sub_result::nothing:
+            return *this;
+        case sub_result::tree:
+            return {res.data.tree, size - 1};
+        default:
+            IMMER_UNREACHABLE;
+        }
+    }
+
+    template <typename Eq = Equal>
+    bool equals(const champ& other) const
+    {
+        return size == other.size && equals_tree<Eq>(root, other.root, 0);
+    }
+
+    template <typename Eq>
+    static bool equals_tree(const node_t* a, const node_t* b, count_t depth)
+    {
+        if (a == b)
+            return true;
+        else if (depth == max_depth<B>) {
+            auto nv = a->collision_count();
+            return nv == b->collision_count() &&
+                   equals_collisions<Eq>(a->collisions(), b->collisions(), nv);
+        } else {
+            if (a->nodemap() != b->nodemap() || a->datamap() != b->datamap())
+                return false;
+            auto n = popcount(a->nodemap());
+            for (auto i = count_t{}; i < n; ++i)
+                if (!equals_tree<Eq>(
+                        a->children()[i], b->children()[i], depth + 1))
+                    return false;
+            auto nv = popcount(a->datamap());
+            return !nv || equals_values<Eq>(a->values(), b->values(), nv);
+        }
+    }
+
+    template <typename Eq>
+    static bool equals_values(const T* a, const T* b, count_t n)
+    {
+        return std::equal(a, a + n, b, Eq{});
+    }
+
+    template <typename Eq>
+    static bool equals_collisions(const T* a, const T* b, count_t n)
+    {
+        auto ae = a + n;
+        auto be = b + n;
+        for (; a != ae; ++a) {
+            for (auto fst = b; fst != be; ++fst)
+                if (Eq{}(*a, *fst))
+                    goto good;
+            return false;
+        good:
+            continue;
+        }
+        return true;
+    }
+};
+
+} // namespace hamts
+} // namespace detail
+} // namespace immer