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.

Pigweed provides many queue and deque implementations to meet different needs.

`std::deque` & `std::queue` equivalents#

pw_containers provides a family of deques and queues that implement the std:deque or std::queue API, but offer much more control with significantly smaller code size.

The std::deque-like containers are:

pw::Deque – uses a fixed-capacity external storage buffer
pw::FixedDeque – uses a fixed-capacity storage buffer, which is optionally owned and may be statically or dynamically allocated
pw::DynamicDeque – dynamically allocates a storage buffer using a pw::Allocator
pw::InlineDeque – uses an inline, statically allocated storage buffer

Equivalent std::queue-like classes are also provided:

POD deque specialization for FixedDeque#

When the element type of a pw::FixedDeque is a POD (Plain Old Data) type – specifically, a type that is both trivially copyable and trivially destructible (e.g., primitives like uint32_t or simple structs) – pw_containers automatically uses an optimized, type-erased specialization.

Because the underlying byte-manipulation implementation is shared across different POD element types rather than re-instantiated per template parameter, additional instantiations of FixedDeque with POD types incur significantly less code size overhead.

Code size savings#

Additional POD instantiations: Additional instances of FixedDeque with POD element types save ~59.6% in flash memory compared to the initial instance cost, whereas non-POD types only save ~20% across additional instantiations.

\[\text{Savings} = \frac{\text{FlashSize}_{\text{Initial}} - \text{FlashSize}_{\text{Additional}}}{\text{FlashSize}_{\text{Initial}}}\]
Primitive POD types: For simple primitive types like uint32_t or uint64_t, static FixedDeque instantiations save ~25% flash memory on additional instances.

Note

In size reporting comparisons between POD and non-POD FixedDeque instances, initial flash numbers for POD types may appear slightly higher than expected compared to other deques. This is because the benchmark uses a data structure slightly more complex than a primitive to minimize code size disparity from non-trivial constructors/destructors, bringing their initial flash size numbers closer for a fair comparison.

pw::InlineVarLenEntryQueue#

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.

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

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.

Example#

C++

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

