Skip to main content
Pigweed's logo Pigweed
code_xml
  1. Home
  2. Reference
  3. C/C++
  4. Data structures & utilities
  5. pw_containers
  6. Queues
  7. pw::LockFreeSpscQueue< T, SizeType > Class Template Reference
pw::LockFreeSpscQueue< T, SizeType > Class Template Reference

Overview

template<typename T, typename SizeType = size_t>
class pw::LockFreeSpscQueue< T, SizeType >

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.

Note
On Armv6-M targets (Cortex-M0 and Cortex-M0+), aligned 8-, 16-, and 32-bit loads and stores are single-copy atomic in hardware. Under GCC (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).
Template Parameters
TThe type of elements stored in the queue.
SizeTypeUnsigned 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.

thread safemaybe isr safemaybe nmi safemaybe

Inheritance diagram for pw::LockFreeSpscQueue< T, SizeType >:
pw::FixedLockFreeSpscQueue< T, kInlineCapacity, SizeType >

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
 

Constructor & Destructor Documentation

◆ LockFreeSpscQueue() [1/2]

template<typename T , typename SizeType = size_t>
constexpr pw::LockFreeSpscQueue< T, SizeType >::LockFreeSpscQueue ( span< std::byte >  unaligned_buffer)
inlineexplicitconstexprnoexcept

Constructs an empty LockFreeSpscQueue using the provided buffer for storage.

Precondition
The aligned capacity (unaligned_buffer.size() / sizeof(value_type)) must not exceed kMaxCapacity.
Parameters
[in]unaligned_bufferStorage 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.

thread safeyes isr safeyes nmi safemaybe

◆ LockFreeSpscQueue() [2/2]

template<typename T , typename SizeType = size_t>
template<size_t kAlignment, size_t kSizeBytes>
constexpr pw::LockFreeSpscQueue< T, SizeType >::LockFreeSpscQueue ( containers::Storage< kAlignment, kSizeBytes > &  storage)
inlineexplicitconstexprnoexcept

Constructs an empty LockFreeSpscQueue using a pw::containers::Storage buffer. This constructor avoids runtime alignment checks.

Parameters
[in,out]storagePre-aligned storage buffer for the queue.

thread safeyes isr safeyes nmi safeyes

◆ ~LockFreeSpscQueue()

template<typename T , typename SizeType = size_t>
pw::LockFreeSpscQueue< T, SizeType >::~LockFreeSpscQueue ( )
inline

Destroys the queue and any remaining elements.

Precondition
No producer or consumer operations may be running concurrently during destruction.
Note
ISR-safe and NMI-safe if T::~T() is ISR/NMI-safe.

thread safeno isr safemaybe nmi safemaybe

Member Function Documentation

◆ BeginRead()

template<typename T , typename SizeType = size_t>
ReadTransaction pw::LockFreeSpscQueue< T, SizeType >::BeginRead ( )
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.

Note
Safe to call concurrently with producer operations from the single consumer context.
Returns
A ReadTransaction bound to this queue.

thread safemaybe isr safeyes nmi safemaybe

◆ BeginWrite()

template<typename T , typename SizeType = size_t>
WriteTransaction pw::LockFreeSpscQueue< T, SizeType >::BeginWrite ( )
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.

Note
Safe to call concurrently with consumer operations from the single producer context.
Returns
A WriteTransaction bound to this queue.

thread safemaybe isr safeyes nmi safemaybe

◆ capacity()

template<typename T , typename SizeType = size_t>
constexpr size_type pw::LockFreeSpscQueue< T, SizeType >::capacity ( ) const
inlineconstexprnoexcept

Returns the maximum number of elements the queue can hold.

Returns
The capacity of the queue in elements.

thread safeyes isr safeyes nmi safeyes

◆ clear()

template<typename T , typename SizeType = size_t>
void pw::LockFreeSpscQueue< T, SizeType >::clear ( )
inlinenoexcept

