LLVM  13.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 <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 
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 {
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 {
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;
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 =
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  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;
134  : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
135 
137  List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
138  }
139 
141  clear(); // Dispose of current nodes explicitly.
142  List = std::move(X.List);
143  getAlloc() = std::move(X.getAlloc());
144  return *this;
145  }
146 
148  List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
149  return *this;
150  }
151 
153 
154  void swap(AllocatorList &RHS) {
155  List.swap(RHS.List);
156  std::swap(getAlloc(), RHS.getAlloc());
157  }
158 
159  bool empty() { return List.empty(); }
160  size_t size() { return List.size(); }
161 
162  iterator begin() { return iterator(List.begin()); }
163  iterator end() { return iterator(List.end()); }
164  const_iterator begin() const { return const_iterator(List.begin()); }
165  const_iterator end() const { return const_iterator(List.end()); }
169  return const_reverse_iterator(List.rbegin());
170  }
172  return const_reverse_iterator(List.rend());
173  }
174 
175  T &back() { return List.back().V; }
176  T &front() { return List.front().V; }
177  const T &back() const { return List.back().V; }
178  const T &front() const { return List.front().V; }
179 
180  template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
181  return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
182  }
183 
185  return iterator(List.insert(I.wrapped(), *create(std::move(V))));
186  }
187  iterator insert(iterator I, const T &V) {
188  return iterator(List.insert(I.wrapped(), *create(V)));
189  }
190 
191  template <class Iterator>
192  void insert(iterator I, Iterator First, Iterator Last) {
193  for (; First != Last; ++First)
194  List.insert(I.wrapped(), *create(*First));
195  }
196 
198  return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
199  }
200 
202  return iterator(
203  List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
204  }
205 
206  void clear() { List.clearAndDispose(Disposer(*this)); }
207  void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
208  void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
209  void push_back(T &&V) { insert(end(), std::move(V)); }
210  void push_front(T &&V) { insert(begin(), std::move(V)); }
211  void push_back(const T &V) { insert(end(), V); }
212  void push_front(const T &V) { insert(begin(), V); }
213  template <class... Ts> void emplace_back(Ts &&... Vs) {
214  emplace(end(), std::forward<Ts>(Vs)...);
215  }
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()
223  void resetAlloc() {
224  assert(empty() && "Cannot reset allocator if not empty");
225  getAlloc().Reset();
226  }
227 };
228 
230 
231 } // end namespace llvm
232 
233 #endif // LLVM_ADT_ALLOCATORLIST_H
llvm::AllocatorList::front
T & front()
Definition: AllocatorList.h:176
llvm::AllocatorList< Token >::iterator
IteratorImpl< Token, typename list_type::iterator > iterator
Definition: AllocatorList.h:124
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:250
llvm::AllocatorList::AllocatorList
AllocatorList(const AllocatorList &X)
Definition: AllocatorList.h:136
Allocator.h
llvm::AllocatorList< Token >::reference
Token & reference
Definition: AllocatorList.h:80
llvm::AllocatorList::insert
void insert(iterator I, Iterator First, Iterator Last)
Definition: AllocatorList.h:192
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:207
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::iterator_adaptor_base< IteratorImpl< ValueT, IteratorBase >, IteratorBase, std::bidirectional_iterator_tag, ValueT >::wrapped
const IteratorBase & wrapped() const
Definition: iterator.h:222
llvm::AllocatorList::erase
iterator erase(iterator I)
Definition: AllocatorList.h:197
llvm::AllocatorList::resetAlloc
void resetAlloc()
Reset the underlying allocator.
Definition: AllocatorList.h:223
llvm::AllocatorList< Token >::const_iterator
IteratorImpl< const Token, typename list_type::const_iterator > const_iterator
Definition: AllocatorList.h:128
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:152
llvm::AllocatorList::swap
void swap(AllocatorList &RHS)
Definition: AllocatorList.h:154
IteratorBase
llvm::AllocatorList::begin
iterator begin()
Definition: AllocatorList.h:162
llvm::AllocatorList::erase
iterator erase(iterator First, iterator Last)
Definition: AllocatorList.h:201
Node::Node
Node(Kind K_, Cache RHSComponentCache_=Cache::No, Cache ArrayCache_=Cache::No, Cache FunctionCache_=Cache::No)
Definition: ItaniumDemangle.h:144
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:163
llvm::AllocatorList::pop_front
void pop_front()
Definition: AllocatorList.h:208
llvm::AllocatorList::rbegin
reverse_iterator rbegin()
Definition: AllocatorList.h:166
llvm::AllocatorList::emplace
iterator emplace(iterator I, Ts &&... Vs)
Definition: AllocatorList.h:180
llvm::AllocatorList::begin
const_iterator begin() const
Definition: AllocatorList.h:164
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:165
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::AllocatorList
A linked-list with a custom, local allocator.
Definition: AllocatorList.h:34
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:1556
llvm::AllocatorList::rend
reverse_iterator rend()
Definition: AllocatorList.h:167
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:944
llvm::AllocatorList::AllocatorList
AllocatorList(AllocatorList &&X)
Definition: AllocatorList.h:133
llvm::AllocatorList::front
const T & front() const
Definition: AllocatorList.h:178
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2159
llvm::AllocatorList< Token >::pointer
Token * pointer
Definition: AllocatorList.h:79
llvm::AllocatorList< Token >::const_pointer
const Token * const_pointer
Definition: AllocatorList.h:81
llvm::AllocatorList::empty
bool empty()
Definition: AllocatorList.h:159
ValueT
llvm::AllocatorList::insert
iterator insert(iterator I, T &&V)
Definition: AllocatorList.h:184
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:83
llvm::AllocatorList< Token >::difference_type
typename list_type::difference_type difference_type
Definition: AllocatorList.h:84
llvm::ilist_node
Definition: ilist_node.h:148
llvm::AllocatorList::clear
void clear()
Definition: AllocatorList.h:206
llvm::AllocatorList::push_back
void push_back(const T &V)
Definition: AllocatorList.h:211
std
Definition: BitVector.h:941
llvm::AllocatorList::rbegin
const_reverse_iterator rbegin() const
Definition: AllocatorList.h:168
llvm::AllocatorList::push_front
void push_front(T &&V)
Definition: AllocatorList.h:210
llvm::AllocatorList::size
size_t size()
Definition: AllocatorList.h:160
llvm::AllocatorList< Token >::value_type
Token value_type
Definition: AllocatorList.h:78
llvm::AllocatorList::push_front
void push_front(const T &V)
Definition: AllocatorList.h:212
llvm::AllocatorList::insert
iterator insert(iterator I, const T &V)
Definition: AllocatorList.h:187
llvm::AllocatorList::back
const T & back() const
Definition: AllocatorList.h:177
List
const NodeList & List
Definition: RDFGraph.cpp:201
llvm::AllocatorList::emplace_back
void emplace_back(Ts &&... Vs)
Definition: AllocatorList.h:213
N
#define N
llvm::AllocatorList::AllocatorList
AllocatorList()=default
llvm::AllocatorList::pop_back
void pop_back()
Definition: AllocatorList.h:207
simple_ilist.h
llvm::simple_ilist< Node >
ilist_node.h
llvm::AllocatorList::operator=
AllocatorList & operator=(AllocatorList &&X)
Definition: AllocatorList.h:140
llvm::AllocatorList< Token >::const_reference
const Token & const_reference
Definition: AllocatorList.h:82
llvm::AllocatorList< Token >::reverse_iterator
IteratorImpl< Token, typename list_type::reverse_iterator > reverse_iterator
Definition: AllocatorList.h:126
llvm::AllocatorList< Token >::const_reverse_iterator
IteratorImpl< const Token, typename list_type::const_reverse_iterator > const_reverse_iterator
Definition: AllocatorList.h:130
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:379
llvm::AllocatorList::rend
const_reverse_iterator rend() const
Definition: AllocatorList.h:171
llvm::AllocatorList::back
T & back()
Definition: AllocatorList.h:175
llvm::AllocatorList::push_back
void push_back(T &&V)
Definition: AllocatorList.h:209
llvm::AllocatorList::operator=
AllocatorList & operator=(const AllocatorList &X)
Definition: AllocatorList.h:147
llvm::AllocatorList::emplace_front
void emplace_front(Ts &&... Vs)
Definition: AllocatorList.h:216