Queues#

pw_containers: Generic collections of objects for embedded devices

A queue is an ordered collection designed to add items at one end and remove them from the other. This allows “first in, first out”, or FIFO, behavior. Pigweed provides both single and double-ended queues that are backed by fixed storage.

pw::InlineDeque#

template<typename T, size_t kCapacity = containers::internal::kGenericSized>
using pw::InlineDeque = BasicInlineDeque<T, uint16_t, kCapacity>#

The InlineDeque class is similar to the STL’s double ended queue (std::deque), except it is backed by a fixed-size buffer. InlineDeque’s must be declared with an explicit maximum size (e.g. InlineDeque<int, 10>>) but deques can be used and referred to without the max size template parameter (e.g. InlineDeque<int>).

To allow referring to a pw::InlineDeque without an explicit maximum size, all InlineDeque classes inherit from the BasicInlineDequeStorage class, which in turn inherits from InlineDeque<T>, which stores the maximum size in a variable. This allows InlineDeques to be used without having to know their maximum size at compile time. It also keeps code size small since function implementations are shared for all maximum sizes.

API reference#

template<typename ValueType, typename SizeType, size_t kCapacity = containers::internal::kGenericSized>
class BasicInlineDeque : public pw::BasicInlineDequeStorage<ValueType, SizeType, containers::internal::kGenericSized, std::is_trivially_destructible_v<ValueType>>#

Public Functions

inline BasicInlineDeque() noexcept#

Constructs with zero elements.

inline BasicInlineDeque(size_type count, const_reference value)#

Constructs with count copies of value.

inline explicit BasicInlineDeque(size_type count)#

Constructs with count default-initialized elements.

template<typename InputIterator, typename = containers::internal::EnableIfInputIterator<InputIterator>>
inline BasicInlineDeque(
InputIterator start,
InputIterator finish,
)#

Copy constructs from an iterator.

inline BasicInlineDeque(const BasicInlineDeque &other)#

Copy constructs for matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineDeque(const BasicInlineDeque<ValueType, SizeType, kOtherCapacity> &other)#

Copy constructs for mismatched capacity.

Note that this will result in a crash if kOtherCapacity < size().

inline BasicInlineDeque(BasicInlineDeque &&other) noexcept#

Move constructs for matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineDeque(
BasicInlineDeque<ValueType, SizeType, kOtherCapacity> &&other,
) noexcept#

Move constructs for mismatched capacity.

inline BasicInlineDeque(const std::initializer_list<value_type> &list)#

Copy constructs from an initializer list.

template<typename T, typename = containers::internal::EnableIfIterable<T>>
inline BasicInlineDeque(const T &other)#

Copy constructor for arbitrary iterables.

inline BasicInlineDeque &operator=(const std::initializer_list<value_type> &list)#

Copy assigns from list.

inline BasicInlineDeque &operator=(const BasicInlineDeque &other)#

Copy assigns for matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineDeque &operator=(
const BasicInlineDeque<ValueType, SizeType, kOtherCapacity> &other,
)#

Copy assigns for mismatched capacity.

Note that this will result in a crash if kOtherCapacity < size().

inline BasicInlineDeque &operator=(BasicInlineDeque &&other) noexcept#

Move assigns for matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineDeque &operator=(
BasicInlineDeque<ValueType, SizeType, kOtherCapacity> &&other,
) noexcept#

Move assigns for mismatched capacity.

pw::InlineQueue#

template<typename T, size_t kCapacity = containers::internal::kGenericSized>
using pw::InlineQueue = BasicInlineQueue<T, uint16_t, kCapacity>#

The InlineQueue class is similar to std::queue<T, std::deque>, except it is backed by a fixed-size buffer. InlineQueue’s must be declared with an explicit maximum size (e.g. InlineQueue<int, 10>>) but deques can be used and referred to without the max size template parameter (e.g. InlineQueue<int>).

pw::InlineQueue is wrapper around pw::InlineDeque with a simplified API and push_overwrite() & emplace_overwrite() helpers.

API reference#

template<typename ValueType, typename SizeType, size_t kCapacity = containers::internal::kGenericSized>
class BasicInlineQueue#

