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 or dynamic storage.
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#
-
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 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*#
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 ofvalue
. 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 const_reference at(size_type index) const#
-
inline constexpr const_reference operator[](size_type index) const#
-
inline constexpr const_reference front() const#
-
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 const_iterator begin() const noexcept#
-
inline constexpr const_iterator cbegin() const 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)#
-
void pop_back()#
-
inline void push_front(const value_type &value)#
-
inline void push_front(value_type &&value)#
-
void pop_front()#
-
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#
-
using size_type = typename CountAndCapacityType::size_type#
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 addstry_*
versions of operations that crash on allocation failure.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()
andshrink_to_fit()
to manage memory usage.Never allocates in the constructor.
constexpr
constructible.Compact representation when used with a
size_type
ofuint8_t
oruint16_t
.Uses
pw::Allocator::Resize()
when possible to maximize efficiency.
Public Types
-
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#
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()
tonew_capacity
. Ifnew_capacity
is larger thancapacity()
, attempts to allocate memory and returns whether it succeeded. Otherwise, does nothing and returnstrue
.
-
inline void reserve(size_type new_capacity)#
Changes
capacity()
tonew_capacity
. Crashes on failure.
-
void shrink_to_fit()#
Attempts to reduce
capacity()
tosize()
. Not guaranteed to succeed.
-
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 ofvalue
. Ifcount <blockquote>‍capacity()
and allocation is supported, attempts to allocate toincrease capacity. Does nothing if unable to accommodate
count
items.
-
template<typename It, int&..., typename = containers::internal::EnableIfForwardIterator<It>>
bool try_assign(
)# 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 astd::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.
-
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)#
-
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, allInlineDeque
classes inherit from theBasicInlineDequeStorage
class, which in turn inherits fromInlineDeque<T>
, which stores the maximum size in a variable. This allowsInlineDeque
s 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 aPW_ASSERT
. Avoid this by choosing a large enough capacity or checkingfull()
before adding items.
API reference#
-
template<typename ValueType, typename CountAndCapacityType, size_t kCapacity>
class BasicInlineDequeImpl : public pw::containers::internal::BasicInlineDequeStorage<ValueType, CountAndCapacityType, kCapacity, std::is_trivially_destructible_v<ValueType>># Public Functions
-
inline BasicInlineDequeImpl() noexcept#
Constructs with zero elements.
-
inline BasicInlineDequeImpl(size_type count, const_reference value)#
Constructs with
count
copies ofvalue
.
-
inline explicit BasicInlineDequeImpl(size_type count)#
Constructs with
count
default-initialized elements.
-
template<typename InputIterator, typename = EnableIfInputIterator<InputIterator>>
inline BasicInlineDequeImpl( - InputIterator start,
- InputIterator finish,
Copy constructs from an iterator.
-
inline BasicInlineDequeImpl(const BasicInlineDequeImpl &other)#
Copy constructs for matching capacity.
-
template<size_t kOtherCapacity>
inline BasicInlineDequeImpl( - const BasicInlineDequeImpl<ValueType, CountAndCapacityType, kOtherCapacity> &other,
Copy constructs for mismatched capacity.
Note that this will result in a crash if
kOtherCapacity < size()
.
-
inline BasicInlineDequeImpl(BasicInlineDequeImpl &&other) noexcept#
Move constructs for matching capacity.
-
template<size_t kOtherCapacity>
inline BasicInlineDequeImpl(
) noexcept# Move constructs for mismatched capacity.
-
inline BasicInlineDequeImpl(const std::initializer_list<value_type> &list)#
Copy constructs from an initializer list.
-
template<typename T, typename = EnableIfIterable<T>>
inline BasicInlineDequeImpl(const T &other)# Copy constructor for arbitrary iterables.
-
inline BasicInlineDequeImpl &operator=(const std::initializer_list<value_type> &list)#
Copy assigns from
list
.
-
inline BasicInlineDequeImpl &operator=(const BasicInlineDequeImpl &other)#
Copy assigns for matching capacity.
-
template<size_t kOtherCapacity>
inline BasicInlineDequeImpl &operator=( - const BasicInlineDequeImpl<ValueType, CountAndCapacityType, kOtherCapacity> &other,
Copy assigns for mismatched capacity.
Note that this will result in a crash if
kOtherCapacity < size()
.
-
inline BasicInlineDequeImpl &operator=(BasicInlineDequeImpl &&other) noexcept#
Move assigns for matching capacity.
-
template<size_t kOtherCapacity>
inline BasicInlineDequeImpl &operator=(
) noexcept# Move assigns for mismatched capacity.
-
inline BasicInlineDequeImpl() noexcept#
pw::DynamicQueue#
-
template<typename T, typename SizeType = uint16_t>
class DynamicQueue# 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 fallibletry_*
operations for scenarios where allocation failure may be handled gracefully.- Template Parameters:
T – The type of elements stored in the queue.
Public Types
-
using container_type = DynamicDeque<T, SizeType>#
-
using size_type = typename container_type::size_type#
-
using reference = value_type&#
-
using const_reference = const 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 bool empty() const#
Checks if the queue is empty.
-
inline size_type max_size() const#
Maximum possible queue
size()
, ignoring limitations of the allocator.
-
inline size_type capacity() const#
Returns the number of elements the queue can hold without attempting to allocate.
-
inline const_reference front() const#
Returns a const reference to the first element in the queue.
-
inline const_reference back() const#
Returns a const reference to the last element in the queue.
-
inline void clear()#
Removes all elements from the queue.
-
inline void push(const value_type &value)#
Copies an element to the back of the queue. Crashes on allocation failure.
-
inline void push(value_type &&value)#
Moves an element to the back of the queue. Crashes on allocation failure.
-
template<typename ...Args>
inline void emplace(Args&&... args)# Constructs an element in place at the back of the queue. Crashes on allocation failure.
-
inline void pop()#
Removes the first element from the queue. The queue must not be empty.
-
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 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.
pw::InlineQueue#
-
template<typename T, size_t kCapacity = containers::internal::kGenericSized>
using pw::InlineQueue = BasicInlineQueue<T, uint16_t, kCapacity># The
InlineQueue
class is similar tostd::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 aroundpw::InlineDeque
with a simplified API andpush_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()
.
-
inline BasicInlineQueue(const BasicInlineQueue &other)#
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
oruint8_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; calltry_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 auint32_t
array. The array MUST be larger thanPW_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 auint32_t
array. The array MUST be larger thanPW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32
(3) elements.
-
inline Entry front() const#
-
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 withstd::copy()
, sincecopy()
uses one or twomemcpy
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
-
inline std::pair<span<const value_type>, span<const value_type>> contiguous_data() const#
-
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 auint32_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 auint32_t
array. The array MUST be larger thanPW_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; calltry_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 theEnd
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 aInlineVarLenEntryQueue
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 tomax_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, inuint32_t
elements. This header stores the buffer length and head and tail offsets.The underlying
uint32_t
array of aInlineVarLenEntryQueue
must be larger than this size.
-
struct pw_InlineVarLenEntryQueue_Iterator#
Iterator object for a
InlineVarLenEntryQueue
. Iterators are checked for equality withpw_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. AsInlineDeque
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. AsInlineQueue
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 anInlineQueue
of the same type. These types reuse code, so the combined sum is less than the sum of its parts.
Label |
Segment |
Delta |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
InlineDeque |
FLASH
|
+1,048 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+84 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional InlineDeque with different item type |
FLASH
|
+800 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+172 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
InlineQueue |
FLASH
|
+608 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+84 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional InlineQueue with different item type |
FLASH
|
+416 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+172 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
InlineDeque and InlineQueue |
FLASH
|
+1,320 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+136 |