llvm/ADT/ilist_node.h

0001 //===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the ilist_node class template, which is a convenient
0011 /// base class for creating classes that can be used with ilists.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_ADT_ILIST_NODE_H
0016 #define LLVM_ADT_ILIST_NODE_H
0017
0018 #include "llvm/ADT/ilist_node_base.h"
0019 #include "llvm/ADT/ilist_node_options.h"
0020
0021 namespace llvm {
0022
0023 namespace ilist_detail {
0024
0025 struct NodeAccess;
0026
0027 /// Mixin base class that is used to add \a getParent() and
0028 /// \a setParent(ParentTy*) methods to \a ilist_node_impl iff \a ilist_parent
0029 /// has been set in the list options.
0030 template <class NodeTy, class ParentTy> class node_parent_access {
0031 public:
0032   inline const ParentTy *getParent() const {
0033     return static_cast<const NodeTy *>(this)->getNodeBaseParent();
0034   }
0035   inline ParentTy *getParent() {
0036     return static_cast<NodeTy *>(this)->getNodeBaseParent();
0037   }
0038   void setParent(ParentTy *Parent) {
0039     return static_cast<NodeTy *>(this)->setNodeBaseParent(Parent);
0040   }
0041 };
0042 template <class NodeTy> class node_parent_access<NodeTy, void> {};
0043
0044 } // end namespace ilist_detail
0045
0046 template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
0047 template <class OptionsT, bool IsReverse, bool IsConst>
0048 class ilist_iterator_w_bits;
0049 template <class OptionsT> class ilist_sentinel;
0050
0051 // Selector for which iterator type to pick given the iterator-bits node option.
0052 template <bool use_iterator_bits, typename Opts, bool arg1, bool arg2>
0053 class ilist_select_iterator_type {
0054 public:
0055   using type = ilist_iterator<Opts, arg1, arg2>;
0056 };
0057 template <typename Opts, bool arg1, bool arg2>
0058 class ilist_select_iterator_type<true, Opts, arg1, arg2> {
0059 public:
0060   using type = ilist_iterator_w_bits<Opts, arg1, arg2>;
0061 };
0062
0063 /// Implementation for an ilist node.
0064 ///
0065 /// Templated on an appropriate \a ilist_detail::node_options, usually computed
0066 /// by \a ilist_detail::compute_node_options.
0067 ///
0068 /// This is a wrapper around \a ilist_node_base whose main purpose is to
0069 /// provide type safety: you can't insert nodes of \a ilist_node_impl into the
0070 /// wrong \a simple_ilist or \a iplist.
0071 template <class OptionsT>
0072 class ilist_node_impl
0073     : OptionsT::node_base_type,
0074       public ilist_detail::node_parent_access<ilist_node_impl<OptionsT>,
0075                                               typename OptionsT::parent_ty> {
0076   using value_type = typename OptionsT::value_type;
0077   using node_base_type = typename OptionsT::node_base_type;
0078   using list_base_type = typename OptionsT::list_base_type;
0079
0080   friend typename OptionsT::list_base_type;
0081   friend struct ilist_detail::NodeAccess;
0082   friend class ilist_sentinel<OptionsT>;
0083
0084   friend class ilist_detail::node_parent_access<ilist_node_impl<OptionsT>,
0085                                                 typename OptionsT::parent_ty>;
0086   friend class ilist_iterator<OptionsT, false, false>;
0087   friend class ilist_iterator<OptionsT, false, true>;
0088   friend class ilist_iterator<OptionsT, true, false>;
0089   friend class ilist_iterator<OptionsT, true, true>;
0090   friend class ilist_iterator_w_bits<OptionsT, false, false>;
0091   friend class ilist_iterator_w_bits<OptionsT, false, true>;
0092   friend class ilist_iterator_w_bits<OptionsT, true, false>;
0093   friend class ilist_iterator_w_bits<OptionsT, true, true>;
0094
0095 protected:
0096   using self_iterator =
0097       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0098                                           false, false>::type;
0099   using const_self_iterator =
0100       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0101                                           false, true>::type;
0102   using reverse_self_iterator =
0103       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0104                                           true, false>::type;
0105   using const_reverse_self_iterator =
0106       typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
0107                                           true, true>::type;
0108
0109   ilist_node_impl() = default;
0110
0111 private:
0112   ilist_node_impl *getPrev() {
0113     return static_cast<ilist_node_impl *>(node_base_type::getPrev());
0114   }
0115
0116   ilist_node_impl *getNext() {
0117     return static_cast<ilist_node_impl *>(node_base_type::getNext());
0118   }
0119
0120   const ilist_node_impl *getPrev() const {
0121     return static_cast<ilist_node_impl *>(node_base_type::getPrev());
0122   }
0123
0124   const ilist_node_impl *getNext() const {
0125     return static_cast<ilist_node_impl *>(node_base_type::getNext());
0126   }
0127
0128   void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
0129   void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }
0130
0131 public:
0132   self_iterator getIterator() { return self_iterator(*this); }
0133   const_self_iterator getIterator() const { return const_self_iterator(*this); }
0134
0135   reverse_self_iterator getReverseIterator() {
0136     return reverse_self_iterator(*this);
0137   }
0138
0139   const_reverse_self_iterator getReverseIterator() const {
0140     return const_reverse_self_iterator(*this);
0141   }
0142
0143   // Under-approximation, but always available for assertions.
0144   using node_base_type::isKnownSentinel;
0145
0146   /// Check whether this is the sentinel node.
0147   ///
0148   /// This requires sentinel tracking to be explicitly enabled.  Use the
0149   /// ilist_sentinel_tracking<true> option to get this API.
0150   bool isSentinel() const {
0151     static_assert(OptionsT::is_sentinel_tracking_explicit,
0152                   "Use ilist_sentinel_tracking<true> to enable isSentinel()");
0153     return node_base_type::isSentinel();
0154   }
0155 };
0156
0157 /// An intrusive list node.
0158 ///
0159 /// A base class to enable membership in intrusive lists, including \a
0160 /// simple_ilist, \a iplist, and \a ilist.  The first template parameter is the
0161 /// \a value_type for the list.
0162 ///
0163 /// An ilist node can be configured with compile-time options to change
0164 /// behaviour and/or add API.
0165 ///
0166 /// By default, an \a ilist_node knows whether it is the list sentinel (an
0167 /// instance of \a ilist_sentinel) if and only if
0168 /// LLVM_ENABLE_ABI_BREAKING_CHECKS.  The function \a isKnownSentinel() always
0169 /// returns \c false tracking is off.  Sentinel tracking steals a bit from the
0170 /// "prev" link, which adds a mask operation when decrementing an iterator, but
0171 /// enables bug-finding assertions in \a ilist_iterator.
0172 ///
0173 /// To turn sentinel tracking on all the time, pass in the
0174 /// ilist_sentinel_tracking<true> template parameter.  This also enables the \a
0175 /// isSentinel() function.  The same option must be passed to the intrusive
0176 /// list.  (ilist_sentinel_tracking<false> turns sentinel tracking off all the
0177 /// time.)
0178 ///
0179 /// A type can inherit from ilist_node multiple times by passing in different
0180 /// \a ilist_tag options.  This allows a single instance to be inserted into
0181 /// multiple lists simultaneously, where each list is given the same tag.
0182 ///
0183 /// \example
0184 /// struct A {};
0185 /// struct B {};
0186 /// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};
0187 ///
0188 /// void foo() {
0189 ///   simple_ilist<N, ilist_tag<A>> ListA;
0190 ///   simple_ilist<N, ilist_tag<B>> ListB;
0191 ///   N N1;
0192 ///   ListA.push_back(N1);
0193 ///   ListB.push_back(N1);
0194 /// }
0195 /// \endexample
0196 ///
0197 /// When the \a ilist_parent<ParentTy> option is passed to an ilist_node and the
0198 /// owning ilist, each node contains a pointer to the ilist's owner. This adds
0199 /// \a getParent() and \a setParent(ParentTy*) methods to the ilist_node, which
0200 /// will be used for node access by the ilist if the node class publicly
0201 /// inherits from \a ilist_node_with_parent. By default, setParent() is not
0202 /// automatically called by the ilist; a SymbolTableList will call setParent()
0203 /// on inserted nodes, but the sentinel must still be manually set after the
0204 /// list is created (e.g. SymTabList.end()->setParent(Parent)).
0205 ///
0206 /// The primary benefit of using ilist_parent is that a parent
0207 /// pointer will be stored in the sentinel, meaning that you can safely use \a
0208 /// ilist_iterator::getNodeParent() to get the node parent from any valid (i.e.
0209 /// non-null) iterator, even one that points to a sentinel value.
0210 ///
0211 /// See \a is_valid_option for steps on adding a new option.
0212 template <class T, class... Options>
0213 class ilist_node
0214     : public ilist_node_impl<
0215           typename ilist_detail::compute_node_options<T, Options...>::type> {
0216   static_assert(ilist_detail::check_options<Options...>::value,
0217                 "Unrecognized node option!");
0218 };
0219
0220 namespace ilist_detail {
0221
0222 /// An access class for ilist_node private API.
0223 ///
0224 /// This gives access to the private parts of ilist nodes.  Nodes for an ilist
0225 /// should friend this class if they inherit privately from ilist_node.
0226 ///
0227 /// Using this class outside of the ilist implementation is unsupported.
0228 struct NodeAccess {
0229 protected:
0230   template <class OptionsT>
0231   static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
0232     return N;
0233   }
0234
0235   template <class OptionsT>
0236   static const ilist_node_impl<OptionsT> *
0237   getNodePtr(typename OptionsT::const_pointer N) {
0238     return N;
0239   }
0240
0241   template <class OptionsT>
0242   static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
0243     return static_cast<typename OptionsT::pointer>(N);
0244   }
0245
0246   template <class OptionsT>
0247   static typename OptionsT::const_pointer
0248   getValuePtr(const ilist_node_impl<OptionsT> *N) {
0249     return static_cast<typename OptionsT::const_pointer>(N);
0250   }
0251
0252   template <class OptionsT>
0253   static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
0254     return N.getPrev();
0255   }
0256
0257   template <class OptionsT>
0258   static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
0259     return N.getNext();
0260   }
0261
0262   template <class OptionsT>
0263   static const ilist_node_impl<OptionsT> *
0264   getPrev(const ilist_node_impl<OptionsT> &N) {
0265     return N.getPrev();
0266   }
0267
0268   template <class OptionsT>
0269   static const ilist_node_impl<OptionsT> *
0270   getNext(const ilist_node_impl<OptionsT> &N) {
0271     return N.getNext();
0272   }
0273 };
0274
0275 template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
0276 protected:
0277   using pointer = typename OptionsT::pointer;
0278   using const_pointer = typename OptionsT::const_pointer;
0279   using node_type = ilist_node_impl<OptionsT>;
0280
0281   static node_type *getNodePtr(pointer N) {
0282     return NodeAccess::getNodePtr<OptionsT>(N);
0283   }
0284
0285   static const node_type *getNodePtr(const_pointer N) {
0286     return NodeAccess::getNodePtr<OptionsT>(N);
0287   }
0288
0289   static pointer getValuePtr(node_type *N) {
0290     return NodeAccess::getValuePtr<OptionsT>(N);
0291   }
0292
0293   static const_pointer getValuePtr(const node_type *N) {
0294     return NodeAccess::getValuePtr<OptionsT>(N);
0295   }
0296 };
0297
0298 } // end namespace ilist_detail
0299
0300 template <class OptionsT>
0301 class ilist_sentinel : public ilist_node_impl<OptionsT> {
0302 public:
0303   ilist_sentinel() {
0304     this->initializeSentinel();
0305     reset();
0306   }
0307
0308   void reset() {
0309     this->setPrev(this);
0310     this->setNext(this);
0311   }
0312
0313   bool empty() const { return this == this->getPrev(); }
0314 };
0315
0316 /// An ilist node that can access its parent list.
0317 ///
0318 /// Requires \c NodeTy to have \a getParent() to find the parent node, and the
0319 /// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
0320 template <typename NodeTy, typename ParentTy, class... Options>
0321 class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
0322 protected:
0323   ilist_node_with_parent() = default;
0324
0325 private:
0326   /// Forward to NodeTy::getParent().
0327   ///
0328   /// Note: do not use the name "getParent()".  We want a compile error
0329   /// (instead of recursion) when the subclass fails to implement \a
0330   /// getParent().
0331   const ParentTy *getNodeParent() const {
0332     return static_cast<const NodeTy *>(this)->getParent();
0333   }
0334
0335 public:
0336   /// @name Adjacent Node Accessors
0337   /// @{
0338   /// Get the previous node, or \c nullptr for the list head.
0339   NodeTy *getPrevNode() {
0340     // Should be separated to a reused function, but then we couldn't use auto
0341     // (and would need the type of the list).
0342     const auto &List =
0343         getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
0344     return List.getPrevNode(*static_cast<NodeTy *>(this));
0345   }
0346
0347   /// Get the previous node, or \c nullptr for the list head.
0348   const NodeTy *getPrevNode() const {
0349     return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
0350   }
0351
0352   /// Get the next node, or \c nullptr for the list tail.
0353   NodeTy *getNextNode() {
0354     // Should be separated to a reused function, but then we couldn't use auto
0355     // (and would need the type of the list).
0356     const auto &List =
0357         getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
0358     return List.getNextNode(*static_cast<NodeTy *>(this));
0359   }
0360
0361   /// Get the next node, or \c nullptr for the list tail.
0362   const NodeTy *getNextNode() const {
0363     return const_cast<ilist_node_with_parent *>(this)->getNextNode();
0364   }
0365   /// @}
0366 };
0367
0368 } // end namespace llvm
0369
0370 #endif // LLVM_ADT_ILIST_NODE_H