path: root/libs/kstd/kstd/bits/shared_ptr.hpp

#ifndef KSTD_BITS_SHARED_PTR_HPP
#define KSTD_BITS_SHARED_PTR_HPP

#include <atomic>
#include <concepts>
#include <cstddef>
#include <type_traits>
#include <utility>

// IWYU pragma: private, include <kstd/memory.hpp>

namespace kstd
{

  namespace bits
  {
    //! The control block used by shared pointers and weak pointers.
    //!
    //! @see shared_ptr
    //! @see weak_ptr
    struct shared_control_block
    {
      //! The number of strong references to the managed object.
      std::atomic<std::size_t> strong_count;
      //! The number of weak  references to the managed object.
      std::atomic<std::size_t> weak_count;

      //! Construct a new control block with a given number of references.
      //!
      //! @param shared The number of strong references.
      //! @param weak The number of weak references.
      explicit shared_control_block(std::size_t shared = 1, std::size_t weak = 1)
          : strong_count(shared)
          , weak_count(weak)
      {}
    };

    template<typename Y, typename T>
    struct is_shared_pointer_ctor_compatible : std::false_type
    {
    };

    template<typename Y, typename T>
    struct is_shared_pointer_ctor_compatible<Y *, T *> : std::is_convertible<Y *, T *>
    {
    };

    template<typename U, std::size_t N>
    struct is_shared_pointer_ctor_compatible<U (*)[N], U (*)[]>  // NOLINT(modernize-avoid-c-arrays)
        : std::true_type
    {
    };

    template<typename U, std::size_t N>
    struct is_shared_pointer_ctor_compatible<U (*)[N], U const (*)[]>  // NOLINT(modernize-avoid-c-arrays)
        : std::true_type
    {
    };

    template<typename U, std::size_t N>
    struct is_shared_pointer_ctor_compatible<U (*)[N], U volatile (*)[]>  // NOLINT(modernize-avoid-c-arrays)
        : std::true_type
    {
    };

    template<typename U, std::size_t N>
    struct is_shared_pointer_ctor_compatible<U (*)[N], U volatile const (*)[]>  // NOLINT(modernize-avoid-c-arrays)
        : std::true_type
    {
    };
  }  // namespace bits

  template<typename T>
  struct shared_ptr;

  //! A pointer type to hold a non-owning reference to an object managed by a share pointer.
  //!
  //! @tparam T The type of the object referenced by this weak pointer.
  template<typename T>
  struct weak_ptr
  {
    template<typename U>
    friend struct shared_ptr;

    //! Construct an empty weak pointer.
    constexpr weak_ptr() noexcept
        : m_storage(nullptr)
        , m_control_block(nullptr)
    {}

    //! Construct a weak pointer which shares ownership of the object managed by other.
    constexpr weak_ptr(weak_ptr const & other) noexcept
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      if (m_control_block != nullptr)
      {
        ++(m_control_block->weak_count);
      }
    }