Public Functions

inline BasicInlineQueue(const BasicInlineQueue &other)#

Copy constructs for matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineQueue(const BasicInlineQueue<ValueType, SizeType, kOtherCapacity> &other)#

Copy constructs for mismatched capacity.

Note that this will result in a crash if kOtherCapacity < size().

inline BasicInlineQueue(BasicInlineQueue &&other)#

Move constructs for matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineQueue(BasicInlineQueue<ValueType, SizeType, kOtherCapacity> &&other)#

Move constructs for mismatched capacity.

Note that this will result in a crash if kOtherCapacity < size().

inline BasicInlineQueue &operator=(const BasicInlineQueue &other)#

Copy assigns from matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineQueue &operator=(
const BasicInlineQueue<ValueType, SizeType, kOtherCapacity> &other,
)#

Copy assigns from mismatched capacity.

Note that this will result in a crash if kOtherCapacity < size().

inline BasicInlineQueue &operator=(BasicInlineQueue &&other)#

Move assigns from matching capacity.

template<size_t kOtherCapacity>
inline BasicInlineQueue &operator=(
BasicInlineQueue<ValueType, SizeType, kOtherCapacity> &&other,
)#

Move assigns from mismatched capacity.

Note that this will result in a crash if kOtherCapacity < size().

pw::InlineVarLenEntryQueue#

A InlineVarLenEntryQueue is a queue of inline variable-length binary entries. It is implemented as a ring (circular) buffer and supports operations to append entries and overwrite if necessary. Entries may be zero bytes up to the maximum size supported by the queue.

The InlineVarLenEntryQueue has a few interesting properties.

  • Data and metadata are stored inline in a contiguous block of uint32_t-aligned memory.

  • The data structure is trivially copyable.

  • All state changes are accomplished with a single update to a uint32_t. The memory is always in a valid state and may be parsed offline.

This data structure is a much simpler version of pw::ring_buffer::PrefixedEntryRingBuffer . Prefer this sized-entry ring buffer to PrefixedEntryRingBuffer when:

  • A simple ring buffer of variable-length entries is needed. Advanced features like multiple readers and a user-defined preamble are not required.

  • A consistent, parsable, in-memory representation is required (e.g. to decode the buffer from a block of memory).

  • C support is required.

InlineVarLenEntryQueue is implemented in C and provides complete C and C++ APIs. The InlineVarLenEntryQueue C++ class is structured similarly to pw::InlineQueue and pw::Vector.

Example#

Queues are declared with their max size (InlineVarLenEntryQueue<kMaxSize>) but may be used without specifying the size (InlineVarLenEntryQueue<>&).

// Declare a queue with capacity sufficient for one 10-byte entry or
// multiple smaller entries.
pw::InlineVarLenEntryQueue<10> queue;

// Push an entry, asserting if the entry does not fit.
queue.push(queue, data)

// Use push_overwrite() to push entries, overwriting older entries
// as needed.
queue.push_overwrite(queue, more_data)

// Remove an entry.
queue.pop();

Alternately, a InlineVarLenEntryQueue may be initialized in an existing uint32_t array.

// Initialize a InlineVarLenEntryQueue.
uint32_t buffer[32];
auto& queue = pw::InlineVarLenEntryQueue<>::Init(buffer);

// Largest supported entry is 114 B (13 B overhead + 1 B prefix)
assert(queue.max_size_bytes() == 114u);

// Write data
queue.push_overwrite(data);

A InlineVarLenEntryQueue may be declared and initialized in C with the PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE macro.

// Declare a queue with capacity sufficient for one 10-byte entry or
// multiple smaller entries.
PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 10);

// Push an entry, asserting if the entry does not fit.
pw_InlineVarLenEntryQueue_Push(queue, "12345", 5);

// Use push_overwrite() to push entries, overwriting older entries
// as needed.
pw_InlineVarLenEntryQueue_PushOverwrite(queue, "abcdefg", 7);

// Remove an entry.
pw_InlineVarLenEntryQueue_Pop(queue);

