33 #ifndef _GLIBCXX_BARRIER
34 #define _GLIBCXX_BARRIER 1
36 #pragma GCC system_header
38 #if __cplusplus > 201703L
40 #if __cpp_lib_atomic_wait && __cpp_aligned_new
46 #define __cpp_lib_barrier 201907L
48 namespace std _GLIBCXX_VISIBILITY(default)
50 _GLIBCXX_BEGIN_NAMESPACE_VERSION
52 struct __empty_completion
54 _GLIBCXX_ALWAYS_INLINE
void
73 enum class __barrier_phase_t : unsigned char { };
75 template<
typename _CompletionF>
78 using __atomic_phase_ref_t = std::__atomic_ref<__barrier_phase_t>;
79 using __atomic_phase_const_ref_t = std::__atomic_ref<const __barrier_phase_t>;
80 static constexpr
auto __phase_alignment =
81 __atomic_phase_ref_t::required_alignment;
84 struct alignas(64) __state_t
86 alignas(__phase_alignment) __tickets_t __tickets;
89 ptrdiff_t _M_expected;
90 unique_ptr<__state_t[]> _M_state;
91 __atomic_base<ptrdiff_t> _M_expected_adjustment;
92 _CompletionF _M_completion;
94 alignas(__phase_alignment) __barrier_phase_t _M_phase;
97 _M_arrive(__barrier_phase_t __old_phase,
size_t __current)
99 const auto __old_phase_val =
static_cast<unsigned char>(__old_phase);
100 const auto __half_step =
101 static_cast<__barrier_phase_t
>(__old_phase_val + 1);
102 const auto __full_step =
103 static_cast<__barrier_phase_t
>(__old_phase_val + 2);
105 size_t __current_expected = _M_expected;
106 __current %= ((_M_expected + 1) >> 1);
108 for (
int __round = 0; ; ++__round)
110 if (__current_expected <= 1)
112 size_t const __end_node = ((__current_expected + 1) >> 1),
113 __last_node = __end_node - 1;
114 for ( ; ; ++__current)
116 if (__current == __end_node)
118 auto __expect = __old_phase;
119 __atomic_phase_ref_t __phase(_M_state[__current]
120 .__tickets[__round]);
121 if (__current == __last_node && (__current_expected & 1))
123 if (__phase.compare_exchange_strong(__expect, __full_step,
124 memory_order_acq_rel))
127 else if (__phase.compare_exchange_strong(__expect, __half_step,
128 memory_order_acq_rel))
132 else if (__expect == __half_step)
134 if (__phase.compare_exchange_strong(__expect, __full_step,
135 memory_order_acq_rel))
139 __current_expected = __last_node + 1;
145 using arrival_token = __barrier_phase_t;
147 static constexpr ptrdiff_t
149 {
return __PTRDIFF_MAX__; }
151 __tree_barrier(ptrdiff_t __expected, _CompletionF __completion)
152 : _M_expected(__expected), _M_expected_adjustment(0),
153 _M_completion(
move(__completion)),
154 _M_phase(static_cast<__barrier_phase_t>(0))
156 size_t const __count = (_M_expected + 1) >> 1;
158 _M_state = std::make_unique<__state_t[]>(__count);
161 [[nodiscard]] arrival_token
162 arrive(ptrdiff_t __update)
166 __atomic_phase_ref_t __phase(_M_phase);
167 const auto __old_phase = __phase.load(memory_order_relaxed);
168 const auto __cur =
static_cast<unsigned char>(__old_phase);
169 for(; __update; --__update)
171 if(_M_arrive(__old_phase, __current))
174 _M_expected += _M_expected_adjustment.load(memory_order_relaxed);
175 _M_expected_adjustment.store(0, memory_order_relaxed);
176 auto __new_phase =
static_cast<__barrier_phase_t
>(__cur + 2);
177 __phase.store(__new_phase, memory_order_release);
178 __phase.notify_all();
185 wait(arrival_token&& __old_phase)
const
187 __atomic_phase_const_ref_t __phase(_M_phase);
188 auto const __test_fn = [=]
190 return __phase.load(memory_order_acquire) != __old_phase;
192 std::__atomic_wait_address(&_M_phase, __test_fn);
198 _M_expected_adjustment.fetch_sub(1, memory_order_relaxed);
203 template<
typename _CompletionF = __empty_completion>
208 using __algorithm_t = __tree_barrier<_CompletionF>;
212 class arrival_token final
215 arrival_token(arrival_token&&) =
default;
216 arrival_token&
operator=(arrival_token&&) =
default;
217 ~arrival_token() =
default;
220 friend class barrier;
221 using __token =
typename __algorithm_t::arrival_token;
222 explicit arrival_token(__token __tok) noexcept : _M_tok(__tok) { }
226 static constexpr ptrdiff_t
231 barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
232 : _M_b(__count, std::
move(__completion))
235 barrier(barrier
const&) =
delete;
236 barrier&
operator=(barrier
const&) =
delete;
238 [[nodiscard]] arrival_token
239 arrive(ptrdiff_t __update = 1)
240 {
return arrival_token{_M_b.arrive(__update)}; }
243 wait(arrival_token&& __phase)
const
244 { _M_b.wait(
std::move(__phase._M_tok)); }
252 { _M_b.arrive_and_drop(); }
255 _GLIBCXX_END_NAMESPACE_VERSION
257 #endif // __cpp_lib_atomic_wait && __cpp_aligned_new
258 #endif // __cplusplus > 201703L
259 #endif // _GLIBCXX_BARRIER
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Primary class template hash.
A standard container for storing a fixed size sequence of elements.
thread::id get_id() noexcept
this_thread::get_id
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.