LCOV - code coverage report
Current view: top level - include/llvm/ADT - ilist_node.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 39 39 100.0 %
Date: 2017-09-14 15:23:50 Functions: 0 0 -
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13