contrib/llvm/include/llvm/ADT/ilist_node.h

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