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 = ilist_iterator<OptionsT, false, false>; |
96 | using const_iterator = ilist_iterator<OptionsT, false, true>; |
97 | using reverse_iterator = ilist_iterator<OptionsT, true, false>; |
98 | using const_reverse_iterator = ilist_iterator<OptionsT, true, true>; |
99 | using size_type = size_t; |
100 | using difference_type = ptrdiff_t; |
101 | |
102 | simple_ilist() = default; |
103 | ~simple_ilist() = default; |
104 | |
105 | // No copy constructors. |
106 | simple_ilist(const simple_ilist &) = delete; |
107 | simple_ilist &operator=(const simple_ilist &) = delete; |
108 | |
109 | // Move constructors. |
110 | simple_ilist(simple_ilist &&X) { splice(end(), X); } |
111 | simple_ilist &operator=(simple_ilist &&X) { |
112 | clear(); |
113 | splice(end(), X); |
114 | return *this; |
115 | } |
116 | |
117 | iterator begin() { return ++iterator(Sentinel); } |
118 | const_iterator begin() const { return ++const_iterator(Sentinel); } |
119 | iterator end() { return iterator(Sentinel); } |
120 | const_iterator end() const { return const_iterator(Sentinel); } |
121 | reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } |
122 | const_reverse_iterator rbegin() const { |
123 | return ++const_reverse_iterator(Sentinel); |
124 | } |
125 | reverse_iterator rend() { return reverse_iterator(Sentinel); } |
126 | const_reverse_iterator rend() const { |
127 | return const_reverse_iterator(Sentinel); |
128 | } |
129 | |
130 | /// Check if the list is empty in constant time. |
131 | LLVM_NODISCARD bool empty() const { return Sentinel.empty(); } |
132 | |
133 | /// Calculate the size of the list in linear time. |
134 | LLVM_NODISCARD size_type size() const { |
135 | return std::distance(begin(), end()); |
136 | } |
137 | |
138 | reference front() { return *begin(); } |
139 | const_reference front() const { return *begin(); } |
140 | reference back() { return *rbegin(); } |
141 | const_reference back() const { return *rbegin(); } |
142 | |
143 | /// Insert a node at the front; never copies. |
144 | void push_front(reference Node) { insert(begin(), Node); } |
145 | |
146 | /// Insert a node at the back; never copies. |
147 | void push_back(reference Node) { insert(end(), Node); } |
148 | |
149 | /// Remove the node at the front; never deletes. |
150 | void pop_front() { erase(begin()); } |
151 | |
152 | /// Remove the node at the back; never deletes. |
153 | void pop_back() { erase(--end()); } |
154 | |
155 | /// Swap with another list in place using std::swap. |
156 | void swap(simple_ilist &X) { std::swap(*this, X); } |
157 | |
158 | /// Insert a node by reference; never copies. |
159 | iterator insert(iterator I, reference Node) { |
160 | list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); |
161 | return iterator(&Node); |
162 | } |
163 | |
164 | /// Insert a range of nodes; never copies. |
165 | template <class Iterator> |
166 | void insert(iterator I, Iterator First, Iterator Last) { |
167 | for (; First != Last; ++First) |
168 | insert(I, *First); |
169 | } |
170 | |
171 | /// Clone another list. |
172 | template <class Cloner, class Disposer> |
173 | void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { |
174 | clearAndDispose(dispose); |
175 | for (const_reference V : L2) |
176 | push_back(*clone(V)); |
177 | } |
178 | |
179 | /// Remove a node by reference; never deletes. |
180 | /// |
181 | /// \see \a erase() for removing by iterator. |
182 | /// \see \a removeAndDispose() if the node should be deleted. |
183 | void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } |
184 | |
185 | /// Remove a node by reference and dispose of it. |
186 | template <class Disposer> |
187 | void removeAndDispose(reference N, Disposer dispose) { |
188 | remove(N); |
189 | dispose(&N); |
190 | } |
191 | |
192 | /// Remove a node by iterator; never deletes. |
193 | /// |
194 | /// \see \a remove() for removing by reference. |
195 | /// \see \a eraseAndDispose() it the node should be deleted. |
196 | iterator erase(iterator I) { |
197 | assert(I != end() && "Cannot remove end of list!" ); |
198 | remove(*I++); |
199 | return I; |
200 | } |
201 | |
202 | /// Remove a range of nodes; never deletes. |
203 | /// |
204 | /// \see \a eraseAndDispose() if the nodes should be deleted. |
205 | iterator erase(iterator First, iterator Last) { |
206 | list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); |
207 | return Last; |
208 | } |
209 | |
210 | /// Remove a node by iterator and dispose of it. |
211 | template <class Disposer> |
212 | iterator eraseAndDispose(iterator I, Disposer dispose) { |
213 | auto Next = std::next(I); |
214 | erase(I); |
215 | dispose(&*I); |
216 | return Next; |
217 | } |
218 | |
219 | /// Remove a range of nodes and dispose of them. |
220 | template <class Disposer> |
221 | iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { |
222 | while (First != Last) |
223 | First = eraseAndDispose(First, dispose); |
224 | return Last; |
225 | } |
226 | |
227 | /// Clear the list; never deletes. |
228 | /// |
229 | /// \see \a clearAndDispose() if the nodes should be deleted. |
230 | void clear() { Sentinel.reset(); } |
231 | |
232 | /// Clear the list and dispose of the nodes. |
233 | template <class Disposer> void clearAndDispose(Disposer dispose) { |
234 | eraseAndDispose(begin(), end(), dispose); |
235 | } |
236 | |
237 | /// Splice in another list. |
238 | void splice(iterator I, simple_ilist &L2) { |
239 | splice(I, L2, L2.begin(), L2.end()); |
240 | } |
241 | |
242 | /// Splice in a node from another list. |
243 | void splice(iterator I, simple_ilist &L2, iterator Node) { |
244 | splice(I, L2, Node, std::next(Node)); |
245 | } |
246 | |
247 | /// Splice in a range of nodes from another list. |
248 | void splice(iterator I, simple_ilist &, iterator First, iterator Last) { |
249 | list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), |
250 | *Last.getNodePtr()); |
251 | } |
252 | |
253 | /// Merge in another list. |
254 | /// |
255 | /// \pre \c this and \p RHS are sorted. |
256 | ///@{ |
257 | void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } |
258 | template <class Compare> void merge(simple_ilist &RHS, Compare comp); |
259 | ///@} |
260 | |
261 | /// Sort the list. |
262 | ///@{ |
263 | void sort() { sort(std::less<T>()); } |
264 | template <class Compare> void sort(Compare comp); |
265 | ///@} |
266 | }; |
267 | |
268 | template <class T, class... Options> |
269 | template <class Compare> |
270 | void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { |
271 | if (this == &RHS || RHS.empty()) |
272 | return; |
273 | iterator LI = begin(), LE = end(); |
274 | iterator RI = RHS.begin(), RE = RHS.end(); |
275 | while (LI != LE) { |
276 | if (comp(*RI, *LI)) { |
277 | // Transfer a run of at least size 1 from RHS to LHS. |
278 | iterator RunStart = RI++; |
279 | RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); |
280 | splice(LI, RHS, RunStart, RI); |
281 | if (RI == RE) |
282 | return; |
283 | } |
284 | ++LI; |
285 | } |
286 | // Transfer the remaining RHS nodes once LHS is finished. |
287 | splice(LE, RHS, RI, RE); |
288 | } |
289 | |
290 | template <class T, class... Options> |
291 | template <class Compare> |
292 | void simple_ilist<T, Options...>::sort(Compare comp) { |
293 | // Vacuously sorted. |
294 | if (empty() || std::next(begin()) == end()) |
295 | return; |
296 | |
297 | // Split the list in the middle. |
298 | iterator Center = begin(), End = begin(); |
299 | while (End != end() && ++End != end()) { |
300 | ++Center; |
301 | ++End; |
302 | } |
303 | simple_ilist RHS; |
304 | RHS.splice(RHS.end(), *this, Center, end()); |
305 | |
306 | // Sort the sublists and merge back together. |
307 | sort(comp); |
308 | RHS.sort(comp); |
309 | merge(RHS, comp); |
310 | } |
311 | |
312 | } // end namespace llvm |
313 | |
314 | #endif // LLVM_ADT_SIMPLE_ILIST_H |
315 | |