LLVM 17.0.0git
simple_ilist.h
Go to the documentation of this file.
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"
14#include "llvm/ADT/ilist_node.h"
17#include <algorithm>
18#include <cassert>
19#include <cstddef>
20#include <functional>
21#include <iterator>
22#include <utility>
23
24namespace 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.
77template <typename T, class... Options>
79 : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
81 typename ilist_detail::compute_node_options<T, Options...>::type> {
83 "Unrecognized node option!");
84 using OptionsT =
86 using list_base_type = typename OptionsT::list_base_type;
88
89public:
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;
99 using size_type = size_t;
101
102 simple_ilist() = default;
103 ~simple_ilist() = default;
104
105 // No copy constructors.
106 simple_ilist(const simple_ilist &) = delete;
108
109 // Move constructors.
112 clear();
113 splice(end(), X);
114 return *this;
115 }
116
124 }
128 }
129
130 /// Check if the list is empty in constant time.
131 [[nodiscard]] bool empty() const { return Sentinel.empty(); }
132
133 /// Calculate the size of the list in linear time.
134 [[nodiscard]] size_type size() const { return std::distance(begin(), end()); }
135
136 reference front() { return *begin(); }
137 const_reference front() const { return *begin(); }
138 reference back() { return *rbegin(); }
139 const_reference back() const { return *rbegin(); }
140
141 /// Insert a node at the front; never copies.
143
144 /// Insert a node at the back; never copies.
146
147 /// Remove the node at the front; never deletes.
148 void pop_front() { erase(begin()); }
149
150 /// Remove the node at the back; never deletes.
151 void pop_back() { erase(--end()); }
152
153 /// Swap with another list in place using std::swap.
154 void swap(simple_ilist &X) { std::swap(*this, X); }
155
156 /// Insert a node by reference; never copies.
158 list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
159 return iterator(&Node);
160 }
161
162 /// Insert a range of nodes; never copies.
163 template <class Iterator>
164 void insert(iterator I, Iterator First, Iterator Last) {
165 for (; First != Last; ++First)
166 insert(I, *First);
167 }
168
169 /// Clone another list.
170 template <class Cloner, class Disposer>
171 void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
172 clearAndDispose(dispose);
173 for (const_reference V : L2)
174 push_back(*clone(V));
175 }
176
177 /// Remove a node by reference; never deletes.
178 ///
179 /// \see \a erase() for removing by iterator.
180 /// \see \a removeAndDispose() if the node should be deleted.
181 void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }
182
183 /// Remove a node by reference and dispose of it.
184 template <class Disposer>
185 void removeAndDispose(reference N, Disposer dispose) {
186 remove(N);
187 dispose(&N);
188 }
189
190 /// Remove a node by iterator; never deletes.
191 ///
192 /// \see \a remove() for removing by reference.
193 /// \see \a eraseAndDispose() it the node should be deleted.
195 assert(I != end() && "Cannot remove end of list!");
196 remove(*I++);
197 return I;
198 }
199
200 /// Remove a range of nodes; never deletes.
201 ///
202 /// \see \a eraseAndDispose() if the nodes should be deleted.
204 list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
205 return Last;
206 }
207
208 /// Remove a node by iterator and dispose of it.
209 template <class Disposer>
210 iterator eraseAndDispose(iterator I, Disposer dispose) {
211 auto Next = std::next(I);
212 erase(I);
213 dispose(&*I);
214 return Next;
215 }
216
217 /// Remove a range of nodes and dispose of them.
218 template <class Disposer>
219 iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
220 while (First != Last)
221 First = eraseAndDispose(First, dispose);
222 return Last;
223 }
224
225 /// Clear the list; never deletes.
226 ///
227 /// \see \a clearAndDispose() if the nodes should be deleted.
228 void clear() { Sentinel.reset(); }
229
230 /// Clear the list and dispose of the nodes.
231 template <class Disposer> void clearAndDispose(Disposer dispose) {
232 eraseAndDispose(begin(), end(), dispose);
233 }
234
235 /// Splice in another list.
237 splice(I, L2, L2.begin(), L2.end());
238 }
239
240 /// Splice in a node from another list.
242 splice(I, L2, Node, std::next(Node));
243 }
244
245 /// Splice in a range of nodes from another list.
247 list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
248 *Last.getNodePtr());
249 }
250
251 /// Merge in another list.
252 ///
253 /// \pre \c this and \p RHS are sorted.
254 ///@{
255 void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
256 template <class Compare> void merge(simple_ilist &RHS, Compare comp);
257 ///@}
258
259 /// Sort the list.
260 ///@{
261 void sort() { sort(std::less<T>()); }
262 template <class Compare> void sort(Compare comp);
263 ///@}
264};
265
266template <class T, class... Options>
267template <class Compare>
269 if (this == &RHS || RHS.empty())
270 return;
271 iterator LI = begin(), LE = end();
272 iterator RI = RHS.begin(), RE = RHS.end();
273 while (LI != LE) {
274 if (comp(*RI, *LI)) {
275 // Transfer a run of at least size 1 from RHS to LHS.
276 iterator RunStart = RI++;
277 RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
278 splice(LI, RHS, RunStart, RI);
279 if (RI == RE)
280 return;
281 }
282 ++LI;
283 }
284 // Transfer the remaining RHS nodes once LHS is finished.
285 splice(LE, RHS, RI, RE);
286}
287
288template <class T, class... Options>
289template <class Compare>
291 // Vacuously sorted.
292 if (empty() || std::next(begin()) == end())
293 return;
294
295 // Split the list in the middle.
296 iterator Center = begin(), End = begin();
297 while (End != end() && ++End != end()) {
298 ++Center;
299 ++End;
300 }
302 RHS.splice(RHS.end(), *this, Center, end());
303
304 // Sort the sublists and merge back together.
305 sort(comp);
306 RHS.sort(comp);
307 merge(RHS, comp);
308}
309
310} // end namespace llvm
311
312#endif // LLVM_ADT_SIMPLE_ILIST_H
Given that RA is a live value
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static LVOptions Options
Definition: LVOptions.cpp:25
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
#define I(x, y, z)
Definition: MD5.cpp:58
#define T
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Iterator for intrusive lists based on ilist_node.
A simple intrusive list implementation.
Definition: simple_ilist.h:81
typename OptionsT::reference reference
Definition: simple_ilist.h:92
iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose)
Remove a range of nodes and dispose of them.
Definition: simple_ilist.h:219
iterator eraseAndDispose(iterator I, Disposer dispose)
Remove a node by iterator and dispose of it.
Definition: simple_ilist.h:210
void splice(iterator I, simple_ilist &, iterator First, iterator Last)
Splice in a range of nodes from another list.
Definition: simple_ilist.h:246
typename OptionsT::const_reference const_reference
Definition: simple_ilist.h:94
simple_ilist(simple_ilist &&X)
Definition: simple_ilist.h:110
simple_ilist & operator=(const simple_ilist &)=delete
ilist_iterator< OptionsT, false, false > iterator
Definition: simple_ilist.h:95
const_reverse_iterator rend() const
Definition: simple_ilist.h:126
ilist_iterator< OptionsT, false, true > const_iterator
Definition: simple_ilist.h:96
const_reverse_iterator rbegin() const
Definition: simple_ilist.h:122
void splice(iterator I, simple_ilist &L2)
Splice in another list.
Definition: simple_ilist.h:236
const_reference front() const
Definition: simple_ilist.h:137
simple_ilist & operator=(simple_ilist &&X)
Definition: simple_ilist.h:111
reference back()
Definition: simple_ilist.h:138
void swap(simple_ilist &X)
Swap with another list in place using std::swap.
Definition: simple_ilist.h:154
const_reference back() const
Definition: simple_ilist.h:139
iterator erase(iterator I)
Remove a node by iterator; never deletes.
Definition: simple_ilist.h:194
void sort(Compare comp)
Definition: simple_ilist.h:290
void pop_back()
Remove the node at the back; never deletes.
Definition: simple_ilist.h:151
simple_ilist(const simple_ilist &)=delete
void push_front(reference Node)
Insert a node at the front; never copies.
Definition: simple_ilist.h:142
ilist_iterator< OptionsT, true, true > const_reverse_iterator
Definition: simple_ilist.h:98
~simple_ilist()=default
void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose)
Clone another list.
Definition: simple_ilist.h:171
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:157
reverse_iterator rend()
Definition: simple_ilist.h:125
void merge(simple_ilist &RHS, Compare comp)
Definition: simple_ilist.h:268
void merge(simple_ilist &RHS)
Merge in another list.
Definition: simple_ilist.h:255
const_iterator end() const
Definition: simple_ilist.h:120
void clear()
Clear the list; never deletes.
Definition: simple_ilist.h:228
simple_ilist()=default
void insert(iterator I, Iterator First, Iterator Last)
Insert a range of nodes; never copies.
Definition: simple_ilist.h:164
const_iterator begin() const
Definition: simple_ilist.h:118
bool empty() const
Check if the list is empty in constant time.
Definition: simple_ilist.h:131
void pop_front()
Remove the node at the front; never deletes.
Definition: simple_ilist.h:148
iterator erase(iterator First, iterator Last)
Remove a range of nodes; never deletes.
Definition: simple_ilist.h:203
typename OptionsT::value_type value_type
Definition: simple_ilist.h:90
void push_back(reference Node)
Insert a node at the back; never copies.
Definition: simple_ilist.h:145
typename OptionsT::const_pointer const_pointer
Definition: simple_ilist.h:93
void sort()
Sort the list.
Definition: simple_ilist.h:261
ilist_iterator< OptionsT, true, false > reverse_iterator
Definition: simple_ilist.h:97
void splice(iterator I, simple_ilist &L2, iterator Node)
Splice in a node from another list.
Definition: simple_ilist.h:241
reverse_iterator rbegin()
Definition: simple_ilist.h:121
void remove(reference N)
Remove a node by reference; never deletes.
Definition: simple_ilist.h:181
void clearAndDispose(Disposer dispose)
Clear the list and dispose of the nodes.
Definition: simple_ilist.h:231
typename OptionsT::pointer pointer
Definition: simple_ilist.h:91
size_type size() const
Calculate the size of the list in linear time.
Definition: simple_ilist.h:134
void removeAndDispose(reference N, Disposer dispose)
Remove a node by reference and dispose of it.
Definition: simple_ilist.h:185
reference front()
Definition: simple_ilist.h:136
This file defines the ilist_node class template, which is a convenient base class for creating classe...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1683
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
#define N
Check whether options are valid.