Alternately, a InlineVarLenEntryQueue may be initialized in an existing uint32_t array.

// Initialize a InlineVarLenEntryQueue.
uint32_t buffer[32];
pw_InlineVarLenEntryQueue_Init(buffer, 32);

// Largest supported entry is 114 B (13 B overhead + 1 B prefix)
assert(pw_InlineVarLenEntryQueue_MaxSizeBytes(buffer) == 114u);

// Write some data
pw_InlineVarLenEntryQueue_PushOverwrite(buffer, "123", 3);

API reference#

C++#

template<size_t kMaxSizeBytes = containers::internal::kGenericSized>
using InlineVarLenEntryQueue = BasicInlineVarLenEntryQueue<std::byte, kMaxSizeBytes>#

Variable-length entry queue that uses std::byte for the byte type.

template<typename T>
class BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>#

Variable-length entry queue class template for any byte type (e.g. std::byte or uint8_t).

BasicInlineVarLenEntryQueue instances are declared with their capacity / max single entry size (BasicInlineVarLenEntryQueue<char, 64>), but may be referred to without the size (BasicInlineVarLenEntryQueue<char>&).

Public Functions

inline Entry front() const#

Returns the first entry in the queue.

Pre:

The queue must NOT empty (empty() is false).

inline const_iterator begin() const#

Returns an iterator to the start of the InlineVarLenEntryQueue.

inline const_iterator end() const#

Returns an iterator that points past the end of the queue.

inline bool empty() const#

Returns true if the InlineVarLenEntryQueue is empty, false if it has at least one entry.

inline size_type size() const#

Returns the number of variable-length entries in the queue. This is O(n) in the number of entries in the queue.

inline size_type max_size() const#

Returns the maximum number of entries in the queue. This is only attainable if all entries are empty.

inline size_type size_bytes() const#

Returns the combined size in bytes of all entries in the queue, excluding metadata. This is O(n) in the number of entries in the queue.

inline size_type max_size_bytes() const#

Returns the the maximum number of bytes that can be stored in the queue. This is largest possible value of size_bytes(), and the size of the largest single entry that can be stored in this queue. Attempting to store a larger entry is invalid and results in a crash.

inline span<const T> raw_storage() const#

Underlying storage of the variable-length entry queue. May be used to memcpy the queue.

inline void clear()#

Empties the queue.

inline void push(span<const T> value)#

Appends an entry to the end of the queue.

Pre:

The entry MUST NOT be larger than max_size_bytes().

Pre:

There must be sufficient space in the queue for this entry.

inline bool try_push(span<const T> value)#

Appends an entry to the end of the queue, but only if there is sufficient space for it.

Returns:

true if the data was added to the queue; false if it did not fit

Pre:

The entry MUST NOT be larger than max_size_bytes().

inline void push_overwrite(span<const T> value)#

Appends an entry to the end of the queue, removing entries with Pop as necessary to make room. Calling this function drops old entries to make room for new; call try_push() to drop new entries instead.

Pre:

The entry MUST NOT be larger than max_size_bytes().

inline void pop()#

Removes the first entry from queue.

Pre:

The queue MUST have at least one entry.

Public Static Functions

template<size_t kArraySize>
static inline BasicInlineVarLenEntryQueue &Init(uint32_t (&array)[kArraySize])#

Initializes a InlineVarLenEntryQueue in place in a uint32_t array. The array MUST be larger than PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements.

static inline BasicInlineVarLenEntryQueue &Init(uint32_t array[], size_t array_size_uint32)#

Initializes a InlineVarLenEntryQueue in place in a uint32_t array. The array MUST be larger than PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements.

class Entry#

Refers to an entry in-place in the queue. Entries may be discontiguous.

Public Functions

inline std::pair<span<const value_type>, span<const value_type>> contiguous_data() const#

Entries may be stored in up to two segments, so this returns spans refering to both portions of the entry. If the entry is contiguous, the second span is empty.

inline size_type copy(T *dest, size_type count) const#

Copies the contents of the entry to the provided buffer. The entry may be split into two regions; this serializes it into one buffer.

