generation.h

#ifndef CYCLE_PTR_DETAIL_GENERATION_H
#define CYCLE_PTR_DETAIL_GENERATION_H

#include <atomic>
#include <cassert>
#include <cstdint>
#include <utility>
#include <cycle_ptr/detail/color.h>
#include <cycle_ptr/detail/base_control.h>
#include <cycle_ptr/detail/intrusive_ptr.h>

namespace cycle_ptr {
class gc_operation;
} /* namespace cycle_ptr */

namespace cycle_ptr::detail {


class generation {
  friend class cycle_ptr::gc_operation;

  friend auto intrusive_ptr_add_ref(generation* g)
  noexcept
  -> void {
    assert(g != nullptr);

    [[maybe_unused]]
    std::uintptr_t old = g->refs_.fetch_add(1u, std::memory_order_relaxed);
    assert(old < UINTPTR_MAX);
  }

  friend auto intrusive_ptr_release(generation* g)
  noexcept
  -> void {
    assert(g != nullptr);

    std::uintptr_t old = g->refs_.fetch_sub(1u, std::memory_order_release);
    assert(old > 0u);

    if (old == 1u) delete g;
  }

 private:
  using controls_list = llist<base_control, base_control>;

  generation() = default;

  generation(std::uintmax_t seq)
  : seq_(seq)
  {}

  generation(const generation&) = delete;

#ifndef NDEBUG
  ~generation() noexcept {
    assert(controls_.empty());
    assert(refs_ == 0u);
  }
#else
  ~generation() noexcept = default;
#endif

 public:
  static auto new_generation()
  -> intrusive_ptr<generation> {
    return intrusive_ptr<generation>(new generation(), true);
  }

  static auto new_generation(std::uintmax_t seq)
  -> intrusive_ptr<generation> {
    return intrusive_ptr<generation>(new generation(seq), true);
  }

  static auto order_invariant(const generation& origin, const generation& dest)
  noexcept
  -> bool {
    return origin.seq() < (dest.seq() & ~moveable_seq);
  }

  auto link(base_control& bc) noexcept
  -> void {
    std::lock_guard<std::shared_mutex> lck{ mtx_ };
    controls_.push_back(bc);
  }

  auto unlink(base_control& bc) noexcept
  -> void {
    std::lock_guard<std::shared_mutex> lck{ mtx_ };
    controls_.erase(controls_.iterator_to(bc));
  }

 private:
  static constexpr std::uintmax_t moveable_seq = 0x1;

  static auto new_seq_() noexcept -> std::uintmax_t;

 public:
  auto seq() const
  noexcept
  -> std::uintmax_t {
    return seq_.load(std::memory_order_relaxed);
  }

  auto gc() noexcept -> void;

  static auto fix_ordering(base_control& src, base_control& dst) noexcept
  -> std::shared_lock<std::shared_mutex>;

 private:
  auto gc_() noexcept -> void;

  auto gc_mark_() noexcept -> controls_list::iterator;

  auto gc_phase2_mark_(controls_list::iterator b) noexcept
  -> controls_list::iterator;

  auto gc_sweep_(controls_list::iterator wavefront_end) noexcept
  -> controls_list::iterator;

  auto gc_phase2_sweep_(controls_list::iterator wavefront_end) noexcept
  -> controls_list::iterator;

  static auto merge_(
      std::tuple<intrusive_ptr<generation>, bool> src_tpl,
      std::tuple<intrusive_ptr<generation>, bool> dst_tpl) noexcept
  -> std::tuple<intrusive_ptr<generation>, bool>;

  [[nodiscard]]
  static auto merge0_(
      std::tuple<generation*, bool> x,
      std::tuple<generation*, bool> y,
      [[maybe_unused]] const std::unique_lock<std::shared_mutex>& x_mtx_lck,
      [[maybe_unused]] const std::unique_lock<std::shared_mutex>& x_merge_mtx_lck) noexcept
  -> bool;

 public:
  std::shared_mutex mtx_;
  std::shared_mutex merge_mtx_;

 private:
  controls_list controls_;

 public:
  std::shared_mutex red_promotion_mtx_;

 private:
  std::atomic<std::uintmax_t> seq_ = new_seq_();
  std::atomic<std::uintptr_t> refs_{ 0u };
  std::atomic_flag gc_flag_;
};


} /* namespace cycle_ptr::detail */

#endif /* CYCLE_PTR_DETAIL_GENERATION_H */