rcu.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 "wfree_idle_count.hpp"
#include "unfair_mutex.hpp"
#include <vector>
#include <tuple>
#include <mutex>
#include <memory>
 
namespace hi::inline v1 {
 
template<typename T, typename Allocator = std::allocator<T>>
class rcu {
public:
    using value_type = T;
    using allocator_type = Allocator;
 
    constexpr rcu(allocator_type allocator = allocator_type{}) noexcept : _allocator(allocator) {}
 
    ~rcu() = default;
    rcu(rcu const&) = delete;
    rcu(rcu&&) = delete;
    rcu& operator=(rcu const&) = delete;
    rcu& operator=(rcu&&) = delete;
 
    void lock() const noexcept
    {
        _idle_count.lock();
    }
 
    void unlock() const noexcept
    {
        _idle_count.unlock();
    }
 
    value_type const *get() const noexcept
    {
        return _ptr.load(std::memory_order::acquire);
    }
 
    value_type const *unsafe_get() noexcept
    {
#if defined(__alpha__) or defined(__alpha) or defined(_M_ALPHA)
        return _ptr.load(std::memory_order::acquire);
#else
        return _ptr.load(std::memory_order::relaxed);
#endif
    }
 
    [[nodiscard]] uint64_t version() const noexcept
    {
        return *_idle_count;
    }
 
    [[nodiscard]] size_t capacity() const noexcept
    {
        hilet lock = std::scoped_lock(_old_ptrs_mutex);
        return _old_ptrs.size() + not empty();
    }
 
    [[nodiscard]] value_type *exchange(value_type *ptr) noexcept
    {
        return _ptr.exchange(ptr, std::memory_order::release);
    }
 
    [[nodiscard]] value_type *copy(value_type const *ptr) const noexcept
    {
        hi_axiom(ptr != nullptr);
        value_type *new_ptr = std::allocator_traits<allocator_type>::allocate(_allocator, 1);
        std::allocator_traits<allocator_type>::construct(_allocator, new_ptr, *ptr);
        return std::launder(new_ptr);
    }
 
    [[nodiscard]] value_type *copy() const noexcept
    {
        auto *new_ptr = std::allocator_traits<allocator_type>::allocate(_allocator, 1);
        lock();
        value_type const * const ptr = get();
        hi_axiom(ptr != nullptr);
        std::allocator_traits<allocator_type>::construct(_allocator, new_ptr, *ptr);
        unlock();
        return std::launder(new_ptr);
    }
 
    void abort(value_type *ptr) const noexcept
    {
        std::allocator_traits<allocator_type>::destroy(_allocator, ptr);
        std::allocator_traits<allocator_type>::deallocate(_allocator, ptr, 1);
    }
 
    void commit(value_type *ptr) noexcept
    {
        lock();
        auto *old_ptr = exchange(ptr);
        auto old_version = version();
        unlock();
        add_old_copy(old_version, old_ptr);
    }
 
    void emplace(auto&&...args) noexcept
    {
        value_type *const new_ptr = std::allocator_traits<allocator_type>::allocate(_allocator, 1);
        std::allocator_traits<allocator_type>::construct(_allocator, new_ptr, hi_forward(args)...);
 
        lock();
        auto *const old_ptr = exchange(new_ptr);
        hilet old_version = version();
        unlock();
 
        add_old_copy(old_version, old_ptr);
    }
 
    [[nodiscard]] bool empty() const noexcept
    {
        return not to_bool(_ptr.load(std::memory_order::relaxed));
    }
 
    explicit operator bool() const noexcept
    {
        return not empty();
    }
 
    void reset() noexcept
    {
        lock();
        auto *const old_ptr = _ptr.exchange(nullptr, std::memory_order::release);
        hilet old_version = *_idle_count;
        unlock();
 
        add_old_copy(old_version, old_ptr);
    }
 
    rcu& operator=(nullptr_t) noexcept
    {
        reset();
        return *this;
    }
 
    void add_old_copy(uint64_t old_version, value_type *old_ptr) noexcept
    {
        if (not old_ptr) {
            return;
        }
 
        hilet new_version = version();
 
        hilet lock = std::scoped_lock(_old_ptrs_mutex);
        _old_ptrs.emplace_back(old_version, old_ptr);
 
        // Destroy all objects from previous idle-count versions.
        auto it = _old_ptrs.begin();
        while (it != _old_ptrs.end() and it->first < new_version) {
            std::allocator_traits<allocator_type>::destroy(_allocator, it->second);
            std::allocator_traits<allocator_type>::deallocate(_allocator, it->second, 1);
            ++it;
        }
        _old_ptrs.erase(_old_ptrs.begin(), it);
    }
 
private:
    std::atomic<value_type *> _ptr = nullptr;
    mutable wfree_idle_count _idle_count;
 
    mutable allocator_type _allocator;
    mutable unfair_mutex _old_ptrs_mutex;
    std::vector<std::pair<uint64_t, value_type *>> _old_ptrs;
};
 
} // namespace hi::inline v1