pw_containers#

The pw_containers module provides embedded-friendly container classes.

pw::Vector#

The Vector class is similar to std::vector, except it is backed by a fixed-size buffer. Vectors must be declared with an explicit maximum size (e.g. Vector<int, 10>) but vectors can be used and referred to without the max size template parameter (e.g. Vector<int>).

To allow referring to a pw::Vector without an explicit maximum size, all Vector classes inherit from the generic Vector<T>, which stores the maximum size in a variable. This allows Vectors 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.

pw::InlineDeque#

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

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

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

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.

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#

C++

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

Queue vs. deque#

This module provides 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.

API Reference#

C++#

template<size_t kMaxSizeBytes = containers::internal::kGenericSized> using InlineVarLenEntryQueue = BasicInlineVarLenEntryQueue<std::byte, kMaxSizeBytes>#: Variable-length entry queue that uses std::byte for the byte type.

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

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

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

Public Functions

inline Entry front() const#

Returns the first entry in the queue.

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

inline const_iterator begin() const#: Returns an iterator to the start of the InlineVarLenEntryQueue.

inline const_iterator end() const#: Returns an iterator that points past the end of the queue.

inline bool empty() const#: Returns true if the InlineVarLenEntryQueue is empty, false if it has at least one entry.

inline size_type size() const#: Returns the number of variable-length entries in the queue. This is O(n) in the number of entries in the queue.

inline size_type max_size() const#: Returns the maximum number of entries in the queue. This is only attainable if all entries are empty.

inline size_type size_bytes() const#: Returns the combined size in bytes of all entries in the queue, excluding metadata. This is O(n) in the number of entries in the queue.

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

inline span<const T> raw_storage() const#: Underlying storage of the variable-length entry queue. May be used to memcpy the queue.

inline void clear()#: Empties the queue.

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

Appends an entry to the end of the queue.

Pre:: The entry MUST NOT be larger than max_size_bytes().
Pre:: There must be sufficient space in the queue for this entry.

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

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

Returns:: true if the data was added to the queue; false if it did not fit
Pre:: The entry MUST NOT be larger than max_size_bytes().

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

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

Pre:: The entry MUST NOT be larger than max_size_bytes().

inline void pop()#

Removes the first entry from queue.

Pre:: The queue MUST have at least one entry.

Public Static Functions

template<size_t kArraySize> static inline BasicInlineVarLenEntryQueue &Init(uint32_t (&array)[kArraySize])#: Initializes a InlineVarLenEntryQueue in place in a uint32_t array. The array MUST be larger than PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements.

static inline BasicInlineVarLenEntryQueue &Init(uint32_t array[], size_t array_size_uint32)#: Initializes a InlineVarLenEntryQueue in place in a uint32_t array. The array MUST be larger than PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements.

class Entry#

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

Public Functions

inline std::pair<span<const value_type>, span<const value_type>> contiguous_data() const#: Entries may be stored in up to two segments, so this returns spans refering to both portions of the entry. If the entry is contiguous, the second span is empty.

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

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

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

Parameters:

entry – The entry whose contents to copy
dest – The buffer into which to copy the serialized entry
count – Copy up to this many bytes; must not be larger than the dest buffer, but may be larger than the entry

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

class iterator#

Iterator object for a InlineVarLenEntryQueue.

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

C#

typedef uint32_t *pw_InlineVarLenEntryQueue_Handle#: Handle that refers to a InlineVarLenEntryQueue. In memory, the queue is a uint32_t array.

typedef const uint32_t *pw_InlineVarLenEntryQueue_ConstHandle#

static inline void pw_InlineVarLenEntryQueue_Init(uint32_t array[], size_t array_size_uint32)#: Initializes a InlineVarLenEntryQueue in place in a uint32_t array. The array MUST be larger than PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements.

static inline void pw_InlineVarLenEntryQueue_Clear(pw_InlineVarLenEntryQueue_Handle queue)#: Empties the queue.

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

Appends an entry to the end of the queue.

Pre:: The entry MUST NOT be larger than max_size_bytes().
Pre:: There must be sufficient space in the queue for this entry.

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

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

Returns:: true if the data was added to the queue; false if it did not fit
Pre:: The entry MUST NOT be larger than max_size_bytes().

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

Pre:: The entry MUST NOT be larger than max_size_bytes().

void pw_InlineVarLenEntryQueue_Pop(pw_InlineVarLenEntryQueue_Handle queue)#

Removes the first entry from queue.

Pre:: The queue MUST have at least one entry.

static inline pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_Begin(pw_InlineVarLenEntryQueue_ConstHandle queue)#: Returns an iterator to the start of the InlineVarLenEntryQueue.

static inline pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_End(pw_InlineVarLenEntryQueue_ConstHandle queue)#: Returns an iterator that points past the end of the queue.

void pw_InlineVarLenEntryQueue_Iterator_Advance(pw_InlineVarLenEntryQueue_Iterator *iterator)#: Advances an iterator to point to the next entry in the queue. It is invalid to call Advance on an iterator equal to the End iterator.

static inline bool pw_InlineVarLenEntryQueue_Iterator_Equal( const pw_InlineVarLenEntryQueue_Iterator *lhs, const pw_InlineVarLenEntryQueue_Iterator *rhs, )#: Compares two iterators for equality.

pw_InlineVarLenEntryQueue_Entry pw_InlineVarLenEntryQueue_GetEntry(const pw_InlineVarLenEntryQueue_Iterator *iterator)#: Dereferences an iterator, loading the entry it points to.

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

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

Parameters:

entry – The entry whose contents to copy
dest – The buffer into which to copy the serialized entry
count – Copy up to this many bytes; must not be larger than the dest buffer, but may be larger than the entry

static inline uint8_t pw_InlineVarLenEntryQueue_Entry_At(const pw_InlineVarLenEntryQueue_Entry *entry, size_t index)#: Returns the byte at the specified index in the entry. Asserts if index is out-of-bounds.

uint32_t pw_InlineVarLenEntryQueue_Size(pw_InlineVarLenEntryQueue_ConstHandle queue)#: Returns the number of variable-length entries in the queue. This is O(n) in the number of entries in the queue.

