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