Destroys all elements in the queue and resets its indices.

Precondition
Requires exclusive access; no producer or consumer operations may run concurrently with clear().
Note
ISR-safe and NMI-safe if T::~T() is ISR/NMI-safe.

thread safeno isr safemaybe nmi safemaybe

◆ emplace()

template<typename T , typename SizeType = size_t>
template<typename... Args>
void pw::LockFreeSpscQueue< T, SizeType >::emplace ( Args &&...  args)
inline

Constructs an element in-place at the back of the queue.

Precondition
The queue must not be full (!full()). Crashes via PW_ASSERT if the queue is full.
Note
Safe to call concurrently with consumer operations from the single producer context. ISR-safe and NMI-safe if the queue is not full and T's constructor is ISR/NMI-safe.
Template Parameters
ArgsConstructor argument types for T.
Parameters
[in]argsArguments forwarded to T's constructor.

thread safemaybe isr safemaybe nmi safemaybe

◆ empty()

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::empty ( ) const
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.

Note
Safe to call concurrently from either the producer or the consumer context.
Returns
true if the queue is empty, or false otherwise.

thread safemaybe isr safeyes nmi safemaybe

◆ front() [1/2]

template<typename T , typename SizeType = size_t>
reference pw::LockFreeSpscQueue< T, SizeType >::front ( )
inline

Returns a mutable reference to the front element in the queue.

Precondition
The queue must not be empty (!empty()). Crashes via PW_ASSERT if empty.
Note
Safe to call concurrently with producer operations from the single consumer context. NMI-safe if !empty().
Returns
A reference to the oldest element in the queue.

thread safemaybe isr safeyes nmi safemaybe

◆ front() [2/2]

template<typename T , typename SizeType = size_t>
const_reference pw::LockFreeSpscQueue< T, SizeType >::front ( ) const
inline

Returns a const reference to the front element in the queue.

Precondition
The queue must not be empty (!empty()). Crashes via PW_ASSERT if empty.
Note
Safe to call concurrently with producer operations from the single consumer context. NMI-safe if !empty().
Returns
A const reference to the oldest element in the queue.

thread safemaybe isr safeyes nmi safemaybe

◆ full()

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::full ( ) const
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.

Note
Safe to call concurrently from either the producer or the consumer context.
Returns
true if the queue is at capacity, or false otherwise.

thread safemaybe isr safeyes nmi safemaybe

◆ max_size()

template<typename T , typename SizeType = size_t>
constexpr size_type pw::LockFreeSpscQueue< T, SizeType >::max_size ( ) const
inlineconstexprnoexcept

Returns the maximum number of elements the queue can hold.

Returns
The maximum capacity of the queue in elements.

thread safeyes isr safeyes nmi safeyes

◆ move_push_some()

template<typename T , typename SizeType = size_t>
size_type pw::LockFreeSpscQueue< T, SizeType >::move_push_some ( span< value_type >  items)
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.

Note
Safe to call concurrently with consumer operations from the single producer context.
Parameters
[in,out]itemsSpan of elements to move into the queue.
Returns
The number of elements pushed (0 <= count <= items.size()).

thread safemaybe isr safemaybe nmi safemaybe

◆ pop()

template<typename T , typename SizeType = size_t>
void pw::LockFreeSpscQueue< T, SizeType >::pop ( )
inline

Removes and destroys the front element from the queue.

Precondition
The queue must not be empty (!empty()). Crashes via PW_ASSERT if empty.
Note
Safe to call concurrently with producer operations from the single consumer context. ISR-safe and NMI-safe if !empty() and T::~T() is ISR/NMI-safe.

thread safemaybe isr safemaybe nmi safemaybe

◆ pop_n()

template<typename T , typename SizeType = size_t>
size_type pw::LockFreeSpscQueue< T, SizeType >::pop_n ( size_type  count)
inlinenoexcept

