1.. _module-pw_containers-lists: 2 3===== 4Lists 5===== 6.. pigweed-module-subpage:: 7 :name: pw_containers 8 9A linked list is an ordered collection of items in which each item is associated 10with pointers to one or more of its adjacent items. Pigweed provides intrusive 11lists, meaning the pointers are stored within the items themselves. This allows 12an arbitrary number of items to be added to a list without requiring additional 13memory beyond that of the items themselves. 14 15.. _module-pw_containers-intrusive_list: 16 17----------------- 18pw::IntrusiveList 19----------------- 20``pw::IntrusiveList`` provides an embedded-friendly, double-linked, intrusive 21list implementation. An intrusive list is a type of linked list that embeds list 22metadata, such as a "next" pointer, into the list object itself. This allows the 23construction of a linked list without the need to dynamically allocate list 24entries. 25 26In C, an intrusive list can be made by manually including the "next" pointer as 27a member of the object's struct. ``pw::IntrusiveList`` uses C++ features to 28simplify the process of creating an intrusive list. It provides classes that 29list elements can inherit from, protecting the list metadata from being accessed 30by the item class. 31 32See also :ref:`module-pw_containers-multiple_containers`. 33 34.. _module-pw_containers-intrusive_list-example: 35 36Example 37======= 38.. literalinclude:: examples/intrusive_list.cc 39 :language: cpp 40 :linenos: 41 :start-after: [pw_containers-intrusive_list] 42 :end-before: [pw_containers-intrusive_list] 43 44If you need to add this item to containers of more than one type, see 45:ref:`module-pw_containers-multiple_containers`, 46 47API reference 48============= 49This class is similar to ``std::list<T>``, except that the type of items to be 50added must derive from ``pw::IntrusiveList<T>::Item``. 51 52.. doxygenclass:: pw::containers::future::IntrusiveList 53 :members: 54 55.. note:: 56 Originally, ``pw::IntrusiveList<T>`` was implemented as a singly linked list. 57 To facilitate migration to ``pw::IntrusiveForwardList<T>::Item``, this 58 original implementation can still be temporarily used by enabling the 59 ``PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST`` module configuration option. 60 61------------------------ 62pw::IntrusiveForwardList 63------------------------ 64``pw::IntrusiveForwardList`` provides an embedded-friendly, singly linked, 65intrusive list implementation. It is very similar to 66:ref:`module-pw_containers-intrusive_list`, except that it is singly rather than 67doubly linked. 68 69See also :ref:`module-pw_containers-multiple_containers`. 70 71Example 72======= 73.. literalinclude:: examples/intrusive_forward_list.cc 74 :language: cpp 75 :linenos: 76 :start-after: [pw_containers-intrusive_forward_list] 77 :end-before: [pw_containers-intrusive_forward_list] 78 79If you need to add this item to containers of more than one type, see 80:ref:`module-pw_containers-multiple_containers`, 81 82API reference 83============= 84This class is similar to ``std::forward_list<T>``. Items to be added must derive 85from ``pw::IntrusiveForwardList<T>::Item``. 86 87.. doxygenclass:: pw::IntrusiveForwardList 88 :members: 89 90Performance considerations 91========================== 92Items only include pointers to the next item. To reach previous items, the list 93maintains a cycle of items so that the first item can be reached from the last. 94This structure means certain operations have linear complexity in terms of the 95number of items in the list, i.e. they are "O(n)": 96 97- Removing an item from a list using 98 ``pw::IntrusiveForwardList<T>::remove(const T&)``. 99- Getting the list size using ``pw::IntrusiveForwardList<T>::size()``. 100 101When using a ``pw::IntrusiveForwardList<T>`` in a performance-critical section 102or with many items, authors should prefer to avoid these methods. For example, 103it may be preferable to create items that together with their storage outlive 104the list. 105 106Notably, ``pw::IntrusiveForwardList<T>::end()`` is constant complexity (i.e. 107"O(1)"). As a result iterating over a list does not incur an additional penalty. 108 109.. _module-pw_containers-intrusivelist-size-report: 110 111Size reports 112------------ 113The tables below illustrate the following scenarios: 114 115* Scenarios related to ``IntrusiveList``: 116 117 * The memory and code size cost incurred by a adding a single 118 ``IntrusiveList``. 119 * The memory and code size cost incurred by adding another ``IntrusiveList`` 120 with a different type. As ``IntrusiveList`` is templated on type, this 121 results in additional code being generated. 122 123* Scenarios related to ``IntrusiveForwardList``: 124 125 * The memory and code size cost incurred by a adding a single 126 ``IntrusiveForwardList``. 127 * The memory and code size cost incurred by adding another 128 ``IntrusiveForwardList`` with a different type. As ``IntrusiveForwardList`` 129 is templated on type, this results in additional code being generated. 130 131* The memory and code size cost incurred by a adding both an ``IntrusiveList`` 132 and an ``IntrusiveForwardList`` of the same type. These types reuse code, so 133 the combined sum is less than the sum of its parts. 134 135.. TODO: b/388905812 - Re-enable the size report. 136.. .. include:: lists_size_report 137.. include:: ../size_report_notice 138