/home/arjun/llvm-project/llvm/include/llvm/ADT/AllocatorList.h
Line | Count | Source (jump to first uncovered line) |
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 | | |
23 | | namespace 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. |
34 | | template <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 | 0 | Node(T &&V) : V(std::move(V)) {} |
42 | 0 | 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 | 0 | AllocatorT &getAlloc() { return *this; } |
52 | | const AllocatorT &getAlloc() const { return *this; } |
53 | | |
54 | 0 | template <class... ArgTs> Node *create(ArgTs &&... Args) { |
55 | 0 | return new (getAlloc()) Node(std::forward<ArgTs>(Args)...); |
56 | 0 | } Unexecuted instantiation: _ZN4llvm13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE6createIJS2_EEEPNS6_4NodeEDpOT_ Unexecuted instantiation: _ZN4llvm13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE6createIJRKS2_EEEPNS6_4NodeEDpOT_ |
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 | 0 | Disposer(AllocatorList &AL) : AL(AL) {} |
70 | | |
71 | 0 | void operator()(Node *N) const { |
72 | 0 | N->~Node(); |
73 | 0 | AL.getAlloc().Deallocate(N); |
74 | 0 | } |
75 | | }; |
76 | | |
77 | | public: |
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 | | |
86 | | private: |
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 | 0 | IteratorImpl() = default; |
106 | | IteratorImpl(const IteratorImpl &) = default; |
107 | | IteratorImpl &operator=(const IteratorImpl &) = default; |
108 | | |
109 | 0 | 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 | 0 | reference operator*() const { return base_type::wrapped()->V; } |
120 | 0 | pointer operator->() const { return &operator*(); } |
121 | | |
122 | 0 | friend bool operator==(const IteratorImpl &L, const IteratorImpl &R) { |
123 | 0 | return L.wrapped() == R.wrapped(); |
124 | 0 | } |
125 | 0 | friend bool operator!=(const IteratorImpl &L, const IteratorImpl &R) { |
126 | 0 | return !(L == R); |
127 | 0 | } |
128 | | }; |
129 | | |
130 | | public: |
131 | | using iterator = IteratorImpl<T, typename list_type::iterator>; |
132 | | using reverse_iterator = |
133 | | IteratorImpl<T, typename list_type::reverse_iterator>; |
134 | | using const_iterator = |
135 | | IteratorImpl<const T, typename list_type::const_iterator>; |
136 | | using const_reverse_iterator = |
137 | | IteratorImpl<const T, typename list_type::const_reverse_iterator>; |
138 | | |
139 | 0 | AllocatorList() = default; |
140 | | AllocatorList(AllocatorList &&X) |
141 | | : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {} |
142 | | |
143 | | AllocatorList(const AllocatorList &X) { |
144 | | List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); |
145 | | } |
146 | | |
147 | | AllocatorList &operator=(AllocatorList &&X) { |
148 | | clear(); // Dispose of current nodes explicitly. |
149 | | List = std::move(X.List); |
150 | | getAlloc() = std::move(X.getAlloc()); |
151 | | return *this; |
152 | | } |
153 | | |
154 | | AllocatorList &operator=(const AllocatorList &X) { |
155 | | List.cloneFrom(X.List, Cloner(*this), Disposer(*this)); |
156 | | return *this; |
157 | | } |
158 | | |
159 | 0 | ~AllocatorList() { clear(); } |
160 | | |
161 | | void swap(AllocatorList &RHS) { |
162 | | List.swap(RHS.List); |
163 | | std::swap(getAlloc(), RHS.getAlloc()); |
164 | | } |
165 | | |
166 | 0 | bool empty() { return List.empty(); } |
167 | | size_t size() { return List.size(); } |
168 | | |
169 | 0 | iterator begin() { return iterator(List.begin()); } |
170 | 0 | iterator end() { return iterator(List.end()); } |
171 | | const_iterator begin() const { return const_iterator(List.begin()); } |
172 | | const_iterator end() const { return const_iterator(List.end()); } |
173 | | reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); } |
174 | | reverse_iterator rend() { return reverse_iterator(List.rend()); } |
175 | | const_reverse_iterator rbegin() const { |
176 | | return const_reverse_iterator(List.rbegin()); |
177 | | } |
178 | | const_reverse_iterator rend() const { |
179 | | return const_reverse_iterator(List.rend()); |
180 | | } |
181 | | |
182 | | T &back() { return List.back().V; } |
183 | 0 | T &front() { return List.front().V; } |
184 | | const T &back() const { return List.back().V; } |
185 | | const T &front() const { return List.front().V; } |
186 | | |
187 | | template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) { |
188 | | return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...))); |
189 | | } |
190 | | |
191 | 0 | iterator insert(iterator I, T &&V) { |
192 | 0 | return iterator(List.insert(I.wrapped(), *create(std::move(V)))); |
193 | 0 | } |
194 | 0 | iterator insert(iterator I, const T &V) { |
195 | 0 | return iterator(List.insert(I.wrapped(), *create(V))); |
196 | 0 | } |
197 | | |
198 | | template <class Iterator> |
199 | | void insert(iterator I, Iterator First, Iterator Last) { |
200 | | for (; First != Last; ++First) |
201 | | List.insert(I.wrapped(), *create(*First)); |
202 | | } |
203 | | |
204 | | iterator erase(iterator I) { |
205 | | return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this))); |
206 | | } |
207 | | |
208 | | iterator erase(iterator First, iterator Last) { |
209 | | return iterator( |
210 | | List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this))); |
211 | | } |
212 | | |
213 | 0 | void clear() { List.clearAndDispose(Disposer(*this)); } |
214 | | void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); } |
215 | 0 | void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); } |
216 | 0 | void push_back(T &&V) { insert(end(), std::move(V)); } |
217 | | void push_front(T &&V) { insert(begin(), std::move(V)); } |
218 | 0 | void push_back(const T &V) { insert(end(), V); } |
219 | | void push_front(const T &V) { insert(begin(), V); } |
220 | | template <class... Ts> void emplace_back(Ts &&... Vs) { |
221 | | emplace(end(), std::forward<Ts>(Vs)...); |
222 | | } |
223 | | template <class... Ts> void emplace_front(Ts &&... Vs) { |
224 | | emplace(begin(), std::forward<Ts>(Vs)...); |
225 | | } |
226 | | |
227 | | /// Reset the underlying allocator. |
228 | | /// |
229 | | /// \pre \c empty() |
230 | 0 | void resetAlloc() { |
231 | 0 | assert(empty() && "Cannot reset allocator if not empty"); |
232 | 0 | getAlloc().Reset(); |
233 | 0 | } |
234 | | }; |
235 | | |
236 | | template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>; |
237 | | |
238 | | } // end namespace llvm |
239 | | |
240 | | #endif // LLVM_ADT_ALLOCATORLIST_H |