Overview

Generic collections of objects for embedded devices.

Submodules
	C API

	Lists

	Maps

	Queues

	Sets

	Utilities

	Vectors

Namespaces
namespace	pw
	The Pigweed namespace.

Classes
class	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >

class	pw::containers::internal::GenericAATree

class	pw::containers::internal::KeyedAATree< K >

class	pw::containers::internal::AATree< K, V >

class	pw::containers::internal::AATree< K, V >::Item

class	pw::containers::internal::AATree< K, V >::Pair
	An extension of `Item` that includes storage for a key. More...

Macros
#define	PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3)

#define	_PW_VAR_QUEUE_SIZE_UINT32(max_size_bytes)

#define	_PW_VAR_QUEUE_DATA_SIZE_UINT32(max_size_bytes) ((_PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes) + 3 /* round up */) / 4)

#define	_PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes)

#define	_PW_VAR_QUEUE_CHECK_SIZE(max_size_bytes)

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

template<size_t kCapacity>
using	pw::BasicInlineQueue< ValueType, SizeType, containers::internal::kGenericSized >::Derived = BasicInlineQueue< value_type, size_type, kCapacity >

using	pw::containers::internal::GenericAATree::iterator = AATreeIterator<>

using	pw::containers::internal::KeyedAATree< K >::Key = K

using	pw::containers::internal::KeyedAATree< K >::Compare = Function< bool(Key, Key)>

using	pw::containers::internal::KeyedAATree< K >::GetKey = Function< Key(const AATreeItem &)>

using	pw::containers::internal::AATree< K, V >::Base = KeyedAATree< K >

using	pw::containers::internal::AATree< K, V >::Key = typename Base::Key

using	pw::containers::internal::AATree< K, V >::Compare = typename Base::Compare

using	pw::containers::internal::AATree< K, V >::GetKey = Function< Key(const V &)>

template<typename T >
using	pw::IntrusiveList = containers::future::IntrusiveList< T >

Functions
constexpr	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (ConstexprTag constexpr_tag) noexcept

	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (size_type count, const_reference value)

	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (size_type count)

template<typename InputIterator , typename = containers::internal::EnableIfInputIterator<InputIterator>>
	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (InputIterator start, InputIterator finish)

	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (const std::initializer_list< value_type > &list)

	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (const BasicInlineQueue &other)
	Copy constructs for matching capacity.

template<size_t kOtherCapacity>
	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (const BasicInlineQueue< ValueType, SizeType, kOtherCapacity > &other)

	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (BasicInlineQueue &&other)
	Move constructs for matching capacity.

template<size_t kOtherCapacity>
	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (BasicInlineQueue< ValueType, SizeType, kOtherCapacity > &&other)

template<typename T , typename = containers::internal::EnableIfIterable<T>>
	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue (const T &other)

BasicInlineQueue &	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= (const std::initializer_list< value_type > &list)

BasicInlineQueue &	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= (const BasicInlineQueue &other)
	Copy assigns from matching capacity.

template<size_t kOtherCapacity>
BasicInlineQueue &	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= (const BasicInlineQueue< ValueType, SizeType, kOtherCapacity > &other)

BasicInlineQueue &	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= (BasicInlineQueue &&other)
	Move assigns from matching capacity.

template<size_t kOtherCapacity>
BasicInlineQueue &	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= (BasicInlineQueue< ValueType, SizeType, kOtherCapacity > &&other)

template<typename T , typename = containers::internal::EnableIfIterable<T>>
BasicInlineQueue &	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= (const T &other)

static constexpr size_type	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::max_size ()

static constexpr size_type	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::capacity ()

Deque &	pw::BasicInlineQueue< ValueType, SizeType, containers::internal::kGenericSized >::deque ()

const Deque &	pw::BasicInlineQueue< ValueType, SizeType, containers::internal::kGenericSized >::deque () const

reference	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::at (size_type index)

const_reference	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::at (size_type index) const

reference	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::operator[] (size_type index)

const_reference	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::operator[] (size_type index) const

std::pair< span< const value_type >, span< const value_type > >	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::contiguous_data () const

std::pair< span< value_type >, span< value_type > >	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::contiguous_data ()

iterator	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::begin () noexcept

const_iterator	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::begin () const noexcept

const_iterator	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::cbegin () const noexcept

iterator	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::end () noexcept

const_iterator	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::end () const noexcept

const_iterator	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::cend () const noexcept

bool	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::full () const noexcept

