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

          Line data    Source code
       1             : //===- llvm/ADT/AllocatorList.h - Custom allocator 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_ALLOCATORLIST_H
      11             : #define LLVM_ADT_ALLOCATORLIST_H
      12             : 
      13             : #include "llvm/ADT/ilist_node.h"
      14             : #include "llvm/ADT/iterator.h"
      15             : #include "llvm/ADT/simple_ilist.h"
      16             : #include "llvm/Support/Allocator.h"
      17             : #include <algorithm>
      18             : #include <cassert>
      19             : #include <cstddef>
      20             : #include <iterator>
      21             : #include <type_traits>
      22             : #include <utility>
      23             : 
      24             : namespace llvm {
      25             : 
      26             : /// A linked-list with a custom, local allocator.
      27             : ///
      28             : /// Expose a std::list-like interface that owns and uses a custom LLVM-style
      29             : /// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the
      30             : /// implementation details.
      31             : ///
      32             : /// Because this list owns the allocator, calling \a splice() with a different
      33             : /// list isn't generally safe.  As such, \a splice has been left out of the
      34             : /// interface entirely.
      35             : template <class T, class AllocatorT> class AllocatorList : AllocatorT {
      36     1995740 :   struct Node : ilist_node<Node> {
      37             :     Node(Node &&) = delete;
      38             :     Node(const Node &) = delete;
      39             :     Node &operator=(Node &&) = delete;
      40             :     Node &operator=(const Node &) = delete;
      41             : 
      42         108 :     Node(T &&V) : V(std::move(V)) {}
      43     2993593 :     Node(const T &V) : V(V) {}
      44          54 :     template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {}
      45             :     T V;
      46             :   };
      47             : 
      48             :   using list_type = simple_ilist<Node>;
      49             : 
      50             :   list_type List;
      51             : 
      52     1437047 :   AllocatorT &getAlloc() { return *this; }
      53             :   const AllocatorT &getAlloc() const { return *this; }
      54             : 
      55      997877 :   template <class... ArgTs> Node *create(ArgTs &&... Args) {
      56     3991714 :     return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);
      57             :   }
      58             : 
      59             :   struct Cloner {
      60             :     AllocatorList &AL;
      61             : 
      62           2 :     Cloner(AllocatorList &AL) : AL(AL) {}
      63             : 
      64           2 :     Node *operator()(const Node &N) const { return AL.create(N.V); }
      65             :   };
      66             : 
      67             :   struct Disposer {
      68             :     AllocatorList &AL;
      69             : 
      70      997822 :     Disposer(AllocatorList &AL) : AL(AL) {}
      71             : 
      72             :     void operator()(Node *N) const {
      73      997870 :       N->~Node();
      74      997917 :       AL.getAlloc().Deallocate(N);
      75             :     }
      76             :   };
      77             : 
      78             : public:
      79             :   using value_type = T;
      80             :   using pointer = T *;
      81             :   using reference = T &;
      82             :   using const_pointer = const T *;
      83             :   using const_reference = const T &;
      84             :   using size_type = typename list_type::size_type;
      85             :   using difference_type = typename list_type::difference_type;
      86             : 
      87             : private:
      88             :   template <class ValueT, class IteratorBase>
      89             :   class IteratorImpl
      90             :       : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,
      91             :                                      IteratorBase,
      92             :                                      std::bidirectional_iterator_tag, ValueT> {
      93             :     template <class OtherValueT, class OtherIteratorBase>
      94             :     friend class IteratorImpl;
      95             :     friend AllocatorList;
      96             : 
      97             :     using base_type =
      98             :         iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,
      99             :                               std::bidirectional_iterator_tag, ValueT>;
     100             : 
     101             :   public:
     102             :     using value_type = ValueT;
     103             :     using pointer = ValueT *;
     104             :     using reference = ValueT &;
     105             : 
     106     7497446 :     IteratorImpl() = default;
     107             :     IteratorImpl(const IteratorImpl &) = default;
     108             :     IteratorImpl &operator=(const IteratorImpl &) = default;
     109             : 
     110    12196194 :     explicit IteratorImpl(const IteratorBase &I) : base_type(I) {}
     111             : 
     112             :     template <class OtherValueT, class OtherIteratorBase>
     113             :     IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X,
     114             :                  typename std::enable_if<std::is_convertible<
     115             :                      OtherIteratorBase, IteratorBase>::value>::type * = nullptr)
     116             :         : base_type(X.wrapped()) {}
     117             : 
     118             :     ~IteratorImpl() = default;
     119             : 
     120      372422 :     reference operator*() const { return base_type::wrapped()->V; }
     121      186191 :     pointer operator->() const { return &operator*(); }
     122             : 
     123             :     friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) {
     124     1687666 :       return L.wrapped() == R.wrapped();
     125             :     }
     126             :     friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) {
     127      364926 :       return !(L == R);
     128             :     }
     129             :   };
     130             : 
     131             : public:
     132             :   using iterator = IteratorImpl<T, typename list_type::iterator>;
     133             :   using reverse_iterator =
     134             :       IteratorImpl<T, typename list_type::reverse_iterator>;
     135             :   using const_iterator =
     136             :       IteratorImpl<const T, typename list_type::const_iterator>;
     137             :   using const_reverse_iterator =
     138             :       IteratorImpl<const T, typename list_type::const_reverse_iterator>;
     139             : 
     140       10227 :   AllocatorList() = default;
     141             :   AllocatorList(AllocatorList &&X)
     142             :       : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
     143             : 
     144             :   AllocatorList(const AllocatorList &X) {
     145             :     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
     146             :   }
     147             : 
     148           2 :   AllocatorList &operator=(AllocatorList &&X) {
     149           2 :     clear(); // Dispose of current nodes explicitly.
     150           4 :     List = std::move(X.List);
     151           4 :     getAlloc() = std::move(X.getAlloc());
     152           2 :     return *this;
     153             :   }
     154             : 
     155             :   AllocatorList &operator=(const AllocatorList &X) {
     156           6 :     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
     157             :     return *this;
     158             :   }
     159             : 
     160        6794 :   ~AllocatorList() { clear(); }
     161             : 
     162             :   void swap(AllocatorList &RHS) {
     163           2 :     List.swap(RHS.List);
     164           1 :     std::swap(getAlloc(), RHS.getAlloc());
     165             :   }
     166             : 
     167    11015760 :   bool empty() { return List.empty(); }
     168          10 :   size_t size() { return List.size(); }
     169             : 
     170    11115927 :   iterator begin() { return iterator(List.begin()); }
     171     4184598 :   iterator end() { return iterator(List.end()); }
     172             :   const_iterator begin() const { return const_iterator(List.begin()); }
     173             :   const_iterator end() const { return const_iterator(List.end()); }
     174           3 :   reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
     175           3 :   reverse_iterator rend() { return reverse_iterator(List.rend()); }
     176             :   const_reverse_iterator rbegin() const {
     177             :     return const_reverse_iterator(List.rbegin());
     178             :   }
     179             :   const_reverse_iterator rend() const {
     180             :     return const_reverse_iterator(List.rend());
     181             :   }
     182             : 
     183          40 :   T &back() { return List.back().V; }
     184     6423038 :   T &front() { return List.front().V; }
     185             :   const T &back() const { return List.back().V; }
     186             :   const T &front() const { return List.front().V; }
     187             : 
     188          10 :   template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
     189          48 :     return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
     190             :   }
     191             : 
     192          16 :   iterator insert(iterator I, T &&V) {
     193         130 :     return iterator(List.insert(I.wrapped(), *create(std::move(V))));
     194             :   }
     195          10 :   iterator insert(iterator I, const T &V) {
     196     2993620 :     return iterator(List.insert(I.wrapped(), *create(V)));
     197             :   }
     198             : 
     199             :   template <class Iterator>
     200           2 :   void insert(iterator I, Iterator First, Iterator Last) {
     201          22 :     for (; First != Last; ++First)
     202          30 :       List.insert(I.wrapped(), *create(*First));
     203           2 :   }
     204             : 
     205             :   iterator erase(iterator I) {
     206           4 :     return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
     207             :   }
     208             : 
     209             :   iterator erase(iterator First, iterator Last) {
     210             :     return iterator(
     211             :         List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
     212             :   }
     213             : 
     214       10266 :   void clear() { List.clearAndDispose(Disposer(*this)); }
     215          80 :   void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
     216     2983158 :   void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
     217          88 :   void push_back(T &&V) { insert(end(), std::move(V)); }
     218          10 :   void push_front(T &&V) { insert(begin(), std::move(V)); }
     219     1561700 :   void push_back(const T &V) { insert(end(), V); }
     220           5 :   void push_front(const T &V) { insert(begin(), V); }
     221           2 :   template <class... Ts> void emplace_back(Ts &&... Vs) {
     222          14 :     emplace(end(), std::forward<Ts>(Vs)...);
     223           2 :   }
     224             :   template <class... Ts> void emplace_front(Ts &&... Vs) {
     225          10 :     emplace(begin(), std::forward<Ts>(Vs)...);
     226             :   }
     227             : 
     228             :   /// Reset the underlying allocator.
     229             :   ///
     230             :   /// \pre \c empty()
     231             :   void resetAlloc() {
     232             :     assert(empty() && "Cannot reset allocator if not empty");
     233      439115 :     getAlloc().Reset();
     234             :   }
     235             : };
     236             : 
     237             : template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
     238             : 
     239             : } // end namespace llvm
     240             : 
     241             : #endif // LLVM_ADT_ALLOCATORLIST_H

Generated by: LCOV version 1.13