A wait-free single-producer, single-consumer (SPSC) FIFO queue backed by a caller-provided, fixed-size storage buffer.
LockFreeSpscQueue provides a pw::Queue-like interface and synchronizes between a single producer context and a single consumer context using C++ atomics with acquire/release memory ordering rather than locks. This makes it suitable for passing typed elements between two threads or between a thread and an Interrupt Service Routine (ISR).
Like pw::Queue and pw::Deque, LockFreeSpscQueue does not own its underlying storage buffer and is neither copyable nor movable. To instantiate a LockFreeSpscQueue with an inline statically allocated buffer or an owned dynamically allocated buffer, use pw::FixedLockFreeSpscQueue.
Producer operations (push(), try_push(), emplace(), try_emplace(), push_some(), move_push_some(), try_push_all(), try_move_push_all(), BeginWrite()) may be called concurrently with consumer operations (front(), try_peek(), pop(), try_pop(), pop_some(), pop_n(), BeginRead()), provided there is at most one active producer context and at most one active consumer context at any time. Size observers (empty(), full(), size(), remaining_capacity()) may be called concurrently from either the producer or the consumer context (not from a third independent thread). clear() and destruction require exclusive access with no concurrent producer or consumer operations.
arm-none-eabi-g++), std::atomic loads and stores are lowered directly to inline hardware load/store instructions and dmb barriers. Under Clang (--target=armv6m-none-eabi), std::atomic loads and stores are lowered to __atomic_load_* and __atomic_store_* library calls (pw_atomic masks interrupts via PRIMASK).| T | The type of elements stored in the queue. |
| SizeType | Unsigned integer type used to store sizes and indices. Defaults to size_t rather than a smaller integer type to ensure that atomic operations on indices are lock-free across all supported target architectures. |
Classes | |
| class | ReadTransaction |
| class | WriteTransaction |
Public Types | |
| using | value_type = T |
| The type of elements stored in the queue. | |
| using | size_type = SizeType |
| Unsigned integer type used for indexing and sizes. | |
| using | difference_type = ptrdiff_t |
| Signed integer type for pointer differences. | |
| using | reference = value_type & |
| Mutable reference to an element. | |
| using | const_reference = const value_type & |
| Const reference to an element. | |
| using | pointer = value_type * |
| Pointer to an element. | |
| using | const_pointer = const value_type * |
| Const pointer to an element. | |
Public Member Functions | |
| constexpr | LockFreeSpscQueue (span< std::byte > unaligned_buffer) noexcept |
| template<size_t kAlignment, size_t kSizeBytes> | |
| constexpr | LockFreeSpscQueue (containers::Storage< kAlignment, kSizeBytes > &storage) noexcept |
| LockFreeSpscQueue (const LockFreeSpscQueue &)=delete | |
| LockFreeSpscQueue & | operator= (const LockFreeSpscQueue &)=delete |
| LockFreeSpscQueue (LockFreeSpscQueue &&)=delete | |
| LockFreeSpscQueue & | operator= (LockFreeSpscQueue &&)=delete |
| ~LockFreeSpscQueue () | |
| reference | front () |
| const_reference | front () const |
| pointer | try_peek () noexcept |
| const_pointer | try_peek () const noexcept |
| bool | empty () const noexcept |
| bool | full () const noexcept |
| size_type | size () const noexcept |
| constexpr size_type | capacity () const noexcept |
| constexpr size_type | max_size () const noexcept |
| size_type | remaining_capacity () const noexcept |
| void | clear () noexcept |
| void | push (const value_type &value) |
| void | push (value_type &&value) |
| bool | try_push (const value_type &value) |
| bool | try_push (value_type &&value) |
| template<typename... Args> | |
| void | emplace (Args &&... args) |
| template<typename... Args> | |
| bool | try_emplace (Args &&... args) |
| void | pop () |
| std::optional< value_type > | try_pop () |
| bool | try_pop (value_type &out) |
| WriteTransaction | BeginWrite () noexcept |
| ReadTransaction | BeginRead () noexcept |
| size_type | push_some (span< const value_type > items) |
| size_type | move_push_some (span< value_type > items) |
| bool | try_push_all (span< const value_type > items) |
| bool | try_move_push_all (span< value_type > items) |
| size_type | pop_some (span< value_type > dest) |
| size_type | pop_n (size_type count) noexcept |
Static Public Attributes | |
| static constexpr size_type | kMaxCapacity |
|
inlineexplicitconstexprnoexcept |
Constructs an empty LockFreeSpscQueue using the provided buffer for storage.
unaligned_buffer.size() / sizeof(value_type)) must not exceed kMaxCapacity.| [in] | unaligned_buffer | Storage for the queue. If the buffer is not aligned as value_type, an aligned subset of the buffer will be used. If the buffer is too small to hold at least one value_type, the queue's capacity will be 0. |
|
inlineexplicitconstexprnoexcept |
Constructs an empty LockFreeSpscQueue using a pw::containers::Storage buffer. This constructor avoids runtime alignment checks.
| [in,out] | storage | Pre-aligned storage buffer for the queue. |
|
inline |
Destroys the queue and any remaining elements.
T::~T() is ISR/NMI-safe.
|
inlinenoexcept |
Begins a scoped consumer transaction (ReadTransaction) that caches the number of available elements with a single std::memory_order_acquire load of tail_ and commits all consumed elements with a single std::memory_order_release store to head_ on Commit() or scope exit.
ReadTransaction bound to this queue.
|
inlinenoexcept |
Begins a scoped producer transaction (WriteTransaction) that caches the current queue capacity with a single std::memory_order_acquire load of head_ and commits all staged elements with a single std::memory_order_release store to tail_ on Commit() or scope exit.
WriteTransaction bound to this queue.
|
inlineconstexprnoexcept |
Returns the maximum number of elements the queue can hold.
|
inlinenoexcept |
Destroys all elements in the queue and resets its indices.
clear().T::~T() is ISR/NMI-safe.
|
inline |
Constructs an element in-place at the back of the queue.
!full()). Crashes via PW_ASSERT if the queue is full.T's constructor is ISR/NMI-safe.| Args | Constructor argument types for T. |
| [in] | args | Arguments forwarded to T's constructor. |
|
inlinenoexcept |
Checks whether the queue has no elements.
Because head_ is only advanced by the consumer and tail_ is only advanced by the producer, if empty() returns false to the consumer, at least one element is guaranteed to remain available to consume.
true if the queue is empty, or false otherwise.
|
inline |
Returns a mutable reference to the front element in the queue.
!empty()). Crashes via PW_ASSERT if empty.!empty().
|
inline |
Returns a const reference to the front element in the queue.
!empty()). Crashes via PW_ASSERT if empty.!empty().
|
inlinenoexcept |
Checks whether the queue is at full capacity.
Because tail_ is only advanced by the producer and head_ is only advanced by the consumer, if full() returns false to the producer, at least one slot is guaranteed to remain available for the producer.
true if the queue is at capacity, or false otherwise.
|
inlineconstexprnoexcept |
Returns the maximum number of elements the queue can hold.
|
inline |
Pushes as many elements from items as fit in the queue by move, updating tail_ with a single std::memory_order_release store.
Only the first count elements of items (where count is the returned value) are moved from; any remaining elements are left unmodified.
| [in,out] | items | Span of elements to move into the queue. |
0 <= count <= items.size()).
|
inline |
Removes and destroys the front element from the queue.
!empty()). Crashes via PW_ASSERT if empty.!empty() and T::~T() is ISR/NMI-safe.
|
inlinenoexcept |
Removes and destroys up to count elements from the front of the queue, updating head_ with a single std::memory_order_release store.
| [in] | count | Maximum number of elements to remove. |
0 <= removed <= count).
|
inline |
Pops up to dest.size() elements from the front of the queue and assigns them into dest (by move if move-assignable, otherwise by copy), updating head_ with a single std::memory_order_release store.
| [out] | dest | Destination span to receive the popped elements. |
dest (0 <= count <= dest.size()).
|
inline |
Pushes a copy of value to the back of the queue.
!full()). Crashes via PW_ASSERT if the queue is full.T's copy constructor is ISR/NMI-safe.| [in] | value | The value to copy into the queue. |
|
inline |
Pushes value to the back of the queue by move.
!full()). Crashes via PW_ASSERT if the queue is full.T's move constructor is ISR/NMI-safe.| [in] | value | The value to move into the queue. |
|
inline |
Pushes as many elements from items as fit in the queue by copy, updating tail_ with a single std::memory_order_release store.
| [in] | items | Span of elements to copy into the queue. |
0 <= count <= items.size()).
|
inlinenoexcept |
Returns the number of additional elements that can be pushed without exceeding capacity.
|
inlinenoexcept |
Returns the number of elements currently in the queue.
In an SPSC queue, at least one of head_ (consumer) or tail_ (producer) is invariant when called from either endpoint, so loading both with acquire ordering yields a consistent snapshot without a retry loop. For the consumer, the returned count is a conservative lower bound on available items; for the producer, it is a conservative upper bound on queued items.
|
inline |
Attempts to construct an element in-place at the back of the queue.
T's constructor is ISR/NMI-safe.| Args | Constructor argument types for T. |
| [in] | args | Arguments forwarded to T's constructor. |
true if the element was constructed and pushed, or false if the queue is full.
|
inline |
Attempts to push all elements of items into the queue by move in a single all-or-nothing batch.
If fewer than items.size() slots are available, no elements are moved from items and false is returned.
| [in,out] | items | Span of elements to move into the queue. |
true if all elements in items were pushed, or false if remaining_capacity() < items.size().
|
inlinenoexcept |
Returns a const pointer to the front element in the queue if available, without removing it.
nullptr if the queue is empty.
|
inlinenoexcept |
Returns a pointer to the front element in the queue if available, without removing it.
Unlike calling !empty() followed by front(), try_peek() performs a single acquire load of tail_. The returned pointer remains valid until the element is removed via pop() or try_pop(), or the queue is cleared or destroyed.
nullptr if the queue is empty.
|
inline |
Removes and returns the front element from the queue if available.
T's move/copy constructor and destructor are ISR/NMI-safe.std::nullopt if the queue is empty.
|
inline |
Removes the front element from the queue and assigns it to out if available.
T's move/copy assignment operator and destructor are ISR/NMI-safe.| [out] | out | Destination object to receive the popped element. Left unmodified if false is returned. |
true if an element was popped into out, or false if the queue is empty.
|
inline |
Attempts to push a copy of value to the back of the queue.
T's copy constructor is ISR/NMI-safe.| [in] | value | The value to copy into the queue. |
true if the element was pushed, or false if the queue is full.
|
inline |
Attempts to push value to the back of the queue by move.
T's move constructor is ISR/NMI-safe.| [in] | value | The value to move into the queue. If false is returned because the queue is full, value is not moved from. |
true if the element was pushed, or false if the queue is full.
|
inline |
Attempts to push all elements of items into the queue by copy in a single all-or-nothing batch.
If fewer than items.size() slots are available, no elements are pushed and false is returned.
| [in] | items | Span of elements to copy into the queue. |
true if all elements in items were pushed, or false if remaining_capacity() < items.size().
|
staticconstexpr |
Maximum number of elements supported by SizeType. Virtual head and tail indices range over [0, 2 * capacity) to distinguish empty and full states without wasting a storage slot.