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 
NodeNode41     Node(T &&V) : V(std::move(V)) {}
NodeNode42     Node(const T &V) : V(V) {}
NodeNode43     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 
getAlloc()51   AllocatorT &getAlloc() { return *this; }
getAlloc()52   const AllocatorT &getAlloc() const { return *this; }
53 
create(ArgTs &&...Args)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 
ClonerCloner61     Cloner(AllocatorList &AL) : AL(AL) {}
62 
operatorCloner63     Node *operator()(const Node &N) const { return AL.create(N.V); }
64   };
65 
66   struct Disposer {
67     AllocatorList &AL;
68 
DisposerDisposer69     Disposer(AllocatorList &AL) : AL(AL) {}
70 
operatorDisposer71     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 
IteratorImpl(const IteratorBase & I)109     explicit IteratorImpl(const IteratorBase &I) : base_type(I) {}
110 
111     template <class OtherValueT, class OtherIteratorBase>
112     IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X,
113                  std::enable_if_t<std::is_convertible<
114                      OtherIteratorBase, IteratorBase>::value> * = 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 
123 public:
124   using iterator = IteratorImpl<T, typename list_type::iterator>;
125   using reverse_iterator =
126       IteratorImpl<T, typename list_type::reverse_iterator>;
127   using const_iterator =
128       IteratorImpl<const T, typename list_type::const_iterator>;
129   using const_reverse_iterator =
130       IteratorImpl<const T, typename list_type::const_reverse_iterator>;
131 
132   AllocatorList() = default;
AllocatorList(AllocatorList && X)133   AllocatorList(AllocatorList &&X)
134       : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
135 
AllocatorList(const AllocatorList & X)136   AllocatorList(const AllocatorList &X) {
137     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
138   }
139 
140   AllocatorList &operator=(AllocatorList &&X) {
141     clear(); // Dispose of current nodes explicitly.
142     List = std::move(X.List);
143     getAlloc() = std::move(X.getAlloc());
144     return *this;
145   }
146 
147   AllocatorList &operator=(const AllocatorList &X) {
148     List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
149     return *this;
150   }
151 
~AllocatorList()152   ~AllocatorList() { clear(); }
153 
swap(AllocatorList & RHS)154   void swap(AllocatorList &RHS) {
155     List.swap(RHS.List);
156     std::swap(getAlloc(), RHS.getAlloc());
157   }
158 
empty()159   bool empty() { return List.empty(); }
size()160   size_t size() { return List.size(); }
161 
begin()162   iterator begin() { return iterator(List.begin()); }
end()163   iterator end() { return iterator(List.end()); }
begin()164   const_iterator begin() const { return const_iterator(List.begin()); }
end()165   const_iterator end() const { return const_iterator(List.end()); }
rbegin()166   reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
rend()167   reverse_iterator rend() { return reverse_iterator(List.rend()); }
rbegin()168   const_reverse_iterator rbegin() const {
169     return const_reverse_iterator(List.rbegin());
170   }
rend()171   const_reverse_iterator rend() const {
172     return const_reverse_iterator(List.rend());
173   }
174 
back()175   T &back() { return List.back().V; }
front()176   T &front() { return List.front().V; }
back()177   const T &back() const { return List.back().V; }
front()178   const T &front() const { return List.front().V; }
179 
emplace(iterator I,Ts &&...Vs)180   template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
181     return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
182   }
183 
insert(iterator I,T && V)184   iterator insert(iterator I, T &&V) {
185     return iterator(List.insert(I.wrapped(), *create(std::move(V))));
186   }
insert(iterator I,const T & V)187   iterator insert(iterator I, const T &V) {
188     return iterator(List.insert(I.wrapped(), *create(V)));
189   }
190 
191   template <class Iterator>
insert(iterator I,Iterator First,Iterator Last)192   void insert(iterator I, Iterator First, Iterator Last) {
193     for (; First != Last; ++First)
194       List.insert(I.wrapped(), *create(*First));
195   }
196 
erase(iterator I)197   iterator erase(iterator I) {
198     return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
199   }
200 
erase(iterator First,iterator Last)201   iterator erase(iterator First, iterator Last) {
202     return iterator(
203         List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
204   }
205 
clear()206   void clear() { List.clearAndDispose(Disposer(*this)); }
pop_back()207   void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
pop_front()208   void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
push_back(T && V)209   void push_back(T &&V) { insert(end(), std::move(V)); }
push_front(T && V)210   void push_front(T &&V) { insert(begin(), std::move(V)); }
push_back(const T & V)211   void push_back(const T &V) { insert(end(), V); }
push_front(const T & V)212   void push_front(const T &V) { insert(begin(), V); }
emplace_back(Ts &&...Vs)213   template <class... Ts> void emplace_back(Ts &&... Vs) {
214     emplace(end(), std::forward<Ts>(Vs)...);
215   }
emplace_front(Ts &&...Vs)216   template <class... Ts> void emplace_front(Ts &&... Vs) {
217     emplace(begin(), std::forward<Ts>(Vs)...);
218   }
219 
220   /// Reset the underlying allocator.
221   ///
222   /// \pre \c empty()
resetAlloc()223   void resetAlloc() {
224     assert(empty() && "Cannot reset allocator if not empty");
225     getAlloc().Reset();
226   }
227 };
228 
229 template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
230 
231 } // end namespace llvm
232 
233 #endif // LLVM_ADT_ALLOCATORLIST_H
234