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      133881 :     ~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      268087 :     bool IsInList() const { return (mPrev != nullptr && mNext != nullptr); }
      98             : 
      99             : private:
     100             :     friend class IntrusiveListBase;
     101      134151 :     IntrusiveListNodePrivateBase(IntrusiveListNodePrivateBase * prev, IntrusiveListNodePrivateBase * next) :
     102      134151 :         mPrev(prev), mNext(next)
     103      134151 :     {}
     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        8136 :     void Prepend(IntrusiveListNodePrivateBase * node)
     117             :     {
     118        8136 :         VerifyOrDie(IsInList());
     119        8136 :         VerifyOrDie(!node->IsInList());
     120        8136 :         node->mPrev  = mPrev;
     121        8136 :         node->mNext  = this;
     122        8136 :         mPrev->mNext = node;
     123        8136 :         mPrev        = node;
     124        8136 :     }
     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      133880 :     void Remove()
     138             :     {
     139      133880 :         VerifyOrDie(IsInList());
     140      133880 :         mPrev->mNext = mNext;
     141      133880 :         mNext->mPrev = mPrev;
     142      133880 :         mPrev        = nullptr;
     143      133880 :         mNext        = nullptr;
     144      133880 :     }
     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             :     ~IntrusiveListNodeBase() { Unlink(); }
     163             :     void Unlink()
     164             :     {
     165             :         if (IsInList())
     166             :             Remove();
     167             :     }
     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       16258 :         ConstIteratorBase(const IntrusiveListNodePrivateBase * cur) : mCurrent(cur) {}
     179             : 
     180       36364 :         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       36364 :         bool operator==(const ConstIteratorBase & that) const { return mCurrent == that.mCurrent; }
     192       36364 :         bool operator!=(const ConstIteratorBase & that) const { return !(*this == that); }
     193             : 
     194       28235 :         ConstIteratorBase & operator++()
     195             :         {
     196       28235 :             mCurrent = mCurrent->mNext;
     197       28235 :             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         307 :         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         296 :         bool operator==(const IteratorBase & that) const { return mCurrent == that.mCurrent; }
     242         296 :         bool operator!=(const IteratorBase & that) const { return !(*this == that); }
     243             : 
     244         160 :         IteratorBase & operator++()
     245             :         {
     246         160 :             mCurrent = mCurrent->mNext;
     247         160 :             return *this;
     248             :         }
     249             : 
     250           0 :         IteratorBase operator++(int)
     251             :         {
     252           0 :             IteratorBase res(mCurrent);
     253           0 :             mCurrent = mCurrent->mNext;
     254           0 :             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      267421 :     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      134151 :     IntrusiveListBase() : mNode(&mNode, &mNode) {}
     288      133769 :     ~IntrusiveListBase()
     289             :     {
     290      133769 :         VerifyOrDie(Empty());
     291             :         /* clear mNode such that the destructor checking mNode.IsInList doesn't fail */
     292      133769 :         mNode.Remove();
     293      133769 :     }
     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        8129 :     ConstIteratorBase begin() const { return ConstIteratorBase(mNode.mNext); }
     317        8129 :     ConstIteratorBase end() const { return ConstIteratorBase(&mNode); }
     318         152 :     IteratorBase begin() { return IteratorBase(mNode.mNext); }
     319         201 :     IteratorBase end() { return IteratorBase(&mNode); }
     320             : 
     321             :     void PushFront(IntrusiveListNodePrivateBase * node) { mNode.Append(node); }
     322        8136 :     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        6446 :     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        8129 :     bool Contains(const IntrusiveListNodePrivateBase * node) const
     339             :     {
     340       36364 :         for (auto & iter : *this)
     341             :         {
     342       36364 :             if (&iter == node)
     343        8129 :                 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         175 :     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       16272 :     static IntrusiveListNodeBase<Mode> * ToNode(T * object) { return static_cast<IntrusiveListNodeBase<Mode> *>(object); }
     369        8129 :     static const IntrusiveListNodeBase<Mode> * ToNode(const T * object)
     370             :     {
     371        8129 :         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      135143 :     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             : 
     419             :     class Iterator : public IntrusiveListBase::IteratorBase
     420             :     {
     421             :     public:
     422             :         using value_type = T;
     423             :         using pointer    = T *;
     424             :         using reference  = T &;
     425             : 
     426         573 :         Iterator(IntrusiveListBase::IteratorBase && base) : IntrusiveListBase::IteratorBase(std::move(base)) {}
     427          72 :         T * operator->() { return Hook::ToObject(mCurrent); }
     428         103 :         T & operator*() { return *Hook::ToObject(mCurrent); }
     429             :     };
     430             : 
     431             :     ConstIterator begin() const { return IntrusiveListBase::begin(); }
     432             :     ConstIterator end() const { return IntrusiveListBase::end(); }
     433         285 :     Iterator begin() { return IntrusiveListBase::begin(); }
     434         334 :     Iterator end() { return IntrusiveListBase::end(); }
     435             :     void PushFront(T * value) { IntrusiveListBase::PushFront(Hook::ToNode(value)); }
     436        8136 :     void PushBack(T * value) { IntrusiveListBase::PushBack(Hook::ToNode(value)); }
     437             :     void InsertBefore(Iterator pos, T * value) { IntrusiveListBase::InsertBefore(pos, Hook::ToNode(value)); }
     438             :     void InsertAfter(Iterator pos, T * value) { IntrusiveListBase::InsertAfter(pos, Hook::ToNode(value)); }
     439        8136 :     void Remove(T * value) { IntrusiveListBase::Remove(Hook::ToNode(value)); }
     440             :     void Replace(T * original, T * replacement) { IntrusiveListBase::Replace(Hook::ToNode(original), Hook::ToNode(replacement)); }
     441        8129 :     bool Contains(const T * value) const { return IntrusiveListBase::Contains(Hook::ToNode(value)); }
     442             : 
     443             :     void Clear()
     444             :     {
     445             :         while (begin() != end())
     446             :         {
     447             :             Remove(&(*begin()));
     448             :         }
     449             :     }
     450             : };
     451             : 
     452             : } // namespace chip