void	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::clear () noexcept

void	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::push_overwrite (const value_type &value)

void	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::push_overwrite (value_type &&value)

template<typename... Args>
void	pw::containers::internal::BasicInlineQueueImpl< Derived, Deque >::emplace_overwrite (Args &&... args)

constexpr	pw::containers::internal::GenericAATree::GenericAATree (bool unique_keys)

	pw::containers::internal::GenericAATree::~GenericAATree ()
	Destructor.

	pw::containers::internal::GenericAATree::GenericAATree (const GenericAATree &)=delete

GenericAATree &	pw::containers::internal::GenericAATree::operator= (const GenericAATree &)=delete

constexpr bool	pw::containers::internal::GenericAATree::unique_keys () const

void	pw::containers::internal::GenericAATree::SetRoot (AATreeItem *item)
	Sets the tree's root item.

constexpr iterator	pw::containers::internal::GenericAATree::begin () noexcept
	Returns a pointer to the first item, if any.

constexpr iterator	pw::containers::internal::GenericAATree::end () noexcept
	Returns a pointer to the last item, if any.

constexpr bool	pw::containers::internal::GenericAATree::empty () const
	Returns whether the tree has zero items or not.

size_t	pw::containers::internal::GenericAATree::size () const
	Returns the number of items in the tree.

constexpr size_t	pw::containers::internal::GenericAATree::max_size () const noexcept

void	pw::containers::internal::GenericAATree::clear ()

iterator	pw::containers::internal::GenericAATree::erase_one (AATreeItem &item)

iterator	pw::containers::internal::GenericAATree::erase_range (AATreeItem &first, AATreeItem &last)

iterator	pw::containers::internal::GenericAATree::erase_range (iterator first, iterator last)

void	pw::containers::internal::GenericAATree::swap (GenericAATree &other)
	Exchanges this tree's items with the `other` tree's items.

constexpr	pw::containers::internal::KeyedAATree< K >::KeyedAATree (bool unique_keys, Compare &&compare, GetKey &&get_key)

void	pw::containers::internal::KeyedAATree< K >::SetCompare (Compare &&compare)

void	pw::containers::internal::KeyedAATree< K >::SetGetKey (GetKey &&get_key)

std::pair< iterator, bool >	pw::containers::internal::KeyedAATree< K >::insert (AATreeItem &item)

template<class Iterator >
void	pw::containers::internal::KeyedAATree< K >::insert (Iterator first, Iterator last)

size_t	pw::containers::internal::KeyedAATree< K >::erase_all (Key key)

void	pw::containers::internal::KeyedAATree< K >::merge (KeyedAATree< K > &other)

size_t	pw::containers::internal::KeyedAATree< K >::count (Key key)

iterator	pw::containers::internal::KeyedAATree< K >::find (Key key)

std::pair< iterator, iterator >	pw::containers::internal::KeyedAATree< K >::equal_range (Key key)

iterator	pw::containers::internal::KeyedAATree< K >::lower_bound (Key key)

iterator	pw::containers::internal::KeyedAATree< K >::upper_bound (Key key)

constexpr	pw::containers::internal::AATree< K, V >::Pair::Pair (Key key)

constexpr Key	pw::containers::internal::AATree< K, V >::Pair::key () const

constexpr bool	pw::containers::internal::AATree< K, V >::Pair::operator< (const Pair &rhs)

constexpr	pw::containers::internal::AATree< K, V >::AATree (bool unique_keys, Compare &&compare, GetKey &&get_key)

Variables
GetKey	pw::containers::internal::AATree< K, V >::get_key_

Friends
template<typename , typename >
class	pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::containers::internal::BasicInlineQueueImpl

template<typename , typename >
class	pw::BasicInlineQueue< ValueType, SizeType, containers::internal::kGenericSized >::containers::internal::GenericQueue

template<typename >
class	pw::containers::internal::GenericAATree::KeyedAATree

template<typename , typename , bool >
struct	pw::containers::internal::AATree< K, V >::Item::IntrusiveItem

Macro Definition Documentation

◆ _PW_VAR_QUEUE_CHECK_SIZE

#define _PW_VAR_QUEUE_CHECK_SIZE ( max_size_bytes )

Value:

static_assert(sizeof(pw::InlineVarLenEntryQueue<max_size_bytes>) == \

_PW_VAR_QUEUE_SIZE_UINT32(max_size_bytes) * sizeof(uint32_t));

pw::BasicInlineVarLenEntryQueue

