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
25namespace spvtools {
26namespace 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
48template <class NodeType>
49class 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
208template <class NodeType>
209inline IntrusiveList<NodeType>::IntrusiveList() : sentinel_() {
210 sentinel_.next_node_ = &sentinel_;
211 sentinel_.previous_node_ = &sentinel_;
212 sentinel_.is_sentinel_ = true;
213}
214
215template <class NodeType>
216IntrusiveList<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
223template <class NodeType>
224IntrusiveList<NodeType>::~IntrusiveList() {
225 clear();
226}
227
228template <class NodeType>
229IntrusiveList<NodeType>& IntrusiveList<NodeType>::operator=(
230 IntrusiveList<NodeType>&& list) {
231 list.sentinel_.ReplaceWith(&sentinel_);
232 return *this;
233}
234
235template <class NodeType>
236inline typename IntrusiveList<NodeType>::iterator
237IntrusiveList<NodeType>::begin() {
238 return iterator(sentinel_.next_node_);
239}
240
241template <class NodeType>
242inline typename IntrusiveList<NodeType>::iterator
243IntrusiveList<NodeType>::end() {
244 return iterator(&sentinel_);
245}
246
247template <class NodeType>
248inline typename IntrusiveList<NodeType>::const_iterator
249IntrusiveList<NodeType>::begin() const {
250 return const_iterator(sentinel_.next_node_);
251}
252
253template <class NodeType>
254inline typename IntrusiveList<NodeType>::const_iterator
255IntrusiveList<NodeType>::end() const {
256 return const_iterator(&sentinel_);
257}
258
259template <class NodeType>
260inline typename IntrusiveList<NodeType>::const_iterator
261IntrusiveList<NodeType>::cbegin() const {
262 return const_iterator(sentinel_.next_node_);
263}
264
265template <class NodeType>
266inline typename IntrusiveList<NodeType>::const_iterator
267IntrusiveList<NodeType>::cend() const {
268 return const_iterator(&sentinel_);
269}
270
271template <class NodeType>
272void IntrusiveList<NodeType>::push_back(NodeType* node) {
273 node->InsertBefore(&sentinel_);
274}
275
276template <class NodeType>
277bool IntrusiveList<NodeType>::empty() const {
278 return sentinel_.NextNode() == nullptr;
279}
280
281template <class NodeType>
282void IntrusiveList<NodeType>::clear() {
283 while (!empty()) {
284 front().RemoveFromList();
285 }
286}
287
288template <class NodeType>
289NodeType& 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
295template <class NodeType>
296NodeType& 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
302template <class NodeType>
303const 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
309template <class NodeType>
310const 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
316template <class NodeType>
317void 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
339template <class NodeType>
340void 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