static inline uint32_t pw_InlineVarLenEntryQueue_MaxSize(pw_InlineVarLenEntryQueue_ConstHandle queue)#: Returns the maximum number of entries in the queue. This is only attainable if all entries are empty.

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

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

static inline uint32_t pw_InlineVarLenEntryQueue_RawStorageSizeBytes(pw_InlineVarLenEntryQueue_ConstHandle queue)#: Returns the size of the raw underlying InlineVarLenEntryQueue storage. This size may be used to copy a InlineVarLenEntryQueue into another 32-bit aligned memory location.

static inline bool pw_InlineVarLenEntryQueue_Empty(pw_InlineVarLenEntryQueue_ConstHandle queue)#: Returns true if the InlineVarLenEntryQueue is empty, false if it has at least one entry.

PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(variable, max_size_bytes)#

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

Parameters:

variable – variable name for the queue
max_size_bytes – the capacity of the queue

PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32#

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

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

struct pw_InlineVarLenEntryQueue_Iterator#

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

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

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

Python#

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

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

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

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

pw::IntrusiveList#

pw::IntrusiveList provides an embedded-friendly, double-linked, intrusive list implementation. An intrusive list is a type of linked list that embeds list metadata, such as a “next” pointer, into the list object itself. This allows the construction of a linked list without the need to dynamically allocate list entries.

In C, an intrusive list can be made by manually including the “next” pointer as a member of the object’s struct. pw::IntrusiveList uses C++ features to simplify the process of creating an intrusive list. It provides classes that list elements can inherit from, protecting the list metadata from being accessed by the item class.

API Reference#

This class is similar to std::list<T>, except that the type of items to be added must derive from pw::IntrusiveList<T>::Item.

template<typename T> class IntrusiveList#

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.

Public Functions

inline T &front()#: Reference to the first element in the list. Undefined behavior if empty().

inline T &back()#: Reference to the last element in the list. Undefined behavior if empty().

inline constexpr size_type max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#: Removes all items from the list.

inline iterator insert(iterator pos, T &item)#: Inserts the given item before the given position, pos.

template<typename Iterator> inline iterator insert(iterator pos, Iterator first, Iterator last)#: Inserts the range of items from first (inclusive) to last (exclusive) before the given position, pos.

inline iterator insert(iterator pos, std::initializer_list<T*> items)#: Inserts the range of items from first (inclusive) to last (exclusive) before the given position, pos.

inline iterator erase(T &item)#: Removes the given item from the list. The item is not destructed.

inline iterator erase(iterator pos)#: Removes the item following pos from the list. The item is not destructed.

inline iterator erase(iterator first, iterator last)#: Removes the range of items from first (inclusive) to last (exclusive).

inline void push_back(T &item)#: Inserts an element at the end of the list.

inline void pop_back()#: Removes the last item in the list. The list must not be empty.

inline void push_front(T &item)#: Inserts an element at the beginning of the list.

inline void pop_front()#: Removes the first item in the list. The list must not be empty.

inline void swap(IntrusiveList<T> &other) noexcept#: Exchanges this list’s items with the other list’s items.

inline void merge(IntrusiveList<T> &other)#

Merges the given other list into this one.

After the call, the list will be sorted according to comp. The sort is stable, and equivalent items in each list will remain in the same order relative to each other.

This overload uses T::operator<.

template<typename Compare> inline void merge(IntrusiveList<T> &other, Compare comp)#

Merges the given other list into this one.

After the call, the list will be sorted according to comp. The sort is stable, and equivalent items in each list will remain in the same order relative to each other.

inline void splice(iterator pos, IntrusiveList<T> &other)#: Inserts the items of other to before pos in this list. Upon returning, other will be empty.

inline void splice(iterator pos, IntrusiveList<T> &other, iterator it)#: Moves the item pointed to by it from other to before pos in this list.

inline void splice(iterator pos, IntrusiveList<T> &other, iterator first, iterator last)#: Moves the items between first, inclusively, and last, exclusively from other to before pos in this list.

template<typename UnaryPredicate> inline size_type remove_if(UnaryPredicate pred)#

Removes any item for which the given unary predicate function p evaluates to true when passed that item.

Template Parameters:: UnaryPredicate – Function with the signature bool(const Item&)
Returns:: The number of items removed.

inline void reverse()#: Reverses the order of items in the list.

inline size_type unique()#

Removes consecutive ietms that are equivalent accroding to the given binary predicate p, leaving only the first item in the list.

This overload uses T::operator==.

Template Parameters:: BinaryPredicate – Function with the signature bool(const Item&, const Item&)

template<typename BinaryPredicate> inline size_type unique(BinaryPredicate pred)#

Removes consecutive ietms that are equivalent accroding to the given binary predicate p, leaving only the first item in the list.

Template Parameters:: BinaryPredicate – Function with the signature bool(const Item&, const Item&)

inline void sort()#

Rearranges the items in the list such that the given comparison function comp evaluates to true for each pair of successive items.

This overload uses T::operator<.

Template Parameters:: BinaryPredicate – Function with the signature bool(const Item&, const Item&)

template<typename Compare> inline void sort(Compare comp)#

Rearranges the items in the list such that the given comparison function comp evaluates to true for each pair of successive items.

Template Parameters:: BinaryPredicate – Function with the signature bool(const Item&, const Item&)

class Item : public ItemBase#: Subclassed by pw::allocator::SequencedItem, pw::allocator::test::TestHarness::Allocation, pw::multibuf::internal::LinkedRegionTracker

Note

Originally, pw::IntrusiveList<T> was implemented as a singly-linked list. To facilitate migration to pw::IntrusiveForwardList<T>::Item, this original implementation can still be temporarily used by enabling the PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST module configuration option.

Example#

using pw::containers::future::IntrusiveList;

class IntWrapper : public IntrusiveList<IntWrapper>::Item {
 public:
  IntWrapper(int value) : value_(value) {}
  int value() const { return value_; }

 private:
  const int value_;
};

