6 #ifndef XENIUM_CHASE_WORK_STEALING_DEQUE_HPP
7 #define XENIUM_CHASE_WORK_STEALING_DEQUE_HPP
9 #include <xenium/parameter.hpp>
10 #include <xenium/policy.hpp>
11 #include <xenium/detail/fixed_size_circular_array.hpp>
12 #include <xenium/detail/growing_circular_array.hpp>
37 template <
class T,
class... Policies>
39 using value_type = T*;
40 static constexpr std::size_t capacity = parameter::value_param_t<std::size_t,
policy::capacity, 128, Policies...>::value;
41 using container = parameter::type_param_t<policy::container, detail::growing_circular_array<T, capacity>, Policies...>;
51 bool try_push(value_type item);
52 [[nodiscard]]
bool try_pop(value_type &result);
53 [[nodiscard]]
bool try_steal(value_type &result);
56 auto t = top.load(std::memory_order_relaxed);
57 return bottom.load(std::memory_order_relaxed) - t; }
60 std::atomic<std::size_t> bottom;
61 std::atomic<std::size_t> top;
64 template <
class T,
class... Policies>
70 template <
class T,
class... Policies>
71 bool chase_work_stealing_deque<T, Policies...>::try_push(value_type item) {
72 auto b = bottom.load(std::memory_order_relaxed);
73 auto t = top.load(std::memory_order_relaxed);
75 if (size >= items.capacity()) {
76 if (items.can_grow()) {
78 assert(size < items.capacity());
85 items.put(b, item, std::memory_order_relaxed);
88 bottom.store(b + 1, std::memory_order_release);
92 template <
class T,
class... Policies>
93 bool chase_work_stealing_deque<T, Policies...>::try_pop(value_type &result) {
94 auto b = bottom.load(std::memory_order_relaxed);
95 auto t = top.load(std::memory_order_relaxed);
105 bottom.store(b, std::memory_order_seq_cst);
107 auto item = items.get(b, std::memory_order_relaxed);
109 t = top.load(std::memory_order_seq_cst);
116 if (top.compare_exchange_strong(t, t + 1, std::memory_order_relaxed)) {
117 bottom.store(t + 1, std::memory_order_relaxed);
121 bottom.store(t, std::memory_order_relaxed);
127 bottom.store(t, std::memory_order_relaxed);
131 template <
class T,
class... Policies>
132 bool chase_work_stealing_deque<T, Policies...>::try_steal(value_type &result) {
133 auto t = top.load(std::memory_order_relaxed);
137 auto b = bottom.load(std::memory_order_seq_cst);
138 auto size = (int)b - (
int)t;
142 auto item = items.get(t, std::memory_order_relaxed);
144 if (top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst, std::memory_order_relaxed)) {
A lock-free work stealing deque.
Definition: chase_work_stealing_deque.hpp:38
Policy to configure the capacity of various containers.
Definition: policy.hpp:61