Line data Source code
1 : /*
2 : * Copyright (c) 2021 Project CHIP Authors
3 : *
4 : * Licensed under the Apache License, Version 2.0 (the "License");
5 : * you may not use this file except in compliance with the License.
6 : * You may obtain a copy of the License at
7 : *
8 : * http://www.apache.org/licenses/LICENSE-2.0
9 : *
10 : * Unless required by applicable law or agreed to in writing, software
11 : * distributed under the License is distributed on an "AS IS" BASIS,
12 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : * See the License for the specific language governing permissions and
14 : * limitations under the License.
15 : */
16 :
17 : #pragma once
18 :
19 : #include <iterator>
20 : #include <utility>
21 :
22 : #include <lib/support/CodeUtils.h>
23 :
24 : namespace chip {
25 :
26 : class IntrusiveListBase;
27 :
28 : enum class IntrusiveMode
29 : {
30 : // Strict mode features
31 : //
32 : // Node constructor puts the hook in a well-known default state.
33 : //
34 : // Node destructor checks if the hook is in the well-known default state.
35 : // If not, an assertion is raised.
36 : //
37 : // Every time an object is inserted in the intrusive container, the
38 : // container checks if the hook is in the well-known default state. If
39 : // not, an assertion is raised.
40 : //
41 : // Every time an object is being erased from the intrusive container, the
42 : // container puts the erased object in the well-known default state.
43 : //
44 : // Note: The strict mode works similar as safe mode for Boost.Intrusive
45 : //
46 : Strict,
47 :
48 : // Auto-unlink mode features
49 : //
50 : // When the destructor of the node is called, the hook checks if the node
51 : // is inserted in a container. If so, the hook removes the node from the
52 : // container.
53 : //
54 : // The hook has a member function called unlink() that can be used to
55 : // unlink the node from the container at any time, without having any
56 : // reference to the container, if the user wants to do so.
57 : //
58 : // This auto-unlink feature is useful in certain applications but it must
59 : // be used very carefully:
60 : //
61 : // If several threads are using the same container the destructor of the
62 : // auto-unlink hook will be called without any thread synchronization so
63 : // removing the object is thread-unsafe. Container contents change
64 : // silently without modifying the container directly. This can lead to
65 : // surprising effects.
66 : //
67 : // These auto-unlink hooks have also strict-mode properties:
68 : //
69 : // Node constructors put the hook in a well-known default state.
70 : //
71 : // Every time an object is inserted in the intrusive container, the
72 : // container checks if the hook is in the well-known default state. If
73 : // not, an assertion is raised.
74 : //
75 : // Every time an object is erased from an intrusive container, the
76 : // container puts the erased object in the well-known default state.
77 : //
78 : // Note: The strict mode works similar as auto-unlink mode for
79 : // Boost.Intrusive
80 : //
81 : AutoUnlink,
82 : };
83 :
84 : class IntrusiveListNodePrivateBase
85 : {
86 : public:
87 10 : IntrusiveListNodePrivateBase() : mPrev(nullptr), mNext(nullptr) {}
88 133987 : ~IntrusiveListNodePrivateBase() { VerifyOrDie(!IsInList()); }
89 :
90 : // Note: The copy construct/assignment is not provided because the list node state is not copyable.
91 : // The move construct/assignment is not provided because all modifications to the list shall go through the list object.
92 : IntrusiveListNodePrivateBase(const IntrusiveListNodePrivateBase &) = delete;
93 : IntrusiveListNodePrivateBase & operator=(const IntrusiveListNodePrivateBase &) = delete;
94 : IntrusiveListNodePrivateBase(IntrusiveListNodePrivateBase &&) = delete;
95 : IntrusiveListNodePrivateBase & operator=(IntrusiveListNodePrivateBase &&) = delete;
96 :
97 268419 : bool IsInList() const { return (mPrev != nullptr && mNext != nullptr); }
98 :
99 : private:
100 : friend class IntrusiveListBase;
101 134198 : IntrusiveListNodePrivateBase(IntrusiveListNodePrivateBase * prev, IntrusiveListNodePrivateBase * next) :
102 134198 : mPrev(prev), mNext(next)
103 134198 : {}
104 :
105 : void TakePlaceOf(const IntrusiveListNodePrivateBase * that)
106 : {
107 : // prerequisite `that` is in a list
108 : // `this` will take place of the position of `that`.
109 : // `that` will be emptied by the caller after this function
110 : mPrev = that->mPrev;
111 : mNext = that->mNext;
112 : mPrev->mNext = this;
113 : mNext->mPrev = this;
114 : }
115 :
116 8754 : void Prepend(IntrusiveListNodePrivateBase * node)
117 : {
118 8754 : VerifyOrDie(IsInList());
119 8754 : VerifyOrDie(!node->IsInList());
120 8754 : node->mPrev = mPrev;
121 8754 : node->mNext = this;
122 8754 : mPrev->mNext = node;
123 8754 : mPrev = node;
124 8754 : }
125 :
126 : void Append(IntrusiveListNodePrivateBase * node)
127 : {
128 : VerifyOrDie(IsInList());
129 : VerifyOrDie(!node->IsInList());
130 : node->mPrev = this;
131 : node->mNext = mNext;
132 : mNext->mPrev = node;
133 : mNext = node;
134 : }
135 :
136 : protected:
137 133976 : void Remove()
138 : {
139 133976 : VerifyOrDie(IsInList());
140 133976 : mPrev->mNext = mNext;
141 133976 : mNext->mPrev = mPrev;
142 133976 : mPrev = nullptr;
143 133976 : mNext = nullptr;
144 133976 : }
145 :
146 : private:
147 : IntrusiveListNodePrivateBase * mPrev;
148 : IntrusiveListNodePrivateBase * mNext;
149 : };
150 :
151 : // Strict mode implementation
152 : template <IntrusiveMode Mode = IntrusiveMode::Strict>
153 : class IntrusiveListNodeBase : public IntrusiveListNodePrivateBase
154 : {
155 : };
156 :
157 : // Partial specialization implementation for auto-unlink mode.
158 : template <>
159 : class IntrusiveListNodeBase<IntrusiveMode::AutoUnlink> : public IntrusiveListNodePrivateBase
160 : {
161 : public:
162 10 : ~IntrusiveListNodeBase() { Unlink(); }
163 10 : void Unlink()
164 : {
165 10 : if (IsInList())
166 0 : Remove();
167 10 : }
168 : };
169 :
170 : // Non-template part of IntrusiveList. It appears that for list structure, both mode can share same implementation.
171 : class IntrusiveListBase
172 : {
173 : public:
174 : class ConstIteratorBase
175 : {
176 : private:
177 : friend class IntrusiveListBase;
178 17490 : ConstIteratorBase(const IntrusiveListNodePrivateBase * cur) : mCurrent(cur) {}
179 :
180 37622 : const IntrusiveListNodePrivateBase & operator*() { return *mCurrent; }
181 :
182 : public:
183 : using difference_type = std::ptrdiff_t;
184 : using iterator_category = std::bidirectional_iterator_tag;
185 :
186 : ConstIteratorBase(const ConstIteratorBase &) = default;
187 : ConstIteratorBase(ConstIteratorBase &&) = default;
188 : ConstIteratorBase & operator=(const ConstIteratorBase &) = default;
189 : ConstIteratorBase & operator=(ConstIteratorBase &&) = default;
190 :
191 37622 : bool operator==(const ConstIteratorBase & that) const { return mCurrent == that.mCurrent; }
192 37622 : bool operator!=(const ConstIteratorBase & that) const { return !(*this == that); }
193 :
194 28877 : ConstIteratorBase & operator++()
195 : {
196 28877 : mCurrent = mCurrent->mNext;
197 28877 : return *this;
198 : }
199 :
200 : ConstIteratorBase operator++(int)
201 : {
202 : ConstIteratorBase res(mCurrent);
203 : mCurrent = mCurrent->mNext;
204 : return res;
205 : }
206 :
207 : ConstIteratorBase & operator--()
208 : {
209 : mCurrent = mCurrent->mPrev;
210 : return *this;
211 : }
212 :
213 : ConstIteratorBase operator--(int)
214 : {
215 : ConstIteratorBase res(mCurrent);
216 : mCurrent = mCurrent->mPrev;
217 : return res;
218 : }
219 :
220 : protected:
221 : const IntrusiveListNodePrivateBase * mCurrent;
222 : };
223 :
224 : class IteratorBase
225 : {
226 : private:
227 : friend class IntrusiveListBase;
228 749 : IteratorBase(IntrusiveListNodePrivateBase * cur) : mCurrent(cur) {}
229 :
230 : IntrusiveListNodePrivateBase & operator*() { return *mCurrent; }
231 :
232 : public:
233 : using difference_type = std::ptrdiff_t;
234 : using iterator_category = std::bidirectional_iterator_tag;
235 :
236 : IteratorBase(const IteratorBase &) = default;
237 : IteratorBase(IteratorBase &&) = default;
238 : IteratorBase & operator=(const IteratorBase &) = default;
239 : IteratorBase & operator=(IteratorBase &&) = default;
240 :
241 13201515 : bool operator==(const IteratorBase & that) const { return mCurrent == that.mCurrent; }
242 13201515 : bool operator!=(const IteratorBase & that) const { return !(*this == that); }
243 :
244 169 : IteratorBase & operator++()
245 : {
246 169 : mCurrent = mCurrent->mNext;
247 169 : return *this;
248 : }
249 :
250 8 : IteratorBase operator++(int)
251 : {
252 8 : IteratorBase res(mCurrent);
253 8 : mCurrent = mCurrent->mNext;
254 8 : return res;
255 : }
256 :
257 : IteratorBase & operator--()
258 : {
259 : mCurrent = mCurrent->mPrev;
260 : return *this;
261 : }
262 :
263 : IteratorBase operator--(int)
264 : {
265 : IteratorBase res(mCurrent);
266 : mCurrent = mCurrent->mPrev;
267 : return res;
268 : }
269 :
270 : protected:
271 : IntrusiveListNodePrivateBase * mCurrent;
272 : };
273 :
274 267425 : bool Empty() const { return mNode.mNext == &mNode; }
275 :
276 0 : void Erase(IteratorBase pos) { pos.mCurrent->Remove(); }
277 :
278 : protected:
279 : // The list is formed as a ring with mNode being the end.
280 : //
281 : // begin end
282 : // v v
283 : // item(first) -> item -> ... -> item(last) -> mNode
284 : // ^ |
285 : // \------------------------------------------/
286 : //
287 134198 : IntrusiveListBase() : mNode(&mNode, &mNode) {}
288 133773 : ~IntrusiveListBase()
289 : {
290 133773 : VerifyOrDie(Empty());
291 : /* clear mNode such that the destructor checking mNode.IsInList doesn't fail */
292 133773 : mNode.Remove();
293 133773 : }
294 :
295 : IntrusiveListBase(const IntrusiveListBase &) = delete;
296 : IntrusiveListBase & operator=(const IntrusiveListBase &) = delete;
297 :
298 : IntrusiveListBase(IntrusiveListBase && that) : mNode(&mNode, &mNode) { *this = std::move(that); }
299 :
300 : IntrusiveListBase & operator=(IntrusiveListBase && that)
301 : {
302 : VerifyOrDie(Empty());
303 : if (!that.Empty())
304 : {
305 : mNode.TakePlaceOf(&that.mNode);
306 : that.mNode.mNext = &that.mNode;
307 : that.mNode.mPrev = &that.mNode;
308 : }
309 : else
310 : {
311 : // Do nothing here if that is empty, because there is a prerequisite that `this` is empty.
312 : }
313 : return *this;
314 : }
315 :
316 8745 : ConstIteratorBase begin() const { return ConstIteratorBase(mNode.mNext); }
317 8745 : ConstIteratorBase end() const { return ConstIteratorBase(&mNode); }
318 365 : IteratorBase begin() { return IteratorBase(mNode.mNext); }
319 13201420 : IteratorBase end() { return IteratorBase(&mNode); }
320 :
321 : void PushFront(IntrusiveListNodePrivateBase * node) { mNode.Append(node); }
322 8754 : void PushBack(IntrusiveListNodePrivateBase * node) { mNode.Prepend(node); }
323 :
324 : void InsertBefore(IteratorBase pos, IntrusiveListNodePrivateBase * node) { pos.mCurrent->Prepend(node); }
325 : void InsertAfter(IteratorBase pos, IntrusiveListNodePrivateBase * node) { pos.mCurrent->Append(node); }
326 6891 : void Remove(IntrusiveListNodePrivateBase * node) { node->Remove(); }
327 :
328 : /// @brief Replace an original node in list with a new node.
329 : void Replace(IntrusiveListNodePrivateBase * original, IntrusiveListNodePrivateBase * replacement)
330 : {
331 : // VerifyOrDie(Contains(original)); This check is too heavy to do, but it shall hold
332 : VerifyOrDie(!replacement->IsInList());
333 : replacement->TakePlaceOf(original);
334 : original->mPrev = nullptr;
335 : original->mNext = nullptr;
336 : }
337 :
338 8745 : bool Contains(const IntrusiveListNodePrivateBase * node) const
339 : {
340 37622 : for (auto & iter : *this)
341 : {
342 37622 : if (&iter == node)
343 8745 : return true;
344 : }
345 0 : return false;
346 : }
347 :
348 : private:
349 : IntrusiveListNodePrivateBase mNode;
350 : };
351 :
352 : /// The hook converts between node object T and IntrusiveListNodeBase
353 : ///
354 : /// When using this hook, the node type (T) MUST inherit from IntrusiveListNodeBase.
355 : ///
356 : template <typename T, IntrusiveMode Mode>
357 : class IntrusiveListBaseHook
358 : {
359 : public:
360 : static_assert(std::is_base_of<IntrusiveListNodeBase<Mode>, T>::value, "T must be derived from IntrusiveListNodeBase");
361 :
362 183 : static T * ToObject(IntrusiveListNodePrivateBase * node) { return static_cast<T *>(node); }
363 : static const T * ToObject(const IntrusiveListNodePrivateBase * node) { return static_cast<T *>(node); }
364 :
365 : static T * ToObject(IntrusiveListNodeBase<Mode> * node) { return static_cast<T *>(node); }
366 : static const T * ToObject(const IntrusiveListNodeBase<Mode> * node) { return static_cast<T *>(node); }
367 :
368 17508 : static IntrusiveListNodeBase<Mode> * ToNode(T * object) { return static_cast<IntrusiveListNodeBase<Mode> *>(object); }
369 8745 : static const IntrusiveListNodeBase<Mode> * ToNode(const T * object)
370 : {
371 8745 : return static_cast<const IntrusiveListNodeBase<Mode> *>(object);
372 : }
373 : };
374 :
375 : /// A double-linked list where the data is stored together with the previous/next pointers for cache efficiency / and compactness.
376 : ///
377 : /// The default hook (IntrusiveListBaseHook<T>) requires T to inherit from IntrusiveListNodeBase.
378 : ///
379 : /// Consumers must ensure that the IntrusiveListNodeBase object associated with
380 : /// a node is removed from any list it might belong to before it is destroyed.
381 : ///
382 : /// Consumers must ensure that a list is empty before it is destroyed.
383 : ///
384 : /// A node may only belong to a single list. The code will assert (via VerifyOrDie) on this invariant.
385 : ///
386 : /// Example usage:
387 : ///
388 : /// class ListNode : public IntrusiveListNodeBase {};
389 : /// // ...
390 : /// ListNode a,b,c;
391 : /// IntrusiveList<ListNode> list; // NOTE: node lifetime >= list lifetime
392 : ///
393 : /// list.PushBack(&a);
394 : /// list.PushFront(&b);
395 : /// assert(list.Contains(&a) && list.Contains(&b) && !list.Contains(&c));
396 : /// list.Remove(&a);
397 : /// list.Remove(&b);
398 : template <typename T, IntrusiveMode Mode = IntrusiveMode::Strict, typename Hook = IntrusiveListBaseHook<T, Mode>>
399 : class IntrusiveList : public IntrusiveListBase
400 : {
401 : public:
402 134930 : IntrusiveList() : IntrusiveListBase() {}
403 :
404 : IntrusiveList(IntrusiveList &&) = default;
405 : IntrusiveList & operator=(IntrusiveList &&) = default;
406 :
407 : class ConstIterator : public IntrusiveListBase::ConstIteratorBase
408 : {
409 : public:
410 : using value_type = const T;
411 : using pointer = const T *;
412 : using reference = const T &;
413 :
414 : ConstIterator(IntrusiveListBase::ConstIteratorBase && base) : IntrusiveListBase::ConstIteratorBase(std::move(base)) {}
415 : const T * operator->() { return Hook::ToObject(mCurrent); }
416 : const T & operator*() { return *Hook::ToObject(mCurrent); }
417 :
418 : ConstIterator & operator++() { return static_cast<ConstIterator &>(IntrusiveListBase::ConstIteratorBase::operator++()); }
419 : ConstIterator operator++(int) { return IntrusiveListBase::ConstIteratorBase::operator++(1); }
420 : ConstIterator & operator--() { return static_cast<ConstIterator &>(IntrusiveListBase::ConstIteratorBase::operator--()); }
421 : ConstIterator operator--(int) { return IntrusiveListBase::ConstIteratorBase::operator--(1); }
422 : };
423 :
424 : class Iterator : public IntrusiveListBase::IteratorBase
425 : {
426 : public:
427 : using value_type = T;
428 : using pointer = T *;
429 : using reference = T &;
430 :
431 26407295 : Iterator(IntrusiveListBase::IteratorBase && base) : IntrusiveListBase::IteratorBase(std::move(base)) {}
432 72 : T * operator->() { return Hook::ToObject(mCurrent); }
433 111 : T & operator*() { return *Hook::ToObject(mCurrent); }
434 :
435 169 : Iterator & operator++() { return static_cast<Iterator &>(IntrusiveListBase::IteratorBase::operator++()); }
436 8 : Iterator operator++(int) { return IntrusiveListBase::IteratorBase::operator++(1); }
437 : Iterator & operator--() { return static_cast<Iterator &>(IntrusiveListBase::IteratorBase::operator--()); }
438 : Iterator operator--(int) { return IntrusiveListBase::IteratorBase::operator--(1); }
439 : };
440 :
441 : ConstIterator begin() const { return IntrusiveListBase::begin(); }
442 : ConstIterator end() const { return IntrusiveListBase::end(); }
443 13203638 : Iterator begin() { return IntrusiveListBase::begin(); }
444 13203707 : Iterator end() { return IntrusiveListBase::end(); }
445 : void PushFront(T * value) { IntrusiveListBase::PushFront(Hook::ToNode(value)); }
446 8754 : void PushBack(T * value) { IntrusiveListBase::PushBack(Hook::ToNode(value)); }
447 : void InsertBefore(Iterator pos, T * value) { IntrusiveListBase::InsertBefore(pos, Hook::ToNode(value)); }
448 : void InsertAfter(Iterator pos, T * value) { IntrusiveListBase::InsertAfter(pos, Hook::ToNode(value)); }
449 8754 : void Remove(T * value) { IntrusiveListBase::Remove(Hook::ToNode(value)); }
450 : void Replace(T * original, T * replacement) { IntrusiveListBase::Replace(Hook::ToNode(original), Hook::ToNode(replacement)); }
451 8745 : bool Contains(const T * value) const { return IntrusiveListBase::Contains(Hook::ToNode(value)); }
452 :
453 103 : void Clear()
454 : {
455 103 : while (begin() != end())
456 : {
457 0 : Remove(&(*begin()));
458 : }
459 103 : }
460 : };
461 :
462 : } // namespace chip
|