Copying with copy() is likely more efficient than an iterator-based copy with std::copy(), since copy() uses one or two memcpy calls instead of copying byte-by-byte.

Parameters:

  • entry – The entry whose contents to copy

  • dest – The buffer into which to copy the serialized entry

  • count – Copy up to this many bytes; must not be larger than the dest buffer, but may be larger than the entry

class iterator#

Iterator for the bytes in an Entry. Entries may be discontiguous, so a pointer cannot serve as an iterator.

class iterator#

Iterator object for a InlineVarLenEntryQueue.

Iterators are invalidated by any operations that change the container or its underlying data (push/pop/init).

C#

typedef uint32_t *pw_InlineVarLenEntryQueue_Handle#

Handle that refers to a InlineVarLenEntryQueue. In memory, the queue is a uint32_t array.

typedef const uint32_t *pw_InlineVarLenEntryQueue_ConstHandle#
static inline void pw_InlineVarLenEntryQueue_Init(uint32_t array[], size_t array_size_uint32)#

Initializes a InlineVarLenEntryQueue in place in a uint32_t array. The array MUST be larger than PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements.

static inline void pw_InlineVarLenEntryQueue_Clear(pw_InlineVarLenEntryQueue_Handle queue)#

Empties the queue.

void pw_InlineVarLenEntryQueue_Push(pw_InlineVarLenEntryQueue_Handle queue, const void *data, uint32_t data_size_bytes)#

Appends an entry to the end of the queue.

Pre:

The entry MUST NOT be larger than max_size_bytes().

Pre:

There must be sufficient space in the queue for this entry.

bool pw_InlineVarLenEntryQueue_TryPush(pw_InlineVarLenEntryQueue_Handle queue, const void *data, const uint32_t data_size_bytes)#

Appends an entry to the end of the queue, but only if there is sufficient space for it.

Returns:

true if the data was added to the queue; false if it did not fit

Pre:

The entry MUST NOT be larger than max_size_bytes().

void pw_InlineVarLenEntryQueue_PushOverwrite(pw_InlineVarLenEntryQueue_Handle queue, const void *data, uint32_t data_size_bytes)#

Appends an entry to the end of the queue, removing entries with Pop as necessary to make room. Calling this function drops old entries to make room for new; call try_push() to drop new entries instead.

Pre:

The entry MUST NOT be larger than max_size_bytes().

void pw_InlineVarLenEntryQueue_Pop(pw_InlineVarLenEntryQueue_Handle queue)#

Removes the first entry from queue.

Pre:

The queue MUST have at least one entry.

