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

          Line data    Source code
       1             : //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- 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             : #ifndef LLVM_ADT_SIMPLE_ILIST_H
      11             : #define LLVM_ADT_SIMPLE_ILIST_H
      12             : 
      13             : #include "llvm/ADT/ilist_base.h"
      14             : #include "llvm/ADT/ilist_iterator.h"
      15             : #include "llvm/ADT/ilist_node.h"
      16             : #include "llvm/ADT/ilist_node_options.h"
      17             : #include "llvm/Support/Compiler.h"
      18             : #include <algorithm>
      19             : #include <cassert>
      20             : #include <cstddef>
      21             : #include <functional>
      22             : #include <iterator>
      23             : #include <utility>
      24             : 
      25             : namespace llvm {
      26             : 
      27             : /// A simple intrusive list implementation.
      28             : ///
      29             : /// This is a simple intrusive list for a \c T that inherits from \c
      30             : /// ilist_node<T>.  The list never takes ownership of anything inserted in it.
      31             : ///
      32             : /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never allocates or
      33             : /// deletes values, and has no callback traits.
      34             : ///
      35             : /// The API for adding nodes include \a push_front(), \a push_back(), and \a
      36             : /// insert().  These all take values by reference (not by pointer), except for
      37             : /// the range version of \a insert().
      38             : ///
      39             : /// There are three sets of API for discarding nodes from the list: \a
      40             : /// remove(), which takes a reference to the node to remove, \a erase(), which
      41             : /// takes an iterator or iterator range and returns the next one, and \a
      42             : /// clear(), which empties out the container.  All three are constant time
      43             : /// operations.  None of these deletes any nodes; in particular, if there is a
      44             : /// single node in the list, then these have identical semantics:
      45             : /// \li \c L.remove(L.front());
      46             : /// \li \c L.erase(L.begin());
      47             : /// \li \c L.clear();
      48             : ///
      49             : /// As a convenience for callers, there are parallel APIs that take a \c
      50             : /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
      51             : /// eraseAndDispose(), and \a clearAndDispose().  These have different names
      52             : /// because the extra semantic is otherwise non-obvious.  They are equivalent
      53             : /// to calling \a std::for_each() on the range to be discarded.
      54             : ///
      55             : /// The currently available \p Options customize the nodes in the list.  The
      56             : /// same options must be specified in the \a ilist_node instantation for
      57             : /// compatibility (although the order is irrelevant).
      58             : /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this
      59             : /// list should use.  This is useful if a type \p T is part of multiple,
      60             : /// independent lists simultaneously.
      61             : /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a
      62             : /// node is a sentinel.  Specifying \c true enables the \a
      63             : /// ilist_node::isSentinel() API.  Unlike \a ilist_node::isKnownSentinel(),
      64             : /// which is only appropriate for assertions, \a ilist_node::isSentinel() is
      65             : /// appropriate for real logic.
      66             : ///
      67             : /// Here are examples of \p Options usage:
      68             : /// \li \c simple_ilist<T> gives the defaults.  \li \c
      69             : /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a
      70             : /// ilist_node::isSentinel() API.
      71             : /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>>
      72             : /// specifies a tag of A and that tracking should be off (even when
      73             : /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
      74             : /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is
      75             : /// equivalent to the last.
      76             : ///
      77             : /// See \a is_valid_option for steps on adding a new option.
      78             : template <typename T, class... Options>
      79             : class simple_ilist
      80             :     : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
      81             :       ilist_detail::SpecificNodeAccess<
      82             :           typename ilist_detail::compute_node_options<T, Options...>::type> {
      83             :   static_assert(ilist_detail::check_options<Options...>::value,
      84             :                 "Unrecognized node option!");
      85             :   using OptionsT =
      86             :       typename ilist_detail::compute_node_options<T, Options...>::type;
      87             :   using list_base_type = typename OptionsT::list_base_type;
      88             :   ilist_sentinel<OptionsT> Sentinel;
      89             : 
      90             : public:
      91             :   using value_type = typename OptionsT::value_type;
      92             :   using pointer = typename OptionsT::pointer;
      93             :   using reference = typename OptionsT::reference;
      94             :   using const_pointer = typename OptionsT::const_pointer;
      95             :   using const_reference = typename OptionsT::const_reference;
      96             :   using iterator = ilist_iterator<OptionsT, false, false>;
      97             :   using const_iterator = ilist_iterator<OptionsT, false, true>;
      98             :   using reverse_iterator = ilist_iterator<OptionsT, true, false>;
      99             :   using const_reverse_iterator = ilist_iterator<OptionsT, true, true>;
     100             :   using size_type = size_t;
     101             :   using difference_type = ptrdiff_t;
     102             : 
     103     7709608 :   simple_ilist() = default;
     104             :   ~simple_ilist() = default;
     105             : 
     106             :   // No copy constructors.
     107             :   simple_ilist(const simple_ilist &) = delete;
     108             :   simple_ilist &operator=(const simple_ilist &) = delete;
     109             : 
     110             :   // Move constructors.
     111         104 :   simple_ilist(simple_ilist &&X) { splice(end(), X); }
     112             :   simple_ilist &operator=(simple_ilist &&X) {
     113           6 :     clear();
     114          12 :     splice(end(), X);
     115             :     return *this;
     116             :   }
     117             : 
     118   429333432 :   iterator begin() { return ++iterator(Sentinel); }
     119    94281346 :   const_iterator begin() const { return ++const_iterator(Sentinel); }
     120   207029933 :   iterator end() { return iterator(Sentinel); }
     121    49070773 :   const_iterator end() const { return const_iterator(Sentinel); }
     122    27661668 :   reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
     123             :   const_reverse_iterator rbegin() const {
     124   220356512 :     return ++const_reverse_iterator(Sentinel);
     125             :   }
     126     5086027 :   reverse_iterator rend() { return reverse_iterator(Sentinel); }
     127             :   const_reverse_iterator rend() const {
     128       56283 :     return const_reverse_iterator(Sentinel);
     129             :   }
     130             : 
     131             :   /// Check if the list is empty in constant time.
     132   305304520 :   LLVM_NODISCARD bool empty() const { return Sentinel.empty(); }
     133             : 
     134             :   /// Calculate the size of the list in linear time.
     135             :   LLVM_NODISCARD size_type size() const {
     136    10829092 :     return std::distance(begin(), end());
     137             :   }
     138             : 
     139    45380908 :   reference front() { return *begin(); }
     140    20368042 :   const_reference front() const { return *begin(); }
     141    11081870 :   reference back() { return *rbegin(); }
     142   220165350 :   const_reference back() const { return *rbegin(); }
     143             : 
     144             :   /// Insert a node at the front; never copies.
     145      188274 :   void push_front(reference Node) { insert(begin(), Node); }
     146             : 
     147             :   /// Insert a node at the back; never copies.
     148     1648706 :   void push_back(reference Node) { insert(end(), Node); }
     149             : 
     150             :   /// Remove the node at the front; never deletes.
     151           4 :   void pop_front() { erase(begin()); }
     152             : 
     153             :   /// Remove the node at the back; never deletes.
     154           6 :   void pop_back() { erase(--end()); }
     155             : 
     156             :   /// Swap with another list in place using std::swap.
     157           2 :   void swap(simple_ilist &X) { std::swap(*this, X); }
     158             : 
     159             :   /// Insert a node by reference; never copies.
     160             :   iterator insert(iterator I, reference Node) {
     161   112119428 :     list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
     162    56059714 :     return iterator(&Node);
     163             :   }
     164             : 
     165             :   /// Insert a range of nodes; never copies.
     166             :   template <class Iterator>
     167             :   void insert(iterator I, Iterator First, Iterator Last) {
     168             :     for (; First != Last; ++First)
     169             :       insert(I, *First);
     170             :   }
     171             : 
     172             :   /// Clone another list.
     173             :   template <class Cloner, class Disposer>
     174           2 :   void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
     175           4 :     clearAndDispose(dispose);
     176           7 :     for (const_reference V : L2)
     177           2 :       push_back(*clone(V));
     178           2 :   }
     179             : 
     180             :   /// Remove a node by reference; never deletes.
     181             :   ///
     182             :   /// \see \a erase() for removing by iterator.
     183             :   /// \see \a removeAndDispose() if the node should be deleted.
     184   101096626 :   void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }
     185             : 
     186             :   /// Remove a node by reference and dispose of it.
     187             :   template <class Disposer>
     188             :   void removeAndDispose(reference N, Disposer dispose) {
     189           4 :     remove(N);
     190           2 :     dispose(&N);
     191             :   }
     192             : 
     193             :   /// Remove a node by iterator; never deletes.
     194             :   ///
     195             :   /// \see \a remove() for removing by reference.
     196             :   /// \see \a eraseAndDispose() it the node should be deleted.
     197             :   iterator erase(iterator I) {
     198             :     assert(I != end() && "Cannot remove end of list!");
     199     3991736 :     remove(*I++);
     200             :     return I;
     201             :   }
     202             : 
     203             :   /// Remove a range of nodes; never deletes.
     204             :   ///
     205             :   /// \see \a eraseAndDispose() if the nodes should be deleted.
     206             :   iterator erase(iterator First, iterator Last) {
     207           2 :     list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
     208             :     return Last;
     209             :   }
     210             : 
     211             :   /// Remove a node by iterator and dispose of it.
     212             :   template <class Disposer>
     213      997871 :   iterator eraseAndDispose(iterator I, Disposer dispose) {
     214             :     auto Next = std::next(I);
     215     1995858 :     erase(I);
     216     1995805 :     dispose(&*I);
     217      997871 :     return Next;
     218             :   }
     219             : 
     220             :   /// Remove a range of nodes and dispose of them.
     221             :   template <class Disposer>
     222             :   iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
     223        6957 :     while (First != Last)
     224        3529 :       First = eraseAndDispose(First, dispose);
     225             :     return Last;
     226             :   }
     227             : 
     228             :   /// Clear the list; never deletes.
     229             :   ///
     230             :   /// \see \a clearAndDispose() if the nodes should be deleted.
     231      653510 :   void clear() { Sentinel.reset(); }
     232             : 
     233             :   /// Clear the list and dispose of the nodes.
     234             :   template <class Disposer> void clearAndDispose(Disposer dispose) {
     235        6877 :     eraseAndDispose(begin(), end(), dispose);
     236             :   }
     237             : 
     238             :   /// Splice in another list.
     239             :   void splice(iterator I, simple_ilist &L2) {
     240          66 :     splice(I, L2, L2.begin(), L2.end());
     241             :   }
     242             : 
     243             :   /// Splice in a node from another list.
     244           1 :   void splice(iterator I, simple_ilist &L2, iterator Node) {
     245           1 :     splice(I, L2, Node, std::next(Node));
     246           1 :   }
     247             : 
     248             :   /// Splice in a range of nodes from another list.
     249             :   void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
     250     2703479 :     list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
     251     1613579 :                                    *Last.getNodePtr());
     252             :   }
     253             : 
     254             :   /// Merge in another list.
     255             :   ///
     256             :   /// \pre \c this and \p RHS are sorted.
     257             :   ///@{
     258           5 :   void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
     259             :   template <class Compare> void merge(simple_ilist &RHS, Compare comp);
     260             :   ///@}
     261             : 
     262             :   /// Sort the list.
     263             :   ///@{
     264           2 :   void sort() { sort(std::less<T>()); }
     265             :   template <class Compare> void sort(Compare comp);
     266             :   ///@}
     267             : };
     268             : 
     269             : template <class T, class... Options>
     270             : template <class Compare>
     271         342 : void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) {
     272         684 :   if (this == &RHS || RHS.empty())
     273          65 :     return;
     274         680 :   iterator LI = begin(), LE = end();
     275         680 :   iterator RI = RHS.begin(), RE = RHS.end();
     276         784 :   while (LI != LE) {
     277        1083 :     if (comp(*RI, *LI)) {
     278             :       // Transfer a run of at least size 1 from RHS to LHS.
     279         216 :       iterator RunStart = RI++;
     280         334 :       RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
     281         216 :       splice(LI, RHS, RunStart, RI);
     282         108 :       if (RI == RE)
     283             :         return;
     284             :     }
     285             :     ++LI;
     286             :   }
     287             :   // Transfer the remaining RHS nodes once LHS is finished.
     288         277 :   splice(LE, RHS, RI, RE);
     289             : }
     290             : 
     291             : template <class T, class... Options>
     292             : template <class Compare>
     293         742 : void simple_ilist<T, Options...>::sort(Compare comp) {
     294             :   // Vacuously sorted.
     295        2965 :   if (empty() || std::next(begin()) == end())
     296         407 :     return;
     297             : 
     298             :   // Split the list in the middle.
     299             :   iterator Center = begin(), End = begin();
     300        2059 :   while (End != end() && ++End != end()) {
     301         496 :     ++Center;
     302             :     ++End;
     303             :   }
     304         335 :   simple_ilist RHS;
     305         670 :   RHS.splice(RHS.end(), *this, Center, end());
     306             : 
     307             :   // Sort the sublists and merge back together.
     308         335 :   sort(comp);
     309         335 :   RHS.sort(comp);
     310         335 :   merge(RHS, comp);
     311             : }
     312             : 
     313             : } // end namespace llvm
     314             : 
     315             : #endif // LLVM_ADT_SIMPLE_ILIST_H

Generated by: LCOV version 1.13