LLVM  6.0.0svn
simple_ilist.h
Go to the documentation of this file.
1 //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- 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 #ifndef LLVM_ADT_SIMPLE_ILIST_H
11 #define LLVM_ADT_SIMPLE_ILIST_H
12 
13 #include "llvm/ADT/ilist_base.h"
15 #include "llvm/ADT/ilist_node.h"
17 #include "llvm/Support/Compiler.h"
18 #include <algorithm>
19 #include <cassert>
20 #include <cstddef>
21 #include <functional>
22 #include <iterator>
23 #include <utility>
24 
25 namespace llvm {
26 
27 /// A simple intrusive list implementation.
28 ///
29 /// This is a simple intrusive list for a \c T that inherits from \c
30 /// ilist_node<T>. The list never takes ownership of anything inserted in it.
31 ///
32 /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never allocates or
33 /// deletes values, and has no callback traits.
34 ///
35 /// The API for adding nodes include \a push_front(), \a push_back(), and \a
36 /// insert(). These all take values by reference (not by pointer), except for
37 /// the range version of \a insert().
38 ///
39 /// There are three sets of API for discarding nodes from the list: \a
40 /// remove(), which takes a reference to the node to remove, \a erase(), which
41 /// takes an iterator or iterator range and returns the next one, and \a
42 /// clear(), which empties out the container. All three are constant time
43 /// operations. None of these deletes any nodes; in particular, if there is a
44 /// single node in the list, then these have identical semantics:
45 /// \li \c L.remove(L.front());
46 /// \li \c L.erase(L.begin());
47 /// \li \c L.clear();
48 ///
49 /// As a convenience for callers, there are parallel APIs that take a \c
50 /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
51 /// eraseAndDispose(), and \a clearAndDispose(). These have different names
52 /// because the extra semantic is otherwise non-obvious. They are equivalent
53 /// to calling \a std::for_each() on the range to be discarded.
54 ///
55 /// The currently available \p Options customize the nodes in the list. The
56 /// same options must be specified in the \a ilist_node instantation for
57 /// compatibility (although the order is irrelevant).
58 /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this
59 /// list should use. This is useful if a type \p T is part of multiple,
60 /// independent lists simultaneously.
61 /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a
62 /// node is a sentinel. Specifying \c true enables the \a
63 /// ilist_node::isSentinel() API. Unlike \a ilist_node::isKnownSentinel(),
64 /// which is only appropriate for assertions, \a ilist_node::isSentinel() is
65 /// appropriate for real logic.
66 ///
67 /// Here are examples of \p Options usage:
68 /// \li \c simple_ilist<T> gives the defaults. \li \c
69 /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a
70 /// ilist_node::isSentinel() API.
71 /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>>
72 /// specifies a tag of A and that tracking should be off (even when
73 /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
74 /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is
75 /// equivalent to the last.
76 ///
77 /// See \a is_valid_option for steps on adding a new option.
78 template <typename T, class... Options>
80  : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
82  typename ilist_detail::compute_node_options<T, Options...>::type> {
84  "Unrecognized node option!");
85  using OptionsT =
86  typename ilist_detail::compute_node_options<T, Options...>::type;
87  using list_base_type = typename OptionsT::list_base_type;
88  ilist_sentinel<OptionsT> Sentinel;
89 
90 public:
91  using value_type = typename OptionsT::value_type;
92  using pointer = typename OptionsT::pointer;
93  using reference = typename OptionsT::reference;
94  using const_pointer = typename OptionsT::const_pointer;
95  using const_reference = typename OptionsT::const_reference;
100  using size_type = size_t;
102 
103  simple_ilist() = default;
104  ~simple_ilist() = default;
105 
106  // No copy constructors.
107  simple_ilist(const simple_ilist &) = delete;
108  simple_ilist &operator=(const simple_ilist &) = delete;
109 
110  // Move constructors.
113  clear();
114  splice(end(), X);
115  return *this;
116  }
117 
118  iterator begin() { return ++iterator(Sentinel); }
119  const_iterator begin() const { return ++const_iterator(Sentinel); }
120  iterator end() { return iterator(Sentinel); }
121  const_iterator end() const { return const_iterator(Sentinel); }
122  reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
124  return ++const_reverse_iterator(Sentinel);
125  }
126  reverse_iterator rend() { return reverse_iterator(Sentinel); }
128  return const_reverse_iterator(Sentinel);
129  }
130 
131  /// Check if the list is empty in constant time.
132  LLVM_NODISCARD bool empty() const { return Sentinel.empty(); }
133 
134  /// Calculate the size of the list in linear time.
136  return std::distance(begin(), end());
137  }
138 
139  reference front() { return *begin(); }
140  const_reference front() const { return *begin(); }
141  reference back() { return *rbegin(); }
142  const_reference back() const { return *rbegin(); }
143 
144  /// Insert a node at the front; never copies.
145  void push_front(reference Node) { insert(begin(), Node); }
146 
147  /// Insert a node at the back; never copies.
148  void push_back(reference Node) { insert(end(), Node); }
149 
150  /// Remove the node at the front; never deletes.
151  void pop_front() { erase(begin()); }
152 
153  /// Remove the node at the back; never deletes.
154  void pop_back() { erase(--end()); }
155 
156  /// Swap with another list in place using std::swap.
157  void swap(simple_ilist &X) { std::swap(*this, X); }
158 
159  /// Insert a node by reference; never copies.
161  list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
162  return iterator(&Node);
163  }
164 
165  /// Insert a range of nodes; never copies.
166  template <class Iterator>
167  void insert(iterator I, Iterator First, Iterator Last) {
168  for (; First != Last; ++First)
169  insert(I, *First);
170  }
171 
172  /// Clone another list.
173  template <class Cloner, class Disposer>
174  void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
175  clearAndDispose(dispose);
176  for (const_reference V : L2)
177  push_back(*clone(V));
178  }
179 
180  /// Remove a node by reference; never deletes.
181  ///
182  /// \see \a erase() for removing by iterator.
183  /// \see \a removeAndDispose() if the node should be deleted.
184  void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }
185 
186  /// Remove a node by reference and dispose of it.
187  template <class Disposer>
188  void removeAndDispose(reference N, Disposer dispose) {
189  remove(N);
190  dispose(&N);
191  }
192 
193  /// Remove a node by iterator; never deletes.
194  ///
195  /// \see \a remove() for removing by reference.
196  /// \see \a eraseAndDispose() it the node should be deleted.
198  assert(I != end() && "Cannot remove end of list!");
199  remove(*I++);
200  return I;
201  }
202 
203  /// Remove a range of nodes; never deletes.
204  ///
205  /// \see \a eraseAndDispose() if the nodes should be deleted.
207  list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
208  return Last;
209  }
210 
211  /// Remove a node by iterator and dispose of it.
212  template <class Disposer>
213  iterator eraseAndDispose(iterator I, Disposer dispose) {
214  auto Next = std::next(I);
215  erase(I);
216  dispose(&*I);
217  return Next;
218  }
219 
220  /// Remove a range of nodes and dispose of them.
221  template <class Disposer>
222  iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
223  while (First != Last)
224  First = eraseAndDispose(First, dispose);
225  return Last;
226  }
227 
228  /// Clear the list; never deletes.
229  ///
230  /// \see \a clearAndDispose() if the nodes should be deleted.
231  void clear() { Sentinel.reset(); }
232 
233  /// Clear the list and dispose of the nodes.
234  template <class Disposer> void clearAndDispose(Disposer dispose) {
235  eraseAndDispose(begin(), end(), dispose);
236  }
237 
238  /// Splice in another list.
240  splice(I, L2, L2.begin(), L2.end());
241  }
242 
243  /// Splice in a node from another list.
244  void splice(iterator I, simple_ilist &L2, iterator Node) {
245  splice(I, L2, Node, std::next(Node));
246  }
247 
248  /// Splice in a range of nodes from another list.
249  void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
250  list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
251  *Last.getNodePtr());
252  }
253 
254  /// Merge in another list.
255  ///
256  /// \pre \c this and \p RHS are sorted.
257  ///@{
258  void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
259  template <class Compare> void merge(simple_ilist &RHS, Compare comp);
260  ///@}
261 
262  /// Sort the list.
263  ///@{
264  void sort() { sort(std::less<T>()); }
265  template <class Compare> void sort(Compare comp);
266  ///@}
267 };
268 
269 template <class T, class... Options>
270 template <class Compare>
272  if (this == &RHS || RHS.empty())
273  return;
274  iterator LI = begin(), LE = end();
275  iterator RI = RHS.begin(), RE = RHS.end();
276  while (LI != LE) {
277  if (comp(*RI, *LI)) {
278  // Transfer a run of at least size 1 from RHS to LHS.
279  iterator RunStart = RI++;
280  RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
281  splice(LI, RHS, RunStart, RI);
282  if (RI == RE)
283  return;
284  }
285  ++LI;
286  }
287  // Transfer the remaining RHS nodes once LHS is finished.
288  splice(LE, RHS, RI, RE);
289 }
290 
291 template <class T, class... Options>
292 template <class Compare>
294  // Vacuously sorted.
295  if (empty() || std::next(begin()) == end())
296  return;
297 
298  // Split the list in the middle.
299  iterator Center = begin(), End = begin();
300  while (End != end() && ++End != end()) {
301  ++Center;
302  ++End;
303  }
304  simple_ilist RHS;
305  RHS.splice(RHS.end(), *this, Center, end());
306 
307  // Sort the sublists and merge back together.
308  sort(comp);
309  RHS.sort(comp);
310  merge(RHS, comp);
311 }
312 
313 } // end namespace llvm
314 
315 #endif // LLVM_ADT_SIMPLE_ILIST_H
void sort()
Sort the list.
Definition: simple_ilist.h:264
ilist_iterator< OptionsT, false, false > iterator
Definition: simple_ilist.h:96
void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose)
Clone another list.
Definition: simple_ilist.h:174
iterator erase(iterator I)
Remove a node by iterator; never deletes.
Definition: simple_ilist.h:197
void pop_front()
Remove the node at the front; never deletes.
Definition: simple_ilist.h:151
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
typename OptionsT::const_reference const_reference
Definition: simple_ilist.h:95
ilist_iterator< OptionsT, false, true > const_iterator
Definition: simple_ilist.h:97
void swap(simple_ilist &X)
Swap with another list in place using std::swap.
Definition: simple_ilist.h:157
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
void push_back(reference Node)
Insert a node at the back; never copies.
Definition: simple_ilist.h:148
void merge(simple_ilist &RHS)
Merge in another list.
Definition: simple_ilist.h:258
void pop_back()
Remove the node at the back; never deletes.
Definition: simple_ilist.h:154
iterator erase(iterator First, iterator Last)
Remove a range of nodes; never deletes.
Definition: simple_ilist.h:206
reference back()
Definition: simple_ilist.h:141
ilist_iterator< OptionsT, true, true > const_reverse_iterator
Definition: simple_ilist.h:99
simple_ilist & operator=(const simple_ilist &)=delete
ilist_iterator< OptionsT, true, false > reverse_iterator
Definition: simple_ilist.h:98
void removeAndDispose(reference N, Disposer dispose)
Remove a node by reference and dispose of it.
Definition: simple_ilist.h:188
void splice(iterator I, simple_ilist &L2)
Splice in another list.
Definition: simple_ilist.h:239
A simple intrusive list implementation.
Definition: simple_ilist.h:79
const_reverse_iterator rend() const
Definition: simple_ilist.h:127
#define T
node_pointer getNodePtr() const
Get the underlying ilist_node.
void clear()
Clear the list; never deletes.
Definition: simple_ilist.h:231
void insert(iterator I, Iterator First, Iterator Last)
Insert a range of nodes; never copies.
Definition: simple_ilist.h:167
const_iterator end() const
Definition: simple_ilist.h:121
iterator eraseAndDispose(iterator I, Disposer dispose)
Remove a node by iterator and dispose of it.
Definition: simple_ilist.h:213
simple_ilist(simple_ilist &&X)
Definition: simple_ilist.h:111
reverse_iterator rend()
Definition: simple_ilist.h:126
LLVM_NODISCARD size_type size() const
Calculate the size of the list in linear time.
Definition: simple_ilist.h:135
typename ilist_detail::compute_node_options< MachineInstr, Options... >::type ::pointer pointer
Definition: ilist_node.h:213
typename ilist_detail::compute_node_options< MachineInstr, Options... >::type ::const_pointer const_pointer
Definition: ilist_node.h:214
static const unsigned End
bool empty() const
Definition: ilist_node.h:249
const_reference back() const
Definition: simple_ilist.h:142
Iterator for intrusive lists based on ilist_node.
~simple_ilist()=default
void splice(iterator I, simple_ilist &L2, iterator Node)
Splice in a node from another list.
Definition: simple_ilist.h:244
Check whether options are valid.
const_iterator begin() const
Definition: simple_ilist.h:119
const_reference front() const
Definition: simple_ilist.h:140
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
LLVM_NODISCARD bool empty() const
Check if the list is empty in constant time.
Definition: simple_ilist.h:132
void clearAndDispose(Disposer dispose)
Clear the list and dispose of the nodes.
Definition: simple_ilist.h:234
typename OptionsT::value_type value_type
Definition: simple_ilist.h:91
simple_ilist & operator=(simple_ilist &&X)
Definition: simple_ilist.h:112
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
reference front()
Definition: simple_ilist.h:139
simple_ilist()=default
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:160
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:126
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose)
Remove a range of nodes and dispose of them.
Definition: simple_ilist.h:222
void splice(iterator I, simple_ilist &, iterator First, iterator Last)
Splice in a range of nodes from another list.
Definition: simple_ilist.h:249
const_reverse_iterator rbegin() const
Definition: simple_ilist.h:123
auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:795
typename OptionsT::reference reference
Definition: simple_ilist.h:93
reverse_iterator rbegin()
Definition: simple_ilist.h:122
void push_front(reference Node)
Insert a node at the front; never copies.
Definition: simple_ilist.h:145