1 // Copyright 2015-2016 Espressif Systems (Shanghai) PTE LTD
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 
7 //     http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 #ifndef intrusive_list_h
15 #define intrusive_list_h
16 
17 #include <cassert>
18 #include <unordered_map>
19 
20 template <typename T>
21 class intrusive_list;
22 
23 template <typename T>
24 class intrusive_list_node
25 {
26 protected:
27     friend class intrusive_list<T>;
28     T* mPrev = nullptr;
29     T* mNext = nullptr;
30 };
31 
32 template <typename T>
33 class intrusive_list
34 {
35     typedef intrusive_list_node<T> TNode;
36     static_assert(std::is_base_of<TNode, T>::value, "");
37 
38 public:
39 
40     class iterator : public std::iterator<std::forward_iterator_tag, T>
41     {
42     public:
43 
iterator()44         iterator() : mPos(nullptr) {}
45 
iterator(T * pos)46         iterator(T* pos) : mPos(pos) {}
47 
48         iterator operator++(int)
49         {
50             auto result = *this;
51             mPos = mPos->mNext;
52             return result;
53         }
54 
55         iterator operator--(int)
56         {
57             auto result = *this;
58             mPos = mPos->mPrev;
59             return result;
60         }
61 
62         iterator& operator++()
63         {
64             mPos = mPos->mNext;
65             return *this;
66         }
67 
68         iterator& operator--()
69         {
70             mPos = mPos->mPrev;
71             return *this;
72         }
73 
74 
75         bool operator==(const iterator& other) const
76         {
77             return mPos == other.mPos;
78         }
79 
80         bool operator!=(const iterator& other) const
81         {
82             return !(*this == other);
83         }
84 
85         T& operator*()
86         {
87             return *mPos;
88         }
89 
90         const T& operator*() const
91         {
92             return *mPos;
93         }
94 
95         T* operator->()
96         {
97             return mPos;
98         }
99 
100         const T* operator->() const
101         {
102             return mPos;
103         }
104 
105         operator T*()
106         {
107             return mPos;
108         }
109 
110         operator const T*() const
111         {
112             return mPos;
113         }
114 
115 
116     protected:
117         T* mPos;
118     };
119 
push_back(T * node)120     void push_back(T* node)
121     {
122         if (mLast) {
123             mLast->mNext = node;
124         }
125         node->mPrev = mLast;
126         node->mNext = nullptr;
127         mLast = node;
128         if (mFirst == nullptr) {
129             mFirst = node;
130         }
131         ++mSize;
132     }
133 
push_front(T * node)134     void push_front(T* node)
135     {
136         node->mPrev = nullptr;
137         node->mNext = mFirst;
138         if (mFirst) {
139             mFirst->mPrev = node;
140         }
141         mFirst = node;
142         if (mLast == nullptr) {
143             mLast = node;
144         }
145         ++mSize;
146     }
147 
back()148     T& back()
149     {
150         return *mLast;
151     }
152 
back()153     const T& back() const
154     {
155         return *mLast;
156     }
157 
front()158     T& front()
159     {
160         return *mFirst;
161     }
162 
front()163     const T& front() const
164     {
165         return *mFirst;
166     }
167 
pop_front()168     void pop_front()
169     {
170         erase(mFirst);
171     }
172 
pop_back()173     void pop_back()
174     {
175         erase(mLast);
176     }
177 
insert(iterator next,T * node)178     void insert(iterator next, T* node)
179     {
180         if (static_cast<T*>(next) == nullptr) {
181             push_back(node);
182         } else {
183             auto prev = next->mPrev;
184             if (!prev) {
185                 push_front(node);
186             } else {
187                 prev->mNext = node;
188                 next->mPrev = node;
189                 node->mNext = next;
190                 node->mPrev = &(*prev);
191                 ++mSize;
192             }
193         }
194     }
195 
erase(iterator it)196     void erase(iterator it)
197     {
198         auto prev = it->mPrev;
199         auto next = it->mNext;
200 
201         if (prev) {
202             prev->mNext = next;
203         } else {
204             mFirst = next;
205         }
206         if (next) {
207             next->mPrev = prev;
208         } else {
209             mLast = prev;
210         }
211         --mSize;
212     }
213 
begin()214     iterator begin()
215     {
216         return iterator(mFirst);
217     }
218 
end()219     iterator end()
220     {
221         return iterator(nullptr);
222     }
223 
size()224     size_t size() const
225     {
226         return mSize;
227     }
228 
empty()229     bool empty() const
230     {
231         return mSize == 0;
232     }
233 
clear()234     void clear()
235     {
236         while (mFirst) {
237             erase(mFirst);
238         }
239     }
240 
clearAndFreeNodes()241     void clearAndFreeNodes()
242     {
243         while (mFirst) {
244             auto tmp = mFirst;
245             erase(mFirst);
246             delete tmp;
247         }
248     }
249 
250 
251 protected:
252     T* mFirst = nullptr;
253     T* mLast = nullptr;
254     size_t mSize = 0;
255 };
256 
257 
258 #endif /* intrusive_list_h */
259