Queues#

pw::containers::internal::GenericDeque#

These types are not meant to be used directly, but provide a number of common methods for all other deque types, and by extension, queues.

template<typename CountAndCapacityType>
class GenericDequeBase#

Base class for deques.

This type does not depend on the type of the elements being stored in the container.

Template Parameters:

CountAndCapacityType – Type that encapsulates the containers overall capacity and current count of elements. Different implementation may add additional behavior when the count or capacity changes.

Subclassed by pw::containers::internal::GenericDeque< DynamicDeque< ValueType, uint16_t >, ValueType, containers::internal::CountAndCapacity< uint16_t > >, pw::containers::internal::GenericDeque< BasicInlineDequeImpl< ValueType, CountAndCapacityType, kGenericSized >, ValueType, CountAndCapacityType >, pw::containers::internal::GenericDeque< DynamicDeque< T, uint16_t >, T, containers::internal::CountAndCapacity< uint16_t > >, pw::containers::internal::GenericDeque< Derived, ValueType, CountAndCapacityType >

Public Types

using size_type = typename CountAndCapacityType::size_type#

Public Functions

inline constexpr bool empty() const noexcept#

inline constexpr size_type size() const noexcept#

Returns the number of elements in the deque.

inline constexpr size_type capacity() const noexcept#

Returns the maximum number of elements in the deque.

template<typename Derived, typename ValueType, typename CountAndCapacityType>
class GenericDeque : public pw::containers::internal::GenericDequeBase<CountAndCapacityType>#

Generic array-based deque class.

Uses CRTP to access the underlying array and handle potentially resizing it. Extended by pw::InlineDeque and pw::DynamicDeque.

Subclassed by pw::DynamicDeque< T, uint16_t >, pw::DynamicDeque< ValueType, SizeType >

Public Types

using value_type = ValueType#

using size_type = typename CountAndCapacityType::size_type#

using difference_type = ptrdiff_t#

using reference = value_type&#

using const_reference = const value_type&#

using pointer = value_type*#

using const_pointer = const value_type*#

using iterator = containers::internal::DequeIterator<Derived>#

using const_iterator = containers::internal::DequeIterator<const Derived>#

Public Functions

GenericDeque(const GenericDeque&) = delete#

GenericDeque(GenericDeque&&) = delete#

GenericDeque &operator=(const GenericDeque&) = delete#

GenericDeque &&operator=(GenericDeque&&) = delete#

inline void assign(size_type count, const value_type &value)#

Sets the contents to count copies of value. Crashes if cannot fit.

template<typename It, int&..., typename = containers::internal::EnableIfInputIterator<It>>
void assign(It start, It finish)#

Sets the contents to copies of the items from the iterator. Crashes if cannot fit.

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

Sets contents to copies of the items from the list. Crashes if cannot fit.

inline constexpr reference at(size_type index)#

inline constexpr const_reference at(size_type index) const#

inline constexpr reference operator[](size_type index)#

inline constexpr const_reference operator[](size_type index) const#

inline constexpr reference front()#

inline constexpr const_reference front() const#

inline constexpr reference back()#

inline constexpr const_reference back() const#

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

Provides access to the valid data in a contiguous form.

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

inline constexpr iterator begin() noexcept#

inline constexpr const_iterator begin() const noexcept#

inline constexpr const_iterator cbegin() const noexcept#

inline constexpr iterator end() noexcept#

inline constexpr const_iterator end() const noexcept#

inline constexpr const_iterator cend() const noexcept#

inline void clear()#

inline void push_back(const value_type &value)#

inline void push_back(value_type &&value)#

template<typename ...Args>
inline void emplace_back(Args&&... args)#

void pop_back()#

inline void push_front(const value_type &value)#

inline void push_front(value_type &&value)#

template<typename ...Args>
inline void emplace_front(Args&&... args)#

void pop_front()#

inline void resize(size_type new_size)#

inline void resize(size_type new_size, const value_type &value)#