Definition: inline_var_len_entry_queue.h:101

◆ _PW_VAR_QUEUE_DATA_SIZE_BYTES

#define _PW_VAR_QUEUE_DATA_SIZE_BYTES ( max_size_bytes )

Value:

(PW_VARINT_ENCODED_SIZE_BYTES(max_size_bytes) + max_size_bytes + \

1 /*end byte*/)

PW_VARINT_ENCODED_SIZE_BYTES

#define PW_VARINT_ENCODED_SIZE_BYTES(value)

Definition: varint.h:290

◆ _PW_VAR_QUEUE_SIZE_UINT32

#define _PW_VAR_QUEUE_SIZE_UINT32 ( max_size_bytes )

Value:

(PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 + \

_PW_VAR_QUEUE_DATA_SIZE_UINT32(max_size_bytes))

PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32

#define PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32

Definition: inline_var_len_entry_queue.h:77

◆ PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32

#define PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3)

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.

Typedef Documentation

◆ InlineDeque

template<typename T , size_t kCapacity = containers::internal::kGenericSized>

using pw::InlineDeque = typedef 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.

◆ IntrusiveList

template<typename T >

using pw::IntrusiveList = typedef containers::future::IntrusiveList<T>

A doubly-linked intrusive list.

IntrusiveList<T> is a handle to access and manipulate the list, and IntrusiveList<T>::Item is the type from which the base class items must derive.

As a doubly-linked list, operations such as removal are O(1) in time, and the list may be iterated in either direction. However, the overhead needed is 2*sizeof(T*).

This class is modeled on std::list, with the following differences:

Since items are not allocated by this class, the following methods have no analogue:
- std::list<T>::get_allocator
- std::list<T>::emplace
- std::list<T>::emplace_front
- std::list<T>::emplace_back
- std::list<T>::resize
Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:
- std::list<T>::(constructor)
- std::list<T>::assign
- std::list<T>::insert
There are no overloads corresponding to the following methods that take r-value references.:
- std::list<T>::insert
- std::list<T>::push_back
- std::list<T>::push_front
- std::list<T>::splice
Since modifying the list modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
- std::list<T>::insert
- std::list<T>::erase
- std::list<T>::splice
An additional overload of erase is provided that takes a direct reference to an item.
C++23 methods are not (yet) supported.

Template Parameters

T	Type of intrusive items stored in the list.

Function Documentation

◆ AATree()

template<typename K , typename V >

constexpr pw::containers::internal::AATree< K, V >::AATree	(	bool	unique_keys,
		Compare &&	compare,
		GetKey &&	get_key
	)

inlineconstexpr

Constructs an empty AA tree.

Parameters

unique_keys Indicates if this tree requires unique keys or allows duplicate keys.

◆ BasicInlineQueue() [1/2]

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

template<size_t kOtherCapacity>

pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue ( BasicInlineQueue< ValueType, SizeType, kOtherCapacity > && other )

inline

Move constructs for mismatched capacity.

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

◆ BasicInlineQueue() [2/2]

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

template<size_t kOtherCapacity>

pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::BasicInlineQueue ( const BasicInlineQueue< ValueType, SizeType, kOtherCapacity > & other )

inline

Copy constructs for mismatched capacity.

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

◆ clear()

void pw::containers::internal::GenericAATree::clear ( )

Removes all items from the tree and leaves it empty.

The items themselves are not destructed.

◆ count()

template<typename K >

size_t pw::containers::internal::KeyedAATree< K >::count ( Key key )

Returns the number of items in the tree with the given key.

If the tree requires unique keys, this simply 0 or 1.

◆ equal_range()

template<typename K >

std::pair< GenericAATree::iterator, GenericAATree::iterator > pw::containers::internal::KeyedAATree< K >::equal_range ( Key key )

Returns a pair of items where the first points to the item with the smallest key that is not less than the given key, and the second points to the item with the smallest key that is greater than the given key.

◆ erase_all()

template<typename K >

size_t pw::containers::internal::KeyedAATree< K >::erase_all ( Key key )

Removes items that match the given key, and returns an iterator to the item after the removed items and the number of items removed.

◆ erase_one()

iterator pw::containers::internal::GenericAATree::erase_one ( AATreeItem & item )

Removes an item from the tree and returns an iterator to the item after the removed item.

The items themselves are not destructed.

◆ erase_range() [1/2]

iterator pw::containers::internal::GenericAATree::erase_range	(	AATreeItem &	first,
		AATreeItem &	last
	)

