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 24 namespace 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. 77 template <typename T, class... Options> 78 class 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 89 public: 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 = 96 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, 97 false, false>::type; 98 using const_iterator = 99 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, 100 false, true>::type; 101 using reverse_iterator = 102 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, 103 true, false>::type; 104 using const_reverse_iterator = 105 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, 106 true, true>::type; 107 using size_type = size_t; 108 using difference_type = ptrdiff_t; 109 110 simple_ilist() = default; 111 ~simple_ilist() = default; 112 113 // No copy constructors. 114 simple_ilist(const simple_ilist &) = delete; 115 simple_ilist &operator=(const simple_ilist &) = delete; 116 117 // Move constructors. 118 simple_ilist(simple_ilist &&X) { splice(end(), X); } 119 simple_ilist &operator=(simple_ilist &&X) { 120 clear(); 121 splice(end(), X); 122 return *this; 123 } 124 125 iterator begin() { return ++iterator(Sentinel); } 126 const_iterator begin() const { return ++const_iterator(Sentinel); } 127 iterator end() { return iterator(Sentinel); } 128 const_iterator end() const { return const_iterator(Sentinel); } 129 reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } 130 const_reverse_iterator rbegin() const { 131 return ++const_reverse_iterator(Sentinel); 132 } 133 reverse_iterator rend() { return reverse_iterator(Sentinel); } 134 const_reverse_iterator rend() const { 135 return const_reverse_iterator(Sentinel); 136 } 137 138 /// Check if the list is empty in constant time. 139 [[nodiscard]] bool empty() const { return Sentinel.empty(); } 140 141 /// Calculate the size of the list in linear time. 142 [[nodiscard]] size_type size() const { return std::distance(begin(), end()); } 143 144 reference front() { return *begin(); } 145 const_reference front() const { return *begin(); } 146 reference back() { return *rbegin(); } 147 const_reference back() const { return *rbegin(); } 148 149 /// Insert a node at the front; never copies. 150 void push_front(reference Node) { insert(begin(), Node); } 151 152 /// Insert a node at the back; never copies. 153 void push_back(reference Node) { insert(end(), Node); } 154 155 /// Remove the node at the front; never deletes. 156 void pop_front() { erase(begin()); } 157 158 /// Remove the node at the back; never deletes. 159 void pop_back() { erase(--end()); } 160 161 /// Swap with another list in place using std::swap. 162 void swap(simple_ilist &X) { std::swap(*this, X); } 163 164 /// Insert a node by reference; never copies. 165 iterator insert(iterator I, reference Node) { 166 list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); 167 return iterator(&Node); 168 } 169 170 /// Insert a range of nodes; never copies. 171 template <class Iterator> 172 void insert(iterator I, Iterator First, Iterator Last) { 173 for (; First != Last; ++First) 174 insert(I, *First); 175 } 176 177 /// Clone another list. 178 template <class Cloner, class Disposer> 179 void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { 180 clearAndDispose(dispose); 181 for (const_reference V : L2) 182 push_back(*clone(V)); 183 } 184 185 /// Remove a node by reference; never deletes. 186 /// 187 /// \see \a erase() for removing by iterator. 188 /// \see \a removeAndDispose() if the node should be deleted. 189 void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } 190 191 /// Remove a node by reference and dispose of it. 192 template <class Disposer> 193 void removeAndDispose(reference N, Disposer dispose) { 194 remove(N); 195 dispose(&N); 196 } 197 198 /// Remove a node by iterator; never deletes. 199 /// 200 /// \see \a remove() for removing by reference. 201 /// \see \a eraseAndDispose() it the node should be deleted. 202 iterator erase(iterator I) { 203 assert(I != end() && "Cannot remove end of list!"); 204 remove(*I++); 205 return I; 206 } 207 208 /// Remove a range of nodes; never deletes. 209 /// 210 /// \see \a eraseAndDispose() if the nodes should be deleted. 211 iterator erase(iterator First, iterator Last) { 212 list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); 213 return Last; 214 } 215 216 /// Remove a node by iterator and dispose of it. 217 template <class Disposer> 218 iterator eraseAndDispose(iterator I, Disposer dispose) { 219 auto Next = std::next(I); 220 erase(I); 221 dispose(&*I); 222 return Next; 223 } 224 225 /// Remove a range of nodes and dispose of them. 226 template <class Disposer> 227 iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { 228 while (First != Last) 229 First = eraseAndDispose(First, dispose); 230 return Last; 231 } 232 233 /// Clear the list; never deletes. 234 /// 235 /// \see \a clearAndDispose() if the nodes should be deleted. 236 void clear() { Sentinel.reset(); } 237 238 /// Clear the list and dispose of the nodes. 239 template <class Disposer> void clearAndDispose(Disposer dispose) { 240 eraseAndDispose(begin(), end(), dispose); 241 } 242 243 /// Splice in another list. 244 void splice(iterator I, simple_ilist &L2) { 245 splice(I, L2, L2.begin(), L2.end()); 246 } 247 248 /// Splice in a node from another list. 249 void splice(iterator I, simple_ilist &L2, iterator Node) { 250 splice(I, L2, Node, std::next(Node)); 251 } 252 253 /// Splice in a range of nodes from another list. 254 void splice(iterator I, simple_ilist &, iterator First, iterator Last) { 255 list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), 256 *Last.getNodePtr()); 257 } 258 259 /// Merge in another list. 260 /// 261 /// \pre \c this and \p RHS are sorted. 262 ///@{ 263 void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } 264 template <class Compare> void merge(simple_ilist &RHS, Compare comp); 265 ///@} 266 267 /// Sort the list. 268 ///@{ 269 void sort() { sort(std::less<T>()); } 270 template <class Compare> void sort(Compare comp); 271 ///@} 272 }; 273 274 template <class T, class... Options> 275 template <class Compare> 276 void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { 277 if (this == &RHS || RHS.empty()) 278 return; 279 iterator LI = begin(), LE = end(); 280 iterator RI = RHS.begin(), RE = RHS.end(); 281 while (LI != LE) { 282 if (comp(*RI, *LI)) { 283 // Transfer a run of at least size 1 from RHS to LHS. 284 iterator RunStart = RI++; 285 RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); 286 splice(LI, RHS, RunStart, RI); 287 if (RI == RE) 288 return; 289 } 290 ++LI; 291 } 292 // Transfer the remaining RHS nodes once LHS is finished. 293 splice(LE, RHS, RI, RE); 294 } 295 296 template <class T, class... Options> 297 template <class Compare> 298 void simple_ilist<T, Options...>::sort(Compare comp) { 299 // Vacuously sorted. 300 if (empty() || std::next(begin()) == end()) 301 return; 302 303 // Split the list in the middle. 304 iterator Center = begin(), End = begin(); 305 while (End != end() && ++End != end()) { 306 ++Center; 307 ++End; 308 } 309 simple_ilist RHS; 310 RHS.splice(RHS.end(), *this, Center, end()); 311 312 // Sort the sublists and merge back together. 313 sort(comp); 314 RHS.sort(comp); 315 merge(RHS, comp); 316 } 317 318 } // end namespace llvm 319 320 #endif // LLVM_ADT_SIMPLE_ILIST_H 321