1 // Copyright (c) 2017 Google Inc. 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 15 #ifndef SOURCE_UTIL_ILIST_H_ 16 #define SOURCE_UTIL_ILIST_H_ 17 18 #include <cassert> 19 #include <memory> 20 #include <type_traits> 21 #include <vector> 22 23 #include "source/util/ilist_node.h" 24 25 namespace spvtools { 26 namespace utils { 27 28 // An IntrusiveList is a generic implementation of a doubly-linked list. The 29 // intended convention for using this container is: 30 // 31 // class Node : public IntrusiveNodeBase<Node> { 32 // // Note that "Node", the class being defined is the template. 33 // // Must have a default constructor accessible to List. 34 // // Add whatever data is needed in the node 35 // }; 36 // 37 // using List = IntrusiveList<Node>; 38 // 39 // You can also inherit from IntrusiveList instead of a typedef if you want to 40 // add more functionality. 41 // 42 // The condition on the template for IntrusiveNodeBase is there to add some type 43 // checking to the container. The compiler will still allow inserting elements 44 // of type IntrusiveNodeBase<Node>, but that would be an error. This assumption 45 // allows NextNode and PreviousNode to return pointers to Node, and casting will 46 // not be required by the user. 47 48 template <class NodeType> 49 class IntrusiveList { 50 public: 51 static_assert( 52 std::is_base_of<IntrusiveNodeBase<NodeType>, NodeType>::value, 53 "The type from the node must be derived from IntrusiveNodeBase, with " 54 "itself in the template."); 55 56 // Creates an empty list. 57 inline IntrusiveList(); 58 59 // Moves the contents of the given list to the list being constructed. 60 IntrusiveList(IntrusiveList&&); 61 62 // Destorys the list. Note that the elements of the list will not be deleted, 63 // but they will be removed from the list. 64 virtual ~IntrusiveList(); 65 66 // Moves all of the elements in the list on the RHS to the list on the LHS. 67 IntrusiveList& operator=(IntrusiveList&&); 68 69 // Basetype for iterators so an IntrusiveList can be traversed like STL 70 // containers. 71 template <class T> 72 class iterator_template { 73 public: 74 iterator_template(const iterator_template& i) : node_(i.node_) {} 75 76 iterator_template& operator++() { 77 node_ = node_->next_node_; 78 return *this; 79 } 80 81 iterator_template& operator--() { 82 node_ = node_->previous_node_; 83 return *this; 84 } 85 86 iterator_template& operator=(const iterator_template& i) { 87 node_ = i.node_; 88 return *this; 89 } 90 91 T& operator*() const { return *node_; } 92 T* operator->() const { return node_; } 93 94 friend inline bool operator==(const iterator_template& lhs, 95 const iterator_template& rhs) { 96 return lhs.node_ == rhs.node_; 97 } 98 friend inline bool operator!=(const iterator_template& lhs, 99 const iterator_template& rhs) { 100 return !(lhs == rhs); 101 } 102 103 // Moves the nodes in |list| to the list that |this| points to. The 104 // positions of the nodes will be immediately before the element pointed to 105 // by the iterator. The return value will be an iterator pointing to the 106 // first of the newly inserted elements. 107 iterator_template MoveBefore(IntrusiveList* list) { 108 if (list->empty()) return *this; 109 110 NodeType* first_node = list->sentinel_.next_node_; 111 NodeType* last_node = list->sentinel_.previous_node_; 112 113 this->node_->previous_node_->next_node_ = first_node; 114 first_node->previous_node_ = this->node_->previous_node_; 115 116 last_node->next_node_ = this->node_; 117 this->node_->previous_node_ = last_node; 118 119 list->sentinel_.next_node_ = &list->sentinel_; 120 list->sentinel_.previous_node_ = &list->sentinel_; 121 122 return iterator(first_node); 123 } 124 125 // Define standard iterator types needs so this class can be 126 // used with <algorithms>. 127 using iterator_category = std::bidirectional_iterator_tag; 128 using difference_type = std::ptrdiff_t; 129 using value_type = T; 130 using pointer = T*; 131 using const_pointer = const T*; 132 using reference = T&; 133 using const_reference = const T&; 134 using size_type = size_t; 135 136 protected: 137 iterator_template() = delete; 138 inline iterator_template(T* node) { node_ = node; } 139 T* node_; 140 141 friend IntrusiveList; 142 }; 143 144 using iterator = iterator_template<NodeType>; 145 using const_iterator = iterator_template<const NodeType>; 146 147 // Various types of iterators for the start (begin) and one past the end (end) 148 // of the list. 149 // 150 // Decrementing |end()| iterator will give and iterator pointing to the last 151 // element in the list, if one exists. 152 // 153 // Incrementing |end()| iterator will give |begin()|. 154 // 155 // Decrementing |begin()| will give |end()|. 156 // 157 // TODO: Not marking these functions as noexcept because Visual Studio 2013 158 // does not support it. When we no longer care about that compiler, we should 159 // mark these as noexcept. 160 iterator begin(); 161 iterator end(); 162 const_iterator begin() const; 163 const_iterator end() const; 164 const_iterator cbegin() const; 165 const_iterator cend() const; 166 167 // Appends |node| to the end of the list. If |node| is already in a list, it 168 // will be removed from that list first. 169 void push_back(NodeType* node); 170 171 // Returns true if the list is empty. 172 bool empty() const; 173 174 // Makes the current list empty. 175 inline void clear(); 176 177 // Returns references to the first or last element in the list. It is an 178 // error to call these functions on an empty list. 179 NodeType& front(); 180 NodeType& back(); 181 const NodeType& front() const; 182 const NodeType& back() const; 183 184 // Transfers [|first|, |last|) from |other| into the list at |where|. 185 // 186 // If |other| is |this|, no change is made. 187 void Splice(iterator where, IntrusiveList<NodeType>* other, iterator first, 188 iterator last); 189 190 protected: 191 // Doing a deep copy of the list does not make sense if the list does not own 192 // the data. It is not clear who will own the newly created data. Making 193 // copies illegal for that reason. 194 IntrusiveList(const IntrusiveList&) = delete; 195 IntrusiveList& operator=(const IntrusiveList&) = delete; 196 197 // This function will assert if it finds the list containing |node| is not in 198 // a valid state. 199 static void Check(NodeType* node); 200 201 // A special node used to represent both the start and end of the list, 202 // without being part of the list. 203 NodeType sentinel_; 204 }; 205 206 // Implementation of IntrusiveList 207 208 template <class NodeType> 209 inline IntrusiveList<NodeType>::IntrusiveList() : sentinel_() { 210 sentinel_.next_node_ = &sentinel_; 211 sentinel_.previous_node_ = &sentinel_; 212 sentinel_.is_sentinel_ = true; 213 } 214 215 template <class NodeType> 216 IntrusiveList<NodeType>::IntrusiveList(IntrusiveList&& list) : sentinel_() { 217 sentinel_.next_node_ = &sentinel_; 218 sentinel_.previous_node_ = &sentinel_; 219 sentinel_.is_sentinel_ = true; 220 list.sentinel_.ReplaceWith(&sentinel_); 221 } 222 223 template <class NodeType> 224 IntrusiveList<NodeType>::~IntrusiveList() { 225 clear(); 226 } 227 228 template <class NodeType> 229 IntrusiveList<NodeType>& IntrusiveList<NodeType>::operator=( 230 IntrusiveList<NodeType>&& list) { 231 list.sentinel_.ReplaceWith(&sentinel_); 232 return *this; 233 } 234 235 template <class NodeType> 236 inline typename IntrusiveList<NodeType>::iterator 237 IntrusiveList<NodeType>::begin() { 238 return iterator(sentinel_.next_node_); 239 } 240 241 template <class NodeType> 242 inline typename IntrusiveList<NodeType>::iterator 243 IntrusiveList<NodeType>::end() { 244 return iterator(&sentinel_); 245 } 246 247 template <class NodeType> 248 inline typename IntrusiveList<NodeType>::const_iterator 249 IntrusiveList<NodeType>::begin() const { 250 return const_iterator(sentinel_.next_node_); 251 } 252 253 template <class NodeType> 254 inline typename IntrusiveList<NodeType>::const_iterator 255 IntrusiveList<NodeType>::end() const { 256 return const_iterator(&sentinel_); 257 } 258 259 template <class NodeType> 260 inline typename IntrusiveList<NodeType>::const_iterator 261 IntrusiveList<NodeType>::cbegin() const { 262 return const_iterator(sentinel_.next_node_); 263 } 264 265 template <class NodeType> 266 inline typename IntrusiveList<NodeType>::const_iterator 267 IntrusiveList<NodeType>::cend() const { 268 return const_iterator(&sentinel_); 269 } 270 271 template <class NodeType> 272 void IntrusiveList<NodeType>::push_back(NodeType* node) { 273 node->InsertBefore(&sentinel_); 274 } 275 276 template <class NodeType> 277 bool IntrusiveList<NodeType>::empty() const { 278 return sentinel_.NextNode() == nullptr; 279 } 280 281 template <class NodeType> 282 void IntrusiveList<NodeType>::clear() { 283 while (!empty()) { 284 front().RemoveFromList(); 285 } 286 } 287 288 template <class NodeType> 289 NodeType& IntrusiveList<NodeType>::front() { 290 NodeType* node = sentinel_.NextNode(); 291 assert(node != nullptr && "Can't get the front of an empty list."); 292 return *node; 293 } 294 295 template <class NodeType> 296 NodeType& IntrusiveList<NodeType>::back() { 297 NodeType* node = sentinel_.PreviousNode(); 298 assert(node != nullptr && "Can't get the back of an empty list."); 299 return *node; 300 } 301 302 template <class NodeType> 303 const NodeType& IntrusiveList<NodeType>::front() const { 304 NodeType* node = sentinel_.NextNode(); 305 assert(node != nullptr && "Can't get the front of an empty list."); 306 return *node; 307 } 308 309 template <class NodeType> 310 const NodeType& IntrusiveList<NodeType>::back() const { 311 NodeType* node = sentinel_.PreviousNode(); 312 assert(node != nullptr && "Can't get the back of an empty list."); 313 return *node; 314 } 315 316 template <class NodeType> 317 void IntrusiveList<NodeType>::Splice(iterator where, 318 IntrusiveList<NodeType>* other, 319 iterator first, iterator last) { 320 if (first == last) return; 321 if (other == this) return; 322 323 NodeType* first_prev = first.node_->previous_node_; 324 NodeType* where_next = where.node_->next_node_; 325 326 // Attach first. 327 where.node_->next_node_ = first.node_; 328 first.node_->previous_node_ = where.node_; 329 330 // Attach last. 331 where_next->previous_node_ = last.node_->previous_node_; 332 last.node_->previous_node_->next_node_ = where_next; 333 334 // Fixup other. 335 first_prev->next_node_ = last.node_; 336 last.node_->previous_node_ = first_prev; 337 } 338 339 template <class NodeType> 340 void IntrusiveList<NodeType>::Check(NodeType* start) { 341 int sentinel_count = 0; 342 NodeType* p = start; 343 do { 344 assert(p != nullptr); 345 assert(p->next_node_->previous_node_ == p); 346 assert(p->previous_node_->next_node_ == p); 347 if (p->is_sentinel_) sentinel_count++; 348 p = p->next_node_; 349 } while (p != start); 350 assert(sentinel_count == 1 && "List should have exactly 1 sentinel node."); 351 352 p = start; 353 do { 354 assert(p != nullptr); 355 assert(p->previous_node_->next_node_ == p); 356 assert(p->next_node_->previous_node_ == p); 357 if (p->is_sentinel_) sentinel_count++; 358 p = p->previous_node_; 359 } while (p != start); 360 } 361 362 } // namespace utils 363 } // namespace spvtools 364 365 #endif // SOURCE_UTIL_ILIST_H_ 366