void GenericCapacityQueue() {
  // 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.

void InitFromArray() {
  // 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);
}

C

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

Python API reference#

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.

The queue includes both the data buffer and the indices that designate the range in the buffer that contains variable-length entries.

Parameters:: queue – The bytes representation of a variable-length entry queue.
Yields:: Each entry in the buffer as bytes.

Size reports#

The tables below illustrate the memory and code size costs for various queue and deque implementations, with std::deque serving as a baseline. The size reports generally cover:

The cost of a single instance.
The cost of instantiating a second container of the same class with a different element type, showing the impact of templates on code size.
The cost of using related classes, such as pw::InlineQueue and pw::InlineDeque or static and dynamic pw::FixedDeques.

Label

Segment

Delta

std::deque

FLASH

	+528	[section .rodata]
	+86	pw::string::FormatVaList()
	+4	__aeabi_dcmpun
	+4	pw::containers::size_report::Measure()
	+2	pw::allocator::LibCAllocator::DoReallocate()
DEL	-8	__aeabi_memmove
NEW	+682	std::__2::deque<>::__add_front_capacity[abi:nqn240000]()
NEW	+584	std::__2::deque<>::__add_back_capacity[abi:nqn240000]()
NEW	+512	std::__2::deque<>::insert[abi:nqn240000]()
NEW	+352	std::__2::deque<>::erase[abi:nqn240000]()
NEW	+284	std::__2::__split_buffer<>::emplace_front[abi:nqn240000]<>()
NEW	+276	std::__2::__split_buffer<>::emplace_back[abi:nqn240000]<>()
NEW	+262	pw::containers::size_report::MeasureDeque<>()
NEW	+228	std::__2::__copy_move_unwrap_iters[abi:nqn240000]<>()
NEW	+204	std::__2::deque<>::__move_construct_backward_and_check[abi:nqn240000]()
NEW	+184	std::__2::deque<>::__move_backward_and_check[abi:nqn240000]()
NEW	+180	std::__2::deque<>::__move_construct_and_check[abi:nqn240000]()
NEW	+168	std::__2::deque<>::__move_and_check[abi:nqn240000]()
NEW	+148	std::__2::__move_impl<>::operator()[abi:nqn240000]<>()
NEW	+144	std::__2::__move_backward_impl<>::operator()[abi:nqn240000]<>()
NEW	+144	std::__2::deque<>::__erase_to_end[abi:nqn240000]()
NEW	+136	std::__2::deque<>::__append_with_size[abi:nqn240000]<>()
NEW	+126	std::__2::deque<>::__append[abi:nqn240000]()
NEW	+120	std::__2::__deque_iterator<>::operator+=[abi:nqn240000]()
NEW	+112	std::__2::deque<>::clear[abi:nqn240000]()
NEW	+106	std::__2::__for_each_n_segment[abi:nqn240000]<>()
NEW	+104	std::__2::__copy_impl::operator()[abi:nqn240000]<>()
NEW	+100	std::__2::__libcpp_verbose_abort()
NEW	+98	std::__2::__split_buffer<>::shrink_to_fit[abi:nqn240000]()
NEW	+96	std::__2::deque<>::__assign_with_size_random_access[abi:nqn240000]<>()
NEW	+80	std::__2::operator-[abi:nqn240000]()
NEW	+70	std::__2::deque<>::shrink_to_fit[abi:nqn240000]()
NEW	+66	std::__2::__for_each_segment_backward[abi:nqn240000]<>()
NEW	+66	std::__2::deque<>::push_front[abi:nqn240000]()
NEW	+60	std::__2::deque<>::resize[abi:nqn240000]()
NEW	+60	std::__2::move[abi:nqn240000]<>()
NEW	+60	std::__2::move_backward[abi:nqn240000]<>()
NEW	+56	std::__2::__for_each_segment[abi:nqn240000]<>()
NEW	+54	std::__2::deque<>::__maybe_remove_back_spare[abi:nqn240000]()
NEW	+52	pw::InlineBasicString<>::SetSizeAndTerminate()
NEW	+52	pw::containers::size_report::MeasureStdDeque<>()
NEW	+50	std::__2::__split_buffer<>::__split_buffer[abi:nqn240000]()
NEW	+50	std::__2::deque<>::__maybe_remove_front_spare[abi:nqn240000]()
NEW	+42	pw::InlineBasicString<>::InlineBasicString()
NEW	+42	pw::containers::size_report::MeasureContainer<>()
NEW	+42	std::__2::deque<>::push_back[abi:nqn240000]()
NEW	+40	pw::string_impl::CheckedCastToSize<>()
NEW	+38	std::__2::deque<>::end[abi:nqn240000]()
NEW	+36	std::__2::__split_buffer<>::~__split_buffer[abi:nqn240000]()
NEW	+36	std::__2::deque<>::begin[abi:nqn240000]()
NEW	+28	std::__2::__move_backward_impl<>::operator()[abi:nqn240000]<>()::{lambda()#1}::operator()[abi:nqn240000]()
NEW	+28	std::__2::__move_impl<>::operator()[abi:nqn240000]<>()::{lambda()#1}::operator()[abi:nqn240000]()
NEW	+28	std::__2::deque<>::__back_spare[abi:nqn240000]()
NEW	+26	std::__2::__fill_n[abi:nqn240000]<>()
NEW	+26	std::__2::__split_buffer<>::__construct_at_end_with_size[abi:nqn240000]<>()
NEW	+24	std::__2::__copy_n[abi:nqn240000]<>()
NEW	+24	std::__2::copy[abi:nqn240000]<>()
NEW	+24	std::__2::copy_n[abi:nqn240000]<>()
NEW	+24	std::__2::deque<>::back[abi:nqn240000]()
NEW	+22	std::__2::deque<>::pop_front[abi:nqn240000]()
NEW	+20	std::__2::__deque_iterator<>::operator-=[abi:nqn240000]()
NEW	+20	std::__2::unique_ptr<>::reset[abi:nqn240000]()
NEW	+18	std::__2::__fill_n[abi:nqn240000]<>()::{lambda()#1}::operator()[abi:nqn240000]()
NEW	+18	std::__2::allocator<>::allocate[abi:nqn240000]()
NEW	+16	std::__2::__allocator_destructor<>::operator()[abi:nqn240000]()
NEW	+16	std::__2::deque<>::pop_back[abi:nqn240000]()
NEW	+14	std::__2::unique_ptr<>::~unique_ptr[abi:nqn240000]()
NEW	+12	std::__2::__split_buffer<>::__construct_at_end[abi:nqn240000]<>()
NEW	+12	std::__2::deque<>::assign[abi:nqn240000]<>()
NEW	+12	std::__throw_bad_array_new_length[abi:nqn240000]()
NEW	+10	std::__2::deque<>::__back_spare_blocks[abi:nqn240000]()
NEW	+8	__aeabi_memmove4
NEW	+8	operator new()

+7,456

+60

Additional std::deque with different item type

FLASH

+682	std::__2::deque<>::__add_front_capacity[abi:nqn240000]()
+584	std::__2::deque<>::__add_back_capacity[abi:nqn240000]()
+520	std::__2::deque<>::insert[abi:nqn240000]()
+352	std::__2::deque<>::erase[abi:nqn240000]()
+284	std::__2::__split_buffer<>::emplace_front[abi:nqn240000]<>()
+276	std::__2::__split_buffer<>::emplace_back[abi:nqn240000]<>()
+272	pw::containers::size_report::MeasureDeque<>()
+228	std::__2::__copy_move_unwrap_iters[abi:nqn240000]<>()
+210	std::__2::deque<>::__move_construct_backward_and_check[abi:nqn240000]()
+186	std::__2::deque<>::__move_backward_and_check[abi:nqn240000]()
+188	std::__2::deque<>::__move_construct_and_check[abi:nqn240000]()
+168	std::__2::deque<>::__move_and_check[abi:nqn240000]()
+148	std::__2::__move_impl<>::operator()[abi:nqn240000]<>()
+144	std::__2::__move_backward_impl<>::operator()[abi:nqn240000]<>()
+144	std::__2::deque<>::__erase_to_end[abi:nqn240000]()
+146	std::__2::deque<>::__append_with_size[abi:nqn240000]<>()
+130	std::__2::deque<>::__append[abi:nqn240000]()
+120	std::__2::__deque_iterator<>::operator+=[abi:nqn240000]()
+112	std::__2::deque<>::clear[abi:nqn240000]()
+106	std::__2::__for_each_n_segment[abi:nqn240000]<>()
+104	std::__2::__copy_impl::operator()[abi:nqn240000]<>()
+98	std::__2::__split_buffer<>::shrink_to_fit[abi:nqn240000]()
+96	std::__2::deque<>::__assign_with_size_random_access[abi:nqn240000]<>()
+80	std::__2::operator-[abi:nqn240000]()
+70	std::__2::deque<>::shrink_to_fit[abi:nqn240000]()
+66	std::__2::__for_each_segment_backward[abi:nqn240000]<>()
+70	std::__2::deque<>::push_front[abi:nqn240000]()
+60	std::__2::deque<>::resize[abi:nqn240000]()
+60	std::__2::move[abi:nqn240000]<>()
+60	std::__2::move_backward[abi:nqn240000]<>()
-4	vPortSVCHandler_C
+56	std::__2::__for_each_segment[abi:nqn240000]<>()
+54	std::__2::deque<>::__maybe_remove_back_spare[abi:nqn240000]()
+52	pw::containers::size_report::MeasureStdDeque<>()
+50	std::__2::__split_buffer<>::__split_buffer[abi:nqn240000]()
+50	std::__2::deque<>::__maybe_remove_front_spare[abi:nqn240000]()
+42	pw::containers::size_report::MeasureContainer<>()
+48	std::__2::deque<>::push_back[abi:nqn240000]()
+38	std::__2::deque<>::end[abi:nqn240000]()
+36	std::__2::__split_buffer<>::~__split_buffer[abi:nqn240000]()
+36	std::__2::deque<>::begin[abi:nqn240000]()
+20	pw::containers::size_report::Measure()
+28	std::__2::__move_backward_impl<>::operator()[abi:nqn240000]<>()::{lambda()#1}::operator()[abi:nqn240000]()
+28	std::__2::__move_impl<>::operator()[abi:nqn240000]<>()::{lambda()#1}::operator()[abi:nqn240000]()
+28	std::__2::deque<>::__back_spare[abi:nqn240000]()
+32	std::__2::__fill_n[abi:nqn240000]<>()
+24	std::__2::__split_buffer<>::__construct_at_end_with_size[abi:nqn240000]<>()
+24	std::__2::__copy_n[abi:nqn240000]<>()
+24	std::__2::copy[abi:nqn240000]<>()
+24	std::__2::copy_n[abi:nqn240000]<>()
+24	std::__2::deque<>::back[abi:nqn240000]()
+22	std::__2::deque<>::pop_front[abi:nqn240000]()
+20	std::__2::__deque_iterator<>::operator-=[abi:nqn240000]()
+20	std::__2::unique_ptr<>::reset[abi:nqn240000]()
+18	std::__2::__fill_n[abi:nqn240000]<>()::{lambda()#1}::operator()[abi:nqn240000]()
+18	std::__2::allocator<>::allocate[abi:nqn240000]()
+16	std::__2::__allocator_destructor<>::operator()[abi:nqn240000]()
+16	std::__2::deque<>::pop_back[abi:nqn240000]()
+14	std::__2::unique_ptr<>::~unique_ptr[abi:nqn240000]()
+12	std::__2::__split_buffer<>::__construct_at_end[abi:nqn240000]<>()
+12	std::__2::deque<>::assign[abi:nqn240000]<>()
+10	std::__2::deque<>::__back_spare_blocks[abi:nqn240000]()

+6,656

+108

DynamicDeque

FLASH

	+240	[section .rodata]
	+2	pw::containers::size_report::SetBaseline()
	-12	vPortSVCHandler_C
	-2	pw::allocator::Layout::Of<>()
	+4	pw::containers::size_report::Measure()
	+2	pw::allocator::LibCAllocator::DoReallocate()
NEW	+192	pw::containers::size_report::MeasureDeque<>()
NEW	+156	pw::containers::internal::GenericDeque<>::erase()
NEW	+126	pw::DynamicDeque<>::ReallocateBuffer()
NEW	+108	std::__2::__copy_move_unwrap_iters[abi:nqn240000]<>()
NEW	+100	std::__2::__move_backward_impl<>::operator()[abi:nqn240000]<>()
NEW	+100	std::__2::__uninitialized_move[abi:nqn240000]<>()
NEW	+98	std::__2::__move_impl<>::operator()[abi:nqn240000]<>()
NEW	+96	pw::containers::internal::GenericDeque<>::try_assign<>()
NEW	+86	std::__2::__uninitialized_move_n[abi:nqn240000]<>()
NEW	+84	pw::containers::internal::GenericDeque<>::ShiftLeft()
NEW	+82	pw::containers::internal::GenericDeque<>::contiguous_data()
NEW	+78	pw::containers::internal::GenericDeque<>::ShiftRight()
NEW	+76	pw::containers::internal::GenericDeque<>::try_resize()
NEW	+74	pw::DynamicDeque<>::try_reserve()
NEW	+70	pw::DynamicDeque<>::shrink_to_fit()
NEW	+70	pw::containers::internal::GenericDeque<>::try_insert()
NEW	+68	pw::DynamicDeque<>::IncreaseCapacity()
NEW	+68	pw::containers::internal::GenericDeque<>::insert()
NEW	+60	pw::containers::internal::GenericDeque<>::back()
NEW	+60	pw::containers::size_report::MeasureDynamicDeque<>()
NEW	+56	pw::containers::internal::GenericDeque<>::FillAt()
NEW	+54	pw::containers::internal::GenericDeque<>::ShiftForInsert()
NEW	+54	pw::containers::internal::GenericDeque<>::resize()
NEW	+52	pw::containers::internal::GenericDequeBase<>::AbsoluteIndexChecked()
NEW	+44	pw::containers::internal::GenericDeque<>::front()
NEW	+44	pw::containers::internal::GenericDeque<>::pop_back()
NEW	+44	pw::containers::internal::GenericDeque<>::pop_front()
NEW	+40	pw::containers::internal::GenericDeque<>::assign<>()
NEW	+40	pw::containers::internal::GenericDeque<>::push_back()
NEW	+40	pw::containers::internal::GenericDeque<>::push_front()
NEW	+40	pw::containers::internal::GenericDeque<>::try_emplace_front<>()
NEW	+40	std::__2::uninitialized_move_n[abi:nqn240000]<>()
NEW	+36	pw::containers::size_report::MeasureContainer<>()
NEW	+36	std::__2::move[abi:nqn240000]<>()
NEW	+36	std::__2::move_backward[abi:nqn240000]<>()
NEW	+36	std::__2::uninitialized_move[abi:nqn240000]<>()
NEW	+30	pw::containers::internal::GenericDeque<>::try_emplace_back<>()
NEW	+26	pw::DynamicDeque<>::DeallocateBuffer()
NEW	+24	pw::containers::internal::GenericDequeBase<>::PopFront()
NEW	+24	pw::containers::internal::GenericDequeBase<>::PushBack()
NEW	+22	pw::containers::internal::GenericDeque<>::CheckCapacityAdd()
NEW	+22	pw::containers::internal::GenericDequeBase<>::PopBack()
NEW	+20	pw::containers::internal::GenericDeque<>::EmplaceBackUnchecked<>()
NEW	+20	pw::containers::internal::GenericDequeBase<>::PushFront()
NEW	+16	pw::containers::internal::GenericDeque<>::at()
NEW	+14	std::__2::__uninitialized_fill_n[abi:nqn240000]<>()
NEW	+12	pw::containers::internal::DequeIterator<>::operator*()

+3,008

+52

Additional DynamicDeque with different item type

+2,736

+100

FixedDeque (static)

+808

+92

Additional FixedDeque (static) with different item type

+592

+180

FixedDeque (dynamic)

+1,264

+52

Additional FixedDeque (dynamic) with different item type

+928

+100

FixedDeque (static and dynamic)

+1,944

+112

InlineDeque

+984

+80

Additional InlineDeque with different item type

+768

+176

InlineQueue

+624

+80

Additional InlineQueue with different item type

+400

+176

InlineDeque and InlineQueue

+1,248

+128

FixedDeque w/ POD

+808

+180

Additional FixedDeque with different POD item type

+336

+180

FixedDeque w/ non-POD

+1,336

+180

Additional FixedDeque with different non-POD item type

+1,088

+180

API reference#

Moved: pw_containers_queues

Queues#

std::deque & std::queue equivalents#

POD deque specialization for FixedDeque#

Code size savings#

pw::InlineVarLenEntryQueue#

Queue vs. deque#

Example#

Python API reference#

Size reports#

API reference#

`std::deque` & `std::queue` equivalents#