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
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
46 using list_type = simple_ilist<Node>;
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 &;
82 using size_type = typename list_type::size_type;
83 using difference_type = typename list_type::difference_type;
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 =
96 iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,
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>;
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;
132 AllocatorList(AllocatorList &&X)
133 : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
134
135 AllocatorList(const AllocatorList &X) {
136 List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
137 }
138
139 AllocatorList &operator=(AllocatorList &&X) {
140 clear(); // Dispose of current nodes explicitly.
141 List = std::move(X.List);
142 getAlloc() = std::move(X.getAlloc());
143 return *this;
144 }
145
146 AllocatorList &operator=(const AllocatorList &X) {
147 List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
148 return *this;
149 }
150
151 ~AllocatorList() { clear(); }
152
153 void swap(AllocatorList &RHS) {
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()); }
165 reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
166 reverse_iterator rend() { return reverse_iterator(List.rend()); }
167 const_reverse_iterator rbegin() const {
168 return const_reverse_iterator(List.rbegin());
169 }
170 const_reverse_iterator rend() const {
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
183 iterator insert(iterator I, T &&V) {
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
196 iterator erase(iterator I) {
197 return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
198 }
199
200 iterator erase(iterator First, iterator Last) {
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
228template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
229
230} // end namespace llvm
231
232#endif // LLVM_ADT_ALLOCATORLIST_H
233

source code of llvm/include/llvm/ADT/AllocatorList.h