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
25namespace 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.
78template <typename T, class... Options>
79class 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
90public:
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 iterator end() { return iterator(Sentinel); }
121 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 reverse_iterator rend() { return reverse_iterator(Sentinel); }
127 const_reverse_iterator rend() const {
128 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 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 void swap(simple_ilist &X) { std::swap(*this, X); }
158
159 /// Insert a node by reference; never copies.
160 iterator insert(iterator I, reference Node) {
161 list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
162 return iterator(&Node);
163 }
164
165 /// Insert a range of nodes; never copies.
166 template <class Iterator>
167 void insert(iterator I, Iterator First, Iterator Last) {
168 for (; First != Last; ++First)
169 insert(I, *First);
170 }
171
172 /// Clone another list.
173 template <class Cloner, class Disposer>
174 void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
175 clearAndDispose(dispose);
176 for (const_reference V : L2)
177 push_back(*clone(V));
178 }
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 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 dispose(&N);
191 }
192
193 /// Remove a node by iterator; never deletes.
194 ///
195 /// \see \a remove() for removing by reference.
196 /// \see \a eraseAndDispose() it the node should be deleted.
197 iterator erase(iterator I) {
198 assert(I != end() && "Cannot remove end of list!");
199 remove(*I++);
200 return I;
201 }
202
203 /// Remove a range of nodes; never deletes.
204 ///
205 /// \see \a eraseAndDispose() if the nodes should be deleted.
206 iterator erase(iterator First, iterator Last) {
207 list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
208 return Last;
209 }
210
211 /// Remove a node by iterator and dispose of it.
212 template <class Disposer>
213 iterator eraseAndDispose(iterator I, Disposer dispose) {
214 auto Next = std::next(I);
215 erase(I);
216 dispose(&*I);
217 return Next;
218 }
219
220 /// Remove a range of nodes and dispose of them.
221 template <class Disposer>
222 iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
223 while (First != Last)
224 First = eraseAndDispose(First, dispose);
225 return Last;
226 }
227
228 /// Clear the list; never deletes.
229 ///
230 /// \see \a clearAndDispose() if the nodes should be deleted.
231 void clear() { Sentinel.reset(); }
232
233 /// Clear the list and dispose of the nodes.
234 template <class Disposer> void clearAndDispose(Disposer dispose) {
235 eraseAndDispose(begin(), end(), dispose);
236 }
237
238 /// Splice in another list.
239 void splice(iterator I, simple_ilist &L2) {
240 splice(I, L2, L2.begin(), L2.end());
241 }
242
243 /// Splice in a node from another list.
244 void splice(iterator I, simple_ilist &L2, iterator Node) {
245 splice(I, L2, Node, std::next(Node));
246 }
247
248 /// Splice in a range of nodes from another list.
249 void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
250 list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
251 *Last.getNodePtr());
252 }
253
254 /// Merge in another list.
255 ///
256 /// \pre \c this and \p RHS are sorted.
257 ///@{
258 void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
259 template <class Compare> void merge(simple_ilist &RHS, Compare comp);
260 ///@}
261
262 /// Sort the list.
263 ///@{
264 void sort() { sort(std::less<T>()); }
265 template <class Compare> void sort(Compare comp);
266 ///@}
267};
268
269template <class T, class... Options>
270template <class Compare>
271void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) {
272 if (this == &RHS || RHS.empty())
273 return;
274 iterator LI = begin(), LE = end();
275 iterator RI = RHS.begin(), RE = RHS.end();
276 while (LI != LE) {
277 if (comp(*RI, *LI)) {
278 // Transfer a run of at least size 1 from RHS to LHS.
279 iterator RunStart = RI++;
280 RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
281 splice(LI, RHS, RunStart, RI);
282 if (RI == RE)
283 return;
284 }
285 ++LI;
286 }
287 // Transfer the remaining RHS nodes once LHS is finished.
288 splice(LE, RHS, RI, RE);
289}
290
291template <class T, class... Options>
292template <class Compare>
293void simple_ilist<T, Options...>::sort(Compare comp) {
294 // Vacuously sorted.
295 if (empty() || std::next(begin()) == end())
296 return;
297
298 // Split the list in the middle.
299 iterator Center = begin(), End = begin();
300 while (End != end() && ++End != end()) {
301 ++Center;
302 ++End;
303 }
304 simple_ilist RHS;
305 RHS.splice(RHS.end(), *this, Center, end());
306
307 // Sort the sublists and merge back together.
308 sort(comp);
309 RHS.sort(comp);
310 merge(RHS, comp);
311}
312
313} // end namespace llvm
314
315#endif // LLVM_ADT_SIMPLE_ILIST_H
316