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