From 6ea3b5617632e65f3d9fbb919172429b0e52c959 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Thu, 23 Jul 2026 16:35:05 +0200 Subject: kstd: improve shared_ptr implementation --- libs/kstd/kstd/bits/shared_ptr.hpp | 483 +++++++++++++++++++++++-------------- 1 file changed, 308 insertions(+), 175 deletions(-) diff --git a/libs/kstd/kstd/bits/shared_ptr.hpp b/libs/kstd/kstd/bits/shared_ptr.hpp index 34332ace..0d5e0285 100644 --- a/libs/kstd/kstd/bits/shared_ptr.hpp +++ b/libs/kstd/kstd/bits/shared_ptr.hpp @@ -1,9 +1,12 @@ #ifndef KSTD_BITS_SHARED_PTR_HPP #define KSTD_BITS_SHARED_PTR_HPP +#include #include +#include #include #include +#include #include #include @@ -14,29 +17,141 @@ 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 strong_count; - //! The number of weak references to the managed object. - std::atomic weak_count; - //! The deleter for the managed object - void (*deleter)(void *); - - //! Construct a new control block with a given number of references. + //! The type-erased base for the control block of shared and weak pointers. + struct shared_ptr_control_block_base + { + constexpr shared_ptr_control_block_base(std::size_t strong, std::size_t weak) + : m_strong_count(strong) + , m_weak_count(weak) + {} + + //! Virtual destructor to ensure correct deletion through pointer to base. + constexpr virtual ~shared_ptr_control_block_base() = default; + + //! Increase the strong reference count on this control block. + auto acquire_shared() noexcept -> void + { + m_strong_count.fetch_add(1, std::memory_order_relaxed); + } + + //! Increase the weak reference count on this control block. + auto acquire_weak() noexcept -> void + { + m_weak_count.fetch_add(1, std::memory_order_relaxed); + } + + //! Try to increase the strong reference count on this control block. + //! + //! If the managed object is already being disposed, nothing happens. + //! + //! @return true iff. the strong count was increased, false otherwise. + auto try_acquire_shared() noexcept -> bool + { + auto current = m_strong_count.load(std::memory_order_relaxed); + while (current != 0) + { + if (m_strong_count.compare_exchange_weak(current, current + 1, std::memory_order::acquire, + std::memory_order::relaxed)) + { + return true; + } + } + return false; + } + + //! Decrease the strong reference count. //! - //! @param deleter The function to use to delete the managed object - explicit shared_control_block(void (*deleter)(void *)) - : strong_count(1) - , weak_count(1) - , deleter(deleter) + //! If, as part of executing this operation, the strong reference count hits 0, the managed object will be + //! destroyed. + auto release_shared() -> void + { + if (m_strong_count.fetch_sub(1, std::memory_order::acq_rel) == 1) + { + destroy_object(); + release_weak(); + } + } + + auto release_weak() -> void + { + if (m_weak_count.fetch_sub(1, std::memory_order::acq_rel) == 1) + { + delete this; + } + } + + [[nodiscard]] auto strong_count() const noexcept -> std::size_t + { + return m_strong_count.load(std::memory_order::relaxed); + } + + protected: + //! Destroy the managed object. + //! + //! It is the responsibility of the derived control block to ensure the managed object is correctly deleted. + constexpr virtual auto destroy_object() -> void = 0; + + private: + std::atomic m_strong_count; + std::atomic m_weak_count; + }; + + //! The control block used by shared pointers and weak pointers. + template + struct shared_ptr_control_block final : shared_ptr_control_block_base + { + using deleter = Deleter; + using pointer = OriginalType *; + + shared_ptr_control_block(pointer pointer, deleter deleter) + : shared_ptr_control_block_base{1, 1} + , m_deleter{deleter} + , m_pointer{pointer} {} + + constexpr auto destroy_object() -> void override + { + m_deleter(m_pointer); + } + + private: + [[no_unique_address]] deleter m_deleter; + pointer m_pointer; }; + template + struct make_shared_control_block final : shared_ptr_control_block_base + { + template + explicit make_shared_control_block(Args &&... args) + : shared_ptr_control_block_base{1, 1} + { + std::construct_at(std::bit_cast(m_storage.data()), std::forward(args)...); + } + + [[nodiscard]] auto get_pointer() noexcept -> ObjectType * + { + return std::bit_cast(m_storage.data()); + } + + protected: + constexpr auto destroy_object() -> void override + { + std::destroy_at(std::bit_cast(m_storage.data())); + } + + private: + alignas(ObjectType) std::array m_storage; + }; + + struct weak_ptr_locked_t + { + } constexpr inline weak_ptr_locked{}; + + struct make_shared_allocated_t + { + } constexpr inline make_shared_allocated{}; + template struct is_shared_pointer_ctor_compatible : std::false_type { @@ -84,23 +199,30 @@ namespace kstd template friend struct shared_ptr; + template + friend struct weak_ptr; + + template + friend auto make_shared(Args &&... args) -> shared_ptr; + //! The type of object referred to by this instance. using element_type = std::remove_extent_t; + using pointer = element_type *; //! Construct an empty weak pointer. constexpr weak_ptr() noexcept - : m_storage(nullptr) + : m_pointer(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_pointer(other.m_pointer) , m_control_block(other.m_control_block) { if (m_control_block != nullptr) { - ++(m_control_block->weak_count); + m_control_block->acquire_weak(); } } @@ -108,12 +230,12 @@ namespace kstd template requires bits::is_shared_pointer_ctor_compatible::value constexpr weak_ptr(weak_ptr const & other) - : m_storage(other.m_storage) + : m_pointer(other.m_pointer) , m_control_block(other.m_control_block) { if (m_control_block != nullptr) { - ++(m_control_block->weak_count); + m_control_block->acquire_weak(); } } @@ -121,18 +243,18 @@ namespace kstd template requires bits::is_shared_pointer_ctor_compatible::value constexpr weak_ptr(shared_ptr const & other) - : m_storage(other.m_storage) + : m_pointer(other.m_pointer) , m_control_block(other.m_control_block) { if (m_control_block != nullptr) { - ++(m_control_block->weak_count); + m_control_block->acquire_weak(); } } //! 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_pointer(std::exchange(other.m_pointer, nullptr)) , m_control_block(std::exchange(other.m_control_block, nullptr)) {} @@ -140,7 +262,7 @@ namespace kstd template requires std::is_convertible_v constexpr weak_ptr(weak_ptr && other) noexcept - : m_storage(std::exchange(other.m_storage, nullptr)) + : m_pointer(std::exchange(other.m_pointer, nullptr)) , m_control_block(std::exchange(other.m_control_block, nullptr)) {} @@ -187,12 +309,7 @@ namespace kstd { if (m_control_block) { - if (!--m_control_block->weak_count) - { - delete m_control_block; - m_control_block = nullptr; - m_storage = nullptr; - } + m_control_block->release_weak(); } } @@ -205,7 +322,7 @@ namespace kstd //! 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_pointer, other.m_pointer); std::ranges::swap(m_control_block, other.m_control_block); } @@ -220,7 +337,7 @@ namespace kstd { if (m_control_block) { - return m_control_block->strong_count; + return m_control_block->strong_count(); } return 0; } @@ -234,7 +351,11 @@ namespace kstd //! Create a shared pointer that manages the object, if any, managed by this weak pointer. [[nodiscard]] auto lock() const -> shared_ptr { - return expired() ? shared_ptr{} : shared_ptr(*this); + if (m_control_block && m_control_block->try_acquire_shared()) + { + return shared_ptr{m_pointer, m_control_block, bits::weak_ptr_locked}; + } + return shared_ptr{}; } //! Check if this weak pointer precedes another one in owner-based order. @@ -252,8 +373,8 @@ namespace kstd } private: - T * m_storage; - bits::shared_control_block * m_control_block; + pointer m_pointer; + bits::shared_ptr_control_block_base * m_control_block; }; //! Deduction guide for construction from a shared pointer. @@ -294,8 +415,11 @@ namespace kstd 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(enable_shared_from_this const &) {} + + auto operator=(enable_shared_from_this const &) -> enable_shared_from_this & {} + ~enable_shared_from_this() = default; void internal_assign_ptr(shared_ptr const & ptr) const @@ -327,19 +451,26 @@ namespace kstd template friend struct weak_ptr; + template + friend auto make_shared(Args &&... args) -> shared_ptr; + + //! The type of object referred to by this instance. + using element_type = std::remove_extent_t; + using weak_type = weak_ptr; + /** * @brief Construct an empty shared_ptr. */ constexpr shared_ptr() noexcept - : m_storage(nullptr) + : m_pointer(nullptr) , m_control_block(nullptr) {} /** * @brief Construct an empty shared_ptr from nullptr. */ - shared_ptr(std::nullptr_t) noexcept - : m_storage(nullptr) + constexpr shared_ptr(std::nullptr_t) noexcept + : m_pointer(nullptr) , m_control_block(nullptr) {} @@ -350,11 +481,23 @@ namespace kstd */ template requires(std::is_convertible_v) - explicit shared_ptr(U * pointer = nullptr) - : m_storage(pointer) - , m_control_block(pointer != nullptr - ? new bits::shared_control_block([](auto object) { delete static_cast(object); }) - : nullptr) + constexpr explicit shared_ptr(U * pointer) + : m_pointer(pointer) + , m_control_block( + new bits::shared_ptr_control_block>{pointer, std::default_delete{}}) + { + assign_enable_shared_from_this(pointer); + } + + //! Construct a new shared pointer managing the given object with the given deleter. + //! + //! @param pointer A pointer to the object to manage. + //! @param deleter The deleter to use when destroying the object. + template + requires(std::is_convertible_v) + constexpr shared_ptr(Y * pointer, Deleter deleter) + : m_pointer(pointer) + , m_control_block(new bits::shared_ptr_control_block{pointer, deleter}) { assign_enable_shared_from_this(pointer); } @@ -368,21 +511,13 @@ namespace kstd template requires(std::is_convertible_v) explicit shared_ptr(weak_ptr const & other) - : m_storage(nullptr) + : m_pointer(nullptr) , m_control_block(nullptr) { - if (other.m_control_block) + if (other.m_control_block && other.m_control_block->try_acquire_shared()) { - 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; - } + m_pointer = other.m_pointer; + m_control_block = other.m_control_block; } } @@ -393,12 +528,12 @@ namespace kstd //! @param pointer The pointer this shared_ptr should own. template shared_ptr(shared_ptr const & other, T * pointer) noexcept - : m_storage{pointer} + : m_pointer{pointer} , m_control_block{other.m_control_block} { if (m_control_block != nullptr) { - ++(m_control_block->strong_count); + m_control_block->acquire_shared(); } } @@ -408,12 +543,12 @@ namespace kstd * @param other The shared_ptr to copy from. */ shared_ptr(shared_ptr const & other) - : m_storage(other.m_storage) + : m_pointer(other.m_pointer) , m_control_block(other.m_control_block) { if (m_control_block != nullptr) { - ++(m_control_block->strong_count); + m_control_block->acquire_shared(); } } @@ -426,12 +561,12 @@ namespace kstd template requires(std::is_convertible_v) shared_ptr(shared_ptr const & other) - : m_storage(other.m_storage) + : m_pointer(other.m_pointer) , m_control_block(other.m_control_block) { if (m_control_block != nullptr) { - ++(m_control_block->strong_count); + m_control_block->acquire_shared(); } } @@ -441,12 +576,9 @@ namespace kstd * @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; - } + : m_pointer(std::exchange(other.m_pointer, nullptr)) + , m_control_block(std::exchange(other.m_control_block, nullptr)) + {} /** * @brief Converting move constructor for compatible shared_ptr types. @@ -457,12 +589,9 @@ namespace kstd template requires(std::is_convertible_v) 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; - } + : m_pointer(std::exchange(other.m_pointer, nullptr)) + , m_control_block(std::exchange(other.m_control_block, nullptr)) + {} /** * @brief Copy assignment operator. Replaces the managed object with the one managed by r. Shares ownership of the @@ -474,18 +603,7 @@ namespace kstd */ 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); - } - } - + shared_ptr(other).swap(*this); return *this; } @@ -500,15 +618,7 @@ namespace kstd requires(std::is_convertible_v) auto operator=(shared_ptr 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); - } - + shared_ptr(other).swap(*this); return *this; } @@ -521,15 +631,7 @@ namespace kstd */ 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; - } - + shared_ptr(std::move(other)).swap(*this); return *this; } @@ -544,12 +646,7 @@ namespace kstd requires(std::is_convertible_v) auto operator=(shared_ptr && 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; - + shared_ptr(std::move(other)).swap(*this); return *this; } @@ -559,7 +656,7 @@ namespace kstd auto operator=(std::nullptr_t) noexcept -> shared_ptr & { cleanup(); - m_storage = nullptr; + m_pointer = nullptr; m_control_block = nullptr; return *this; } @@ -572,6 +669,42 @@ namespace kstd cleanup(); } + //! Check if two shared pointer objects point to the same object. + //! + //!@tparam Y, 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 + [[nodiscard]] constexpr auto friend operator==(shared_ptr const & lhs, shared_ptr const & rhs) noexcept -> bool + { + return lhs.get() == rhs.get(); + } + + //! Lexicographically compare two shared pointer objects based on the objects they point to. + //! + //! @tparam Y, 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 + [[nodiscard]] constexpr auto friend operator<=>(shared_ptr const & lhs, shared_ptr const & rhs) noexcept + -> std::strong_ordering + { + return std::compare_three_way{}(lhs.get(), rhs.get()); + } + + //! Check if a shared pointer points to no object. + [[nodiscard]] constexpr friend auto operator==(shared_ptr const & lhs, std::nullptr_t) noexcept -> bool + { + return !lhs; + } + + //! Lexicographically compare a shared pointer to a null pointer. + [[nodiscard]] constexpr friend auto operator<=>(shared_ptr const & lhs, std::nullptr_t) noexcept + -> std::strong_ordering + { + return std::compare_three_way{}(lhs.get(), static_cast(nullptr)); + } + /** * @brief Replaces the managed object. * @@ -579,12 +712,7 @@ namespace kstd */ void reset(T * ptr = nullptr) { - cleanup(); - m_storage = ptr; - m_control_block = ptr != nullptr - ? new bits::shared_control_block([](auto object) { delete static_cast(object); }) - : nullptr; - assign_enable_shared_from_this(ptr); + shared_ptr(ptr).swap(*this); } /** @@ -595,8 +723,8 @@ namespace kstd */ void swap(shared_ptr & other) { - std::swap(m_storage, other.m_storage); - std::swap(m_control_block, other.m_control_block); + std::ranges::swap(m_pointer, other.m_pointer); + std::ranges::swap(m_control_block, other.m_control_block); } /** @@ -606,7 +734,7 @@ namespace kstd */ [[nodiscard]] auto operator*() const -> T & { - return *m_storage; + return *m_pointer; } /** @@ -616,7 +744,7 @@ namespace kstd */ [[nodiscard]] auto operator->() const -> T * { - return m_storage; + return m_pointer; } /** @@ -626,7 +754,7 @@ namespace kstd */ [[nodiscard]] auto get() const -> T * { - return m_storage; + return m_pointer; } /** @@ -644,7 +772,7 @@ namespace kstd { if (m_control_block != nullptr) { - return m_control_block->strong_count; + return m_control_block->strong_count(); } return 0; @@ -657,26 +785,24 @@ namespace kstd */ [[nodiscard]] explicit operator bool() const { - return m_storage != nullptr; + return m_pointer != nullptr; } - /** - * @brief Compare shared_ptr with nullptr. - */ - [[nodiscard]] auto operator==(std::nullptr_t) const -> bool + private: + shared_ptr(T * pointer, bits::shared_ptr_control_block_base * control_block, bits::weak_ptr_locked_t) noexcept + : m_pointer(pointer) + , m_control_block(control_block) { - return m_storage == nullptr; + assign_enable_shared_from_this(pointer); } - /** - * @brief Compare nullptr with shared_ptr. - */ - [[nodiscard]] friend auto operator==(std::nullptr_t, shared_ptr const & ptr) -> bool + shared_ptr(T * pointer, bits::shared_ptr_control_block_base * control_block, bits::make_shared_allocated_t) noexcept + : m_pointer(pointer) + , m_control_block(control_block) { - return ptr.m_storage == nullptr; + assign_enable_shared_from_this(pointer); } - 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 @@ -688,11 +814,11 @@ namespace kstd template auto assign_enable_shared_from_this(U * candidate) -> void { - if constexpr (requires(U * p, shared_ptr const & sp) { p->internal_assign_ptr(sp); }) + if constexpr (requires(U * p) { p->internal_assign_ptr(shared_ptr{}); }) { if (candidate != nullptr) { - candidate->internal_assign_ptr(*this); + candidate->internal_assign_ptr(shared_ptr(*this, candidate)); } } } @@ -704,21 +830,14 @@ namespace kstd { if (m_control_block != nullptr) { - if (--(m_control_block->strong_count) == 0) - { - m_control_block->deleter(m_storage); - m_storage = nullptr; - - if (--(m_control_block->weak_count) == 0) - { - delete m_control_block; - } - } + m_control_block->release_shared(); + m_pointer = nullptr; + m_control_block = nullptr; } } - T * m_storage; ///< The managed object. - bits::shared_control_block * m_control_block; ///< Shared control block. + T * m_pointer; ///< The pointed-to object. + bits::shared_ptr_control_block_base * m_control_block; ///< Shared control block. }; /** @@ -737,7 +856,7 @@ namespace kstd /** * @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(new T(std::forward(args)...)). + * not an array type. * * @tparam T Type of the managed object. * @tparam Args Argument types for T's constructor. @@ -745,39 +864,53 @@ namespace kstd * @returns Shared_pointer of an instance of type T. */ template - auto make_shared(Args &&... args) -> shared_ptr + [[nodiscard]] auto make_shared(Args &&... args) -> shared_ptr { - return shared_ptr(new T(std::forward(args)...)); + auto control_block = new bits::make_shared_control_block{std::forward(args)...}; + auto pointer = control_block->get_pointer(); + return shared_ptr{pointer, control_block, bits::make_shared_allocated}; } template - [[nodiscard]] auto static_pointer_cast(shared_ptr const & other) noexcept -> shared_ptr + [[nodiscard]] constexpr auto static_pointer_cast(shared_ptr const & other) noexcept -> shared_ptr { - return shared_ptr{other, static_cast(other.get())}; + return shared_ptr{other, static_cast::element_type *>(other.get())}; } - /** - * @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 - [[nodiscard]] auto inline operator==(shared_ptr const & lhs, shared_ptr const & rhs) -> bool + [[nodiscard]] constexpr auto static_pointer_cast(shared_ptr && other) noexcept -> shared_ptr { - return lhs.get() == rhs.get(); + return shared_ptr{std::move(other), static_cast::element_type *>(other.get())}; + } + + template + [[nodiscard]] constexpr auto dynamic_pointer_cast(shared_ptr const & other) noexcept -> shared_ptr = delete; + + template + [[nodiscard]] constexpr auto dynamic_pointer_cast(shared_ptr && other) noexcept -> shared_ptr = delete; + + template + [[nodiscard]] constexpr auto const_pointer_cast(shared_ptr const & other) noexcept -> shared_ptr + { + return shared_ptr{other, const_cast::element_type *>(other.get())}; + } + + template + [[nodiscard]] constexpr auto const_pointer_cast(shared_ptr && other) noexcept -> shared_ptr + { + return shared_ptr{std::move(other), const_cast::element_type *>(other.get())}; + } + + template + [[nodiscard]] constexpr auto reinterpret_pointer_cast(shared_ptr const & other) noexcept -> shared_ptr + { + return shared_ptr{other, reinterpret_cast::element_type *>(other.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 - [[nodiscard]] auto inline operator<=>(shared_ptr const & lhs, shared_ptr const & rhs) + [[nodiscard]] constexpr auto reinterpret_pointer_cast(shared_ptr && other) noexcept -> shared_ptr { - return lhs.get() <=> rhs.get(); + return shared_ptr{std::move(other), reinterpret_cast::element_type *>(other.get())}; } } // namespace kstd -- cgit v1.2.3