Kiwano Engine v1.3.x
IntrusiveList.h
1// Copyright (c) 2016-2018 Kiwano - Nomango
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in
11// all copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19// THE SOFTWARE.
20
21#pragma once
22#include <type_traits>
23#include <iterator>
24#include <stdexcept>
25#include <kiwano/macros.h>
26
27namespace kiwano
28{
29
32template <typename _PtrTy>
34{
35public:
36 using value_type = typename std::pointer_traits<_PtrTy>::pointer;
37 using pointer = value_type*;
38 using reference = value_type&;
39
41 : first_()
42 , last_()
43 {
44 }
45
47 {
48 Clear();
49 }
50
53 const value_type& GetFirst() const
54 {
55 return first_;
56 }
57
60 value_type& GetFirst()
61 {
62 return first_;
63 }
64
67 const value_type& GetLast() const
68 {
69 return last_;
70 }
71
74 value_type& GetLast()
75 {
76 return last_;
77 }
78
81 inline bool IsEmpty() const
82 {
83 return first_ == nullptr;
84 }
85
88 void PushBack(reference child)
89 {
90 if (child->prev_)
91 child->prev_->next_ = child->next_;
92 if (child->next_)
93 child->next_->prev_ = child->prev_;
94
95 child->prev_ = last_;
96 child->next_ = nullptr;
97
98 if (first_)
99 {
100 last_->next_ = child;
101 }
102 else
103 {
104 first_ = child;
105 }
106
107 last_ = child;
108 }
109
112 void PushFront(reference child)
113 {
114 if (child->prev_)
115 child->prev_->next_ = child->next_;
116 if (child->next_)
117 child->next_->prev_ = child->prev_;
118
119 child->prev_ = nullptr;
120 child->next_ = first_;
121
122 if (first_)
123 {
124 first_->prev_ = child;
125 }
126 else
127 {
128 last_ = child;
129 }
130
131 first_ = child;
132 }
133
136 void InsertBefore(reference child, reference before)
137 {
138 if (child->prev_)
139 child->prev_->next_ = child->next_;
140 if (child->next_)
141 child->next_->prev_ = child->prev_;
142
143 if (before->prev_)
144 before->prev_->next_ = child;
145 else
146 first_ = child;
147
148 child->prev_ = before->prev_;
149 child->next_ = before;
150 before->prev_ = child;
151 }
152
155 void InsertAfter(reference child, reference after)
156 {
157 if (child->prev_)
158 child->prev_->next_ = child->next_;
159 if (child->next_)
160 child->next_->prev_ = child->prev_;
161
162 if (after->next_)
163 after->next_->prev_ = child;
164 else
165 last_ = child;
166
167 child->next_ = after->next_;
168 child->prev_ = after;
169 after->next_ = child;
170 }
171
174 void Remove(reference child)
175 {
176 if (child->next_)
177 {
178 child->next_->prev_ = child->prev_;
179 }
180 else
181 {
182 last_ = child->prev_;
183 }
184
185 if (child->prev_)
186 {
187 child->prev_->next_ = child->next_;
188 }
189 else
190 {
191 first_ = child->next_;
192 }
193
194 child->prev_ = nullptr;
195 child->next_ = nullptr;
196 }
197
200 void Clear()
201 {
202 value_type p = first_;
203 while (p)
204 {
205 value_type tmp = p;
206 p = p->next_;
207 if (tmp)
208 {
209 tmp->next_ = nullptr;
210 tmp->prev_ = nullptr;
211 }
212 }
213 first_ = nullptr;
214 last_ = nullptr;
215 }
216
220 {
221 if (!first_)
222 return true;
223
224 int pos = 0;
225
226 value_type p = first_;
227 value_type tmp = p;
228 do
229 {
230 tmp = p;
231 p = p->next_;
232 ++pos;
233
234 if (p)
235 {
236 if (p->prev_ != tmp)
237 return false;
238 }
239 else
240 {
241 if (tmp != last_)
242 return false;
243 }
244 } while (p);
245 return true;
246 }
247
248public:
249 template <typename _IterPtrTy>
250 struct Iterator
251 {
252 using iterator_category = std::bidirectional_iterator_tag;
253 using value_type = _IterPtrTy;
254 using pointer = _IterPtrTy*;
255 using reference = _IterPtrTy&;
256 using difference_type = ptrdiff_t;
257
258 inline Iterator(value_type ptr = nullptr, bool is_end = false)
259 : base_(ptr)
260 , is_end_(is_end)
261 {
262 }
263
264 inline reference operator*() const
265 {
266 KGE_ASSERT(base_ && !is_end_);
267 return const_cast<reference>(base_);
268 }
269
270 inline pointer operator->() const
271 {
272 return std::pointer_traits<pointer>::pointer_to(**this);
273 }
274
275 inline Iterator& operator++()
276 {
277 KGE_ASSERT(base_ && !is_end_);
278 value_type next = base_->GetNext();
279 if (next)
280 base_ = next;
281 else
282 is_end_ = true;
283 return (*this);
284 }
285
286 inline Iterator operator++(int)
287 {
288 Iterator old = (*this);
289 ++(*this);
290 return old;
291 }
292
293 inline Iterator& operator--()
294 {
295 KGE_ASSERT(base_);
296 if (is_end_)
297 is_end_ = false;
298 else
299 base_ = base_->GetPrev();
300 return (*this);
301 }
302
303 inline Iterator operator--(int)
304 {
305 Iterator old = (*this);
306 --(*this);
307 return old;
308 }
309
310 inline bool operator==(const Iterator& other) const
311 {
312 return base_ == other.base_ && is_end_ == other.is_end_;
313 }
314
315 inline bool operator!=(const Iterator& other) const
316 {
317 return !(*this == other);
318 }
319
320 inline operator bool() const
321 {
322 return base_ != nullptr && !is_end_;
323 }
324
325 private:
326 bool is_end_;
327
328 typename std::remove_const<value_type>::type base_;
329 };
330
331public:
334 using reverse_iterator = std::reverse_iterator<iterator>;
335 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
336
337 inline iterator begin()
338 {
339 return iterator(first_, first_ == nullptr);
340 }
341
342 inline const_iterator begin() const
343 {
344 return const_iterator(first_, first_ == nullptr);
345 }
346
347 inline const_iterator cbegin() const
348 {
349 return begin();
350 }
351
352 inline iterator end()
353 {
354 return iterator(last_, true);
355 }
356
357 inline const_iterator end() const
358 {
359 return const_iterator(last_, true);
360 }
361
362 inline const_iterator cend() const
363 {
364 return end();
365 }
366
367 inline reverse_iterator rbegin()
368 {
369 return reverse_iterator(end());
370 }
371
372 inline const_reverse_iterator rbegin() const
373 {
374 return const_reverse_iterator(end());
375 }
376
377 inline const_reverse_iterator crbegin() const
378 {
379 return rbegin();
380 }
381
382 inline reverse_iterator rend()
383 {
384 return reverse_iterator(begin());
385 }
386
387 inline const_reverse_iterator rend() const
388 {
389 return const_reverse_iterator(begin());
390 }
391
392 inline const_reverse_iterator crend() const
393 {
394 return rend();
395 }
396
397 inline value_type& front()
398 {
399 if (IsEmpty())
400 throw std::out_of_range("front() called on empty list");
401 return first_;
402 }
403
404 inline const value_type& front() const
405 {
406 if (IsEmpty())
407 throw std::out_of_range("front() called on empty list");
408 return first_;
409 }
410
411 inline value_type& back()
412 {
413 if (IsEmpty())
414 throw std::out_of_range("back() called on empty list");
415 return last_;
416 }
417
418 inline const value_type& back() const
419 {
420 if (IsEmpty())
421 throw std::out_of_range("back() called on empty list");
422 return last_;
423 }
424
425private:
426 value_type first_;
427 value_type last_;
428};
429
432template <typename _PtrTy>
434{
435public:
436 using value_type = typename std::pointer_traits<_PtrTy>::pointer;
437 using reference = value_type&;
438 using pointer = value_type*;
439
441 : prev_(nullptr)
442 , next_(nullptr)
443 {
444 }
445
446 IntrusiveListValue(value_type rhs)
447 : prev_(nullptr)
448 , next_(nullptr)
449 {
450 if (rhs)
451 {
452 prev_ = rhs->prev_;
453 next_ = rhs->next_;
454 }
455 }
456
459 const value_type& GetPrev() const
460 {
461 return prev_;
462 }
463
466 value_type& GetPrev()
467 {
468 return prev_;
469 }
470
473 const value_type& GetNext() const
474 {
475 return next_;
476 }
477
480 value_type& GetNext()
481 {
482 return next_;
483 }
484
485private:
486 value_type prev_;
487 value_type next_;
488
489 friend class IntrusiveList<_PtrTy>;
490};
491
492} // namespace kiwano
侵入式链表元素
Definition: IntrusiveList.h:434
const value_type & GetPrev() const
获取前一元素
Definition: IntrusiveList.h:459
value_type & GetNext()
获取下一元素
Definition: IntrusiveList.h:480
const value_type & GetNext() const
获取下一元素
Definition: IntrusiveList.h:473
value_type & GetPrev()
获取前一元素
Definition: IntrusiveList.h:466
侵入式链表
Definition: IntrusiveList.h:34
value_type & GetFirst()
获取首元素
Definition: IntrusiveList.h:60
void InsertBefore(reference child, reference before)
在链表的对象前插入新对象
Definition: IntrusiveList.h:136
void Clear()
清空所有对象
Definition: IntrusiveList.h:200
const value_type & GetFirst() const
获取首元素
Definition: IntrusiveList.h:53
value_type & GetLast()
获取尾元素
Definition: IntrusiveList.h:74
void PushBack(reference child)
在链表尾部添加对象
Definition: IntrusiveList.h:88
void InsertAfter(reference child, reference after)
在链表的对象后插入新对象
Definition: IntrusiveList.h:155
void Remove(reference child)
移除对象
Definition: IntrusiveList.h:174
bool IsEmpty() const
链表是否为空
Definition: IntrusiveList.h:81
void PushFront(reference child)
在链表头部添加对象
Definition: IntrusiveList.h:112
bool CheckValid()
检查链表是否有效
Definition: IntrusiveList.h:219
const value_type & GetLast() const
获取尾元素
Definition: IntrusiveList.h:67
Definition: IntrusiveList.h:251