Wyatt Hepler | f9fb90f | 2020-09-30 18:59:33 -0700 | [diff] [blame] | 1 | .. _module-pw_containers: |
Wyatt Hepler | 3c4e5de | 2020-03-03 14:37:52 -0800 | [diff] [blame] | 2 | |
| 3 | ------------- |
| 4 | pw_containers |
| 5 | ------------- |
Armando Montanez | 0054a9b | 2020-03-13 13:06:24 -0700 | [diff] [blame] | 6 | The ``pw_containers`` module provides embedded-friendly container classes. |
Wyatt Hepler | 3c4e5de | 2020-03-03 14:37:52 -0800 | [diff] [blame] | 7 | |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 8 | pw::Vector |
| 9 | ========== |
| 10 | The Vector class is similar to ``std::vector``, except it is backed by a |
Wyatt Hepler | 3c4e5de | 2020-03-03 14:37:52 -0800 | [diff] [blame] | 11 | fixed-size buffer. Vectors must be declared with an explicit maximum size |
| 12 | (e.g. ``Vector<int, 10>``) but vectors can be used and referred to without the |
| 13 | max size template parameter (e.g. ``Vector<int>``). |
| 14 | |
| 15 | To allow referring to a ``pw::Vector`` without an explicit maximum size, all |
| 16 | Vector classes inherit from the generic ``Vector<T>``, which stores the maximum |
| 17 | size in a variable. This allows Vectors to be used without having to know |
| 18 | their maximum size at compile time. It also keeps code size small since |
| 19 | function implementations are shared for all maximum sizes. |
| 20 | |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 21 | pw::IntrusiveList |
| 22 | ================= |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 23 | IntrusiveList provides an embedded-friendly singly-linked intrusive list |
| 24 | implementation. An intrusive list is a type of linked list that embeds the |
| 25 | "next" pointer into the list object itself. This allows the construction of a |
| 26 | linked list without the need to dynamically allocate list entries. |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 27 | |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 28 | In C, an intrusive list can be made by manually including the "next" pointer as |
| 29 | a member of the object's struct. ``pw::IntrusiveList`` uses C++ features to |
| 30 | simplify the process of creating an intrusive list. ``pw::IntrusiveList`` |
| 31 | provides a class that list elements can inherit from. This protects the "next" |
| 32 | pointer from being accessed by the item class, so only the ``pw::IntrusiveList`` |
| 33 | class can modify the list. |
Kevin Zeng | b0bb849 | 2021-01-11 21:32:24 -0800 | [diff] [blame] | 34 | |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 35 | Usage |
| 36 | ----- |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 37 | While the API of ``pw::IntrusiveList`` is similar to a ``std::forward_list``, |
| 38 | there are extra steps to creating objects that can be stored in this data |
| 39 | structure. Objects that will be added to a ``IntrusiveList<T>`` must inherit |
| 40 | from ``IntrusiveList<T>::Item``. They can inherit directly from it or inherit |
| 41 | from it through another base class. When an item is instantiated and added to a |
| 42 | linked list, the pointer to the object is added to the "next" pointer of |
| 43 | whichever object is the current tail. |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 44 | |
| 45 | That means two key things: |
| 46 | |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 47 | - An instantiated ``IntrusiveList<T>::Item`` must remain in scope for the |
| 48 | lifetime of the ``IntrusiveList`` it has been added to. |
| 49 | - A linked list item CANNOT be included in two lists. Attempting to do so |
| 50 | results in an assert failure. |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 51 | |
| 52 | .. code-block:: cpp |
| 53 | |
| 54 | class Square |
Prashanth Swaminathan | 6573187 | 2021-02-11 08:51:08 -0800 | [diff] [blame] | 55 | : public pw::IntrusiveList<Square>::Item { |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 56 | public: |
| 57 | Square(unsigned int side_length) : side_length(side_length) {} |
| 58 | unsigned long Area() { return side_length * side_length; } |
| 59 | |
| 60 | private: |
| 61 | unsigned int side_length; |
| 62 | }; |
| 63 | |
Prashanth Swaminathan | 6573187 | 2021-02-11 08:51:08 -0800 | [diff] [blame] | 64 | pw::IntrusiveList<Square> squares; |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 65 | |
| 66 | Square small(1); |
| 67 | Square large(4000); |
| 68 | // These elements are not copied into the linked list, the original objects |
| 69 | // are just chained together and can be accessed via |
| 70 | // `IntrusiveList<Square> squares`. |
| 71 | squares.push_back(small); |
| 72 | squares.push_back(large); |
| 73 | |
| 74 | { |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 75 | // When different_scope goes out of scope, it removes itself from the list. |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 76 | Square different_scope = Square(5); |
| 77 | squares.push_back(&different_scope); |
| 78 | } |
| 79 | |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 80 | for (const auto& square : squares) { |
| 81 | PW_LOG_INFO("Found a square with an area of %lu", square.Area()); |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 82 | } |
| 83 | |
Wyatt Hepler | 7db89d1 | 2022-02-02 16:02:55 -0800 | [diff] [blame] | 84 | // Like std::forward_list, an iterator is invalidated when the item it refers |
| 85 | // to is removed. It is *NOT* safe to remove items from a list while iterating |
| 86 | // over it in a range-based for loop. |
| 87 | for (const auto& square_bad_example : squares) { |
| 88 | if (square_bad_example.verticies() != 4) { |
| 89 | // BAD EXAMPLE of how to remove matching items from a singly linked list. |
| 90 | squares.remove(square_bad_example); // NEVER DO THIS! THIS IS A BUG! |
| 91 | } |
| 92 | } |
| 93 | |
| 94 | // To remove items while iterating, use an iterator to the previous item. |
| 95 | auto previous = squares.before_begin(); |
| 96 | auto current = squares.begin(); |
| 97 | |
| 98 | while (current != squares.end()) { |
| 99 | if (current->verticies() != 4) { |
| 100 | current = squares.erase_after(previous); |
| 101 | } else { |
| 102 | previous = current; |
| 103 | ++current; |
| 104 | } |
Erik Gilling | 5733a0e | 2022-01-24 21:59:49 +0000 | [diff] [blame] | 105 | } |
| 106 | |
Wyatt Hepler | b6884d7 | 2021-06-11 09:23:52 -0700 | [diff] [blame] | 107 | pw::containers::FlatMap |
| 108 | ======================= |
| 109 | FlatMap provides a simple, fixed-size associative array with lookup by key or |
| 110 | value. ``pw::containers::FlatMap`` contains the same methods and features for |
| 111 | looking up data as std::map. However, there are no methods that modify the |
| 112 | underlying data. The underlying array in ``pw::containers::FlatMap`` does not |
| 113 | need to be sorted. During construction, ``pw::containers::FlatMap`` will |
| 114 | perform a constexpr insertion sort. |
Armando Montanez | 516022c | 2020-05-14 09:12:19 -0700 | [diff] [blame] | 115 | |
Wyatt Hepler | 100a160 | 2021-10-05 14:02:02 -0700 | [diff] [blame] | 116 | pw::containers::FilteredView |
| 117 | ============================ |
| 118 | ``pw::containers::FilteredView`` provides a view of a container that only |
| 119 | contains elements that match the specified filter. This class is similar to |
| 120 | C++20's `std::ranges::filter_view |
| 121 | <https://en.cppreference.com/w/cpp/ranges/filter_view>`_. |
| 122 | |
| 123 | To create a ``FilteredView``, pass a container and a filter object, which may be |
| 124 | a lambda or class that implements ``operator()`` for the container's value type. |
| 125 | |
| 126 | .. code-block:: cpp |
| 127 | |
| 128 | std::array<int, 99> kNumbers = {3, 1, 4, 1, ...}; |
| 129 | |
| 130 | for (int even : FilteredView(kNumbers, [](int n) { return n % 2 == 0; })) { |
| 131 | PW_LOG_INFO("This number is even: %d", even); |
| 132 | } |
| 133 | |
Wyatt Hepler | bfb9887 | 2021-10-07 21:16:24 -0700 | [diff] [blame] | 134 | pw::containers::WrappedIterator |
| 135 | =============================== |
| 136 | ``pw::containers::WrappedIterator`` is a class that makes it easy to wrap an |
| 137 | existing iterator type. It reduces boilerplate by providing ``operator++``, |
| 138 | ``operator--``, ``operator==``, ``operator!=``, and the standard iterator |
| 139 | aliases (``difference_type``, ``value_type``, etc.). It does not provide the |
| 140 | dereference operator; that must be supplied by a derived class. |
| 141 | |
| 142 | To use it, create a class that derives from ``WrappedIterator`` and define |
| 143 | ``operator*()`` and ``operator->()`` as appropriate. The new iterator might |
| 144 | apply a transformation to or access a member of the values provided by the |
| 145 | original iterator. The following example defines an iterator that multiplies the |
| 146 | values in an array by 2. |
| 147 | |
| 148 | .. code-block:: cpp |
| 149 | |
| 150 | // Divides values in a std::array by two. |
| 151 | class DoubleIterator |
| 152 | : public pw::containers::WrappedIterator<DoubleIterator, const int*, int> { |
| 153 | public: |
| 154 | constexpr DoubleIterator(const int* it) : WrappedIterator(it) {} |
| 155 | |
| 156 | int operator*() const { return value() * 2; } |
| 157 | |
| 158 | // Don't define operator-> since this iterator returns by value. |
| 159 | }; |
| 160 | |
| 161 | constexpr std::array<int, 6> kArray{0, 1, 2, 3, 4, 5}; |
| 162 | |
| 163 | void SomeFunction { |
| 164 | for (DoubleIterator it(kArray.begin()); it != DoubleIterator(kArray.end()); ++it) { |
| 165 | // The iterator yields 0, 2, 4, 6, 8, 10 instead of the original values. |
| 166 | } |
| 167 | }; |
| 168 | |
| 169 | ``WrappedIterator`` may be used in concert with ``FilteredView`` to create a |
| 170 | view that iterates over a matching values in a container and applies a |
| 171 | transformation to the values. For example, it could be used with |
| 172 | ``FilteredView`` to filter a list of packets and yield only one field from the |
| 173 | packet. |
| 174 | |
| 175 | The combination of ``FilteredView`` and ``WrappedIterator`` provides some basic |
| 176 | functional programming features similar to (though much more cumbersome than) |
| 177 | `generator expressions <https://www.python.org/dev/peps/pep-0289/>`_ (or `filter |
| 178 | <https://docs.python.org/3/library/functions.html#filter>`_/`map |
| 179 | <https://docs.python.org/3/library/functions.html#map>`_) in Python or streams |
| 180 | in Java 8. ``WrappedIterator`` and ``FilteredView`` require no memory |
| 181 | allocation, which is helpful when memory is too constrained to process the items |
| 182 | into a new container. |
| 183 | |
Wyatt Hepler | fff3c7c | 2021-08-17 18:15:10 -0700 | [diff] [blame] | 184 | pw::containers::to_array |
| 185 | ======================== |
| 186 | ``pw::containers::to_array`` is a C++14-compatible implementation of C++20's |
| 187 | `std::to_array <https://en.cppreference.com/w/cpp/container/array/to_array>`_. |
| 188 | It converts a C array to a ``std::array``. |
| 189 | |
Wyatt Hepler | 3c4e5de | 2020-03-03 14:37:52 -0800 | [diff] [blame] | 190 | Compatibility |
| 191 | ============= |
Wyatt Hepler | 3c4e5de | 2020-03-03 14:37:52 -0800 | [diff] [blame] | 192 | * C++17 |
| 193 | |
| 194 | Dependencies |
| 195 | ============ |
Armando Montanez | 0054a9b | 2020-03-13 13:06:24 -0700 | [diff] [blame] | 196 | * ``pw_span`` |
Yuval Peress | b8f3ad2 | 2021-10-26 22:55:27 -0600 | [diff] [blame] | 197 | |
| 198 | Zephyr |
| 199 | ====== |
| 200 | To enable ``pw_containers`` for Zephyr add ``CONFIG_PIGWEED_CONTAINERS=y`` to |
| 201 | the project's configuration. |