Lists#

pw_containers: Generic collections of objects for embedded devices

A linked list is an ordered collection of items in which each item is associated with pointers to one or more of its adjacent items. Pigweed provides intrusive lists, meaning the pointers are stored within the items themselves. This allows an arbitrary number of items to be added to a list without requiring additional memory beyond that of the items themselves.

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.

See also Using items with multiple containers.

Example#

 1using pw::containers::future::IntrusiveList;
 2
 3class IntWrapper : public IntrusiveList<IntWrapper>::Item {
 4 public:
 5  IntWrapper(int value) : value_(value) {}
 6  int value() const { return value_; }
 7
 8 private:
 9  const int value_;
10};
11
12// This example is adapted from https://en.cppreference.com/w/cpp/container/list
13int CreateAndSum() {
14  // Create a list containing integers
15  std::array<IntWrapper, 4> wrappers = {{{6}, {7}, {3}, {0}}};
16  IntrusiveList<IntWrapper> list(wrappers.begin(), wrappers.end());
17
18  // Add an integer to the front of the list
19  IntWrapper eight(8);
20  list.push_front(eight);
21
22  // Add an integer to the back of the list
23  IntWrapper nine(9);
24  list.push_back(nine);
25
26  // Insert an integer before 3 by searching
27  IntWrapper five(5);
28  auto it = list.begin();
29  while (it != list.end()) {
30    if (it->value() == 3) {
31      list.insert(it, five);
32      break;
33    }
34    ++it;
35  }
36
37  // Sum the list
38  int sum = 0;
39  for (const auto& wrapper : list) {
40    sum += wrapper.value();
41  }
42
43  // It is an error for items to go out of scope while still listed, or for a
44  // list to go out of scope while it still has items.
45  list.clear();
46
47  return sum;
48}

If you need to add this item to containers of more than one type, see Using items with multiple containers,

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

IntrusiveList(IntrusiveList&&) = default#

Clears this list and moves the other list’s contents into it.

This is O(1).

IntrusiveList &operator=(IntrusiveList&&) = default#

Clears this list and moves the other list’s contents into it.

This is O(1).

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.

This is O(1).

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.

pw::IntrusiveForwardList#

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

See also Using items with multiple containers.

Example#

 1class Square : public pw::IntrusiveForwardList<Square>::Item {
 2 public:
 3  Square(size_t side_length) : side_length_(side_length) {}
 4  size_t Area() const { return side_length_ * side_length_; }
 5
 6 private:
 7  size_t side_length_;
 8};
 9
10class SquareList {
11 public:
12  // These elements are not copied into the linked list, the original objects
13  // are just chained together and can be accessed via `list_`.
14  SquareList() : list_(squares_.begin(), squares_.end()) {}
15
16  // It is an error for items to go out of scope while still listed, or for a
17  // list to go out of scope while it still has items.
18  ~SquareList() { list_.clear(); }
19
20  // The list can be iterated over normally.
21  size_t SumAreas() const {
22    size_t sum = 0;
23    for (const auto& square : list_) {
24      sum += square.Area();
25    }
26    return sum;
27  }
28
29  // Like `std::forward_list`, an iterator is invalidated when the item it
30  // refers to is removed. It is *NOT* safe to remove items from a list while
31  // iterating over it in a range-based for loop.
32  //
33  // To remove items while iterating, use an iterator to the previous item. If
34  // only removing items, consider using `remove_if` instead.
35  size_t RemoveAndSumAreas(size_t area_to_remove) {
36    size_t sum = 0;
37    auto previous = list_.before_begin();
38    auto current = list_.begin();
39    while (current != list_.end()) {
40      if (current->Area() == area_to_remove) {
41        current = list_.erase_after(previous);
42      } else {
43        sum += current->Area();
44        previous = current;
45        ++current;
46      }
47    }
48    return sum;
49  }
50
51 private:
52  std::array<Square, 3> squares_ = {{{1}, {20}, {400}}};
53  pw::IntrusiveForwardList<Square> list_;
54};

If you need to add this item to containers of more than one type, see Using items with multiple containers,

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

IntrusiveForwardList(IntrusiveForwardList&&) = default#

Moves the other list’s contents into this list.

This is O(n).

IntrusiveForwardList &operator=(IntrusiveForwardList&&) = default#

Clears this list and moves the other list’s contents into it.

This is O(n).

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 swap(IntrusiveForwardList<T> &other) noexcept#

Exchanges this list’s items with the other list’s items.

This is O(n), where “n” is the number of items in the range.

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::digital_io::McuxpressoDigitalInOutInterrupt

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 reports#

The tables below illustrate the following scenarios:

  • Scenarios related to IntrusiveList:

    • The memory and code size cost incurred by a adding a single IntrusiveList.

    • The memory and code size cost incurred by adding another IntrusiveList with a different type. As IntrusiveList is templated on type, this results in additional code being generated.

  • Scenarios related to IntrusiveForwardList:

    • The memory and code size cost incurred by a adding a single IntrusiveForwardList.

    • The memory and code size cost incurred by adding another IntrusiveForwardList with a different type. As IntrusiveForwardList is templated on type, this results in additional code being generated.

  • The memory and code size cost incurred by a adding both an IntrusiveList and an IntrusiveForwardList of the same type. These types reuse code, so the combined sum is less than the sum of its parts.

Note

The size report that is usually displayed here is temporarily unavailable while we migrate the pigweed.dev build system from GN to Bazel. See b/388905812 for updates.

On this page