ilist.h revision 218893
162587Sitojun//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// 295023Ssuz// 362587Sitojun// The LLVM Compiler Infrastructure 4139823Simp// 554263Sshin// This file is distributed under the University of Illinois Open Source 654263Sshin// License. See LICENSE.TXT for details. 754263Sshin// 854263Sshin//===----------------------------------------------------------------------===// 954263Sshin// 1054263Sshin// This file defines classes to implement an intrusive doubly linked list class 1154263Sshin// (i.e. each node of the list must contain a next and previous field for the 1254263Sshin// list. 1354263Sshin// 1454263Sshin// The ilist_traits trait class is used to gain access to the next and previous 1554263Sshin// fields of the node type that the list is instantiated with. If it is not 1654263Sshin// specialized, the list defaults to using the getPrev(), getNext() method calls 1754263Sshin// to get the next and previous pointers. 1854263Sshin// 1954263Sshin// The ilist class itself, should be a plug in replacement for list, assuming 2054263Sshin// that the nodes contain next/prev pointers. This list replacement does not 2154263Sshin// provide a constant time size() method, so be careful to use empty() when you 2254263Sshin// really want to know if it's empty. 2354263Sshin// 2454263Sshin// The ilist class is implemented by allocating a 'tail' node when the list is 2554263Sshin// created (using ilist_traits<>::createSentinel()). This tail node is 2654263Sshin// absolutely required because the user must be able to compute end()-1. Because 2754263Sshin// of this, users of the direct next/prev links will see an extra link on the 2854263Sshin// end of the list, which should be ignored. 2954263Sshin// 3054263Sshin// Requirements for a user of this list: 3154263Sshin// 3254263Sshin// 1. The user must provide {g|s}et{Next|Prev} methods, or specialize 3354263Sshin// ilist_traits to provide an alternate way of getting and setting next and 3454263Sshin// prev links. 35101739Srwatson// 3654263Sshin//===----------------------------------------------------------------------===// 3754263Sshin 3854263Sshin#ifndef LLVM_ADT_ILIST_H 3954263Sshin#define LLVM_ADT_ILIST_H 4054263Sshin 4154263Sshin#include <algorithm> 42129880Sphk#include <cassert> 4354263Sshin#include <cstddef> 4454263Sshin#include <iterator> 4554263Sshin 4654263Sshinnamespace llvm { 4791270Sbrooks 4854263Sshintemplate<typename NodeTy, typename Traits> class iplist; 49178888Sjuliantemplate<typename NodeTy> class ilist_iterator; 5062587Sitojun 5179106Sbrooks/// ilist_nextprev_traits - A fragment for template traits for intrusive list 52181803Sbz/// that provides default next/prev implementations for common operations. 5354263Sshin/// 5454263Sshintemplate<typename NodeTy> 5554263Sshinstruct ilist_nextprev_traits { 56130933Sbrooks static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } 5754263Sshin static NodeTy *getNext(NodeTy *N) { return N->getNext(); } 5854263Sshin static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } 5954263Sshin static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } 6054263Sshin 6154263Sshin static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } 6254263Sshin static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } 6354263Sshin}; 6478064Sume 6578064Sumetemplate<typename NodeTy> 6654263Sshinstruct ilist_traits; 6754263Sshin 6879106Sbrooks/// ilist_sentinel_traits - A fragment for template traits for intrusive list 6954263Sshin/// that provides default sentinel implementations for common operations. 7054263Sshin/// 7154263Sshin/// ilist_sentinel_traits implements a lazy dynamic sentinel allocation 7254263Sshin/// strategy. The sentinel is stored in the prev field of ilist's Head. 7354263Sshin/// 7454263Sshintemplate<typename NodeTy> 7554263Sshinstruct ilist_sentinel_traits { 7654263Sshin /// createSentinel - create the dynamic sentinel 7754263Sshin static NodeTy *createSentinel() { return new NodeTy(); } 78148385Sume 7954263Sshin /// destroySentinel - deallocate the dynamic sentinel 8062587Sitojun static void destroySentinel(NodeTy *N) { delete N; } 8154263Sshin 8254263Sshin /// provideInitialHead - when constructing an ilist, provide a starting 8362587Sitojun /// value for its Head 84153621Sthompsa /// @return null node to indicate that it needs to be allocated later 85153621Sthompsa static NodeTy *provideInitialHead() { return 0; } 8654263Sshin 8754263Sshin /// ensureHead - make sure that Head is either already 88163606Srwatson /// initialized or assigned a fresh sentinel 89163606Srwatson /// @return the sentinel 9079106Sbrooks static NodeTy *ensureHead(NodeTy *&Head) { 9162587Sitojun if (!Head) { 92127305Srwatson Head = ilist_traits<NodeTy>::createSentinel(); 93127898Sru ilist_traits<NodeTy>::noteHead(Head, Head); 94127305Srwatson ilist_traits<NodeTy>::setNext(Head, 0); 95127305Srwatson return Head; 9679106Sbrooks } 9789065Smsmith return ilist_traits<NodeTy>::getPrev(Head); 9879106Sbrooks } 9983998Sbrooks 10083998Sbrooks /// noteHead - stash the sentinel into its default location 10183998Sbrooks static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { 10283998Sbrooks ilist_traits<NodeTy>::setPrev(NewHead, Sentinel); 10383998Sbrooks } 104153621Sthompsa}; 105160195Ssam 106128209Sbrooks/// ilist_node_traits - A fragment for template traits for intrusive list 10779106Sbrooks/// that provides default node related operations. 108130933Sbrooks/// 10979106Sbrookstemplate<typename NodeTy> 11092725Salfredstruct ilist_node_traits { 11179106Sbrooks static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } 11291270Sbrooks static void deleteNode(NodeTy *V) { delete V; } 11391270Sbrooks 11491270Sbrooks void addNodeToList(NodeTy *) {} 11562587Sitojun void removeNodeFromList(NodeTy *) {} 11662587Sitojun void transferNodesFromList(ilist_node_traits & /*SrcTraits*/, 11791270Sbrooks ilist_iterator<NodeTy> /*first*/, 11862587Sitojun ilist_iterator<NodeTy> /*last*/) {} 11962587Sitojun}; 12062587Sitojun 12195023Ssuz/// ilist_default_traits - Default template traits for intrusive list. 12262587Sitojun/// By inheriting from this, you can easily use default implementations 12362587Sitojun/// for all common operations. 12462587Sitojun/// 12562587Sitojuntemplate<typename NodeTy> 126183550Szecstruct ilist_default_traits : public ilist_nextprev_traits<NodeTy>, 12762587Sitojun public ilist_sentinel_traits<NodeTy>, 128183550Szec public ilist_node_traits<NodeTy> { 129183550Szec}; 130183550Szec 13162587Sitojun// Template traits for intrusive list. By specializing this template class, you 132183550Szec// can change what next/prev fields are used to store the links... 133183550Szectemplate<typename NodeTy> 134183550Szecstruct ilist_traits : public ilist_default_traits<NodeTy> {}; 135183550Szec 136183550Szec// Const traits are the same as nonconst traits... 137183550Szectemplate<typename Ty> 13891270Sbrooksstruct ilist_traits<const Ty> : public ilist_traits<Ty> {}; 13991270Sbrooks 14091270Sbrooks//===----------------------------------------------------------------------===// 14191270Sbrooks// ilist_iterator<Node> - Iterator for intrusive list. 14291270Sbrooks// 14391270Sbrookstemplate<typename NodeTy> 14491270Sbrooksclass ilist_iterator 14591270Sbrooks : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { 14691270Sbrooks 14791270Sbrookspublic: 148183550Szec typedef ilist_traits<NodeTy> Traits; 149183550Szec typedef std::iterator<std::bidirectional_iterator_tag, 15091270Sbrooks NodeTy, ptrdiff_t> super; 151176879Sthompsa 152176879Sthompsa typedef typename super::value_type value_type; 153176879Sthompsa typedef typename super::difference_type difference_type; 154176879Sthompsa typedef typename super::pointer pointer; 155176879Sthompsa typedef typename super::reference reference; 156176879Sthompsaprivate: 157176879Sthompsa pointer NodePtr; 158176879Sthompsa 159128209Sbrooks // ilist_iterator is not a random-access iterator, but it has an 160160195Ssam // implicit conversion to pointer-type, which is. Declare (but 16179106Sbrooks // don't define) these functions as private to help catch 16292081Smux // accidental misuse. 163160195Ssam void operator[](difference_type) const; 16454263Sshin void operator+(difference_type) const; 165183550Szec void operator-(difference_type) const; 16678064Sume void operator+=(difference_type) const; 16754263Sshin void operator-=(difference_type) const; 168131672Sbms template<class T> void operator<(T) const; 169178888Sjulian template<class T> void operator<=(T) const; 170147256Sbrooks template<class T> void operator>(T) const; 171147256Sbrooks template<class T> void operator>=(T) const; 172147256Sbrooks template<class T> void operator-(T) const; 173147256Sbrookspublic: 174147256Sbrooks 17579106Sbrooks ilist_iterator(pointer NP) : NodePtr(NP) {} 176155037Sglebius ilist_iterator(reference NR) : NodePtr(&NR) {} 177155037Sglebius ilist_iterator() : NodePtr(0) {} 178147256Sbrooks 179147256Sbrooks // This is templated so that we can allow constructing a const iterator from 18079106Sbrooks // a nonconst iterator... 18179106Sbrooks template<class node_ty> 18262587Sitojun ilist_iterator(const ilist_iterator<node_ty> &RHS) 183147256Sbrooks : NodePtr(RHS.getNodePtrUnchecked()) {} 184147256Sbrooks 185147256Sbrooks // This is templated so that we can allow assigning to a const iterator from 18678064Sume // a nonconst iterator... 18779106Sbrooks template<class node_ty> 188147256Sbrooks const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { 18978064Sume NodePtr = RHS.getNodePtrUnchecked(); 190147256Sbrooks return *this; 191153621Sthompsa } 192147256Sbrooks 193147256Sbrooks // Accessors... 194147256Sbrooks operator pointer() const { 195147611Sdwmalone return NodePtr; 19683998Sbrooks } 197147256Sbrooks 198155037Sglebius reference operator*() const { 199155037Sglebius return *NodePtr; 200181803Sbz } 201155037Sglebius pointer operator->() const { return &operator*(); } 202155037Sglebius 203155037Sglebius // Comparison operators 20479106Sbrooks bool operator==(const ilist_iterator &RHS) const { 20579106Sbrooks return NodePtr == RHS.NodePtr; 206127305Srwatson } 207151266Sthompsa bool operator!=(const ilist_iterator &RHS) const { 208151266Sthompsa return NodePtr != RHS.NodePtr; 20979106Sbrooks } 21079106Sbrooks 211151266Sthompsa // Increment and decrement operators... 21279106Sbrooks ilist_iterator &operator--() { // predecrement - Back up 213151266Sthompsa NodePtr = Traits::getPrev(NodePtr); 214151266Sthompsa assert(NodePtr && "--'d off the beginning of an ilist!"); 215151266Sthompsa return *this; 216151266Sthompsa } 217127305Srwatson ilist_iterator &operator++() { // preincrement - Advance 218105293Sume NodePtr = Traits::getNext(NodePtr); 219105293Sume return *this; 220105293Sume } 221105293Sume ilist_iterator operator--(int) { // postdecrement operators... 222105293Sume ilist_iterator tmp = *this; 223105293Sume --*this; 224105293Sume return tmp; 22579106Sbrooks } 22679106Sbrooks ilist_iterator operator++(int) { // postincrement operators... 22779106Sbrooks ilist_iterator tmp = *this; 22879106Sbrooks ++*this; 229105293Sume return tmp; 23079106Sbrooks } 23183998Sbrooks 23283998Sbrooks // Internal interface, do not use... 23379106Sbrooks pointer getNodePtrUnchecked() const { return NodePtr; } 23479106Sbrooks}; 235147256Sbrooks 23679106Sbrooks// do not implement. this is to catch errors when people try to use 237155037Sglebius// them as random access iterators 238155037Sglebiustemplate<typename T> 23979106Sbrooksvoid operator-(int, ilist_iterator<T>); 24079106Sbrookstemplate<typename T> 24179106Sbrooksvoid operator-(ilist_iterator<T>,int); 24279106Sbrooks 24379106Sbrookstemplate<typename T> 24479106Sbrooksvoid operator+(int, ilist_iterator<T>); 24579106Sbrookstemplate<typename T> 24679106Sbrooksvoid operator+(ilist_iterator<T>,int); 24779106Sbrooks 24879106Sbrooks// operator!=/operator== - Allow mixed comparisons without dereferencing 24979106Sbrooks// the iterator, which could very likely be pointing to end(). 25079106Sbrookstemplate<typename T> 251127305Srwatsonbool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { 252181803Sbz return LHS != RHS.getNodePtrUnchecked(); 25379106Sbrooks} 25479106Sbrookstemplate<typename T> 25579106Sbrooksbool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { 256181803Sbz return LHS == RHS.getNodePtrUnchecked(); 25762587Sitojun} 25879106Sbrookstemplate<typename T> 25979106Sbrooksbool operator!=(T* LHS, const ilist_iterator<T> &RHS) { 26079106Sbrooks return LHS != RHS.getNodePtrUnchecked(); 26179106Sbrooks} 262127305Srwatsontemplate<typename T> 26379106Sbrooksbool operator==(T* LHS, const ilist_iterator<T> &RHS) { 264181803Sbz return LHS == RHS.getNodePtrUnchecked(); 26562587Sitojun} 26679106Sbrooks 267132199Sphk 268132199Sphk// Allow ilist_iterators to convert into pointers to a node automatically when 26954263Sshin// used by the dyn_cast, cast, isa mechanisms... 27079106Sbrooks 27154263Sshintemplate<typename From> struct simplify_type; 27254263Sshin 27379106Sbrookstemplate<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { 27479106Sbrooks typedef NodeTy* SimpleType; 27579106Sbrooks 27679106Sbrooks static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 27779106Sbrooks return &*Node; 27854263Sshin } 27979106Sbrooks}; 28083997Sbrookstemplate<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { 28179106Sbrooks typedef NodeTy* SimpleType; 282105293Sume 28362587Sitojun static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 28462587Sitojun return &*Node; 28562587Sitojun } 28662587Sitojun}; 28762587Sitojun 28862587Sitojun 28962587Sitojun//===----------------------------------------------------------------------===// 29062587Sitojun// 29162587Sitojun/// iplist - The subset of list functionality that can safely be used on nodes 29262587Sitojun/// of polymorphic types, i.e. a heterogenous list with a common base class that 29362587Sitojun/// holds the next/prev pointers. The only state of the list itself is a single 29462587Sitojun/// pointer to the head of the list. 29562587Sitojun/// 296147256Sbrooks/// This list can be in one of three interesting states: 29762587Sitojun/// 1. The list may be completely unconstructed. In this case, the head 29862587Sitojun/// pointer is null. When in this form, any query for an iterator (e.g. 29962587Sitojun/// begin() or end()) causes the list to transparently change to state #2. 30062587Sitojun/// 2. The list may be empty, but contain a sentinel for the end iterator. This 30162587Sitojun/// sentinel is created by the Traits::createSentinel method and is a link 30262587Sitojun/// in the list. When the list is empty, the pointer in the iplist points 30362587Sitojun/// to the sentinel. Once the sentinel is constructed, it 30462587Sitojun/// is not destroyed until the list is. 30562587Sitojun/// 3. The list may contain actual objects in it, which are stored as a doubly 30662587Sitojun/// linked list of nodes. One invariant of the list is that the predecessor 30762587Sitojun/// of the first node in the list always points to the last node in the list, 30862587Sitojun/// and the successor pointer for the sentinel (which always stays at the 30962587Sitojun/// end of the list) is always null. 31062587Sitojun/// 31162587Sitojuntemplate<typename NodeTy, typename Traits=ilist_traits<NodeTy> > 312153621Sthompsaclass iplist : public Traits { 313153621Sthompsa mutable NodeTy *Head; 314153621Sthompsa 31562587Sitojun // Use the prev node pointer of 'head' as the tail pointer. This is really a 31662587Sitojun // circularly linked list where we snip the 'next' link from the sentinel node 31762587Sitojun // back to the first node in the list (to preserve assertions about going off 31862587Sitojun // the end of the list). 319105339Sume NodeTy *getTail() { return this->ensureHead(Head); } 320105339Sume const NodeTy *getTail() const { return this->ensureHead(Head); } 321105339Sume void setTail(NodeTy *N) const { this->noteHead(Head, N); } 322105339Sume 32391327Sbrooks /// CreateLazySentinel - This method verifies whether the sentinel for the 32462587Sitojun /// list has been created and lazily makes it if not. 32562587Sitojun void CreateLazySentinel() const { 32662587Sitojun this->ensureHead(Head); 32762587Sitojun } 32862587Sitojun 32962587Sitojun static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } 33062587Sitojun static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } 33162587Sitojun 33262587Sitojun // No fundamental reason why iplist can't be copyable, but the default 33362587Sitojun // copy/copy-assign won't do. 33462587Sitojun iplist(const iplist &); // do not implement 335105293Sume void operator=(const iplist &); // do not implement 336105293Sume 33762587Sitojunpublic: 33862587Sitojun typedef NodeTy *pointer; 33962587Sitojun typedef const NodeTy *const_pointer; 34062587Sitojun typedef NodeTy &reference; 34162587Sitojun typedef const NodeTy &const_reference; 34262587Sitojun typedef NodeTy value_type; 34362587Sitojun typedef ilist_iterator<NodeTy> iterator; 34462587Sitojun typedef ilist_iterator<const NodeTy> const_iterator; 34562587Sitojun typedef size_t size_type; 34662587Sitojun typedef ptrdiff_t difference_type; 347153621Sthompsa typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 348153621Sthompsa typedef std::reverse_iterator<iterator> reverse_iterator; 349153621Sthompsa 350153621Sthompsa iplist() : Head(this->provideInitialHead()) {} 351153621Sthompsa ~iplist() { 352153621Sthompsa if (!Head) return; 353153621Sthompsa clear(); 354153621Sthompsa Traits::destroySentinel(getTail()); 355153621Sthompsa } 356153621Sthompsa 357153621Sthompsa // Iterator creation methods. 358153621Sthompsa iterator begin() { 359153621Sthompsa CreateLazySentinel(); 360153621Sthompsa return iterator(Head); 361153621Sthompsa } 362153621Sthompsa const_iterator begin() const { 363153621Sthompsa CreateLazySentinel(); 364153621Sthompsa return const_iterator(Head); 365153621Sthompsa } 366153621Sthompsa iterator end() { 367153621Sthompsa CreateLazySentinel(); 368153621Sthompsa return iterator(getTail()); 36954263Sshin } 37054263Sshin const_iterator end() const { 37154263Sshin CreateLazySentinel(); 37254263Sshin return const_iterator(getTail()); 37354263Sshin } 37454263Sshin 37554263Sshin // reverse iterator creation methods. 376183550Szec reverse_iterator rbegin() { return reverse_iterator(end()); } 377147256Sbrooks const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 378127898Sru reverse_iterator rend() { return reverse_iterator(begin()); } 37954263Sshin const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 380127898Sru 381147611Sdwmalone 38254263Sshin // Miscellaneous inspection routines. 383101182Srwatson size_type max_size() const { return size_type(-1); } 384172930Srwatson bool empty() const { return Head == 0 || Head == getTail(); } 385101739Srwatson 386101739Srwatson // Front and back accessor functions... 387101739Srwatson reference front() { 388101739Srwatson assert(!empty() && "Called front() on empty list!"); 389101182Srwatson return *Head; 390101182Srwatson } 39154263Sshin const_reference front() const { 39254263Sshin assert(!empty() && "Called front() on empty list!"); 393127898Sru return *Head; 394127898Sru } 395127898Sru reference back() { 39654263Sshin assert(!empty() && "Called back() on empty list!"); 39754263Sshin return *this->getPrev(getTail()); 398127898Sru } 399127898Sru const_reference back() const { 400127898Sru assert(!empty() && "Called back() on empty list!"); 401127898Sru return *this->getPrev(getTail()); 402127898Sru } 403127898Sru 404127898Sru void swap(iplist &RHS) { 405127898Sru assert(0 && "Swap does not use list traits callback correctly yet!"); 406127898Sru std::swap(Head, RHS.Head); 407127898Sru } 408127898Sru 409127898Sru iterator insert(iterator where, NodeTy *New) { 410127898Sru NodeTy *CurNode = where.getNodePtrUnchecked(); 411127898Sru NodeTy *PrevNode = this->getPrev(CurNode); 412181803Sbz this->setNext(New, CurNode); 41354263Sshin this->setPrev(New, PrevNode); 41454263Sshin 415127303Srwatson if (CurNode != Head) // Is PrevNode off the beginning of the list? 41654263Sshin this->setNext(PrevNode, New); 41754263Sshin else 41854263Sshin Head = New; 41954263Sshin this->setPrev(CurNode, New); 420127898Sru 421127898Sru this->addNodeToList(New); // Notify traits that we added a node... 422127898Sru return New; 423127898Sru } 424127898Sru 425127898Sru iterator insertAfter(iterator where, NodeTy *New) { 426127898Sru if (empty()) 427127898Sru return insert(begin(), New); 428127898Sru else 42962587Sitojun return insert(++where, New); 43054263Sshin } 431155037Sglebius 432155037Sglebius NodeTy *remove(iterator &IT) { 433155037Sglebius assert(IT != end() && "Cannot remove end of list!"); 43454263Sshin NodeTy *Node = &*IT; 43554263Sshin NodeTy *NextNode = this->getNext(Node); 436159174Sglebius NodeTy *PrevNode = this->getPrev(Node); 43754263Sshin 43854263Sshin if (Node != Head) // Is PrevNode off the beginning of the list? 43954263Sshin this->setNext(PrevNode, NextNode); 44054263Sshin else 44154263Sshin Head = NextNode; 442147611Sdwmalone this->setPrev(NextNode, PrevNode); 443147611Sdwmalone IT = NextNode; 444147611Sdwmalone this->removeNodeFromList(Node); // Notify traits that we removed a node... 445147611Sdwmalone 446147611Sdwmalone // Set the next/prev pointers of the current node to null. This isn't 447147611Sdwmalone // strictly required, but this catches errors where a node is removed from 448153621Sthompsa // an ilist (and potentially deleted) with iterators still pointing at it. 449159180Scsjp // When those iterators are incremented or decremented, they will assert on 45062587Sitojun // the null next/prev pointer instead of "usually working". 45154263Sshin this->setNext(Node, 0); 45254263Sshin this->setPrev(Node, 0); 453153621Sthompsa return Node; 454153621Sthompsa } 455153621Sthompsa 456153621Sthompsa NodeTy *remove(const iterator &IT) { 457178888Sjulian iterator MutIt = IT; 45878064Sume return remove(MutIt); 45978064Sume } 46062587Sitojun 46162587Sitojun // erase - remove a node from the controlled sequence... and delete it. 46278064Sume iterator erase(iterator where) { 46354263Sshin this->deleteNode(remove(where)); 46454263Sshin return where; 46554263Sshin } 466153621Sthompsa 46754263Sshin 46854263Sshinprivate: 46954263Sshin // transfer - The heart of the splice function. Move linked list nodes from 47054263Sshin // [first, last) into position. 471153621Sthompsa // 47254263Sshin void transfer(iterator position, iplist &L2, iterator first, iterator last) { 47354263Sshin assert(first != last && "Should be checked by callers"); 47454263Sshin 47562587Sitojun if (position != last) { 47654263Sshin // Note: we have to be careful about the case when we move the first node 47754263Sshin // in the list. This node is the list sentinel node and we can't move it. 47854263Sshin NodeTy *ThisSentinel = getTail(); 479159174Sglebius setTail(0); 48054263Sshin NodeTy *L2Sentinel = L2.getTail(); 48178064Sume L2.setTail(0); 48278064Sume 483155037Sglebius // Remove [first, last) from its old position. 48454263Sshin NodeTy *First = &*first, *Prev = this->getPrev(First); 48554263Sshin NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next); 48654263Sshin if (Prev) 487105338Sume this->setNext(Prev, Next); 48854263Sshin else 48954263Sshin L2.Head = Next; 490105338Sume this->setPrev(Next, Prev); 49154263Sshin 492153621Sthompsa // Splice [first, last) into its new position. 493153621Sthompsa NodeTy *PosNext = position.getNodePtrUnchecked(); 494176879Sthompsa NodeTy *PosPrev = this->getPrev(PosNext); 495176879Sthompsa 49654263Sshin // Fix head of list... 497105338Sume if (PosPrev) 49854263Sshin this->setNext(PosPrev, First); 49954263Sshin else 50054263Sshin Head = First; 50154263Sshin this->setPrev(First, PosPrev); 50254263Sshin 503105338Sume // Fix end of list... 504101182Srwatson this->setNext(Last, PosNext); 505101182Srwatson this->setPrev(PosNext, Last); 506172930Srwatson 507101182Srwatson this->transferNodesFromList(L2, First, PosNext); 508101182Srwatson 509159180Scsjp // Now that everything is set, restore the pointers to the list sentinels. 51078064Sume L2.setTail(L2Sentinel); 511123922Ssam setTail(ThisSentinel); 51254263Sshin } 51354263Sshin } 51483998Sbrooks 515105338Sumepublic: 51683998Sbrooks 51783998Sbrooks //===----------------------------------------------------------------------=== 51883998Sbrooks // Functionality derived from other functions defined above... 51983998Sbrooks // 52054263Sshin 52154263Sshin size_type size() const { 52254263Sshin if (Head == 0) return 0; // Don't require construction of sentinel if empty. 52354263Sshin return std::distance(begin(), end()); 52495023Ssuz } 52554263Sshin 52695023Ssuz iterator erase(iterator first, iterator last) { 52754263Sshin while (first != last) 52895023Ssuz first = erase(first); 52995023Ssuz return last; 53054263Sshin } 53154263Sshin 53254263Sshin void clear() { if (Head) erase(begin(), end()); } 53354263Sshin 53454263Sshin // Front and back inserters... 53554263Sshin void push_front(NodeTy *val) { insert(begin(), val); } 53654263Sshin void push_back(NodeTy *val) { insert(end(), val); } 53754263Sshin void pop_front() { 53854263Sshin assert(!empty() && "pop_front() on empty list!"); 53954263Sshin erase(begin()); 54054263Sshin } 54154263Sshin void pop_back() { 542153621Sthompsa assert(!empty() && "pop_back() on empty list!"); 543153621Sthompsa iterator t = end(); erase(--t); 544153621Sthompsa } 545153621Sthompsa 546153621Sthompsa // Special forms of insert... 547153621Sthompsa template<class InIt> void insert(iterator where, InIt first, InIt last) { 548153621Sthompsa for (; first != last; ++first) insert(where, *first); 549153621Sthompsa } 550153621Sthompsa 551153621Sthompsa // Splice members - defined in terms of transfer... 552153621Sthompsa void splice(iterator where, iplist &L2) { 553153621Sthompsa if (!L2.empty()) 554153621Sthompsa transfer(where, L2, L2.begin(), L2.end()); 555153621Sthompsa } 556153621Sthompsa void splice(iterator where, iplist &L2, iterator first) { 557153621Sthompsa iterator last = first; ++last; 558153621Sthompsa if (where == first || where == last) return; // No change 559153621Sthompsa transfer(where, L2, first, last); 560153621Sthompsa } 561153621Sthompsa void splice(iterator where, iplist &L2, iterator first, iterator last) { 562153621Sthompsa if (first != last) transfer(where, L2, first, last); 563153621Sthompsa } 564176879Sthompsa 565176879Sthompsa 566176879Sthompsa 567176879Sthompsa //===----------------------------------------------------------------------=== 568176879Sthompsa // High-Level Functionality that shouldn't really be here, but is part of list 569176879Sthompsa // 570176879Sthompsa 571176879Sthompsa // These two functions are actually called remove/remove_if in list<>, but 572176879Sthompsa // they actually do the job of erase, rename them accordingly. 573176879Sthompsa // 574153621Sthompsa void erase(const NodeTy &val) { 575176879Sthompsa for (iterator I = begin(), E = end(); I != E; ) { 576176879Sthompsa iterator next = I; ++next; 577176879Sthompsa if (*I == val) erase(I); 578176879Sthompsa I = next; 579176879Sthompsa } 580176879Sthompsa } 581176879Sthompsa template<class Pr1> void erase_if(Pr1 pred) { 582176879Sthompsa for (iterator I = begin(), E = end(); I != E; ) { 583176879Sthompsa iterator next = I; ++next; 584176879Sthompsa if (pred(*I)) erase(I); 585153621Sthompsa I = next; 586153621Sthompsa } 587153621Sthompsa } 588153621Sthompsa 58954263Sshin template<class Pr2> void unique(Pr2 pred) { 59083998Sbrooks if (empty()) return; 591105338Sume for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) { 59283998Sbrooks if (pred(*I)) 59383998Sbrooks erase(Next); 59454263Sshin else 59554263Sshin I = Next; 59654263Sshin Next = I; 597105338Sume } 598105338Sume } 599111888Sjlemon void unique() { unique(op_equal); } 60054263Sshin 60154263Sshin template<class Pr3> void merge(iplist &right, Pr3 pred) { 60262587Sitojun iterator first1 = begin(), last1 = end(); 60354263Sshin iterator first2 = right.begin(), last2 = right.end(); 60454263Sshin while (first1 != last1 && first2 != last2) 60554263Sshin if (pred(*first2, *first1)) { 60654263Sshin iterator next = first2; 60754263Sshin transfer(first1, right, first2, ++next); 60854263Sshin first2 = next; 609147256Sbrooks } else { 61054263Sshin ++first1; 61154263Sshin } 61262587Sitojun if (first2 != last2) transfer(last1, right, first2, last2); 613105339Sume } 614105339Sume void merge(iplist &right) { return merge(right, op_less); } 615105339Sume 616105339Sume template<class Pr3> void sort(Pr3 pred); 61754263Sshin void sort() { sort(op_less); } 61854263Sshin}; 619105293Sume 62054263Sshin 62162587Sitojuntemplate<typename NodeTy> 62254263Sshinstruct ilist : public iplist<NodeTy> { 62354263Sshin typedef typename iplist<NodeTy>::size_type size_type; 62454263Sshin typedef typename iplist<NodeTy>::iterator iterator; 62554263Sshin 62654263Sshin ilist() {} 62754263Sshin ilist(const ilist &right) { 62854263Sshin insert(this->begin(), right.begin(), right.end()); 62962587Sitojun } 63054263Sshin explicit ilist(size_type count) { 63154263Sshin insert(this->begin(), count, NodeTy()); 63262587Sitojun } 63354263Sshin ilist(size_type count, const NodeTy &val) { 634105339Sume insert(this->begin(), count, val); 635105339Sume } 636105339Sume template<class InIt> ilist(InIt first, InIt last) { 637105339Sume insert(this->begin(), first, last); 63854263Sshin } 63962587Sitojun 64054263Sshin // bring hidden functions into scope 641105339Sume using iplist<NodeTy>::insert; 64254263Sshin using iplist<NodeTy>::push_front; 643105339Sume using iplist<NodeTy>::push_back; 64454263Sshin 64554263Sshin // Main implementation here - Insert for a node passed by value... 64654263Sshin iterator insert(iterator where, const NodeTy &val) { 64778064Sume return insert(where, this->createNode(val)); 64862587Sitojun } 64978064Sume 65062587Sitojun 65154263Sshin // Front and back inserters... 65254263Sshin void push_front(const NodeTy &val) { insert(this->begin(), val); } 65354263Sshin void push_back(const NodeTy &val) { insert(this->end(), val); } 65454263Sshin 65562587Sitojun // Special forms of insert... 65678064Sume template<class InIt> void insert(iterator where, InIt first, InIt last) { 65762587Sitojun for (; first != last; ++first) insert(where, *first); 65862587Sitojun } 65962587Sitojun void insert(iterator where, size_type count, const NodeTy &val) { 66062587Sitojun for (; count != 0; --count) insert(where, val); 66162587Sitojun } 66262587Sitojun 66362587Sitojun // Assign special forms... 66462587Sitojun void assign(size_type count, const NodeTy &val) { 66578064Sume iterator I = this->begin(); 66678064Sume for (; I != this->end() && count != 0; ++I, --count) 66778064Sume *I = val; 66878064Sume if (count != 0) 66978064Sume insert(this->end(), val, val); 670105293Sume else 67191327Sbrooks erase(I, this->end()); 672105293Sume } 67362587Sitojun template<class InIt> void assign(InIt first1, InIt last1) { 67454263Sshin iterator first2 = this->begin(), last2 = this->end(); 67578064Sume for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) 67678064Sume *first1 = *first2; 67778064Sume if (first2 == last2) 67878064Sume erase(first1, last1); 67978064Sume else 68078064Sume insert(last1, first2, last2); 68178064Sume } 68278064Sume 68378064Sume 68478064Sume // Resize members... 68578064Sume void resize(size_type newsize, NodeTy val) { 68678064Sume iterator i = this->begin(); 68778064Sume size_type len = 0; 68878064Sume for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ; 68978064Sume 69078064Sume if (len == newsize) 69178064Sume erase(i, this->end()); 69278064Sume else // i == end() 69378064Sume insert(this->end(), newsize - len, val); 69478064Sume } 69578064Sume void resize(size_type newsize) { resize(newsize, NodeTy()); } 69678064Sume}; 69778064Sume 69878064Sume} // End llvm namespace 69978064Sume 70078064Sumenamespace std { 70178064Sume // Ensure that swap uses the fast list swap... 70278064Sume template<class Ty> 70378064Sume void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 70478064Sume Left.swap(Right); 70578064Sume } 70678064Sume} // End 'std' extensions... 70778064Sume 70878064Sume#endif // LLVM_ADT_ILIST_H 70978064Sume