LLVM  6.0.0svn
ilist_node.h
Go to the documentation of this file.
1 //===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- 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 the ilist_node class template, which is a convenient
11 // base class for creating classes that can be used with ilists.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ADT_ILIST_NODE_H
16 #define LLVM_ADT_ILIST_NODE_H
17 
20 
21 namespace llvm {
22 
23 namespace ilist_detail {
24 
25 struct NodeAccess;
26 
27 } // end namespace ilist_detail
28 
29 template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
30 template <class OptionsT> class ilist_sentinel;
31 
32 /// Implementation for an ilist node.
33 ///
34 /// Templated on an appropriate \a ilist_detail::node_options, usually computed
35 /// by \a ilist_detail::compute_node_options.
36 ///
37 /// This is a wrapper around \a ilist_node_base whose main purpose is to
38 /// provide type safety: you can't insert nodes of \a ilist_node_impl into the
39 /// wrong \a simple_ilist or \a iplist.
40 template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
41  using value_type = typename OptionsT::value_type;
42  using node_base_type = typename OptionsT::node_base_type;
43  using list_base_type = typename OptionsT::list_base_type;
44 
45  friend typename OptionsT::list_base_type;
46  friend struct ilist_detail::NodeAccess;
47  friend class ilist_sentinel<OptionsT>;
48  friend class ilist_iterator<OptionsT, false, false>;
49  friend class ilist_iterator<OptionsT, false, true>;
50  friend class ilist_iterator<OptionsT, true, false>;
51  friend class ilist_iterator<OptionsT, true, true>;
52 
53 protected:
58 
59  ilist_node_impl() = default;
60 
61 private:
62  ilist_node_impl *getPrev() {
63  return static_cast<ilist_node_impl *>(node_base_type::getPrev());
64  }
65 
66  ilist_node_impl *getNext() {
67  return static_cast<ilist_node_impl *>(node_base_type::getNext());
68  }
69 
70  const ilist_node_impl *getPrev() const {
71  return static_cast<ilist_node_impl *>(node_base_type::getPrev());
72  }
73 
74  const ilist_node_impl *getNext() const {
75  return static_cast<ilist_node_impl *>(node_base_type::getNext());
76  }
77 
78  void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
79  void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }
80 
81 public:
84 
86  return reverse_self_iterator(*this);
87  }
88 
90  return const_reverse_self_iterator(*this);
91  }
92 
93  // Under-approximation, but always available for assertions.
94  using node_base_type::isKnownSentinel;
95 
96  /// Check whether this is the sentinel node.
97  ///
98  /// This requires sentinel tracking to be explicitly enabled. Use the
99  /// ilist_sentinel_tracking<true> option to get this API.
100  bool isSentinel() const {
101  static_assert(OptionsT::is_sentinel_tracking_explicit,
102  "Use ilist_sentinel_tracking<true> to enable isSentinel()");
103  return node_base_type::isSentinel();
104  }
105 };
106 
107 /// An intrusive list node.
108 ///
109 /// A base class to enable membership in intrusive lists, including \a
110 /// simple_ilist, \a iplist, and \a ilist. The first template parameter is the
111 /// \a value_type for the list.
112 ///
113 /// An ilist node can be configured with compile-time options to change
114 /// behaviour and/or add API.
115 ///
116 /// By default, an \a ilist_node knows whether it is the list sentinel (an
117 /// instance of \a ilist_sentinel) if and only if
118 /// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always
119 /// returns \c false tracking is off. Sentinel tracking steals a bit from the
120 /// "prev" link, which adds a mask operation when decrementing an iterator, but
121 /// enables bug-finding assertions in \a ilist_iterator.
122 ///
123 /// To turn sentinel tracking on all the time, pass in the
124 /// ilist_sentinel_tracking<true> template parameter. This also enables the \a
125 /// isSentinel() function. The same option must be passed to the intrusive
126 /// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the
127 /// time.)
128 ///
129 /// A type can inherit from ilist_node multiple times by passing in different
130 /// \a ilist_tag options. This allows a single instance to be inserted into
131 /// multiple lists simultaneously, where each list is given the same tag.
132 ///
133 /// \example
134 /// struct A {};
135 /// struct B {};
136 /// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};
137 ///
138 /// void foo() {
139 /// simple_ilist<N, ilist_tag<A>> ListA;
140 /// simple_ilist<N, ilist_tag<B>> ListB;
141 /// N N1;
142 /// ListA.push_back(N1);
143 /// ListB.push_back(N1);
144 /// }
145 /// \endexample
146 ///
147 /// See \a is_valid_option for steps on adding a new option.
148 template <class T, class... Options>
150  : public ilist_node_impl<
151  typename ilist_detail::compute_node_options<T, Options...>::type> {
153  "Unrecognized node option!");
154 };
155 
156 namespace ilist_detail {
157 
158 /// An access class for ilist_node private API.
159 ///
160 /// This gives access to the private parts of ilist nodes. Nodes for an ilist
161 /// should friend this class if they inherit privately from ilist_node.
162 ///
163 /// Using this class outside of the ilist implementation is unsupported.
164 struct NodeAccess {
165 protected:
166  template <class OptionsT>
167  static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
168  return N;
169  }
170 
171  template <class OptionsT>
172  static const ilist_node_impl<OptionsT> *
173  getNodePtr(typename OptionsT::const_pointer N) {
174  return N;
175  }
176 
177  template <class OptionsT>
178  static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
179  return static_cast<typename OptionsT::pointer>(N);
180  }
181 
182  template <class OptionsT>
183  static typename OptionsT::const_pointer
185  return static_cast<typename OptionsT::const_pointer>(N);
186  }
187 
188  template <class OptionsT>
190  return N.getPrev();
191  }
192 
193  template <class OptionsT>
195  return N.getNext();
196  }
197 
198  template <class OptionsT>
199  static const ilist_node_impl<OptionsT> *
201  return N.getPrev();
202  }
203 
204  template <class OptionsT>
205  static const ilist_node_impl<OptionsT> *
207  return N.getNext();
208  }
209 };
210 
211 template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
212 protected:
213  using pointer = typename OptionsT::pointer;
214  using const_pointer = typename OptionsT::const_pointer;
216 
218  return NodeAccess::getNodePtr<OptionsT>(N);
219  }
220 
222  return NodeAccess::getNodePtr<OptionsT>(N);
223  }
224 
226  return NodeAccess::getValuePtr<OptionsT>(N);
227  }
228 
230  return NodeAccess::getValuePtr<OptionsT>(N);
231  }
232 };
233 
234 } // end namespace ilist_detail
235 
236 template <class OptionsT>
237 class ilist_sentinel : public ilist_node_impl<OptionsT> {
238 public:
240  this->initializeSentinel();
241  reset();
242  }
243 
244  void reset() {
245  this->setPrev(this);
246  this->setNext(this);
247  }
248 
249  bool empty() const { return this == this->getPrev(); }
250 };
251 
252 /// An ilist node that can access its parent list.
253 ///
254 /// Requires \c NodeTy to have \a getParent() to find the parent node, and the
255 /// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
256 template <typename NodeTy, typename ParentTy, class... Options>
257 class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
258 protected:
259  ilist_node_with_parent() = default;
260 
261 private:
262  /// Forward to NodeTy::getParent().
263  ///
264  /// Note: do not use the name "getParent()". We want a compile error
265  /// (instead of recursion) when the subclass fails to implement \a
266  /// getParent().
267  const ParentTy *getNodeParent() const {
268  return static_cast<const NodeTy *>(this)->getParent();
269  }
270 
271 public:
272  /// @name Adjacent Node Accessors
273  /// @{
274  /// \brief Get the previous node, or \c nullptr for the list head.
275  NodeTy *getPrevNode() {
276  // Should be separated to a reused function, but then we couldn't use auto
277  // (and would need the type of the list).
278  const auto &List =
279  getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
280  return List.getPrevNode(*static_cast<NodeTy *>(this));
281  }
282 
283  /// \brief Get the previous node, or \c nullptr for the list head.
284  const NodeTy *getPrevNode() const {
285  return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
286  }
287 
288  /// \brief Get the next node, or \c nullptr for the list tail.
289  NodeTy *getNextNode() {
290  // Should be separated to a reused function, but then we couldn't use auto
291  // (and would need the type of the list).
292  const auto &List =
293  getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
294  return List.getNextNode(*static_cast<NodeTy *>(this));
295  }
296 
297  /// \brief Get the next node, or \c nullptr for the list tail.
298  const NodeTy *getNextNode() const {
299  return const_cast<ilist_node_with_parent *>(this)->getNextNode();
300  }
301  /// @}
302 };
303 
304 } // end namespace llvm
305 
306 #endif // LLVM_ADT_ILIST_NODE_H
static const ilist_node_impl< OptionsT > * getNext(const ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:206
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const_reverse_self_iterator getReverseIterator() const
Definition: ilist_node.h:89
static const ilist_node_impl< OptionsT > * getNodePtr(typename OptionsT::const_pointer N)
Definition: ilist_node.h:173
static node_type * getNodePtr(pointer N)
Definition: ilist_node.h:217
static const node_type * getNodePtr(const_pointer N)
Definition: ilist_node.h:221
static pointer getValuePtr(node_type *N)
Definition: ilist_node.h:225
Implementation for an ilist node.
Definition: ilist_node.h:40
static const_pointer getValuePtr(const node_type *N)
Definition: ilist_node.h:229
#define T
static ilist_node_impl< OptionsT > * getNodePtr(typename OptionsT::pointer N)
Definition: ilist_node.h:167
static ilist_node_impl< OptionsT > * getPrev(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:189
An ilist node that can access its parent list.
Definition: ilist_node.h:257
typename ilist_detail::compute_node_options< Instruction, Options... >::type ::pointer pointer
Definition: ilist_node.h:213
typename ilist_detail::compute_node_options< Instruction, Options... >::type ::const_pointer const_pointer
Definition: ilist_node.h:214
self_iterator getIterator()
Definition: ilist_node.h:82
const NodeTy * getPrevNode() const
Get the previous node, or nullptr for the list head.
Definition: ilist_node.h:284
static const ilist_node_impl< OptionsT > * getPrev(const ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:200
bool empty() const
Definition: ilist_node.h:249
An access class for ilist_node private API.
Definition: ilist_node.h:164
static OptionsT::pointer getValuePtr(ilist_node_impl< OptionsT > *N)
Definition: ilist_node.h:178
Iterator for intrusive lists based on ilist_node.
Check whether options are valid.
const_self_iterator getIterator() const
Definition: ilist_node.h:83
static OptionsT::const_pointer getValuePtr(const ilist_node_impl< OptionsT > *N)
Definition: ilist_node.h:184
const NodeTy * getNextNode() const
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:298
Basic Alias true
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
const NodeList & List
Definition: RDFGraph.cpp:210
#define N
bool isSentinel() const
Check whether this is the sentinel node.
Definition: ilist_node.h:100
static const Function * getParent(const Value *V)
static ilist_node_impl< OptionsT > * getNext(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:194