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
33namespace glow {
34
35template <typename T> class TaggedListNode;
36template <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.
43template <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
58namespace tagged_list_details {
59
60/// Base class for nodes that can be inserted in a `TaggedList`.
61///
62/// Users should derive from `TaggedListNode<T>`.
63class NodeBase {
64public:
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
72private:
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.
83template <typename T, bool IsConst> struct IteratorTraits;
84template <typename T> struct IteratorTraits<T, false> {
85 using ValueType = T;
86 using NodePtr = NodeBase *;
87};
88template <typename T> struct IteratorTraits<T, true> {
89 using ValueType = const T;
90 using NodePtr = const NodeBase *;
91};
92
93/// Iterator for a TaggedList<T>.
94template <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
108public:
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
190private:
191 // This is either pointing to a list element of type T or the sentinel
192 // NodeBase object.
193 NodePtr node_;
194};
195
196template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst>
197bool operator<(const Iterator<T, IsReverse, IsLHSConst> &LHS,
198 const Iterator<T, IsReverse, IsRHSConst> &RHS) {
199 return LHS.getNodeOrdering() < RHS.getNodeOrdering();
200}
201
202template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst>
203bool operator<=(const Iterator<T, IsReverse, IsLHSConst> &LHS,
204 const Iterator<T, IsReverse, IsRHSConst> &RHS) {
205 return LHS.getNodeOrdering() <= RHS.getNodeOrdering();
206}
207
208template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst>
209bool operator>(const Iterator<T, IsReverse, IsLHSConst> &LHS,
210 const Iterator<T, IsReverse, IsRHSConst> &RHS) {
211 return LHS.getNodeOrdering() > RHS.getNodeOrdering();
212}
213
214template <typename T, bool IsReverse, bool IsLHSConst, bool IsRHSConst>
215bool 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`.
221class ListImpl {
222public:
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
274private:
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>.
286template <typename T>
287class TaggedListNode : public tagged_list_details::NodeBase {
288public:
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
310template <typename T, typename Traits = TaggedListTraits<T>>
311class TaggedList : public Traits {
312public:
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
394private:
395 tagged_list_details::ListImpl impl_;
396};
397
398} // namespace glow
399#endif // GLOW_BASE_TAGGEDLIST_H
400