6 #ifndef XENIUM_MICHAEL_SCOTT_QUEUE_HPP
7 #define XENIUM_MICHAEL_SCOTT_QUEUE_HPP
9 #include <xenium/acquire_guard.hpp>
10 #include <xenium/backoff.hpp>
11 #include <xenium/parameter.hpp>
12 #include <xenium/policy.hpp>
16 #pragma warning(disable: 4324) // structure was padded due to alignment specifier
36 template <
class T,
class... Policies>
40 using reclaimer = parameter::type_param_t<
policy::reclaimer, parameter::nil, Policies...>;
43 template <
class... NewPolicies>
46 static_assert(parameter::is_set<reclaimer>::value,
"reclaimer policy must be specified");
66 [[nodiscard]]
bool try_pop(T &result);
71 using concurrent_ptr =
typename reclaimer::template concurrent_ptr<node, 0>;
72 using marked_ptr =
typename concurrent_ptr::marked_ptr;
73 using guard_ptr =
typename concurrent_ptr::guard_ptr;
75 struct node : reclaimer::template enable_concurrent_ptr<node>
78 node(T&& v) : value(std::move(v)) {}
84 alignas(64) concurrent_ptr head;
85 alignas(64) concurrent_ptr tail;
88 template <
class T,
class... Policies>
92 head.store(n, std::memory_order_relaxed);
93 tail.store(n, std::memory_order_relaxed);
96 template <
class T,
class... Policies>
97 michael_scott_queue<T, Policies...>::~michael_scott_queue()
100 auto n = head.load(std::memory_order_acquire);
104 auto next = n->next.load(std::memory_order_acquire);
110 template <
class T,
class... Policies>
113 node* n =
new node(std::move(value));
122 t.acquire(tail, std::memory_order_acquire);
126 auto next = t->next.load(std::memory_order_acquire);
127 if (next.get() !=
nullptr)
129 marked_ptr expected(t.get());
131 tail.compare_exchange_weak(expected, next, std::memory_order_release, std::memory_order_relaxed);
138 if (t->next.compare_exchange_weak(
null, n, std::memory_order_release, std::memory_order_relaxed))
145 marked_ptr expected = t.get();
147 tail.compare_exchange_strong(expected, n, std::memory_order_release, std::memory_order_relaxed);
150 template <
class T,
class... Policies>
160 h.acquire(head, std::memory_order_acquire);
164 auto next = acquire_guard(h->next, std::memory_order_acquire);
165 if (head.load(std::memory_order_relaxed).get() != h.get())
170 if (next.get() ==
nullptr)
173 marked_ptr t = tail.load(std::memory_order_relaxed);
176 if (h.get() == t.get())
179 tail.compare_exchange_weak(t, next, std::memory_order_release, std::memory_order_relaxed);
184 marked_ptr expected(h.get());
186 if (head.compare_exchange_weak(expected, next, std::memory_order_release, std::memory_order_relaxed))
189 result = std::move(next->value);