LLVM  6.0.0svn
ilist.h
Go to the documentation of this file.
1 //==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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 
32 namespace 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
41 template <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
57 template <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.
65 template <typename NodeTy> struct ilist_callback_traits {
66  void addNodeToList(NodeTy *) {}
67  void removeNodeFromList(NodeTy *) {}
68 
69  /// Callback before transferring nodes to this list.
70  ///
71  /// \pre \c this!=&OldList
72  template <class Iterator>
73  void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
74  Iterator /*last*/) {
75  (void)OldList;
76  }
77 };
78 
79 /// A fragment for template traits for intrusive list that provides default
80 /// node related operations.
81 ///
82 /// TODO: Remove this layer of indirection. It's not necessary.
83 template <typename NodeTy>
85  ilist_callback_traits<NodeTy> {};
86 
87 /// Default template traits for intrusive list.
88 ///
89 /// By inheriting from this, you can easily use default implementations for all
90 /// common operations.
91 ///
92 /// TODO: Remove this customization point. Specializing ilist_traits is
93 /// already fully general.
94 template <typename NodeTy>
95 struct ilist_default_traits : public ilist_node_traits<NodeTy> {};
96 
97 /// Template traits for intrusive list.
98 ///
99 /// Customize callbacks and allocation semantics.
100 template <typename NodeTy>
101 struct ilist_traits : public ilist_default_traits<NodeTy> {};
102 
103 /// Const traits should never be instantiated.
104 template <typename Ty> struct ilist_traits<const Ty> {};
105 
106 namespace ilist_detail {
107 
108 template <class T> T &make();
109 
110 /// Type trait to check for a traits class that has a getNext member (as a
111 /// canary for any of the ilist_nextprev_traits API).
112 template <class TraitsT, class NodeT> struct HasGetNext {
113  typedef char Yes[1];
114  typedef char No[2];
115  template <size_t N> struct SFINAE {};
116 
117  template <class U>
118  static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0);
119  template <class> static No &test(...);
120 
121 public:
122  static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
123 };
124 
125 /// Type trait to check for a traits class that has a createSentinel member (as
126 /// a canary for any of the ilist_sentinel_traits API).
127 template <class TraitsT> struct HasCreateSentinel {
128  typedef char Yes[1];
129  typedef char No[2];
130 
131  template <class U>
132  static Yes &test(U *I, decltype(I->createSentinel()) * = 0);
133  template <class> static No &test(...);
134 
135 public:
136  static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
137 };
138 
139 /// Type trait to check for a traits class that has a createNode member.
140 /// Allocation should be managed in a wrapper class, instead of in
141 /// ilist_traits.
142 template <class TraitsT, class NodeT> struct HasCreateNode {
143  typedef char Yes[1];
144  typedef char No[2];
145  template <size_t N> struct SFINAE {};
146 
147  template <class U>
148  static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0);
149  template <class> static No &test(...);
150 
151 public:
152  static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
153 };
154 
155 template <class TraitsT, class NodeT> struct HasObsoleteCustomization {
156  static const bool value = HasGetNext<TraitsT, NodeT>::value ||
159 };
160 
161 } // end namespace ilist_detail
162 
163 //===----------------------------------------------------------------------===//
164 //
165 /// A wrapper around an intrusive list with callbacks and non-intrusive
166 /// ownership.
167 ///
168 /// This wraps a purely intrusive list (like simple_ilist) with a configurable
169 /// traits class. The traits can implement callbacks and customize the
170 /// ownership semantics.
171 ///
172 /// This is a subset of ilist functionality that can safely be used on nodes of
173 /// polymorphic types, i.e. a heterogeneous list with a common base class that
174 /// holds the next/prev pointers. The only state of the list itself is an
175 /// ilist_sentinel, which holds pointers to the first and last nodes in the
176 /// list.
177 template <class IntrusiveListT, class TraitsT>
178 class iplist_impl : public TraitsT, IntrusiveListT {
179  typedef IntrusiveListT base_list_type;
180 
181 protected:
183 
184 public:
195  typedef
197 
198 private:
199  // TODO: Drop this assertion and the transitive type traits anytime after
200  // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code
201  // update).
202  static_assert(
204  "ilist customization points have changed!");
205 
206  static bool op_less(const_reference L, const_reference R) { return L < R; }
207  static bool op_equal(const_reference L, const_reference R) { return L == R; }
208 
209 public:
210  iplist_impl() = default;
211 
212  iplist_impl(const iplist_impl &) = delete;
213  iplist_impl &operator=(const iplist_impl &) = delete;
214 
216  : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {}
218  *static_cast<TraitsT *>(this) = std::move(X);
219  *static_cast<IntrusiveListT *>(this) = std::move(X);
220  return *this;
221  }
222 
224 
225  // Miscellaneous inspection routines.
226  size_type max_size() const { return size_type(-1); }
227 
228  using base_list_type::begin;
229  using base_list_type::end;
231  using base_list_type::rend;
232  using base_list_type::empty;
233  using base_list_type::front;
234  using base_list_type::back;
235 
236  void swap(iplist_impl &RHS) {
237  assert(0 && "Swap does not use list traits callback correctly yet!");
239  }
240 
241  iterator insert(iterator where, pointer New) {
242  this->addNodeToList(New); // Notify traits that we added a node...
243  return base_list_type::insert(where, *New);
244  }
245 
246  iterator insert(iterator where, const_reference New) {
247  return this->insert(where, new value_type(New));
248  }
249 
250  iterator insertAfter(iterator where, pointer New) {
251  if (empty())
252  return insert(begin(), New);
253  else
254  return insert(++where, New);
255  }
256 
257  /// Clone another list.
258  template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
259  clear();
260  for (const_reference V : L2)
261  push_back(clone(V));
262  }
263 
264  pointer remove(iterator &IT) {
265  pointer Node = &*IT++;
266  this->removeNodeFromList(Node); // Notify traits that we removed a node...
267  base_list_type::remove(*Node);
268  return Node;
269  }
270 
271  pointer remove(const iterator &IT) {
272  iterator MutIt = IT;
273  return remove(MutIt);
274  }
275 
276  pointer remove(pointer IT) { return remove(iterator(IT)); }
277  pointer remove(reference IT) { return remove(iterator(IT)); }
278 
279  // erase - remove a node from the controlled sequence... and delete it.
280  iterator erase(iterator where) {
281  this->deleteNode(remove(where));
282  return where;
283  }
284 
285  iterator erase(pointer IT) { return erase(iterator(IT)); }
286  iterator erase(reference IT) { return erase(iterator(IT)); }
287 
288  /// Remove all nodes from the list like clear(), but do not call
289  /// removeNodeFromList() or deleteNode().
290  ///
291  /// This should only be used immediately before freeing nodes in bulk to
292  /// avoid traversing the list and bringing all the nodes into cache.
294 
295 private:
296  // transfer - The heart of the splice function. Move linked list nodes from
297  // [first, last) into position.
298  //
299  void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
300  if (position == last)
301  return;
302 
303  if (this != &L2) // Notify traits we moved the nodes...
304  this->transferNodesFromList(L2, first, last);
305 
306  base_list_type::splice(position, L2, first, last);
307  }
308 
309 public:
310  //===----------------------------------------------------------------------===
311  // Functionality derived from other functions defined above...
312  //
313 
314  using base_list_type::size;
315 
316  iterator erase(iterator first, iterator last) {
317  while (first != last)
318  first = erase(first);
319  return last;
320  }
321 
322  void clear() { erase(begin(), end()); }
323 
324  // Front and back inserters...
325  void push_front(pointer val) { insert(begin(), val); }
326  void push_back(pointer val) { insert(end(), val); }
327  void pop_front() {
328  assert(!empty() && "pop_front() on empty list!");
329  erase(begin());
330  }
331  void pop_back() {
332  assert(!empty() && "pop_back() on empty list!");
333  iterator t = end(); erase(--t);
334  }
335 
336  // Special forms of insert...
337  template<class InIt> void insert(iterator where, InIt first, InIt last) {
338  for (; first != last; ++first) insert(where, *first);
339  }
340 
341  // Splice members - defined in terms of transfer...
342  void splice(iterator where, iplist_impl &L2) {
343  if (!L2.empty())
344  transfer(where, L2, L2.begin(), L2.end());
345  }
346  void splice(iterator where, iplist_impl &L2, iterator first) {
347  iterator last = first; ++last;
348  if (where == first || where == last) return; // No change
349  transfer(where, L2, first, last);
350  }
351  void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
352  if (first != last) transfer(where, L2, first, last);
353  }
354  void splice(iterator where, iplist_impl &L2, reference N) {
355  splice(where, L2, iterator(N));
356  }
357  void splice(iterator where, iplist_impl &L2, pointer N) {
358  splice(where, L2, iterator(N));
359  }
360 
361  template <class Compare>
363  if (this == &Right)
364  return;
365  this->transferNodesFromList(Right, Right.begin(), Right.end());
366  base_list_type::merge(Right, comp);
367  }
368  void merge(iplist_impl &Right) { return merge(Right, op_less); }
369 
370  using base_list_type::sort;
371 
372  /// \brief Get the previous node, or \c nullptr for the list head.
373  pointer getPrevNode(reference N) const {
374  auto I = N.getIterator();
375  if (I == begin())
376  return nullptr;
377  return &*std::prev(I);
378  }
379  /// \brief Get the previous node, or \c nullptr for the list head.
380  const_pointer getPrevNode(const_reference N) const {
381  return getPrevNode(const_cast<reference >(N));
382  }
383 
384  /// \brief Get the next node, or \c nullptr for the list tail.
385  pointer getNextNode(reference N) const {
386  auto Next = std::next(N.getIterator());
387  if (Next == end())
388  return nullptr;
389  return &*Next;
390  }
391  /// \brief Get the next node, or \c nullptr for the list tail.
392  const_pointer getNextNode(const_reference N) const {
393  return getNextNode(const_cast<reference >(N));
394  }
395 };
396 
397 /// An intrusive list with ownership and callbacks specified/controlled by
398 /// ilist_traits, only with API safe for polymorphic types.
399 ///
400 /// The \p Options parameters are the same as those for \a simple_ilist. See
401 /// there for a description of what's available.
402 template <class T, class... Options>
403 class iplist
404  : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
405  typedef typename iplist::iplist_impl_type iplist_impl_type;
406 
407 public:
408  iplist() = default;
409 
410  iplist(const iplist &X) = delete;
411  iplist &operator=(const iplist &X) = delete;
412 
413  iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
415  *static_cast<iplist_impl_type *>(this) = std::move(X);
416  return *this;
417  }
418 };
419 
420 template <class T, class... Options> using ilist = iplist<T, Options...>;
421 
422 } // end namespace llvm
423 
424 namespace std {
425 
426  // Ensure that swap uses the fast list swap...
427  template<class Ty>
429  Left.swap(Right);
430  }
431 
432 } // end namespace std
433 
434 #endif // LLVM_ADT_ILIST_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:243
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
base_list_type::const_iterator const_iterator
Definition: ilist.h:193
iterator erase(reference IT)
Definition: ilist.h:286
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:234
iterator erase(iterator where)
Definition: ilist.h:280
base_list_type::const_reverse_iterator const_reverse_iterator
Definition: ilist.h:196
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:66
A wrapper around an intrusive list with callbacks and non-intrusive ownership.
Definition: ilist.h:178
typename OptionsT::const_reference const_reference
Definition: simple_ilist.h:95
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
void insert(iterator where, InIt first, InIt last)
Definition: ilist.h:337
Template traits for intrusive list.
Definition: ilist.h:101
pointer getPrevNode(reference N) const
Get the previous node, or nullptr for the list head.
Definition: ilist.h:373
void splice(iterator where, iplist_impl &L2, iterator first, iterator last)
Definition: ilist.h:351
const_pointer getPrevNode(const_reference N) const
Get the previous node, or nullptr for the list head.
Definition: ilist.h:380
Custom traits to do nothing on deletion.
Definition: ilist.h:57
Definition: BitVector.h:920
reverse_iterator rbegin(StringRef path, Style style=Style::native)
Get reverse begin iterator over path.
Definition: Path.cpp:305
Type trait to check for a traits class that has a createSentinel member (as a canary for any of the i...
Definition: ilist.h:127
Default template traits for intrusive list.
Definition: ilist.h:95
base_list_type::const_pointer const_pointer
Definition: ilist.h:186
static void deleteNode(NodeTy *V)
Definition: ilist.h:58
#define T
base_list_type::difference_type difference_type
Definition: ilist.h:191
iterator erase(pointer IT)
Definition: ilist.h:285
Type trait to check for a traits class that has a createNode member.
Definition: ilist.h:142
iplist_impl(iplist_impl &&X)
Definition: ilist.h:215
typename OptionsT::const_pointer const_pointer
Definition: simple_ilist.h:94
void merge(iplist_impl &Right, Compare comp)
Definition: ilist.h:362
Use delete by default for iplist and ilist.
Definition: ilist.h:41
iplist_impl & operator=(iplist_impl &&X)
Definition: ilist.h:217
void push_front(pointer val)
Definition: ilist.h:325
void merge(iplist_impl &Right)
Definition: ilist.h:368
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:112
void pop_front()
Definition: ilist.h:327
void splice(iterator where, iplist_impl &L2, iterator first)
Definition: ilist.h:346
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:342
base_list_type::const_reference const_reference
Definition: ilist.h:188
base_list_type::reference reference
Definition: ilist.h:187
A fragment for template traits for intrusive list that provides default node related operations...
Definition: ilist.h:84
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:403
pointer getNextNode(reference N) const
Get the next node, or nullptr for the list tail.
Definition: ilist.h:385
void splice(iterator where, iplist_impl &L2, reference N)
Definition: ilist.h:354
unsigned first
Iterator for intrusive lists based on ilist_node.
base_list_type::iterator iterator
Definition: ilist.h:192
base_list_type::size_type size_type
Definition: ilist.h:190
void swap(llvm::iplist< Ty > &Left, llvm::iplist< Ty > &Right)
Definition: ilist.h:428
void removeNodeFromList(NodeTy *)
Definition: ilist.h:67
size_type max_size() const
Definition: ilist.h:226
static void deleteNode(NodeTy *V)
Definition: ilist.h:42
iplist & operator=(iplist &&X)
Definition: ilist.h:414
void splice(iterator where, iplist_impl &L2, pointer N)
Definition: ilist.h:357
void push_back(pointer val)
Definition: ilist.h:326
iterator erase(iterator first, iterator last)
Definition: ilist.h:316
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:210
typename OptionsT::value_type value_type
Definition: simple_ilist.h:91
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:413
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
base_list_type::pointer pointer
Definition: ilist.h:185
void clear()
Definition: ilist.h:322
#define I(x, y, z)
Definition: MD5.cpp:58
void swap(iplist_impl &RHS)
Definition: ilist.h:236
#define N
iterator insert(iterator where, const_reference New)
Definition: ilist.h:246
reverse_iterator rend(StringRef path)
Get reverse end iterator over path.
Definition: Path.cpp:313
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:293
Callbacks do nothing by default in iplist and ilist.
Definition: ilist.h:65
const_pointer getNextNode(const_reference N) const
Get the next node, or nullptr for the list tail.
Definition: ilist.h:392
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
iplist_impl iplist_impl_type
Definition: ilist.h:182
void pop_back()
Definition: ilist.h:331
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:250
base_list_type::reverse_iterator reverse_iterator
Definition: ilist.h:194
typename OptionsT::reference reference
Definition: simple_ilist.h:93
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:73
base_list_type::value_type value_type
Definition: ilist.h:189
void cloneFrom(const iplist_impl &L2, Cloner clone)
Clone another list.
Definition: ilist.h:258