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 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> 78class 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 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; 95 using iterator = ilist_iterator<OptionsT, false, false>; 96 using const_iterator = ilist_iterator<OptionsT, false, true>; 97 using reverse_iterator = ilist_iterator<OptionsT, true, false>; 98 using const_reverse_iterator = ilist_iterator<OptionsT, true, true>; 99 using size_type = size_t; 100 using difference_type = ptrdiff_t; 101 102 simple_ilist() = default; 103 ~simple_ilist() = default; 104 105 // No copy constructors. 106 simple_ilist(const simple_ilist &) = delete; 107 simple_ilist &operator=(const simple_ilist &) = delete; 108 109 // Move constructors. 110 simple_ilist(simple_ilist &&X) { splice(end(), X); } 111 simple_ilist &operator=(simple_ilist &&X) { 112 clear(); 113 splice(end(), X); 114 return *this; 115 } 116 117 iterator begin() { return ++iterator(Sentinel); } 118 const_iterator begin() const { return ++const_iterator(Sentinel); } 119 iterator end() { return iterator(Sentinel); } 120 const_iterator end() const { return const_iterator(Sentinel); } 121 reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } 122 const_reverse_iterator rbegin() const { 123 return ++const_reverse_iterator(Sentinel); 124 } 125 reverse_iterator rend() { return reverse_iterator(Sentinel); } 126 const_reverse_iterator rend() const { 127 return const_reverse_iterator(Sentinel); 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. 142 void push_front(reference Node) { insert(begin(), Node); } 143 144 /// Insert a node at the back; never copies. 145 void push_back(reference Node) { insert(end(), Node); } 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. 157 iterator insert(iterator I, reference Node) { 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. 194 iterator erase(iterator I) { 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. 203 iterator erase(iterator First, iterator Last) { 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. 236 void splice(iterator I, simple_ilist &L2) { 237 splice(I, L2, L2.begin(), L2.end()); 238 } 239 240 /// Splice in a node from another list. 241 void splice(iterator I, simple_ilist &L2, iterator Node) { 242 splice(I, L2, Node, std::next(Node)); 243 } 244 245 /// Splice in a range of nodes from another list. 246 void splice(iterator I, simple_ilist &, iterator First, iterator Last) { 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> 268void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { 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> 290void simple_ilist<T, Options...>::sort(Compare comp) { 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 } 301 simple_ilist RHS; 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 313