ilist.h revision 066075030ad46b3494480a5f79f05443f947aca7
19682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// 29682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 39682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// The LLVM Compiler Infrastructure 49682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 59682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// This file is distributed under the University of Illinois Open Source 69682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// License. See LICENSE.TXT for details. 79682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 89682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall//===----------------------------------------------------------------------===// 99682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// This file defines classes to implement an intrusive doubly linked list class 119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// (i.e. each node of the list must contain a next and previous field for the 129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// list. 139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// The ilist_traits trait class is used to gain access to the next and previous 159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// fields of the node type that the list is instantiated with. If it is not 169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// specialized, the list defaults to using the getPrev(), getNext() method calls 179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// to get the next and previous pointers. 189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// The ilist class itself, should be a plug in replacement for list, assuming 209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// that the nodes contain next/prev pointers. This list replacement does not 219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// provide a constant time size() method, so be careful to use empty() when you 229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// really want to know if it's empty. 239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// The ilist class is implemented by allocating a 'tail' node when the list is 259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// created (using ilist_traits<>::createSentinel()). This tail node is 269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// absolutely required because the user must be able to compute end()-1. Because 279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// of this, users of the direct next/prev links will see an extra link on the 289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// end of the list, which should be ignored. 299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Requirements for a user of this list: 319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 1. The user must provide {g|s}et{Next|Prev} methods, or specialize 339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// ilist_traits to provide an alternate way of getting and setting next and 349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// prev links. 359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall//===----------------------------------------------------------------------===// 379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifndef LLVM_ADT_ILIST_H 399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define LLVM_ADT_ILIST_H 409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include "llvm/ADT/iterator.h" 429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <cassert> 439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <cstdlib> 449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallnamespace llvm { 469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy, typename Traits> class iplist; 489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy> class ilist_iterator; 499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Template traits for intrusive list. By specializing this template class, you 519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// can change what next/prev fields are used to store the links... 529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy> 539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstruct ilist_traits { 549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } 559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static NodeTy *getNext(NodeTy *N) { return N->getNext(); } 569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } 579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } 589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } 609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } 619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } 639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static void deleteNode(NodeTy *V) { delete V; } 649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static NodeTy *createSentinel() { return new NodeTy(); } 669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static void destroySentinel(NodeTy *N) { delete N; } 679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void addNodeToList(NodeTy *NTy) {} 699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void removeNodeFromList(NodeTy *NTy) {} 709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void transferNodesFromList(iplist<NodeTy, ilist_traits> &L2, 719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator<NodeTy> first, 729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator<NodeTy> last) {} 739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall}; 749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Const traits are the same as nonconst traits... 769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename Ty> 779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstruct ilist_traits<const Ty> : public ilist_traits<Ty> {}; 789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall//===----------------------------------------------------------------------===// 819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// ilist_iterator<Node> - Iterator for intrusive list. 829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy> 849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallclass ilist_iterator 859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall : public bidirectional_iterator<NodeTy, ptrdiff_t> { 869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallpublic: 889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef ilist_traits<NodeTy> Traits; 899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef bidirectional_iterator<NodeTy, ptrdiff_t> super; 909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef size_t size_type; 929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef typename super::pointer pointer; 939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef typename super::reference reference; 949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallprivate: 959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall pointer NodePtr; 969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // operator[] is not defined. Compile error instead of having a runtime bug. 989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void operator[](unsigned) {} 999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void operator[](unsigned) const {} 1009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallpublic: 1019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator(pointer NP) : NodePtr(NP) {} 1039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator(reference NR) : NodePtr(&NR) {} 1049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator() : NodePtr(0) {} 1059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // This is templated so that we can allow constructing a const iterator from 1079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // a nonconst iterator... 1089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall template<class node_ty> 1099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator(const ilist_iterator<node_ty> &RHS) 1109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall : NodePtr(RHS.getNodePtrUnchecked()) {} 1119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // This is templated so that we can allow assigning to a const iterator from 1139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // a nonconst iterator... 1149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall template<class node_ty> 1159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { 1169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall NodePtr = RHS.getNodePtrUnchecked(); 1179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *this; 1189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Accessors... 1219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall operator pointer() const { 1229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!"); 1239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return NodePtr; 1249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall reference operator*() const { 1279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!"); 1289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *NodePtr; 1299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall pointer operator->() const { return &operator*(); } 1319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Comparison operators 1339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall bool operator==(const ilist_iterator &RHS) const { 1349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return NodePtr == RHS.NodePtr; 1359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall bool operator!=(const ilist_iterator &RHS) const { 1379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return NodePtr != RHS.NodePtr; 1389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Increment and decrement operators... 1419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator &operator--() { // predecrement - Back up 1429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall NodePtr = Traits::getPrev(NodePtr); 1439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(Traits::getNext(NodePtr) && "--'d off the beginning of an ilist!"); 1449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *this; 1459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator &operator++() { // preincrement - Advance 1479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall NodePtr = Traits::getNext(NodePtr); 1489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(NodePtr && "++'d off the end of an ilist!"); 1499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *this; 1509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator operator--(int) { // postdecrement operators... 1529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator tmp = *this; 1539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall --*this; 1549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return tmp; 1559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator operator++(int) { // postincrement operators... 1579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ilist_iterator tmp = *this; 1589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ++*this; 1599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return tmp; 1609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Internal interface, do not use... 1639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall pointer getNodePtrUnchecked() const { return NodePtr; } 1649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall}; 1659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// do not implement. this is to catch errors when people try to use 1679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// them as random access iterators 1689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallvoid operator-(int, ilist_iterator<T>); 1709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallvoid operator-(ilist_iterator<T>,int); 1729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallvoid operator+(int, ilist_iterator<T>); 1759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallvoid operator+(ilist_iterator<T>,int); 1779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// operator!=/operator== - Allow mixed comparisons without dereferencing 1799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// the iterator, which could very likely be pointing to end(). 1809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallbool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { 1829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return LHS != RHS.getNodePtrUnchecked(); 1839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 1849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallbool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { 1869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return LHS == RHS.getNodePtrUnchecked(); 1879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 1889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallbool operator!=(T* LHS, const ilist_iterator<T> &RHS) { 1909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return LHS != RHS.getNodePtrUnchecked(); 1919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 1929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename T> 1939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallbool operator==(T* LHS, const ilist_iterator<T> &RHS) { 1949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return LHS == RHS.getNodePtrUnchecked(); 1959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 1969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Allow ilist_iterators to convert into pointers to a node automatically when 1999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// used by the dyn_cast, cast, isa mechanisms... 2009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename From> struct simplify_type; 2029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { 2049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef NodeTy* SimpleType; 2059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 2079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return &*Node; 2089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall}; 2109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { 2119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef NodeTy* SimpleType; 2129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 2149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return &*Node; 2159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall}; 2179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall//===----------------------------------------------------------------------===// 2209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 2219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// iplist - The subset of list functionality that can safely be used on nodes 2229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// of polymorphic types, i.e. a heterogenous list with a common base class that 2239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// holds the next/prev pointers. The only state of the list itself is a single 2249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// pointer to the head of the list. 2259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// 2269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// This list can be in one of three interesting states: 2279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// 1. The list may be completely unconstructed. In this case, the head 2289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// pointer is null. When in this form, any query for an iterator (e.g. 2299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// begin() or end()) causes the list to transparently change to state #2. 2309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// 2. The list may be empty, but contain a sentinal for the end iterator. This 2319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// sentinal is created by the Traits::createSentinel method and is a link 2329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// in the list. When the list is empty, the pointer in the iplist points 2339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// to the sentinal. Once the sentinal is constructed, it 2349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// is not destroyed until the list is. 2359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// 3. The list may contain actual objects in it, which are stored as a doubly 2369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// linked list of nodes. One invariant of the list is that the predecessor 2379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// of the first node in the list always points to the last node in the list, 2389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// and the successor pointer for the sentinal (which always stays at the 2399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// end of the list) is always null. 2409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/// 2419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltemplate<typename NodeTy, typename Traits=ilist_traits<NodeTy> > 2429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallclass iplist : public Traits { 2439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall mutable NodeTy *Head; 2449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Use the prev node pointer of 'head' as the tail pointer. This is really a 2469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // circularly linked list where we snip the 'next' link from the sentinel node 2479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // back to the first node in the list (to preserve assertions about going off 2489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // the end of the list). 2499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall NodeTy *getTail() { return getPrev(Head); } 2509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const NodeTy *getTail() const { return getPrev(Head); } 2519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void setTail(NodeTy *N) const { setPrev(Head, N); } 2529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /// CreateLazySentinal - This method verifies whether the sentinal for the 2549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /// list has been created and lazily makes it if not. 2559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void CreateLazySentinal() const { 2569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (Head != 0) return; 2579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Head = Traits::createSentinel(); 2589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall setNext(Head, 0); 2599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall setTail(Head); 2609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } 2639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } 2649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // No fundamental reason why iplist can't by copyable, but the default 2669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // copy/copy-assign won't do. 2679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall iplist(const iplist &); // do not implement 2689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void operator=(const iplist &); // do not implement 2699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallpublic: 2719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef NodeTy *pointer; 2729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef const NodeTy *const_pointer; 2739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef NodeTy &reference; 2749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef const NodeTy &const_reference; 2759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef NodeTy value_type; 2769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef ilist_iterator<NodeTy> iterator; 2779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef ilist_iterator<const NodeTy> const_iterator; 2789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef size_t size_type; 2799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef ptrdiff_t difference_type; 2809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 2819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall typedef std::reverse_iterator<iterator> reverse_iterator; 2829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall iplist() : Head(0) {} 2849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ~iplist() { 2859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (!Head) return; 2869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall clear(); 2879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Traits::destroySentinel(getTail()); 2889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Iterator creation methods. 2919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall iterator begin() { 2929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall CreateLazySentinal(); 2939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return iterator(Head); 2949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const_iterator begin() const { 2969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall CreateLazySentinal(); 2979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return const_iterator(Head); 2989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall iterator end() { 3009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall CreateLazySentinal(); 3019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return iterator(getTail()); 3029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const_iterator end() const { 3049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall CreateLazySentinal(); 3059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return const_iterator(getTail()); 3069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // reverse iterator creation methods. 3099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall reverse_iterator rbegin() { return reverse_iterator(end()); } 3109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 3119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall reverse_iterator rend() { return reverse_iterator(begin()); } 3129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 3139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Miscellaneous inspection routines. 3169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall size_type max_size() const { return size_type(-1); } 3179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall bool empty() const { return Head == 0 || Head == getTail(); } 3189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall // Front and back accessor functions... 3209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall reference front() { 3219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(!empty() && "Called front() on empty list!"); 3229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *Head; 3239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const_reference front() const { 3259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(!empty() && "Called front() on empty list!"); 3269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *Head; 3279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall reference back() { 3299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(!empty() && "Called back() on empty list!"); 3309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *getPrev(getTail()); 3319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall const_reference back() const { 3339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(!empty() && "Called back() on empty list!"); 3349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return *getPrev(getTail()); 3359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall void swap(iplist &RHS) { 3389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall abort(); // Swap does not use list traits callback correctly yet! 3399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall std::swap(Head, RHS.Head); 3409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 341 342 iterator insert(iterator where, NodeTy *New) { 343 NodeTy *CurNode = where.getNodePtrUnchecked(), *PrevNode = getPrev(CurNode); 344 setNext(New, CurNode); 345 setPrev(New, PrevNode); 346 347 if (CurNode != Head) // Is PrevNode off the beginning of the list? 348 setNext(PrevNode, New); 349 else 350 Head = New; 351 setPrev(CurNode, New); 352 353 addNodeToList(New); // Notify traits that we added a node... 354 return New; 355 } 356 357 NodeTy *remove(iterator &IT) { 358 assert(IT != end() && "Cannot remove end of list!"); 359 NodeTy *Node = &*IT; 360 NodeTy *NextNode = getNext(Node); 361 NodeTy *PrevNode = getPrev(Node); 362 363 if (Node != Head) // Is PrevNode off the beginning of the list? 364 setNext(PrevNode, NextNode); 365 else 366 Head = NextNode; 367 setPrev(NextNode, PrevNode); 368 IT = NextNode; 369 removeNodeFromList(Node); // Notify traits that we removed a node... 370 371 // Set the next/prev pointers of the current node to null. This isn't 372 // strictly required, but this catches errors where a node is removed from 373 // an ilist (and potentially deleted) with iterators still pointing at it. 374 // When those iterators are incremented or decremented, they will assert on 375 // the null next/prev pointer instead of "usually working". 376 setNext(Node, 0); 377 setPrev(Node, 0); 378 return Node; 379 } 380 381 NodeTy *remove(const iterator &IT) { 382 iterator MutIt = IT; 383 return remove(MutIt); 384 } 385 386 // erase - remove a node from the controlled sequence... and delete it. 387 iterator erase(iterator where) { 388 deleteNode(remove(where)); 389 return where; 390 } 391 392 393private: 394 // transfer - The heart of the splice function. Move linked list nodes from 395 // [first, last) into position. 396 // 397 void transfer(iterator position, iplist &L2, iterator first, iterator last) { 398 assert(first != last && "Should be checked by callers"); 399 400 if (position != last) { 401 // Note: we have to be careful about the case when we move the first node 402 // in the list. This node is the list sentinel node and we can't move it. 403 NodeTy *ThisSentinel = getTail(); 404 setTail(0); 405 NodeTy *L2Sentinel = L2.getTail(); 406 L2.setTail(0); 407 408 // Remove [first, last) from its old position. 409 NodeTy *First = &*first, *Prev = getPrev(First); 410 NodeTy *Next = last.getNodePtrUnchecked(), *Last = getPrev(Next); 411 if (Prev) 412 setNext(Prev, Next); 413 else 414 L2.Head = Next; 415 setPrev(Next, Prev); 416 417 // Splice [first, last) into its new position. 418 NodeTy *PosNext = position.getNodePtrUnchecked(); 419 NodeTy *PosPrev = getPrev(PosNext); 420 421 // Fix head of list... 422 if (PosPrev) 423 setNext(PosPrev, First); 424 else 425 Head = First; 426 setPrev(First, PosPrev); 427 428 // Fix end of list... 429 setNext(Last, PosNext); 430 setPrev(PosNext, Last); 431 432 transferNodesFromList(L2, First, PosNext); 433 434 // Now that everything is set, restore the pointers to the list sentinals. 435 L2.setTail(L2Sentinel); 436 setTail(ThisSentinel); 437 } 438 } 439 440public: 441 442 //===----------------------------------------------------------------------=== 443 // Functionality derived from other functions defined above... 444 // 445 446 size_type size() const { 447 if (Head == 0) return 0; // Don't require construction of sentinal if empty. 448#if __GNUC__ == 2 449 // GCC 2.95 has a broken std::distance 450 size_type Result = 0; 451 std::distance(begin(), end(), Result); 452 return Result; 453#else 454 return std::distance(begin(), end()); 455#endif 456 } 457 458 iterator erase(iterator first, iterator last) { 459 while (first != last) 460 first = erase(first); 461 return last; 462 } 463 464 void clear() { if (Head) erase(begin(), end()); } 465 466 // Front and back inserters... 467 void push_front(NodeTy *val) { insert(begin(), val); } 468 void push_back(NodeTy *val) { insert(end(), val); } 469 void pop_front() { 470 assert(!empty() && "pop_front() on empty list!"); 471 erase(begin()); 472 } 473 void pop_back() { 474 assert(!empty() && "pop_back() on empty list!"); 475 iterator t = end(); erase(--t); 476 } 477 478 // Special forms of insert... 479 template<class InIt> void insert(iterator where, InIt first, InIt last) { 480 for (; first != last; ++first) insert(where, *first); 481 } 482 483 // Splice members - defined in terms of transfer... 484 void splice(iterator where, iplist &L2) { 485 if (!L2.empty()) 486 transfer(where, L2, L2.begin(), L2.end()); 487 } 488 void splice(iterator where, iplist &L2, iterator first) { 489 iterator last = first; ++last; 490 if (where == first || where == last) return; // No change 491 transfer(where, L2, first, last); 492 } 493 void splice(iterator where, iplist &L2, iterator first, iterator last) { 494 if (first != last) transfer(where, L2, first, last); 495 } 496 497 498 499 //===----------------------------------------------------------------------=== 500 // High-Level Functionality that shouldn't really be here, but is part of list 501 // 502 503 // These two functions are actually called remove/remove_if in list<>, but 504 // they actually do the job of erase, rename them accordingly. 505 // 506 void erase(const NodeTy &val) { 507 for (iterator I = begin(), E = end(); I != E; ) { 508 iterator next = I; ++next; 509 if (*I == val) erase(I); 510 I = next; 511 } 512 } 513 template<class Pr1> void erase_if(Pr1 pred) { 514 for (iterator I = begin(), E = end(); I != E; ) { 515 iterator next = I; ++next; 516 if (pred(*I)) erase(I); 517 I = next; 518 } 519 } 520 521 template<class Pr2> void unique(Pr2 pred) { 522 if (empty()) return; 523 for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) { 524 if (pred(*I)) 525 erase(Next); 526 else 527 I = Next; 528 Next = I; 529 } 530 } 531 void unique() { unique(op_equal); } 532 533 template<class Pr3> void merge(iplist &right, Pr3 pred) { 534 iterator first1 = begin(), last1 = end(); 535 iterator first2 = right.begin(), last2 = right.end(); 536 while (first1 != last1 && first2 != last2) 537 if (pred(*first2, *first1)) { 538 iterator next = first2; 539 transfer(first1, right, first2, ++next); 540 first2 = next; 541 } else { 542 ++first1; 543 } 544 if (first2 != last2) transfer(last1, right, first2, last2); 545 } 546 void merge(iplist &right) { return merge(right, op_less); } 547 548 template<class Pr3> void sort(Pr3 pred); 549 void sort() { sort(op_less); } 550 void reverse(); 551}; 552 553 554template<typename NodeTy> 555struct ilist : public iplist<NodeTy> { 556 typedef typename iplist<NodeTy>::size_type size_type; 557 typedef typename iplist<NodeTy>::iterator iterator; 558 559 ilist() {} 560 ilist(const ilist &right) { 561 insert(this->begin(), right.begin(), right.end()); 562 } 563 explicit ilist(size_type count) { 564 insert(this->begin(), count, NodeTy()); 565 } 566 ilist(size_type count, const NodeTy &val) { 567 insert(this->begin(), count, val); 568 } 569 template<class InIt> ilist(InIt first, InIt last) { 570 insert(this->begin(), first, last); 571 } 572 573 574 // Forwarding functions: A workaround for GCC 2.95 which does not correctly 575 // support 'using' declarations to bring a hidden member into scope. 576 // 577 iterator insert(iterator a, NodeTy *b){ return iplist<NodeTy>::insert(a, b); } 578 void push_front(NodeTy *a) { iplist<NodeTy>::push_front(a); } 579 void push_back(NodeTy *a) { iplist<NodeTy>::push_back(a); } 580 581 582 // Main implementation here - Insert for a node passed by value... 583 iterator insert(iterator where, const NodeTy &val) { 584 return insert(where, createNode(val)); 585 } 586 587 588 // Front and back inserters... 589 void push_front(const NodeTy &val) { insert(this->begin(), val); } 590 void push_back(const NodeTy &val) { insert(this->end(), val); } 591 592 // Special forms of insert... 593 template<class InIt> void insert(iterator where, InIt first, InIt last) { 594 for (; first != last; ++first) insert(where, *first); 595 } 596 void insert(iterator where, size_type count, const NodeTy &val) { 597 for (; count != 0; --count) insert(where, val); 598 } 599 600 // Assign special forms... 601 void assign(size_type count, const NodeTy &val) { 602 iterator I = this->begin(); 603 for (; I != this->end() && count != 0; ++I, --count) 604 *I = val; 605 if (count != 0) 606 insert(this->end(), val, val); 607 else 608 erase(I, this->end()); 609 } 610 template<class InIt> void assign(InIt first1, InIt last1) { 611 iterator first2 = this->begin(), last2 = this->end(); 612 for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) 613 *first1 = *first2; 614 if (first2 == last2) 615 erase(first1, last1); 616 else 617 insert(last1, first2, last2); 618 } 619 620 621 // Resize members... 622 void resize(size_type newsize, NodeTy val) { 623 iterator i = this->begin(); 624 size_type len = 0; 625 for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ; 626 627 if (len == newsize) 628 erase(i, this->end()); 629 else // i == end() 630 insert(this->end(), newsize - len, val); 631 } 632 void resize(size_type newsize) { resize(newsize, NodeTy()); } 633}; 634 635} // End llvm namespace 636 637namespace std { 638 // Ensure that swap uses the fast list swap... 639 template<class Ty> 640 void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 641 Left.swap(Right); 642 } 643} // End 'std' extensions... 644 645#endif // LLVM_ADT_ILIST_H 646