1 //===----------------------------------------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_HAS_NO_THREADS
16 _LIBCPP_BEGIN_NAMESPACE_STD
18 #if !defined(_LIBCPP_HAS_NO_TREE_BARRIER)
20 class __barrier_algorithm_base {
22 struct alignas(64) /* naturally-align the heap state */ __state_t
25 __atomic_base<__barrier_phase_t> __phase{0};
29 ptrdiff_t& __expected;
30 unique_ptr<__state_t[]> __state;
33 __barrier_algorithm_base(ptrdiff_t& __expected)
34 : __expected(__expected)
36 size_t const __count = (__expected + 1) >> 1;
37 __state = unique_ptr<__state_t[]>(new __state_t[__count]);
40 bool __arrive(__barrier_phase_t __old_phase)
42 __barrier_phase_t const __half_step = __old_phase + 1,
43 __full_step = __old_phase + 2;
44 size_t __current_expected = __expected,
45 __current = hash<thread::id>()(this_thread::get_id()) % ((__expected + 1) >> 1);
46 for(int __round = 0;; ++__round) {
47 if(__current_expected <= 1)
49 size_t const __end_node = ((__current_expected + 1) >> 1),
50 __last_node = __end_node - 1;
52 if(__current == __end_node)
54 __barrier_phase_t expect = __old_phase;
55 if(__current == __last_node && (__current_expected & 1))
57 if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
58 break; // I'm 1 in 1, go to next __round
60 else if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __half_step, memory_order_acq_rel))
62 return false; // I'm 1 in 2, done with arrival
64 else if(expect == __half_step)
66 if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel))
67 break; // I'm 2 in 2, go to next __round
70 __current_expected = __last_node + 1;
76 _LIBCPP_EXPORTED_FROM_ABI
77 __barrier_algorithm_base * __construct_barrier_algorithm_base(ptrdiff_t& __expected)
79 return new __barrier_algorithm_base(__expected);
81 _LIBCPP_EXPORTED_FROM_ABI
82 bool __arrive_barrier_algorithm_base(__barrier_algorithm_base* __barrier,
83 __barrier_phase_t __old_phase)
85 return __barrier->__arrive(__old_phase);
87 _LIBCPP_EXPORTED_FROM_ABI
88 void __destroy_barrier_algorithm_base(__barrier_algorithm_base* __barrier)
93 #endif //!defined(_LIBCPP_HAS_NO_TREE_BARRIER)
95 _LIBCPP_END_NAMESPACE_STD
97 #endif //_LIBCPP_HAS_NO_THREADS