    //! Construct a weak pointer which shares ownership of the object managed by other.
    template<typename Y>
      requires bits::is_shared_pointer_ctor_compatible<Y *, T *>::value
    constexpr weak_ptr(weak_ptr<Y> const & other)
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      if (m_control_block != nullptr)
      {
        ++(m_control_block->weak_count);
      }
    }

    //! Construct a weak pointer which shares ownership of the object managed by other.
    template<typename Y>
      requires bits::is_shared_pointer_ctor_compatible<Y *, T *>::value
    constexpr weak_ptr(shared_ptr<Y> const & other)
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      if (m_control_block != nullptr)
      {
        ++(m_control_block->weak_count);
      }
    }

    //! Construct a weak pointer which takes ownership of the object managed by other.
    constexpr weak_ptr(weak_ptr && other) noexcept
        : m_storage(std::exchange(other.m_storage, nullptr))
        , m_control_block(std::exchange(other.m_control_block, nullptr))
    {}

    //! Construct a weak pointer which takes ownership of the object managed by other.
    template<typename Y>
      requires std::is_convertible_v<Y *, T *>
    constexpr weak_ptr(weak_ptr<Y> && other) noexcept
        : m_storage(std::exchange(other.m_storage, nullptr))
        , m_control_block(std::exchange(other.m_control_block, nullptr))
    {}

    //! Replace the object managed by this pointer with the one managed by another one.
    auto operator=(weak_ptr const & other) noexcept -> weak_ptr &
    {
      weak_ptr<T>{other}.swap(*this);
      return *this;
    }

    //! Replace the object managed by this pointer with the one managed by another one.
    template<typename Y>
    constexpr auto operator=(weak_ptr<Y> const & other) noexcept -> weak_ptr &
    {
      weak_ptr<T>{other}.swap(*this);
      return *this;
    }

    //! Replace the object managed by this pointer with the one managed by shared pointer.
    template<typename Y>
    constexpr auto operator=(shared_ptr<Y> const & other) noexcept -> weak_ptr &
    {
      weak_ptr<T>{other}.swap(*this);
      return *this;
    }

    //! Replace the object managed by this pointer with the one managed by another one.
    auto operator=(weak_ptr && other) noexcept -> weak_ptr &
    {
      weak_ptr<T>{std::move(other)}.swap(*this);
      return *this;
    }

    //! Replace the object managed by this pointer with the one managed by another one.
    template<typename Y>
    auto operator=(weak_ptr<Y> && other) noexcept -> weak_ptr &
    {
      weak_ptr<T>{std::move(other)}.swap(*this);
      return *this;
    }

    //! Destroy this pointer, cleaning up resources if necessary.
    ~weak_ptr()
    {
      if (m_control_block)
      {
        if (!m_control_block->weak_count.fetch_sub(1))
        {
          delete m_control_block;
          m_control_block = nullptr;
          m_storage = nullptr;
        }
      }
    }

    //! Release the reference to the object managed by this weak pointer.
    constexpr auto reset() -> void
    {
      weak_ptr<T>{}.swap(*this);
    }

    //! Exchange the ownership of the object managed by this pointer with the one of another one.
    constexpr auto swap(weak_ptr & other) -> void
    {
      std::ranges::swap(m_storage, other.m_storage);
      std::ranges::swap(m_control_block, other.m_control_block);
    }

    //! Exchange the ownership of the object managed by weak pointer objects.
    constexpr auto friend swap(weak_ptr & lhs, weak_ptr & rhs) noexcept -> void
    {
      return lhs.swap(rhs);
    }

    //! Get the number of shared pointers that share ownership with the object managed by this weak pointer.
    [[nodiscard]] constexpr auto use_count() const noexcept -> long
    {
      if (m_control_block)
      {
        return m_control_block->strong_count;
      }
      return 0;
    }

    //! Check if the object managed by this weak pointer has already been deleted.
    [[nodiscard]] constexpr auto expired() const noexcept -> bool
    {
      return use_count() == 0;
    }

    //! Create a shared pointer that manages the object, if any, managed by this weak pointer.
    [[nodiscard]] auto lock() const -> shared_ptr<T>
    {
      return expired() ? shared_ptr<T>{} : shared_ptr<T>(*this);
    }

    //! Check if this weak pointer precedes another one in owner-based order.
    template<typename Y>
    [[nodiscard]] auto owner_before(weak_ptr<Y> const & other) const noexcept -> bool
    {
      return m_control_block < other.m_control_block;
    }

    //! Check if this weak pointer precedes a shared pointer in owner-based order.
    template<typename Y>
    [[nodiscard]] auto owner_before(shared_ptr<Y> const & other) const noexcept -> bool
    {
      return m_control_block < other.m_control_block;
    }

  private:
    T * m_storage;
    bits::shared_control_block * m_control_block;
  };

  //! Deduction guide for construction from a shared pointer.
  template<typename T>
  weak_ptr(shared_ptr<T>) -> weak_ptr<T>;

  /**
   * @brief enable_shared_from_this is a base class that allows an object that is currently managed by a shared_ptr to
   * create additional shared_ptr instances that share ownership of the same object. This is usefl when you want to
   * create shared_ptr instances in a member function of the object.
   *
   * @tparam T The type of the managed object.
   */
  template<typename T>
  struct enable_shared_from_this
  {
    template<typename U>
    friend struct shared_ptr;

    friend T;

  public:
    /**
     * @brief Returns a shared_ptr that shares ownership of *this.
     */
    auto shared_from_this() -> shared_ptr<T>
    {
      return shared_ptr<T>(m_weak_this);
    }

    /**
     * @brief Returns a shared_ptr that shares ownership of *this.
     */
    auto shared_from_this() const -> shared_ptr<T const>
    {
      return shared_ptr<T const>(m_weak_this);
    }

  private:
    enable_shared_from_this() = default;
    enable_shared_from_this(enable_shared_from_this const &) = default;
    auto operator=(enable_shared_from_this const &) -> enable_shared_from_this & = default;
    ~enable_shared_from_this() = default;

    void internal_assign_ptr(shared_ptr<T> const & ptr) const
    {
      m_weak_this = ptr;
    }

    mutable weak_ptr<T> m_weak_this{};  ///< Weak pointer to the object, used for shared_from_this functionality.
  };

  /**
   * @brief Shared_pointer is a smart pointer that retains shared ownership of an object through a pointer. Several
   * shared_ptr objects may own the same object. The object is destroyed and its memory deallocated when either of
   * the following happens: the last remaining shared_ptr owning the object is destroyed; the last remaining
   * shared_ptr owning the object is assigned another pointer via operator= or reset(). A
   * shared_ptr can share ownership of an object while storing a pointer to another object. This feature can be used
   * to point to member objects while owning the object they belong to. The stored pointer is the one accessed by get(),
   * the dereference and the comparison operators. The managed pointer is the one passed to the deleter when use count
   * reaches zero.
   *
   * @tparam T The type of the managed object.
   */
  template<typename T>
  struct shared_ptr
  {
    template<typename U>
    friend struct shared_ptr;

    template<typename U>
    friend struct weak_ptr;

    /**
     * @brief Construct an empty shared_ptr.
     */
    shared_ptr() noexcept
        : m_storage(nullptr)
        , m_control_block(nullptr)
    {}

    /**
     * @brief Construct an empty shared_ptr from nullptr.
     */
    shared_ptr(std::nullptr_t) noexcept
        : m_storage(nullptr)
        , m_control_block(nullptr)
    {}

    /**
     * @brief Constructor.
     *
     * @param pointer A pointer to an object to manage (default is nullptr).
     */
    template<typename U>
      requires(std::is_convertible_v<U *, T *>)
    explicit shared_ptr(U * pointer = nullptr)
        : m_storage(pointer)
        , m_control_block(pointer != nullptr ? new bits::shared_control_block() : nullptr)
    {
      assign_enable_shared_from_this(pointer);
    }

    /**
     * @brief Constructor a shared_ptr from a weak_ptr. If other is not expired, constructs a shared_ptr which shares
     * ownership of the object managed by other. Otherwise, constructs an empty shared_ptr.
     *
     * @param other The weak_ptr to construct from.
     */
    template<typename U>
      requires(std::is_convertible_v<U *, T *>)
    explicit shared_ptr(weak_ptr<U> const & other)
        : m_storage(nullptr)
        , m_control_block(nullptr)
    {
      if (other.m_control_block)
      {
        auto count = other.m_control_block->strong_count.load(std::memory_order::relaxed);
        while (count != 0 && !other.m_control_block->strong_count.compare_exchange_weak(
                                 count, count + 1, std::memory_order::acquire, std::memory_order::relaxed))
          ;

        if (count != 0)
        {
          m_storage = other.m_storage;
          m_control_block = other.m_control_block;
        }
      }
    }

    /**
     * @brief Copy constructor.
     *
     * @param other The shared_ptr to copy from.
     */
    shared_ptr(shared_ptr const & other)
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      if (m_control_block != nullptr)
      {
        ++(m_control_block->strong_count);
      }
    }

    /**
     * @brief Converting copy constructor for compatible shared_ptr types.
     *
     * @tparam U Source pointer element type.
     * @param other The shared_ptr to copy from.
     */
    template<typename U>
      requires(std::is_convertible_v<U *, T *>)
    shared_ptr(shared_ptr<U> const & other)
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      if (m_control_block != nullptr)
      {
        ++(m_control_block->strong_count);
      }
    }

    /**
     * @brief Move constructor.
     *
     * @param other The shared_ptr to move from.
     */
    shared_ptr(shared_ptr && other) noexcept
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      other.m_storage = nullptr;
      other.m_control_block = nullptr;
    }

    /**
     * @brief Converting move constructor for compatible shared_ptr types.
     *
     * @tparam U Source pointer element type.
     * @param other The shared_ptr to move from.
     */
    template<typename U>
      requires(std::is_convertible_v<U *, T *>)
    shared_ptr(shared_ptr<U> && other) noexcept
        : m_storage(other.m_storage)
        , m_control_block(other.m_control_block)
    {
      other.m_storage = nullptr;
      other.m_control_block = nullptr;
    }

    /**
     * @brief Copy assignment operator. Replaces the managed object with the one managed by r. Shares ownership of the
     * object managed by r. If r manages no object, *this manages no object too. Equivalent to
     * shared_ptr<T>(r).swap(*this).
     *
     * @param other Another smart pointer to share the ownership with.
     * @return Reference to this shared pointer.
     */
    auto operator=(shared_ptr const & other) -> shared_ptr &
    {
      if (this != &other)
      {
        cleanup();
        m_storage = other.m_storage;
        m_control_block = other.m_control_block;

        if (m_control_block != nullptr)
        {
          ++(m_control_block->strong_count);
        }
      }

      return *this;
    }

    /**
     * @brief Converting copy assignment for compatible shared_ptr types.
     *
     * @tparam U Source pointer element type.
     * @param other Another smart pointer to share ownership with.
     * @return Reference to this shared pointer.
     */
    template<typename U>
      requires(std::is_convertible_v<U *, T *>)
    auto operator=(shared_ptr<U> const & other) -> shared_ptr &
    {
      cleanup();
      m_storage = other.m_storage;
      m_control_block = other.m_control_block;

      if (m_control_block != nullptr)
      {
        ++(m_control_block->strong_count);
      }

      return *this;
    }

    /**
     * @brief Move assignment operator. Move-assigns a shared_ptr from r. After the assignment, *this contains a copy of
     * the previous state of r, and r is empty. Equivalent to shared_ptr<T>(std::move(r)).swap(*this).
     *
     * @param other Another smart pointer to acquire the ownership from.
     * @return Reference to this shared pointer.
     */
    auto operator=(shared_ptr && other) noexcept -> shared_ptr &
    {
      if (this != &other)
      {
        cleanup();
        m_storage = other.m_storage;
        m_control_block = other.m_control_block;
        other.m_storage = nullptr;
        other.m_control_block = nullptr;
      }

      return *this;
    }

    /**
     * @brief Converting move assignment for compatible shared_ptr types.
     *
     * @tparam U Source pointer element type.
     * @param other Another smart pointer to acquire ownership from.
     * @return Reference to this shared pointer.
     */
    template<typename U>
      requires(std::is_convertible_v<U *, T *>)
    auto operator=(shared_ptr<U> && other) noexcept -> shared_ptr &
    {
      cleanup();
      m_storage = other.m_storage;
      m_control_block = other.m_control_block;
      other.m_storage = nullptr;
      other.m_control_block = nullptr;

      return *this;
    }

    /**
     * @brief Reset this shared_ptr to empty via nullptr assignment.
     */
    auto operator=(std::nullptr_t) noexcept -> shared_ptr &
    {
      cleanup();
      m_storage = nullptr;
      m_control_block = nullptr;
      return *this;
    }

    /**
     * @brief Destructor. Cleans up resources if necessary.
     */
    ~shared_ptr()
    {
      cleanup();
    }

    /**
     * @brief Replaces the managed object.
     *
     * @param ptr Pointer to a new object to manage (default = nullptr).
     */
    void reset(T * ptr = nullptr)
    {
      cleanup();
      m_storage = ptr;
      m_control_block = ptr != nullptr ? new bits::shared_control_block() : nullptr;
      assign_enable_shared_from_this(ptr);
    }

    /**
     * @brief Exchanges the stored pointer values and the ownerships of *this and r. Reference counts, if any, are not
     * adjusted.
     *
     * @param other The shared_ptr to swap with.
     */
    void swap(shared_ptr & other)
    {
      std::swap(m_storage, other.m_storage);
      std::swap(m_control_block, other.m_control_block);
    }

    /**
     * @brief Dereference operator. If get() is a null pointer, the behavior is undefined.
     *
     * @return Returns the object owned by *this, equivalent to *get().
     */
    [[nodiscard]] auto operator*() const -> T &
    {
      return *m_storage;
    }

    /**
     * @brief Member access operator.
     *
     * @return Returns a pointer to the object owned by *this, i.e. get().
     */
    [[nodiscard]] auto operator->() const -> T *
    {
      return m_storage;
    }

    /**
     * @brief Returns a pointer to the managed object or nullptr if no object is owned.
     *
     * @return Pointer to the managed object or nullptr if no object is owned.
     */
    [[nodiscard]] auto get() const -> T *
    {
      return m_storage;
    }

    /**
     * @brief Returns the number of different shared_ptr instances (*this included) managing the current object. If
     * there is no managed object, ​0​ is returned.
     *
     * @note Common use cases include comparison with ​0​. If use_count returns zero, the shared pointer is empty
     * and manages no objects (whether or not its stored pointer is nullptr). Comparison with 1. If use_count returns 1,
     * there are no other owners.
     *
     * @return The number of Shared_pointer instances managing the current object or ​0​ if there is no managed
     * object.
     */
    [[nodiscard]] auto use_count() const -> std::size_t
    {
      if (m_control_block != nullptr)
      {
        return m_control_block->strong_count;
      }

      return 0;
    }

    /**
     * @brief Checks whether *this owns an object, i.e. whether get() != nullptr.
     *
     * @return true if *this owns an object, false otherwise.
     */
    [[nodiscard]] explicit operator bool() const
    {
      return m_storage != nullptr;
    }

    /**
     * @brief Compare shared_ptr with nullptr.
     */
    [[nodiscard]] auto operator==(std::nullptr_t) const -> bool
    {
      return m_storage == nullptr;
    }

    /**
     * @brief Compare nullptr with shared_ptr.
     */
    [[nodiscard]] friend auto operator==(std::nullptr_t, shared_ptr const & ptr) -> bool
    {
      return ptr.m_storage == nullptr;
    }

  private:
    /**
     * @brief If the candidate type inherits from enable_shared_from_this, assigns the internal weak pointer to this
     * shared_ptr. This weak_ptr is used to implement shared_from_this functionality for the candidate type. If the
     * candidate type does not inherit from enable_shared_from_this, this function does nothing.
     *
     * @tparam U The candidate type to check for enable_shared_from_this inheritance.
     * @param candidate The candidate object to assign the internal weak pointer for.
     */
    template<typename U>
    auto assign_enable_shared_from_this(U * candidate) -> void
    {
      if constexpr (requires(U * p, shared_ptr<T> const & sp) { p->internal_assign_ptr(sp); })
      {
        if (candidate != nullptr)
        {
          candidate->internal_assign_ptr(*this);
        }
      }
    }

    /**
     * @brief Releases ownership and deletes the object if this was the last reference to the owned managed object.
     */
    auto cleanup() -> void
    {
      if (m_control_block != nullptr)
      {
        if (--(m_control_block->strong_count) == 0)
        {
          delete m_storage;
          m_storage = nullptr;

          if (--(m_control_block->weak_count) == 0)
          {
            delete m_control_block;
          }
        }
      }
    }

    T * m_storage;                                 ///< The managed object.
    bits::shared_control_block * m_control_block;  ///< Shared control block.
  };

  /**
   * @brief Specializes the std::swap algorithm for stl::unique_ptr. Swaps the contents of lhs and rhs. Calls
   * lhs.swap(rhs).
   *
   * @tparam T Type of the managed object.
   * @param lhs, rhs Smart pointers whose contents to swap.
   */
  template<typename T>
  auto swap(shared_ptr<T> & lhs, shared_ptr<T> & rhs) -> void
  {
    lhs.swap(rhs);
  }

  /**
   * @brief Constructs an object of type T and wraps it in a shared_ptr. Constructs a non-array type T. The
   * arguments args are passed to the constructor of T. This overload participates in overload resolution only if T is
   * not an array type. The function is equivalent to: shared_ptr<T>(new T(std::forward<Args>(args)...)).
   *
   * @tparam T Type of the managed object.
   * @tparam Args Argument types for T's constructor.
   * @param args List of arguments with which an instance of T will be constructed.
   * @returns Shared_pointer of an instance of type T.
   */
  template<typename T, typename... Args>
  auto make_shared(Args &&... args) -> shared_ptr<T>
  {
    return shared_ptr<T>(new T(std::forward<Args>(args)...));
  }

  /**
   * @brief Equality operator for shared_ptr. Two shared_ptr instances are equal if they point to the same object
   * @tparam T, U Types of the managed objects of the shared_ptr instances being compared.
   * @param lhs, rhs The shared_ptr instances to compare.
   * @return true if lhs and rhs point to the same object, false otherwise.
   */
  template<typename T, typename U>
  [[nodiscard]] auto inline operator==(shared_ptr<T> const & lhs, shared_ptr<U> const & rhs) -> bool
  {
    return lhs.get() == rhs.get();
  }

  /**
   * @brief Three-way comparison operator for shared_ptr. Compares the stored pointers of lhs and rhs using operator<=>.
   * @tparam T, U Types of the managed objects of the shared_ptr instances being compared.
   * @param lhs, rhs The shared_ptr instances to compare.
   * @return The result of comparing the stored pointers of lhs and rhs using operator<=>
   */
  template<typename T, typename U>
  [[nodiscard]] auto inline operator<=>(shared_ptr<T> const & lhs, shared_ptr<U> const & rhs)
  {
    return lhs.get() <=> rhs.get();
  }
}  // namespace kstd

#endif