// This example is adapted from https://en.cppreference.com/w/cpp/container/list
int CreateAndSum() {
  // Create a list containing integers
  std::array<IntWrapper, 4> wrappers = {{{6}, {7}, {3}, {0}}};
  IntrusiveList<IntWrapper> list(wrappers.begin(), wrappers.end());

  // Add an integer to the front of the list
  IntWrapper eight(8);
  list.push_front(eight);

  // Add an integer to the back of the list
  IntWrapper nine(9);
  list.push_back(nine);

  // Insert an integer before 3 by searching
  IntWrapper five(5);
  auto it = list.begin();
  while (it != list.end()) {
    if (it->value() == 3) {
      list.insert(it, five);
      break;
    }
    ++it;
  }

  // Sum the list
  int sum = 0;
  for (const auto& wrapper : list) {
    sum += wrapper.value();
  }

  // It is an error for items to go out of scope while still listed, or for a
  // list to go out of scope while it still has items.
  list.clear();

  return sum;
}

pw::IntrusiveForwardList#

pw::IntrusiveForwardList provides an embedded-friendly, singly-linked, intrusive list implementation. It is very similar to pw::IntrusiveList, except that is singly rather than doubly linked.

API Reference#

This class is similar to std::forward_list<T>. Items to be added must derive from pw::IntrusiveForwardList<T>::Item.

template<typename T> class IntrusiveForwardList#

A singly-list intrusive list.

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

As a singly-linked list, the overhead required is only sizeof(T*). However, operations such as removal may require O(n) time to walk the length of the list.

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

Since items are not allocated by this class, the following methods have no analogue:
- std::forward_list<T>::get_allocator
- std::forward_list<T>::emplace_after
- std::forward_list<T>::emplace_front
- std::forward_list<T>::resize
Methods corresponding to the following take initializer lists of pointer to items rather than the itenms themselves:
- std::forward_list<T>::(constructor)
- std::forward_list<T>::assign
- std::forward_list<T>::insert_after
There are no overloads corresponding to the following methods that take r-value references.:
- std::forward_list<T>::insert_after
- std::forward_list<T>::push_front
- std::forward_list<T>::splice_after
Since modifying the list modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
- std::forward_list<T>::insert_after
- std::forward_list<T>::erase_after
- std::forward_list<T>::splice_after
C++23 methods are not (yet) supported.

Template Parameters:: T – Type of intrusive items stored in the list.

Public Functions

template<typename Iterator> inline IntrusiveForwardList(Iterator first, Iterator last)#: Constructs a list from an iterator over items. The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

inline IntrusiveForwardList(std::initializer_list<Item*> items)#: Constructs a list from a std::initializer_list of pointers to items.

inline reference front()#: Reference to the first element in the list. Undefined behavior if empty().

inline iterator insert_after(iterator pos, T &item)#: Inserts the given item after the given position, pos.

template<typename Iterator> inline iterator insert_after(iterator pos, Iterator first, Iterator last)#: Inserts the range of items from first (inclusive) to last (exclusive) after the given position, pos.

inline iterator insert_after(iterator pos, std::initializer_list<T*> items)#: Inserts the range of items from first (inclusive) to last (exclusive) after the given position, pos.

inline iterator erase_after(iterator pos)#: Removes the item following pos from the list. The item is not destructed.

inline iterator erase_after(iterator first, iterator last)#: Removes the range of items from first (inclusive) to last (exclusive).

inline void push_front(T &item)#: Inserts the item at the start of the list.

inline void pop_front()#: Removes the first item in the list. The list must not be empty.

inline void merge(IntrusiveForwardList<T> &other)#: This overload uses T::operator<.

inline void splice_after(iterator pos, IntrusiveForwardList<T> &other)#: Inserts the items of other to after pos in this list. Upon returning, other will be empty.

inline void splice_after(iterator pos, IntrusiveForwardList<T> &other, iterator it)#: Moves the item pointed to by the iterator following it from other to after pos in this list.

inline void splice_after(iterator pos, IntrusiveForwardList<T> &other, iterator first, iterator last)#: Moves the items exclusively between first and last from other to after pos in this list.

inline size_type unique()#: This overload uses T::operator==.

inline void sort()#: This overload uses T::operator<.

class Item : public ItemBase#: Subclassed by pw::allocator::SortedItem, pw::allocator::UnorderedItem, pw::async2::TimeFuture< Clock >, pw::multibuf::MultiBufAllocationFuture

Example#

class Square : public pw::IntrusiveForwardList<Square>::Item {
 public:
  Square(size_t side_length) : side_length_(side_length) {}
  size_t Area() const { return side_length_ * side_length_; }

 private:
  size_t side_length_;
};

class SquareList {
 public:
  // These elements are not copied into the linked list, the original objects
  // are just chained together and can be accessed via `list_`.
  SquareList() : list_(squares_.begin(), squares_.end()) {}

  // It is an error for items to go out of scope while still listed, or for a
  // list to go out of scope while it still has items.
  ~SquareList() { list_.clear(); }

  // The list can be iterated over normally.
  size_t SumAreas() const {
    size_t sum = 0;
    for (const auto& square : list_) {
      sum += square.Area();
    }
    return sum;
  }

  // Like `std::forward_list`, an iterator is invalidated when the item it
  // refers to is removed. It is *NOT* safe to remove items from a list while
  // iterating over it in a range-based for loop.
  //
  // To remove items while iterating, use an iterator to the previous item. If
  // only removing items, consider using `remove_if` instead.
  size_t RemoveAndSumAreas(size_t area_to_remove) {
    size_t sum = 0;
    auto previous = list_.before_begin();
    auto current = list_.begin();
    while (current != list_.end()) {
      if (current->Area() == area_to_remove) {
        current = list_.erase_after(previous);
      } else {
        sum += current->Area();
        previous = current;
        ++current;
      }
    }
    return sum;
  }

 private:
  std::array<Square, 3> squares_ = {{{1}, {20}, {400}}};
  pw::IntrusiveForwardList<Square> list_;
};

Performance Considerations#

Items only include pointers to the next item. To reach previous items, the list maintains a cycle of items so that the first item can be reached from the last. This structure means certain operations have linear complexity in terms of the number of items in the list, i.e. they are “O(n)”:

