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 | |
22 | namespace 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. |
33 | template <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 | |
76 | public: |
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 | |
85 | private: |
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 | |
122 | public: |
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 | |
228 | template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>; |
229 | |
230 | } // end namespace llvm |
231 | |
232 | #endif // LLVM_ADT_ALLOCATORLIST_H |
233 | |