Branch data Line data Source code
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 [ # # ]: 0 : iterator begin() { return ++iterator(Sentinel); }
126 : : const_iterator begin() const { return ++const_iterator(Sentinel); }
127 : 0 : 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(*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(*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
|
