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