LLVM  10.0.0svn
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  typename std::enable_if<std::is_convertible<
114  OtherIteratorBase, IteratorBase>::value>::type * = 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  friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) {
123  return L.wrapped() == R.wrapped();
124  }
125  friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) {
126  return !(L == R);
127  }
128  };
129 
130 public:
131  using iterator = IteratorImpl<T, typename list_type::iterator>;
132  using reverse_iterator =
133  IteratorImpl<T, typename list_type::reverse_iterator>;
134  using const_iterator =
135  IteratorImpl<const T, typename list_type::const_iterator>;
136  using const_reverse_iterator =
137  IteratorImpl<const T, typename list_type::const_reverse_iterator>;
138 
139  AllocatorList() = default;
141  : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
142 
144  List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
145  }
146 
148  clear(); // Dispose of current nodes explicitly.
149  List = std::move(X.List);
150  getAlloc() = std::move(X.getAlloc());
151  return *this;
152  }
153 
155  List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
156  return *this;
157  }
158 
160 
161  void swap(AllocatorList &RHS) {
162  List.swap(RHS.List);
163  std::swap(getAlloc(), RHS.getAlloc());
164  }
165 
166  bool empty() { return List.empty(); }
167  size_t size() { return List.size(); }
168 
169  iterator begin() { return iterator(List.begin()); }
170  iterator end() { return iterator(List.end()); }
171  const_iterator begin() const { return const_iterator(List.begin()); }
172  const_iterator end() const { return const_iterator(List.end()); }
176  return const_reverse_iterator(List.rbegin());
177  }
179  return const_reverse_iterator(List.rend());
180  }
181 
182  T &back() { return List.back().V; }
183  T &front() { return List.front().V; }
184  const T &back() const { return List.back().V; }
185  const T &front() const { return List.front().V; }
186 
187  template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
188  return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
189  }
190 
192  return iterator(List.insert(I.wrapped(), *create(std::move(V))));
193  }
194  iterator insert(iterator I, const T &V) {
195  return iterator(List.insert(I.wrapped(), *create(V)));
196  }
197 
198  template <class Iterator>
199  void insert(iterator I, Iterator First, Iterator Last) {
200  for (; First != Last; ++First)
201  List.insert(I.wrapped(), *create(*First));
202  }
203 
205  return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
206  }
207 
209  return iterator(
210  List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
211  }
212 
213  void clear() { List.clearAndDispose(Disposer(*this)); }
214  void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
215  void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
216  void push_back(T &&V) { insert(end(), std::move(V)); }
217  void push_front(T &&V) { insert(begin(), std::move(V)); }
218  void push_back(const T &V) { insert(end(), V); }
219  void push_front(const T &V) { insert(begin(), V); }
220  template <class... Ts> void emplace_back(Ts &&... Vs) {
221  emplace(end(), std::forward<Ts>(Vs)...);
222  }
223  template <class... Ts> void emplace_front(Ts &&... Vs) {
224  emplace(begin(), std::forward<Ts>(Vs)...);
225  }
226 
227  /// Reset the underlying allocator.
228  ///
229  /// \pre \c empty()
230  void resetAlloc() {
231  assert(empty() && "Cannot reset allocator if not empty");
232  getAlloc().Reset();
233  }
234 };
235 
237 
238 } // end namespace llvm
239 
240 #endif // LLVM_ADT_ALLOCATORLIST_H
reverse_iterator rend()
void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose)
Clone another list.
Definition: simple_ilist.h:173
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
AllocatorList & operator=(AllocatorList &&X)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A linked-list with a custom, local allocator.
Definition: AllocatorList.h:34
void swap(simple_ilist &X)
Swap with another list in place using std::swap.
Definition: simple_ilist.h:156
void push_front(T &&V)
void emplace_front(Ts &&... Vs)
void push_front(const T &V)
const T & front() const
void insert(iterator I, Iterator First, Iterator Last)
void resetAlloc()
Reset the underlying allocator.
Node(Kind K_, Cache RHSComponentCache_=Cache::No, Cache ArrayCache_=Cache::No, Cache FunctionCache_=Cache::No)
const_iterator end() const
const T & back() const
reference back()
Definition: simple_ilist.h:140
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
void push_back(T &&V)
Definition: BitVector.h:937
iterator erase(iterator I)
AllocatorList()=default
const_iterator begin() const
void emplace_back(Ts &&... Vs)
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2097
IteratorImpl< Token, typename list_type::reverse_iterator > reverse_iterator
const_reverse_iterator rend() const
AllocatorList & operator=(const AllocatorList &X)
const_reverse_iterator rbegin() const
IteratorImpl< Token, typename list_type::iterator > iterator
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:205
iterator eraseAndDispose(iterator I, Disposer dispose)
Remove a node by iterator and dispose of it.
Definition: simple_ilist.h:212
reverse_iterator rend()
Definition: simple_ilist.h:125
LLVM_NODISCARD size_type size() const
Calculate the size of the list in linear time.
Definition: simple_ilist.h:134
typename list_type::size_type size_type
Definition: AllocatorList.h:83
AllocatorList(AllocatorList &&X)
iterator erase(iterator First, iterator Last)
iterator insert(iterator I, T &&V)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
iterator insert(iterator I, const T &V)
LLVM_NODISCARD bool empty() const
Check if the list is empty in constant time.
Definition: simple_ilist.h:131
void clearAndDispose(Disposer dispose)
Clear the list and dispose of the nodes.
Definition: simple_ilist.h:233
AllocatorList(const AllocatorList &X)
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1975
void swap(AllocatorList &RHS)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
IteratorImpl< const Token, typename list_type::const_reverse_iterator > const_reverse_iterator
reference front()
Definition: simple_ilist.h:138
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:159
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
iterator emplace(iterator I, Ts &&... Vs)
IteratorImpl< const Token, typename list_type::const_iterator > const_iterator
reverse_iterator rbegin()
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1973
typename list_type::difference_type difference_type
Definition: AllocatorList.h:84
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
reverse_iterator rbegin()
Definition: simple_ilist.h:121
void push_back(const T &V)