Removes and destroys up to count elements from the front of the queue, updating head_ with a single std::memory_order_release store.

Note
Safe to call concurrently with producer operations from the single consumer context.
Parameters
[in]countMaximum number of elements to remove.
Returns
The number of elements actually removed (0 <= removed <= count).

thread safemaybe isr safemaybe nmi safemaybe

◆ pop_some()

template<typename T , typename SizeType = size_t>
size_type pw::LockFreeSpscQueue< T, SizeType >::pop_some ( span< value_type >  dest)
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.

Note
Safe to call concurrently with producer operations from the single consumer context.
Parameters
[out]destDestination span to receive the popped elements.
Returns
The number of elements popped into dest (0 <= count <= dest.size()).

thread safemaybe isr safemaybe nmi safemaybe

◆ push() [1/2]

template<typename T , typename SizeType = size_t>
void pw::LockFreeSpscQueue< T, SizeType >::push ( const value_type &  value)
inline

Pushes a copy of value to the back of the queue.

Precondition
The queue must not be full (!full()). Crashes via PW_ASSERT if the queue is full.
Note
Safe to call concurrently with consumer operations from the single producer context. ISR-safe and NMI-safe if the queue is not full and T's copy constructor is ISR/NMI-safe.
Parameters
[in]valueThe value to copy into the queue.

thread safemaybe isr safemaybe nmi safemaybe

◆ push() [2/2]

template<typename T , typename SizeType = size_t>
void pw::LockFreeSpscQueue< T, SizeType >::push ( value_type &&  value)
inline

Pushes value to the back of the queue by move.

Precondition
The queue must not be full (!full()). Crashes via PW_ASSERT if the queue is full.
Note
Safe to call concurrently with consumer operations from the single producer context. ISR-safe and NMI-safe if the queue is not full and T's move constructor is ISR/NMI-safe.
Parameters
[in]valueThe value to move into the queue.

thread safemaybe isr safemaybe nmi safemaybe

◆ push_some()

template<typename T , typename SizeType = size_t>
size_type pw::LockFreeSpscQueue< T, SizeType >::push_some ( span< const value_type >  items)
inline

Pushes as many elements from items as fit in the queue by copy, updating tail_ with a single std::memory_order_release store.

Note
Safe to call concurrently with consumer operations from the single producer context.
Parameters
[in]itemsSpan of elements to copy into the queue.
Returns
The number of elements pushed (0 <= count <= items.size()).

thread safemaybe isr safemaybe nmi safemaybe

◆ remaining_capacity()

template<typename T , typename SizeType = size_t>
size_type pw::LockFreeSpscQueue< T, SizeType >::remaining_capacity ( ) const
inlinenoexcept

Returns the number of additional elements that can be pushed without exceeding capacity.

Note
Safe to call concurrently from either the producer or the consumer context.
Returns
The number of unoccupied slots in the queue.

thread safemaybe isr safeyes nmi safemaybe

◆ size()

template<typename T , typename SizeType = size_t>
size_type pw::LockFreeSpscQueue< T, SizeType >::size ( ) const
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.

Note
Safe to call concurrently from either the producer or the consumer context.
Returns
The number of elements in the queue.

thread safemaybe isr safeyes nmi safemaybe

◆ try_emplace()

template<typename T , typename SizeType = size_t>
template<typename... Args>
bool pw::LockFreeSpscQueue< T, SizeType >::try_emplace ( Args &&...  args)
inline

Attempts to construct an element in-place at the back of the queue.

Note
Safe to call concurrently with consumer operations from the single producer context. ISR-safe and NMI-safe if T's constructor is ISR/NMI-safe.
Template Parameters
ArgsConstructor argument types for T.
Parameters
[in]argsArguments forwarded to T's constructor.
Returns
true if the element was constructed and pushed, or false if the queue is full.

thread safemaybe isr safemaybe nmi safemaybe

◆ try_move_push_all()

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::try_move_push_all ( span< value_type >  items)
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.

