include/Support/ilist

   1 //===-- <Support/ilist> - Intrusive Linked List Template ---------*- C++ -*--=//
   2 //
   3 // This file defines classes to implement an intrusive doubly linked list class
   4 // (ie each node of the list must contain a next and previous field for the
   5 // list.
   6 //
   7 // The ilist_traits trait class is used to gain access to the next and previous
   8 // fields of the node type that the list is instantiated with.  If it is not
   9 // specialized, the list defaults to using the getPrev(), getNext() method calls
  10 // to get the next and previous pointers.
  11 //
  12 // The ilist class itself, should be a plug in replacement for list, assuming
  13 // that the nodes contain next/prev pointers.  This list replacement does not
  14 // provides a constant time size() method, so be careful to use empty() when you
  15 // really want to know if it's empty.
  16 //
  17 // The ilist class is implemented by allocating a 'tail' node when the list is
  18 // created (using ilist_traits<>::createEndMarker()).  This tail node is
  19 // absolutely required because the user must be able to compute end()-1. Because
  20 // of this, users of the direct next/prev links will see an extra link on the
  21 // end of the list, which should be ignored.
  22 //
  23 // Requirements for a user of this list:
  24 //
  25 //   1. The user must provide {g|s}et{Next|Prev} methods, or specialize
  26 //      ilist_traits to provide an alternate way of getting and setting next and
  27 //      prev links.
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #ifndef SUPPORT_ILIST
  32 #define SUPPORT_ILIST
  33
  34 #include <algorithm>
  35 #include <Support/iterator>
  36
  37 template<typename NodeTy, typename Traits> class iplist;
  38 template<typename NodeTy> class ilist_iterator;
  39
  40 // Template traits for intrusive list.  By specializing this template class, you
  41 // can change what next/prev fields are used to store the links...
  42 template<typename NodeTy>
  43 struct ilist_traits {
  44   static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); }
  45   static NodeTy *getNext(NodeTy *N) { return N->getNext(); }
  46   static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); }
  47   static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); }
  48
  49   static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); }
  50   static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
  51
  52   static NodeTy *createNode() { return new NodeTy(); }
  53   static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
  54
  55
  56   void addNodeToList(NodeTy *NTy) {}
  57   void removeNodeFromList(NodeTy *NTy) {}
  58   void transferNodesFromList(iplist<NodeTy, ilist_traits> &L2,
  59                              ilist_iterator<NodeTy> first,
  60                              ilist_iterator<NodeTy> last) {}
  61 };
  62
  63 // Const traits are the same as nonconst traits...
  64 template<typename Ty>
  65 struct ilist_traits<const Ty> : public ilist_traits<Ty> {};
  66
  67
  68 //===----------------------------------------------------------------------===//
  69 // ilist_iterator<Node> - Iterator for intrusive list.
  70 //
  71 template<typename NodeTy>
  72 class ilist_iterator
  73   : public bidirectional_iterator<NodeTy, ptrdiff_t> {
  74   typedef ilist_traits<NodeTy> Traits;
  75   typedef bidirectional_iterator<NodeTy, ptrdiff_t> super;
  76
  77   typedef typename super::pointer pointer;
  78   typedef typename super::reference reference;
  79   pointer NodePtr;
  80 public:
  81   typedef size_t size_type;
  82
  83   ilist_iterator(pointer NP) : NodePtr(NP) {}
  84   ilist_iterator(reference NR) : NodePtr(&NR) {}
  85   ilist_iterator() : NodePtr(0) {}
  86
  87   // This is templated so that we can allow constructing a const iterator from
  88   // a nonconst iterator...
  89   template<class node_ty>
  90   ilist_iterator(const ilist_iterator<node_ty> &RHS)
  91     : NodePtr(RHS.getNodePtrUnchecked()) {}
  92
  93   // This is templated so that we can allow assigning to a const iterator from
  94   // a nonconst iterator...
  95   template<class node_ty>
  96   const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) {
  97     NodePtr = RHS.getNodePtrUnchecked();
  98     return *this;
  99   }
 100
 101   // Accessors...
 102   operator pointer() const {
 103     assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!");
 104     return NodePtr;
 105   }
 106
 107   reference operator*() const {
 108     assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!");
 109     return *NodePtr;
 110   }
 111   pointer operator->() { return &operator*(); }
 112   const pointer operator->() const { return &operator*(); }
 113
 114   // Comparison operators
 115   bool operator==(const ilist_iterator &RHS) const {
 116     return NodePtr == RHS.NodePtr;
 117   }
 118   bool operator!=(const ilist_iterator &RHS) const {
 119     return NodePtr != RHS.NodePtr;
 120   }
 121
 122   // Increment and decrement operators...
 123   ilist_iterator &operator--() {      // predecrement - Back up
 124     NodePtr = Traits::getPrev(NodePtr);
 125     assert(NodePtr && "--'d off the beginning of an ilist!");
 126     return *this;
 127   }
 128   ilist_iterator &operator++() {      // preincrement - Advance
 129     NodePtr = Traits::getNext(NodePtr);
 130     assert(NodePtr && "++'d off the end of an ilist!");
 131     return *this;
 132   }
 133   ilist_iterator operator--(int) {    // postdecrement operators...
 134     ilist_iterator tmp = *this;
 135     --*this;
 136     return tmp;
 137   }
 138   ilist_iterator operator++(int) {    // postincrement operators...
 139     ilist_iterator tmp = *this;
 140     ++*this;
 141     return tmp;
 142   }
 143
 144
 145   // Dummy operators to make errors apparent...
 146   template<class X> void operator+(X Val) {}
 147   template<class X> void operator-(X Val) {}
 148
 149   // Internal interface, do not use...
 150   pointer getNodePtrUnchecked() const { return NodePtr; }
 151 };
 152
 153 // Allow ilist_iterators to convert into pointers to a node automatically when
 154 // used by the dyn_cast, cast, isa mechanisms...
 155
 156 template<typename From> struct simplify_type;
 157
 158 template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > {
 159   typedef NodeTy* SimpleType;
 160
 161   static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
 162     return &*Node;
 163   }
 164 };
 165 template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > {
 166   typedef NodeTy* SimpleType;
 167
 168   static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
 169     return &*Node;
 170   }
 171 };
 172
 173
 174 //===----------------------------------------------------------------------===//
 175 //
 176 // iplist - The subset of list functionality that can safely be used on nodes of
 177 // polymorphic types, ie a heterogeneus list with a common base class that holds
 178 // the next/prev pointers...
 179 //
 180 template<typename NodeTy, typename Traits=ilist_traits<NodeTy> >
 181 class iplist : public Traits {
 182   NodeTy *Head, *Tail;
 183
 184   static bool op_less(NodeTy &L, NodeTy &R) { return L < R; }
 185   static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; }
 186 public:
 187   typedef NodeTy *pointer;
 188   typedef const NodeTy *const_pointer;
 189   typedef NodeTy &reference;
 190   typedef const NodeTy &const_reference;
 191   typedef NodeTy value_type;
 192   typedef ilist_iterator<NodeTy> iterator;
 193   typedef ilist_iterator<const NodeTy> const_iterator;
 194   typedef size_t size_type;
 195   typedef ptrdiff_t difference_type;
 196   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
 197   typedef std::reverse_iterator<iterator>  reverse_iterator;
 198
 199   iplist() : Head(createNode()), Tail(Head) {
 200     setNext(Head, 0);
 201     setPrev(Head, 0);
 202   }
 203   ~iplist() { clear(); delete Tail; }
 204
 205   // Iterator creation methods...
 206   iterator begin()             { return iterator(Head); }
 207   const_iterator begin() const { return const_iterator(Head); }
 208   iterator end()               { return iterator(Tail); }
 209   const_iterator end() const   { return const_iterator(Tail); }
 210
 211   // reverse iterator creation methods...
 212   reverse_iterator rbegin()            { return reverse_iterator(end()); }
 213   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
 214   reverse_iterator rend()              { return reverse_iterator(begin()); }
 215   const_reverse_iterator rend() const  {return const_reverse_iterator(begin());}
 216
 217   // Miscellaneous inspection routines...
 218   size_type max_size() const { return size_type(-1); }
 219   bool empty() const { return Head == Tail; }
 220
 221   // Front and back accessor functions...
 222   reference front() {
 223     assert(!empty() && "Called front() on empty list!");
 224     return *Head;
 225   }
 226   const_reference front() const {
 227     assert(!empty() && "Called front() on empty list!");
 228     return *Head;
 229   }
 230   reference back() {
 231     assert(!empty() && "Called back() on empty list!");
 232     return *getPrev(Tail);
 233   }
 234   const_reference back() const {
 235     assert(!empty() && "Called back() on empty list!");
 236     return *getPrev(Tail);
 237   }
 238
 239   void swap(iplist &RHS) {
 240     abort();     // Swap does not use list traits callback correctly yet!
 241     std::swap(Head, RHS.Head);
 242     std::swap(Tail, RHS.Tail);
 243   }
 244
 245   iterator insert(iterator where, NodeTy *New) {
 246     NodeTy *CurNode = where.getNodePtrUnchecked(), *PrevNode = getPrev(CurNode);
 247     setNext(New, CurNode);
 248     setPrev(New, PrevNode);
 249
 250     if (PrevNode)
 251       setNext(PrevNode, New);
 252     else
 253       Head = New;
 254     setPrev(CurNode, New);
 255
 256     addNodeToList(New);  // Notify traits that we added a node...
 257     return New;
 258   }
 259
 260   NodeTy *remove(iterator &IT) {
 261     assert(IT != end() && "Cannot remove end of list!");
 262     NodeTy *Node = &*IT;
 263     NodeTy *NextNode = getNext(Node);
 264     NodeTy *PrevNode = getPrev(Node);
 265
 266     if (PrevNode)
 267       setNext(PrevNode, NextNode);
 268     else
 269       Head = NextNode;
 270     setPrev(NextNode, PrevNode);
 271     IT = NextNode;
 272     removeNodeFromList(Node);  // Notify traits that we added a node...
 273     return Node;
 274   }
 275
 276   NodeTy *remove(const iterator &IT) {
 277     iterator MutIt = IT;
 278     return remove(MutIt);
 279   }
 280
 281   // erase - remove a node from the controlled sequence... and delete it.
 282   iterator erase(iterator where) {
 283     delete remove(where);
 284     return where;
 285   }
 286
 287
 288 private:
 289   // transfer - The heart of the splice function.  Move linked list nodes from
 290   // [first, last) into position.
 291   //
 292   void transfer(iterator position, iplist &L2, iterator first, iterator last) {
 293     assert(first != last && "Should be checked by callers");
 294     if (position != last) {
 295       // Remove [first, last) from its old position.
 296       NodeTy *First = &*first, *Prev = getPrev(First);
 297       NodeTy *Next = last.getNodePtrUnchecked(), *Last = getPrev(Next);
 298       if (Prev)
 299         setNext(Prev, Next);
 300       else
 301         L2.Head = Next;
 302       setPrev(Next, Prev);
 303
 304       // Splice [first, last) into its new position.
 305       NodeTy *PosNext = position.getNodePtrUnchecked();
 306       NodeTy *PosPrev = getPrev(PosNext);
 307
 308       // Fix head of list...
 309       if (PosPrev)
 310         setNext(PosPrev, First);
 311       else
 312         Head = First;
 313       setPrev(First, PosPrev);
 314
 315       // Fix end of list...
 316       setNext(Last, PosNext);
 317       setPrev(PosNext, Last);
 318
 319       transferNodesFromList(L2, First, PosNext);
 320     }
 321   }
 322
 323 public:
 324
 325   //===----------------------------------------------------------------------===
 326   // Functionality derived from other functions defined above...
 327   //
 328
 329   size_type size() const {
 330 #if __GNUC__ == 3
 331     size_type Result = std::distance(begin(), end());
 332 #else
 333     size_type Result = 0;
 334     std::distance(begin(), end(), Result);
 335 #endif
 336     return Result;
 337   }
 338
 339   iterator erase(iterator first, iterator last) {
 340     while (first != last)
 341       first = erase(first);
 342     return last;
 343   }
 344
 345   void clear() { erase(begin(), end()); }
 346
 347   // Front and back inserters...
 348   void push_front(NodeTy *val) { insert(begin(), val); }
 349   void push_back(NodeTy *val) { insert(end(), val); }
 350   void pop_front() {
 351     assert(!empty() && "pop_front() on empty list!");
 352     erase(begin());
 353   }
 354   void pop_back() {
 355     assert(!empty() && "pop_back() on empty list!");
 356     iterator t = end(); erase(--t);
 357   }
 358
 359   // Special forms of insert...
 360   template<class InIt> void insert(iterator where, InIt first, InIt last) {
 361     for (; first != last; ++first) insert(where, *first);
 362   }
 363
 364   // Splice members - defined in terms of transfer...
 365   void splice(iterator where, iplist &L2) {
 366     if (!L2.empty())
 367       transfer(where, L2, L2.begin(), L2.end());
 368   }
 369   void splice(iterator where, iplist &L2, iterator first) {
 370     iterator last = first; ++last;
 371     if (where == first || where == last) return; // No change
 372     transfer(where, L2, first, last);
 373   }
 374   void splice(iterator where, iplist &L2, iterator first, iterator last) {
 375     if (first != last) transfer(where, L2, first, last);
 376   }
 377
 378
 379
 380   //===----------------------------------------------------------------------===
 381   // High-Level Functionality that shouldn't really be here, but is part of list
 382   //
 383
 384   // These two functions are actually called remove/remove_if in list<>, but
 385   // they actually do the job of erase, rename them accordingly.
 386   //
 387   void erase(const NodeTy &val) {
 388     for (iterator I = begin(), E = end(); I != E; ) {
 389       iterator next = I; ++next;
 390       if (*I == val) erase(I);
 391       I = next;
 392     }
 393   }
 394   template<class Pr1> void erase_if(Pr1 pred) {
 395     for (iterator I = begin(), E = end(); I != E; ) {
 396       iterator next = I; ++next;
 397       if (pred(*I)) erase(I);
 398       I = next;
 399     }
 400   }
 401
 402   template<class Pr2> void unique(Pr2 pred) {
 403     if (empty()) return;
 404     for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) {
 405       if (pred(*I))
 406         erase(Next);
 407       else
 408         I = Next;
 409       Next = I;
 410     }
 411   }
 412   void unique() { unique(op_equal); }
 413
 414   template<class Pr3> void merge(iplist &right, Pr3 pred) {
 415     iterator first1 = begin(), last1 = end();
 416     iterator first2 = right.begin(), last2 = right.end();
 417     while (first1 != last1 && first2 != last2)
 418       if (pred(*first2, *first1)) {
 419         iterator next = first2;
 420         transfer(first1, right, first2, ++next);
 421         first2 = next;
 422       } else {
 423         ++first1;
 424       }
 425     if (first2 != last2) transfer(last1, right, first2, last2);
 426   }
 427   void merge(iplist &right) { return merge(right, op_less); }
 428
 429   template<class Pr3> void sort(Pr3 pred);
 430   void sort() { sort(op_less); }
 431   void reverse();
 432 };
 433
 434
 435 template<typename NodeTy>
 436 struct ilist : public iplist<NodeTy> {
 437   typedef typename iplist<NodeTy>::size_type size_type;
 438   typedef typename iplist<NodeTy>::iterator iterator;
 439
 440   ilist() {}
 441   ilist(const ilist &right) {
 442     insert(begin(), right.begin(), right.end());
 443   }
 444   explicit ilist(size_type count) {
 445     insert(begin(), count, NodeTy());
 446   }
 447   ilist(size_type count, const NodeTy &val) {
 448     insert(begin(), count, val);
 449   }
 450   template<class InIt> ilist(InIt first, InIt last) {
 451     insert(begin(), first, last);
 452   }
 453
 454
 455   // Forwarding functions: A workaround for GCC 2.95 which does not correctly
 456   // support 'using' declarations to bring a hidden member into scope.
 457   //
 458   iterator insert(iterator a, NodeTy *b){ return iplist<NodeTy>::insert(a, b); }
 459   void push_front(NodeTy *a) { iplist<NodeTy>::push_front(a); }
 460   void push_back(NodeTy *a)  { iplist<NodeTy>::push_back(a); }
 461
 462
 463   // Main implementation here - Insert for a node passed by value...
 464   iterator insert(iterator where, const NodeTy &val) {
 465     return insert(where, createNode(val));
 466   }
 467
 468
 469   // Front and back inserters...
 470   void push_front(const NodeTy &val) { insert(begin(), val); }
 471   void push_back(const NodeTy &val) { insert(end(), val); }
 472
 473   // Special forms of insert...
 474   template<class InIt> void insert(iterator where, InIt first, InIt last) {
 475     for (; first != last; ++first) insert(where, *first);
 476   }
 477   void insert(iterator where, size_type count, const NodeTy &val) {
 478     for (; count != 0; --count) insert(where, val);
 479   }
 480
 481   // Assign special forms...
 482   void assign(size_type count, const NodeTy &val) {
 483     iterator I = begin();
 484     for (; I != end() && count != 0; ++I, --count)
 485       *I = val;
 486     if (count != 0)
 487       insert(end(), n, val);
 488     else
 489       erase(I, end());
 490   }
 491   template<class InIt> void assign(InIt first, InIt last) {
 492     iterator first1 = begin(), last1 = end();
 493     for ( ; first1 != last1 && first2 != last2; ++first1, ++first2)
 494       *first1 = *first2;
 495     if (first2 == last2)
 496       erase(first1, last1);
 497     else
 498       insert(last1, first2, last2);
 499   }
 500
 501
 502   // Resize members...
 503   void resize(size_type newsize, NodeTy val) {
 504     iterator i = begin();
 505     size_type len = 0;
 506     for ( ; i != end() && len < newsize; ++i, ++len) /* empty*/ ;
 507
 508     if (len == newsize)
 509       erase(i, end());
 510     else                                          // i == end()
 511       insert(end(), newsize - len, val);
 512   }
 513   void resize(size_type newsize) { resize(newsize, NodeTy()); }
 514 };
 515
 516 namespace std {
 517   // Ensure that swap uses the fast list swap...
 518   template<class Ty>
 519   void swap(iplist<Ty> &Left, iplist<Ty> &Right) {
 520     Left.swap(Right);
 521   }
 522 }  // End 'std' extensions...
 523
 524 #endif