LLVM  10.0.0svn
ilist.h
Go to the documentation of this file.
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 
31 namespace 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
40 template <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
56 template <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.
64 template <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.
81 template <typename NodeTy>
83  ilist_callback_traits<NodeTy> {};
84 
85 /// Template traits for intrusive list.
86 ///
87 /// Customize callbacks and allocation semantics.
88 template <typename NodeTy>
89 struct ilist_traits : public ilist_node_traits<NodeTy> {};
90 
91 /// Const traits should never be instantiated.
92 template <typename Ty> struct ilist_traits<const Ty> {};
93 
94 namespace ilist_detail {
95 
96 template <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).
100 template <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 
109 public:
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).
115 template <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 
123 public:
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.
130 template <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 
139 public:
140  static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
141 };
142 
143 template <class TraitsT, class NodeT> struct HasObsoleteCustomization {
144  static const bool value = HasGetNext<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.
165 template <class IntrusiveListT, class TraitsT>
166 class iplist_impl : public TraitsT, IntrusiveListT {
167  typedef IntrusiveListT base_list_type;
168 
169 public:
180  typedef
182 
183 private:
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(
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 
194 public:
195  iplist_impl() = default;
196 
197  iplist_impl(const iplist_impl &) = delete;
198  iplist_impl &operator=(const iplist_impl &) = delete;
199 
201  : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {}
203  *static_cast<TraitsT *>(this) = std::move(X);
204  *static_cast<IntrusiveListT *>(this) = std::move(X);
205  return *this;
206  }
207 
209 
210  // Miscellaneous inspection routines.
211  size_type max_size() const { return size_type(-1); }
212 
213  using base_list_type::begin;
214  using base_list_type::end;
216  using base_list_type::rend;
217  using base_list_type::empty;
218  using base_list_type::front;
219  using base_list_type::back;
220 
221  void swap(iplist_impl &RHS) {
222  assert(0 && "Swap does not use list traits callback correctly yet!");
224  }
225 
226  iterator insert(iterator where, pointer New) {
227  this->addNodeToList(New); // Notify traits that we added a node...
228  return base_list_type::insert(where, *New);
229  }
230 
231  iterator insert(iterator where, const_reference New) {
232  return this->insert(where, new value_type(New));
233  }
234 
235  iterator insertAfter(iterator where, pointer New) {
236  if (empty())
237  return insert(begin(), New);
238  else
239  return insert(++where, New);
240  }
241 
242  /// Clone another list.
243  template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
244  clear();
245  for (const_reference V : L2)
246  push_back(clone(V));
247  }
248 
249  pointer remove(iterator &IT) {
250  pointer Node = &*IT++;
251  this->removeNodeFromList(Node); // Notify traits that we removed a node...
252  base_list_type::remove(*Node);
253  return Node;
254  }
255 
256  pointer remove(const iterator &IT) {
257  iterator MutIt = IT;
258  return remove(MutIt);
259  }
260 
261  pointer remove(pointer IT) { return remove(iterator(IT)); }
262  pointer remove(reference IT) { return remove(iterator(IT)); }
263 
264  // erase - remove a node from the controlled sequence... and delete it.
265  iterator erase(iterator where) {
266  this->deleteNode(remove(where));
267  return where;
268  }
269 
270  iterator erase(pointer IT) { return erase(iterator(IT)); }
271  iterator erase(reference IT) { return erase(iterator(IT)); }
272 
273  /// Remove all nodes from the list like clear(), but do not call
274  /// removeNodeFromList() or deleteNode().
275  ///
276  /// This should only be used immediately before freeing nodes in bulk to
277  /// avoid traversing the list and bringing all the nodes into cache.
279 
280 private:
281  // transfer - The heart of the splice function. Move linked list nodes from
282  // [first, last) into position.
283  //
284  void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
285  if (position == last)
286  return;
287 
288  // Notify traits we moved the nodes...
289  this->transferNodesFromList(L2, first, last);
290 
291  base_list_type::splice(position, L2, first, last);
292  }
293 
294 public:
295  //===----------------------------------------------------------------------===
296  // Functionality derived from other functions defined above...
297  //
298 
299  using base_list_type::size;
300 
301  iterator erase(iterator first, iterator last) {
302  while (first != last)
303  first = erase(first);
304  return last;
305  }
306 
307  void clear() { erase(begin(), end()); }
308 
309  // Front and back inserters...
310  void push_front(pointer val) { insert(begin(), val); }
311  void push_back(pointer val) { insert(end(), val); }
312  void pop_front() {
313  assert(!empty() && "pop_front() on empty list!");
314  erase(begin());
315  }
316  void pop_back() {
317  assert(!empty() && "pop_back() on empty list!");
318  iterator t = end(); erase(--t);
319  }
320 
321  // Special forms of insert...
322  template<class InIt> void insert(iterator where, InIt first, InIt last) {
323  for (; first != last; ++first) insert(where, *first);
324  }
325 
326  // Splice members - defined in terms of transfer...
327  void splice(iterator where, iplist_impl &L2) {
328  if (!L2.empty())
329  transfer(where, L2, L2.begin(), L2.end());
330  }
331  void splice(iterator where, iplist_impl &L2, iterator first) {
332  iterator last = first; ++last;
333  if (where == first || where == last) return; // No change
334  transfer(where, L2, first, last);
335  }
336  void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
337  if (first != last) transfer(where, L2, first, last);
338  }
339  void splice(iterator where, iplist_impl &L2, reference N) {
340  splice(where, L2, iterator(N));
341  }
342  void splice(iterator where, iplist_impl &L2, pointer N) {
343  splice(where, L2, iterator(N));
344  }
345 
346  template <class Compare>
348  if (this == &Right)
349  return;
350  this->transferNodesFromList(Right, Right.begin(), Right.end());
351  base_list_type::merge(Right, comp);
352  }
353  void merge(iplist_impl &Right) { return merge(Right, op_less); }
354 
355  using base_list_type::sort;
356 
357  /// Get the previous node, or \c nullptr for the list head.
358  pointer getPrevNode(reference N) const {
359  auto I = N.getIterator();
360  if (I == begin())
361  return nullptr;
362  return &*std::prev(I);
363  }
364  /// Get the previous node, or \c nullptr for the list head.
365  const_pointer getPrevNode(const_reference N) const {
366  return getPrevNode(const_cast<reference >(N));
367  }
368 
369  /// Get the next node, or \c nullptr for the list tail.
370  pointer getNextNode(reference N) const {
371  auto Next = std::next(N.getIterator());
372  if (Next == end())
373  return nullptr;
374  return &*Next;
375  }
376  /// Get the next node, or \c nullptr for the list tail.
377  const_pointer getNextNode(const_reference N) const {
378  return getNextNode(const_cast<reference >(N));
379  }
380 };
381 
382 /// An intrusive list with ownership and callbacks specified/controlled by
383 /// ilist_traits, only with API safe for polymorphic types.
384 ///
385 /// The \p Options parameters are the same as those for \a simple_ilist. See
386 /// there for a description of what's available.
387 template <class T, class... Options>
388 class iplist
389  : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
390  using iplist_impl_type = typename iplist::iplist_impl;
391 
392 public:
393  iplist() = default;
394 
395  iplist(const iplist &X) = delete;
396  iplist &operator=(const iplist &X) = delete;
397 
398  iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
400  *static_cast<iplist_impl_type *>(this) = std::move(X);
401  return *this;
402  }
403 };
404 
405 template <class T, class... Options> using ilist = iplist<T, Options...>;
406 
407 } // end namespace llvm
408 
409 namespace std {
410 
411  // Ensure that swap uses the fast list swap...
412  template<class Ty>
414  Left.swap(Right);
415  }
416 
417 } // end namespace std
418 
419 #endif // LLVM_ADT_ILIST_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
base_list_type::const_iterator const_iterator
Definition: ilist.h:178
iterator erase(reference IT)
Definition: ilist.h:271
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
iterator erase(iterator where)
Definition: ilist.h:265
base_list_type::const_reverse_iterator const_reverse_iterator
Definition: ilist.h:181
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void addNodeToList(NodeTy *)
When an MBB is added to an MF, we need to update the parent pointer of the MBB, the MBB numbering...
Definition: ilist.h:65
A wrapper around an intrusive list with callbacks and non-intrusive ownership.
Definition: ilist.h:166
typename OptionsT::const_reference const_reference
Definition: simple_ilist.h:94
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
void insert(iterator where, InIt first, InIt last)
Definition: ilist.h:322
Template traits for intrusive list.
Definition: ilist.h:89
pointer getPrevNode(reference N) const
Get the previous node, or nullptr for the list head.
Definition: ilist.h:358
void splice(iterator where, iplist_impl &L2, iterator first, iterator last)
Definition: ilist.h:336
const_pointer getPrevNode(const_reference N) const
Get the previous node, or nullptr for the list head.
Definition: ilist.h:365
Custom traits to do nothing on deletion.
Definition: ilist.h:56
Definition: BitVector.h:937
reverse_iterator rbegin(StringRef path, Style style=Style::native)
Get reverse begin iterator over path.
Definition: Path.cpp:295
Type trait to check for a traits class that has a createSentinel member (as a canary for any of the i...
Definition: ilist.h:115
base_list_type::const_pointer const_pointer
Definition: ilist.h:171
static void deleteNode(NodeTy *V)
Definition: ilist.h:57
base_list_type::difference_type difference_type
Definition: ilist.h:176
iterator erase(pointer IT)
Definition: ilist.h:270
Type trait to check for a traits class that has a createNode member.
Definition: ilist.h:130
iplist_impl(iplist_impl &&X)
Definition: ilist.h:200
typename OptionsT::const_pointer const_pointer
Definition: simple_ilist.h:93
void merge(iplist_impl &Right, Compare comp)
Definition: ilist.h:347
Use delete by default for iplist and ilist.
Definition: ilist.h:40
iplist_impl & operator=(iplist_impl &&X)
Definition: ilist.h:202
void push_front(pointer val)
Definition: ilist.h:310
void merge(iplist_impl &Right)
Definition: ilist.h:353
Type trait to check for a traits class that has a getNext member (as a canary for any of the ilist_ne...
Definition: ilist.h:100
void pop_front()
Definition: ilist.h:312
void splice(iterator where, iplist_impl &L2, iterator first)
Definition: ilist.h:331
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:327
base_list_type::const_reference const_reference
Definition: ilist.h:173
base_list_type::reference reference
Definition: ilist.h:172
A fragment for template traits for intrusive list that provides default node related operations...
Definition: ilist.h:82
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:388
pointer getNextNode(reference N) const
Get the next node, or nullptr for the list tail.
Definition: ilist.h:370
void splice(iterator where, iplist_impl &L2, reference N)
Definition: ilist.h:339
unsigned first
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
Iterator for intrusive lists based on ilist_node.
base_list_type::iterator iterator
Definition: ilist.h:177
base_list_type::size_type size_type
Definition: ilist.h:175
void swap(llvm::iplist< Ty > &Left, llvm::iplist< Ty > &Right)
Definition: ilist.h:413
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
void removeNodeFromList(NodeTy *)
Definition: ilist.h:66
size_type max_size() const
Definition: ilist.h:211
static void deleteNode(NodeTy *V)
Definition: ilist.h:41
iplist & operator=(iplist &&X)
Definition: ilist.h:399
void splice(iterator where, iplist_impl &L2, pointer N)
Definition: ilist.h:342
void push_back(pointer val)
Definition: ilist.h:311
iterator erase(iterator first, iterator last)
Definition: ilist.h:301
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:225
typename OptionsT::value_type value_type
Definition: simple_ilist.h:90
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
iplist(iplist &&X)
Definition: ilist.h:398
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
base_list_type::pointer pointer
Definition: ilist.h:170
void clear()
Definition: ilist.h:307
#define I(x, y, z)
Definition: MD5.cpp:58
void swap(iplist_impl &RHS)
Definition: ilist.h:221
#define N
iterator insert(iterator where, const_reference New)
Definition: ilist.h:231
reverse_iterator rend(StringRef path)
Get reverse end iterator over path.
Definition: Path.cpp:304
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
void clearAndLeakNodesUnsafely()
Remove all nodes from the list like clear(), but do not call removeNodeFromList() or deleteNode()...
Definition: ilist.h:278
Callbacks do nothing by default in iplist and ilist.
Definition: ilist.h:64
const_pointer getNextNode(const_reference N) const
Get the next node, or nullptr for the list tail.
Definition: ilist.h:377
void pop_back()
Definition: ilist.h:316
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:235
base_list_type::reverse_iterator reverse_iterator
Definition: ilist.h:179
typename OptionsT::reference reference
Definition: simple_ilist.h:92
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:71
base_list_type::value_type value_type
Definition: ilist.h:174
void cloneFrom(const iplist_impl &L2, Cloner clone)
Clone another list.
Definition: ilist.h:243