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 20namespace 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. 73template <typename T, class... Options> 74class 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 85public: 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. 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 113 iterator begin() { return ++iterator(Sentinel); } 114 const_iterator begin() const { return ++const_iterator(Sentinel); } 115 iterator end() { return iterator(Sentinel); } 116 const_iterator end() const { return const_iterator(Sentinel); } 117 reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } 118 const_reverse_iterator rbegin() const { 119 return ++const_reverse_iterator(Sentinel); 120 } 121 reverse_iterator rend() { return reverse_iterator(Sentinel); } 122 const_reverse_iterator rend() const { 123 return const_reverse_iterator(Sentinel); 124 } 125 126 /// Check if the list is empty in constant time. 127 LLVM_NODISCARD bool empty() const { return Sentinel.empty(); } 128 129 /// Calculate the size of the list in linear time. 130 LLVM_NODISCARD size_type size() const { 131 return std::distance(begin(), end()); 132 } 133 134 reference front() { return *begin(); } 135 const_reference front() const { return *begin(); } 136 reference back() { return *rbegin(); } 137 const_reference back() const { return *rbegin(); } 138 139 /// Insert a node at the front; never copies. 140 void push_front(reference Node) { insert(begin(), Node); } 141 142 /// Insert a node at the back; never copies. 143 void push_back(reference Node) { insert(end(), Node); } 144 145 /// Remove the node at the front; never deletes. 146 void pop_front() { erase(begin()); } 147 148 /// Remove the node at the back; never deletes. 149 void pop_back() { erase(--end()); } 150 151 /// Swap with another list in place using std::swap. 152 void swap(simple_ilist &X) { std::swap(*this, X); } 153 154 /// Insert a node by reference; never copies. 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> 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> 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. 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> 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. 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. 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> 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> 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. 226 void clear() { Sentinel.reset(); } 227 228 /// Clear the list and dispose of the nodes. 229 template <class Disposer> void clearAndDispose(Disposer dispose) { 230 eraseAndDispose(begin(), end(), dispose); 231 } 232 233 /// Splice in another list. 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. 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. 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 ///@{ 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 ///@{ 259 void sort() { sort(std::less<T>()); } 260 template <class Compare> void sort(Compare comp); 261 ///@} 262}; 263 264template <class T, class... Options> 265template <class Compare> 266void 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 286template <class T, class... Options> 287template <class Compare> 288void 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