LLVM  16.0.0git
AllocatorList.h
Go to the documentation of this file.
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 
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 {
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 {
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;
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 =
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;
133  : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
134 
136  List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
137  }
138 
140  clear(); // Dispose of current nodes explicitly.
141  List = std::move(X.List);
142  getAlloc() = std::move(X.getAlloc());
143  return *this;
144  }
145 
147  List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
148  return *this;
149  }
150 
152 
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()); }
168  return const_reverse_iterator(List.rbegin());
169  }
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 
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 
197  return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
198  }
199 
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 
229 
230 } // end namespace llvm
231 
232 #endif // LLVM_ADT_ALLOCATORLIST_H
llvm::AllocatorList::front
T & front()
Definition: AllocatorList.h:175
llvm::AllocatorList< Token >::iterator
IteratorImpl< Token, typename list_type::iterator > iterator
Definition: AllocatorList.h:123
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
llvm::AllocatorList::AllocatorList
AllocatorList(const AllocatorList &X)
Definition: AllocatorList.h:135
llvm::PseudoProbeReservedId::Last
@ Last
Allocator.h
llvm::AllocatorList< Token >::reference
Token & reference
Definition: AllocatorList.h:79
llvm::AllocatorList::insert
void insert(iterator I, Iterator First, Iterator Last)
Definition: AllocatorList.h:191
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:235
T
#define T
Definition: Mips16ISelLowering.cpp:341
Node::Node
Node(Kind K_, Prec Precedence_=Prec::Primary, Cache RHSComponentCache_=Cache::No, Cache ArrayCache_=Cache::No, Cache FunctionCache_=Cache::No)
Definition: ItaniumDemangle.h:212
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::iterator_adaptor_base< IteratorImpl< ValueT, IteratorBase >, IteratorBase, std::bidirectional_iterator_tag, ValueT >::wrapped
const IteratorBase & wrapped() const
Definition: iterator.h:250
llvm::AllocatorList::erase
iterator erase(iterator I)
Definition: AllocatorList.h:196
llvm::AllocatorList::resetAlloc
void resetAlloc()
Reset the underlying allocator.
Definition: AllocatorList.h:222
llvm::AllocatorList< Token >::const_iterator
IteratorImpl< const Token, typename list_type::const_iterator > const_iterator
Definition: AllocatorList.h:127
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::AllocatorList::~AllocatorList
~AllocatorList()
Definition: AllocatorList.h:151
llvm::AllocatorList::swap
void swap(AllocatorList &RHS)
Definition: AllocatorList.h:153
IteratorBase
llvm::AllocatorList::begin
iterator begin()
Definition: AllocatorList.h:161
llvm::AllocatorList::erase
iterator erase(iterator First, iterator Last)
Definition: AllocatorList.h:200
llvm::simple_ilist< Node >::difference_type
ptrdiff_t difference_type
Definition: simple_ilist.h:100
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::AllocatorList::end
iterator end()
Definition: AllocatorList.h:162
llvm::AllocatorList::pop_front
void pop_front()
Definition: AllocatorList.h:207
llvm::AllocatorList::rbegin
reverse_iterator rbegin()
Definition: AllocatorList.h:165
llvm::AllocatorList::emplace
iterator emplace(iterator I, Ts &&... Vs)
Definition: AllocatorList.h:179
llvm::AllocatorList::begin
const_iterator begin() const
Definition: AllocatorList.h:163
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::AllocatorList::end
const_iterator end() const
Definition: AllocatorList.h:164
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AllocatorList
A linked-list with a custom, local allocator.
Definition: AllocatorList.h:33
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1836
llvm::AllocatorList::rend
reverse_iterator rend()
Definition: AllocatorList.h:166
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::AllocatorList::AllocatorList
AllocatorList(AllocatorList &&X)
Definition: AllocatorList.h:132
llvm::AllocatorList::front
const T & front() const
Definition: AllocatorList.h:177
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2134
llvm::AllocatorList< Token >::pointer
Token * pointer
Definition: AllocatorList.h:78
llvm::AllocatorList< Token >::const_pointer
const Token * const_pointer
Definition: AllocatorList.h:80
llvm::AllocatorList::empty
bool empty()
Definition: AllocatorList.h:158
ValueT
llvm::AllocatorList::insert
iterator insert(iterator I, T &&V)
Definition: AllocatorList.h:183
llvm::simple_ilist< Node >::size_type
size_t size_type
Definition: simple_ilist.h:99
llvm::AllocatorList< Token >::size_type
typename list_type::size_type size_type
Definition: AllocatorList.h:82
llvm::AllocatorList< Token >::difference_type
typename list_type::difference_type difference_type
Definition: AllocatorList.h:83
llvm::ilist_node
Definition: ilist_node.h:149
llvm::AllocatorList::clear
void clear()
Definition: AllocatorList.h:205
llvm::AllocatorList::push_back
void push_back(const T &V)
Definition: AllocatorList.h:210
std
Definition: BitVector.h:851
llvm::AllocatorList::rbegin
const_reverse_iterator rbegin() const
Definition: AllocatorList.h:167
llvm::AllocatorList::push_front
void push_front(T &&V)
Definition: AllocatorList.h:209
llvm::AllocatorList::size
size_t size()
Definition: AllocatorList.h:159
llvm::AllocatorList< Token >::value_type
Token value_type
Definition: AllocatorList.h:77
llvm::AllocatorList::push_front
void push_front(const T &V)
Definition: AllocatorList.h:211
llvm::AllocatorList::insert
iterator insert(iterator I, const T &V)
Definition: AllocatorList.h:186
llvm::AllocatorList::back
const T & back() const
Definition: AllocatorList.h:176
List
const NodeList & List
Definition: RDFGraph.cpp:199
llvm::AllocatorList::emplace_back
void emplace_back(Ts &&... Vs)
Definition: AllocatorList.h:212
N
#define N
llvm::AllocatorList::AllocatorList
AllocatorList()=default
llvm::AllocatorList::pop_back
void pop_back()
Definition: AllocatorList.h:206
simple_ilist.h
llvm::simple_ilist< Node >
ilist_node.h
llvm::AllocatorList::operator=
AllocatorList & operator=(AllocatorList &&X)
Definition: AllocatorList.h:139
llvm::AllocatorList< Token >::const_reference
const Token & const_reference
Definition: AllocatorList.h:81
llvm::AllocatorList< Token >::reverse_iterator
IteratorImpl< Token, typename list_type::reverse_iterator > reverse_iterator
Definition: AllocatorList.h:125
llvm::AllocatorList< Token >::const_reverse_iterator
IteratorImpl< const Token, typename list_type::const_reverse_iterator > const_reverse_iterator
Definition: AllocatorList.h:129
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::AllocatorList::rend
const_reverse_iterator rend() const
Definition: AllocatorList.h:170
llvm::AllocatorList::back
T & back()
Definition: AllocatorList.h:174
llvm::AllocatorList::push_back
void push_back(T &&V)
Definition: AllocatorList.h:208
llvm::AllocatorList::operator=
AllocatorList & operator=(const AllocatorList &X)
Definition: AllocatorList.h:146
llvm::AllocatorList::emplace_front
void emplace_front(Ts &&... Vs)
Definition: AllocatorList.h:215