stable_set.hpp

// Copyright Take Vos 2022.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
 
#pragma once
 
#include "unfair_mutex.hpp"
#include <mutex>
#include <memory>
#include <atomic>
#include <map>
#include <unordered_map>
#include <functional>
 
namespace hi::inline v1 {
 
template<typename Key>
class stable_set {
public:
    using value_type = Key;
    using size_type = size_t;
    using map_type = std::conditional_t<
        std::is_default_constructible<std::hash<Key>>::value,
        std::unordered_map<Key, size_type>,
        std::map<Key, size_type>>;
    using key_type = Key;
    using difference_type = ptrdiff_t;
    using reference = value_type const&;
    using const_reference = value_type const&;
    using pointer = value_type const *;
    using const_pointer = value_type const *;
 
    ~stable_set() = default;
    constexpr stable_set() noexcept = default;
    stable_set(stable_set const&) = delete;
    stable_set(stable_set&&) = delete;
    stable_set& operator=(stable_set const&) = delete;
    stable_set& operator=(stable_set&&) = delete;
 
    [[nodiscard]] size_t size() const noexcept
    {
        hilet lock = std::scoped_lock(_mutex);
        return _vector.size();
    }
 
    [[nodiscard]] bool empty() const noexcept
    {
        return size() == 0;
    }
 
    operator bool() const noexcept
    {
        return not empty();
    }
 
    [[nodiscard]] const_reference operator[](size_t index) const noexcept
    {
        hilet lock = std::scoped_lock(_mutex);
        hi_axiom(index < _vector.size());
        return *_vector[index];
    }
 
    template<typename Arg>
    [[nodiscard]] size_t insert(Arg&& arg) noexcept requires(std::is_same_v<std::decay_t<Arg>, value_type>)
    {
        hilet lock = std::scoped_lock(_mutex);
 
        hilet[it, is_inserted] = _map.emplace(std::forward<Arg>(arg), _vector.size());
        if (is_inserted) {
            _vector.push_back(std::addressof(it->first));
        }
        return it->second;
    }
 
    template<typename... Args>
    [[nodiscard]] size_t emplace(Args&&...args) noexcept
    {
        hilet lock = std::scoped_lock(_mutex);
 
        hilet[it, is_inserted] = _map.emplace(value_type{std::forward<Args>(args)...}, _vector.size());
        if (is_inserted) {
            _vector.push_back(std::addressof(it->first));
        }
        return it->second;
    }
 
private:
    // clang-format sucks.
    using vector_type = std::vector<const_pointer>;
 
    vector_type _vector;
    map_type _map;
    mutable unfair_mutex _mutex;
};
} // namespace hi::inline v1