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