include/llvm/ADT/ilist_node.h

   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
  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:
  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
  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:
  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.
 147 template <class T, class... Options>
 148 class 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
 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
 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
 210 template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
 211 protected:
 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
 235 template <class OptionsT>
 236 class ilist_sentinel : public ilist_node_impl<OptionsT> {
 237 public:
 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.
 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