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_traits trait class is used to gain access to the next and previous 15 // fields of the node type that the list is instantiated with. If it is not 16 // specialized, the list defaults to using the getPrev(), getNext() method calls 17 // to get the next and previous pointers. 18 // 19 // The ilist class itself, should be a plug in replacement for list, assuming 20 // that the nodes contain next/prev pointers. This list replacement does not 21 // provide a constant time size() method, so be careful to use empty() when you 22 // really want to know if it's empty. 23 // 24 // The ilist class is implemented by allocating a 'tail' node when the list is 25 // created (using ilist_traits<>::createSentinel()). This tail node is 26 // absolutely required because the user must be able to compute end()-1. Because 27 // of this, users of the direct next/prev links will see an extra link on the 28 // end of the list, which should be ignored. 29 // 30 // Requirements for a user of this list: 31 // 32 // 1. The user must provide {g|s}et{Next|Prev} methods, or specialize 33 // ilist_traits to provide an alternate way of getting and setting next and 34 // prev links. 35 // 36 //===----------------------------------------------------------------------===// 37 38 #ifndef LLVM_ADT_ILIST_H 39 #define LLVM_ADT_ILIST_H 40 41 #include "llvm/Support/Compiler.h" 42 #include <algorithm> 43 #include <cassert> 44 #include <cstddef> 45 #include <iterator> 46 47 namespace llvm { 48 49 template<typename NodeTy, typename Traits> class iplist; 50 template<typename NodeTy> class ilist_iterator; 51 52 /// ilist_nextprev_traits - A fragment for template traits for intrusive list 53 /// that provides default next/prev implementations for common operations. 54 /// 55 template<typename NodeTy> 56 struct ilist_nextprev_traits { getPrevilist_nextprev_traits57 static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } getNextilist_nextprev_traits58 static NodeTy *getNext(NodeTy *N) { return N->getNext(); } getPrevilist_nextprev_traits59 static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } getNextilist_nextprev_traits60 static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } 61 setPrevilist_nextprev_traits62 static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } setNextilist_nextprev_traits63 static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } 64 }; 65 66 template<typename NodeTy> 67 struct ilist_traits; 68 69 /// ilist_sentinel_traits - A fragment for template traits for intrusive list 70 /// that provides default sentinel implementations for common operations. 71 /// 72 /// ilist_sentinel_traits implements a lazy dynamic sentinel allocation 73 /// strategy. The sentinel is stored in the prev field of ilist's Head. 74 /// 75 template<typename NodeTy> 76 struct ilist_sentinel_traits { 77 /// createSentinel - create the dynamic sentinel createSentinelilist_sentinel_traits78 static NodeTy *createSentinel() { return new NodeTy(); } 79 80 /// destroySentinel - deallocate the dynamic sentinel destroySentinelilist_sentinel_traits81 static void destroySentinel(NodeTy *N) { delete N; } 82 83 /// provideInitialHead - when constructing an ilist, provide a starting 84 /// value for its Head 85 /// @return null node to indicate that it needs to be allocated later provideInitialHeadilist_sentinel_traits86 static NodeTy *provideInitialHead() { return nullptr; } 87 88 /// ensureHead - make sure that Head is either already 89 /// initialized or assigned a fresh sentinel 90 /// @return the sentinel ensureHeadilist_sentinel_traits91 static NodeTy *ensureHead(NodeTy *&Head) { 92 if (!Head) { 93 Head = ilist_traits<NodeTy>::createSentinel(); 94 ilist_traits<NodeTy>::noteHead(Head, Head); 95 ilist_traits<NodeTy>::setNext(Head, nullptr); 96 return Head; 97 } 98 return ilist_traits<NodeTy>::getPrev(Head); 99 } 100 101 /// noteHead - stash the sentinel into its default location noteHeadilist_sentinel_traits102 static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { 103 ilist_traits<NodeTy>::setPrev(NewHead, Sentinel); 104 } 105 }; 106 107 template <typename NodeTy> class ilist_half_node; 108 template <typename NodeTy> class ilist_node; 109 110 /// Traits with an embedded ilist_node as a sentinel. 111 /// 112 /// FIXME: The downcast in createSentinel() is UB. 113 template <typename NodeTy> struct ilist_embedded_sentinel_traits { 114 /// Get hold of the node that marks the end of the list. createSentinelilist_embedded_sentinel_traits115 NodeTy *createSentinel() const { 116 // Since i(p)lists always publicly derive from their corresponding traits, 117 // placing a data member in this class will augment the i(p)list. But since 118 // the NodeTy is expected to be publicly derive from ilist_node<NodeTy>, 119 // there is a legal viable downcast from it to NodeTy. We use this trick to 120 // superimpose an i(p)list with a "ghostly" NodeTy, which becomes the 121 // sentinel. Dereferencing the sentinel is forbidden (save the 122 // ilist_node<NodeTy>), so no one will ever notice the superposition. 123 return static_cast<NodeTy *>(&Sentinel); 124 } destroySentinelilist_embedded_sentinel_traits125 static void destroySentinel(NodeTy *) {} 126 provideInitialHeadilist_embedded_sentinel_traits127 NodeTy *provideInitialHead() const { return createSentinel(); } ensureHeadilist_embedded_sentinel_traits128 NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } noteHeadilist_embedded_sentinel_traits129 static void noteHead(NodeTy *, NodeTy *) {} 130 131 private: 132 mutable ilist_node<NodeTy> Sentinel; 133 }; 134 135 /// Trait with an embedded ilist_half_node as a sentinel. 136 /// 137 /// FIXME: The downcast in createSentinel() is UB. 138 template <typename NodeTy> struct ilist_half_embedded_sentinel_traits { 139 /// Get hold of the node that marks the end of the list. createSentinelilist_half_embedded_sentinel_traits140 NodeTy *createSentinel() const { 141 // See comment in ilist_embedded_sentinel_traits::createSentinel(). 142 return static_cast<NodeTy *>(&Sentinel); 143 } destroySentinelilist_half_embedded_sentinel_traits144 static void destroySentinel(NodeTy *) {} 145 provideInitialHeadilist_half_embedded_sentinel_traits146 NodeTy *provideInitialHead() const { return createSentinel(); } ensureHeadilist_half_embedded_sentinel_traits147 NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } noteHeadilist_half_embedded_sentinel_traits148 static void noteHead(NodeTy *, NodeTy *) {} 149 150 private: 151 mutable ilist_half_node<NodeTy> Sentinel; 152 }; 153 154 /// ilist_node_traits - A fragment for template traits for intrusive list 155 /// that provides default node related operations. 156 /// 157 template<typename NodeTy> 158 struct ilist_node_traits { createNodeilist_node_traits159 static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } deleteNodeilist_node_traits160 static void deleteNode(NodeTy *V) { delete V; } 161 addNodeToListilist_node_traits162 void addNodeToList(NodeTy *) {} removeNodeFromListilist_node_traits163 void removeNodeFromList(NodeTy *) {} transferNodesFromListilist_node_traits164 void transferNodesFromList(ilist_node_traits & /*SrcTraits*/, 165 ilist_iterator<NodeTy> /*first*/, 166 ilist_iterator<NodeTy> /*last*/) {} 167 }; 168 169 /// ilist_default_traits - Default template traits for intrusive list. 170 /// By inheriting from this, you can easily use default implementations 171 /// for all common operations. 172 /// 173 template<typename NodeTy> 174 struct ilist_default_traits : public ilist_nextprev_traits<NodeTy>, 175 public ilist_sentinel_traits<NodeTy>, 176 public ilist_node_traits<NodeTy> { 177 }; 178 179 // Template traits for intrusive list. By specializing this template class, you 180 // can change what next/prev fields are used to store the links... 181 template<typename NodeTy> 182 struct ilist_traits : public ilist_default_traits<NodeTy> {}; 183 184 // Const traits are the same as nonconst traits... 185 template<typename Ty> 186 struct ilist_traits<const Ty> : public ilist_traits<Ty> {}; 187 188 //===----------------------------------------------------------------------===// 189 // ilist_iterator<Node> - Iterator for intrusive list. 190 // 191 template<typename NodeTy> 192 class ilist_iterator 193 : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { 194 195 public: 196 typedef ilist_traits<NodeTy> Traits; 197 typedef std::iterator<std::bidirectional_iterator_tag, 198 NodeTy, ptrdiff_t> super; 199 200 typedef typename super::value_type value_type; 201 typedef typename super::difference_type difference_type; 202 typedef typename super::pointer pointer; 203 typedef typename super::reference reference; 204 private: 205 pointer NodePtr; 206 207 // ilist_iterator is not a random-access iterator, but it has an 208 // implicit conversion to pointer-type, which is. Declare (but 209 // don't define) these functions as private to help catch 210 // accidental misuse. 211 void operator[](difference_type) const; 212 void operator+(difference_type) const; 213 void operator-(difference_type) const; 214 void operator+=(difference_type) const; 215 void operator-=(difference_type) const; 216 template<class T> void operator<(T) const; 217 template<class T> void operator<=(T) const; 218 template<class T> void operator>(T) const; 219 template<class T> void operator>=(T) const; 220 template<class T> void operator-(T) const; 221 public: 222 223 explicit ilist_iterator(pointer NP) : NodePtr(NP) {} 224 explicit ilist_iterator(reference NR) : NodePtr(&NR) {} 225 ilist_iterator() : NodePtr(nullptr) {} 226 227 // This is templated so that we can allow constructing a const iterator from 228 // a nonconst iterator... 229 template<class node_ty> 230 ilist_iterator(const ilist_iterator<node_ty> &RHS) 231 : NodePtr(RHS.getNodePtrUnchecked()) {} 232 233 // This is templated so that we can allow assigning to a const iterator from 234 // a nonconst iterator... 235 template<class node_ty> 236 const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { 237 NodePtr = RHS.getNodePtrUnchecked(); 238 return *this; 239 } 240 241 void reset(pointer NP) { NodePtr = NP; } 242 243 // Accessors... 244 explicit operator pointer() const { 245 return NodePtr; 246 } 247 248 reference operator*() const { 249 return *NodePtr; 250 } 251 pointer operator->() const { return &operator*(); } 252 253 // Comparison operators 254 template <class Y> bool operator==(const ilist_iterator<Y> &RHS) const { 255 return NodePtr == RHS.getNodePtrUnchecked(); 256 } 257 template <class Y> bool operator!=(const ilist_iterator<Y> &RHS) const { 258 return NodePtr != RHS.getNodePtrUnchecked(); 259 } 260 261 // Increment and decrement operators... 262 ilist_iterator &operator--() { // predecrement - Back up 263 NodePtr = Traits::getPrev(NodePtr); 264 assert(NodePtr && "--'d off the beginning of an ilist!"); 265 return *this; 266 } 267 ilist_iterator &operator++() { // preincrement - Advance 268 NodePtr = Traits::getNext(NodePtr); 269 return *this; 270 } 271 ilist_iterator operator--(int) { // postdecrement operators... 272 ilist_iterator tmp = *this; 273 --*this; 274 return tmp; 275 } 276 ilist_iterator operator++(int) { // postincrement operators... 277 ilist_iterator tmp = *this; 278 ++*this; 279 return tmp; 280 } 281 282 // Internal interface, do not use... 283 pointer getNodePtrUnchecked() const { return NodePtr; } 284 }; 285 286 // These are to catch errors when people try to use them as random access 287 // iterators. 288 template<typename T> 289 void operator-(int, ilist_iterator<T>) = delete; 290 template<typename T> 291 void operator-(ilist_iterator<T>,int) = delete; 292 293 template<typename T> 294 void operator+(int, ilist_iterator<T>) = delete; 295 template<typename T> 296 void operator+(ilist_iterator<T>,int) = delete; 297 298 // operator!=/operator== - Allow mixed comparisons without dereferencing 299 // the iterator, which could very likely be pointing to end(). 300 template<typename T> 301 bool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { 302 return LHS != RHS.getNodePtrUnchecked(); 303 } 304 template<typename T> 305 bool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { 306 return LHS == RHS.getNodePtrUnchecked(); 307 } 308 template<typename T> 309 bool operator!=(T* LHS, const ilist_iterator<T> &RHS) { 310 return LHS != RHS.getNodePtrUnchecked(); 311 } 312 template<typename T> 313 bool operator==(T* LHS, const ilist_iterator<T> &RHS) { 314 return LHS == RHS.getNodePtrUnchecked(); 315 } 316 317 318 // Allow ilist_iterators to convert into pointers to a node automatically when 319 // used by the dyn_cast, cast, isa mechanisms... 320 321 template<typename From> struct simplify_type; 322 323 template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { 324 typedef NodeTy* SimpleType; 325 326 static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) { 327 return &*Node; 328 } 329 }; 330 template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { 331 typedef /*const*/ NodeTy* SimpleType; 332 333 static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 334 return &*Node; 335 } 336 }; 337 338 339 //===----------------------------------------------------------------------===// 340 // 341 /// iplist - The subset of list functionality that can safely be used on nodes 342 /// of polymorphic types, i.e. a heterogeneous list with a common base class that 343 /// holds the next/prev pointers. The only state of the list itself is a single 344 /// pointer to the head of the list. 345 /// 346 /// This list can be in one of three interesting states: 347 /// 1. The list may be completely unconstructed. In this case, the head 348 /// pointer is null. When in this form, any query for an iterator (e.g. 349 /// begin() or end()) causes the list to transparently change to state #2. 350 /// 2. The list may be empty, but contain a sentinel for the end iterator. This 351 /// sentinel is created by the Traits::createSentinel method and is a link 352 /// in the list. When the list is empty, the pointer in the iplist points 353 /// to the sentinel. Once the sentinel is constructed, it 354 /// is not destroyed until the list is. 355 /// 3. The list may contain actual objects in it, which are stored as a doubly 356 /// linked list of nodes. One invariant of the list is that the predecessor 357 /// of the first node in the list always points to the last node in the list, 358 /// and the successor pointer for the sentinel (which always stays at the 359 /// end of the list) is always null. 360 /// 361 template<typename NodeTy, typename Traits=ilist_traits<NodeTy> > 362 class iplist : public Traits { 363 mutable NodeTy *Head; 364 365 // Use the prev node pointer of 'head' as the tail pointer. This is really a 366 // circularly linked list where we snip the 'next' link from the sentinel node 367 // back to the first node in the list (to preserve assertions about going off 368 // the end of the list). 369 NodeTy *getTail() { return this->ensureHead(Head); } 370 const NodeTy *getTail() const { return this->ensureHead(Head); } 371 void setTail(NodeTy *N) const { this->noteHead(Head, N); } 372 373 /// CreateLazySentinel - This method verifies whether the sentinel for the 374 /// list has been created and lazily makes it if not. 375 void CreateLazySentinel() const { 376 this->ensureHead(Head); 377 } 378 379 static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } 380 static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } 381 382 // No fundamental reason why iplist can't be copyable, but the default 383 // copy/copy-assign won't do. 384 iplist(const iplist &) = delete; 385 void operator=(const iplist &) = delete; 386 387 public: 388 typedef NodeTy *pointer; 389 typedef const NodeTy *const_pointer; 390 typedef NodeTy &reference; 391 typedef const NodeTy &const_reference; 392 typedef NodeTy value_type; 393 typedef ilist_iterator<NodeTy> iterator; 394 typedef ilist_iterator<const NodeTy> const_iterator; 395 typedef size_t size_type; 396 typedef ptrdiff_t difference_type; 397 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 398 typedef std::reverse_iterator<iterator> reverse_iterator; 399 400 iplist() : Head(this->provideInitialHead()) {} 401 ~iplist() { 402 if (!Head) return; 403 clear(); 404 Traits::destroySentinel(getTail()); 405 } 406 407 // Iterator creation methods. 408 iterator begin() { 409 CreateLazySentinel(); 410 return iterator(Head); 411 } 412 const_iterator begin() const { 413 CreateLazySentinel(); 414 return const_iterator(Head); 415 } 416 iterator end() { 417 CreateLazySentinel(); 418 return iterator(getTail()); 419 } 420 const_iterator end() const { 421 CreateLazySentinel(); 422 return const_iterator(getTail()); 423 } 424 425 // reverse iterator creation methods. 426 reverse_iterator rbegin() { return reverse_iterator(end()); } 427 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 428 reverse_iterator rend() { return reverse_iterator(begin()); } 429 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 430 431 432 // Miscellaneous inspection routines. 433 size_type max_size() const { return size_type(-1); } 434 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 435 return !Head || Head == getTail(); 436 } 437 438 // Front and back accessor functions... 439 reference front() { 440 assert(!empty() && "Called front() on empty list!"); 441 return *Head; 442 } 443 const_reference front() const { 444 assert(!empty() && "Called front() on empty list!"); 445 return *Head; 446 } 447 reference back() { 448 assert(!empty() && "Called back() on empty list!"); 449 return *this->getPrev(getTail()); 450 } 451 const_reference back() const { 452 assert(!empty() && "Called back() on empty list!"); 453 return *this->getPrev(getTail()); 454 } 455 456 void swap(iplist &RHS) { 457 assert(0 && "Swap does not use list traits callback correctly yet!"); 458 std::swap(Head, RHS.Head); 459 } 460 461 iterator insert(iterator where, NodeTy *New) { 462 NodeTy *CurNode = where.getNodePtrUnchecked(); 463 NodeTy *PrevNode = this->getPrev(CurNode); 464 this->setNext(New, CurNode); 465 this->setPrev(New, PrevNode); 466 467 if (CurNode != Head) // Is PrevNode off the beginning of the list? 468 this->setNext(PrevNode, New); 469 else 470 Head = New; 471 this->setPrev(CurNode, New); 472 473 this->addNodeToList(New); // Notify traits that we added a node... 474 return iterator(New); 475 } 476 477 iterator insertAfter(iterator where, NodeTy *New) { 478 if (empty()) 479 return insert(begin(), New); 480 else 481 return insert(++where, New); 482 } 483 484 NodeTy *remove(iterator &IT) { 485 assert(IT != end() && "Cannot remove end of list!"); 486 NodeTy *Node = &*IT; 487 NodeTy *NextNode = this->getNext(Node); 488 NodeTy *PrevNode = this->getPrev(Node); 489 490 if (Node != Head) // Is PrevNode off the beginning of the list? 491 this->setNext(PrevNode, NextNode); 492 else 493 Head = NextNode; 494 this->setPrev(NextNode, PrevNode); 495 IT.reset(NextNode); 496 this->removeNodeFromList(Node); // Notify traits that we removed a node... 497 498 // Set the next/prev pointers of the current node to null. This isn't 499 // strictly required, but this catches errors where a node is removed from 500 // an ilist (and potentially deleted) with iterators still pointing at it. 501 // When those iterators are incremented or decremented, they will assert on 502 // the null next/prev pointer instead of "usually working". 503 this->setNext(Node, nullptr); 504 this->setPrev(Node, nullptr); 505 return Node; 506 } 507 508 NodeTy *remove(const iterator &IT) { 509 iterator MutIt = IT; 510 return remove(MutIt); 511 } 512 513 NodeTy *remove(NodeTy *IT) { return remove(iterator(IT)); } 514 NodeTy *remove(NodeTy &IT) { return remove(iterator(IT)); } 515 516 // erase - remove a node from the controlled sequence... and delete it. 517 iterator erase(iterator where) { 518 this->deleteNode(remove(where)); 519 return where; 520 } 521 522 iterator erase(NodeTy *IT) { return erase(iterator(IT)); } 523 iterator erase(NodeTy &IT) { return erase(iterator(IT)); } 524 525 /// Remove all nodes from the list like clear(), but do not call 526 /// removeNodeFromList() or deleteNode(). 527 /// 528 /// This should only be used immediately before freeing nodes in bulk to 529 /// avoid traversing the list and bringing all the nodes into cache. 530 void clearAndLeakNodesUnsafely() { 531 if (Head) { 532 Head = getTail(); 533 this->setPrev(Head, Head); 534 } 535 } 536 537 private: 538 // transfer - The heart of the splice function. Move linked list nodes from 539 // [first, last) into position. 540 // 541 void transfer(iterator position, iplist &L2, iterator first, iterator last) { 542 assert(first != last && "Should be checked by callers"); 543 // Position cannot be contained in the range to be transferred. 544 // Check for the most common mistake. 545 assert(position != first && 546 "Insertion point can't be one of the transferred nodes"); 547 548 if (position != last) { 549 // Note: we have to be careful about the case when we move the first node 550 // in the list. This node is the list sentinel node and we can't move it. 551 NodeTy *ThisSentinel = getTail(); 552 setTail(nullptr); 553 NodeTy *L2Sentinel = L2.getTail(); 554 L2.setTail(nullptr); 555 556 // Remove [first, last) from its old position. 557 NodeTy *First = &*first, *Prev = this->getPrev(First); 558 NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next); 559 if (Prev) 560 this->setNext(Prev, Next); 561 else 562 L2.Head = Next; 563 this->setPrev(Next, Prev); 564 565 // Splice [first, last) into its new position. 566 NodeTy *PosNext = position.getNodePtrUnchecked(); 567 NodeTy *PosPrev = this->getPrev(PosNext); 568 569 // Fix head of list... 570 if (PosPrev) 571 this->setNext(PosPrev, First); 572 else 573 Head = First; 574 this->setPrev(First, PosPrev); 575 576 // Fix end of list... 577 this->setNext(Last, PosNext); 578 this->setPrev(PosNext, Last); 579 580 this->transferNodesFromList(L2, iterator(First), iterator(PosNext)); 581 582 // Now that everything is set, restore the pointers to the list sentinels. 583 L2.setTail(L2Sentinel); 584 setTail(ThisSentinel); 585 } 586 } 587 588 public: 589 590 //===----------------------------------------------------------------------=== 591 // Functionality derived from other functions defined above... 592 // 593 594 size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const { 595 if (!Head) return 0; // Don't require construction of sentinel if empty. 596 return std::distance(begin(), end()); 597 } 598 599 iterator erase(iterator first, iterator last) { 600 while (first != last) 601 first = erase(first); 602 return last; 603 } 604 605 void clear() { if (Head) erase(begin(), end()); } 606 607 // Front and back inserters... 608 void push_front(NodeTy *val) { insert(begin(), val); } 609 void push_back(NodeTy *val) { insert(end(), val); } 610 void pop_front() { 611 assert(!empty() && "pop_front() on empty list!"); 612 erase(begin()); 613 } 614 void pop_back() { 615 assert(!empty() && "pop_back() on empty list!"); 616 iterator t = end(); erase(--t); 617 } 618 619 // Special forms of insert... 620 template<class InIt> void insert(iterator where, InIt first, InIt last) { 621 for (; first != last; ++first) insert(where, *first); 622 } 623 624 // Splice members - defined in terms of transfer... 625 void splice(iterator where, iplist &L2) { 626 if (!L2.empty()) 627 transfer(where, L2, L2.begin(), L2.end()); 628 } 629 void splice(iterator where, iplist &L2, iterator first) { 630 iterator last = first; ++last; 631 if (where == first || where == last) return; // No change 632 transfer(where, L2, first, last); 633 } 634 void splice(iterator where, iplist &L2, iterator first, iterator last) { 635 if (first != last) transfer(where, L2, first, last); 636 } 637 void splice(iterator where, iplist &L2, NodeTy &N) { 638 splice(where, L2, iterator(N)); 639 } 640 void splice(iterator where, iplist &L2, NodeTy *N) { 641 splice(where, L2, iterator(N)); 642 } 643 644 template <class Compare> 645 void merge(iplist &Right, Compare comp) { 646 if (this == &Right) 647 return; 648 iterator First1 = begin(), Last1 = end(); 649 iterator First2 = Right.begin(), Last2 = Right.end(); 650 while (First1 != Last1 && First2 != Last2) { 651 if (comp(*First2, *First1)) { 652 iterator Next = First2; 653 transfer(First1, Right, First2, ++Next); 654 First2 = Next; 655 } else { 656 ++First1; 657 } 658 } 659 if (First2 != Last2) 660 transfer(Last1, Right, First2, Last2); 661 } 662 void merge(iplist &Right) { return merge(Right, op_less); } 663 664 template <class Compare> 665 void sort(Compare comp) { 666 // The list is empty, vacuously sorted. 667 if (empty()) 668 return; 669 // The list has a single element, vacuously sorted. 670 if (std::next(begin()) == end()) 671 return; 672 // Find the split point for the list. 673 iterator Center = begin(), End = begin(); 674 while (End != end() && std::next(End) != end()) { 675 Center = std::next(Center); 676 End = std::next(std::next(End)); 677 } 678 // Split the list into two. 679 iplist RightHalf; 680 RightHalf.splice(RightHalf.begin(), *this, Center, end()); 681 682 // Sort the two sublists. 683 sort(comp); 684 RightHalf.sort(comp); 685 686 // Merge the two sublists back together. 687 merge(RightHalf, comp); 688 } 689 void sort() { sort(op_less); } 690 691 /// \brief Get the previous node, or \c nullptr for the list head. 692 NodeTy *getPrevNode(NodeTy &N) const { 693 auto I = N.getIterator(); 694 if (I == begin()) 695 return nullptr; 696 return &*std::prev(I); 697 } 698 /// \brief Get the previous node, or \c nullptr for the list head. 699 const NodeTy *getPrevNode(const NodeTy &N) const { 700 return getPrevNode(const_cast<NodeTy &>(N)); 701 } 702 703 /// \brief Get the next node, or \c nullptr for the list tail. 704 NodeTy *getNextNode(NodeTy &N) const { 705 auto Next = std::next(N.getIterator()); 706 if (Next == end()) 707 return nullptr; 708 return &*Next; 709 } 710 /// \brief Get the next node, or \c nullptr for the list tail. 711 const NodeTy *getNextNode(const NodeTy &N) const { 712 return getNextNode(const_cast<NodeTy &>(N)); 713 } 714 }; 715 716 717 template<typename NodeTy> 718 struct ilist : public iplist<NodeTy> { 719 typedef typename iplist<NodeTy>::size_type size_type; 720 typedef typename iplist<NodeTy>::iterator iterator; 721 722 ilist() {} 723 ilist(const ilist &right) { 724 insert(this->begin(), right.begin(), right.end()); 725 } 726 explicit ilist(size_type count) { 727 insert(this->begin(), count, NodeTy()); 728 } 729 ilist(size_type count, const NodeTy &val) { 730 insert(this->begin(), count, val); 731 } 732 template<class InIt> ilist(InIt first, InIt last) { 733 insert(this->begin(), first, last); 734 } 735 736 // bring hidden functions into scope 737 using iplist<NodeTy>::insert; 738 using iplist<NodeTy>::push_front; 739 using iplist<NodeTy>::push_back; 740 741 // Main implementation here - Insert for a node passed by value... 742 iterator insert(iterator where, const NodeTy &val) { 743 return insert(where, this->createNode(val)); 744 } 745 746 747 // Front and back inserters... 748 void push_front(const NodeTy &val) { insert(this->begin(), val); } 749 void push_back(const NodeTy &val) { insert(this->end(), val); } 750 751 void insert(iterator where, size_type count, const NodeTy &val) { 752 for (; count != 0; --count) insert(where, val); 753 } 754 755 // Assign special forms... 756 void assign(size_type count, const NodeTy &val) { 757 iterator I = this->begin(); 758 for (; I != this->end() && count != 0; ++I, --count) 759 *I = val; 760 if (count != 0) 761 insert(this->end(), val, val); 762 else 763 erase(I, this->end()); 764 } 765 template<class InIt> void assign(InIt first1, InIt last1) { 766 iterator first2 = this->begin(), last2 = this->end(); 767 for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) 768 *first1 = *first2; 769 if (first2 == last2) 770 erase(first1, last1); 771 else 772 insert(last1, first2, last2); 773 } 774 775 776 // Resize members... 777 void resize(size_type newsize, NodeTy val) { 778 iterator i = this->begin(); 779 size_type len = 0; 780 for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ; 781 782 if (len == newsize) 783 erase(i, this->end()); 784 else // i == end() 785 insert(this->end(), newsize - len, val); 786 } 787 void resize(size_type newsize) { resize(newsize, NodeTy()); } 788 }; 789 790 } // End llvm namespace 791 792 namespace std { 793 // Ensure that swap uses the fast list swap... 794 template<class Ty> 795 void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 796 Left.swap(Right); 797 } 798 } // End 'std' extensions... 799 800 #endif // LLVM_ADT_ILIST_H 801