Removing an item from a list using pw::IntrusiveForwardList<T>::remove(const T&).
Getting the list size using pw::IntrusiveForwardList<T>::size().

When using a pw::IntrusiveForwardList<T> in a performance critical section or with many items, authors should prefer to avoid these methods. For example, it may be preferable to create items that together with their storage outlive the list.

Notably, pw::IntrusiveForwardList<T>::end() is constant complexity (i.e. “O(1)”). As a result iterating over a list does not incur an additional penalty.

Size report#

Label

Segment

Delta

linked list one item

+48

linked list two item

+48

linked list four item

+48

intrusive list one item

+104

intrusive list two item

+112

intrusive list four item

+128

pw::IntrusiveSet#

pw::IntrusiveSet provides an embedded-friendly, tree-based, intrusive set implementation. The intrusive aspect of the set is very similar to that of pw::IntrusiveList.

API Reference#

This class is similar to std::set<T>. Items to be added must derive from pw::IntrusiveSet<T>::Item or an equivalent type.

template<typename T> class IntrusiveSet#

A std::set<Key, Compare>-like class that uses intrusive items as keys.

Since the set structure is stored in the items themselves, each item must outlive any set it is a part of and must be part of at most one set.

This set requires unique keys. Attempting to add an item with same key as an item already in the set will fail.

Since items are not allocated by this class, the following methods have no analogue:
- std::set<T>::operator=
- std::set<T>::operator[]
- std::set<T>::get_allocator
- std::set<T>::insert_or_assign
- std::set<T>::emplace
- std::set<T>::emplace_hint
- std::set<T>::try_emplace
Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:
- std::set<T>::(constructor)
- std::set<T>::insert
There are no overloads corresponding to the following methods that take r-value references.:
- std::set<T>::insert
- std::set<T>::merge
Since modifying the set modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
- std::set<T>::insert
- std::set<T>::erase
C++23 methods are not (yet) supported.

Template Parameters:: T – Type of data stored in the set.

Public Types

using Item = typename Tree::Item#: IntrusiveSet items must derive from Item.

Public Functions

inline explicit constexpr IntrusiveSet()#: Constructs an empty set of items.

template<typename Comparator> inline explicit constexpr IntrusiveSet(Comparator &&compare)#

Constructs an empty set of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters:: Compare – Function with the signature bool(T, T) that is used to order items.

template<typename Iterator, typename ...Functors> inline IntrusiveSet(Iterator first, Iterator last, Functors&&... functors)#

Constructs an IntrusiveSet from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

template<typename ...Functors> inline IntrusiveSet(std::initializer_list<T*> items, Functors&&... functors)#: Constructs an IntrusiveSet from a std::initializer_list of pointers to items.

inline bool empty() const noexcept#: Returns whether the set has zero items or not.

inline size_t size() const#: Returns the number of items in the set.

inline constexpr size_t max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#

Removes all items from the set and leaves it empty.

The items themselves are not destructed.

inline std::pair<iterator, bool> insert(T &item)#

Attempts to add the given item to the set.

The item will be added if the set does not already contain an equivalent item.

Returns:: A pointer to the inserted item and true, or a pointer to the equivalent item and false.

inline iterator erase(iterator pos)#

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

The items themselves are not destructed.

inline void swap(IntrusiveSet<T> &other)#: Exchanges this set’s items with the other set’s items.

template<typename MapType> inline void merge(MapType &other)#

Splices items from the other set into this one.

The receiving set’s Compare function is used when inserting items.

inline size_t count(const T &item) const#

Returns the number of equivalent items in the set.

Since the set requires unique keys, this is always 0 or 1.

inline iterator find(const T &item)#: Returns a pointer to an item with the given key, or null if the set does not contain such an item.

inline std::pair<iterator, iterator> equal_range(const T &item)#: Returns a pair of iterators where the first points to the smallest item that is not less than the given item, and the second points to the smallest item that is strictly greater than the given item.

inline iterator lower_bound(const T &item)#: Returns an iterator to the smallest item in the set that is greater than or equal to the given item, or end() if the set is empty.

inline iterator upper_bound(const T &item)#: Returns an iterator to the smallest item in the set that is strictly greater than the given item, or end() if the set is empty.

class const_iterator : public containers::internal::AATreeIterator<std::add_const_t<T>>#

class iterator : public containers::internal::AATreeIterator<T>#

Example#

class Book : public pw::IntrusiveSet<Book>::Item {
 private:
  using Item = pw::IntrusiveSet<Book>::Item;

 public:
  explicit Book(const char* name) : name_(name) {}
  const char* name() const { return name_; }
  bool operator<(const Book& rhs) const {
    return strcmp(name_, rhs.name()) < 0;
  }

 private:
  const char* name_;
};

std::array<Book, 8> books = {
    Book("A Tale of Two Cities"),
    Book("The Little Prince"),
    Book("The Alchemist"),
    Book("Harry Potter and the Philosopher's Stone"),
    Book("And Then There Were None"),
    Book("Dream of the Red Chamber"),
    Book("The Hobbit"),
    Book("Alice's Adventures in Wonderland"),
};

pw::IntrusiveSet<Book> library(books.begin(), books.end());

void VisitLibrary(pw::IntrusiveSet<Book>& book_bag) {
  // Return any books we previously checked out.
  library.merge(book_bag);

  // Pick out some new books to read to the kids, but only if they're available.
  std::array<const char*, 3> titles = {
      "The Hobbit",
      "Curious George",
      "Harry Potter and the Philosopher's Stone",
  };
  for (const char* title : titles) {
    Book requested(title);
    auto iter = library.find(requested);
    if (iter != library.end()) {
      Book& book = *iter;
      library.erase(iter);
      book_bag.insert(book);
    }
  }
}

pw::IntrusiveMultiSet#

pw::IntrusiveMultiSet provides an embedded-friendly, tree-based, intrusive multiset implementation. This is very similar to pw::IntrusiveSet, except that the tree may contain multiple items with equivalent keys.

API Reference#

This class is similar to std::multiset<T>. Items to be added must derive from pw::IntrusiveMultiSet<T>::Item or an equivalent type.

