LCOV - code coverage report
Current view: top level - include/llvm/ADT - ilist.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 74 77 96.1 %
Date: 2017-09-14 15:23:50 Functions: 61 81 75.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- 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 classes to implement an intrusive doubly linked list class
      11             : // (i.e. each node of the list must contain a next and previous field for the
      12             : // list.
      13             : //
      14             : // The ilist class itself should be a plug in replacement for list.  This list
      15             : // replacement does not provide a constant time size() method, so be careful to
      16             : // use empty() when you really want to know if it's empty.
      17             : //
      18             : // The ilist class is implemented as a circular list.  The list itself contains
      19             : // a sentinel node, whose Next points at begin() and whose Prev points at
      20             : // rbegin().  The sentinel node itself serves as end() and rend().
      21             : //
      22             : //===----------------------------------------------------------------------===//
      23             : 
      24             : #ifndef LLVM_ADT_ILIST_H
      25             : #define LLVM_ADT_ILIST_H
      26             : 
      27             : #include "llvm/ADT/simple_ilist.h"
      28             : #include <cassert>
      29             : #include <cstddef>
      30             : #include <iterator>
      31             : 
      32             : namespace llvm {
      33             : 
      34             : /// Use delete by default for iplist and ilist.
      35             : ///
      36             : /// Specialize this to get different behaviour for ownership-related API.  (If
      37             : /// you really want ownership semantics, consider using std::list or building
      38             : /// something like \a BumpPtrList.)
      39             : ///
      40             : /// \see ilist_noalloc_traits
      41             : template <typename NodeTy> struct ilist_alloc_traits {
      42     3821044 :   static void deleteNode(NodeTy *V) { delete V; }
      43             : };
      44             : 
      45             : /// Custom traits to do nothing on deletion.
      46             : ///
      47             : /// Specialize ilist_alloc_traits to inherit from this to disable the
      48             : /// non-intrusive deletion in iplist (which implies ownership).
      49             : ///
      50             : /// If you want purely intrusive semantics with no callbacks, consider using \a
      51             : /// simple_ilist instead.
      52             : ///
      53             : /// \code
      54             : /// template <>
      55             : /// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
      56             : /// \endcode
      57             : template <typename NodeTy> struct ilist_noalloc_traits {
      58             :   static void deleteNode(NodeTy *V) {}
      59             : };
      60             : 
      61             : /// Callbacks do nothing by default in iplist and ilist.
      62             : ///
      63             : /// Specialize this for to use callbacks for when nodes change their list
      64             : /// membership.
      65             : template <typename NodeTy> struct ilist_callback_traits {
      66             :   void addNodeToList(NodeTy *) {}
      67             :   void removeNodeFromList(NodeTy *) {}
      68             : 
      69             :   /// Callback before transferring nodes to this list.
      70             :   ///
      71             :   /// \pre \c this!=&OldList
      72             :   template <class Iterator>
      73             :   void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
      74             :                              Iterator /*last*/) {
      75             :     (void)OldList;
      76             :   }
      77             : };
      78             : 
      79             : /// A fragment for template traits for intrusive list that provides default
      80             : /// node related operations.
      81             : ///
      82             : /// TODO: Remove this layer of indirection.  It's not necessary.
      83             : template <typename NodeTy>
      84             : struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
      85             :                            ilist_callback_traits<NodeTy> {};
      86             : 
      87             : /// Default template traits for intrusive list.
      88             : ///
      89             : /// By inheriting from this, you can easily use default implementations for all
      90             : /// common operations.
      91             : ///
      92             : /// TODO: Remove this customization point.  Specializing ilist_traits is
      93             : /// already fully general.
      94             : template <typename NodeTy>
      95             : struct ilist_default_traits : public ilist_node_traits<NodeTy> {};
      96             : 
      97             : /// Template traits for intrusive list.
      98             : ///
      99             : /// Customize callbacks and allocation semantics.
     100             : template <typename NodeTy>
     101             : struct ilist_traits : public ilist_default_traits<NodeTy> {};
     102             : 
     103             : /// Const traits should never be instantiated.
     104             : template <typename Ty> struct ilist_traits<const Ty> {};
     105             : 
     106             : namespace ilist_detail {
     107             : 
     108             : template <class T> T &make();
     109             : 
     110             : /// Type trait to check for a traits class that has a getNext member (as a
     111             : /// canary for any of the ilist_nextprev_traits API).
     112             : template <class TraitsT, class NodeT> struct HasGetNext {
     113             :   typedef char Yes[1];
     114             :   typedef char No[2];
     115             :   template <size_t N> struct SFINAE {};
     116             : 
     117             :   template <class U>
     118             :   static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0);
     119             :   template <class> static No &test(...);
     120             : 
     121             : public:
     122             :   static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
     123             : };
     124             : 
     125             : /// Type trait to check for a traits class that has a createSentinel member (as
     126             : /// a canary for any of the ilist_sentinel_traits API).
     127             : template <class TraitsT> struct HasCreateSentinel {
     128             :   typedef char Yes[1];
     129             :   typedef char No[2];
     130             : 
     131             :   template <class U>
     132             :   static Yes &test(U *I, decltype(I->createSentinel()) * = 0);
     133             :   template <class> static No &test(...);
     134             : 
     135             : public:
     136             :   static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
     137             : };
     138             : 
     139             : /// Type trait to check for a traits class that has a createNode member.
     140             : /// Allocation should be managed in a wrapper class, instead of in
     141             : /// ilist_traits.
     142             : template <class TraitsT, class NodeT> struct HasCreateNode {
     143             :   typedef char Yes[1];
     144             :   typedef char No[2];
     145             :   template <size_t N> struct SFINAE {};
     146             : 
     147             :   template <class U>
     148             :   static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0);
     149             :   template <class> static No &test(...);
     150             : 
     151             : public:
     152             :   static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
     153             : };
     154             : 
     155             : template <class TraitsT, class NodeT> struct HasObsoleteCustomization {
     156             :   static const bool value = HasGetNext<TraitsT, NodeT>::value ||
     157             :                             HasCreateSentinel<TraitsT>::value ||
     158             :                             HasCreateNode<TraitsT, NodeT>::value;
     159             : };
     160             : 
     161             : } // end namespace ilist_detail
     162             : 
     163             : //===----------------------------------------------------------------------===//
     164             : //
     165             : /// A wrapper around an intrusive list with callbacks and non-intrusive
     166             : /// ownership.
     167             : ///
     168             : /// This wraps a purely intrusive list (like simple_ilist) with a configurable
     169             : /// traits class.  The traits can implement callbacks and customize the
     170             : /// ownership semantics.
     171             : ///
     172             : /// This is a subset of ilist functionality that can safely be used on nodes of
     173             : /// polymorphic types, i.e. a heterogeneous list with a common base class that
     174             : /// holds the next/prev pointers.  The only state of the list itself is an
     175             : /// ilist_sentinel, which holds pointers to the first and last nodes in the
     176             : /// list.
     177             : template <class IntrusiveListT, class TraitsT>
     178             : class iplist_impl : public TraitsT, IntrusiveListT {
     179             :   typedef IntrusiveListT base_list_type;
     180             : 
     181             : protected:
     182             :   typedef iplist_impl iplist_impl_type;
     183             : 
     184             : public:
     185             :   typedef typename base_list_type::pointer pointer;
     186             :   typedef typename base_list_type::const_pointer const_pointer;
     187             :   typedef typename base_list_type::reference reference;
     188             :   typedef typename base_list_type::const_reference const_reference;
     189             :   typedef typename base_list_type::value_type value_type;
     190             :   typedef typename base_list_type::size_type size_type;
     191             :   typedef typename base_list_type::difference_type difference_type;
     192             :   typedef typename base_list_type::iterator iterator;
     193             :   typedef typename base_list_type::const_iterator const_iterator;
     194             :   typedef typename base_list_type::reverse_iterator reverse_iterator;
     195             :   typedef
     196             :       typename base_list_type::const_reverse_iterator const_reverse_iterator;
     197             : 
     198             : private:
     199             :   // TODO: Drop this assertion and the transitive type traits anytime after
     200             :   // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code
     201             :   // update).
     202             :   static_assert(
     203             :       !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value,
     204             :       "ilist customization points have changed!");
     205             : 
     206             :   static bool op_less(const_reference L, const_reference R) { return L < R; }
     207             :   static bool op_equal(const_reference L, const_reference R) { return L == R; }
     208             : 
     209             : public:
     210     7366462 :   iplist_impl() = default;
     211             : 
     212             :   iplist_impl(const iplist_impl &) = delete;
     213             :   iplist_impl &operator=(const iplist_impl &) = delete;
     214             : 
     215          24 :   iplist_impl(iplist_impl &&X)
     216          48 :       : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {}
     217             :   iplist_impl &operator=(iplist_impl &&X) {
     218             :     *static_cast<TraitsT *>(this) = std::move(X);
     219             :     *static_cast<IntrusiveListT *>(this) = std::move(X);
     220             :     return *this;
     221             :   }
     222             : 
     223     3539102 :   ~iplist_impl() { clear(); }
     224             : 
     225             :   // Miscellaneous inspection routines.
     226             :   size_type max_size() const { return size_type(-1); }
     227             : 
     228             :   using base_list_type::begin;
     229             :   using base_list_type::end;
     230             :   using base_list_type::rbegin;
     231             :   using base_list_type::rend;
     232             :   using base_list_type::empty;
     233             :   using base_list_type::front;
     234             :   using base_list_type::back;
     235             : 
     236             :   void swap(iplist_impl &RHS) {
     237             :     assert(0 && "Swap does not use list traits callback correctly yet!");
     238             :     base_list_type::swap(RHS);
     239             :   }
     240             : 
     241     6456438 :   iterator insert(iterator where, pointer New) {
     242    54143274 :     this->addNodeToList(New); // Notify traits that we added a node...
     243   108286548 :     return base_list_type::insert(where, *New);
     244             :   }
     245             : 
     246             :   iterator insert(iterator where, const_reference New) {
     247             :     return this->insert(where, new value_type(New));
     248             :   }
     249             : 
     250      105115 :   iterator insertAfter(iterator where, pointer New) {
     251      210230 :     if (empty())
     252           0 :       return insert(begin(), New);
     253             :     else
     254      105115 :       return insert(++where, New);
     255             :   }
     256             : 
     257             :   /// Clone another list.
     258           2 :   template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
     259           2 :     clear();
     260          10 :     for (const_reference V : L2)
     261          12 :       push_back(clone(V));
     262           2 :   }
     263             : 
     264    10756643 :   pointer remove(iterator &IT) {
     265   148490655 :     pointer Node = &*IT++;
     266    49496885 :     this->removeNodeFromList(Node); // Notify traits that we removed a node...
     267    98993774 :     base_list_type::remove(*Node);
     268    10756645 :     return Node;
     269             :   }
     270             : 
     271             :   pointer remove(const iterator &IT) {
     272    23266049 :     iterator MutIt = IT;
     273    45496710 :     return remove(MutIt);
     274             :   }
     275             : 
     276    44934364 :   pointer remove(pointer IT) { return remove(iterator(IT)); }
     277             :   pointer remove(reference IT) { return remove(iterator(IT)); }
     278             : 
     279             :   // erase - remove a node from the controlled sequence... and delete it.
     280     6097029 :   iterator erase(iterator where) {
     281    43601172 :     this->deleteNode(remove(where));
     282    11382010 :     return where;
     283             :   }
     284             : 
     285      433357 :   iterator erase(pointer IT) { return erase(iterator(IT)); }
     286             :   iterator erase(reference IT) { return erase(iterator(IT)); }
     287             : 
     288             :   /// Remove all nodes from the list like clear(), but do not call
     289             :   /// removeNodeFromList() or deleteNode().
     290             :   ///
     291             :   /// This should only be used immediately before freeing nodes in bulk to
     292             :   /// avoid traversing the list and bringing all the nodes into cache.
     293      653494 :   void clearAndLeakNodesUnsafely() { base_list_type::clear(); }
     294             : 
     295             : private:
     296             :   // transfer - The heart of the splice function.  Move linked list nodes from
     297             :   // [first, last) into position.
     298             :   //
     299     1550198 :   void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
     300     1665657 :     if (position == last)
     301             :       return;
     302             : 
     303     1612821 :     if (this != &L2) // Notify traits we moved the nodes...
     304      369239 :       this->transferNodesFromList(L2, first, last);
     305             : 
     306     1612824 :     base_list_type::splice(position, L2, first, last);
     307             :   }
     308             : 
     309             : public:
     310             :   //===----------------------------------------------------------------------===
     311             :   // Functionality derived from other functions defined above...
     312             :   //
     313             : 
     314             :   using base_list_type::size;
     315             : 
     316     3169673 :   iterator erase(iterator first, iterator last) {
     317    29889667 :     while (first != last)
     318    30701416 :       first = erase(first);
     319     3169676 :     return last;
     320             :   }
     321             : 
     322    15943186 :   void clear() { erase(begin(), end()); }
     323             : 
     324             :   // Front and back inserters...
     325      123999 :   void push_front(pointer val) { insert(begin(), val); }
     326   101392898 :   void push_back(pointer val) { insert(end(), val); }
     327       10958 :   void pop_front() {
     328             :     assert(!empty() && "pop_front() on empty list!");
     329       32874 :     erase(begin());
     330       10958 :   }
     331       71994 :   void pop_back() {
     332             :     assert(!empty() && "pop_back() on empty list!");
     333      487029 :     iterator t = end(); erase(--t);
     334       71994 :   }
     335             : 
     336             :   // Special forms of insert...
     337             :   template<class InIt> void insert(iterator where, InIt first, InIt last) {
     338        4188 :     for (; first != last; ++first) insert(where, *first);
     339             :   }
     340             : 
     341             :   // Splice members - defined in terms of transfer...
     342           1 :   void splice(iterator where, iplist_impl &L2) {
     343      296132 :     if (!L2.empty())
     344      427299 :       transfer(where, L2, L2.begin(), L2.end());
     345           1 :   }
     346      115460 :   void splice(iterator where, iplist_impl &L2, iterator first) {
     347      878970 :     iterator last = first; ++last;
     348      439485 :     if (where == first || where == last) return; // No change
     349       92209 :     transfer(where, L2, first, last);
     350             :   }
     351           0 :   void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
     352     1337675 :     if (first != last) transfer(where, L2, first, last);
     353           0 :   }
     354          13 :   void splice(iterator where, iplist_impl &L2, reference N) {
     355          26 :     splice(where, L2, iterator(N));
     356          13 :   }
     357      295099 :   void splice(iterator where, iplist_impl &L2, pointer N) {
     358      670645 :     splice(where, L2, iterator(N));
     359      295099 :   }
     360             : 
     361             :   template <class Compare>
     362             :   void merge(iplist_impl &Right, Compare comp) {
     363             :     if (this == &Right)
     364             :       return;
     365             :     this->transferNodesFromList(Right, Right.begin(), Right.end());
     366             :     base_list_type::merge(Right, comp);
     367             :   }
     368             :   void merge(iplist_impl &Right) { return merge(Right, op_less); }
     369             : 
     370             :   using base_list_type::sort;
     371             : 
     372             :   /// \brief Get the previous node, or \c nullptr for the list head.
     373             :   pointer getPrevNode(reference N) const {
     374     4837000 :     auto I = N.getIterator();
     375     4837000 :     if (I == begin())
     376             :       return nullptr;
     377     1537598 :     return &*std::prev(I);
     378             :   }
     379             :   /// \brief Get the previous node, or \c nullptr for the list head.
     380             :   const_pointer getPrevNode(const_reference N) const {
     381           1 :     return getPrevNode(const_cast<reference >(N));
     382             :   }
     383             : 
     384             :   /// \brief Get the next node, or \c nullptr for the list tail.
     385             :   pointer getNextNode(reference N) const {
     386    17573058 :     auto Next = std::next(N.getIterator());
     387    11715424 :     if (Next == end())
     388             :       return nullptr;
     389     1218567 :     return &*Next;
     390             :   }
     391             :   /// \brief Get the next node, or \c nullptr for the list tail.
     392             :   const_pointer getNextNode(const_reference N) const {
     393           1 :     return getNextNode(const_cast<reference >(N));
     394             :   }
     395             : };
     396             : 
     397             : /// An intrusive list with ownership and callbacks specified/controlled by
     398             : /// ilist_traits, only with API safe for polymorphic types.
     399             : ///
     400             : /// The \p Options parameters are the same as those for \a simple_ilist.  See
     401             : /// there for a description of what's available.
     402             : template <class T, class... Options>
     403     4352540 : class iplist
     404             :     : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
     405             :   typedef typename iplist::iplist_impl_type iplist_impl_type;
     406             : 
     407             : public:
     408     4368224 :   iplist() = default;
     409             : 
     410             :   iplist(const iplist &X) = delete;
     411             :   iplist &operator=(const iplist &X) = delete;
     412             : 
     413          48 :   iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
     414             :   iplist &operator=(iplist &&X) {
     415             :     *static_cast<iplist_impl_type *>(this) = std::move(X);
     416             :     return *this;
     417             :   }
     418             : };
     419             : 
     420             : template <class T, class... Options> using ilist = iplist<T, Options...>;
     421             : 
     422             : } // end namespace llvm
     423             : 
     424             : namespace std {
     425             : 
     426             :   // Ensure that swap uses the fast list swap...
     427             :   template<class Ty>
     428             :   void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
     429             :     Left.swap(Right);
     430             :   }
     431             : 
     432             : } // end namespace std
     433             : 
     434             : #endif // LLVM_ADT_ILIST_H

Generated by: LCOV version 1.13