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