template<typename T> class IntrusiveMultiSet#

A std::multiset<Key, Compare>-like class that uses intrusive items.

Since the set structure is stored in the items themselves, each item must outlive any set it is a part of and must be part of at most one set.

This set does not require unique keys. Multiple equivalent items may be added.

Since items are not allocated by this class, the following methods have no analogue:
- std::multiset<T>::operator=
- std::multiset<T>::get_allocator
- std::multiset<T>::emplace
- std::multiset<T>::emplace_hint
Methods corresponding to the following take initializer lists of pointer to items rather than the items themselves:
- std::multiset<T>::(constructor)
- std::multiset<T>::insert
There are no overloads corresponding to the following methods that take r-value references.:
- std::multiset<T>::insert
- std::multiset<T>::merge
Since modifying the set modifies the items themselves, methods corresponding to those below only take iterators and not const_iterators:
- std::multiset<T>::insert
- std::multiset<T>::erase
C++23 methods are not (yet) supported.

Template Parameters:: T – Type of items stored in the set.

Public Types

using Item = typename Tree::Item#: IntrusiveMultiSet items must derive from Item.

Public Functions

inline explicit constexpr IntrusiveMultiSet()#: Constructs an empty set of items.

template<typename Comparator> inline explicit constexpr IntrusiveMultiSet(Comparator &&compare)#

Constructs an empty set of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters:: Compare – Function with the signature bool(T, T) that is used to order items.

template<typename Iterator, typename ...Functors> inline IntrusiveMultiSet( Iterator first, Iterator last, Functors&&... functors, )#

Constructs an IntrusiveMultiSet from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

template<typename ...Functors> inline IntrusiveMultiSet(std::initializer_list<T*> items, Functors&&... functors)#: Constructs an IntrusiveMultiSet from a std::initializer_list of pointers to items.

inline bool empty() const noexcept#: Returns whether the multiset has zero items or not.

inline size_t size() const#: Returns the number of items in the multiset.

inline constexpr size_t max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#

Removes all items from the multiset and leaves it empty.

The items themselves are not destructed.

inline iterator insert(T &item)#: Adds the given item to the multiset.

inline iterator erase(iterator pos)#

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

The items themselves are not destructed.

inline void swap(IntrusiveMultiSet<T> &other)#: Exchanges this multiset’s items with the other multiset’s items.

template<typename MapType> inline void merge(MapType &other)#

Splices items from the other set into this one.

The receiving set’s Compare function is used when inserting items.

inline size_t count(const T &item) const#: Returns the number of items in the multimap with the given key.

inline iterator find(const T &item)#: Returns a pointer to an item with the given key, or null if the multimap does not contain such an item.

inline std::pair<iterator, iterator> equal_range(const T &item)#: Returns a pair of iterators 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.

inline iterator lower_bound(const T &item)#: Returns an iterator to the item in the multimap with the smallest key that is greater than or equal to the given key, or end() if the multimap is empty.

inline iterator upper_bound(const T &item)#: Returns an iterator to the item in the multimap with the smallest key that is strictly greater than the given key, or end() if the multimap is empty.

class const_iterator : public containers::internal::AATreeIterator<std::add_const_t<T>>#

class iterator : public containers::internal::AATreeIterator<T>#

Example#

class Book : public pw::IntrusiveMultiSet<Book>::Item {
 private:
  using Item = pw::IntrusiveMultiSet<Book>::Item;

 public:
  explicit Book(const char* name) : name_(name) {}
  const char* name() const { return name_; }
  bool operator<(const Book& rhs) const {
    return strcmp(name_, rhs.name()) < 0;
  }

 private:
  const char* name_;
};

std::array<Book, 12> books = {
    Book("The Little Prince"),
    Book("Harry Potter and the Philosopher's Stone"),
    Book("Harry Potter and the Philosopher's Stone"),
    Book("Harry Potter and the Philosopher's Stone"),
    Book("Harry Potter and the Philosopher's Stone"),
    Book("Harry Potter and the Philosopher's Stone"),
    Book("The Hobbit"),
    Book("The Hobbit"),
    Book("The Hobbit"),
    Book("The Hobbit"),
    Book("Alice's Adventures in Wonderland"),
    Book("Alice's Adventures in Wonderland"),
};
pw::IntrusiveMultiSet<Book> library(books.begin(), books.end());

void VisitLibrary(pw::IntrusiveMultiSet<Book>& book_bag) {
  // Pick out some new books to read to the kids, but only if they're available.
  std::array<const char*, 3> titles = {
      "The Hobbit",
      "Alice's Adventures in Wonderland",
      "The Little Prince",
  };
  for (const char* title : titles) {
    Book requested(title);
    auto iter = library.find(requested);
    if (iter != library.end()) {
      Book& book = *iter;
      library.erase(iter);
      book_bag.insert(book);
    }
  }
}

pw::IntrusiveMap#

pw::IntrusiveMap provides an embedded-friendly, tree-based, intrusive map implementation. The intrusive aspect of the map is very similar to that of pw::IntrusiveList.

API Reference#

This class is similar to std::map<K, V>. Items to be added must derive from pw::IntrusiveMap<K, V>::Item or an equivalent type.

template<typename Key, typename T> class IntrusiveMap#

A std::map<Key, T, Compare>-like class that uses intrusive items.

Since the map structure is stored in the items themselves, each item must outlive any map it is a part of and must be part of at most one map.

This map requires unique keys. Attempting to add an item with same key as an item already in the map will fail.

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

Template Parameters:

Key – Type to sort items on
T – Type of values stored in the map.

Public Types

using Item = typename Tree::Item#: IntrusiveMap items must derive from either Item or Pair. Use Pair to automatically provide storage for a Key. Use Item when the derived type has a key() accessor method or when the map provides a custom GetKey function object.

Public Functions

inline explicit constexpr IntrusiveMap()#: Constructs an empty map of items.

template<typename Comparator> inline explicit constexpr IntrusiveMap(Comparator &&compare)#

Constructs an empty map of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters:: compare – Function with the signature bool(Key, Key) that is used to order items.

