LLVM API Documentation
00001 //==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines classes to implement an intrusive doubly linked list class 00011 // (i.e. each node of the list must contain a next and previous field for the 00012 // list. 00013 // 00014 // The ilist_traits trait class is used to gain access to the next and previous 00015 // fields of the node type that the list is instantiated with. If it is not 00016 // specialized, the list defaults to using the getPrev(), getNext() method calls 00017 // to get the next and previous pointers. 00018 // 00019 // The ilist class itself, should be a plug in replacement for list, assuming 00020 // that the nodes contain next/prev pointers. This list replacement does not 00021 // provide a constant time size() method, so be careful to use empty() when you 00022 // really want to know if it's empty. 00023 // 00024 // The ilist class is implemented by allocating a 'tail' node when the list is 00025 // created (using ilist_traits<>::createSentinel()). This tail node is 00026 // absolutely required because the user must be able to compute end()-1. Because 00027 // of this, users of the direct next/prev links will see an extra link on the 00028 // end of the list, which should be ignored. 00029 // 00030 // Requirements for a user of this list: 00031 // 00032 // 1. The user must provide {g|s}et{Next|Prev} methods, or specialize 00033 // ilist_traits to provide an alternate way of getting and setting next and 00034 // prev links. 00035 // 00036 //===----------------------------------------------------------------------===// 00037 00038 #ifndef LLVM_ADT_ILIST_H 00039 #define LLVM_ADT_ILIST_H 00040 00041 #include "llvm/ADT/iterator.h" 00042 #include <cassert> 00043 00044 namespace llvm { 00045 00046 template<typename NodeTy, typename Traits> class iplist; 00047 template<typename NodeTy> class ilist_iterator; 00048 00049 /// ilist_nextprev_traits - A fragment for template traits for intrusive list 00050 /// that provides default next/prev implementations for common operations. 00051 /// 00052 template<typename NodeTy> 00053 struct ilist_nextprev_traits { 00054 static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } 00055 static NodeTy *getNext(NodeTy *N) { return N->getNext(); } 00056 static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } 00057 static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } 00058 00059 static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } 00060 static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } 00061 }; 00062 00063 template<typename NodeTy> 00064 struct ilist_traits; 00065 00066 /// ilist_sentinel_traits - A fragment for template traits for intrusive list 00067 /// that provides default sentinel implementations for common operations. 00068 /// 00069 /// ilist_sentinel_traits implements a lazy dynamic sentinel allocation 00070 /// strategy. The sentinel is stored in the prev field of ilist's Head. 00071 /// 00072 template<typename NodeTy> 00073 struct ilist_sentinel_traits { 00074 /// createSentinel - create the dynamic sentinel 00075 static NodeTy *createSentinel() { return new NodeTy(); } 00076 00077 /// destroySentinel - deallocate the dynamic sentinel 00078 static void destroySentinel(NodeTy *N) { delete N; } 00079 00080 /// provideInitialHead - when constructing an ilist, provide a starting 00081 /// value for its Head 00082 /// @return null node to indicate that it needs to be allocated later 00083 static NodeTy *provideInitialHead() { return 0; } 00084 00085 /// ensureHead - make sure that Head is either already 00086 /// initialized or assigned a fresh sentinel 00087 /// @return the sentinel 00088 static NodeTy *ensureHead(NodeTy *&Head) { 00089 if (!Head) { 00090 Head = ilist_traits<NodeTy>::createSentinel(); 00091 ilist_traits<NodeTy>::noteHead(Head, Head); 00092 ilist_traits<NodeTy>::setNext(Head, 0); 00093 return Head; 00094 } 00095 return ilist_traits<NodeTy>::getPrev(Head); 00096 } 00097 00098 /// noteHead - stash the sentinel into its default location 00099 static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { 00100 ilist_traits<NodeTy>::setPrev(NewHead, Sentinel); 00101 } 00102 }; 00103 00104 /// ilist_node_traits - A fragment for template traits for intrusive list 00105 /// that provides default node related operations. 00106 /// 00107 template<typename NodeTy> 00108 struct ilist_node_traits { 00109 static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); } 00110 static void deleteNode(NodeTy *V) { delete V; } 00111 00112 void addNodeToList(NodeTy *) {} 00113 void removeNodeFromList(NodeTy *) {} 00114 void transferNodesFromList(ilist_node_traits & /*SrcTraits*/, 00115 ilist_iterator<NodeTy> /*first*/, 00116 ilist_iterator<NodeTy> /*last*/) {} 00117 }; 00118 00119 /// ilist_default_traits - Default template traits for intrusive list. 00120 /// By inheriting from this, you can easily use default implementations 00121 /// for all common operations. 00122 /// 00123 template<typename NodeTy> 00124 struct ilist_default_traits : ilist_nextprev_traits<NodeTy>, 00125 ilist_sentinel_traits<NodeTy>, 00126 ilist_node_traits<NodeTy> { 00127 }; 00128 00129 // Template traits for intrusive list. By specializing this template class, you 00130 // can change what next/prev fields are used to store the links... 00131 template<typename NodeTy> 00132 struct ilist_traits : ilist_default_traits<NodeTy> {}; 00133 00134 // Const traits are the same as nonconst traits... 00135 template<typename Ty> 00136 struct ilist_traits<const Ty> : public ilist_traits<Ty> {}; 00137 00138 //===----------------------------------------------------------------------===// 00139 // ilist_iterator<Node> - Iterator for intrusive list. 00140 // 00141 template<typename NodeTy> 00142 class ilist_iterator 00143 : public bidirectional_iterator<NodeTy, ptrdiff_t> { 00144 00145 public: 00146 typedef ilist_traits<NodeTy> Traits; 00147 typedef bidirectional_iterator<NodeTy, ptrdiff_t> super; 00148 00149 typedef typename super::value_type value_type; 00150 typedef typename super::difference_type difference_type; 00151 typedef typename super::pointer pointer; 00152 typedef typename super::reference reference; 00153 private: 00154 pointer NodePtr; 00155 00156 // ilist_iterator is not a random-access iterator, but it has an 00157 // implicit conversion to pointer-type, which is. Declare (but 00158 // don't define) these functions as private to help catch 00159 // accidental misuse. 00160 void operator[](difference_type) const; 00161 void operator+(difference_type) const; 00162 void operator-(difference_type) const; 00163 void operator+=(difference_type) const; 00164 void operator-=(difference_type) const; 00165 template<class T> void operator<(T) const; 00166 template<class T> void operator<=(T) const; 00167 template<class T> void operator>(T) const; 00168 template<class T> void operator>=(T) const; 00169 template<class T> void operator-(T) const; 00170 public: 00171 00172 ilist_iterator(pointer NP) : NodePtr(NP) {} 00173 ilist_iterator(reference NR) : NodePtr(&NR) {} 00174 ilist_iterator() : NodePtr(0) {} 00175 00176 // This is templated so that we can allow constructing a const iterator from 00177 // a nonconst iterator... 00178 template<class node_ty> 00179 ilist_iterator(const ilist_iterator<node_ty> &RHS) 00180 : NodePtr(RHS.getNodePtrUnchecked()) {} 00181 00182 // This is templated so that we can allow assigning to a const iterator from 00183 // a nonconst iterator... 00184 template<class node_ty> 00185 const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { 00186 NodePtr = RHS.getNodePtrUnchecked(); 00187 return *this; 00188 } 00189 00190 // Accessors... 00191 operator pointer() const { 00192 assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!"); 00193 return NodePtr; 00194 } 00195 00196 reference operator*() const { 00197 assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!"); 00198 return *NodePtr; 00199 } 00200 pointer operator->() const { return &operator*(); } 00201 00202 // Comparison operators 00203 bool operator==(const ilist_iterator &RHS) const { 00204 return NodePtr == RHS.NodePtr; 00205 } 00206 bool operator!=(const ilist_iterator &RHS) const { 00207 return NodePtr != RHS.NodePtr; 00208 } 00209 00210 // Increment and decrement operators... 00211 ilist_iterator &operator--() { // predecrement - Back up 00212 NodePtr = Traits::getPrev(NodePtr); 00213 assert(NodePtr && "--'d off the beginning of an ilist!"); 00214 return *this; 00215 } 00216 ilist_iterator &operator++() { // preincrement - Advance 00217 NodePtr = Traits::getNext(NodePtr); 00218 assert(NodePtr && "++'d off the end of an ilist!"); 00219 return *this; 00220 } 00221 ilist_iterator operator--(int) { // postdecrement operators... 00222 ilist_iterator tmp = *this; 00223 --*this; 00224 return tmp; 00225 } 00226 ilist_iterator operator++(int) { // postincrement operators... 00227 ilist_iterator tmp = *this; 00228 ++*this; 00229 return tmp; 00230 } 00231 00232 // Internal interface, do not use... 00233 pointer getNodePtrUnchecked() const { return NodePtr; } 00234 }; 00235 00236 // do not implement. this is to catch errors when people try to use 00237 // them as random access iterators 00238 template<typename T> 00239 void operator-(int, ilist_iterator<T>); 00240 template<typename T> 00241 void operator-(ilist_iterator<T>,int); 00242 00243 template<typename T> 00244 void operator+(int, ilist_iterator<T>); 00245 template<typename T> 00246 void operator+(ilist_iterator<T>,int); 00247 00248 // operator!=/operator== - Allow mixed comparisons without dereferencing 00249 // the iterator, which could very likely be pointing to end(). 00250 template<typename T> 00251 bool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { 00252 return LHS != RHS.getNodePtrUnchecked(); 00253 } 00254 template<typename T> 00255 bool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { 00256 return LHS == RHS.getNodePtrUnchecked(); 00257 } 00258 template<typename T> 00259 bool operator!=(T* LHS, const ilist_iterator<T> &RHS) { 00260 return LHS != RHS.getNodePtrUnchecked(); 00261 } 00262 template<typename T> 00263 bool operator==(T* LHS, const ilist_iterator<T> &RHS) { 00264 return LHS == RHS.getNodePtrUnchecked(); 00265 } 00266 00267 00268 // Allow ilist_iterators to convert into pointers to a node automatically when 00269 // used by the dyn_cast, cast, isa mechanisms... 00270 00271 template<typename From> struct simplify_type; 00272 00273 template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { 00274 typedef NodeTy* SimpleType; 00275 00276 static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 00277 return &*Node; 00278 } 00279 }; 00280 template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { 00281 typedef NodeTy* SimpleType; 00282 00283 static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { 00284 return &*Node; 00285 } 00286 }; 00287 00288 00289 //===----------------------------------------------------------------------===// 00290 // 00291 /// iplist - The subset of list functionality that can safely be used on nodes 00292 /// of polymorphic types, i.e. a heterogenous list with a common base class that 00293 /// holds the next/prev pointers. The only state of the list itself is a single 00294 /// pointer to the head of the list. 00295 /// 00296 /// This list can be in one of three interesting states: 00297 /// 1. The list may be completely unconstructed. In this case, the head 00298 /// pointer is null. When in this form, any query for an iterator (e.g. 00299 /// begin() or end()) causes the list to transparently change to state #2. 00300 /// 2. The list may be empty, but contain a sentinel for the end iterator. This 00301 /// sentinel is created by the Traits::createSentinel method and is a link 00302 /// in the list. When the list is empty, the pointer in the iplist points 00303 /// to the sentinel. Once the sentinel is constructed, it 00304 /// is not destroyed until the list is. 00305 /// 3. The list may contain actual objects in it, which are stored as a doubly 00306 /// linked list of nodes. One invariant of the list is that the predecessor 00307 /// of the first node in the list always points to the last node in the list, 00308 /// and the successor pointer for the sentinel (which always stays at the 00309 /// end of the list) is always null. 00310 /// 00311 template<typename NodeTy, typename Traits=ilist_traits<NodeTy> > 00312 class iplist : public Traits { 00313 mutable NodeTy *Head; 00314 00315 // Use the prev node pointer of 'head' as the tail pointer. This is really a 00316 // circularly linked list where we snip the 'next' link from the sentinel node 00317 // back to the first node in the list (to preserve assertions about going off 00318 // the end of the list). 00319 NodeTy *getTail() { return this->ensureHead(Head); } 00320 const NodeTy *getTail() const { return this->ensureHead(Head); } 00321 void setTail(NodeTy *N) const { this->noteHead(Head, N); } 00322 00323 /// CreateLazySentinel - This method verifies whether the sentinel for the 00324 /// list has been created and lazily makes it if not. 00325 void CreateLazySentinel() const { 00326 this->ensureHead(Head); 00327 } 00328 00329 static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } 00330 static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } 00331 00332 // No fundamental reason why iplist can't be copyable, but the default 00333 // copy/copy-assign won't do. 00334 iplist(const iplist &); // do not implement 00335 void operator=(const iplist &); // do not implement 00336 00337 public: 00338 typedef NodeTy *pointer; 00339 typedef const NodeTy *const_pointer; 00340 typedef NodeTy &reference; 00341 typedef const NodeTy &const_reference; 00342 typedef NodeTy value_type; 00343 typedef ilist_iterator<NodeTy> iterator; 00344 typedef ilist_iterator<const NodeTy> const_iterator; 00345 typedef size_t size_type; 00346 typedef ptrdiff_t difference_type; 00347 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00348 typedef std::reverse_iterator<iterator> reverse_iterator; 00349 00350 iplist() : Head(this->provideInitialHead()) {} 00351 ~iplist() { 00352 if (!Head) return; 00353 clear(); 00354 Traits::destroySentinel(getTail()); 00355 } 00356 00357 // Iterator creation methods. 00358 iterator begin() { 00359 CreateLazySentinel(); 00360 return iterator(Head); 00361 } 00362 const_iterator begin() const { 00363 CreateLazySentinel(); 00364 return const_iterator(Head); 00365 } 00366 iterator end() { 00367 CreateLazySentinel(); 00368 return iterator(getTail()); 00369 } 00370 const_iterator end() const { 00371 CreateLazySentinel(); 00372 return const_iterator(getTail()); 00373 } 00374 00375 // reverse iterator creation methods. 00376 reverse_iterator rbegin() { return reverse_iterator(end()); } 00377 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 00378 reverse_iterator rend() { return reverse_iterator(begin()); } 00379 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 00380 00381 00382 // Miscellaneous inspection routines. 00383 size_type max_size() const { return size_type(-1); } 00384 bool empty() const { return Head == 0 || Head == getTail(); } 00385 00386 // Front and back accessor functions... 00387 reference front() { 00388 assert(!empty() && "Called front() on empty list!"); 00389 return *Head; 00390 } 00391 const_reference front() const { 00392 assert(!empty() && "Called front() on empty list!"); 00393 return *Head; 00394 } 00395 reference back() { 00396 assert(!empty() && "Called back() on empty list!"); 00397 return *this->getPrev(getTail()); 00398 } 00399 const_reference back() const { 00400 assert(!empty() && "Called back() on empty list!"); 00401 return *this->getPrev(getTail()); 00402 } 00403 00404 void swap(iplist &RHS) { 00405 assert(0 && "Swap does not use list traits callback correctly yet!"); 00406 std::swap(Head, RHS.Head); 00407 } 00408 00409 iterator insert(iterator where, NodeTy *New) { 00410 NodeTy *CurNode = where.getNodePtrUnchecked(); 00411 NodeTy *PrevNode = this->getPrev(CurNode); 00412 this->setNext(New, CurNode); 00413 this->setPrev(New, PrevNode); 00414 00415 if (CurNode != Head) // Is PrevNode off the beginning of the list? 00416 this->setNext(PrevNode, New); 00417 else 00418 Head = New; 00419 this->setPrev(CurNode, New); 00420 00421 this->addNodeToList(New); // Notify traits that we added a node... 00422 return New; 00423 } 00424 00425 iterator insertAfter(iterator where, NodeTy *New) { 00426 if (empty()) 00427 return insert(begin(), New); 00428 else 00429 return insert(++where, New); 00430 } 00431 00432 NodeTy *remove(iterator &IT) { 00433 assert(IT != end() && "Cannot remove end of list!"); 00434 NodeTy *Node = &*IT; 00435 NodeTy *NextNode = this->getNext(Node); 00436 NodeTy *PrevNode = this->getPrev(Node); 00437 00438 if (Node != Head) // Is PrevNode off the beginning of the list? 00439 this->setNext(PrevNode, NextNode); 00440 else 00441 Head = NextNode; 00442 this->setPrev(NextNode, PrevNode); 00443 IT = NextNode; 00444 this->removeNodeFromList(Node); // Notify traits that we removed a node... 00445 00446 // Set the next/prev pointers of the current node to null. This isn't 00447 // strictly required, but this catches errors where a node is removed from 00448 // an ilist (and potentially deleted) with iterators still pointing at it. 00449 // When those iterators are incremented or decremented, they will assert on 00450 // the null next/prev pointer instead of "usually working". 00451 this->setNext(Node, 0); 00452 this->setPrev(Node, 0); 00453 return Node; 00454 } 00455 00456 NodeTy *remove(const iterator &IT) { 00457 iterator MutIt = IT; 00458 return remove(MutIt); 00459 } 00460 00461 // erase - remove a node from the controlled sequence... and delete it. 00462 iterator erase(iterator where) { 00463 this->deleteNode(remove(where)); 00464 return where; 00465 } 00466 00467 00468 private: 00469 // transfer - The heart of the splice function. Move linked list nodes from 00470 // [first, last) into position. 00471 // 00472 void transfer(iterator position, iplist &L2, iterator first, iterator last) { 00473 assert(first != last && "Should be checked by callers"); 00474 00475 if (position != last) { 00476 // Note: we have to be careful about the case when we move the first node 00477 // in the list. This node is the list sentinel node and we can't move it. 00478 NodeTy *ThisSentinel = getTail(); 00479 setTail(0); 00480 NodeTy *L2Sentinel = L2.getTail(); 00481 L2.setTail(0); 00482 00483 // Remove [first, last) from its old position. 00484 NodeTy *First = &*first, *Prev = this->getPrev(First); 00485 NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next); 00486 if (Prev) 00487 this->setNext(Prev, Next); 00488 else 00489 L2.Head = Next; 00490 this->setPrev(Next, Prev); 00491 00492 // Splice [first, last) into its new position. 00493 NodeTy *PosNext = position.getNodePtrUnchecked(); 00494 NodeTy *PosPrev = this->getPrev(PosNext); 00495 00496 // Fix head of list... 00497 if (PosPrev) 00498 this->setNext(PosPrev, First); 00499 else 00500 Head = First; 00501 this->setPrev(First, PosPrev); 00502 00503 // Fix end of list... 00504 this->setNext(Last, PosNext); 00505 this->setPrev(PosNext, Last); 00506 00507 this->transferNodesFromList(L2, First, PosNext); 00508 00509 // Now that everything is set, restore the pointers to the list sentinels. 00510 L2.setTail(L2Sentinel); 00511 setTail(ThisSentinel); 00512 } 00513 } 00514 00515 public: 00516 00517 //===----------------------------------------------------------------------=== 00518 // Functionality derived from other functions defined above... 00519 // 00520 00521 size_type size() const { 00522 if (Head == 0) return 0; // Don't require construction of sentinel if empty. 00523 return std::distance(begin(), end()); 00524 } 00525 00526 iterator erase(iterator first, iterator last) { 00527 while (first != last) 00528 first = erase(first); 00529 return last; 00530 } 00531 00532 void clear() { if (Head) erase(begin(), end()); } 00533 00534 // Front and back inserters... 00535 void push_front(NodeTy *val) { insert(begin(), val); } 00536 void push_back(NodeTy *val) { insert(end(), val); } 00537 void pop_front() { 00538 assert(!empty() && "pop_front() on empty list!"); 00539 erase(begin()); 00540 } 00541 void pop_back() { 00542 assert(!empty() && "pop_back() on empty list!"); 00543 iterator t = end(); erase(--t); 00544 } 00545 00546 // Special forms of insert... 00547 template<class InIt> void insert(iterator where, InIt first, InIt last) { 00548 for (; first != last; ++first) insert(where, *first); 00549 } 00550 00551 // Splice members - defined in terms of transfer... 00552 void splice(iterator where, iplist &L2) { 00553 if (!L2.empty()) 00554 transfer(where, L2, L2.begin(), L2.end()); 00555 } 00556 void splice(iterator where, iplist &L2, iterator first) { 00557 iterator last = first; ++last; 00558 if (where == first || where == last) return; // No change 00559 transfer(where, L2, first, last); 00560 } 00561 void splice(iterator where, iplist &L2, iterator first, iterator last) { 00562 if (first != last) transfer(where, L2, first, last); 00563 } 00564 00565 00566 00567 //===----------------------------------------------------------------------=== 00568 // High-Level Functionality that shouldn't really be here, but is part of list 00569 // 00570 00571 // These two functions are actually called remove/remove_if in list<>, but 00572 // they actually do the job of erase, rename them accordingly. 00573 // 00574 void erase(const NodeTy &val) { 00575 for (iterator I = begin(), E = end(); I != E; ) { 00576 iterator next = I; ++next; 00577 if (*I == val) erase(I); 00578 I = next; 00579 } 00580 } 00581 template<class Pr1> void erase_if(Pr1 pred) { 00582 for (iterator I = begin(), E = end(); I != E; ) { 00583 iterator next = I; ++next; 00584 if (pred(*I)) erase(I); 00585 I = next; 00586 } 00587 } 00588 00589 template<class Pr2> void unique(Pr2 pred) { 00590 if (empty()) return; 00591 for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) { 00592 if (pred(*I)) 00593 erase(Next); 00594 else 00595 I = Next; 00596 Next = I; 00597 } 00598 } 00599 void unique() { unique(op_equal); } 00600 00601 template<class Pr3> void merge(iplist &right, Pr3 pred) { 00602 iterator first1 = begin(), last1 = end(); 00603 iterator first2 = right.begin(), last2 = right.end(); 00604 while (first1 != last1 && first2 != last2) 00605 if (pred(*first2, *first1)) { 00606 iterator next = first2; 00607 transfer(first1, right, first2, ++next); 00608 first2 = next; 00609 } else { 00610 ++first1; 00611 } 00612 if (first2 != last2) transfer(last1, right, first2, last2); 00613 } 00614 void merge(iplist &right) { return merge(right, op_less); } 00615 00616 template<class Pr3> void sort(Pr3 pred); 00617 void sort() { sort(op_less); } 00618 void reverse(); 00619 }; 00620 00621 00622 template<typename NodeTy> 00623 struct ilist : public iplist<NodeTy> { 00624 typedef typename iplist<NodeTy>::size_type size_type; 00625 typedef typename iplist<NodeTy>::iterator iterator; 00626 00627 ilist() {} 00628 ilist(const ilist &right) { 00629 insert(this->begin(), right.begin(), right.end()); 00630 } 00631 explicit ilist(size_type count) { 00632 insert(this->begin(), count, NodeTy()); 00633 } 00634 ilist(size_type count, const NodeTy &val) { 00635 insert(this->begin(), count, val); 00636 } 00637 template<class InIt> ilist(InIt first, InIt last) { 00638 insert(this->begin(), first, last); 00639 } 00640 00641 // bring hidden functions into scope 00642 using iplist<NodeTy>::insert; 00643 using iplist<NodeTy>::push_front; 00644 using iplist<NodeTy>::push_back; 00645 00646 // Main implementation here - Insert for a node passed by value... 00647 iterator insert(iterator where, const NodeTy &val) { 00648 return insert(where, createNode(val)); 00649 } 00650 00651 00652 // Front and back inserters... 00653 void push_front(const NodeTy &val) { insert(this->begin(), val); } 00654 void push_back(const NodeTy &val) { insert(this->end(), val); } 00655 00656 // Special forms of insert... 00657 template<class InIt> void insert(iterator where, InIt first, InIt last) { 00658 for (; first != last; ++first) insert(where, *first); 00659 } 00660 void insert(iterator where, size_type count, const NodeTy &val) { 00661 for (; count != 0; --count) insert(where, val); 00662 } 00663 00664 // Assign special forms... 00665 void assign(size_type count, const NodeTy &val) { 00666 iterator I = this->begin(); 00667 for (; I != this->end() && count != 0; ++I, --count) 00668 *I = val; 00669 if (count != 0) 00670 insert(this->end(), val, val); 00671 else 00672 erase(I, this->end()); 00673 } 00674 template<class InIt> void assign(InIt first1, InIt last1) { 00675 iterator first2 = this->begin(), last2 = this->end(); 00676 for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) 00677 *first1 = *first2; 00678 if (first2 == last2) 00679 erase(first1, last1); 00680 else 00681 insert(last1, first2, last2); 00682 } 00683 00684 00685 // Resize members... 00686 void resize(size_type newsize, NodeTy val) { 00687 iterator i = this->begin(); 00688 size_type len = 0; 00689 for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ; 00690 00691 if (len == newsize) 00692 erase(i, this->end()); 00693 else // i == end() 00694 insert(this->end(), newsize - len, val); 00695 } 00696 void resize(size_type newsize) { resize(newsize, NodeTy()); } 00697 }; 00698 00699 } // End llvm namespace 00700 00701 namespace std { 00702 // Ensure that swap uses the fast list swap... 00703 template<class Ty> 00704 void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 00705 Left.swap(Right); 00706 } 00707 } // End 'std' extensions... 00708 00709 #endif // LLVM_ADT_ILIST_H