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--------------- 23pw::InlineDeque 24--------------- 25.. doxygentypedef:: pw::InlineDeque 26 27--------------- 28pw::InlineQueue 29--------------- 30.. doxygentypedef:: pw::InlineQueue 31 32-------------------------- 33pw::InlineVarLenEntryQueue 34-------------------------- 35.. doxygenfile:: pw_containers/inline_var_len_entry_queue.h 36 :sections: detaileddescription 37 38Example 39======= 40.. tab-set:: 41 42 .. tab-item:: C++ 43 :sync: c++ 44 45 Queues are declared with their max size 46 (``InlineVarLenEntryQueue<kMaxSize>``) but may be used without 47 specifying the size (``InlineVarLenEntryQueue<>&``). 48 49 .. code-block:: c++ 50 51 // Declare a queue with capacity sufficient for one 10-byte entry or 52 // multiple smaller entries. 53 pw::InlineVarLenEntryQueue<10> queue; 54 55 // Push an entry, asserting if the entry does not fit. 56 queue.push(queue, data) 57 58 // Use push_overwrite() to push entries, overwriting older entries 59 // as needed. 60 queue.push_overwrite(queue, more_data) 61 62 // Remove an entry. 63 queue.pop(); 64 65 Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an 66 existing ``uint32_t`` array. 67 68 .. code-block:: c++ 69 70 // Initialize a InlineVarLenEntryQueue. 71 uint32_t buffer[32]; 72 auto& queue = pw::InlineVarLenEntryQueue<>::Init(buffer); 73 74 // Largest supported entry is 114 B (13 B overhead + 1 B prefix) 75 assert(queue.max_size_bytes() == 114u); 76 77 // Write data 78 queue.push_overwrite(data); 79 80 .. tab-item:: C 81 :sync: c 82 83 A ``InlineVarLenEntryQueue`` may be declared and initialized in C with the 84 :c:macro:`PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE` macro. 85 86 .. code-block:: c 87 88 // Declare a queue with capacity sufficient for one 10-byte entry or 89 // multiple smaller entries. 90 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 10); 91 92 // Push an entry, asserting if the entry does not fit. 93 pw_InlineVarLenEntryQueue_Push(queue, "12345", 5); 94 95 // Use push_overwrite() to push entries, overwriting older entries 96 // as needed. 97 pw_InlineVarLenEntryQueue_PushOverwrite(queue, "abcdefg", 7); 98 99 // Remove an entry. 100 pw_InlineVarLenEntryQueue_Pop(queue); 101 102 Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an 103 existing ``uint32_t`` array. 104 105 .. code-block:: c 106 107 // Initialize a InlineVarLenEntryQueue. 108 uint32_t buffer[32]; 109 pw_InlineVarLenEntryQueue_Init(buffer, 32); 110 111 // Largest supported entry is 114 B (13 B overhead + 1 B prefix) 112 assert(pw_InlineVarLenEntryQueue_MaxSizeBytes(buffer) == 114u); 113 114 // Write some data 115 pw_InlineVarLenEntryQueue_PushOverwrite(buffer, "123", 3); 116 117Queue vs. deque 118=============== 119This module provides :cpp:type:`InlineVarLenEntryQueue`, but no corresponding 120``InlineVarLenEntryDeque`` class. Following the C++ Standard Library style, 121the deque class would provide ``push_front()`` and ``pop_back()`` operations in 122addition to ``push_back()`` and ``pop_front()`` (equivalent to a queue's 123``push()`` and ``pop()``). 124 125There is no ``InlineVarLenEntryDeque`` class because there is no efficient way 126to implement ``push_front()`` and ``pop_back()``. These operations would 127necessarily be O(n), since each entry knows the position of the next entry, but 128not the previous, as in a single-linked list. Given that these operations would 129be inefficient and unlikely to be used, they are not implemented, and only a 130queue class is provided. 131 132API Reference 133============= 134C++ 135--- 136.. doxygengroup:: inline_var_len_entry_queue_cpp_api 137 :content-only: 138 :members: 139 140C 141- 142.. doxygengroup:: inline_var_len_entry_queue_c_api 143 :content-only: 144 145Python 146------ 147.. automodule:: pw_containers.inline_var_len_entry_queue 148 :members: 149 150.. _module-pw_containers-intrusive_list: 151 152----------------- 153pw::IntrusiveList 154----------------- 155``pw::IntrusiveList`` provides an embedded-friendly, double-linked, intrusive 156list implementation. An intrusive list is a type of linked list that embeds list 157metadata, such as a "next" pointer, into the list object itself. This allows the 158construction of a linked list without the need to dynamically allocate list 159entries. 160 161In C, an intrusive list can be made by manually including the "next" pointer as 162a member of the object's struct. ``pw::IntrusiveList`` uses C++ features to 163simplify the process of creating an intrusive list. It provides classes that 164list elements can inherit from, protecting the list metadata from being accessed 165by the item class. 166 167API Reference 168============= 169This class is similar to ``std::list<T>``, except that the type of items to be 170added must derive from ``pw::IntrusiveList<T>::Item``. 171 172.. doxygenclass:: pw::containers::future::IntrusiveList 173 :members: 174 175.. note:: 176 Originally, ``pw::IntrusiveList<T>`` was implemented as a singly-linked list. 177 To facilitate migration to ``pw::IntrusiveForwardList<T>::Item``, this 178 original implementation can still be temporarily used by enabling the 179 ``PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST`` module configuration option. 180 181.. _module-pw_containers-intrusive_list-example: 182 183Example 184======= 185.. literalinclude:: examples/intrusive_list.cc 186 :language: cpp 187 :linenos: 188 :start-after: [pw_containers-intrusive_list] 189 :end-before: [pw_containers-intrusive_list] 190 191------------------------ 192pw::IntrusiveForwardList 193------------------------ 194``pw::IntrusiveForwardList`` provides an embedded-friendly, singly-linked, 195intrusive list implementation. It is very similar to 196:ref:`module-pw_containers-intrusive_list`, except that is singly rather than 197doubly linked. 198 199API Reference 200============= 201This class is similar to ``std::forward_list<T>``. Items to be added must derive 202from ``pw::IntrusiveForwardList<T>::Item``. 203 204.. doxygenclass:: pw::IntrusiveForwardList 205 :members: 206 207Example 208======= 209.. literalinclude:: examples/intrusive_forward_list.cc 210 :language: cpp 211 :linenos: 212 :start-after: [pw_containers-intrusive_forward_list] 213 :end-before: [pw_containers-intrusive_forward_list] 214 215Performance Considerations 216========================== 217Items only include pointers to the next item. To reach previous items, the list 218maintains a cycle of items so that the first item can be reached from the last. 219This structure means certain operations have linear complexity in terms of the 220number of items in the list, i.e. they are "O(n)": 221 222- Removing an item from a list using 223 ``pw::IntrusiveForwardList<T>::remove(const T&)``. 224- Getting the list size using ``pw::IntrusiveForwardList<T>::size()``. 225 226When using a ``pw::IntrusiveForwardList<T>`` in a performance critical section 227or with many items, authors should prefer to avoid these methods. For example, 228it may be preferable to create items that together with their storage outlive 229the list. 230 231Notably, ``pw::IntrusiveForwardList<T>::end()`` is constant complexity (i.e. 232"O(1)"). As a result iterating over a list does not incur an additional penalty. 233 234.. _module-pw_containers-intrusivelist-size-report: 235 236Size report 237=========== 238.. include:: intrusive_list_size_report 239 240.. _module-pw_containers-intrusive_set: 241 242---------------- 243pw::IntrusiveSet 244---------------- 245``pw::IntrusiveSet`` provides an embedded-friendly, tree-based, intrusive 246set implementation. The intrusive aspect of the set is very similar to that of 247:ref:`module-pw_containers-intrusive_list`. 248 249API Reference 250============= 251This class is similar to ``std::set<T>``. Items to be added must derive from 252``pw::IntrusiveSet<T>::Item`` or an equivalent type. 253 254.. doxygenclass:: pw::IntrusiveSet 255 :members: 256 257Example 258======= 259.. literalinclude:: examples/intrusive_set.cc 260 :language: cpp 261 :linenos: 262 :start-after: [pw_containers-intrusive_set] 263 :end-before: [pw_containers-intrusive_set] 264 265--------------------- 266pw::IntrusiveMultiSet 267--------------------- 268``pw::IntrusiveMultiSet`` provides an embedded-friendly, tree-based, intrusive 269multiset implementation. This is very similar to 270:ref:`module-pw_containers-intrusive_set`, except that the tree may contain 271multiple items with equivalent keys. 272 273API Reference 274============= 275This class is similar to ``std::multiset<T>``. Items to be added must derive 276from ``pw::IntrusiveMultiSet<T>::Item`` or an equivalent type. 277 278.. doxygenclass:: pw::IntrusiveMultiSet 279 :members: 280 281Example 282======= 283.. literalinclude:: examples/intrusive_multiset.cc 284 :language: cpp 285 :linenos: 286 :start-after: [pw_containers-intrusive_multiset] 287 :end-before: [pw_containers-intrusive_multiset] 288 289.. _module-pw_containers-intrusive_map: 290 291---------------- 292pw::IntrusiveMap 293---------------- 294``pw::IntrusiveMap`` provides an embedded-friendly, tree-based, intrusive 295map implementation. The intrusive aspect of the map is very similar to that of 296:ref:`module-pw_containers-intrusive_list`. 297 298API Reference 299============= 300This class is similar to ``std::map<K, V>``. Items to be added must derive from 301``pw::IntrusiveMap<K, V>::Item`` or an equivalent type. 302 303.. doxygenclass:: pw::IntrusiveMap 304 :members: 305 306Example 307======= 308.. literalinclude:: examples/intrusive_map.cc 309 :language: cpp 310 :linenos: 311 :start-after: [pw_containers-intrusive_map] 312 :end-before: [pw_containers-intrusive_map] 313 314--------------------- 315pw::IntrusiveMultiMap 316--------------------- 317``pw::IntrusiveMultiMap`` provides an embedded-friendly, tree-based, intrusive 318multimap implementation. This is very similar to 319:ref:`module-pw_containers-intrusive_map`, except that the tree may contain 320multiple items with equivalent keys. 321 322API Reference 323============= 324This class is similar to ``std::multimap<K, V>``. Items to be added must derive 325from ``pw::IntrusiveMultiMap<K, V>::Item`` or an equivalent type. 326 327.. doxygenclass:: pw::IntrusiveMultiMap 328 :members: 329 330Example 331======= 332.. literalinclude:: examples/intrusive_multimap.cc 333 :language: cpp 334 :linenos: 335 :start-after: [pw_containers-intrusive_multimap] 336 :end-before: [pw_containers-intrusive_multimap] 337 338------------------------------------ 339Using items with multiple containers 340------------------------------------ 341Intrusive items may be used with multiple containers, provided each of those 342containers is templated on a type that is not derived from any of the others. 343This can be achieved by multiply inheriting from distinct type: 344 345.. literalinclude:: examples/multiple_containers.cc 346 :language: cpp 347 :linenos: 348 :start-after: [pw_containers-multiple_containers] 349 :end-before: [pw_containers-multiple_containers] 350 351If one or more types is derived from another, the compiler will fail to build 352with an error that ``ItemType`` is ambiguous or found in multiple base classes. 353 354----------------------- 355pw::containers::FlatMap 356----------------------- 357``FlatMap`` provides a simple, fixed-size associative array with `O`\ (log `n`) 358lookup by key. 359 360``pw::containers::FlatMap`` contains the same methods and features for looking 361up data as ``std::map``. However, modification of the underlying data is limited 362to the mapped values, via ``.at()`` (key must exist) and ``mapped_iterator`` 363objects returned by ``.mapped_begin()`` and ``.mapped_end()``. 364``mapped_iterator`` objects are bidirectional iterators that can be dereferenced 365to access and mutate the mapped value objects. 366 367The underlying array in ``pw::containers::FlatMap`` does not need to be sorted. 368During construction, ``pw::containers::FlatMap`` will perform a constexpr 369insertion sort. 370 371A ``FlatMap`` can be created in one of several ways. Each of the following 372examples defines a ``FlatMap`` with two items. 373 374.. literalinclude:: examples/flat_map.cc 375 :language: cpp 376 :linenos: 377 :start-after: [pw_containers-flat_map] 378 :end-before: [pw_containers-flat_map] 379 380---------------------------- 381pw::containers::FilteredView 382---------------------------- 383.. doxygenclass:: pw::containers::FilteredView 384 385------------------------------- 386pw::containers::WrappedIterator 387------------------------------- 388``pw::containers::WrappedIterator`` is a class that makes it easy to wrap an 389existing iterator type. It reduces boilerplate by providing ``operator++``, 390``operator--``, ``operator==``, ``operator!=``, and the standard iterator 391aliases (``difference_type``, ``value_type``, etc.). It does not provide the 392dereference operator; that must be supplied by a derived class. 393 394To use it, create a class that derives from ``WrappedIterator`` and define 395``operator*()`` and ``operator->()`` as appropriate. The new iterator might 396apply a transformation to or access a member of the values provided by the 397original iterator. The following example defines an iterator that multiplies the 398values in an array by 2. 399 400.. literalinclude:: examples/wrapped_iterator.cc 401 :language: cpp 402 :linenos: 403 :start-after: [pw_containers-wrapped_iterator] 404 :end-before: [pw_containers-wrapped_iterator] 405 406``WrappedIterator`` may be used in concert with ``FilteredView`` to create a 407view that iterates over a matching values in a container and applies a 408transformation to the values. For example, it could be used with 409``FilteredView`` to filter a list of packets and yield only one field from the 410packet. 411 412The combination of ``FilteredView`` and ``WrappedIterator`` provides some basic 413functional programming features similar to (though much more cumbersome than) 414`generator expressions <https://www.python.org/dev/peps/pep-0289/>`_ (or `filter 415<https://docs.python.org/3/library/functions.html#filter>`_/`map 416<https://docs.python.org/3/library/functions.html#map>`_) in Python or streams 417in Java 8. ``WrappedIterator`` and ``FilteredView`` require no memory 418allocation, which is helpful when memory is too constrained to process the items 419into a new container. 420 421------------------------ 422pw::containers::to_array 423------------------------ 424``pw::containers::to_array`` is a C++14-compatible implementation of C++20's 425`std::to_array <https://en.cppreference.com/w/cpp/container/array/to_array>`_. 426In C++20, it is an alias for ``std::to_array``. It converts a C array to a 427``std::array``. 428 429------------------------- 430pw_containers/algorithm.h 431------------------------- 432Pigweed provides a set of Container-based versions of algorithmic functions 433within the C++ standard library, based on a subset of 434``absl/algorithm/container.h``. 435 436.. cpp:function:: bool pw::containers::AllOf() 437 438 Container-based version of the <algorithm> ``std::all_of()`` function to 439 test if all elements within a container satisfy a condition. 440 441.. cpp:function:: bool pw::containers::AnyOf() 442 443 Container-based version of the <algorithm> ``std::any_of()`` function to 444 test if any element in a container fulfills a condition. 445 446.. cpp:function:: bool pw::containers::NoneOf() 447 448 Container-based version of the <algorithm> ``std::none_of()`` function to 449 test if no elements in a container fulfill a condition. 450 451.. cpp:function:: pw::containers::ForEach() 452 453 Container-based version of the <algorithm> ``std::for_each()`` function to 454 apply a function to a container's elements. 455 456.. cpp:function:: pw::containers::Find() 457 458 Container-based version of the <algorithm> ``std::find()`` function to find 459 the first element containing the passed value within a container value. 460 461.. cpp:function:: pw::containers::FindIf() 462 463 Container-based version of the <algorithm> ``std::find_if()`` function to find 464 the first element in a container matching the given condition. 465 466.. cpp:function:: pw::containers::FindIfNot() 467 468 Container-based version of the <algorithm> ``std::find_if_not()`` function to 469 find the first element in a container not matching the given condition. 470 471.. cpp:function:: pw::containers::FindEnd() 472 473 Container-based version of the <algorithm> ``std::find_end()`` function to 474 find the last subsequence within a container. 475 476.. cpp:function:: pw::containers::FindFirstOf() 477 478 Container-based version of the <algorithm> ``std::find_first_of()`` function 479 to find the first element within the container that is also within the options 480 container. 481 482.. cpp:function:: pw::containers::AdjacentFind() 483 484 Container-based version of the <algorithm> ``std::adjacent_find()`` function 485 to find equal adjacent elements within a container. 486 487.. cpp:function:: pw::containers::Count() 488 489 Container-based version of the <algorithm> ``std::count()`` function to count 490 values that match within a container. 491 492.. cpp:function:: pw::containers::CountIf() 493 494 Container-based version of the <algorithm> ``std::count_if()`` function to 495 count values matching a condition within a container. 496 497.. cpp:function:: pw::containers::Mismatch() 498 499 Container-based version of the <algorithm> ``std::mismatch()`` function to 500 return the first element where two ordered containers differ. Applies ``==`` 501 to the first ``N`` elements of ``c1`` and ``c2``, where 502 ``N = min(size(c1), size(c2)).`` the function's test condition. Applies 503 ``pred`` to the first N elements of ``c1`` and ``c2``, where 504 ``N = min(size(c1), size(c2))``. 505 506.. cpp:function:: bool pw::containers::Equal() 507 508 Container-based version of the <algorithm> ``std::equal()`` function to 509 test whether two containers are equal. 510 511 .. note:: 512 513 The semantics of ``Equal()`` are slightly different than those of 514 ``std::equal()``: while the latter iterates over the second container only 515 up to the size of the first container, ``Equal()`` also checks whether the 516 container sizes are equal. This better matches expectations about 517 ``Equal()`` based on its signature. 518 519.. cpp:function:: bool pw::containers::IsPermutation() 520 521 Container-based version of the <algorithm> ``std::is_permutation()`` function 522 to test whether a container is a permutation of another. 523 524.. cpp:function:: pw::containers::Search() 525 526 Container-based version of the <algorithm> ``std::search()`` function to 527 search a container for a subsequence. 528 529.. cpp:function:: pw::containers::SearchN() 530 531 Container-based version of the <algorithm> ``std::search_n()`` function to 532 search a container for the first sequence of N elements. 533 534------------- 535Compatibility 536------------- 537- C++17 538 539------ 540Zephyr 541------ 542To enable ``pw_containers`` for Zephyr add ``CONFIG_PIGWEED_CONTAINERS=y`` to 543the project's configuration. 544