LLVM 17.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"
16#include <cassert>
17#include <cstddef>
18#include <iterator>
19#include <type_traits>
20#include <utility>
21
22namespace 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.
33template <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 {
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
76public:
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 &;
84
85private:
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
122public:
123 using iterator = IteratorImpl<T, typename list_type::iterator>;
125 IteratorImpl<T, typename list_type::reverse_iterator>;
127 IteratorImpl<const T, typename list_type::const_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 }
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
This file defines the BumpPtrAllocator interface.
Given that RA is a live value
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define I(x, y, z)
Definition: MD5.cpp:58
#define T
const NodeList & List
Definition: RDFGraph.cpp:199
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
A linked-list with a custom, local allocator.
Definition: AllocatorList.h:33
void emplace_back(Ts &&... Vs)
const_iterator end() const
AllocatorList(AllocatorList &&X)
void insert(iterator I, Iterator First, Iterator Last)
const T & back() const
const_reverse_iterator rend() const
void push_back(T &&V)
typename list_type::size_type size_type
Definition: AllocatorList.h:82
iterator erase(iterator First, iterator Last)
const_iterator begin() const
AllocatorList & operator=(const AllocatorList &X)
void push_back(const T &V)
IteratorImpl< T, typename list_type::reverse_iterator > reverse_iterator
IteratorImpl< const T, typename list_type::const_reverse_iterator > const_reverse_iterator
IteratorImpl< const T, typename list_type::const_iterator > const_iterator
void emplace_front(Ts &&... Vs)
AllocatorList()=default
iterator erase(iterator I)
iterator emplace(iterator I, Ts &&... Vs)
iterator insert(iterator I, T &&V)
void resetAlloc()
Reset the underlying allocator.
const_reverse_iterator rbegin() const
IteratorImpl< T, typename list_type::iterator > iterator
typename list_type::difference_type difference_type
Definition: AllocatorList.h:83
reverse_iterator rend()
const T & front() const
void push_front(const T &V)
AllocatorList & operator=(AllocatorList &&X)
iterator insert(iterator I, const T &V)
void push_front(T &&V)
AllocatorList(const AllocatorList &X)
void swap(AllocatorList &RHS)
reverse_iterator rbegin()
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:237
This file defines the ilist_node class template, which is a convenient base class for creating classe...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2162
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:1862
Definition: BitVector.h:851
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
#define N