template<typename Comparator, typename KeyRetriever> inline constexpr IntrusiveMap(Comparator &&compare, KeyRetriever &&get_key)#

Constructs an empty map of items.

Parameters:

compare – Function with the signature bool(Key, Key) that is used to order items.
get_key – Function with signature Key(const T&) that returns the value that items are sorted on.

template<typename Iterator, typename ...Functors> inline IntrusiveMap(Iterator first, Iterator last, Functors&&... functors)#

Constructs an IntrusiveMap from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

template<typename ...Functors> inline explicit IntrusiveMap(std::initializer_list<T*> items, Functors&&... functors)#: Constructs an IntrusiveMap from a std::initializer_list of pointers to items.

inline T &at(const key_type &key)#

Returns a reference to the item associated with the given key.

Pre:: The map must contain an item associated with the key.

inline bool empty() const noexcept#: Returns whether the map has zero items or not.

inline size_t size() const#: Returns the number of items in the map.

inline constexpr size_t max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#

Removes all items from the map and leaves it empty.

The items themselves are not destructed.

inline std::pair<iterator, bool> insert(T &item)#

Attempts to add the given item to the map.

The item will be added if the map does not already contain an item with the given item’s key.

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

inline iterator erase(T &item)#

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

The items themselves are not destructed.

inline void swap(IntrusiveMap<Key, T> &other)#: Exchanges this map’s items with the other map’s items.

template<typename MapType> inline void merge(MapType &other)#: Splices items from the other map into this one.

inline size_t count(const key_type &key) const#

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

Since the map requires unique keys, this is always 0 or 1.

inline iterator find(const key_type &key)#: Returns a pointer to an item with the given key, or null if the map does not contain such an item.

inline std::pair<iterator, iterator> equal_range(const key_type &key)#: Returns a pair of iterators 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.

inline iterator lower_bound(const key_type &key)#: Returns an iterator to the item in the map with the smallest key that is greater than or equal to the given key, or end() if the map is empty.

inline iterator upper_bound(const key_type &key)#: Returns an iterator to the item in the map with the smallest key that is strictly greater than the given key, or end() if the map is empty.

class const_iterator : public containers::internal::AATreeIterator<std::add_const_t<T>>#

class iterator : public containers::internal::AATreeIterator<T>#

Example#

struct Book : public pw::IntrusiveMap<uint32_t, Book>::Pair {
 private:
  using Pair = pw::IntrusiveMap<uint32_t, Book>::Pair;

 public:
  Book(const char* name, uint32_t oclc) : Pair(oclc), name_(name) {}
  const char* name() const { return name_; }

 private:
  const char* name_;
};

std::array<Book, 8> books = {{
    {"A Tale of Two Cities", 20848014u},
    {"The Little Prince", 182537909u},
    {"The Alchemist", 26857452u},
    {"Harry Potter and the Philosopher's Stone", 44795766u},
    {"And Then There Were None", 47032439u},
    {"Dream of the Red Chamber", 20692970u},
    {"The Hobbit", 1827184u},
    {"Alice's Adventures in Wonderland", 5635965u},
}};

pw::IntrusiveMap<uint32_t, Book> library(books.begin(), books.end());

void VisitLibrary(pw::IntrusiveMap<uint32_t, Book>& book_bag) {
  // Return any books we previously checked out.
  library.merge(book_bag);

  // Pick out some new books to read to the kids, but only if they're available.
  std::array<uint32_t, 3> oclcs = {
      1827184u,   // The Hobbit
      11914189u,  // Curious George
      44795766u,  // Harry Potter
  };
  for (uint32_t oclc : oclcs) {
    auto iter = library.find(oclc);
    if (iter != library.end()) {
      Book& book = *iter;
      library.erase(iter);
      book_bag.insert(book);
    }
  }
}

pw::IntrusiveMultiMap#

pw::IntrusiveMultiMap provides an embedded-friendly, tree-based, intrusive multimap implementation. This is very similar to pw::IntrusiveMap, except that the tree may contain multiple items with equivalent keys.

API Reference#

This class is similar to std::multimap<K, V>. Items to be added must derive from pw::IntrusiveMultiMap<K, V>::Item or an equivalent type.

template<typename Key, typename T> class IntrusiveMultiMap#

A std::multimap<Key, T, Compare>-like class that uses intrusive items.

Since the map structure is stored in the items themselves, each item must outlive any map it is a part of and must be part of at most one map.

This map requires unique keys. Attempting to add an item with same key as an item already in the map will fail.

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

Template Parameters:

Key – Type to sort items on
T – Type of values stored in the map.

Public Types

using Item = typename Tree::Item#: IntrusiveMultiMap items must derive from either Item or Pair. Use Pair to automatically provide storage for a Key. Use Item when the derived type has a key() accessor method or when the map provides a custom GetKey function object.

Public Functions

inline explicit constexpr IntrusiveMultiMap()#: Constructs an empty map of items.

template<typename Comparator> inline explicit constexpr IntrusiveMultiMap(Comparator &&compare)#

Constructs an empty map of items.

SFINAE is used to disambiguate between this constructor and the one that takes an initializer list.

Parameters:

compare – Function with the signature bool(Key, Key) that is used to order items.
get_key – Function with signature Key(const T&) that returns the value that items are sorted on.

template<typename Comparator, typename KeyRetriever> inline constexpr IntrusiveMultiMap( Comparator &&compare, KeyRetriever &&get_key, )#

Constructs an empty map of items.

Parameters:

compare – Function with the signature bool(Key, Key) that is used to order items.
get_key – Function with signature Key(const T&) that returns the value that items are sorted on.

template<typename Iterator, typename ...Functors> inline IntrusiveMultiMap( Iterator first, Iterator last, Functors&&... functors, )#

Constructs an IntrusiveMultiMap from an iterator over Items.

The iterator may dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. from std::initializer_list<Item*>).

template<typename ...Functors> inline IntrusiveMultiMap(std::initializer_list<T*> items, Functors&&... functors)#: Constructs an IntrusiveMultiMap from a std::initializer_list of pointers to items.

inline bool empty() const noexcept#: Returns whether the multimap has zero items or not.