Removes the items from first, inclusive, to last, exclusive from the tree and returns an iterator to the item after the last removed item.

The items themselves are not destructed.

◆ erase_range() [2/2]

iterator pw::containers::internal::GenericAATree::erase_range	(	iterator	first,
		iterator	last
	)

Removes the items from first, inclusive, to last, exclusive from the tree

and returns an iterator to the item after the last removed item.

The items themselves are not destructed.

◆ find()

template<typename K >

GenericAATree::iterator pw::containers::internal::KeyedAATree< K >::find ( Key key )

Returns a pointer to an item with the given key, or null if the tree does not contain such an item.

◆ GenericAATree()

constexpr pw::containers::internal::GenericAATree::GenericAATree ( bool unique_keys )

inlineexplicitconstexpr

Constructs an empty AA tree.

Parameters

unique_keys Indicates if this tree requires unique keys or allows duplicate keys.

◆ insert() [1/2]

template<typename K >

std::pair< GenericAATree::iterator, bool > pw::containers::internal::KeyedAATree< K >::insert ( AATreeItem & item )

Attempts to add the given item to the tree.

The item will be added if the tree does not already contain an item with the given item's key or if the tree does not require unique keys.

Precondition: The item must not be a part of any tree.

Returns: A pointer to the inserted item and true, or a pointer to the existing item with same key and false.

◆ insert() [2/2]

template<typename K >

template<class Iterator >

void pw::containers::internal::KeyedAATree< K >::insert	(	Iterator	first,
		Iterator	last
	)

Inserts each item from first, inclusive, to last, exclusive. If the tree does not all duplicates and an equivalent item is already in the tree, the item is ignored.

◆ KeyedAATree()

template<typename K >

constexpr pw::containers::internal::KeyedAATree< K >::KeyedAATree	(	bool	unique_keys,
		Compare &&	compare,
		GetKey &&	get_key
	)

inlineexplicitconstexpr

Constructs an empty AA tree.

Parameters

unique_keys Indicates if this tree requires unique keys or allows duplicate keys.

◆ lower_bound()

template<typename K >

GenericAATree::iterator pw::containers::internal::KeyedAATree< K >::lower_bound ( Key key )

Returns the item in the tree with the smallest key that is greater than or equal to the given key, or null if the tree is empty.

◆ max_size()

constexpr size_t pw::containers::internal::GenericAATree::max_size ( ) const

inlineconstexprnoexcept

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

◆ merge()

template<typename K >

void pw::containers::internal::KeyedAATree< K >::merge ( KeyedAATree< K > & other )

Splices items from the other tree into this one.

The receiving tree's Compare and GetKey functions are used when inserting items.

◆ operator=() [1/2]

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

template<size_t kOtherCapacity>

BasicInlineQueue & pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= ( BasicInlineQueue< ValueType, SizeType, kOtherCapacity > && other )

inline

Move assigns from mismatched capacity.

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

◆ operator=() [2/2]

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

template<size_t kOtherCapacity>

BasicInlineQueue & pw::BasicInlineQueue< ValueType, SizeType, kCapacity >::operator= ( const BasicInlineQueue< ValueType, SizeType, kOtherCapacity > & other )

inline

Copy assigns from mismatched capacity.

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

◆ upper_bound()

template<typename K >

GenericAATree::iterator pw::containers::internal::KeyedAATree< K >::upper_bound ( Key key )

Returns the item in the tree with the smallest key that is strictly greater than the given key, or null if the tree is empty.

Overview

Submodules

Namespaces

Classes

Macros

Typedefs

Functions

Variables

Friends

Macro Definition Documentation

◆ _PW_VAR_QUEUE_CHECK_SIZE

◆ _PW_VAR_QUEUE_DATA_SIZE_BYTES

◆ _PW_VAR_QUEUE_SIZE_UINT32

◆ PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32

Typedef Documentation

◆ InlineDeque

◆ IntrusiveList

Function Documentation

◆ AATree()

◆ BasicInlineQueue() [1/2]

◆ BasicInlineQueue() [2/2]

◆ clear()

◆ count()

◆ equal_range()

◆ erase_all()

◆ erase_one()

◆ erase_range() [1/2]

◆ erase_range() [2/2]

◆ find()

◆ GenericAATree()

◆ insert() [1/2]

◆ insert() [2/2]

◆ KeyedAATree()

◆ lower_bound()

◆ max_size()

◆ merge()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ upper_bound()