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
17#include "llvm/ADT/ilist_node_base.h"
18#include "llvm/ADT/ilist_node_options.h"
19
20namespace llvm {
21
22namespace ilist_detail {
23
24struct NodeAccess;
25
26} // end namespace ilist_detail
27
28template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
29template <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.
39template <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
52protected:
53  using self_iterator = ilist_iterator<OptionsT, false, false>;
54  using const_self_iterator = ilist_iterator<OptionsT, false, true>;
55  using reverse_self_iterator = ilist_iterator<OptionsT, true, false>;
56  using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>;
57
58  ilist_node_impl() = default;
59
60private:
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
80public:
81  self_iterator getIterator() { return self_iterator(*this); }
82  const_self_iterator getIterator() const { return const_self_iterator(*this); }
83
84  reverse_self_iterator getReverseIterator() {
85    return reverse_self_iterator(*this);
86  }
87
88  const_reverse_self_iterator getReverseIterator() const {
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()");
102    return node_base_type::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.
147template <class T, class... Options>
148class ilist_node
149    : public ilist_node_impl<
150          typename ilist_detail::compute_node_options<T, Options...>::type> {
151  static_assert(ilist_detail::check_options<Options...>::value,
152                "Unrecognized node option!");
153};
154
155namespace 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.
163struct NodeAccess {
164protected:
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
183  getValuePtr(const ilist_node_impl<OptionsT> *N) {
184    return static_cast<typename OptionsT::const_pointer>(N);
185  }
186
187  template <class OptionsT>
188  static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
189    return N.getPrev();
190  }
191
192  template <class OptionsT>
193  static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
194    return N.getNext();
195  }
196
197  template <class OptionsT>
198  static const ilist_node_impl<OptionsT> *
199  getPrev(const ilist_node_impl<OptionsT> &N) {
200    return N.getPrev();
201  }
202
203  template <class OptionsT>
204  static const ilist_node_impl<OptionsT> *
205  getNext(const ilist_node_impl<OptionsT> &N) {
206    return N.getNext();
207  }
208};
209
210template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
211protected:
212  using pointer = typename OptionsT::pointer;
213  using const_pointer = typename OptionsT::const_pointer;
214  using node_type = ilist_node_impl<OptionsT>;
215
216  static node_type *getNodePtr(pointer N) {
217    return NodeAccess::getNodePtr<OptionsT>(N);
218  }
219
220  static const node_type *getNodePtr(const_pointer N) {
221    return NodeAccess::getNodePtr<OptionsT>(N);
222  }
223
224  static pointer getValuePtr(node_type *N) {
225    return NodeAccess::getValuePtr<OptionsT>(N);
226  }
227
228  static const_pointer getValuePtr(const node_type *N) {
229    return NodeAccess::getValuePtr<OptionsT>(N);
230  }
231};
232
233} // end namespace ilist_detail
234
235template <class OptionsT>
236class ilist_sentinel : public ilist_node_impl<OptionsT> {
237public:
238  ilist_sentinel() {
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.
255template <typename NodeTy, typename ParentTy, class... Options>
256class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
257protected:
258  ilist_node_with_parent() = default;
259
260private:
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
270public:
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
306