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 <unordered_map> 18 19 template <typename T> 20 class intrusive_list; 21 22 template <typename T> 23 class intrusive_list_node 24 { 25 protected: 26 friend class intrusive_list<T>; 27 T* mPrev = nullptr; 28 T* mNext = nullptr; 29 }; 30 31 template <typename T> 32 class intrusive_list 33 { 34 typedef intrusive_list_node<T> TNode; 35 static_assert(std::is_base_of<TNode, T>::value, ""); 36 37 public: 38 39 class iterator : public std::iterator<std::forward_iterator_tag, T> 40 { 41 public: 42 iterator()43 iterator() : mPos(nullptr) {} 44 iterator(T * pos)45 iterator(T* pos) : mPos(pos) {} 46 47 iterator operator++(int) 48 { 49 auto result = *this; 50 mPos = mPos->mNext; 51 return result; 52 } 53 54 iterator operator--(int) 55 { 56 auto result = *this; 57 mPos = mPos->mPrev; 58 return result; 59 } 60 61 iterator& operator++() 62 { 63 mPos = mPos->mNext; 64 return *this; 65 } 66 67 iterator& operator--() 68 { 69 mPos = mPos->mPrev; 70 return *this; 71 } 72 73 74 bool operator==(const iterator& other) const 75 { 76 return mPos == other.mPos; 77 } 78 79 bool operator!=(const iterator& other) const 80 { 81 return !(*this == other); 82 } 83 84 T& operator*() 85 { 86 return *mPos; 87 } 88 89 const T& operator*() const 90 { 91 return *mPos; 92 } 93 94 T* operator->() 95 { 96 return mPos; 97 } 98 99 const T* operator->() const 100 { 101 return mPos; 102 } 103 104 operator T*() 105 { 106 return mPos; 107 } 108 109 operator const T*() const 110 { 111 return mPos; 112 } 113 114 115 protected: 116 T* mPos; 117 }; 118 push_back(T * node)119 void push_back(T* node) 120 { 121 if (mLast) { 122 mLast->mNext = node; 123 } 124 node->mPrev = mLast; 125 node->mNext = nullptr; 126 mLast = node; 127 if (mFirst == nullptr) { 128 mFirst = node; 129 } 130 ++mSize; 131 } 132 push_front(T * node)133 void push_front(T* node) 134 { 135 node->mPrev = nullptr; 136 node->mNext = mFirst; 137 if (mFirst) { 138 mFirst->mPrev = node; 139 } 140 mFirst = node; 141 if (mLast == nullptr) { 142 mLast = node; 143 } 144 ++mSize; 145 } 146 back()147 T& back() 148 { 149 return *mLast; 150 } 151 back()152 const T& back() const 153 { 154 return *mLast; 155 } 156 front()157 T& front() 158 { 159 return *mFirst; 160 } 161 front()162 const T& front() const 163 { 164 return *mFirst; 165 } 166 pop_front()167 void pop_front() 168 { 169 erase(mFirst); 170 } 171 pop_back()172 void pop_back() 173 { 174 erase(mLast); 175 } 176 insert(iterator next,T * node)177 void insert(iterator next, T* node) 178 { 179 if (static_cast<T*>(next) == nullptr) { 180 push_back(node); 181 } else { 182 auto prev = next->mPrev; 183 if (!prev) { 184 push_front(node); 185 } else { 186 prev->mNext = node; 187 next->mPrev = node; 188 node->mNext = next; 189 node->mPrev = &(*prev); 190 ++mSize; 191 } 192 } 193 } 194 erase(iterator it)195 void erase(iterator it) 196 { 197 auto prev = it->mPrev; 198 auto next = it->mNext; 199 200 if (prev) { 201 prev->mNext = next; 202 } else { 203 mFirst = next; 204 } 205 if (next) { 206 next->mPrev = prev; 207 } else { 208 mLast = prev; 209 } 210 --mSize; 211 } 212 begin()213 iterator begin() 214 { 215 return iterator(mFirst); 216 } 217 end()218 iterator end() 219 { 220 return iterator(nullptr); 221 } 222 size()223 size_t size() const 224 { 225 return mSize; 226 } 227 empty()228 bool empty() const 229 { 230 return mSize == 0; 231 } 232 clear()233 void clear() 234 { 235 while (mFirst) { 236 erase(mFirst); 237 } 238 } 239 clearAndFreeNodes()240 void clearAndFreeNodes() 241 { 242 while (mFirst) { 243 auto tmp = mFirst; 244 erase(mFirst); 245 delete tmp; 246 } 247 } 248 249 250 protected: 251 T* mFirst = nullptr; 252 T* mLast = nullptr; 253 size_t mSize = 0; 254 }; 255 256 257 #endif /* intrusive_list_h */ 258