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   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 
NodeNode42     Node(T &&V) : V(std::move(V)) {}
NodeNode43     Node(const T &V) : V(V) {}
NodeNode44     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 
getAlloc()52   AllocatorT &getAlloc() { return *this; }
getAlloc()53   const AllocatorT &getAlloc() const { return *this; }
54 
create(ArgTs &&...Args)55   template <class... ArgTs> Node *create(ArgTs &&... Args) {
56     return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);
57   }
58 
59   struct Cloner {
60     AllocatorList &AL;
61 
ClonerCloner62     Cloner(AllocatorList &AL) : AL(AL) {}
63 
operatorCloner64     Node *operator()(const Node &N) const { return AL.create(N.V); }
65   };
66 
67   struct Disposer {
68     AllocatorList &AL;
69 
DisposerDisposer70     Disposer(AllocatorList &AL) : AL(AL) {}
71 
operatorDisposer72     void operator()(Node *N) const {
73       N->~Node();
74       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     IteratorImpl() = default;
107     IteratorImpl(const IteratorImpl &) = default;
108     IteratorImpl &operator=(const IteratorImpl &) = default;
109 
IteratorImpl(const IteratorBase & I)110     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     reference operator*() const { return base_type::wrapped()->V; }
121     pointer operator->() const { return &operator*(); }
122 
123     friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) {
124       return L.wrapped() == R.wrapped();
125     }
126     friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) {
127       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   AllocatorList() = default;
AllocatorList(AllocatorList && X)141   AllocatorList(AllocatorList &&X)
142       : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
143 
AllocatorList(const AllocatorList & X)144   AllocatorList(const AllocatorList &X) {
145     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
146   }
147 
148   AllocatorList &operator=(AllocatorList &&X) {
149     clear(); // Dispose of current nodes explicitly.
150     List = std::move(X.List);
151     getAlloc() = std::move(X.getAlloc());
152     return *this;
153   }
154 
155   AllocatorList &operator=(const AllocatorList &X) {
156     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
157     return *this;
158   }
159 
~AllocatorList()160   ~AllocatorList() { clear(); }
161 
swap(AllocatorList & RHS)162   void swap(AllocatorList &RHS) {
163     List.swap(RHS.List);
164     std::swap(getAlloc(), RHS.getAlloc());
165   }
166 
empty()167   bool empty() { return List.empty(); }
size()168   size_t size() { return List.size(); }
169 
begin()170   iterator begin() { return iterator(List.begin()); }
end()171   iterator end() { return iterator(List.end()); }
begin()172   const_iterator begin() const { return const_iterator(List.begin()); }
end()173   const_iterator end() const { return const_iterator(List.end()); }
rbegin()174   reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
rend()175   reverse_iterator rend() { return reverse_iterator(List.rend()); }
rbegin()176   const_reverse_iterator rbegin() const {
177     return const_reverse_iterator(List.rbegin());
178   }
rend()179   const_reverse_iterator rend() const {
180     return const_reverse_iterator(List.rend());
181   }
182 
back()183   T &back() { return List.back().V; }
front()184   T &front() { return List.front().V; }
back()185   const T &back() const { return List.back().V; }
front()186   const T &front() const { return List.front().V; }
187 
emplace(iterator I,Ts &&...Vs)188   template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
189     return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
190   }
191 
insert(iterator I,T && V)192   iterator insert(iterator I, T &&V) {
193     return iterator(List.insert(I.wrapped(), *create(std::move(V))));
194   }
insert(iterator I,const T & V)195   iterator insert(iterator I, const T &V) {
196     return iterator(List.insert(I.wrapped(), *create(V)));
197   }
198 
199   template <class Iterator>
insert(iterator I,Iterator First,Iterator Last)200   void insert(iterator I, Iterator First, Iterator Last) {
201     for (; First != Last; ++First)
202       List.insert(I.wrapped(), *create(*First));
203   }
204 
erase(iterator I)205   iterator erase(iterator I) {
206     return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
207   }
208 
erase(iterator First,iterator Last)209   iterator erase(iterator First, iterator Last) {
210     return iterator(
211         List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
212   }
213 
clear()214   void clear() { List.clearAndDispose(Disposer(*this)); }
pop_back()215   void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
pop_front()216   void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
push_back(T && V)217   void push_back(T &&V) { insert(end(), std::move(V)); }
push_front(T && V)218   void push_front(T &&V) { insert(begin(), std::move(V)); }
push_back(const T & V)219   void push_back(const T &V) { insert(end(), V); }
push_front(const T & V)220   void push_front(const T &V) { insert(begin(), V); }
emplace_back(Ts &&...Vs)221   template <class... Ts> void emplace_back(Ts &&... Vs) {
222     emplace(end(), std::forward<Ts>(Vs)...);
223   }
emplace_front(Ts &&...Vs)224   template <class... Ts> void emplace_front(Ts &&... Vs) {
225     emplace(begin(), std::forward<Ts>(Vs)...);
226   }
227 
228   /// Reset the underlying allocator.
229   ///
230   /// \pre \c empty()
resetAlloc()231   void resetAlloc() {
232     assert(empty() && "Cannot reset allocator if not empty");
233     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
242