inline constexpr size_type capacity() const noexcept#

Returns the maximum number of elements in the deque.

inline constexpr bool empty() const noexcept#

inline constexpr size_type size() const noexcept#

Returns the number of elements in the deque.

pw::DynamicDeque#

template<typename ValueType, typename SizeType = uint16_t>
class DynamicDeque : public pw::containers::internal::GenericDeque<DynamicDeque<ValueType, uint16_t>, ValueType, containers::internal::CountAndCapacity<uint16_t>>#

Double-ended queue, similar to std::deque, but optimized for embedded.

Key features of pw::DynamicDeque.

• Uses a pw::Allocator for memory operations.

• Provides the std::deque API, but adds try_* versions of operations that crash on allocation failure.

  • assign() & try_assign().

  • push_front() & try_push_front, push_back() & try_push_back

  • emplace_front() & try_emplace_front, emplace_back() & try_emplace_back

  • resize() & try_resize().

• Offers reserve()/try_reserve() and shrink_to_fit() to manage memory usage.

• Never allocates in the constructor. constexpr constructible.

• Compact representation when used with a size_type of uint8_t or uint16_t.

• Uses pw::Allocator::Resize() when possible to maximize efficiency.

Public Types

using allocator_type = Allocator#

using const_iterator = containers::internal::DequeIterator<const Derived>#

using const_pointer = const value_type*#

using const_reference = const value_type&#

using difference_type = ptrdiff_t#

using iterator = containers::internal::DequeIterator<Derived>#

using pointer = value_type*#

using reference = value_type&#

using size_type = typename CountAndCapacityType::size_type#

using value_type = ValueType#

Public Functions

inline constexpr DynamicDeque(Allocator &allocator) noexcept#

Constructs an empty DynamicDeque. No memory is allocated.

Since allocations can fail, initialization in the constructor is not supported.

DynamicDeque(const DynamicDeque&) = delete#

DynamicDeque &operator=(const DynamicDeque&) = delete#

inline constexpr DynamicDeque(DynamicDeque &&other) noexcept#

Move construction/assignment is supported since it cannot fail. Copy construction/assignment is not supported. Can use assign()/try_assign() instead.

DynamicDeque &operator=(DynamicDeque &&other) noexcept#

~DynamicDeque()#

bool try_reserve(size_type new_capacity)#

Attempts to change capacity() to new_capacity. If new_capacity is larger than capacity(), attempts to allocate memory and returns whether it succeeded. Otherwise, does nothing and returns true.

inline void reserve(size_type new_capacity)#

Changes capacity() to new_capacity. Crashes on failure.

void shrink_to_fit()#

Attempts to reduce capacity() to size(). Not guaranteed to succeed.

inline constexpr size_type max_size() const noexcept#

inline constexpr allocator_type &get_allocator() const#

inline void swap(DynamicDeque &other) noexcept#

Swaps the contents of two deques. No allocations occur.

bool try_assign(size_type count, const value_type &value)#

Attempts to replace the contents with count copies of value. If count <blockquote>&zwj;capacity() and allocation is supported, attempts to allocate to

increase capacity. Does nothing if unable to accommodate count items.

template<typename It, int&..., typename = containers::internal::EnableIfForwardIterator<It>>
bool try_assign(

It start,

It finish,

)#

Replaces the container with copies of items from an iterator. Does nothing if unable to accommodate all items.

try_assign() requires a forward iterator so that the capacity can be checked upfront to avoid partial assignments. Input iterators are only suitable for one pass, so could be exhausted by a std::distance check.

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

Replaces the container with copies of items from an initializer list. Does nothing if unable to accommodate all items.

template<typename ...Args>
bool try_emplace_back(Args&&... args)#

template<typename ...Args>
bool try_emplace_front(Args&&... args)#

inline bool try_push_back(const value_type &value)#

inline bool try_push_back(value_type &&value)#

inline bool try_push_front(const value_type &value)#

inline bool try_push_front(value_type &&value)#

