diff options
Diffstat (limited to 'src/buildtool/build_engine/expression/linked_map.hpp')
| -rw-r--r-- | src/buildtool/build_engine/expression/linked_map.hpp | 414 |
1 files changed, 414 insertions, 0 deletions
diff --git a/src/buildtool/build_engine/expression/linked_map.hpp b/src/buildtool/build_engine/expression/linked_map.hpp new file mode 100644 index 00000000..5c6da558 --- /dev/null +++ b/src/buildtool/build_engine/expression/linked_map.hpp @@ -0,0 +1,414 @@ +#ifndef INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_EXPRESSION_LINKED_MAP_HPP +#define INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_EXPRESSION_LINKED_MAP_HPP + +#include <algorithm> +#include <atomic> +#include <condition_variable> +#include <map> +#include <memory> +#include <mutex> +#include <vector> + +#include "fmt/core.h" +#include "src/utils/cpp/atomic.hpp" +#include "src/utils/cpp/hash_combine.hpp" + +template <class K, class V, class NextPtr> +class LinkedMap; + +// Default NextPtr for LinkedMap, based on std::shared_ptr. +template <class K, class V> +class LinkedMapPtr { + using ptr_t = LinkedMapPtr<K, V>; + using map_t = LinkedMap<K, V, ptr_t>; + + public: + LinkedMapPtr() noexcept = default; + explicit LinkedMapPtr(std::shared_ptr<map_t> ptr) noexcept + : ptr_{std::move(ptr)} {} + explicit operator bool() const { return static_cast<bool>(ptr_); } + [[nodiscard]] auto operator*() const& -> map_t const& { return *ptr_; } + [[nodiscard]] auto operator->() const& -> map_t const* { + return ptr_.get(); + } + [[nodiscard]] auto IsNotNull() const noexcept -> bool { + return static_cast<bool>(ptr_); + } + [[nodiscard]] auto LinkedMap() const& -> map_t const& { return *ptr_; } + [[nodiscard]] static auto Make(map_t&& map) -> ptr_t { + return ptr_t{std::make_shared<map_t>(std::move(map))}; + } + + private: + std::shared_ptr<map_t> ptr_{}; +}; + +/// \brief Immutable LinkedMap. +/// Uses smart pointers to build up a list of pointer-linked maps. The NextPtr +/// that is used internally can be overloaded by any class implementing the +/// following methods: +/// 1. auto IsNotNull() const noexcept -> bool; +/// 2. auto LinkedMap() const& -> LinkedMap<K, V, NextPtr> const&; +/// 3. static auto Make(LinkedMap<K, V, NextPtr>&&) -> NextPtr; +template <class K, class V, class NextPtr = LinkedMapPtr<K, V>> +class LinkedMap { + using item_t = std::pair<K, V>; + using items_t = std::vector<item_t>; + using keys_t = std::vector<K>; + using values_t = std::vector<V>; + + public: + using Ptr = NextPtr; + // When merging maps, we always rely on entries being traversed in key + // order; so keep the underlying map an ordered data structure. + using underlying_map_t = std::map<K, V>; + + static constexpr auto MakePtr(underlying_map_t map) -> Ptr { + return Ptr::Make(LinkedMap<K, V, Ptr>{std::move(map)}); + } + + static constexpr auto MakePtr(item_t item) -> Ptr { + return Ptr::Make(LinkedMap<K, V, Ptr>{std::move(item)}); + } + + static constexpr auto MakePtr(K key, V value) -> Ptr { + return Ptr::Make( + LinkedMap<K, V, Ptr>{std::move(key), std::move(value)}); + } + + static constexpr auto MakePtr(Ptr next, Ptr content) -> Ptr { + return Ptr::Make(LinkedMap<K, V, Ptr>{next, content}); + } + + static constexpr auto MakePtr(Ptr next, underlying_map_t map) -> Ptr { + return Ptr::Make(LinkedMap<K, V, Ptr>{next, std::move(map)}); + } + + static constexpr auto MakePtr(Ptr const& next, item_t item) -> Ptr { + return Ptr::Make(LinkedMap<K, V, Ptr>{next, std::move(item)}); + } + + static constexpr auto MakePtr(Ptr const& next, K key, V value) -> Ptr { + return Ptr::Make( + LinkedMap<K, V, Ptr>{next, std::move(key), std::move(value)}); + } + + explicit LinkedMap(underlying_map_t map) noexcept : map_{std::move(map)} {} + explicit LinkedMap(item_t item) noexcept { map_.emplace(std::move(item)); } + LinkedMap(K key, V val) noexcept { + map_.emplace(std::move(key), std::move(val)); + } + LinkedMap(Ptr next, Ptr content) noexcept + : next_{std::move(next)}, content_{std::move(content)} {} + LinkedMap(Ptr next, underlying_map_t map) noexcept + : next_{std::move(next)}, map_{std::move(map)} {} + LinkedMap(Ptr next, item_t item) noexcept : next_{std::move(next)} { + map_.emplace(std::move(item)); + } + LinkedMap(Ptr next, K key, V val) noexcept : next_{std::move(next)} { + map_.emplace(std::move(key), std::move(val)); + } + + LinkedMap() noexcept = default; + LinkedMap(LinkedMap const& other) noexcept + : next_{other.next_}, + content_{other.content_}, + map_{other.map_}, + items_{other.items_.load()} {} + LinkedMap(LinkedMap&& other) noexcept + : next_{std::move(other.next_)}, + content_{std::move(other.content_)}, + map_{std::move(other.map_)}, + items_{other.items_.load()} {} + ~LinkedMap() noexcept = default; + + auto operator=(LinkedMap const& other) noexcept -> LinkedMap& { + next_ = other.next_; + content_ = other.content_; + map_ = other.map_; + items_ = other.items_.load(); + return *this; + } + auto operator=(LinkedMap&& other) noexcept -> LinkedMap& { + next_ = std::move(other.next_); + content_ = std::move(other.content_); + map_ = std::move(other.map_); + items_ = other.items_.load(); + return *this; + } + + [[nodiscard]] auto contains(K const& key) const noexcept -> bool { + return static_cast<bool>(Find(key)); + } + + [[nodiscard]] auto at(K const& key) const& -> V const& { + auto value = Find(key); + if (value) { + return value->get(); + } + throw std::out_of_range{fmt::format("Missing key {}", key)}; + } + + [[nodiscard]] auto at(K const& key) && -> V { + auto value = Find(key); + if (value) { + return std::move(*value); + } + throw std::out_of_range{fmt::format("Missing key {}", key)}; + } + + [[nodiscard]] auto operator[](K const& key) const& -> V const& { + return at(key); + } + + [[nodiscard]] auto empty() const noexcept -> bool { + return (content_.IsNotNull() ? content_.LinkedMap().empty() + : map_.empty()) and + (not next_.IsNotNull() or next_.LinkedMap().empty()); + } + + [[nodiscard]] auto Find(K const& key) const& noexcept + -> std::optional<std::reference_wrapper<V const>> { + if (content_.IsNotNull()) { + auto val = content_.LinkedMap().Find(key); + if (val) { + return val; + } + } + else { + auto it = map_.find(key); + if (it != map_.end()) { + return it->second; + } + } + if (next_.IsNotNull()) { + auto val = next_.LinkedMap().Find(key); + if (val) { + return val; + } + } + return std::nullopt; + } + + [[nodiscard]] auto Find(K const& key) && noexcept -> std::optional<V> { + if (content_.IsNotNull()) { + auto val = content_.LinkedMap().Find(key); + if (val) { + return val->get(); + } + } + else { + auto it = map_.find(key); + if (it != map_.end()) { + return std::move(it->second); + } + } + if (next_.IsNotNull()) { + auto val = next_.LinkedMap().Find(key); + if (val) { + return val->get(); + } + } + return std::nullopt; + } + + [[nodiscard]] auto FindConflictingDuplicate(LinkedMap const& other) + const& noexcept -> std::optional<std::reference_wrapper<K const>> { + auto const& my_items = Items(); + auto const& other_items = other.Items(); + // Search for duplicates, using that iteration over the items is + // orderd by keys. + auto me = my_items.begin(); + auto they = other_items.begin(); + while (me != my_items.end() and they != other_items.end()) { + if (me->first == they->first) { + if (not(me->second == they->second)) { + return me->first; + } + ++me; + ++they; + } + else if (me->first < they->first) { + ++me; + } + else { + ++they; + } + } + return std::nullopt; + } + + [[nodiscard]] auto FindConflictingDuplicate( + LinkedMap const& other) && noexcept = delete; + + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto size() const noexcept -> std::size_t { + return Items().size(); + } + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto begin() const& -> typename items_t::const_iterator { + return Items().cbegin(); + } + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto end() const& -> typename items_t::const_iterator { + return Items().cend(); + } + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto cbegin() const& -> typename items_t::const_iterator { + return begin(); + } + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto cend() const& -> typename items_t::const_iterator { + return end(); + } + + [[nodiscard]] auto begin() && -> typename items_t::const_iterator = delete; + [[nodiscard]] auto end() && -> typename items_t::const_iterator = delete; + [[nodiscard]] auto cbegin() && -> typename items_t::const_iterator = delete; + [[nodiscard]] auto cend() && -> typename items_t::const_iterator = delete; + + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto operator==( + LinkedMap<K, V, NextPtr> const& other) const noexcept -> bool { + return this == &other or (this->empty() and other.empty()) or + this->Items() == other.Items(); + } + + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto Items() const& -> items_t const& { + if (items_.load() == nullptr) { + if (not items_loading_.exchange(true)) { + items_ = std::make_shared<items_t>(ComputeSortedItems()); + items_.notify_all(); + } + else { + items_.wait(nullptr); + } + } + return *items_.load(); + } + + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto Items() && -> items_t { + return items_.load() == nullptr ? ComputeSortedItems() + : std::move(*items_.load()); + } + + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto Keys() const -> keys_t { + auto keys = keys_t{}; + auto const& items = Items(); + keys.reserve(items.size()); + std::transform(items.begin(), + items.end(), + std::back_inserter(keys), + [](auto const& item) { return item.first; }); + return keys; + } + + // NOTE: Expensive, needs to compute sorted items. + [[nodiscard]] auto Values() const -> values_t { + auto values = values_t{}; + auto const& items = Items(); + values.reserve(items.size()); + std::transform(items.begin(), + items.end(), + std::back_inserter(values), + [](auto const& item) { return item.second; }); + return values; + } + + private: + Ptr next_{}; // map that is shadowed by this map + Ptr content_{}; // content of this map if set + underlying_map_t map_{}; // content of this map if content_ is not set + + mutable atomic_shared_ptr<items_t> items_{}; + mutable std::atomic<bool> items_loading_{}; + + [[nodiscard]] auto ComputeSortedItems() const noexcept -> items_t { + auto size = + content_.IsNotNull() ? content_.LinkedMap().size() : map_.size(); + if (next_.IsNotNull()) { + size += next_.LinkedMap().size(); + } + + auto items = items_t{}; + items.reserve(size); + + auto empty = items_t{}; + auto map_copy = items_t{}; + typename items_t::const_iterator citemsit; + typename items_t::const_iterator citemsend; + typename items_t::const_iterator nitemsit; + typename items_t::const_iterator nitemsend; + + if (content_.IsNotNull()) { + auto const& citems = content_.LinkedMap().Items(); + citemsit = citems.begin(); + citemsend = citems.end(); + } + else { + map_copy.reserve(map_.size()); + map_copy.insert(map_copy.end(), map_.begin(), map_.end()); + citemsit = map_copy.begin(); + citemsend = map_copy.end(); + } + if (next_.IsNotNull()) { + auto const& nitems = next_.LinkedMap().Items(); + nitemsit = nitems.begin(); + nitemsend = nitems.end(); + } + else { + nitemsit = empty.begin(); + nitemsend = empty.end(); + } + + while (citemsit != citemsend and nitemsit != nitemsend) { + if (citemsit->first == nitemsit->first) { + items.push_back(*citemsit); + ++citemsit; + ++nitemsit; + } + else if (citemsit->first < nitemsit->first) { + items.push_back(*citemsit); + ++citemsit; + } + else { + items.push_back(*nitemsit); + ++nitemsit; + } + } + + // No more comaprisons to be made; copy over the remaining + // entries + items.insert(items.end(), citemsit, citemsend); + items.insert(items.end(), nitemsit, nitemsend); + + return items; + } +}; + +namespace std { +template <class K, class V, class N> +struct hash<LinkedMap<K, V, N>> { + [[nodiscard]] auto operator()(LinkedMap<K, V, N> const& m) const noexcept + -> std::size_t { + size_t seed{}; + for (auto const& e : m) { + hash_combine(&seed, e.first); + hash_combine(&seed, e.second); + } + return seed; + } +}; +template <class K, class V> +struct hash<LinkedMapPtr<K, V>> { + [[nodiscard]] auto operator()(LinkedMapPtr<K, V> const& p) const noexcept + -> std::size_t { + return std::hash<std::remove_cvref_t<decltype(*p)>>{}(*p); + } +}; +} // namespace std + +#endif // INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_EXPRESSION_LINKED_MAP_HPP |