Note
Safe to call concurrently with consumer operations from the single producer context.
Parameters
[in,out]itemsSpan of elements to move into the queue.
Returns
true if all elements in items were pushed, or false if remaining_capacity() < items.size().

thread safemaybe isr safemaybe nmi safemaybe

◆ try_peek() [1/2]

template<typename T , typename SizeType = size_t>
const_pointer pw::LockFreeSpscQueue< T, SizeType >::try_peek ( ) const
inlinenoexcept

Returns a const pointer to the front element in the queue if available, without removing it.

Note
Safe to call concurrently with producer operations from the single consumer context.
Returns
A const pointer to the oldest element in the queue, or nullptr if the queue is empty.

thread safemaybe isr safeyes nmi safemaybe

◆ try_peek() [2/2]

template<typename T , typename SizeType = size_t>
pointer pw::LockFreeSpscQueue< T, SizeType >::try_peek ( )
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.

Note
Safe to call concurrently with producer operations from the single consumer context.
Returns
A pointer to the oldest element in the queue, or nullptr if the queue is empty.

thread safemaybe isr safeyes nmi safemaybe

◆ try_pop() [1/2]

template<typename T , typename SizeType = size_t>
std::optional< value_type > pw::LockFreeSpscQueue< T, SizeType >::try_pop ( )
inline

Removes and returns the front element from the queue if available.

Note
Safe to call concurrently with producer operations from the single consumer context. ISR-safe and NMI-safe if T's move/copy constructor and destructor are ISR/NMI-safe.
Returns
The front element moved out of the queue, or std::nullopt if the queue is empty.

thread safemaybe isr safemaybe nmi safemaybe

◆ try_pop() [2/2]

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::try_pop ( value_type &  out)
inline

Removes the front element from the queue and assigns it to out if available.

Note
Safe to call concurrently with producer operations from the single consumer context. ISR-safe and NMI-safe if T's move/copy assignment operator and destructor are ISR/NMI-safe.
Parameters
[out]outDestination object to receive the popped element. Left unmodified if false is returned.
Returns
true if an element was popped into out, or false if the queue is empty.

thread safemaybe isr safemaybe nmi safemaybe

◆ try_push() [1/2]

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::try_push ( const value_type &  value)
inline

Attempts to push a copy of value to the back of the queue.

Note
Safe to call concurrently with consumer operations from the single producer context. ISR-safe and NMI-safe if T's copy constructor is ISR/NMI-safe.
Parameters
[in]valueThe value to copy into the queue.
Returns
true if the element was pushed, or false if the queue is full.

thread safemaybe isr safemaybe nmi safemaybe

◆ try_push() [2/2]

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::try_push ( value_type &&  value)
inline

Attempts to push value to the back of the queue by move.

Note
Safe to call concurrently with consumer operations from the single producer context. ISR-safe and NMI-safe if T's move constructor is ISR/NMI-safe.
Parameters
[in]valueThe value to move into the queue. If false is returned because the queue is full, value is not moved from.
Returns
true if the element was pushed, or false if the queue is full.

thread safemaybe isr safemaybe nmi safemaybe

◆ try_push_all()

template<typename T , typename SizeType = size_t>
bool pw::LockFreeSpscQueue< T, SizeType >::try_push_all ( span< const value_type >  items)
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.

Note
Safe to call concurrently with consumer operations from the single producer context.
Parameters
[in]itemsSpan of elements to copy into the queue.
Returns
true if all elements in items were pushed, or false if remaining_capacity() < items.size().

thread safemaybe isr safemaybe nmi safemaybe

Member Data Documentation

◆ kMaxCapacity

template<typename T , typename SizeType = size_t>
constexpr size_type pw::LockFreeSpscQueue< T, SizeType >::kMaxCapacity
staticconstexpr
Initial value:
=
std::numeric_limits<size_type>::max() / 2

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.


The documentation for this class was generated from the following file: