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