1//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines classes to implement an intrusive doubly linked list class
11/// (i.e. each node of the list must contain a next and previous field for the
12/// list.
13///
14/// The ilist class itself should be a plug in replacement for list. This list
15/// replacement does not provide a constant time size() method, so be careful to
16/// use empty() when you really want to know if it's empty.
17///
18/// The ilist class is implemented as a circular list. The list itself contains
19/// a sentinel node, whose Next points at begin() and whose Prev points at
20/// rbegin(). The sentinel node itself serves as end() and rend().
21///
22//===----------------------------------------------------------------------===//
23
24#ifndef LLVM_ADT_ILIST_H
25#define LLVM_ADT_ILIST_H
26
27#include "llvm/ADT/simple_ilist.h"
28#include <cassert>
29#include <cstddef>
30#include <iterator>
31
32namespace llvm {
33
34/// Use delete by default for iplist and ilist.
35///
36/// Specialize this to get different behaviour for ownership-related API. (If
37/// you really want ownership semantics, consider using std::list or building
38/// something like \a BumpPtrList.)
39///
40/// \see ilist_noalloc_traits
41template <typename NodeTy> struct ilist_alloc_traits {
42 static void deleteNode(NodeTy *V) { delete V; }
43};
44
45/// Custom traits to do nothing on deletion.
46///
47/// Specialize ilist_alloc_traits to inherit from this to disable the
48/// non-intrusive deletion in iplist (which implies ownership).
49///
50/// If you want purely intrusive semantics with no callbacks, consider using \a
51/// simple_ilist instead.
52///
53/// \code
54/// template <>
55/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
56/// \endcode
57template <typename NodeTy> struct ilist_noalloc_traits {
58 static void deleteNode(NodeTy *V) {}
59};
60
61/// Callbacks do nothing by default in iplist and ilist.
62///
63/// Specialize this for to use callbacks for when nodes change their list
64/// membership.
65template <typename NodeTy> struct ilist_callback_traits {
66 void addNodeToList(NodeTy *) {}
67 void removeNodeFromList(NodeTy *) {}
68
69 /// Callback before transferring nodes to this list. The nodes may already be
70 /// in this same list.
71 template <class Iterator>
72 void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
73 Iterator /*last*/) {
74 (void)OldList;
75 }
76};
77
78/// A fragment for template traits for intrusive list that provides default
79/// node related operations.
80///
81/// TODO: Remove this layer of indirection. It's not necessary.
82template <typename NodeTy>
83struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
84 ilist_callback_traits<NodeTy> {};
85
86/// Template traits for intrusive list.
87///
88/// Customize callbacks and allocation semantics.
89template <typename NodeTy>
90struct ilist_traits : public ilist_node_traits<NodeTy> {};
91
92/// Const traits should never be instantiated.
93template <typename Ty> struct ilist_traits<const Ty> {};
94
95//===----------------------------------------------------------------------===//
96//
97/// A wrapper around an intrusive list with callbacks and non-intrusive
98/// ownership.
99///
100/// This wraps a purely intrusive list (like simple_ilist) with a configurable
101/// traits class. The traits can implement callbacks and customize the
102/// ownership semantics.
103///
104/// This is a subset of ilist functionality that can safely be used on nodes of
105/// polymorphic types, i.e. a heterogeneous list with a common base class that
106/// holds the next/prev pointers. The only state of the list itself is an
107/// ilist_sentinel, which holds pointers to the first and last nodes in the
108/// list.
109template <class IntrusiveListT, class TraitsT>
110class iplist_impl : public TraitsT, IntrusiveListT {
111 typedef IntrusiveListT base_list_type;
112
113public:
114 typedef typename base_list_type::pointer pointer;
115 typedef typename base_list_type::const_pointer const_pointer;
116 typedef typename base_list_type::reference reference;
117 typedef typename base_list_type::const_reference const_reference;
118 typedef typename base_list_type::value_type value_type;
119 typedef typename base_list_type::size_type size_type;
120 typedef typename base_list_type::difference_type difference_type;
121 typedef typename base_list_type::iterator iterator;
122 typedef typename base_list_type::const_iterator const_iterator;
123 typedef typename base_list_type::reverse_iterator reverse_iterator;
124 typedef
125 typename base_list_type::const_reverse_iterator const_reverse_iterator;
126
127private:
128 static bool op_less(const_reference L, const_reference R) { return L < R; }
129 static bool op_equal(const_reference L, const_reference R) { return L == R; }
130
131public:
132 iplist_impl() = default;
133
134 iplist_impl(const iplist_impl &) = delete;
135 iplist_impl &operator=(const iplist_impl &) = delete;
136
137 iplist_impl(iplist_impl &&X)
138 : TraitsT(std::move(static_cast<TraitsT &>(X))),
139 IntrusiveListT(std::move(static_cast<IntrusiveListT &>(X))) {}
140 iplist_impl &operator=(iplist_impl &&X) {
141 *static_cast<TraitsT *>(this) = std::move(static_cast<TraitsT &>(X));
142 *static_cast<IntrusiveListT *>(this) =
143 std::move(static_cast<IntrusiveListT &>(X));
144 return *this;
145 }
146
147 ~iplist_impl() { clear(); }
148
149 // Miscellaneous inspection routines.
150 size_type max_size() const { return size_type(-1); }
151
152 using base_list_type::begin;
153 using base_list_type::end;
154 using base_list_type::rbegin;
155 using base_list_type::rend;
156 using base_list_type::empty;
157 using base_list_type::front;
158 using base_list_type::back;
159
160 void swap(iplist_impl &RHS) {
161 assert(0 && "Swap does not use list traits callback correctly yet!");
162 base_list_type::swap(RHS);
163 }
164
165 iterator insert(iterator where, pointer New) {
166 this->addNodeToList(New); // Notify traits that we added a node...
167 return base_list_type::insert(where, *New);
168 }
169
170 iterator insert(iterator where, const_reference New) {
171 return this->insert(where, new value_type(New));
172 }
173
174 iterator insertAfter(iterator where, pointer New) {
175 if (empty())
176 return insert(begin(), New);
177 else
178 return insert(++where, New);
179 }
180
181 /// Clone another list.
182 template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
183 clear();
184 for (const_reference V : L2)
185 push_back(val: clone(V));
186 }
187
188 pointer remove(iterator &IT) {
189 pointer Node = &*IT++;
190 this->removeNodeFromList(Node); // Notify traits that we removed a node...
191 base_list_type::remove(*Node);
192 return Node;
193 }
194
195 pointer remove(const iterator &IT) {
196 iterator MutIt = IT;
197 return remove(MutIt);
198 }
199
200 pointer remove(pointer IT) { return remove(iterator(IT)); }
201 pointer remove(reference IT) { return remove(iterator(IT)); }
202
203 // erase - remove a node from the controlled sequence... and delete it.
204 iterator erase(iterator where) {
205 this->deleteNode(remove(where));
206 return where;
207 }
208
209 iterator erase(pointer IT) { return erase(iterator(IT)); }
210 iterator erase(reference IT) { return erase(iterator(IT)); }
211
212 /// Remove all nodes from the list like clear(), but do not call
213 /// removeNodeFromList() or deleteNode().
214 ///
215 /// This should only be used immediately before freeing nodes in bulk to
216 /// avoid traversing the list and bringing all the nodes into cache.
217 void clearAndLeakNodesUnsafely() { base_list_type::clear(); }
218
219private:
220 // transfer - The heart of the splice function. Move linked list nodes from
221 // [first, last) into position.
222 //
223 void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
224 if (position == last)
225 return;
226
227 // Notify traits we moved the nodes...
228 this->transferNodesFromList(L2, first, last);
229
230 base_list_type::splice(position, L2, first, last);
231 }
232
233public:
234 //===----------------------------------------------------------------------===
235 // Functionality derived from other functions defined above...
236 //
237
238 using base_list_type::size;
239
240 iterator erase(iterator first, iterator last) {
241 while (first != last)
242 first = erase(first);
243 return last;
244 }
245
246 void clear() { erase(begin(), end()); }
247
248 // Front and back inserters...
249 void push_front(pointer val) { insert(begin(), val); }
250 void push_back(pointer val) { insert(end(), val); }
251 void pop_front() {
252 assert(!empty() && "pop_front() on empty list!");
253 erase(begin());
254 }
255 void pop_back() {
256 assert(!empty() && "pop_back() on empty list!");
257 iterator t = end(); erase(--t);
258 }
259
260 // Special forms of insert...
261 template<class InIt> void insert(iterator where, InIt first, InIt last) {
262 for (; first != last; ++first) insert(where, *first);
263 }
264
265 // Splice members - defined in terms of transfer...
266 void splice(iterator where, iplist_impl &L2) {
267 if (!L2.empty())
268 transfer(position: where, L2, first: L2.begin(), last: L2.end());
269 }
270 void splice(iterator where, iplist_impl &L2, iterator first) {
271 iterator last = first; ++last;
272 if (where == first || where == last) return; // No change
273 transfer(position: where, L2, first, last);
274 }
275 void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
276 if (first != last) transfer(position: where, L2, first, last);
277 }
278 void splice(iterator where, iplist_impl &L2, reference N) {
279 splice(where, L2, iterator(N));
280 }
281 void splice(iterator where, iplist_impl &L2, pointer N) {
282 splice(where, L2, iterator(N));
283 }
284
285 template <class Compare>
286 void merge(iplist_impl &Right, Compare comp) {
287 if (this == &Right)
288 return;
289 this->transferNodesFromList(Right, Right.begin(), Right.end());
290 base_list_type::merge(Right, comp);
291 }
292 void merge(iplist_impl &Right) { return merge(Right, op_less); }
293
294 using base_list_type::sort;
295
296 /// Get the previous node, or \c nullptr for the list head.
297 pointer getPrevNode(reference N) const {
298 auto I = N.getIterator();
299 if (I == begin())
300 return nullptr;
301 return &*std::prev(I);
302 }
303 /// Get the previous node, or \c nullptr for the list head.
304 const_pointer getPrevNode(const_reference N) const {
305 return getPrevNode(const_cast<reference >(N));
306 }
307
308 /// Get the next node, or \c nullptr for the list tail.
309 pointer getNextNode(reference N) const {
310 auto Next = std::next(N.getIterator());
311 if (Next == end())
312 return nullptr;
313 return &*Next;
314 }
315 /// Get the next node, or \c nullptr for the list tail.
316 const_pointer getNextNode(const_reference N) const {
317 return getNextNode(const_cast<reference >(N));
318 }
319};
320
321/// An intrusive list with ownership and callbacks specified/controlled by
322/// ilist_traits, only with API safe for polymorphic types.
323///
324/// The \p Options parameters are the same as those for \a simple_ilist. See
325/// there for a description of what's available.
326template <class T, class... Options>
327class iplist
328 : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
329 using iplist_impl_type = typename iplist::iplist_impl;
330
331public:
332 iplist() = default;
333
334 iplist(const iplist &X) = delete;
335 iplist &operator=(const iplist &X) = delete;
336
337 iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
338 iplist &operator=(iplist &&X) {
339 *static_cast<iplist_impl_type *>(this) = std::move(X);
340 return *this;
341 }
342};
343
344template <class T, class... Options> using ilist = iplist<T, Options...>;
345
346} // end namespace llvm
347
348namespace std {
349
350 // Ensure that swap uses the fast list swap...
351 template<class Ty>
352 void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
353 Left.swap(Right);
354 }
355
356} // end namespace std
357
358#endif // LLVM_ADT_ILIST_H
359