inline size_t size() const#: Returns the number of items in the multimap.

inline constexpr size_t max_size() const noexcept#

Returns how many items can be added.

As an intrusive container, this is effectively unbounded.

inline void clear()#

Removes all items from the multimap and leaves it empty.

The items themselves are not destructed.

inline iterator insert(T &item)#: Adds the given item to the multimap.

inline iterator erase(T &item)#

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

The items themselves are not destructed.

inline void swap(IntrusiveMultiMap<Key, T> &other)#: Exchanges this multimap’s items with the other multimap’s items.

template<typename MapType> inline void merge(MapType &other)#: Splices items from the other map into this one.

inline size_t count(const Key &key) const#: Returns the number of items in the multimap with the given key.

inline iterator find(const Key &key)#: Returns a pointer to an item with the given key, or null if the multimap does not contain such an item.

inline std::pair<iterator, iterator> equal_range(const Key &key)#: Returns a pair of iterators 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.

inline iterator lower_bound(const Key &key)#: Returns an iterator to the item in the multimap with the smallest key that is greater than or equal to the given key, or end() if the multimap is empty.

inline iterator upper_bound(const Key &key)#: Returns an iterator to the item in the multimap with the smallest key that is strictly greater than the given key, or end() if the multimap is empty.

class const_iterator : public containers::internal::AATreeIterator<std::add_const_t<T>>#

class iterator : public containers::internal::AATreeIterator<T>#

Example#

struct Book : public pw::IntrusiveMultiMap<uint32_t, Book>::Pair {
 private:
  using Pair = pw::IntrusiveMultiMap<uint32_t, Book>::Pair;

 public:
  Book(const char* name, uint32_t oclc) : Pair(oclc), name_(name) {}
  const char* name() const { return name_; }

 private:
  const char* name_;
};

std::array<Book, 12> books = {{
    {"The Little Prince", 182537909u},
    {"Harry Potter and the Philosopher's Stone", 44795766u},
    {"Harry Potter and the Philosopher's Stone", 44795766u},
    {"Harry Potter and the Philosopher's Stone", 44795766u},
    {"Harry Potter and the Philosopher's Stone", 44795766u},
    {"Harry Potter and the Philosopher's Stone", 44795766u},
    {"The Hobbit", 1827184u},
    {"The Hobbit", 1827184u},
    {"The Hobbit", 1827184u},
    {"The Hobbit", 1827184u},
    {"Alice's Adventures in Wonderland", 5635965u},
    {"Alice's Adventures in Wonderland", 5635965u},
}};
pw::IntrusiveMultiMap<uint32_t, Book> library(books.begin(), books.end());

void VisitLibrary(pw::IntrusiveMultiMap<uint32_t, Book>& book_bag) {
  // Pick out some new books to read to the kids, but only if they're available.
  std::array<uint32_t, 3> oclcs = {
      1827184u,    // The Hobbit
      5635965u,    // Alice's Adventures in Wonderland
      182537909u,  // The Little Prince
  };
  for (uint32_t oclc : oclcs) {
    auto iter = library.find(oclc);
    if (iter != library.end()) {
      Book& book = *iter;
      library.erase(iter);
      book_bag.insert(book);
    }
  }
}

Using items with multiple containers#

Intrusive items may be used with multiple containers, provided each of those containers is templated on a type that is not derived from any of the others. This can be achieved by multiply inheriting from distinct type:

// The base type for lists can be trivially derived.
struct ListItem : public pw::containers::future::IntrusiveList<ListItem>::Item {
};

// The base type for maps needs a constructor.
struct MapPair : public pw::IntrusiveMap<const uint32_t&, MapPair>::Pair {
  constexpr MapPair(const uint32_t& id)
      : pw::IntrusiveMap<const uint32_t&, MapPair>::Pair(id) {}
};

struct Task : public ListItem, public MapPair {
  uint32_t id = 0;
  constexpr explicit Task() : MapPair(id) {}
};

namespace examples {

class Scheduler {
 public:
  // Adds a task to the queue, and returns an opaque `id` that identifies it.
  // Returns INVALID_ARGUMENT the task is already in the queue.
  pw::Result<uint32_t> ScheduleTask(Task& task) {
    if (task.id != 0) {
      return pw::Status::InvalidArgument();
    }
    task.id = ++num_ids_;
    by_id_.insert(task);
    queue_.push_back(task);
    return task.id;
  }

  // Removes a task associated with a given `id` from the queue.
  // Returns NOT_FOUND if the task is not in the queue.
  pw::Status CancelTask(uint32_t id) {
    auto iter = by_id_.find(id);
    if (iter == by_id_.end()) {
      return pw::Status::NotFound();
    }
    auto& task = static_cast<Task&>(*iter);
    by_id_.erase(iter);
    queue_.remove(task);
    task.id = 0;
    return pw::OkStatus();
  }

  // Runs the next task, if any, and returns its `id`.
  // Returns NOT_FOUND if the queue is empty.
  pw::Result<uint32_t> RunTask() {
    if (queue_.empty()) {
      return pw::Status::NotFound();
    }
    auto& task = static_cast<Task&>(queue_.front());
    queue_.pop_front();
    by_id_.erase(task.id);
    return task.id;
  }

