1 //==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- 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 // This file defines classes to implement an intrusive doubly linked list class 10 // (i.e. each node of the list must contain a next and previous field for the 11 // list. 12 // 13 // The ilist class itself should be a plug in replacement for list. This list 14 // replacement does not provide a constant time size() method, so be careful to 15 // use empty() when you really want to know if it's empty. 16 // 17 // The ilist class is implemented as a circular list. The list itself contains 18 // a sentinel node, whose Next points at begin() and whose Prev points at 19 // rbegin(). The sentinel node itself serves as end() and rend(). 20 // 21 //===----------------------------------------------------------------------===// 22 23 #ifndef LLVM_ADT_ILIST_H 24 #define LLVM_ADT_ILIST_H 25 26 #include "llvm/ADT/simple_ilist.h" 27 #include <cassert> 28 #include <cstddef> 29 #include <iterator> 30 31 namespace llvm { 32 33 /// Use delete by default for iplist and ilist. 34 /// 35 /// Specialize this to get different behaviour for ownership-related API. (If 36 /// you really want ownership semantics, consider using std::list or building 37 /// something like \a BumpPtrList.) 38 /// 39 /// \see ilist_noalloc_traits 40 template <typename NodeTy> struct ilist_alloc_traits { deleteNodeilist_alloc_traits41 static void deleteNode(NodeTy *V) { delete V; } 42 }; 43 44 /// Custom traits to do nothing on deletion. 45 /// 46 /// Specialize ilist_alloc_traits to inherit from this to disable the 47 /// non-intrusive deletion in iplist (which implies ownership). 48 /// 49 /// If you want purely intrusive semantics with no callbacks, consider using \a 50 /// simple_ilist instead. 51 /// 52 /// \code 53 /// template <> 54 /// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {}; 55 /// \endcode 56 template <typename NodeTy> struct ilist_noalloc_traits { deleteNodeilist_noalloc_traits57 static void deleteNode(NodeTy *V) {} 58 }; 59 60 /// Callbacks do nothing by default in iplist and ilist. 61 /// 62 /// Specialize this for to use callbacks for when nodes change their list 63 /// membership. 64 template <typename NodeTy> struct ilist_callback_traits { addNodeToListilist_callback_traits65 void addNodeToList(NodeTy *) {} removeNodeFromListilist_callback_traits66 void removeNodeFromList(NodeTy *) {} 67 68 /// Callback before transferring nodes to this list. The nodes may already be 69 /// in this same list. 70 template <class Iterator> transferNodesFromListilist_callback_traits71 void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/, 72 Iterator /*last*/) { 73 (void)OldList; 74 } 75 }; 76 77 /// A fragment for template traits for intrusive list that provides default 78 /// node related operations. 79 /// 80 /// TODO: Remove this layer of indirection. It's not necessary. 81 template <typename NodeTy> 82 struct ilist_node_traits : ilist_alloc_traits<NodeTy>, 83 ilist_callback_traits<NodeTy> {}; 84 85 /// Template traits for intrusive list. 86 /// 87 /// Customize callbacks and allocation semantics. 88 template <typename NodeTy> 89 struct ilist_traits : public ilist_node_traits<NodeTy> {}; 90 91 /// Const traits should never be instantiated. 92 template <typename Ty> struct ilist_traits<const Ty> {}; 93 94 namespace ilist_detail { 95 96 template <class T> T &make(); 97 98 /// Type trait to check for a traits class that has a getNext member (as a 99 /// canary for any of the ilist_nextprev_traits API). 100 template <class TraitsT, class NodeT> struct HasGetNext { 101 typedef char Yes[1]; 102 typedef char No[2]; 103 template <size_t N> struct SFINAE {}; 104 105 template <class U> 106 static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0); 107 template <class> static No &test(...); 108 109 public: 110 static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); 111 }; 112 113 /// Type trait to check for a traits class that has a createSentinel member (as 114 /// a canary for any of the ilist_sentinel_traits API). 115 template <class TraitsT> struct HasCreateSentinel { 116 typedef char Yes[1]; 117 typedef char No[2]; 118 119 template <class U> 120 static Yes &test(U *I, decltype(I->createSentinel()) * = 0); 121 template <class> static No &test(...); 122 123 public: 124 static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); 125 }; 126 127 /// Type trait to check for a traits class that has a createNode member. 128 /// Allocation should be managed in a wrapper class, instead of in 129 /// ilist_traits. 130 template <class TraitsT, class NodeT> struct HasCreateNode { 131 typedef char Yes[1]; 132 typedef char No[2]; 133 template <size_t N> struct SFINAE {}; 134 135 template <class U> 136 static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0); 137 template <class> static No &test(...); 138 139 public: 140 static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); 141 }; 142 143 template <class TraitsT, class NodeT> struct HasObsoleteCustomization { 144 static const bool value = HasGetNext<TraitsT, NodeT>::value || 145 HasCreateSentinel<TraitsT>::value || 146 HasCreateNode<TraitsT, NodeT>::value; 147 }; 148 149 } // end namespace ilist_detail 150 151 //===----------------------------------------------------------------------===// 152 // 153 /// A wrapper around an intrusive list with callbacks and non-intrusive 154 /// ownership. 155 /// 156 /// This wraps a purely intrusive list (like simple_ilist) with a configurable 157 /// traits class. The traits can implement callbacks and customize the 158 /// ownership semantics. 159 /// 160 /// This is a subset of ilist functionality that can safely be used on nodes of 161 /// polymorphic types, i.e. a heterogeneous list with a common base class that 162 /// holds the next/prev pointers. The only state of the list itself is an 163 /// ilist_sentinel, which holds pointers to the first and last nodes in the 164 /// list. 165 template <class IntrusiveListT, class TraitsT> 166 class iplist_impl : public TraitsT, IntrusiveListT { 167 typedef IntrusiveListT base_list_type; 168 169 public: 170 typedef typename base_list_type::pointer pointer; 171 typedef typename base_list_type::const_pointer const_pointer; 172 typedef typename base_list_type::reference reference; 173 typedef typename base_list_type::const_reference const_reference; 174 typedef typename base_list_type::value_type value_type; 175 typedef typename base_list_type::size_type size_type; 176 typedef typename base_list_type::difference_type difference_type; 177 typedef typename base_list_type::iterator iterator; 178 typedef typename base_list_type::const_iterator const_iterator; 179 typedef typename base_list_type::reverse_iterator reverse_iterator; 180 typedef 181 typename base_list_type::const_reverse_iterator const_reverse_iterator; 182 183 private: 184 // TODO: Drop this assertion and the transitive type traits anytime after 185 // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code 186 // update). 187 static_assert( 188 !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value, 189 "ilist customization points have changed!"); 190 191 static bool op_less(const_reference L, const_reference R) { return L < R; } 192 static bool op_equal(const_reference L, const_reference R) { return L == R; } 193 194 public: 195 iplist_impl() = default; 196 197 iplist_impl(const iplist_impl &) = delete; 198 iplist_impl &operator=(const iplist_impl &) = delete; 199 200 iplist_impl(iplist_impl &&X) 201 : TraitsT(std::move(static_cast<TraitsT &>(X))), 202 IntrusiveListT(std::move(static_cast<IntrusiveListT &>(X))) {} 203 iplist_impl &operator=(iplist_impl &&X) { 204 *static_cast<TraitsT *>(this) = std::move(static_cast<TraitsT &>(X)); 205 *static_cast<IntrusiveListT *>(this) = 206 std::move(static_cast<IntrusiveListT &>(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 // 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