include/llvm/ADT/AllocatorList.h

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