/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/AllocatorList.h
Line | Count | Source |
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 | | 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 | 23 | Node(T &&V) : V(std::move(V)) {} |
43 | 647k | Node(const T &V) : V(V) {} |
44 | | 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 | 1.52M | AllocatorT &getAlloc() { return *this; } |
53 | | const AllocatorT &getAlloc() const { return *this; } |
54 | | |
55 | 647k | template <class... ArgTs> Node *create(ArgTs &&... Args) { |
56 | 647k | return new (getAlloc()) Node(std::forward<ArgTs>(Args)...); |
57 | 647k | } llvm::AllocatorList<llvm::yaml::Token, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >::Node* llvm::AllocatorList<llvm::yaml::Token, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >::create<llvm::yaml::Token>(llvm::yaml::Token&&) Line | Count | Source | 55 | 23 | template <class... ArgTs> Node *create(ArgTs &&... Args) { | 56 | 23 | return new (getAlloc()) Node(std::forward<ArgTs>(Args)...); | 57 | 23 | } |
llvm::AllocatorList<llvm::yaml::Token, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >::Node* llvm::AllocatorList<llvm::yaml::Token, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >::create<llvm::yaml::Token const&>(llvm::yaml::Token const&&&) Line | Count | Source | 55 | 647k | template <class... ArgTs> Node *create(ArgTs &&... Args) { | 56 | 647k | return new (getAlloc()) Node(std::forward<ArgTs>(Args)...); | 57 | 647k | } |
|
58 | | |
59 | | struct Cloner { |
60 | | AllocatorList &AL; |
61 | | |
62 | | Cloner(AllocatorList &AL) : AL(AL) {} |
63 | | |
64 | | Node *operator()(const Node &N) const { return AL.create(N.V); } |
65 | | }; |
66 | | |
67 | | struct Disposer { |
68 | | AllocatorList &AL; |
69 | | |
70 | 647k | Disposer(AllocatorList &AL) : AL(AL) {} |
71 | | |
72 | 647k | void operator()(Node *N) const { |
73 | 647k | N->~Node(); |
74 | 647k | AL.getAlloc().Deallocate(N); |
75 | 647k | } |
76 | | }; |
77 | | |
78 | | public: |
79 | | using value_type = T; |
80 | | using pointer = T *; |
81 | | using reference = T &; |
82 | | using const_pointer = const T *; |
83 | | using const_reference = const T &; |
84 | | using size_type = typename list_type::size_type; |
85 | | using difference_type = typename list_type::difference_type; |
86 | | |
87 | | private: |
88 | | template <class ValueT, class IteratorBase> |
89 | | class IteratorImpl |
90 | | : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, |
91 | | 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 | 2.72M | IteratorImpl() = default; |
107 | | IteratorImpl(const IteratorImpl &) = default; |
108 | | IteratorImpl &operator=(const IteratorImpl &) = default; |
109 | | |
110 | 4.00M | 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 | 124k | reference operator*() const { return base_type::wrapped()->V; } |
121 | 124k | pointer operator->() const { return &operator*(); } |
122 | | |
123 | 945k | friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) { |
124 | 945k | return L.wrapped() == R.wrapped(); |
125 | 945k | } |
126 | 300k | friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) { |
127 | 300k | return !(L == R); |
128 | 300k | } |
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 | | 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 | 2.53k | 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 | 2.49k | ~AllocatorList() { clear(); } |
161 | | |
162 | | void swap(AllocatorList &RHS) { |
163 | | List.swap(RHS.List); |
164 | | std::swap(getAlloc(), RHS.getAlloc()); |
165 | | } |
166 | | |
167 | 3.61M | bool empty() { return List.empty(); } |
168 | | size_t size() { return List.size(); } |
169 | | |
170 | 2.45M | iterator begin() { return iterator(List.begin()); } |
171 | 902k | iterator end() { return iterator(List.end()); } |
172 | | const_iterator begin() const { return const_iterator(List.begin()); } |
173 | | const_iterator end() const { return const_iterator(List.end()); } |
174 | | reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); } |
175 | | reverse_iterator rend() { return reverse_iterator(List.rend()); } |
176 | | const_reverse_iterator rbegin() const { |
177 | | return const_reverse_iterator(List.rbegin()); |
178 | | } |
179 | | const_reverse_iterator rend() const { |
180 | | return const_reverse_iterator(List.rend()); |
181 | | } |
182 | | |
183 | | T &back() { return List.back().V; } |
184 | 2.09M | 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 | | template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) { |
189 | | return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...))); |
190 | | } |
191 | | |
192 | 23 | iterator insert(iterator I, T &&V) { |
193 | 23 | return iterator(List.insert(I.wrapped(), *create(std::move(V)))); |
194 | 23 | } |
195 | 647k | iterator insert(iterator I, const T &V) { |
196 | 647k | return iterator(List.insert(I.wrapped(), *create(V))); |
197 | 647k | } |
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 | | List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this))); |
212 | | } |
213 | | |
214 | 2.51k | void clear() { List.clearAndDispose(Disposer(*this)); } |
215 | | void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); } |
216 | 644k | void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); } |
217 | 23 | void push_back(T &&V) { insert(end(), std::move(V)); } |
218 | | void push_front(T &&V) { insert(begin(), std::move(V)); } |
219 | 493k | void push_back(const T &V) { insert(end(), V); } |
220 | | void push_front(const T &V) { insert(begin(), V); } |
221 | | template <class... Ts> void emplace_back(Ts &&... Vs) { |
222 | | emplace(end(), std::forward<Ts>(Vs)...); |
223 | | } |
224 | | template <class... Ts> void emplace_front(Ts &&... Vs) { |
225 | | emplace(begin(), std::forward<Ts>(Vs)...); |
226 | | } |
227 | | |
228 | | /// Reset the underlying allocator. |
229 | | /// |
230 | | /// \pre \c empty() |
231 | 235k | void resetAlloc() { |
232 | 235k | assert(empty() && "Cannot reset allocator if not empty"); |
233 | 235k | getAlloc().Reset(); |
234 | 235k | } |
235 | | }; |
236 | | |
237 | | template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>; |
238 | | |
239 | | } // end namespace llvm |
240 | | |
241 | | #endif // LLVM_ADT_ALLOCATORLIST_H |