1.. _module-pw_containers: 2 3============= 4pw_containers 5============= 6The ``pw_containers`` module provides embedded-friendly container classes. 7 8---------- 9pw::Vector 10---------- 11The Vector class is similar to ``std::vector``, except it is backed by a 12fixed-size buffer. Vectors must be declared with an explicit maximum size 13(e.g. ``Vector<int, 10>``) but vectors can be used and referred to without the 14max size template parameter (e.g. ``Vector<int>``). 15 16To allow referring to a ``pw::Vector`` without an explicit maximum size, all 17Vector classes inherit from the generic ``Vector<T>``, which stores the maximum 18size in a variable. This allows Vectors to be used without having to know 19their maximum size at compile time. It also keeps code size small since 20function implementations are shared for all maximum sizes. 21 22.. admonition:: Non-trivially-destructible, self-referencing types 23 24 ``pw::Vector`` is not safe to use with non-trivially-destructible, 25 self-referencing types. See `b/313899658 26 <https://issues.pigweed.dev/issues/313899658>`_. 27 28--------------- 29pw::InlineDeque 30--------------- 31.. doxygentypedef:: pw::InlineDeque 32 33--------------- 34pw::InlineQueue 35--------------- 36.. doxygentypedef:: pw::InlineQueue 37 38-------------------------- 39pw::InlineVarLenEntryQueue 40-------------------------- 41.. doxygenfile:: pw_containers/inline_var_len_entry_queue.h 42 :sections: detaileddescription 43 44Example 45======= 46.. tab-set:: 47 48 .. tab-item:: C++ 49 :sync: c++ 50 51 Queues are declared with their max size 52 (``InlineVarLenEntryQueue<kMaxSize>``) but may be used without 53 specifying the size (``InlineVarLenEntryQueue<>&``). 54 55 .. code-block:: c++ 56 57 // Declare a queue with capacity sufficient for one 10-byte entry or 58 // multiple smaller entries. 59 pw::InlineVarLenEntryQueue<10> queue; 60 61 // Push an entry, asserting if the entry does not fit. 62 queue.push(queue, data) 63 64 // Use push_overwrite() to push entries, overwriting older entries 65 // as needed. 66 queue.push_overwrite(queue, more_data) 67 68 // Remove an entry. 69 queue.pop(); 70 71 Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an 72 existing ``uint32_t`` array. 73 74 .. code-block:: c++ 75 76 // Initialize a InlineVarLenEntryQueue. 77 uint32_t buffer[32]; 78 auto& queue = pw::InlineVarLenEntryQueue<>::Init(buffer); 79 80 // Largest supported entry is 114 B (13 B overhead + 1 B prefix) 81 assert(queue.max_size_bytes() == 114u); 82 83 // Write data 84 queue.push_overwrite(data); 85 86 .. tab-item:: C 87 :sync: c 88 89 A ``InlineVarLenEntryQueue`` may be declared and initialized in C with the 90 :c:macro:`PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE` macro. 91 92 .. code-block:: c 93 94 // Declare a queue with capacity sufficient for one 10-byte entry or 95 // multiple smaller entries. 96 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 10); 97 98 // Push an entry, asserting if the entry does not fit. 99 pw_InlineVarLenEntryQueue_Push(queue, "12345", 5); 100 101 // Use push_overwrite() to push entries, overwriting older entries 102 // as needed. 103 pw_InlineVarLenEntryQueue_PushOverwrite(queue, "abcdefg", 7); 104 105 // Remove an entry. 106 pw_InlineVarLenEntryQueue_Pop(queue); 107 108 Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an 109 existing ``uint32_t`` array. 110 111 .. code-block:: c 112 113 // Initialize a InlineVarLenEntryQueue. 114 uint32_t buffer[32]; 115 pw_InlineVarLenEntryQueue_Init(buffer, 32); 116 117 // Largest supported entry is 114 B (13 B overhead + 1 B prefix) 118 assert(pw_InlineVarLenEntryQueue_MaxSizeBytes(buffer) == 114u); 119 120 // Write some data 121 pw_InlineVarLenEntryQueue_PushOverwrite(buffer, "123", 3); 122 123Queue vs. deque 124=============== 125This module provides :cpp:type:`InlineVarLenEntryQueue`, but no corresponding 126``InlineVarLenEntryDeque`` class. Following the C++ Standard Library style, 127the deque class would provide ``push_front()`` and ``pop_back()`` operations in 128addition to ``push_back()`` and ``pop_front()`` (equivalent to a queue's 129``push()`` and ``pop()``). 130 131There is no ``InlineVarLenEntryDeque`` class because there is no efficient way 132to implement ``push_front()`` and ``pop_back()``. These operations would 133necessarily be O(n), since each entry knows the position of the next entry, but 134not the previous, as in a single-linked list. Given that these operations would 135be inefficient and unlikely to be used, they are not implemented, and only a 136queue class is provided. 137 138API Reference 139=============== 140C++ 141--- 142.. doxygengroup:: inline_var_len_entry_queue_cpp_api 143 :content-only: 144 :members: 145 146C 147- 148.. doxygengroup:: inline_var_len_entry_queue_c_api 149 :content-only: 150 151Python 152------ 153.. automodule:: pw_containers.inline_var_len_entry_queue 154 :members: 155 156----------------- 157pw::IntrusiveList 158----------------- 159IntrusiveList provides an embedded-friendly singly-linked intrusive list 160implementation. An intrusive list is a type of linked list that embeds the 161"next" pointer into the list object itself. This allows the construction of a 162linked list without the need to dynamically allocate list entries. 163 164In C, an intrusive list can be made by manually including the "next" pointer as 165a member of the object's struct. ``pw::IntrusiveList`` uses C++ features to 166simplify the process of creating an intrusive list. ``pw::IntrusiveList`` 167provides a class that list elements can inherit from. This protects the "next" 168pointer from being accessed by the item class, so only the ``pw::IntrusiveList`` 169class can modify the list. 170 171Usage 172===== 173While the API of ``pw::IntrusiveList`` is similar to a ``std::forward_list``, 174there are extra steps to creating objects that can be stored in this data 175structure. Objects that will be added to a ``IntrusiveList<T>`` must inherit 176from ``IntrusiveList<T>::Item``. They can inherit directly from it or inherit 177from it through another base class. When an item is instantiated and added to a 178linked list, the pointer to the object is added to the "next" pointer of 179whichever object is the current tail. 180 181That means two key things: 182 183- An instantiated ``IntrusiveList<T>::Item`` will be removed from its 184 corresponding ``IntrusiveList`` when it goes out of scope. 185- A linked list item CANNOT be included in two lists. Attempting to do so 186 results in an assert failure. 187 188.. code-block:: cpp 189 190 class Square 191 : public pw::IntrusiveList<Square>::Item { 192 public: 193 Square(unsigned int side_length) : side_length(side_length) {} 194 unsigned long Area() { return side_length * side_length; } 195 196 private: 197 unsigned int side_length; 198 }; 199 200 pw::IntrusiveList<Square> squares; 201 202 Square small(1); 203 Square large(4000); 204 // These elements are not copied into the linked list, the original objects 205 // are just chained together and can be accessed via 206 // `IntrusiveList<Square> squares`. 207 squares.push_back(small); 208 squares.push_back(large); 209 210 { 211 // When different_scope goes out of scope, it removes itself from the list. 212 Square different_scope = Square(5); 213 squares.push_back(&different_scope); 214 } 215 216 for (const auto& square : squares) { 217 PW_LOG_INFO("Found a square with an area of %lu", square.Area()); 218 } 219 220 // Like std::forward_list, an iterator is invalidated when the item it refers 221 // to is removed. It is *NOT* safe to remove items from a list while iterating 222 // over it in a range-based for loop. 223 for (const auto& square_bad_example : squares) { 224 if (square_bad_example.verticies() != 4) { 225 // BAD EXAMPLE of how to remove matching items from a singly linked list. 226 squares.remove(square_bad_example); // NEVER DO THIS! THIS IS A BUG! 227 } 228 } 229 230 // To remove items while iterating, use an iterator to the previous item. 231 auto previous = squares.before_begin(); 232 auto current = squares.begin(); 233 234 while (current != squares.end()) { 235 if (current->verticies() != 4) { 236 current = squares.erase_after(previous); 237 } else { 238 previous = current; 239 ++current; 240 } 241 } 242 243Performance Considerations 244========================== 245Items only include pointers to the next item. To reach previous items, the list 246maintains a cycle of items so that the first item can be reached from the last. 247This structure means certain operations have linear complexity in terms of the 248number of items in the list, i.e. they are "O(n)": 249 250- Adding to the end of a list with ``pw::IntrusiveList<T>::push_back(T&)``. 251- Accessing the last item in a list with ``pw::IntrusiveList<T>::back()``. 252- Destroying an item with ``pw::IntrusiveList<T>::Item::~Item()``. 253- Moving an item with either ``pw::IntrusiveList<T>::Item::Item(Item&&)`` or 254 ``pw::IntrusiveList<T>::Item::operator=(Item&&)``. 255- Removing an item from a list using ``pw::IntrusiveList<T>::remove(const T&)``. 256- Getting the list size using ``pw::IntrusiveList<T>::size()``. 257 258When using a ``pw::IntrusiveList<T>`` in a performance critical section or with 259many items, authors should prefer to avoid these methods. For example, it may be 260preferrable to create items that together with their storage outlive the list. 261 262Notably, ``pw::IntrusiveList<T>::end()`` is constant complexity (i.e. "O(1)"). 263As a result iterating over a list does not incur an additional penalty. 264 265----------------------- 266pw::containers::FlatMap 267----------------------- 268``FlatMap`` provides a simple, fixed-size associative array with `O`\ (log `n`) 269lookup by key. 270 271``pw::containers::FlatMap`` contains the same methods and features for looking 272up data as ``std::map``. However, modification of the underlying data is limited 273to the mapped values, via ``.at()`` (key must exist) and ``mapped_iterator`` 274objects returned by ``.mapped_begin()`` and ``.mapped_end()``. 275``mapped_iterator`` objects are bidirectional iterators that can be dereferenced 276to access and mutate the mapped value objects. 277 278The underlying array in ``pw::containers::FlatMap`` does not need to be sorted. 279During construction, ``pw::containers::FlatMap`` will perform a constexpr 280insertion sort. 281 282To create a ``FlatMap``, there are some options. The following example defines 283a ``FlatMap`` with two items. 284 285.. code-block:: cpp 286 287 // Initiates by a std::array of Pair<K, V> objects. 288 FlatMap<int, char, 2> map({{ 289 {1, 'a'}, 290 {-3, 'b'}, 291 }}); 292 293 FlatMap map(std::array{ 294 Pair<int, char>{1, 'a'}, 295 Pair<int, char>{-3, 'b'}, 296 }); 297 298 // Initiates by Pair<K, V> objects. 299 FlatMap map = { 300 Pair<int, char>{1, 'a'}, 301 Pair<int, char>{-3, 'b'}, 302 }; 303 304---------------------------- 305pw::containers::FilteredView 306---------------------------- 307.. doxygenclass:: pw::containers::FilteredView 308 309------------------------------- 310pw::containers::WrappedIterator 311------------------------------- 312``pw::containers::WrappedIterator`` is a class that makes it easy to wrap an 313existing iterator type. It reduces boilerplate by providing ``operator++``, 314``operator--``, ``operator==``, ``operator!=``, and the standard iterator 315aliases (``difference_type``, ``value_type``, etc.). It does not provide the 316dereference operator; that must be supplied by a derived class. 317 318To use it, create a class that derives from ``WrappedIterator`` and define 319``operator*()`` and ``operator->()`` as appropriate. The new iterator might 320apply a transformation to or access a member of the values provided by the 321original iterator. The following example defines an iterator that multiplies the 322values in an array by 2. 323 324.. code-block:: cpp 325 326 // Divides values in a std::array by two. 327 class DoubleIterator 328 : public pw::containers::WrappedIterator<DoubleIterator, const int*, int> { 329 public: 330 constexpr DoubleIterator(const int* it) : WrappedIterator(it) {} 331 332 int operator*() const { return value() * 2; } 333 334 // Don't define operator-> since this iterator returns by value. 335 }; 336 337 constexpr std::array<int, 6> kArray{0, 1, 2, 3, 4, 5}; 338 339 void SomeFunction { 340 for (DoubleIterator it(kArray.begin()); it != DoubleIterator(kArray.end()); ++it) { 341 // The iterator yields 0, 2, 4, 6, 8, 10 instead of the original values. 342 } 343 }; 344 345``WrappedIterator`` may be used in concert with ``FilteredView`` to create a 346view that iterates over a matching values in a container and applies a 347transformation to the values. For example, it could be used with 348``FilteredView`` to filter a list of packets and yield only one field from the 349packet. 350 351The combination of ``FilteredView`` and ``WrappedIterator`` provides some basic 352functional programming features similar to (though much more cumbersome than) 353`generator expressions <https://www.python.org/dev/peps/pep-0289/>`_ (or `filter 354<https://docs.python.org/3/library/functions.html#filter>`_/`map 355<https://docs.python.org/3/library/functions.html#map>`_) in Python or streams 356in Java 8. ``WrappedIterator`` and ``FilteredView`` require no memory 357allocation, which is helpful when memory is too constrained to process the items 358into a new container. 359 360------------------------ 361pw::containers::to_array 362------------------------ 363``pw::containers::to_array`` is a C++14-compatible implementation of C++20's 364`std::to_array <https://en.cppreference.com/w/cpp/container/array/to_array>`_. 365In C++20, it is an alias for ``std::to_array``. It converts a C array to a 366``std::array``. 367 368------------------------- 369pw_containers/algorithm.h 370------------------------- 371Pigweed provides a set of Container-based versions of algorithmic functions 372within the C++ standard library, based on a subset of 373``absl/algorithm/container.h``. 374 375.. cpp:function:: bool pw::containers::AllOf() 376 377 Container-based version of the <algorithm> ``std::all_of()`` function to 378 test if all elements within a container satisfy a condition. 379 380.. cpp:function:: bool pw::containers::AnyOf() 381 382 Container-based version of the <algorithm> ``std::any_of()`` function to 383 test if any element in a container fulfills a condition. 384 385.. cpp:function:: bool pw::containers::NoneOf() 386 387 Container-based version of the <algorithm> ``std::none_of()`` function to 388 test if no elements in a container fulfill a condition. 389 390.. cpp:function:: pw::containers::ForEach() 391 392 Container-based version of the <algorithm> ``std::for_each()`` function to 393 apply a function to a container's elements. 394 395.. cpp:function:: pw::containers::Find() 396 397 Container-based version of the <algorithm> ``std::find()`` function to find 398 the first element containing the passed value within a container value. 399 400.. cpp:function:: pw::containers::FindIf() 401 402 Container-based version of the <algorithm> ``std::find_if()`` function to find 403 the first element in a container matching the given condition. 404 405.. cpp:function:: pw::containers::FindIfNot() 406 407 Container-based version of the <algorithm> ``std::find_if_not()`` function to 408 find the first element in a container not matching the given condition. 409 410.. cpp:function:: pw::containers::FindEnd() 411 412 Container-based version of the <algorithm> ``std::find_end()`` function to 413 find the last subsequence within a container. 414 415.. cpp:function:: pw::containers::FindFirstOf() 416 417 Container-based version of the <algorithm> ``std::find_first_of()`` function 418 to find the first element within the container that is also within the options 419 container. 420 421.. cpp:function:: pw::containers::AdjacentFind() 422 423 Container-based version of the <algorithm> ``std::adjacent_find()`` function 424 to find equal adjacent elements within a container. 425 426.. cpp:function:: pw::containers::Count() 427 428 Container-based version of the <algorithm> ``std::count()`` function to count 429 values that match within a container. 430 431.. cpp:function:: pw::containers::CountIf() 432 433 Container-based version of the <algorithm> ``std::count_if()`` function to 434 count values matching a condition within a container. 435 436.. cpp:function:: pw::containers::Mismatch() 437 438 Container-based version of the <algorithm> ``std::mismatch()`` function to 439 return the first element where two ordered containers differ. Applies ``==`` 440 to the first ``N`` elements of ``c1`` and ``c2``, where 441 ``N = min(size(c1), size(c2)).`` the function's test condition. Applies 442 ``pred`` to the first N elements of ``c1`` and ``c2``, where 443 ``N = min(size(c1), size(c2))``. 444 445.. cpp:function:: bool pw::containers::Equal() 446 447 Container-based version of the <algorithm> ``std::equal()`` function to 448 test whether two containers are equal. 449 450 .. note:: 451 452 The semantics of ``Equal()`` are slightly different than those of 453 ``std::equal()``: while the latter iterates over the second container only 454 up to the size of the first container, ``Equal()`` also checks whether the 455 container sizes are equal. This better matches expectations about 456 ``Equal()`` based on its signature. 457 458.. cpp:function:: bool pw::containers::IsPermutation() 459 460 Container-based version of the <algorithm> ``std::is_permutation()`` function 461 to test whether a container is a permutation of another. 462 463.. cpp:function:: pw::containers::Search() 464 465 Container-based version of the <algorithm> ``std::search()`` function to 466 search a container for a subsequence. 467 468.. cpp:function:: pw::containers::SearchN() 469 470 Container-based version of the <algorithm> ``std::search_n()`` function to 471 search a container for the first sequence of N elements. 472 473------------- 474Compatibility 475------------- 476- C++17 477 478------ 479Zephyr 480------ 481To enable ``pw_containers`` for Zephyr add ``CONFIG_PIGWEED_CONTAINERS=y`` to 482the project's configuration. 483