Embedded Template Library 1.0
intrusive_queue.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2016 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_INTRUSIVE_QUEUE_INCLUDED
32#define ETL_INTRUSIVE_QUEUE_INCLUDED
33
34#include "platform.h"
35#include "type_traits.h"
36#include "error_handler.h"
37#include "intrusive_links.h"
38
39#include <stddef.h>
40
41namespace etl
42{
43 //***************************************************************************
46 //***************************************************************************
48 {
49 public:
50
51 intrusive_queue_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
52 : exception(reason_, file_name_, line_number_)
53 {
54 }
55 };
56
57 //***************************************************************************
60 //***************************************************************************
62 {
63 public:
64
65 intrusive_queue_empty(string_type file_name_, numeric_type line_number_)
66 : intrusive_queue_exception(ETL_ERROR_TEXT("intrusive_queue:empty", ETL_INTRUSIVE_QUEUE_FILE_ID"A"), file_name_, line_number_)
67 {
68 }
69 };
70
71 //***************************************************************************
74 //***************************************************************************
76 {
77 public:
78
79 intrusive_queue_value_is_already_linked(string_type file_name_, numeric_type line_number_)
80 : intrusive_queue_exception(ETL_ERROR_TEXT("intrusive_queue:value is already linked", ETL_INTRUSIVE_QUEUE_FILE_ID"B"), file_name_, line_number_)
81 {
82 }
83 };
84
85 //***************************************************************************
89 //***************************************************************************
90 template <typename TLink>
92 {
93 public:
94
95 // Node typedef.
96 typedef TLink link_type;
97
98 //*************************************************************************
101 //*************************************************************************
102 void push(link_type& value)
103 {
104 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_queue_value_is_already_linked));
105
106 if (empty())
107 {
108 terminator.etl_next = &value;
109 }
110 else
111 {
112 p_back->etl_next = &value;
113 }
114
115 p_back = &value;
116 value.etl_next = &terminator;
117
118 ++current_size;
119 }
120
121 //*************************************************************************
124 //*************************************************************************
125 void pop()
126 {
127#if defined(ETL_CHECK_PUSH_POP)
128 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(intrusive_queue_empty));
129#endif
130
131 link_type* p_front = terminator.etl_next;
132
133 link_type* p_next = p_front->etl_next;
134 terminator.etl_next = p_next;
135
136 p_front->clear();
137
138 if (empty())
139 {
141 }
142
143 --current_size;
144 }
145
146 //*************************************************************************
150 //*************************************************************************
151 template <typename TContainer>
152 void pop_into(TContainer& destination)
153 {
154 link_type* p_link = terminator.etl_next;
155 pop();
156 destination.push(*p_link);
157 }
158
159 //*************************************************************************
161 //*************************************************************************
162 void clear()
163 {
164 while (!empty())
165 {
166 pop();
167 }
168
169 current_size = 0;
170 }
171
172 //*************************************************************************
174 //*************************************************************************
175 bool empty() const
176 {
177 return current_size == 0;
178 }
179
180 //*************************************************************************
182 //*************************************************************************
183 size_t size() const
184 {
185 return current_size;
186 }
187
188 protected:
189
190 //*************************************************************************
192 //*************************************************************************
194 : p_back (&terminator)
195 , current_size(0)
196 {
197 terminator.etl_next = &terminator;
198 }
199
200 //*************************************************************************
202 //*************************************************************************
204 {
205 }
206
207 link_type* p_back;
208 link_type terminator;
209
211 };
212
213 //***************************************************************************
219 //***************************************************************************
220 template <typename TValue, typename TLink>
222 {
223 public:
224
225 // Node typedef.
226 typedef typename etl::intrusive_queue_base<TLink> link_type;
227
228 // STL style typedefs.
229 typedef TValue value_type;
230 typedef value_type* pointer;
231 typedef const value_type* const_pointer;
232 typedef value_type& reference;
233 typedef const value_type& const_reference;
234 typedef size_t size_type;
235
236 //*************************************************************************
238 //*************************************************************************
240 : intrusive_queue_base<TLink>()
241 {
242 }
243
244 //*************************************************************************
248 //*************************************************************************
249 reference front()
250 {
251 return *static_cast<TValue*>(this->terminator.etl_next);
252 }
253
254 //*************************************************************************
258 //*************************************************************************
259 reference back()
260 {
261 return *static_cast<TValue*>(this->p_back);
262 }
263
264 //*************************************************************************
268 //*************************************************************************
269 const_reference front() const
270 {
271 return *static_cast<const TValue*>(this->terminator.etl_next);
272 }
273
274 //*************************************************************************
278 //*************************************************************************
279 const_reference back() const
280 {
281 return *static_cast<const TValue*>(this->p_back);
282 }
283
284 private:
285
286 // Disable copy construction and assignment.
288 intrusive_queue& operator = (const intrusive_queue& rhs);
289 };
290}
291
292#endif
Definition: intrusive_queue.h:62
Definition: intrusive_queue.h:48
Definition: intrusive_queue.h:76
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
void pop_into(TContainer &destination)
Definition: intrusive_queue.h:152
const_reference front() const
Definition: intrusive_queue.h:269
const_reference back() const
Definition: intrusive_queue.h:279
reference back()
Definition: intrusive_queue.h:259
size_t current_size
Counts the number of elements in the list.
Definition: intrusive_queue.h:210
void pop()
Definition: intrusive_queue.h:125
link_type terminator
This link terminates the queue and points to the front of the queue.
Definition: intrusive_queue.h:208
bool empty() const
Checks if the queue is in the empty state.
Definition: intrusive_queue.h:175
intrusive_queue()
Constructor.
Definition: intrusive_queue.h:239
~intrusive_queue_base()
Destructor.
Definition: intrusive_queue.h:203
void push(link_type &value)
Definition: intrusive_queue.h:102
reference front()
Definition: intrusive_queue.h:249
link_type * p_back
Pointer to the current back of the queue.
Definition: intrusive_queue.h:207
void clear()
Clears the queue to the empty state.
Definition: intrusive_queue.h:162
intrusive_queue_base()
Constructor.
Definition: intrusive_queue.h:193
size_t size() const
Returns the number of elements.
Definition: intrusive_queue.h:183
Definition: intrusive_queue.h:222
Definition: intrusive_queue.h:92
bitset_ext
Definition: absolute.h:38