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