1 | /** |
2 | * Copyright (c) Glow Contributors. See CONTRIBUTORS file. |
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 | #ifndef GLOW_BASE_TAGGEDLIST_H |
17 | #define GLOW_BASE_TAGGEDLIST_H |
18 | |
19 | /// \file Intrusive doubly linked list with online node ordering. |
20 | /// |
21 | /// This file implements a TaggedList<T> template which is very similar to |
22 | /// llvm::ilist<T> with the addition of online node ordering. This means that |
23 | /// iterators into a TaggedList<T> can be compared with the standard inequality |
24 | /// operators (<, <=, >, >=), and the iterator relations are consistent with the |
25 | /// list order. |
26 | |
27 | #include <cassert> |
28 | #include <cinttypes> |
29 | #include <cstddef> |
30 | #include <iterator> |
31 | #include <type_traits> |
32 | |
33 | namespace glow { |
34 | |
35 | template <typename T> class TaggedListNode; |
36 | template <typename T, typename Traits> class TaggedList; |
37 | |
38 | /// Traits for a TaggedList<T> |
39 | /// |
40 | /// Specialize these traits to customize list behavior. |
41 | /// |
42 | /// The TaggedList will derive from the traits type. |
43 | template <typename T> struct TaggedListTraits { |
44 | /// Delete a node. |
45 | /// |
46 | /// A TaggedList<T> never allocates nodes, but the erase() and clear() methods |
47 | /// will delete nodes. |
48 | static void deleteNode(T *node) { delete node; } |
49 | |
50 | /// Called before node is added to this list. |
51 | void addNodeToList(T *) {} |
52 | |
53 | /// Called before node is removed from this list. |
54 | void removeNodeFromList(T *) {} |
55 | }; |
56 | |
57 | /// Namespace of TaggedList implementation details |
58 | namespace tagged_list_details { |
59 | |
60 | /// Base class for nodes that can be inserted in a `TaggedList`. |
61 | /// |
62 | /// Users should derive from `TaggedListNode<T>`. |
63 | class NodeBase { |
64 | public: |
65 | /// Is this the `end()` sentinel? All real nodes return false. |
66 | bool isTaggedListSentinel() const { return nodeTag_ == 0; } |
67 | |
68 | /// Is this node inserted in a TaggedList? |
69 | /// This also returns true for the end() sentinel. |
70 | bool inTaggedList() const { return prevTaggedNode_; } |
71 | |
72 | private: |
73 | // Use long member names to avoid cluttering the namespace of sub-classes. |
74 | NodeBase *prevTaggedNode_ = nullptr; |
75 | NodeBase *nextTaggedNode_ = nullptr; |
76 | std::uint32_t nodeTag_ = 0; |
77 | |
78 | friend class ListImpl; |
79 | template <typename T, bool IsReverse, bool IsConst> friend class Iterator; |
80 | }; |
81 | |
82 | /// Traits for sorting out iterator types. |
83 | template <typename T, bool IsConst> struct IteratorTraits; |
84 | template <typename T> struct IteratorTraits<T, false> { |
85 | using ValueType = T; |
86 | using NodePtr = NodeBase *; |
87 | }; |
88 | template <typename T> struct IteratorTraits<T, true> { |
89 | using ValueType = const T; |
90 | using NodePtr = const NodeBase *; |
91 | }; |
92 | |
93 | /// Iterator for a TaggedList<T>. |
94 | template <typename T, bool IsReverse, bool IsConst> class Iterator { |
95 | using Traits = IteratorTraits<T, IsConst>; |
96 | using NodePtr = typename Traits::NodePtr; |
97 | |
98 | template <typename T1, typename T2> friend class glow::TaggedList; |
99 | friend class glow::TaggedListNode<T>; |
100 | |
101 | // Private constructor used by TaggedList<T> and TaggedListNode<T>. |
102 | // Note that `n` will be down-casted to a T* unless it's the end() sentinel. |
103 | Iterator(NodePtr n) : node_(n) { |
104 | assert(n && n->inTaggedList() && |
105 | "TaggedList iterator must point to node in list" ); |
106 | } |
107 | |
108 | public: |
109 | using difference_type = std::ptrdiff_t; |
110 | using value_type = typename Traits::ValueType; |
111 | using pointer = value_type *; |
112 | using reference = value_type &; |
113 | using iterator_category = std::bidirectional_iterator_tag; |
114 | |
115 | /// Create an iterator pointing at n. |
116 | explicit Iterator(value_type *n) : node_(n) { |
117 | assert(n && n->inTaggedList() && |
118 | "TaggedList iterator must point to node in list" ); |
119 | } |
120 | |
121 | /// Copy constructor is templated so a const iterator can be initialized with |
122 | /// a non-const iterator, but not the other way around. |
123 | template <bool OrigIsConst> |
124 | Iterator( |
125 | const Iterator<T, IsReverse, OrigIsConst> &orig, |
126 | typename std::enable_if<IsConst || !OrigIsConst, void *>::type = nullptr) |
127 | : node_(orig.node_) {} |
128 | |
129 | /// Dereferencing with `*i`. |
130 | value_type &operator*() { |
131 | assert(!node_->isTaggedListSentinel() && "* can't dereference end()" ); |
132 | return *static_cast<value_type *>(node_); |
133 | } |
134 | |
135 | /// Dereferencing with `i->field`. |
136 | value_type *operator->() { |
137 | assert(!node_->isTaggedListSentinel() && "-> can't dereference end()" ); |
138 | return static_cast<value_type *>(node_); |
139 | } |
140 | |
141 | /// Comparing iterators for equality. |
142 | friend bool operator==(const Iterator &LHS, const Iterator &RHS) { |
143 | return LHS.node_ == RHS.node_; |
144 | } |
145 | friend bool operator!=(const Iterator &LHS, const Iterator &RHS) { |
146 | return LHS.node_ != RHS.node_; |
147 | } |
148 | |
149 | /// Comparing iterators for inequality. |
150 | /// |
151 | /// This is the defining feature of TaggedList -- It is possible to compare |
152 | /// the relative positions of list nodes in constant time. |
153 | /// |
154 | /// Returns a node ordering key that is always monotonic. |
155 | /// |
156 | /// The key returned for an end() iterator is greater than any other key. |
157 | uint32_t getNodeOrdering() const { |
158 | // The end() sentinel has tag 0 which returns UINT32_MAX in either case. |
159 | return IsReverse ? ~node_->nodeTag_ : node_->nodeTag_ - 1; |
160 | } |
161 | |
162 | /// Pre-increment. |
163 | Iterator &operator++() { |
164 | assert(!node_->isTaggedListSentinel() && "can't ++end()" ); |
165 | node_ = IsReverse ? node_->prevTaggedNode_ : node_->nextTaggedNode_; |
166 | return *this; |
167 | } |
168 | |
169 | /// Post-increment. |
170 | Iterator operator++(int) { |
171 | Iterator tmp = *this; |
172 | ++*this; |
173 | return tmp; |
174 | } |
175 | |
176 | // Pre-decrement. |
177 | Iterator &operator--() { |
178 | node_ = IsReverse ? node_->nextTaggedNode_ : node_->prevTaggedNode_; |
179 | assert(!node_->isTaggedListSentinel() && "can't --begin()" ); |
180 | return *this; |
181 | } |
182 | |
183 | /// Post-decrement. |
184 | Iterator operator--(int) { |
185 | Iterator tmp = *this; |
186 | --*this; |
187 | return tmp; |
188 | } |
189 | |
190 | private: |
191 | // This is either pointing to a list element of type T or the sentinel |
192 | // NodeBase object. |
193 | NodePtr node_; |
194 | }; |
195 | |
196 | template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst> |
197 | bool operator<(const Iterator<T, IsReverse, IsLHSConst> &LHS, |
198 | const Iterator<T, IsReverse, IsRHSConst> &RHS) { |
199 | return LHS.getNodeOrdering() < RHS.getNodeOrdering(); |
200 | } |
201 | |
202 | template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst> |
203 | bool operator<=(const Iterator<T, IsReverse, IsLHSConst> &LHS, |
204 | const Iterator<T, IsReverse, IsRHSConst> &RHS) { |
205 | return LHS.getNodeOrdering() <= RHS.getNodeOrdering(); |
206 | } |
207 | |
208 | template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst> |
209 | bool operator>(const Iterator<T, IsReverse, IsLHSConst> &LHS, |
210 | const Iterator<T, IsReverse, IsRHSConst> &RHS) { |
211 | return LHS.getNodeOrdering() > RHS.getNodeOrdering(); |
212 | } |
213 | |
214 | template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst> |
215 | bool operator>=(const Iterator<T, IsReverse, IsLHSConst> &LHS, |
216 | const Iterator<T, IsReverse, IsRHSConst> &RHS) { |
217 | return LHS.getNodeOrdering() >= RHS.getNodeOrdering(); |
218 | } |
219 | |
220 | /// Template-free implementation of the `TaggedList`. |
221 | class ListImpl { |
222 | public: |
223 | ListImpl() { clear(); } |
224 | |
225 | ListImpl(const ListImpl &) = delete; |
226 | ListImpl(const ListImpl &&) = delete; |
227 | |
228 | /// Get the number of elements in the list. |
229 | /// This is a constant time operation. |
230 | std::size_t size() const { return size_; } |
231 | |
232 | NodeBase *begin() { return sentinel_.nextTaggedNode_; } |
233 | NodeBase *end() { return &sentinel_; } |
234 | NodeBase *rbegin() { return sentinel_.prevTaggedNode_; } |
235 | NodeBase *rend() { return &sentinel_; } |
236 | const NodeBase *begin() const { return sentinel_.nextTaggedNode_; } |
237 | const NodeBase *end() const { return &sentinel_; } |
238 | const NodeBase *rbegin() const { return sentinel_.prevTaggedNode_; } |
239 | const NodeBase *rend() const { return &sentinel_; } |
240 | |
241 | /// Insert `node` before `next`. |
242 | void insert(NodeBase *next, NodeBase *node) { |
243 | size_++; |
244 | NodeBase *prev = next->prevTaggedNode_; |
245 | node->nextTaggedNode_ = next; |
246 | node->prevTaggedNode_ = prev; |
247 | next->prevTaggedNode_ = node; |
248 | prev->nextTaggedNode_ = node; |
249 | |
250 | // Compute a tag half-way between prev and next. |
251 | // Note that if `next` is the sentinel with tag 0, this will compute a tag |
252 | // half-way between prev and UINT32_MAX. That is precisely what we want. |
253 | std::uint32_t delta = (next->nodeTag_ - prev->nodeTag_) / 2; |
254 | node->nodeTag_ = prev->nodeTag_ + delta; |
255 | if (delta == 0) |
256 | renumber(prev, node); |
257 | } |
258 | |
259 | void remove(NodeBase *node) { |
260 | size_--; |
261 | NodeBase *prev = node->prevTaggedNode_; |
262 | NodeBase *next = node->nextTaggedNode_; |
263 | node->nextTaggedNode_ = nullptr; |
264 | node->prevTaggedNode_ = nullptr; |
265 | prev->nextTaggedNode_ = next; |
266 | next->prevTaggedNode_ = prev; |
267 | } |
268 | |
269 | void clear() { |
270 | sentinel_.prevTaggedNode_ = sentinel_.nextTaggedNode_ = &sentinel_; |
271 | size_ = 0; |
272 | } |
273 | |
274 | private: |
275 | void renumber(NodeBase *lo, NodeBase *hi); |
276 | NodeBase sentinel_; |
277 | // Not a size_t because the list can't hold more than 2^32 nodes. |
278 | std::uint32_t size_ = 0; |
279 | }; |
280 | |
281 | } // namespace tagged_list_details |
282 | |
283 | /// Base class for intrusive list nodes of type T. |
284 | /// |
285 | /// A linked list node of type T must be derived from TaggedListNode<T>. |
286 | template <typename T> |
287 | class TaggedListNode : public tagged_list_details::NodeBase { |
288 | public: |
289 | // Get an iterator pointing at this node. |
290 | tagged_list_details::Iterator<T, false, false> getIterator() { |
291 | return tagged_list_details::Iterator<T, false, false>(this); |
292 | } |
293 | |
294 | // Get a const iterator pointing at this node. |
295 | tagged_list_details::Iterator<T, false, true> getIterator() const { |
296 | return tagged_list_details::Iterator<T, false, true>(this); |
297 | } |
298 | |
299 | // Get a reverse iterator pointing at this node. |
300 | tagged_list_details::Iterator<T, true, false> getReverseIterator() { |
301 | return tagged_list_details::Iterator<T, true, false>(this); |
302 | } |
303 | |
304 | // Get a const reverse iterator pointing at this node. |
305 | tagged_list_details::Iterator<T, true, true> getReverseIterator() const { |
306 | return tagged_list_details::Iterator<T, true, true>(this); |
307 | } |
308 | }; |
309 | |
310 | template <typename T, typename Traits = TaggedListTraits<T>> |
311 | class TaggedList : public Traits { |
312 | public: |
313 | using value_type = T; |
314 | using iterator = tagged_list_details::Iterator<T, false, false>; |
315 | using const_iterator = tagged_list_details::Iterator<T, false, true>; |
316 | using reverse_iterator = tagged_list_details::Iterator<T, true, false>; |
317 | using const_reverse_iterator = tagged_list_details::Iterator<T, true, true>; |
318 | |
319 | ~TaggedList() { clear(); } |
320 | |
321 | /// Get the number of elements in the list. |
322 | /// This is a constant time operation. |
323 | size_t size() const { return impl_.size(); } |
324 | |
325 | /// Is the list empty? |
326 | bool empty() const { return size() == 0; } |
327 | |
328 | iterator begin() { return impl_.begin(); } |
329 | iterator end() { return impl_.end(); } |
330 | reverse_iterator rbegin() { return impl_.rbegin(); } |
331 | reverse_iterator rend() { return impl_.rend(); } |
332 | const_iterator begin() const { return impl_.begin(); } |
333 | const_iterator end() const { return impl_.end(); } |
334 | const_reverse_iterator rbegin() const { return impl_.rbegin(); } |
335 | const_reverse_iterator rend() const { return impl_.rend(); } |
336 | |
337 | /// Insert `node` before `next`. |
338 | /// |
339 | /// The node is not copied, and it can't already be on another list. |
340 | /// |
341 | /// Returns an iterator pointing to the inserted node. |
342 | iterator insert(iterator next, T *node) { |
343 | assert(node && !node->inTaggedList()); |
344 | this->addNodeToList(node); |
345 | impl_.insert(next.node_, node); |
346 | return iterator(node); |
347 | } |
348 | |
349 | /// Remove `node` from this list without deleting it. |
350 | /// |
351 | /// Returns a pointer to the removed node. |
352 | T *remove(T *node) { |
353 | assert(node && node->inTaggedList()); |
354 | this->removeNodeFromList(node); |
355 | impl_.remove(node); |
356 | return node; |
357 | } |
358 | |
359 | template <bool IsReverse> |
360 | T *remove(tagged_list_details::Iterator<T, IsReverse, false> node) { |
361 | return remove(&*node); |
362 | } |
363 | |
364 | /// Remove `node` from the list and delete it. |
365 | void erase(T *node) { this->deleteNode(remove(node)); } |
366 | |
367 | template <bool IsReverse> |
368 | void erase(tagged_list_details::Iterator<T, IsReverse, false> node) { |
369 | erase(&*node); |
370 | } |
371 | |
372 | value_type &front() { return *begin(); } |
373 | value_type &back() { return *rbegin(); } |
374 | const value_type &front() const { return *begin(); } |
375 | const value_type &back() const { return *rbegin(); } |
376 | |
377 | void push_front(T *node) { insert(begin(), node); } |
378 | void push_back(T *node) { insert(end(), node); } |
379 | |
380 | void pop_front() { erase(begin()); } |
381 | void pop_back() { erase(rbegin()); } |
382 | |
383 | /// Remove all nodes from the list without calling removeNodeFromList() or |
384 | /// deleteNode(). |
385 | void clearAndLeakNodesUnsafely() { impl_.clear(); } |
386 | |
387 | /// Erase all nodes. |
388 | void clear() { |
389 | while (!empty()) { |
390 | erase(begin()); |
391 | } |
392 | } |
393 | |
394 | private: |
395 | tagged_list_details::ListImpl impl_; |
396 | }; |
397 | |
398 | } // namespace glow |
399 | #endif // GLOW_BASE_TAGGEDLIST_H |
400 | |