20 #include <type_traits> 36 enum class queue_op_status : uint8_t
44 enum struct buffer_queue_policy : uint8_t
52 buffer_queue_policy buffer_policy = buffer_queue_policy::dynamic>
57 using buffer_type = buffer_t;
58 using value_type =
typename buffer_type::value_type;
59 using size_type =
typename buffer_type::size_type;
60 using reference = void;
61 using const_reference = void;
64 buffer_queue() : buffer_queue{0u}
66 buffer_queue(buffer_queue
const &) =
delete;
67 buffer_queue(buffer_queue &&) =
default;
68 buffer_queue & operator=(buffer_queue
const &) =
delete;
69 buffer_queue & operator=(buffer_queue &&) =
default;
70 ~buffer_queue() =
default;
73 explicit buffer_queue(size_type
const init_capacity)
75 data.resize(init_capacity + 1);
76 roundSize =
static_cast<size_type
>(1) << static_cast<size_type>(std::log2(
data.size() - 1) + 1);
79 template <std::ranges::InputRange range_type>
81 buffer_queue(size_type
const init_capacity, range_type && r) : buffer_queue{init_capacity}
89 template <
typename value2_t>
91 void push(value2_t && value)
93 detail::spin_delay delay{};
97 auto status = try_push(std::forward<value2_t>(value));
98 if (status == queue_op_status::closed)
99 throw queue_op_status::closed;
100 else if (status == queue_op_status::success)
104 assert(status == queue_op_status::full);
109 template <
typename value2_t>
111 queue_op_status wait_push(value2_t && value)
113 detail::spin_delay delay{};
117 auto status = try_push(std::forward<value2_t>(value));
119 if (status != queue_op_status::full)
123 assert(status == queue_op_status::full);
128 value_type value_pop()
130 detail::spin_delay delay{};
135 auto status = try_pop(value);
137 if (status == queue_op_status::closed)
138 throw queue_op_status::closed;
139 else if (status == queue_op_status::success)
142 assert(status != queue_op_status::full);
148 queue_op_status wait_pop(value_type & value)
150 detail::spin_delay delay{};
155 status = try_pop(value);
157 if (status == queue_op_status::closed || status == queue_op_status::success)
160 assert(status != queue_op_status::full);
171 template <
typename value2_t>
173 queue_op_status try_push(value2_t &&);
175 queue_op_status try_pop(value_t &);
181 void close() noexcept
183 closed_flag.store(
true, std::memory_order_release);
186 bool is_closed() const noexcept
188 return closed_flag.load(std::memory_order_acquire);
194 return headPos == tailPos;
197 bool is_full() const noexcept
200 return size_impl() ==
data.max_size();
203 size_type
size() const noexcept
212 size_type size_impl() const noexcept
214 size_type mask = roundSize - 1;
215 if ((headPos & mask) <= (tailPos & mask))
216 return tailPos - headPos;
218 return tailPos - headPos - (roundSize -
data.size());
221 size_type cyclic_increment(size_type value,
231 if ((++value & (roundSize - 1)) >= modulo)
232 value += roundSize - modulo;
236 template <
typename value2_t>
238 (buffer_policy == buffer_queue_policy::fixed)
239 bool overflow(value2_t &&)
244 template <
typename value2_t>
246 (buffer_policy == buffer_queue_policy::dynamic)
247 bool overflow(value2_t && value);
261 template <std::Semiregular value_t, SequenceContainer buffer_t = std::vector<value_t>>
262 using fixed_buffer_queue = buffer_queue<value_t, buffer_t, buffer_queue_policy::fixed>;
265 template <std::Semiregular value_t, SequenceContainer buffer_t = std::vector<value_t>>
266 using dynamic_buffer_queue = buffer_queue<value_t, buffer_t, buffer_queue_policy::dynamic>;
276 template <
typename value_t,
typename buffer_t, buffer_queue_policy buffer_policy>
277 template <
typename value2_t>
279 (buffer_policy == buffer_queue_policy::dynamic)
280 inline bool buffer_queue<value_t, buffer_t, buffer_policy>::overflow(value2_t && value)
284 size_type cap =
data.size();
285 size_type roundSize = this->roundSize;
286 size_type headPos = this->headPos;
287 size_type tailPos = this->tailPos;
289 assert(tailPos == this->tailWritePos);
290 assert(headPos == this->headReadPos);
292 bool valueWasAppended =
false;
295 if (cyclic_increment(tailPos, cap, roundSize) >= headPos + roundSize)
301 *it = std::forward<value2_t>(value);
302 tailPos = headPos + roundSize;
303 valueWasAppended =
true;
306 assert(tailPos == headPos + roundSize);
309 size_type headIdx = headPos & (roundSize - 1);
310 size_type tailIdx = tailPos & (roundSize - 1);
313 data.resize(cap + 1);
314 size_type delta =
data.size() - cap;
316 roundSize =
static_cast<size_type
>(1) << ((
data.size() > 1) ? static_cast<size_type>(std::log2(
data.size() - 1) + 1) : 1);
321 this->headReadPos = this->headPos = headIdx + delta;
322 this->tailWritePos = this->tailPos = tailIdx + roundSize;
324 this->roundSize = roundSize;
326 return valueWasAppended;
363 template <
typename value_t,
typename buffer_t, buffer_queue_policy buffer_policy>
364 inline queue_op_status buffer_queue<value_t, buffer_t, buffer_policy>::try_pop(value_t & result)
369 size_type cap =
data.size();
370 size_type roundSize = this->roundSize;
371 size_type headReadPos;
372 size_type newHeadReadPos;
373 detail::spin_delay spinDelay;
378 headReadPos = this->headReadPos;
379 size_type tailPos = this->tailPos;
381 assert(headReadPos <= tailPos);
384 if (headReadPos == tailPos)
387 return queue_op_status::closed;
391 newHeadReadPos = cyclic_increment(headReadPos, cap, roundSize);
393 if (this->headReadPos.compare_exchange_weak(headReadPos, newHeadReadPos))
404 detail::spin_delay delay{};
405 size_type old = headReadPos;
406 while (!this->headPos.compare_exchange_weak(old, newHeadReadPos))
413 return queue_op_status::success;
440 template <
typename value_t,
typename buffer_t, buffer_queue_policy buffer_policy>
441 template <
typename value2_t>
443 inline queue_op_status buffer_queue<value_t, buffer_t, buffer_policy>::try_push(value2_t && value)
447 detail::spin_delay delay{};
452 return queue_op_status::closed;
454 size_type cap =
data.size();
455 size_type roundSize = this->roundSize;
459 size_type tailWritePos = this->tailWritePos;
460 size_type newTailWritePos = cyclic_increment(tailWritePos, cap, roundSize);
461 size_type headPos = this->headPos;
463 assert(newTailWritePos <= (headPos + roundSize + 1));
466 if (newTailWritePos >= headPos + roundSize)
469 if (this->tailWritePos.compare_exchange_weak(tailWritePos, newTailWritePos))
472 *it = std::forward<value2_t>(value);
477 detail::spin_delay delay{};
478 size_type old = tailWritePos;
479 while (!this->tailPos.compare_exchange_weak(old, newTailWritePos))
485 return queue_op_status::success;
493 if (overflow(std::forward<value2_t>(value)))
495 return queue_op_status::success;
499 return queue_op_status::full;
Provides C++17/20 additions to the <new> header, if they are not already available.
Subsumes std::Copyable and std::DefaultConstructible.
::ranges::size size
Alias for ranges::size. Obtains the size of a range whose size can be calculated in constant time...
Definition: ranges:189
::ranges::data data
Alias for ranges::data. Returns a pointer the block of data of a ContiguousRange. ...
Definition: ranges:184
::ranges::iter_move iter_move
Alias for ranges::iter_move. Casts the result of dereferencing an object to its associated rvalue ref...
Definition: iterator:336
constexpr std::size_t hardware_destructive_interference_size
Minimum offset between two objects to avoid false sharing.
Definition: new:33
Definition: buffer_queue.hpp:32
Adaptations of concepts from the Ranges TS.
::ranges::begin begin
Alias for ranges::begin. Returns an iterator to the beginning of a range.
Definition: ranges:174
Provides std::span from the C++20 standard library.
::ranges::copy copy
Alias for ranges::copy. Copies a range of elements to a new location.
Definition: algorithm:44
::ranges::move_backward move_backward
Alias for ranges::move_backward. Moves a range of elements backward to a new location starting from t...
Definition: algorithm:84
Adaptations of algorithms from the Ranges TS.
::ranges::empty empty
Alias for ranges::empty. Checks whether a range is empty.
Definition: ranges:194
Provides seqan3::detail::spin_delay.
Provides various transformation traits used by the range module.
Adaptations of concepts from the standard library.
The concept std::ConvertibleTo<From, To> specifies that an expression of the type and value category ...