Line data Source code
1 : //===- llvm/ADT/AllocatorList.h - Custom allocator list ---------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #ifndef LLVM_ADT_ALLOCATORLIST_H
11 : #define LLVM_ADT_ALLOCATORLIST_H
12 :
13 : #include "llvm/ADT/ilist_node.h"
14 : #include "llvm/ADT/iterator.h"
15 : #include "llvm/ADT/simple_ilist.h"
16 : #include "llvm/Support/Allocator.h"
17 : #include <algorithm>
18 : #include <cassert>
19 : #include <cstddef>
20 : #include <iterator>
21 : #include <type_traits>
22 : #include <utility>
23 :
24 : namespace llvm {
25 :
26 : /// A linked-list with a custom, local allocator.
27 : ///
28 : /// Expose a std::list-like interface that owns and uses a custom LLVM-style
29 : /// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the
30 : /// implementation details.
31 : ///
32 : /// Because this list owns the allocator, calling \a splice() with a different
33 : /// list isn't generally safe. As such, \a splice has been left out of the
34 : /// interface entirely.
35 : template <class T, class AllocatorT> class AllocatorList : AllocatorT {
36 4 : struct Node : ilist_node<Node> {
37 : Node(Node &&) = delete;
38 : Node(const Node &) = delete;
39 : Node &operator=(Node &&) = delete;
40 : Node &operator=(const Node &) = delete;
41 :
42 40 : Node(T &&V) : V(std::move(V)) {}
43 1623410 : Node(const T &V) : V(V) {}
44 10 : template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {}
45 : T V;
46 : };
47 :
48 : using list_type = simple_ilist<Node>;
49 :
50 : list_type List;
51 :
52 2350652 : AllocatorT &getAlloc() { return *this; }
53 : const AllocatorT &getAlloc() const { return *this; }
54 :
55 24 : template <class... ArgTs> Node *create(ArgTs &&... Args) {
56 1623409 : return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);
57 : }
58 :
59 : struct Cloner {
60 : AllocatorList &AL;
61 :
62 2 : Cloner(AllocatorList &AL) : AL(AL) {}
63 :
64 0 : Node *operator()(const Node &N) const { return AL.create(N.V); }
65 : };
66 :
67 : struct Disposer {
68 : AllocatorList &AL;
69 :
70 1 : Disposer(AllocatorList &AL) : AL(AL) {}
71 :
72 0 : void operator()(Node *N) const {
73 : N->~Node();
74 : AL.getAlloc().Deallocate(N);
75 0 : }
76 0 : };
77 :
78 : public:
79 0 : using value_type = T;
80 0 : using pointer = T *;
81 : using reference = T &;
82 : using const_pointer = const T *;
83 0 : using const_reference = const T &;
84 0 : using size_type = typename list_type::size_type;
85 : using difference_type = typename list_type::difference_type;
86 :
87 0 : private:
88 0 : template <class ValueT, class IteratorBase>
89 : class IteratorImpl
90 : : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,
91 0 : IteratorBase,
92 : std::bidirectional_iterator_tag, ValueT> {
93 : template <class OtherValueT, class OtherIteratorBase>
94 : friend class IteratorImpl;
95 : friend AllocatorList;
96 :
97 : using base_type =
98 : iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,
99 : std::bidirectional_iterator_tag, ValueT>;
100 :
101 : public:
102 : using value_type = ValueT;
103 : using pointer = ValueT *;
104 : using reference = ValueT &;
105 :
106 : IteratorImpl() = default;
107 : IteratorImpl(const IteratorImpl &) = default;
108 : IteratorImpl &operator=(const IteratorImpl &) = default;
109 :
110 : explicit IteratorImpl(const IteratorBase &I) : base_type(I) {}
111 :
112 : template <class OtherValueT, class OtherIteratorBase>
113 : IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X,
114 : typename std::enable_if<std::is_convertible<
115 : OtherIteratorBase, IteratorBase>::value>::type * = nullptr)
116 : : base_type(X.wrapped()) {}
117 :
118 : ~IteratorImpl() = default;
119 :
120 : reference operator*() const { return base_type::wrapped()->V; }
121 : pointer operator->() const { return &operator*(); }
122 :
123 : friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) {
124 0 : return L.wrapped() == R.wrapped();
125 : }
126 : friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) {
127 : return !(L == R);
128 : }
129 : };
130 :
131 : public:
132 : using iterator = IteratorImpl<T, typename list_type::iterator>;
133 : using reverse_iterator =
134 : IteratorImpl<T, typename list_type::reverse_iterator>;
135 : using const_iterator =
136 20 : IteratorImpl<const T, typename list_type::const_iterator>;
137 : using const_reverse_iterator =
138 : IteratorImpl<const T, typename list_type::const_reverse_iterator>;
139 :
140 4 : AllocatorList() = default;
141 : AllocatorList(AllocatorList &&X)
142 : : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}
143 :
144 : AllocatorList(const AllocatorList &X) {
145 : List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
146 : }
147 :
148 : AllocatorList &operator=(AllocatorList &&X) {
149 : clear(); // Dispose of current nodes explicitly.
150 : List = std::move(X.List);
151 : getAlloc() = std::move(X.getAlloc());
152 : return *this;
153 : }
154 :
155 : AllocatorList &operator=(const AllocatorList &X) {
156 : List.cloneFrom(X.List, Cloner(*this), Disposer(*this));
157 : return *this;
158 : }
159 :
160 8858 : ~AllocatorList() { clear(); }
161 :
162 : void swap(AllocatorList &RHS) {
163 : List.swap(RHS.List);
164 2 : std::swap(getAlloc(), RHS.getAlloc());
165 : }
166 :
167 2 : bool empty() { return List.empty(); }
168 2 : size_t size() { return List.size(); }
169 :
170 1 : iterator begin() { return iterator(List.begin()); }
171 : iterator end() { return iterator(List.end()); }
172 : const_iterator begin() const { return const_iterator(List.begin()); }
173 1 : const_iterator end() const { return const_iterator(List.end()); }
174 1 : reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }
175 : reverse_iterator rend() { return reverse_iterator(List.rend()); }
176 1 : const_reverse_iterator rbegin() const {
177 : return const_reverse_iterator(List.rbegin());
178 : }
179 1 : const_reverse_iterator rend() const {
180 1 : return const_reverse_iterator(List.rend());
181 : }
182 :
183 : T &back() { return List.back().V; }
184 5206780 : T &front() { return List.front().V; }
185 : const T &back() const { return List.back().V; }
186 : const T &front() const { return List.front().V; }
187 :
188 38 : template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {
189 : return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));
190 : }
191 :
192 1 : iterator insert(iterator I, T &&V) {
193 24 : return iterator(List.insert(I.wrapped(), *create(std::move(V))));
194 : }
195 1623409 : iterator insert(iterator I, const T &V) {
196 1623409 : return iterator(List.insert(I.wrapped(), *create(V)));
197 : }
198 :
199 : template <class Iterator>
200 : void insert(iterator I, Iterator First, Iterator Last) {
201 : for (; First != Last; ++First)
202 : List.insert(I.wrapped(), *create(*First));
203 : }
204 :
205 : iterator erase(iterator I) {
206 : return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));
207 : }
208 :
209 : iterator erase(iterator First, iterator Last) {
210 : return iterator(
211 5 : List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));
212 8 : }
213 :
214 : void clear() { List.clearAndDispose(Disposer(*this)); }
215 : void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }
216 1618841 : void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }
217 10 : void push_back(T &&V) { insert(end(), std::move(V)); }
218 : void push_front(T &&V) { insert(begin(), std::move(V)); }
219 1284416 : void push_back(const T &V) { insert(end(), V); }
220 16 : void push_front(const T &V) { insert(begin(), V); }
221 16 : template <class... Ts> void emplace_back(Ts &&... Vs) {
222 : emplace(end(), std::forward<Ts>(Vs)...);
223 6 : }
224 6 : template <class... Ts> void emplace_front(Ts &&... Vs) {
225 : emplace(begin(), std::forward<Ts>(Vs)...);
226 10 : }
227 10 :
228 : /// Reset the underlying allocator.
229 10 : ///
230 10 : /// \pre \c empty()
231 : void resetAlloc() {
232 0 : assert(empty() && "Cannot reset allocator if not empty");
233 727206 : getAlloc().Reset();
234 : }
235 10 : };
236 10 :
237 : template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;
238 :
239 : } // end namespace llvm
240 2 :
241 12 : #endif // LLVM_ADT_ALLOCATORLIST_H
|
