1.. _module-pw_containers-queues: 2 3====== 4Queues 5====== 6.. pigweed-module-subpage:: 7 :name: pw_containers 8 9A queue is an ordered collection designed to add items at one end and remove 10them from the other. This allows "first in, first out", or FIFO, behavior. 11Pigweed provides both single and double-ended queues that are backed by fixed 12storage. 13 14--------------- 15pw::InlineDeque 16--------------- 17.. doxygentypedef:: pw::InlineDeque 18 19.. TODO: b/394341806 - Add missing examples 20.. Example 21.. ======= 22.. .. literalinclude:: examples/inline_deque.cc 23.. :language: cpp 24.. :linenos: 25.. :start-after: [pw_containers-inline_deque] 26.. :end-before: [pw_containers-inline_deque] 27 28API reference 29============= 30.. doxygenclass:: pw::BasicInlineDeque 31 :members: 32 33--------------- 34pw::InlineQueue 35--------------- 36.. doxygentypedef:: pw::InlineQueue 37 38.. TODO: b/394341806 - Add missing examples 39.. Example 40.. ======= 41.. .. literalinclude:: examples/inline_deque.cc 42.. :language: cpp 43.. :linenos: 44.. :start-after: [pw_containers-inline_deque] 45.. :end-before: [pw_containers-inline_deque] 46 47API reference 48============= 49.. doxygenclass:: pw::BasicInlineQueue 50 :members: 51 52.. _module-pw_containers-queues-inline_var_len_entry_queue: 53 54-------------------------- 55pw::InlineVarLenEntryQueue 56-------------------------- 57.. doxygenfile:: pw_containers/inline_var_len_entry_queue.h 58 :sections: detaileddescription 59 60.. TODO: b/394341806 - Move code to compiled examples 61 62Example 63======= 64.. tab-set:: 65 66 .. tab-item:: C++ 67 :sync: c++ 68 69 Queues are declared with their max size 70 (``InlineVarLenEntryQueue<kMaxSize>``) but may be used without 71 specifying the size (``InlineVarLenEntryQueue<>&``). 72 73 .. code-block:: c++ 74 75 // Declare a queue with capacity sufficient for one 10-byte entry or 76 // multiple smaller entries. 77 pw::InlineVarLenEntryQueue<10> queue; 78 79 // Push an entry, asserting if the entry does not fit. 80 queue.push(queue, data) 81 82 // Use push_overwrite() to push entries, overwriting older entries 83 // as needed. 84 queue.push_overwrite(queue, more_data) 85 86 // Remove an entry. 87 queue.pop(); 88 89 Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an 90 existing ``uint32_t`` array. 91 92 .. code-block:: c++ 93 94 // Initialize a InlineVarLenEntryQueue. 95 uint32_t buffer[32]; 96 auto& queue = pw::InlineVarLenEntryQueue<>::Init(buffer); 97 98 // Largest supported entry is 114 B (13 B overhead + 1 B prefix) 99 assert(queue.max_size_bytes() == 114u); 100 101 // Write data 102 queue.push_overwrite(data); 103 104 .. tab-item:: C 105 :sync: c 106 107 A ``InlineVarLenEntryQueue`` may be declared and initialized in C with the 108 :c:macro:`PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE` macro. 109 110 .. code-block:: c 111 112 // Declare a queue with capacity sufficient for one 10-byte entry or 113 // multiple smaller entries. 114 PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 10); 115 116 // Push an entry, asserting if the entry does not fit. 117 pw_InlineVarLenEntryQueue_Push(queue, "12345", 5); 118 119 // Use push_overwrite() to push entries, overwriting older entries 120 // as needed. 121 pw_InlineVarLenEntryQueue_PushOverwrite(queue, "abcdefg", 7); 122 123 // Remove an entry. 124 pw_InlineVarLenEntryQueue_Pop(queue); 125 126 Alternately, a ``InlineVarLenEntryQueue`` may be initialized in an 127 existing ``uint32_t`` array. 128 129 .. code-block:: c 130 131 // Initialize a InlineVarLenEntryQueue. 132 uint32_t buffer[32]; 133 pw_InlineVarLenEntryQueue_Init(buffer, 32); 134 135 // Largest supported entry is 114 B (13 B overhead + 1 B prefix) 136 assert(pw_InlineVarLenEntryQueue_MaxSizeBytes(buffer) == 114u); 137 138 // Write some data 139 pw_InlineVarLenEntryQueue_PushOverwrite(buffer, "123", 3); 140 141API reference 142============= 143C++ 144--- 145.. doxygengroup:: inline_var_len_entry_queue_cpp_api 146 :content-only: 147 :members: 148 149C 150- 151.. doxygengroup:: inline_var_len_entry_queue_c_api 152 :content-only: 153 154Python 155------ 156.. automodule:: pw_containers.inline_var_len_entry_queue 157 :members: 158 159Queue vs. deque 160=============== 161This module provides 162:ref:`module-pw_containers-queues-inline_var_len_entry_queue`, but no 163corresponding ``InlineVarLenEntryDeque`` class. Following the C++ Standard 164Library style, the deque class would provide ``push_front()`` and ``pop_back()`` 165operations in addition to ``push_back()`` and ``pop_front()`` (equivalent to a 166queue's ``push()`` and ``pop()``). 167 168There is no ``InlineVarLenEntryDeque`` class because there is no efficient way 169to implement ``push_front()`` and ``pop_back()``. These operations would 170necessarily be ``O(n)``, since each entry knows the position of the next entry, 171but not the previous, as in a single-linked list. Given that these operations 172would be inefficient and unlikely to be used, they are not implemented, and only 173a queue class is provided. 174 175Size reports 176------------ 177The tables below illustrate the following scenarios: 178 179.. TODO: b/394341806 - Add size report for InlineVarLenEntryQueue. 180 181* Scenarios related to ``InlineDeque``: 182 183 * The memory and code size cost incurred by a adding a single ``InlineDeque``. 184 * The memory and code size cost incurred by adding another ``InlineDeque`` 185 with a different type. As ``InlineDeque`` is templated on type, this 186 results in additional code being generated. 187 188* Scenarios related to ``InlineQueue``: 189 190 * The memory and code size cost incurred by a adding a single ``InlineQueue``. 191 * The memory and code size cost incurred by adding another ``InlineQueue`` 192 with a different type. As ``InlineQueue`` is templated on type, this results 193 in additional code being generated. 194 195* The memory and code size cost incurred by a adding both an ``InlineDeque`` and 196 an ``InlineQueue`` of the same type. These types reuse code, so the combined 197 sum is less than the sum of its parts. 198 199.. TODO: b/388905812 - Re-enable the size report. 200.. .. include:: queues_size_report 201.. include:: ../size_report_notice 202