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