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.
This class is similar to std::list<T>, except that the type of items to be
added must derive from pw::IntrusiveList<T>::Item.
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.
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.
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,
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.
This class is similar to std::forward_list<T>. Items to be added must derive
from pw::IntrusiveForwardList<T>::Item.
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#
Moved: pw_containers_lists
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
IntrusiveListwith a different type. AsIntrusiveListis 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
IntrusiveForwardListwith a different type. AsIntrusiveForwardListis templated on type, this results in additional code being generated.
The memory and code size cost incurred by a adding both an
IntrusiveListand anIntrusiveForwardListof the same type. These types reuse code, so the combined sum is less than the sum of its parts.
Label |
Segment |
Delta |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
IntrusiveList |
FLASH
|
+1,160 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+128 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveList with different item type |
FLASH
|
+816 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+176 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveForwardList |
FLASH
|
+1,000 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+96 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Additional IntrusiveForwardList with different item type |
FLASH
|
+592 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+160 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IntrusiveForwardList and IntrusiveList |
FLASH
|
+2,056 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
RAM
|
+224 |