1 | //===- llvm/ADT/simple_ilist.h - Simple Intrusive 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_SIMPLE_ILIST_H |
10 | #define LLVM_ADT_SIMPLE_ILIST_H |
11 | |
12 | #include "llvm/ADT/ilist_base.h" |
13 | #include "llvm/ADT/ilist_iterator.h" |
14 | #include "llvm/ADT/ilist_node.h" |
15 | #include "llvm/ADT/ilist_node_options.h" |
16 | #include "llvm/Support/Compiler.h" |
17 | #include <algorithm> |
18 | #include <cassert> |
19 | #include <cstddef> |
20 | #include <functional> |
21 | #include <iterator> |
22 | #include <utility> |
23 | |
24 | namespace llvm { |
25 | |
26 | /// A simple intrusive list implementation. |
27 | /// |
28 | /// This is a simple intrusive list for a \c T that inherits from \c |
29 | /// ilist_node<T>. The list never takes ownership of anything inserted in it. |
30 | /// |
31 | /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never deletes |
32 | /// values, and has no callback traits. |
33 | /// |
34 | /// The API for adding nodes include \a push_front(), \a push_back(), and \a |
35 | /// insert(). These all take values by reference (not by pointer), except for |
36 | /// the range version of \a insert(). |
37 | /// |
38 | /// There are three sets of API for discarding nodes from the list: \a |
39 | /// remove(), which takes a reference to the node to remove, \a erase(), which |
40 | /// takes an iterator or iterator range and returns the next one, and \a |
41 | /// clear(), which empties out the container. All three are constant time |
42 | /// operations. None of these deletes any nodes; in particular, if there is a |
43 | /// single node in the list, then these have identical semantics: |
44 | /// \li \c L.remove(L.front()); |
45 | /// \li \c L.erase(L.begin()); |
46 | /// \li \c L.clear(); |
47 | /// |
48 | /// As a convenience for callers, there are parallel APIs that take a \c |
49 | /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a |
50 | /// eraseAndDispose(), and \a clearAndDispose(). These have different names |
51 | /// because the extra semantic is otherwise non-obvious. They are equivalent |
52 | /// to calling \a std::for_each() on the range to be discarded. |
53 | /// |
54 | /// The currently available \p Options customize the nodes in the list. The |
55 | /// same options must be specified in the \a ilist_node instantiation for |
56 | /// compatibility (although the order is irrelevant). |
57 | /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this |
58 | /// list should use. This is useful if a type \p T is part of multiple, |
59 | /// independent lists simultaneously. |
60 | /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a |
61 | /// node is a sentinel. Specifying \c true enables the \a |
62 | /// ilist_node::isSentinel() API. Unlike \a ilist_node::isKnownSentinel(), |
63 | /// which is only appropriate for assertions, \a ilist_node::isSentinel() is |
64 | /// appropriate for real logic. |
65 | /// |
66 | /// Here are examples of \p Options usage: |
67 | /// \li \c simple_ilist<T> gives the defaults. \li \c |
68 | /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a |
69 | /// ilist_node::isSentinel() API. |
70 | /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>> |
71 | /// specifies a tag of A and that tracking should be off (even when |
72 | /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled). |
73 | /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is |
74 | /// equivalent to the last. |
75 | /// |
76 | /// See \a is_valid_option for steps on adding a new option. |
77 | template <typename T, class... Options> |
78 | class simple_ilist |
79 | : ilist_detail::compute_node_options<T, Options...>::type::list_base_type, |
80 | ilist_detail::SpecificNodeAccess< |
81 | typename ilist_detail::compute_node_options<T, Options...>::type> { |
82 | static_assert(ilist_detail::check_options<Options...>::value, |
83 | "Unrecognized node option!" ); |
84 | using OptionsT = |
85 | typename ilist_detail::compute_node_options<T, Options...>::type; |
86 | using list_base_type = typename OptionsT::list_base_type; |
87 | ilist_sentinel<OptionsT> Sentinel; |
88 | |
89 | public: |
90 | using value_type = typename OptionsT::value_type; |
91 | using pointer = typename OptionsT::pointer; |
92 | using reference = typename OptionsT::reference; |
93 | using const_pointer = typename OptionsT::const_pointer; |
94 | using const_reference = typename OptionsT::const_reference; |
95 | using iterator = |
96 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
97 | false, false>::type; |
98 | using const_iterator = |
99 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
100 | false, true>::type; |
101 | using reverse_iterator = |
102 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
103 | true, false>::type; |
104 | using const_reverse_iterator = |
105 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
106 | true, true>::type; |
107 | using size_type = size_t; |
108 | using difference_type = ptrdiff_t; |
109 | |
110 | simple_ilist() = default; |
111 | ~simple_ilist() = default; |
112 | |
113 | // No copy constructors. |
114 | simple_ilist(const simple_ilist &) = delete; |
115 | simple_ilist &operator=(const simple_ilist &) = delete; |
116 | |
117 | // Move constructors. |
118 | simple_ilist(simple_ilist &&X) { splice(end(), X); } |
119 | simple_ilist &operator=(simple_ilist &&X) { |
120 | clear(); |
121 | splice(end(), X); |
122 | return *this; |
123 | } |
124 | |
125 | iterator begin() { return ++iterator(Sentinel); } |
126 | const_iterator begin() const { return ++const_iterator(Sentinel); } |
127 | iterator end() { return iterator(Sentinel); } |
128 | const_iterator end() const { return const_iterator(Sentinel); } |
129 | reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } |
130 | const_reverse_iterator rbegin() const { |
131 | return ++const_reverse_iterator(Sentinel); |
132 | } |
133 | reverse_iterator rend() { return reverse_iterator(Sentinel); } |
134 | const_reverse_iterator rend() const { |
135 | return const_reverse_iterator(Sentinel); |
136 | } |
137 | |
138 | /// Check if the list is empty in constant time. |
139 | [[nodiscard]] bool empty() const { return Sentinel.empty(); } |
140 | |
141 | /// Calculate the size of the list in linear time. |
142 | [[nodiscard]] size_type size() const { return std::distance(begin(), end()); } |
143 | |
144 | reference front() { return *begin(); } |
145 | const_reference front() const { return *begin(); } |
146 | reference back() { return *rbegin(); } |
147 | const_reference back() const { return *rbegin(); } |
148 | |
149 | /// Insert a node at the front; never copies. |
150 | void push_front(reference Node) { insert(begin(), Node); } |
151 | |
152 | /// Insert a node at the back; never copies. |
153 | void push_back(reference Node) { insert(end(), Node); } |
154 | |
155 | /// Remove the node at the front; never deletes. |
156 | void pop_front() { erase(begin()); } |
157 | |
158 | /// Remove the node at the back; never deletes. |
159 | void pop_back() { erase(--end()); } |
160 | |
161 | /// Swap with another list in place using std::swap. |
162 | void swap(simple_ilist &X) { std::swap(*this, X); } |
163 | |
164 | /// Insert a node by reference; never copies. |
165 | iterator insert(iterator I, reference Node) { |
166 | list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); |
167 | return iterator(&Node); |
168 | } |
169 | |
170 | /// Insert a range of nodes; never copies. |
171 | template <class Iterator> |
172 | void insert(iterator I, Iterator First, Iterator Last) { |
173 | for (; First != Last; ++First) |
174 | insert(I, *First); |
175 | } |
176 | |
177 | /// Clone another list. |
178 | template <class Cloner, class Disposer> |
179 | void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { |
180 | clearAndDispose(dispose); |
181 | for (const_reference V : L2) |
182 | push_back(Node: *clone(V)); |
183 | } |
184 | |
185 | /// Remove a node by reference; never deletes. |
186 | /// |
187 | /// \see \a erase() for removing by iterator. |
188 | /// \see \a removeAndDispose() if the node should be deleted. |
189 | void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } |
190 | |
191 | /// Remove a node by reference and dispose of it. |
192 | template <class Disposer> |
193 | void removeAndDispose(reference N, Disposer dispose) { |
194 | remove(N); |
195 | dispose(&N); |
196 | } |
197 | |
198 | /// Remove a node by iterator; never deletes. |
199 | /// |
200 | /// \see \a remove() for removing by reference. |
201 | /// \see \a eraseAndDispose() it the node should be deleted. |
202 | iterator erase(iterator I) { |
203 | assert(I != end() && "Cannot remove end of list!" ); |
204 | remove(N: *I++); |
205 | return I; |
206 | } |
207 | |
208 | /// Remove a range of nodes; never deletes. |
209 | /// |
210 | /// \see \a eraseAndDispose() if the nodes should be deleted. |
211 | iterator erase(iterator First, iterator Last) { |
212 | list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); |
213 | return Last; |
214 | } |
215 | |
216 | /// Remove a node by iterator and dispose of it. |
217 | template <class Disposer> |
218 | iterator eraseAndDispose(iterator I, Disposer dispose) { |
219 | auto Next = std::next(I); |
220 | erase(I); |
221 | dispose(&*I); |
222 | return Next; |
223 | } |
224 | |
225 | /// Remove a range of nodes and dispose of them. |
226 | template <class Disposer> |
227 | iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { |
228 | while (First != Last) |
229 | First = eraseAndDispose(First, dispose); |
230 | return Last; |
231 | } |
232 | |
233 | /// Clear the list; never deletes. |
234 | /// |
235 | /// \see \a clearAndDispose() if the nodes should be deleted. |
236 | void clear() { Sentinel.reset(); } |
237 | |
238 | /// Clear the list and dispose of the nodes. |
239 | template <class Disposer> void clearAndDispose(Disposer dispose) { |
240 | eraseAndDispose(begin(), end(), dispose); |
241 | } |
242 | |
243 | /// Splice in another list. |
244 | void splice(iterator I, simple_ilist &L2) { |
245 | splice(I, L2, L2.begin(), L2.end()); |
246 | } |
247 | |
248 | /// Splice in a node from another list. |
249 | void splice(iterator I, simple_ilist &L2, iterator Node) { |
250 | splice(I, L2, Node, std::next(Node)); |
251 | } |
252 | |
253 | /// Splice in a range of nodes from another list. |
254 | void splice(iterator I, simple_ilist &, iterator First, iterator Last) { |
255 | list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), |
256 | *Last.getNodePtr()); |
257 | } |
258 | |
259 | /// Merge in another list. |
260 | /// |
261 | /// \pre \c this and \p RHS are sorted. |
262 | ///@{ |
263 | void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } |
264 | template <class Compare> void merge(simple_ilist &RHS, Compare comp); |
265 | ///@} |
266 | |
267 | /// Sort the list. |
268 | ///@{ |
269 | void sort() { sort(std::less<T>()); } |
270 | template <class Compare> void sort(Compare comp); |
271 | ///@} |
272 | }; |
273 | |
274 | template <class T, class... Options> |
275 | template <class Compare> |
276 | void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { |
277 | if (this == &RHS || RHS.empty()) |
278 | return; |
279 | iterator LI = begin(), LE = end(); |
280 | iterator RI = RHS.begin(), RE = RHS.end(); |
281 | while (LI != LE) { |
282 | if (comp(*RI, *LI)) { |
283 | // Transfer a run of at least size 1 from RHS to LHS. |
284 | iterator RunStart = RI++; |
285 | RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); |
286 | splice(LI, RHS, RunStart, RI); |
287 | if (RI == RE) |
288 | return; |
289 | } |
290 | ++LI; |
291 | } |
292 | // Transfer the remaining RHS nodes once LHS is finished. |
293 | splice(LE, RHS, RI, RE); |
294 | } |
295 | |
296 | template <class T, class... Options> |
297 | template <class Compare> |
298 | void simple_ilist<T, Options...>::sort(Compare comp) { |
299 | // Vacuously sorted. |
300 | if (empty() || std::next(begin()) == end()) |
301 | return; |
302 | |
303 | // Split the list in the middle. |
304 | iterator Center = begin(), End = begin(); |
305 | while (End != end() && ++End != end()) { |
306 | ++Center; |
307 | ++End; |
308 | } |
309 | simple_ilist RHS; |
310 | RHS.splice(RHS.end(), *this, Center, end()); |
311 | |
312 | // Sort the sublists and merge back together. |
313 | sort(comp); |
314 | RHS.sort(comp); |
315 | merge(RHS, comp); |
316 | } |
317 | |
318 | } // end namespace llvm |
319 | |
320 | #endif // LLVM_ADT_SIMPLE_ILIST_H |
321 | |