1193323Sed//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines classes to implement an intrusive doubly linked list class 11193323Sed// (i.e. each node of the list must contain a next and previous field for the 12193323Sed// list. 13193323Sed// 14193323Sed// The ilist_traits trait class is used to gain access to the next and previous 15193323Sed// fields of the node type that the list is instantiated with. If it is not 16193323Sed// specialized, the list defaults to using the getPrev(), getNext() method calls 17193323Sed// to get the next and previous pointers. 18193323Sed// 19193323Sed// The ilist class itself, should be a plug in replacement for list, assuming 20193323Sed// that the nodes contain next/prev pointers. This list replacement does not 21193323Sed// provide a constant time size() method, so be careful to use empty() when you 22193323Sed// really want to know if it's empty. 23193323Sed// 24193323Sed// The ilist class is implemented by allocating a 'tail' node when the list is 25193323Sed// created (using ilist_traits<>::createSentinel()). This tail node is 26193323Sed// absolutely required because the user must be able to compute end()-1. Because 27193323Sed// of this, users of the direct next/prev links will see an extra link on the 28193323Sed// end of the list, which should be ignored. 29193323Sed// 30193323Sed// Requirements for a user of this list: 31193323Sed// 32193323Sed// 1. The user must provide {g|s}et{Next|Prev} methods, or specialize 33193323Sed// ilist_traits to provide an alternate way of getting and setting next and 34193323Sed// prev links. 35193323Sed// 36193323Sed//===----------------------------------------------------------------------===// 37193323Sed 38193323Sed#ifndef LLVM_ADT_ILIST_H 39193323Sed#define LLVM_ADT_ILIST_H 40193323Sed 41243830Sdim#include "llvm/Support/Compiler.h" 42218893Sdim#include <algorithm> 43193323Sed#include <cassert> 44210299Sed#include <cstddef> 45198090Srdivacky#include <iterator> 46193323Sed 47193323Sednamespace llvm { 48193323Sed 49193323Sedtemplate<typename NodeTy, typename Traits> class iplist; 50193323Sedtemplate<typename NodeTy> class ilist_iterator; 51193323Sed 52193323Sed/// ilist_nextprev_traits - A fragment for template traits for intrusive list 53193323Sed/// that provides default next/prev implementations for common operations. 54193323Sed/// 55193323Sedtemplate<typename NodeTy> 56193323Sedstruct ilist_nextprev_traits { 57193323Sed static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } 58193323Sed static NodeTy *getNext(NodeTy *N) { return N->getNext(); } 59193323Sed static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } 60193323Sed static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } 61193323Sed 62193323Sed static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } 63193323Sed static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } 64193323Sed}; 65193323Sed 66193323Sedtemplate<typename NodeTy> 67193323Sedstruct ilist_traits; 68193323Sed 69193323Sed/// ilist_sentinel_traits - A fragment for template traits for intrusive list 70193323Sed/// that provides default sentinel implementations for common operations. 71193323Sed/// 72193323Sed/// ilist_sentinel_traits implements a lazy dynamic sentinel allocation 73193323Sed/// strategy. The sentinel is stored in the prev field of ilist's Head. 74193323Sed/// 75193323Sedtemplate<typename NodeTy> 76193323Sedstruct ilist_sentinel_traits { 77193323Sed /// createSentinel - create the dynamic sentinel 78193323Sed static NodeTy *createSentinel() { return new NodeTy(); } 79193323Sed 80193323Sed /// destroySentinel - deallocate the dynamic sentinel 81193323Sed static void destroySentinel(NodeTy *N) { delete N; } 82193323Sed 83193323Sed /// provideInitialHead - when constructing an ilist, provide a starting 84193323Sed /// value for its Head 85193323Sed /// @return null node to indicate that it needs to be allocated later 86193323Sed static NodeTy *provideInitialHead() { return 0; } 87193323Sed 88193323Sed /// ensureHead - make sure that Head is either already 89193323Sed /// initialized or assigned a fresh sentinel 90193323Sed /// @return the sentinel 91193323Sed static NodeTy *ensureHead(NodeTy *&Head) { 92193323Sed if (!Head) { 93193323Sed Head = ilist_traits<NodeTy>::createSentinel(); 94193323Sed ilist_traits<NodeTy>::noteHead(Head, Head); 95193323Sed ilist_traits<NodeTy>::setNext(Head, 0); 96193323Sed return Head; 97193323Sed } 98193323Sed return ilist_traits<NodeTy>::getPrev(Head); 99193323Sed } 100193323Sed 101193323Sed /// noteHead - stash the sentinel into its default location 102193323Sed static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { 103193323Sed ilist_traits<NodeTy>::setPrev(NewHead, Sentinel); 104193323Sed } 105193323Sed}; 106193323Sed 107193323Sed/// ilist_node_traits - A fragment for template traits for intrusive list 108193323Sed/// that provides default node related operations. 109193323Sed/// 110193323Sedtemplate<typename NodeTy> 111193323Sedstruct ilist_node_traits { 112193323Sed static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } 113193323Sed static void deleteNode(NodeTy *V) { delete V; } 114193323Sed 115193323Sed void addNodeToList(NodeTy *) {} 116193323Sed void removeNodeFromList(NodeTy *) {} 117193323Sed void transferNodesFromList(ilist_node_traits & /*SrcTraits*/, 118193323Sed ilist_iterator<NodeTy> /*first*/, 119193323Sed ilist_iterator<NodeTy> /*last*/) {} 120193323Sed}; 121193323Sed 122193323Sed/// ilist_default_traits - Default template traits for intrusive list. 123193323Sed/// By inheriting from this, you can easily use default implementations 124193323Sed/// for all common operations. 125193323Sed/// 126193323Sedtemplate<typename NodeTy> 127198090Srdivackystruct ilist_default_traits : public ilist_nextprev_traits<NodeTy>, 128198090Srdivacky public ilist_sentinel_traits<NodeTy>, 129198090Srdivacky public ilist_node_traits<NodeTy> { 130193323Sed}; 131193323Sed 132193323Sed// Template traits for intrusive list. By specializing this template class, you 133193323Sed// can change what next/prev fields are used to store the links... 134193323Sedtemplate<typename NodeTy> 135198090Srdivackystruct ilist_traits : public ilist_default_traits<NodeTy> {}; 136193323Sed 137193323Sed// Const traits are the same as nonconst traits... 138193323Sedtemplate<typename Ty> 139193323Sedstruct ilist_traits<const Ty> : public ilist_traits<Ty> {}; 140193323Sed 141193323Sed//===----------------------------------------------------------------------===// 142193323Sed// ilist_iterator<Node> - Iterator for intrusive list. 143193323Sed// 144193323Sedtemplate<typename NodeTy> 145193323Sedclass ilist_iterator 146198090Srdivacky : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { 147193323Sed 148193323Sedpublic: 149193323Sed typedef ilist_traits<NodeTy> Traits; 150198090Srdivacky typedef std::iterator<std::bidirectional_iterator_tag, 151198090Srdivacky NodeTy, ptrdiff_t> super; 152193323Sed 153193323Sed typedef typename super::value_type value_type; 154193323Sed typedef typename super::difference_type difference_type; 155193323Sed typedef typename super::pointer pointer; 156193323Sed typedef typename super::reference reference; 157193323Sedprivate: 158193323Sed pointer NodePtr; 159193323Sed 160193323Sed // ilist_iterator is not a random-access iterator, but it has an 161193323Sed // implicit conversion to pointer-type, which is. Declare (but 162193323Sed // don't define) these functions as private to help catch 163193323Sed // accidental misuse. 164193323Sed void operator[](difference_type) const; 165193323Sed void operator+(difference_type) const; 166193323Sed void operator-(difference_type) const; 167193323Sed void operator+=(difference_type) const; 168193323Sed void operator-=(difference_type) const; 169193323Sed template<class T> void operator<(T) const; 170193323Sed template<class T> void operator<=(T) const; 171193323Sed template<class T> void operator>(T) const; 172193323Sed template<class T> void operator>=(T) const; 173193323Sed template<class T> void operator-(T) const; 174193323Sedpublic: 175193323Sed 176193323Sed ilist_iterator(pointer NP) : NodePtr(NP) {} 177193323Sed ilist_iterator(reference NR) : NodePtr(&NR) {} 178193323Sed ilist_iterator() : NodePtr(0) {} 179193323Sed 180193323Sed // This is templated so that we can allow constructing a const iterator from 181193323Sed // a nonconst iterator... 182193323Sed template<class node_ty> 183193323Sed ilist_iterator(const ilist_iterator<node_ty> &RHS) 184193323Sed : NodePtr(RHS.getNodePtrUnchecked()) {} 185193323Sed 186193323Sed // This is templated so that we can allow assigning to a const iterator from 187193323Sed // a nonconst iterator... 188193323Sed template<class node_ty> 189193323Sed const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { 190193323Sed NodePtr = RHS.getNodePtrUnchecked(); 191193323Sed return *this; 192193323Sed } 193193323Sed 194193323Sed // Accessors... 195193323Sed operator pointer() const { 196193323Sed return NodePtr; 197193323Sed } 198193323Sed 199193323Sed reference operator*() const { 200193323Sed return *NodePtr; 201193323Sed } 202193323Sed pointer operator->() const { return &operator*(); } 203193323Sed 204193323Sed // Comparison operators 205193323Sed bool operator==(const ilist_iterator &RHS) const { 206193323Sed return NodePtr == RHS.NodePtr; 207193323Sed } 208193323Sed bool operator!=(const ilist_iterator &RHS) const { 209193323Sed return NodePtr != RHS.NodePtr; 210193323Sed } 211193323Sed 212193323Sed // Increment and decrement operators... 213193323Sed ilist_iterator &operator--() { // predecrement - Back up 214193323Sed NodePtr = Traits::getPrev(NodePtr); 215193323Sed assert(NodePtr && "--'d off the beginning of an ilist!"); 216193323Sed return *this; 217193323Sed } 218193323Sed ilist_iterator &operator++() { // preincrement - Advance 219193323Sed NodePtr = Traits::getNext(NodePtr); 220193323Sed return *this; 221193323Sed } 222193323Sed ilist_iterator operator--(int) { // postdecrement operators... 223193323Sed ilist_iterator tmp = *this; 224193323Sed --*this; 225193323Sed return tmp; 226193323Sed } 227193323Sed ilist_iterator operator++(int) { // postincrement operators... 228193323Sed ilist_iterator tmp = *this; 229193323Sed ++*this; 230193323Sed return tmp; 231193323Sed } 232193323Sed 233193323Sed // Internal interface, do not use... 234193323Sed pointer getNodePtrUnchecked() const { return NodePtr; } 235193323Sed}; 236193323Sed 237249423Sdim// These are to catch errors when people try to use them as random access 238249423Sdim// iterators. 239193323Sedtemplate<typename T> 240249423Sdimvoid operator-(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; 241193323Sedtemplate<typename T> 242249423Sdimvoid operator-(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; 243193323Sed 244193323Sedtemplate<typename T> 245249423Sdimvoid operator+(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; 246193323Sedtemplate<typename T> 247249423Sdimvoid operator+(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; 248193323Sed 249193323Sed// operator!=/operator== - Allow mixed comparisons without dereferencing 250193323Sed// the iterator, which could very likely be pointing to end(). 251193323Sedtemplate<typename T> 252193323Sedbool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { 253193323Sed return LHS != RHS.getNodePtrUnchecked(); 254193323Sed} 255193323Sedtemplate<typename T> 256193323Sedbool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { 257193323Sed return LHS == RHS.getNodePtrUnchecked(); 258193323Sed} 259193323Sedtemplate<typename T> 260193323Sedbool operator!=(T* LHS, const ilist_iterator<T> &RHS) { 261193323Sed return LHS != RHS.getNodePtrUnchecked(); 262193323Sed} 263193323Sedtemplate<typename T> 264193323Sedbool operator==(T* LHS, const ilist_iterator<T> &RHS) { 265193323Sed return LHS == RHS.getNodePtrUnchecked(); 266193323Sed} 267193323Sed 268193323Sed 269193323Sed// Allow ilist_iterators to convert into pointers to a node automatically when 270193323Sed// used by the dyn_cast, cast, isa mechanisms... 271193323Sed 272193323Sedtemplate<typename From> struct simplify_type; 273193323Sed 274193323Sedtemplate<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { 275193323Sed typedef NodeTy* SimpleType; 276193323Sed 277249423Sdim static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) { 278193323Sed return &*Node; 279193323Sed } 280193323Sed}; 281193323Sedtemplate<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { 282249423Sdim typedef /*const*/ NodeTy* SimpleType; 283193323Sed 284193323Sed static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 285193323Sed return &*Node; 286193323Sed } 287193323Sed}; 288193323Sed 289193323Sed 290193323Sed//===----------------------------------------------------------------------===// 291193323Sed// 292193323Sed/// iplist - The subset of list functionality that can safely be used on nodes 293221345Sdim/// of polymorphic types, i.e. a heterogeneous list with a common base class that 294193323Sed/// holds the next/prev pointers. The only state of the list itself is a single 295193323Sed/// pointer to the head of the list. 296193323Sed/// 297193323Sed/// This list can be in one of three interesting states: 298193323Sed/// 1. The list may be completely unconstructed. In this case, the head 299193323Sed/// pointer is null. When in this form, any query for an iterator (e.g. 300193323Sed/// begin() or end()) causes the list to transparently change to state #2. 301193323Sed/// 2. The list may be empty, but contain a sentinel for the end iterator. This 302193323Sed/// sentinel is created by the Traits::createSentinel method and is a link 303193323Sed/// in the list. When the list is empty, the pointer in the iplist points 304193323Sed/// to the sentinel. Once the sentinel is constructed, it 305193323Sed/// is not destroyed until the list is. 306193323Sed/// 3. The list may contain actual objects in it, which are stored as a doubly 307193323Sed/// linked list of nodes. One invariant of the list is that the predecessor 308193323Sed/// of the first node in the list always points to the last node in the list, 309193323Sed/// and the successor pointer for the sentinel (which always stays at the 310193323Sed/// end of the list) is always null. 311193323Sed/// 312193323Sedtemplate<typename NodeTy, typename Traits=ilist_traits<NodeTy> > 313193323Sedclass iplist : public Traits { 314193323Sed mutable NodeTy *Head; 315193323Sed 316193323Sed // Use the prev node pointer of 'head' as the tail pointer. This is really a 317193323Sed // circularly linked list where we snip the 'next' link from the sentinel node 318193323Sed // back to the first node in the list (to preserve assertions about going off 319193323Sed // the end of the list). 320193323Sed NodeTy *getTail() { return this->ensureHead(Head); } 321193323Sed const NodeTy *getTail() const { return this->ensureHead(Head); } 322193323Sed void setTail(NodeTy *N) const { this->noteHead(Head, N); } 323193323Sed 324193323Sed /// CreateLazySentinel - This method verifies whether the sentinel for the 325193323Sed /// list has been created and lazily makes it if not. 326193323Sed void CreateLazySentinel() const { 327198090Srdivacky this->ensureHead(Head); 328193323Sed } 329193323Sed 330193323Sed static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } 331193323Sed static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } 332193323Sed 333198090Srdivacky // No fundamental reason why iplist can't be copyable, but the default 334193323Sed // copy/copy-assign won't do. 335243830Sdim iplist(const iplist &) LLVM_DELETED_FUNCTION; 336243830Sdim void operator=(const iplist &) LLVM_DELETED_FUNCTION; 337193323Sed 338193323Sedpublic: 339193323Sed typedef NodeTy *pointer; 340193323Sed typedef const NodeTy *const_pointer; 341193323Sed typedef NodeTy &reference; 342193323Sed typedef const NodeTy &const_reference; 343193323Sed typedef NodeTy value_type; 344193323Sed typedef ilist_iterator<NodeTy> iterator; 345193323Sed typedef ilist_iterator<const NodeTy> const_iterator; 346193323Sed typedef size_t size_type; 347193323Sed typedef ptrdiff_t difference_type; 348193323Sed typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 349193323Sed typedef std::reverse_iterator<iterator> reverse_iterator; 350193323Sed 351198090Srdivacky iplist() : Head(this->provideInitialHead()) {} 352193323Sed ~iplist() { 353193323Sed if (!Head) return; 354193323Sed clear(); 355193323Sed Traits::destroySentinel(getTail()); 356193323Sed } 357193323Sed 358193323Sed // Iterator creation methods. 359193323Sed iterator begin() { 360193323Sed CreateLazySentinel(); 361193323Sed return iterator(Head); 362193323Sed } 363193323Sed const_iterator begin() const { 364193323Sed CreateLazySentinel(); 365193323Sed return const_iterator(Head); 366193323Sed } 367193323Sed iterator end() { 368193323Sed CreateLazySentinel(); 369193323Sed return iterator(getTail()); 370193323Sed } 371193323Sed const_iterator end() const { 372193323Sed CreateLazySentinel(); 373193323Sed return const_iterator(getTail()); 374193323Sed } 375193323Sed 376193323Sed // reverse iterator creation methods. 377193323Sed reverse_iterator rbegin() { return reverse_iterator(end()); } 378193323Sed const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 379193323Sed reverse_iterator rend() { return reverse_iterator(begin()); } 380193323Sed const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 381193323Sed 382193323Sed 383193323Sed // Miscellaneous inspection routines. 384193323Sed size_type max_size() const { return size_type(-1); } 385263508Sdim bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 386263508Sdim return Head == 0 || Head == getTail(); 387263508Sdim } 388193323Sed 389193323Sed // Front and back accessor functions... 390193323Sed reference front() { 391193323Sed assert(!empty() && "Called front() on empty list!"); 392193323Sed return *Head; 393193323Sed } 394193323Sed const_reference front() const { 395193323Sed assert(!empty() && "Called front() on empty list!"); 396193323Sed return *Head; 397193323Sed } 398193323Sed reference back() { 399193323Sed assert(!empty() && "Called back() on empty list!"); 400193323Sed return *this->getPrev(getTail()); 401193323Sed } 402193323Sed const_reference back() const { 403193323Sed assert(!empty() && "Called back() on empty list!"); 404193323Sed return *this->getPrev(getTail()); 405193323Sed } 406193323Sed 407193323Sed void swap(iplist &RHS) { 408193323Sed assert(0 && "Swap does not use list traits callback correctly yet!"); 409193323Sed std::swap(Head, RHS.Head); 410193323Sed } 411193323Sed 412193323Sed iterator insert(iterator where, NodeTy *New) { 413193323Sed NodeTy *CurNode = where.getNodePtrUnchecked(); 414193323Sed NodeTy *PrevNode = this->getPrev(CurNode); 415193323Sed this->setNext(New, CurNode); 416193323Sed this->setPrev(New, PrevNode); 417193323Sed 418193323Sed if (CurNode != Head) // Is PrevNode off the beginning of the list? 419193323Sed this->setNext(PrevNode, New); 420193323Sed else 421193323Sed Head = New; 422193323Sed this->setPrev(CurNode, New); 423193323Sed 424193323Sed this->addNodeToList(New); // Notify traits that we added a node... 425193323Sed return New; 426193323Sed } 427193323Sed 428193323Sed iterator insertAfter(iterator where, NodeTy *New) { 429193323Sed if (empty()) 430193323Sed return insert(begin(), New); 431193323Sed else 432193323Sed return insert(++where, New); 433193323Sed } 434193323Sed 435193323Sed NodeTy *remove(iterator &IT) { 436193323Sed assert(IT != end() && "Cannot remove end of list!"); 437193323Sed NodeTy *Node = &*IT; 438193323Sed NodeTy *NextNode = this->getNext(Node); 439193323Sed NodeTy *PrevNode = this->getPrev(Node); 440193323Sed 441193323Sed if (Node != Head) // Is PrevNode off the beginning of the list? 442193323Sed this->setNext(PrevNode, NextNode); 443193323Sed else 444193323Sed Head = NextNode; 445193323Sed this->setPrev(NextNode, PrevNode); 446193323Sed IT = NextNode; 447193323Sed this->removeNodeFromList(Node); // Notify traits that we removed a node... 448193323Sed 449193323Sed // Set the next/prev pointers of the current node to null. This isn't 450193323Sed // strictly required, but this catches errors where a node is removed from 451193323Sed // an ilist (and potentially deleted) with iterators still pointing at it. 452193323Sed // When those iterators are incremented or decremented, they will assert on 453193323Sed // the null next/prev pointer instead of "usually working". 454193323Sed this->setNext(Node, 0); 455193323Sed this->setPrev(Node, 0); 456193323Sed return Node; 457193323Sed } 458193323Sed 459193323Sed NodeTy *remove(const iterator &IT) { 460193323Sed iterator MutIt = IT; 461193323Sed return remove(MutIt); 462193323Sed } 463193323Sed 464193323Sed // erase - remove a node from the controlled sequence... and delete it. 465193323Sed iterator erase(iterator where) { 466193323Sed this->deleteNode(remove(where)); 467193323Sed return where; 468193323Sed } 469193323Sed 470249423Sdim /// Remove all nodes from the list like clear(), but do not call 471249423Sdim /// removeNodeFromList() or deleteNode(). 472249423Sdim /// 473249423Sdim /// This should only be used immediately before freeing nodes in bulk to 474249423Sdim /// avoid traversing the list and bringing all the nodes into cache. 475249423Sdim void clearAndLeakNodesUnsafely() { 476249423Sdim if (Head) { 477249423Sdim Head = getTail(); 478249423Sdim this->setPrev(Head, Head); 479249423Sdim } 480249423Sdim } 481193323Sed 482193323Sedprivate: 483193323Sed // transfer - The heart of the splice function. Move linked list nodes from 484193323Sed // [first, last) into position. 485193323Sed // 486193323Sed void transfer(iterator position, iplist &L2, iterator first, iterator last) { 487193323Sed assert(first != last && "Should be checked by callers"); 488249423Sdim // Position cannot be contained in the range to be transferred. 489249423Sdim // Check for the most common mistake. 490249423Sdim assert(position != first && 491249423Sdim "Insertion point can't be one of the transferred nodes"); 492193323Sed 493193323Sed if (position != last) { 494193323Sed // Note: we have to be careful about the case when we move the first node 495193323Sed // in the list. This node is the list sentinel node and we can't move it. 496193323Sed NodeTy *ThisSentinel = getTail(); 497193323Sed setTail(0); 498193323Sed NodeTy *L2Sentinel = L2.getTail(); 499193323Sed L2.setTail(0); 500193323Sed 501193323Sed // Remove [first, last) from its old position. 502193378Sed NodeTy *First = &*first, *Prev = this->getPrev(First); 503193378Sed NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next); 504193323Sed if (Prev) 505193323Sed this->setNext(Prev, Next); 506193323Sed else 507193323Sed L2.Head = Next; 508193323Sed this->setPrev(Next, Prev); 509193323Sed 510193323Sed // Splice [first, last) into its new position. 511193323Sed NodeTy *PosNext = position.getNodePtrUnchecked(); 512193378Sed NodeTy *PosPrev = this->getPrev(PosNext); 513193323Sed 514193323Sed // Fix head of list... 515193323Sed if (PosPrev) 516193323Sed this->setNext(PosPrev, First); 517193323Sed else 518193323Sed Head = First; 519193323Sed this->setPrev(First, PosPrev); 520193323Sed 521193323Sed // Fix end of list... 522193323Sed this->setNext(Last, PosNext); 523193323Sed this->setPrev(PosNext, Last); 524193323Sed 525193378Sed this->transferNodesFromList(L2, First, PosNext); 526193323Sed 527193323Sed // Now that everything is set, restore the pointers to the list sentinels. 528193323Sed L2.setTail(L2Sentinel); 529193323Sed setTail(ThisSentinel); 530193323Sed } 531193323Sed } 532193323Sed 533193323Sedpublic: 534193323Sed 535193323Sed //===----------------------------------------------------------------------=== 536193323Sed // Functionality derived from other functions defined above... 537193323Sed // 538193323Sed 539263508Sdim size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const { 540193323Sed if (Head == 0) return 0; // Don't require construction of sentinel if empty. 541193323Sed return std::distance(begin(), end()); 542193323Sed } 543193323Sed 544193323Sed iterator erase(iterator first, iterator last) { 545193323Sed while (first != last) 546193323Sed first = erase(first); 547193323Sed return last; 548193323Sed } 549193323Sed 550193323Sed void clear() { if (Head) erase(begin(), end()); } 551193323Sed 552193323Sed // Front and back inserters... 553193323Sed void push_front(NodeTy *val) { insert(begin(), val); } 554193323Sed void push_back(NodeTy *val) { insert(end(), val); } 555193323Sed void pop_front() { 556193323Sed assert(!empty() && "pop_front() on empty list!"); 557193323Sed erase(begin()); 558193323Sed } 559193323Sed void pop_back() { 560193323Sed assert(!empty() && "pop_back() on empty list!"); 561193323Sed iterator t = end(); erase(--t); 562193323Sed } 563193323Sed 564193323Sed // Special forms of insert... 565193323Sed template<class InIt> void insert(iterator where, InIt first, InIt last) { 566193323Sed for (; first != last; ++first) insert(where, *first); 567193323Sed } 568193323Sed 569193323Sed // Splice members - defined in terms of transfer... 570193323Sed void splice(iterator where, iplist &L2) { 571193323Sed if (!L2.empty()) 572193323Sed transfer(where, L2, L2.begin(), L2.end()); 573193323Sed } 574193323Sed void splice(iterator where, iplist &L2, iterator first) { 575193323Sed iterator last = first; ++last; 576193323Sed if (where == first || where == last) return; // No change 577193323Sed transfer(where, L2, first, last); 578193323Sed } 579193323Sed void splice(iterator where, iplist &L2, iterator first, iterator last) { 580193323Sed if (first != last) transfer(where, L2, first, last); 581193323Sed } 582193323Sed 583193323Sed 584193323Sed 585193323Sed //===----------------------------------------------------------------------=== 586193323Sed // High-Level Functionality that shouldn't really be here, but is part of list 587193323Sed // 588193323Sed 589193323Sed // These two functions are actually called remove/remove_if in list<>, but 590193323Sed // they actually do the job of erase, rename them accordingly. 591193323Sed // 592193323Sed void erase(const NodeTy &val) { 593193323Sed for (iterator I = begin(), E = end(); I != E; ) { 594193323Sed iterator next = I; ++next; 595193323Sed if (*I == val) erase(I); 596193323Sed I = next; 597193323Sed } 598193323Sed } 599193323Sed template<class Pr1> void erase_if(Pr1 pred) { 600193323Sed for (iterator I = begin(), E = end(); I != E; ) { 601193323Sed iterator next = I; ++next; 602193323Sed if (pred(*I)) erase(I); 603193323Sed I = next; 604193323Sed } 605193323Sed } 606193323Sed 607193323Sed template<class Pr2> void unique(Pr2 pred) { 608193323Sed if (empty()) return; 609193323Sed for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) { 610193323Sed if (pred(*I)) 611193323Sed erase(Next); 612193323Sed else 613193323Sed I = Next; 614193323Sed Next = I; 615193323Sed } 616193323Sed } 617193323Sed void unique() { unique(op_equal); } 618193323Sed 619193323Sed template<class Pr3> void merge(iplist &right, Pr3 pred) { 620193323Sed iterator first1 = begin(), last1 = end(); 621193323Sed iterator first2 = right.begin(), last2 = right.end(); 622193323Sed while (first1 != last1 && first2 != last2) 623193323Sed if (pred(*first2, *first1)) { 624193323Sed iterator next = first2; 625193323Sed transfer(first1, right, first2, ++next); 626193323Sed first2 = next; 627193323Sed } else { 628193323Sed ++first1; 629193323Sed } 630193323Sed if (first2 != last2) transfer(last1, right, first2, last2); 631193323Sed } 632193323Sed void merge(iplist &right) { return merge(right, op_less); } 633193323Sed 634193323Sed template<class Pr3> void sort(Pr3 pred); 635193323Sed void sort() { sort(op_less); } 636193323Sed}; 637193323Sed 638193323Sed 639193323Sedtemplate<typename NodeTy> 640193323Sedstruct ilist : public iplist<NodeTy> { 641193323Sed typedef typename iplist<NodeTy>::size_type size_type; 642193323Sed typedef typename iplist<NodeTy>::iterator iterator; 643193323Sed 644193323Sed ilist() {} 645193323Sed ilist(const ilist &right) { 646193323Sed insert(this->begin(), right.begin(), right.end()); 647193323Sed } 648193323Sed explicit ilist(size_type count) { 649193323Sed insert(this->begin(), count, NodeTy()); 650193323Sed } 651193323Sed ilist(size_type count, const NodeTy &val) { 652193323Sed insert(this->begin(), count, val); 653193323Sed } 654193323Sed template<class InIt> ilist(InIt first, InIt last) { 655193323Sed insert(this->begin(), first, last); 656193323Sed } 657193323Sed 658193323Sed // bring hidden functions into scope 659193323Sed using iplist<NodeTy>::insert; 660193323Sed using iplist<NodeTy>::push_front; 661193323Sed using iplist<NodeTy>::push_back; 662193323Sed 663193323Sed // Main implementation here - Insert for a node passed by value... 664193323Sed iterator insert(iterator where, const NodeTy &val) { 665200581Srdivacky return insert(where, this->createNode(val)); 666193323Sed } 667193323Sed 668193323Sed 669193323Sed // Front and back inserters... 670193323Sed void push_front(const NodeTy &val) { insert(this->begin(), val); } 671193323Sed void push_back(const NodeTy &val) { insert(this->end(), val); } 672193323Sed 673193323Sed void insert(iterator where, size_type count, const NodeTy &val) { 674193323Sed for (; count != 0; --count) insert(where, val); 675193323Sed } 676193323Sed 677193323Sed // Assign special forms... 678193323Sed void assign(size_type count, const NodeTy &val) { 679193323Sed iterator I = this->begin(); 680193323Sed for (; I != this->end() && count != 0; ++I, --count) 681193323Sed *I = val; 682193323Sed if (count != 0) 683193323Sed insert(this->end(), val, val); 684193323Sed else 685193323Sed erase(I, this->end()); 686193323Sed } 687193323Sed template<class InIt> void assign(InIt first1, InIt last1) { 688193323Sed iterator first2 = this->begin(), last2 = this->end(); 689193323Sed for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) 690193323Sed *first1 = *first2; 691193323Sed if (first2 == last2) 692193323Sed erase(first1, last1); 693193323Sed else 694193323Sed insert(last1, first2, last2); 695193323Sed } 696193323Sed 697193323Sed 698193323Sed // Resize members... 699193323Sed void resize(size_type newsize, NodeTy val) { 700193323Sed iterator i = this->begin(); 701193323Sed size_type len = 0; 702193323Sed for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ; 703193323Sed 704193323Sed if (len == newsize) 705193323Sed erase(i, this->end()); 706193323Sed else // i == end() 707193323Sed insert(this->end(), newsize - len, val); 708193323Sed } 709193323Sed void resize(size_type newsize) { resize(newsize, NodeTy()); } 710193323Sed}; 711193323Sed 712193323Sed} // End llvm namespace 713193323Sed 714193323Sednamespace std { 715193323Sed // Ensure that swap uses the fast list swap... 716193323Sed template<class Ty> 717193323Sed void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 718193323Sed Left.swap(Right); 719193323Sed } 720193323Sed} // End 'std' extensions... 721193323Sed 722193323Sed#endif // LLVM_ADT_ILIST_H 723