inline bool try_resize(size_type new_size)#

bool try_resize(size_type new_size, const value_type &value)#

pw::InlineDeque#

template<typename ValueType, typename SizeType, size_t kCapacity = containers::internal::kGenericSized>
using pw::BasicInlineDeque = containers::internal::BasicInlineDequeImpl<ValueType, containers::internal::CountAndCapacity<SizeType>, kCapacity>#

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 a RawStorage 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.

An InlineDeque cannot increase its capacity. Any operations that would exceed the capacity (e.g. assign, push_back, push_front) fail a PW_ASSERT. Avoid this by choosing a large enough capacity or checking full() before adding items.

pw::InlineAsyncDeque#

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

Async wrapper around BasicInlineDeque.

This class mimics the structure of BasicInlineDequeImpl to allow referring to an InlineAsyncDeque without an explicit maximum size.

pw::DynamicQueue#

template<typename T, typename SizeType = uint16_t>
class DynamicQueue : public containers::internal::GenericQueue<DynamicQueue<T, uint16_t>, DynamicDeque<T, uint16_t>>#

A queue implementation backed by pw::DynamicDeque.

This class provides a std::queue-like interface but uses a Pigweed allocator for dynamic memory management. It includes fallible try_* operations for scenarios where allocation failure may be handled gracefully.

Template Parameters:

T – The type of elements stored in the queue.

Public Types

using const_iterator = typename Deque::const_iterator#

using const_pointer = typename Deque::const_pointer#

using const_reference = typename Deque::const_reference#

using difference_type = typename Deque::difference_type#

using iterator = typename Deque::iterator#

using pointer = typename Deque::pointer#

using reference = typename Deque::reference#

using size_type = typename Deque::size_type#

using value_type = typename Deque::value_type#

Public Functions

inline explicit constexpr DynamicQueue(pw::Allocator &allocator)#

Constructs a DynamicQueue using the provided allocator.

DynamicQueue(const DynamicQueue&) = delete#

DynamicQueue &operator=(const DynamicQueue&) = delete#

constexpr DynamicQueue(DynamicQueue&&) = default#

Move operations are supported and incur no allocations.

DynamicQueue &operator=(DynamicQueue&&) = default#

inline void clear()#

Removes all elements from the queue.

inline bool try_push(const value_type &value)#

Attempts to add an element to the back of the queue.

inline bool try_push(value_type &&value)#

Attempts to add an element to the back of the queue (move version).

template<typename ...Args>
inline bool try_emplace(Args&&... args)#

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

inline void reserve(size_type capacity)#

Sets the queue capacity to max(capacity, size()) elements.

inline bool try_reserve(size_type capacity)#

Attempts to set the queue capacity to max(capacity, size()) elements.

inline void shrink_to_fit()#

Reduces memory usage by releasing unused capacity, if possible.

inline void swap(DynamicQueue &other)#

Swaps the contents with another queue.

Friends

friend class containers::internal::GenericQueue

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.

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::InlineAsyncQueue#

template<typename T, size_t kCapacity = containers::internal::kGenericSized>
class InlineAsyncQueue : public pw::containers::internal::BasicInlineQueueImpl<InlineAsyncQueue<T, containers::internal::kGenericSized>, InlineAsyncDeque<T, containers::internal::kGenericSized>>#

Async wrapper around InlineQueue.

Public Types

using const_iterator = typename Deque::const_iterator#

using const_pointer = typename Deque::const_pointer#

using const_reference = typename Deque::const_reference#

using difference_type = typename Deque::difference_type#

using iterator = typename Deque::iterator#

using pointer = typename Deque::pointer#

using reference = typename Deque::reference#

using size_type = typename Deque::size_type#

using value_type = typename Deque::value_type#

Public Functions

inline async2::Poll PendAvailable(async2::Context &context, size_type num = 1)#

Returns Pending until space for num elements is available.

Friends

friend class containers::internal::GenericQueue

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.

// 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();

// 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);

// 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);

// 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);