1 //==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- 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 // This file defines classes to implement an intrusive doubly linked list class 11 // (i.e. each node of the list must contain a next and previous field for the 12 // list. 13 // 14 // The ilist class itself should be a plug in replacement for list. This list 15 // replacement does not provide a constant time size() method, so be careful to 16 // use empty() when you really want to know if it's empty. 17 // 18 // The ilist class is implemented as a circular list. The list itself contains 19 // a sentinel node, whose Next points at begin() and whose Prev points at 20 // rbegin(). The sentinel node itself serves as end() and rend(). 21 // 22 //===----------------------------------------------------------------------===// 23 24 #ifndef LLVM_ADT_ILIST_H 25 #define LLVM_ADT_ILIST_H 26 27 #include "llvm/ADT/simple_ilist.h" 28 #include <cassert> 29 #include <cstddef> 30 #include <iterator> 31 32 namespace llvm { 33 34 /// Use delete by default for iplist and ilist. 35 /// 36 /// Specialize this to get different behaviour for ownership-related API. (If 37 /// you really want ownership semantics, consider using std::list or building 38 /// something like \a BumpPtrList.) 39 /// 40 /// \see ilist_noalloc_traits 41 template <typename NodeTy> struct ilist_alloc_traits { deleteNodeilist_alloc_traits42 static void deleteNode(NodeTy *V) { delete V; } 43 }; 44 45 /// Custom traits to do nothing on deletion. 46 /// 47 /// Specialize ilist_alloc_traits to inherit from this to disable the 48 /// non-intrusive deletion in iplist (which implies ownership). 49 /// 50 /// If you want purely intrusive semantics with no callbacks, consider using \a 51 /// simple_ilist instead. 52 /// 53 /// \code 54 /// template <> 55 /// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {}; 56 /// \endcode 57 template <typename NodeTy> struct ilist_noalloc_traits { deleteNodeilist_noalloc_traits58 static void deleteNode(NodeTy *V) {} 59 }; 60 61 /// Callbacks do nothing by default in iplist and ilist. 62 /// 63 /// Specialize this for to use callbacks for when nodes change their list 64 /// membership. 65 template <typename NodeTy> struct ilist_callback_traits { addNodeToListilist_callback_traits66 void addNodeToList(NodeTy *) {} removeNodeFromListilist_callback_traits67 void removeNodeFromList(NodeTy *) {} 68 69 /// Callback before transferring nodes to this list. 70 /// 71 /// \pre \c this!=&OldList 72 template <class Iterator> transferNodesFromListilist_callback_traits73 void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/, 74 Iterator /*last*/) { 75 (void)OldList; 76 } 77 }; 78 79 /// A fragment for template traits for intrusive list that provides default 80 /// node related operations. 81 /// 82 /// TODO: Remove this layer of indirection. It's not necessary. 83 template <typename NodeTy> 84 struct ilist_node_traits : ilist_alloc_traits<NodeTy>, 85 ilist_callback_traits<NodeTy> {}; 86 87 /// Template traits for intrusive list. 88 /// 89 /// Customize callbacks and allocation semantics. 90 template <typename NodeTy> 91 struct ilist_traits : public ilist_node_traits<NodeTy> {}; 92 93 /// Const traits should never be instantiated. 94 template <typename Ty> struct ilist_traits<const Ty> {}; 95 96 namespace ilist_detail { 97 98 template <class T> T &make(); 99 100 /// Type trait to check for a traits class that has a getNext member (as a 101 /// canary for any of the ilist_nextprev_traits API). 102 template <class TraitsT, class NodeT> struct HasGetNext { 103 typedef char Yes[1]; 104 typedef char No[2]; 105 template <size_t N> struct SFINAE {}; 106 107 template <class U> 108 static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0); 109 template <class> static No &test(...); 110 111 public: 112 static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); 113 }; 114 115 /// Type trait to check for a traits class that has a createSentinel member (as 116 /// a canary for any of the ilist_sentinel_traits API). 117 template <class TraitsT> struct HasCreateSentinel { 118 typedef char Yes[1]; 119 typedef char No[2]; 120 121 template <class U> 122 static Yes &test(U *I, decltype(I->createSentinel()) * = 0); 123 template <class> static No &test(...); 124 125 public: 126 static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); 127 }; 128 129 /// Type trait to check for a traits class that has a createNode member. 130 /// Allocation should be managed in a wrapper class, instead of in 131 /// ilist_traits. 132 template <class TraitsT, class NodeT> struct HasCreateNode { 133 typedef char Yes[1]; 134 typedef char No[2]; 135 template <size_t N> struct SFINAE {}; 136 137 template <class U> 138 static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0); 139 template <class> static No &test(...); 140 141 public: 142 static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); 143 }; 144 145 template <class TraitsT, class NodeT> struct HasObsoleteCustomization { 146 static const bool value = HasGetNext<TraitsT, NodeT>::value || 147 HasCreateSentinel<TraitsT>::value || 148 HasCreateNode<TraitsT, NodeT>::value; 149 }; 150 151 } // end namespace ilist_detail 152 153 //===----------------------------------------------------------------------===// 154 // 155 /// A wrapper around an intrusive list with callbacks and non-intrusive 156 /// ownership. 157 /// 158 /// This wraps a purely intrusive list (like simple_ilist) with a configurable 159 /// traits class. The traits can implement callbacks and customize the 160 /// ownership semantics. 161 /// 162 /// This is a subset of ilist functionality that can safely be used on nodes of 163 /// polymorphic types, i.e. a heterogeneous list with a common base class that 164 /// holds the next/prev pointers. The only state of the list itself is an 165 /// ilist_sentinel, which holds pointers to the first and last nodes in the 166 /// list. 167 template <class IntrusiveListT, class TraitsT> 168 class iplist_impl : public TraitsT, IntrusiveListT { 169 typedef IntrusiveListT base_list_type; 170 171 public: 172 typedef typename base_list_type::pointer pointer; 173 typedef typename base_list_type::const_pointer const_pointer; 174 typedef typename base_list_type::reference reference; 175 typedef typename base_list_type::const_reference const_reference; 176 typedef typename base_list_type::value_type value_type; 177 typedef typename base_list_type::size_type size_type; 178 typedef typename base_list_type::difference_type difference_type; 179 typedef typename base_list_type::iterator iterator; 180 typedef typename base_list_type::const_iterator const_iterator; 181 typedef typename base_list_type::reverse_iterator reverse_iterator; 182 typedef 183 typename base_list_type::const_reverse_iterator const_reverse_iterator; 184 185 private: 186 // TODO: Drop this assertion and the transitive type traits anytime after 187 // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code 188 // update). 189 static_assert( 190 !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value, 191 "ilist customization points have changed!"); 192 193 static bool op_less(const_reference L, const_reference R) { return L < R; } 194 static bool op_equal(const_reference L, const_reference R) { return L == R; } 195 196 public: 197 iplist_impl() = default; 198 199 iplist_impl(const iplist_impl &) = delete; 200 iplist_impl &operator=(const iplist_impl &) = delete; 201 202 iplist_impl(iplist_impl &&X) 203 : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {} 204 iplist_impl &operator=(iplist_impl &&X) { 205 *static_cast<TraitsT *>(this) = std::move(X); 206 *static_cast<IntrusiveListT *>(this) = std::move(X); 207 return *this; 208 } 209 210 ~iplist_impl() { clear(); } 211 212 // Miscellaneous inspection routines. 213 size_type max_size() const { return size_type(-1); } 214 215 using base_list_type::begin; 216 using base_list_type::end; 217 using base_list_type::rbegin; 218 using base_list_type::rend; 219 using base_list_type::empty; 220 using base_list_type::front; 221 using base_list_type::back; 222 223 void swap(iplist_impl &RHS) { 224 assert(0 && "Swap does not use list traits callback correctly yet!"); 225 base_list_type::swap(RHS); 226 } 227 228 iterator insert(iterator where, pointer New) { 229 this->addNodeToList(New); // Notify traits that we added a node... 230 return base_list_type::insert(where, *New); 231 } 232 233 iterator insert(iterator where, const_reference New) { 234 return this->insert(where, new value_type(New)); 235 } 236 237 iterator insertAfter(iterator where, pointer New) { 238 if (empty()) 239 return insert(begin(), New); 240 else 241 return insert(++where, New); 242 } 243 244 /// Clone another list. 245 template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) { 246 clear(); 247 for (const_reference V : L2) 248 push_back(clone(V)); 249 } 250 251 pointer remove(iterator &IT) { 252 pointer Node = &*IT++; 253 this->removeNodeFromList(Node); // Notify traits that we removed a node... 254 base_list_type::remove(*Node); 255 return Node; 256 } 257 258 pointer remove(const iterator &IT) { 259 iterator MutIt = IT; 260 return remove(MutIt); 261 } 262 263 pointer remove(pointer IT) { return remove(iterator(IT)); } 264 pointer remove(reference IT) { return remove(iterator(IT)); } 265 266 // erase - remove a node from the controlled sequence... and delete it. 267 iterator erase(iterator where) { 268 this->deleteNode(remove(where)); 269 return where; 270 } 271 272 iterator erase(pointer IT) { return erase(iterator(IT)); } 273 iterator erase(reference IT) { return erase(iterator(IT)); } 274 275 /// Remove all nodes from the list like clear(), but do not call 276 /// removeNodeFromList() or deleteNode(). 277 /// 278 /// This should only be used immediately before freeing nodes in bulk to 279 /// avoid traversing the list and bringing all the nodes into cache. 280 void clearAndLeakNodesUnsafely() { base_list_type::clear(); } 281 282 private: 283 // transfer - The heart of the splice function. Move linked list nodes from 284 // [first, last) into position. 285 // 286 void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) { 287 if (position == last) 288 return; 289 290 if (this != &L2) // Notify traits we moved the nodes... 291 this->transferNodesFromList(L2, first, last); 292 293 base_list_type::splice(position, L2, first, last); 294 } 295 296 public: 297 //===----------------------------------------------------------------------=== 298 // Functionality derived from other functions defined above... 299 // 300 301 using base_list_type::size; 302 303 iterator erase(iterator first, iterator last) { 304 while (first != last) 305 first = erase(first); 306 return last; 307 } 308 309 void clear() { erase(begin(), end()); } 310 311 // Front and back inserters... 312 void push_front(pointer val) { insert(begin(), val); } 313 void push_back(pointer val) { insert(end(), val); } 314 void pop_front() { 315 assert(!empty() && "pop_front() on empty list!"); 316 erase(begin()); 317 } 318 void pop_back() { 319 assert(!empty() && "pop_back() on empty list!"); 320 iterator t = end(); erase(--t); 321 } 322 323 // Special forms of insert... 324 template<class InIt> void insert(iterator where, InIt first, InIt last) { 325 for (; first != last; ++first) insert(where, *first); 326 } 327 328 // Splice members - defined in terms of transfer... 329 void splice(iterator where, iplist_impl &L2) { 330 if (!L2.empty()) 331 transfer(where, L2, L2.begin(), L2.end()); 332 } 333 void splice(iterator where, iplist_impl &L2, iterator first) { 334 iterator last = first; ++last; 335 if (where == first || where == last) return; // No change 336 transfer(where, L2, first, last); 337 } 338 void splice(iterator where, iplist_impl &L2, iterator first, iterator last) { 339 if (first != last) transfer(where, L2, first, last); 340 } 341 void splice(iterator where, iplist_impl &L2, reference N) { 342 splice(where, L2, iterator(N)); 343 } 344 void splice(iterator where, iplist_impl &L2, pointer N) { 345 splice(where, L2, iterator(N)); 346 } 347 348 template <class Compare> 349 void merge(iplist_impl &Right, Compare comp) { 350 if (this == &Right) 351 return; 352 this->transferNodesFromList(Right, Right.begin(), Right.end()); 353 base_list_type::merge(Right, comp); 354 } 355 void merge(iplist_impl &Right) { return merge(Right, op_less); } 356 357 using base_list_type::sort; 358 359 /// Get the previous node, or \c nullptr for the list head. 360 pointer getPrevNode(reference N) const { 361 auto I = N.getIterator(); 362 if (I == begin()) 363 return nullptr; 364 return &*std::prev(I); 365 } 366 /// Get the previous node, or \c nullptr for the list head. 367 const_pointer getPrevNode(const_reference N) const { 368 return getPrevNode(const_cast<reference >(N)); 369 } 370 371 /// Get the next node, or \c nullptr for the list tail. 372 pointer getNextNode(reference N) const { 373 auto Next = std::next(N.getIterator()); 374 if (Next == end()) 375 return nullptr; 376 return &*Next; 377 } 378 /// Get the next node, or \c nullptr for the list tail. 379 const_pointer getNextNode(const_reference N) const { 380 return getNextNode(const_cast<reference >(N)); 381 } 382 }; 383 384 /// An intrusive list with ownership and callbacks specified/controlled by 385 /// ilist_traits, only with API safe for polymorphic types. 386 /// 387 /// The \p Options parameters are the same as those for \a simple_ilist. See 388 /// there for a description of what's available. 389 template <class T, class... Options> 390 class iplist 391 : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> { 392 using iplist_impl_type = typename iplist::iplist_impl; 393 394 public: 395 iplist() = default; 396 397 iplist(const iplist &X) = delete; 398 iplist &operator=(const iplist &X) = delete; 399 400 iplist(iplist &&X) : iplist_impl_type(std::move(X)) {} 401 iplist &operator=(iplist &&X) { 402 *static_cast<iplist_impl_type *>(this) = std::move(X); 403 return *this; 404 } 405 }; 406 407 template <class T, class... Options> using ilist = iplist<T, Options...>; 408 409 } // end namespace llvm 410 411 namespace std { 412 413 // Ensure that swap uses the fast list swap... 414 template<class Ty> 415 void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 416 Left.swap(Right); 417 } 418 419 } // end namespace std 420 421 #endif // LLVM_ADT_ILIST_H 422