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