CopyOnWrite
copy_on_write.hpp
// SPDX-License-Identifier: BSL-1.0
#ifndef XYZ_COPY_ON_WRITE_HPP
#define XYZ_COPY_ON_WRITE_HPP
#include <atomic>
#include <cassert>
#include <compare>
#include <cstddef>
#include <functional>
#include <memory>
#include <memory_resource>
#include <type_traits>
#include <utility>
namespace xyz {
template <typename T, typename Allocator = std::allocator<T>>
class copy_on_write;
namespace detail {
template <typename F, typename T>
concept action = std::invocable<F, T&> && std::same_as<std::invoke_result_t<F, T&>, void>;
template <typename F, typename T>
concept transformation =
std::invocable<F, T const&> && std::same_as<std::invoke_result_t<F, T const&>, T>;
template <typename>
inline constexpr bool is_copy_on_write_v = false;
template <typename T, typename A>
inline constexpr bool is_copy_on_write_v<copy_on_write<T, A>> = true;
template <typename>
inline constexpr bool is_in_place_type_v = false;
template <typename T>
inline constexpr bool is_in_place_type_v<std::in_place_type_t<T>> = true;
template <typename T, typename U>
requires std::three_way_comparable_with<T, U>
constexpr auto synth_three_way(T const& t, U const& u) -> std::compare_three_way_result_t<T, U>
6
{
return t <=> u;
6
}
template <typename T, typename U>
requires(requires(T const& t, U const& u) {
{ t < u } -> std::convertible_to<bool>;
{ u < t } -> std::convertible_to<bool>;
} && !std::three_way_comparable_with<T, U>)
constexpr auto synth_three_way(T const& t, U const& u) -> std::weak_ordering
3
{
if (t < u) {
3
return std::weak_ordering::less;
1
}
if (u < t) {
2
return std::weak_ordering::greater;
1
}
return std::weak_ordering::equivalent;
1
}
template <typename T, typename U = T>
using synth_three_way_result =
decltype(synth_three_way(std::declval<T const&>(), std::declval<U const&>()));
} // namespace detail
template <typename T, typename Allocator>
class copy_on_write
{
using alloc_traits = std::allocator_traits<Allocator>;
static_assert(std::is_object_v<T>, "T must be an object type");
static_assert(!std::is_array_v<T>, "T must not be an array type");
static_assert(!std::is_same_v<T, std::in_place_t>, "T must not be std::in_place_t");
static_assert(!detail::is_in_place_type_v<T>,
"T must not be a specialization of std::in_place_type_t");
static_assert(!std::is_const_v<T> && !std::is_volatile_v<T>, "T must not be cv-qualified");
static_assert(std::is_same_v<T, typename alloc_traits::value_type>,
"Allocator::value_type must be T");
public:
using value_type = T;
using allocator_type = Allocator;
using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
//
// Member functions
//
explicit copy_on_write()
7
requires std::default_initializable<Allocator>
: _alloc{}
7
, _self{_make_model(_alloc)}
7
{
static_assert(std::is_default_constructible_v<T>);
}
7
template <typename U = T>
requires(!std::same_as<std::remove_cvref_t<U>, copy_on_write> &&
!std::same_as<std::remove_cvref_t<U>, std::in_place_t> &&
std::constructible_from<T, U> && std::default_initializable<Allocator>)
explicit copy_on_write(U&& x)
190
: _alloc{}
190
, _self{_make_model(_alloc, std::forward<U>(x))}
190
{
}
190
template <typename... Us>
requires(std::constructible_from<T, Us...> && std::default_initializable<Allocator>)
explicit copy_on_write(std::in_place_t, Us&&... us)
1
: _alloc{}
1
, _self{_make_model(_alloc, std::forward<Us>(us)...)}
1
{
}
1
template <typename I, typename... Us>
requires(std::constructible_from<T, std::initializer_list<I>&, Us...> &&
std::default_initializable<Allocator>)
explicit copy_on_write(std::in_place_t, std::initializer_list<I> ilist, Us&&... us)
4
: _alloc{}
4
, _self{_make_model(_alloc, ilist, std::forward<Us>(us)...)}
4
{
}
4
explicit copy_on_write(std::allocator_arg_t, Allocator const& a)
1
: _alloc{a}
1
, _self{_make_model(_alloc)}
1
{
static_assert(std::is_default_constructible_v<T>);
}
1
template <typename U = T>
requires(!std::same_as<std::remove_cvref_t<U>, copy_on_write> &&
!std::same_as<std::remove_cvref_t<U>, std::in_place_t> &&
std::constructible_from<T, U>)
explicit copy_on_write(std::allocator_arg_t, Allocator const& a, U&& u)
48
: _alloc{a}
48
, _self{_make_model(_alloc, std::forward<U>(u))}
48
{
}
46
template <typename... Us>
requires std::constructible_from<T, Us...>
explicit copy_on_write(std::allocator_arg_t, Allocator const& a, std::in_place_t, Us&&... us)
1
: _alloc{a}
1
, _self{_make_model(_alloc, std::forward<Us>(us)...)}
1
{
}
1
template <typename I, typename... Us>
requires std::constructible_from<T, std::initializer_list<I>&, Us...>
explicit copy_on_write(std::allocator_arg_t, Allocator const& a, std::in_place_t,
1
std::initializer_list<I> ilist, Us&&... us)
: _alloc{a}
1
, _self{_make_model(_alloc, ilist, std::forward<Us>(us)...)}
1
{
}
1
explicit copy_on_write(std::allocator_arg_t, Allocator const& a, copy_on_write const& other)
8
: _alloc{a}
8
, _self{nullptr}
8
{
static_assert(std::is_copy_constructible_v<T>);
if (other.valueless_after_move()) {
8
return;
1
}
if (a == other._alloc) {
8
_self = other._self;
5
_self->count.fetch_add(1, std::memory_order_relaxed);
5
} else {
_self = _make_model(_alloc, *other);
2
}
}
explicit copy_on_write(std::allocator_arg_t, Allocator const& a,
3
copy_on_write&& other) noexcept(alloc_traits::is_always_equal::value)
: _alloc{a}
3
, _self{nullptr}
3
{
if (other.valueless_after_move()) {
3
return;
1
}
if (alloc_traits::is_always_equal::value || a == other._alloc) {
1
_self = std::exchange(other._self, nullptr);
1
} else {
_self = _make_model(_alloc, std::move(*other));
1
other._reset(nullptr);
1
}
}
copy_on_write(copy_on_write const& x)
24
: _alloc{alloc_traits::select_on_container_copy_construction(x._alloc)}
24
, _self{nullptr}
24
{
static_assert(std::is_copy_constructible_v<T>);
if (x.valueless_after_move()) {
24
return;
1
}
if (alloc_traits::is_always_equal::value || _alloc == x._alloc) {
4
_self = x._self;
21
_self->count.fetch_add(1, std::memory_order_relaxed);
21
} else {
_self = _make_model(_alloc, *x);
2
}
}
copy_on_write(copy_on_write&& other) noexcept
20
: _alloc{other._alloc}
20
, _self{std::exchange(other._self, nullptr)}
20
{
}
20
~copy_on_write()
343
{
assert(valueless_after_move() || _self->count > 0);
343
if (_self != nullptr && _self->count.fetch_sub(1, std::memory_order_release) == 1) {
620
std::atomic_thread_fence(std::memory_order_acquire);
_destroy_model(_alloc, _self);
243
}
}
343
auto operator=(copy_on_write const& x) -> copy_on_write&
10
{
static_assert(std::is_copy_constructible_v<T>);
if (std::addressof(x) == this) {
10
return *this;
1
}
constexpr bool pocca = alloc_traits::propagate_on_container_copy_assignment::value;
9
if (x.valueless_after_move()) {
9
_reset(nullptr);
1
} else if (pocca || alloc_traits::is_always_equal::value || _alloc == x._alloc) {
2
x._self->count.fetch_add(1, std::memory_order_relaxed);
6
_reset(x._self);
6
} else {
_reset(_make_model(_alloc, *x));
2
}
if constexpr (pocca) {
_alloc = x._alloc;
2
}
return *this;
9
}
auto operator=(copy_on_write&& x) noexcept(
17
alloc_traits::propagate_on_container_move_assignment::value ||
alloc_traits::is_always_equal::value) -> copy_on_write&
{
if (std::addressof(x) == this) {
17
return *this;
2
}
constexpr bool pocma = alloc_traits::propagate_on_container_move_assignment::value;
15
if (x.valueless_after_move()) {
15
_reset(nullptr);
2
} else if (pocma || _alloc == x._alloc) {
2
_reset(std::exchange(x._self, nullptr));
11
} else {
_reset(_make_model(_alloc, std::move(x._self->value)));
2
x._reset(nullptr);
2
}
if constexpr (pocma) {
_alloc = x._alloc;
2
}
return *this;
15
}
template <typename U = T>
requires(!std::same_as<std::remove_cvref_t<U>, copy_on_write> &&
std::constructible_from<T, U> && std::assignable_from<T&, U>)
auto operator=(U&& x) -> copy_on_write&
6
{
if (_self != nullptr && use_count() == 1) {
6
_self->value = std::forward<U>(x);
4
return *this;
4
}
return *this = copy_on_write(std::forward<U>(x));
2
}
//
// Observers
//
auto operator*() const noexcept -> value_type const&
196
{
assert(!valueless_after_move());
196
return _self->value;
196
}
auto operator->() const noexcept -> const_pointer
2
{
assert(!valueless_after_move());
2
return std::pointer_traits<const_pointer>::pointer_to(_self->value);
2
}
[[nodiscard]] auto valueless_after_move() const noexcept -> bool { return _self == nullptr; }
974
[[nodiscard]] auto get_allocator() const noexcept -> allocator_type { return _alloc; }
17
[[nodiscard]] auto use_count() const noexcept -> long
56
{
assert(!valueless_after_move());
56
return _self->count.load(std::memory_order_acquire);
112
}
[[nodiscard]] auto identical_to(copy_on_write const& x) const noexcept -> bool
36
{
assert(!valueless_after_move() && !x.valueless_after_move());
36
return _self == x._self;
36
}
//
// Modifiers
//
template <detail::action<T> Action>
void modify(Action&& action)
10
{
if (use_count() > 1) {
10
auto* p = _make_model(_alloc, std::as_const(_self->value));
6
_self->count.fetch_sub(1, std::memory_order_release);
6
_self = p;
6
}
std::forward<Action>(action)(_self->value);
10
}
10
template <detail::action<T> Action, detail::transformation<T> Transform>
void modify(Action&& action, Transform&& transform)
4
{
if (use_count() > 1) {
4
auto* p =
_make_model(_alloc, std::forward<Transform>(transform)(std::as_const(_self->value)));
2
_self->count.fetch_sub(1, std::memory_order_release);
2
_self = p;
2
} else {
std::forward<Action>(action)(_self->value);
2
}
}
4
void swap(copy_on_write& other) noexcept(alloc_traits::propagate_on_container_swap::value ||
4
alloc_traits::is_always_equal::value)
{
assert(alloc_traits::propagate_on_container_swap::value || _alloc == other._alloc);
6
using std::swap;
swap(_self, other._self);
4
if constexpr (alloc_traits::propagate_on_container_swap::value) {
swap(_alloc, other._alloc);
1
}
}
4
private:
struct model
{
std::atomic<long> count;
value_type value;
};
using model_alloc_t = typename alloc_traits::template rebind_alloc<model>;
template <typename... Args>
static auto _make_model(Allocator& a, Args&&... args)
275
{
auto ma = model_alloc_t{a};
48
auto p = std::allocator_traits<model_alloc_t>::allocate(ma, 1);
275
::new (std::addressof(p->count)) std::atomic<long>{1};
275
try {
alloc_traits::construct(a, std::addressof(p->value), std::forward<Args>(args)...);
275
} catch (...) {
8
std::allocator_traits<model_alloc_t>::deallocate(ma, p, 1);
2
throw;
4
}
return p;
496
}
static void _destroy_model(Allocator& a, model* p)
271
{
auto ma = model_alloc_t{a};
46
alloc_traits::destroy(a, std::addressof(p->value));
271
std::allocator_traits<model_alloc_t>::deallocate(ma, p, 1);
46
}
271
void _reset(model* v)
32
{
if (_self != nullptr && _self->count.fetch_sub(1, std::memory_order_release) == 1) {
64
std::atomic_thread_fence(std::memory_order_acquire);
_destroy_model(_alloc, _self);
28
}
_self = v;
32
}
32
[[no_unique_address]] allocator_type _alloc;
model* _self;
};
template <typename T1, typename A1, typename T2, typename A2>
auto operator==(copy_on_write<T1, A1> const& x,
10
copy_on_write<T2, A2> const& y) noexcept(noexcept(*x == *y)) -> bool
{
if (x.valueless_after_move() || y.valueless_after_move()) {
10
return x.valueless_after_move() == y.valueless_after_move();
4
}
if constexpr (std::same_as<T1, T2> && std::same_as<A1, A2>) {
if (x.identical_to(y)) {
6
return true;
3
}
}
return *x == *y;
3
}
template <typename T, typename A, typename U>
requires(!detail::is_copy_on_write_v<U>)
auto operator==(copy_on_write<T, A> const& x, U const& y) noexcept(noexcept(*x == y)) -> bool
3
{
return !x.valueless_after_move() && (*x == y);
3
}
template <typename T1, typename A1, typename T2, typename A2>
auto operator<=>(copy_on_write<T1, A1> const& x, copy_on_write<T2, A2> const& y)
21
-> detail::synth_three_way_result<T1, T2>
{
if (x.valueless_after_move() || y.valueless_after_move()) {
21
return !x.valueless_after_move() <=> !y.valueless_after_move();
7
}
if constexpr (std::same_as<T1, T2> && std::same_as<A1, A2>) {
if (x.identical_to(y)) {
14
return std::strong_ordering::equal;
2
}
}
return detail::synth_three_way(*x, *y);
12
}
template <typename T, typename A, typename U>
requires(!detail::is_copy_on_write_v<U>)
auto operator<=>(copy_on_write<T, A> const& x, U const& y) -> detail::synth_three_way_result<T, U>
4
{
if (x.valueless_after_move()) {
4
return std::strong_ordering::less;
1
}
return detail::synth_three_way(*x, y);
3
}
template <typename T, typename A>
void swap(copy_on_write<T, A>& x, copy_on_write<T, A>& y) noexcept(noexcept(x.swap(y)))
1
{
x.swap(y);
1
}
1
template <typename Value>
copy_on_write(Value) -> copy_on_write<Value>;
template <typename Allocator, typename Value>
copy_on_write(std::allocator_arg_t, Allocator, Value)
-> copy_on_write<Value, typename std::allocator_traits<Allocator>::template rebind_alloc<Value>>;
namespace pmr {
template <typename T>
using copy_on_write = xyz::copy_on_write<T, std::pmr::polymorphic_allocator<T>>;
} // namespace pmr
} // namespace xyz
template <typename T, typename Allocator>
requires requires(T t) { std::hash<T>{}(t); }
struct std::hash<xyz::copy_on_write<T, Allocator>>
{
constexpr std::size_t operator()(xyz::copy_on_write<T, Allocator> const& x) const
13
noexcept(noexcept(std::hash<T>{}(*x)))
{
if (x.valueless_after_move()) {
13
return static_cast<std::size_t>(-1);
2
}
return std::hash<T>{}(*x);
11
}
};
#endif