 private:
  // NOTE! The containers must be templated on their specific item types, not
  // the composite `Task` type.
  pw::containers::future::IntrusiveList<ListItem> queue_;
  pw::IntrusiveMap<uint32_t, MapPair> by_id_;
  uint32_t num_ids_ = 0;
};

If one or more types is derived from another, the compiler will fail to build with an error that ItemType is ambiguous or found in multiple base classes.

pw::containers::FlatMap#

FlatMap provides a simple, fixed-size associative array with O(log n) lookup by key.

pw::containers::FlatMap contains the same methods and features for looking up data as std::map. However, modification of the underlying data is limited to the mapped values, via .at() (key must exist) and mapped_iterator objects returned by .mapped_begin() and .mapped_end(). mapped_iterator objects are bidirectional iterators that can be dereferenced to access and mutate the mapped value objects.

The underlying array in pw::containers::FlatMap does not need to be sorted. During construction, pw::containers::FlatMap will perform a constexpr insertion sort.

A FlatMap can be created in one of several ways. Each of the following examples defines a FlatMap with two items.

using pw::containers::FlatMap;
using pw::containers::Pair;

// Initialized by an initializer list.
FlatMap<int, char, 2> my_flat_map1({{
    {1, 'a'},
    {-3, 'b'},
}});

// Initialized by a std::array of Pair<K, V> objects.
std::array<Pair<int, char>, 2> my_array{{
    {1, 'a'},
    {-3, 'b'},
}};
FlatMap my_flat_map2(my_array);

// Initialized by Pair<K, V> objects.
FlatMap my_flat_map3 = {
    Pair<int, char>{1, 'a'},
    Pair<int, char>{-3, 'b'},
};

pw::containers::FilteredView#

template<typename Container, typename Filter> class FilteredView#

pw::containers::FilteredView provides a view of a container with only elements that match the specified filter. This class is similar to C++20’s std::ranges::filter_view.

FilteredView works with any container with an incrementable iterator. The back() function currently requires a bidirectional iterator.

To create a FilteredView, pass a container and a filter predicate, which may be any callable type including a function pointer, lambda, or pw::Function.

std::array<int, 99> kNumbers = {3, 1, 4, 1, ...};

for (int n : FilteredView(kNumbers, [](int v) { return v % 2 == 0; })) {
  PW_LOG_INFO("This number is even: %d", n);
}

pw::containers::WrappedIterator#

pw::containers::WrappedIterator is a class that makes it easy to wrap an existing iterator type. It reduces boilerplate by providing operator++, operator--, operator==, operator!=, and the standard iterator aliases (difference_type, value_type, etc.). It does not provide the dereference operator; that must be supplied by a derived class.

To use it, create a class that derives from WrappedIterator and define operator*() and operator->() as appropriate. The new iterator might apply a transformation to or access a member of the values provided by the original iterator. The following example defines an iterator that multiplies the values in an array by 2.

using pw::containers::WrappedIterator;

// Multiplies values in a std::array by two.
class DoubleIterator : public WrappedIterator<DoubleIterator, const int*, int> {
 public:
  constexpr DoubleIterator(const int* it) : WrappedIterator(it) {}
  int operator*() const { return value() * 2; }
};

// Returns twice the sum of the elements in a array of integers.
template <size_t kArraySize>
int DoubleSum(const std::array<int, kArraySize>& c) {
  int sum = 0;
  for (DoubleIterator it(c.data()); it != DoubleIterator(c.data() + c.size());
       ++it) {
    // The iterator yields doubles instead of the original values.
    sum += *it;
  }
  return sum;
}

WrappedIterator may be used in concert with FilteredView to create a view that iterates over a matching values in a container and applies a transformation to the values. For example, it could be used with FilteredView to filter a list of packets and yield only one field from the packet.

The combination of FilteredView and WrappedIterator provides some basic functional programming features similar to (though much more cumbersome than) generator expressions (or filter/map) in Python or streams in Java 8. WrappedIterator and FilteredView require no memory allocation, which is helpful when memory is too constrained to process the items into a new container.

pw::containers::to_array#

pw::containers::to_array is a C++14-compatible implementation of C++20’s std::to_array. In C++20, it is an alias for std::to_array. It converts a C array to a std::array.

pw_containers/algorithm.h#

Pigweed provides a set of Container-based versions of algorithmic functions within the C++ standard library, based on a subset of absl/algorithm/container.h.

bool pw::containers::AllOf()#: Container-based version of the <algorithm> std::all_of() function to test if all elements within a container satisfy a condition.

bool pw::containers::AnyOf()#: Container-based version of the <algorithm> std::any_of() function to test if any element in a container fulfills a condition.

bool pw::containers::NoneOf()#: Container-based version of the <algorithm> std::none_of() function to test if no elements in a container fulfill a condition.

pw::containers::ForEach()#: Container-based version of the <algorithm> std::for_each() function to apply a function to a container’s elements.

pw::containers::Find()#: Container-based version of the <algorithm> std::find() function to find the first element containing the passed value within a container value.

pw::containers::FindIf()#: Container-based version of the <algorithm> std::find_if() function to find the first element in a container matching the given condition.

pw::containers::FindIfNot()#: Container-based version of the <algorithm> std::find_if_not() function to find the first element in a container not matching the given condition.

pw::containers::FindEnd()#: Container-based version of the <algorithm> std::find_end() function to find the last subsequence within a container.

pw::containers::FindFirstOf()#: Container-based version of the <algorithm> std::find_first_of() function to find the first element within the container that is also within the options container.

pw::containers::AdjacentFind()#: Container-based version of the <algorithm> std::adjacent_find() function to find equal adjacent elements within a container.

pw::containers::Count()#: Container-based version of the <algorithm> std::count() function to count values that match within a container.

pw::containers::CountIf()#: Container-based version of the <algorithm> std::count_if() function to count values matching a condition within a container.

pw::containers::Mismatch()#: Container-based version of the <algorithm> std::mismatch() function to return the first element where two ordered containers differ. Applies == to the first N elements of c1 and c2, where N = min(size(c1), size(c2)). the function’s test condition. Applies pred to the first N elements of c1 and c2, where N = min(size(c1), size(c2)).

bool pw::containers::Equal()#: Container-based version of the <algorithm> std::equal() function to test whether two containers are equal.

Note

The semantics of Equal() are slightly different than those of std::equal(): while the latter iterates over the second container only up to the size of the first container, Equal() also checks whether the container sizes are equal. This better matches expectations about Equal() based on its signature.

bool pw::containers::IsPermutation()#: Container-based version of the <algorithm> std::is_permutation() function to test whether a container is a permutation of another.

pw::containers::Search()#: Container-based version of the <algorithm> std::search() function to search a container for a subsequence.

pw::containers::SearchN()#: Container-based version of the <algorithm> std::search_n() function to search a container for the first sequence of N elements.

Compatibility#

C++17

Zephyr#

To enable pw_containers for Zephyr add CONFIG_PIGWEED_CONTAINERS=y to the project’s configuration.