static inline pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_Begin(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns an iterator to the start of the InlineVarLenEntryQueue.

static inline pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_End(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns an iterator that points past the end of the queue.

void pw_InlineVarLenEntryQueue_Iterator_Advance(pw_InlineVarLenEntryQueue_Iterator *iterator)#

Advances an iterator to point to the next entry in the queue. It is invalid to call Advance on an iterator equal to the End iterator.

static inline bool pw_InlineVarLenEntryQueue_Iterator_Equal(
const pw_InlineVarLenEntryQueue_Iterator *lhs,
const pw_InlineVarLenEntryQueue_Iterator *rhs,
)#

Compares two iterators for equality.

pw_InlineVarLenEntryQueue_Entry pw_InlineVarLenEntryQueue_GetEntry(const pw_InlineVarLenEntryQueue_Iterator *iterator)#

Dereferences an iterator, loading the entry it points to.

uint32_t pw_InlineVarLenEntryQueue_Entry_Copy(const pw_InlineVarLenEntryQueue_Entry *entry, void *dest, uint32_t count)#

Copies the contents of the entry to the provided buffer. The entry may be split into two regions; this serializes it into one buffer.

Parameters:

  • entry – The entry whose contents to copy

  • dest – The buffer into which to copy the serialized entry

  • count – Copy up to this many bytes; must not be larger than the dest buffer, but may be larger than the entry

static inline uint8_t pw_InlineVarLenEntryQueue_Entry_At(const pw_InlineVarLenEntryQueue_Entry *entry, size_t index)#

Returns the byte at the specified index in the entry. Asserts if index is out-of-bounds.

uint32_t pw_InlineVarLenEntryQueue_Size(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns the number of variable-length entries in the queue. This is O(n) in the number of entries in the queue.

static inline uint32_t pw_InlineVarLenEntryQueue_MaxSize(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns the maximum number of entries in the queue. This is only attainable if all entries are empty.

uint32_t pw_InlineVarLenEntryQueue_SizeBytes(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns the combined size in bytes of all entries in the queue, excluding metadata. This is O(n) in the number of entries in the queue.

static inline uint32_t pw_InlineVarLenEntryQueue_MaxSizeBytes(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns the the maximum number of bytes that can be stored in the queue. This is largest possible value of size_bytes(), and the size of the largest single entry that can be stored in this queue. Attempting to store a larger entry is invalid and results in a crash.

static inline uint32_t pw_InlineVarLenEntryQueue_RawStorageSizeBytes(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns the size of the raw underlying InlineVarLenEntryQueue storage. This size may be used to copy a InlineVarLenEntryQueue into another 32-bit aligned memory location.

static inline bool pw_InlineVarLenEntryQueue_Empty(pw_InlineVarLenEntryQueue_ConstHandle queue)#

Returns true if the InlineVarLenEntryQueue is empty, false if it has at least one entry.

PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(variable, max_size_bytes)#

Declares and initializes a InlineVarLenEntryQueue that can hold up to max_size_bytes bytes. max_size_bytes is the largest supported size for a single entry; attempting to store larger entries is invalid and will fail an assertion.

Parameters:

  • variable – variable name for the queue

  • max_size_bytes – the capacity of the queue

PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32#

The size of the InlineVarLenEntryQueue header, in uint32_t elements. This header stores the buffer length and head and tail offsets.

The underlying uint32_t array of a InlineVarLenEntryQueue must be larger than this size.

struct pw_InlineVarLenEntryQueue_Iterator#

Iterator object for a InlineVarLenEntryQueue. Iterators are checked for equality with pw_InlineVarLenEntryQueue_Iterator_Equal() .

Iterators are invalidated by any operations that change the container or its underlying data (push/pop/init).

struct pw_InlineVarLenEntryQueue_Entry#

An entry in the queue. Entries may be stored in up to two segments, so this struct includes pointers to both portions of the entry.

Python#

Decodes the in-memory representation of a sized-entry ring buffer.

pw_containers.inline_var_len_entry_queue.parse(queue: bytes) → Iterable[bytes]#

Decodes the in-memory representation of a variable-length entry queue.

Parameters:

queue – The bytes representation of a variable-length entry queue.

Yields:

Each entry in the buffer as bytes.

Queue vs. deque#

This module provides pw::InlineVarLenEntryQueue, but no corresponding InlineVarLenEntryDeque class. Following the C++ Standard Library style, the deque class would provide push_front() and pop_back() operations in addition to push_back() and pop_front() (equivalent to a queue’s push() and pop()).

There is no InlineVarLenEntryDeque class because there is no efficient way to implement push_front() and pop_back(). These operations would necessarily be O(n), since each entry knows the position of the next entry, but not the previous, as in a single-linked list. Given that these operations would be inefficient and unlikely to be used, they are not implemented, and only a queue class is provided.

Size reports#

The tables below illustrate the following scenarios:

  • Scenarios related to InlineDeque:

    • The memory and code size cost incurred by a adding a single InlineDeque.

    • The memory and code size cost incurred by adding another InlineDeque with a different type. As InlineDeque is templated on type, this results in additional code being generated.

  • Scenarios related to InlineQueue:

    • The memory and code size cost incurred by a adding a single InlineQueue.

    • The memory and code size cost incurred by adding another InlineQueue with a different type. As InlineQueue is templated on type, this results in additional code being generated.

  • The memory and code size cost incurred by a adding both an InlineDeque and an InlineQueue of the same type. These types reuse code, so the combined sum is less than the sum of its parts.

Note

The size report that is usually displayed here is temporarily unavailable while we migrate the pigweed.dev build system from GN to Bazel. See b/388905812 for updates.

On this page