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
23namespace 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.
34template <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
47 using list_type = simple_ilist<Node>;
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 {
59 AllocatorList &AL;
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 {
67 AllocatorList &AL;
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
77public:
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;
84 using difference_type = typename list_type::difference_type;
85
86private:
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 =
97 iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,
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
123public:
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;
133 AllocatorList(AllocatorList &&X)
134 : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
135
136 AllocatorList(const AllocatorList &X) {
137 List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
138 }
139
140 AllocatorList &operator=(AllocatorList &&X) {
141 clear(); // Dispose of current nodes explicitly.
142 List = std::move(X.List);
143 getAlloc() = std::move(X.getAlloc());
144 return *this;
145 }
146
147 AllocatorList &operator=(const AllocatorList &X) {
148 List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
149 return *this;
150 }
151
152 ~AllocatorList() { clear(); }
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()); }
166 reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
167 reverse_iterator rend() { return reverse_iterator(List.rend()); }
168 const_reverse_iterator rbegin() const {
169 return const_reverse_iterator(List.rbegin());
170 }
171 const_reverse_iterator rend() const {
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
184 iterator insert(iterator I, T &&V) {
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
197 iterator erase(iterator I) {
198 return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
199 }
200
201 iterator erase(iterator First, iterator Last) {
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
229template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
230
231} // end namespace llvm
232
233#endif // LLVM_ADT_ALLOCATORLIST_H
234