• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/Support/Compiler.h"
42 #include <algorithm>
43 #include <cassert>
44 #include <cstddef>
45 #include <iterator>
46 
47 namespace llvm {
48 
49 template<typename NodeTy, typename Traits> class iplist;
50 template<typename NodeTy> class ilist_iterator;
51 
52 /// ilist_nextprev_traits - A fragment for template traits for intrusive list
53 /// that provides default next/prev implementations for common operations.
54 ///
55 template<typename NodeTy>
56 struct ilist_nextprev_traits {
getPrevilist_nextprev_traits57   static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); }
getNextilist_nextprev_traits58   static NodeTy *getNext(NodeTy *N) { return N->getNext(); }
getPrevilist_nextprev_traits59   static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); }
getNextilist_nextprev_traits60   static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); }
61 
setPrevilist_nextprev_traits62   static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); }
setNextilist_nextprev_traits63   static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
64 };
65 
66 template<typename NodeTy>
67 struct ilist_traits;
68 
69 /// ilist_sentinel_traits - A fragment for template traits for intrusive list
70 /// that provides default sentinel implementations for common operations.
71 ///
72 /// ilist_sentinel_traits implements a lazy dynamic sentinel allocation
73 /// strategy. The sentinel is stored in the prev field of ilist's Head.
74 ///
75 template<typename NodeTy>
76 struct ilist_sentinel_traits {
77   /// createSentinel - create the dynamic sentinel
createSentinelilist_sentinel_traits78   static NodeTy *createSentinel() { return new NodeTy(); }
79 
80   /// destroySentinel - deallocate the dynamic sentinel
destroySentinelilist_sentinel_traits81   static void destroySentinel(NodeTy *N) { delete N; }
82 
83   /// provideInitialHead - when constructing an ilist, provide a starting
84   /// value for its Head
85   /// @return null node to indicate that it needs to be allocated later
provideInitialHeadilist_sentinel_traits86   static NodeTy *provideInitialHead() { return nullptr; }
87 
88   /// ensureHead - make sure that Head is either already
89   /// initialized or assigned a fresh sentinel
90   /// @return the sentinel
ensureHeadilist_sentinel_traits91   static NodeTy *ensureHead(NodeTy *&Head) {
92     if (!Head) {
93       Head = ilist_traits<NodeTy>::createSentinel();
94       ilist_traits<NodeTy>::noteHead(Head, Head);
95       ilist_traits<NodeTy>::setNext(Head, nullptr);
96       return Head;
97     }
98     return ilist_traits<NodeTy>::getPrev(Head);
99   }
100 
101   /// noteHead - stash the sentinel into its default location
noteHeadilist_sentinel_traits102   static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) {
103     ilist_traits<NodeTy>::setPrev(NewHead, Sentinel);
104   }
105 };
106 
107 template <typename NodeTy> class ilist_half_node;
108 template <typename NodeTy> class ilist_node;
109 
110 /// Traits with an embedded ilist_node as a sentinel.
111 ///
112 /// FIXME: The downcast in createSentinel() is UB.
113 template <typename NodeTy> struct ilist_embedded_sentinel_traits {
114   /// Get hold of the node that marks the end of the list.
createSentinelilist_embedded_sentinel_traits115   NodeTy *createSentinel() const {
116     // Since i(p)lists always publicly derive from their corresponding traits,
117     // placing a data member in this class will augment the i(p)list.  But since
118     // the NodeTy is expected to be publicly derive from ilist_node<NodeTy>,
119     // there is a legal viable downcast from it to NodeTy. We use this trick to
120     // superimpose an i(p)list with a "ghostly" NodeTy, which becomes the
121     // sentinel. Dereferencing the sentinel is forbidden (save the
122     // ilist_node<NodeTy>), so no one will ever notice the superposition.
123     return static_cast<NodeTy *>(&Sentinel);
124   }
destroySentinelilist_embedded_sentinel_traits125   static void destroySentinel(NodeTy *) {}
126 
provideInitialHeadilist_embedded_sentinel_traits127   NodeTy *provideInitialHead() const { return createSentinel(); }
ensureHeadilist_embedded_sentinel_traits128   NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
noteHeadilist_embedded_sentinel_traits129   static void noteHead(NodeTy *, NodeTy *) {}
130 
131 private:
132   mutable ilist_node<NodeTy> Sentinel;
133 };
134 
135 /// Trait with an embedded ilist_half_node as a sentinel.
136 ///
137 /// FIXME: The downcast in createSentinel() is UB.
138 template <typename NodeTy> struct ilist_half_embedded_sentinel_traits {
139   /// Get hold of the node that marks the end of the list.
createSentinelilist_half_embedded_sentinel_traits140   NodeTy *createSentinel() const {
141     // See comment in ilist_embedded_sentinel_traits::createSentinel().
142     return static_cast<NodeTy *>(&Sentinel);
143   }
destroySentinelilist_half_embedded_sentinel_traits144   static void destroySentinel(NodeTy *) {}
145 
provideInitialHeadilist_half_embedded_sentinel_traits146   NodeTy *provideInitialHead() const { return createSentinel(); }
ensureHeadilist_half_embedded_sentinel_traits147   NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
noteHeadilist_half_embedded_sentinel_traits148   static void noteHead(NodeTy *, NodeTy *) {}
149 
150 private:
151   mutable ilist_half_node<NodeTy> Sentinel;
152 };
153 
154 /// ilist_node_traits - A fragment for template traits for intrusive list
155 /// that provides default node related operations.
156 ///
157 template<typename NodeTy>
158 struct ilist_node_traits {
createNodeilist_node_traits159   static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
deleteNodeilist_node_traits160   static void deleteNode(NodeTy *V) { delete V; }
161 
addNodeToListilist_node_traits162   void addNodeToList(NodeTy *) {}
removeNodeFromListilist_node_traits163   void removeNodeFromList(NodeTy *) {}
transferNodesFromListilist_node_traits164   void transferNodesFromList(ilist_node_traits &    /*SrcTraits*/,
165                              ilist_iterator<NodeTy> /*first*/,
166                              ilist_iterator<NodeTy> /*last*/) {}
167 };
168 
169 /// ilist_default_traits - Default template traits for intrusive list.
170 /// By inheriting from this, you can easily use default implementations
171 /// for all common operations.
172 ///
173 template<typename NodeTy>
174 struct ilist_default_traits : public ilist_nextprev_traits<NodeTy>,
175                               public ilist_sentinel_traits<NodeTy>,
176                               public ilist_node_traits<NodeTy> {
177 };
178 
179 // Template traits for intrusive list.  By specializing this template class, you
180 // can change what next/prev fields are used to store the links...
181 template<typename NodeTy>
182 struct ilist_traits : public ilist_default_traits<NodeTy> {};
183 
184 // Const traits are the same as nonconst traits...
185 template<typename Ty>
186 struct ilist_traits<const Ty> : public ilist_traits<Ty> {};
187 
188 //===----------------------------------------------------------------------===//
189 // Iterator for intrusive list.
190 //
191 template <typename NodeTy>
192 class ilist_iterator
193     : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> {
194 public:
195   typedef ilist_traits<NodeTy> Traits;
196   typedef std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t>
197       super;
198 
199   typedef typename super::value_type value_type;
200   typedef typename super::difference_type difference_type;
201   typedef typename super::pointer pointer;
202   typedef typename super::reference reference;
203 
204 private:
205   pointer NodePtr;
206 
207 public:
208   explicit ilist_iterator(pointer NP) : NodePtr(NP) {}
209   explicit ilist_iterator(reference NR) : NodePtr(&NR) {}
210   ilist_iterator() : NodePtr(nullptr) {}
211 
212   // This is templated so that we can allow constructing a const iterator from
213   // a nonconst iterator...
214   template <class node_ty>
215   ilist_iterator(const ilist_iterator<node_ty> &RHS)
216       : NodePtr(RHS.getNodePtrUnchecked()) {}
217 
218   // This is templated so that we can allow assigning to a const iterator from
219   // a nonconst iterator...
220   template <class node_ty>
221   const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) {
222     NodePtr = RHS.getNodePtrUnchecked();
223     return *this;
224   }
225 
226   void reset(pointer NP) { NodePtr = NP; }
227 
228   // Accessors...
229   explicit operator pointer() const { return NodePtr; }
230   reference operator*() const { return *NodePtr; }
231   pointer operator->() const { return &operator*(); }
232 
233   // Comparison operators
234   template <class Y> bool operator==(const ilist_iterator<Y> &RHS) const {
235     return NodePtr == RHS.getNodePtrUnchecked();
236   }
237   template <class Y> bool operator!=(const ilist_iterator<Y> &RHS) const {
238     return NodePtr != RHS.getNodePtrUnchecked();
239   }
240 
241   // Increment and decrement operators...
242   ilist_iterator &operator--() {
243     NodePtr = Traits::getPrev(NodePtr);
244     assert(NodePtr && "--'d off the beginning of an ilist!");
245     return *this;
246   }
247   ilist_iterator &operator++() {
248     NodePtr = Traits::getNext(NodePtr);
249     return *this;
250   }
251   ilist_iterator operator--(int) {
252     ilist_iterator tmp = *this;
253     --*this;
254     return tmp;
255   }
256   ilist_iterator operator++(int) {
257     ilist_iterator tmp = *this;
258     ++*this;
259     return tmp;
260   }
261 
262   // Internal interface, do not use...
263   pointer getNodePtrUnchecked() const { return NodePtr; }
264 };
265 
266 // Allow ilist_iterators to convert into pointers to a node automatically when
267 // used by the dyn_cast, cast, isa mechanisms...
268 
269 template<typename From> struct simplify_type;
270 
271 template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > {
272   typedef NodeTy* SimpleType;
273 
274   static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) {
275     return &*Node;
276   }
277 };
278 template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > {
279   typedef /*const*/ NodeTy* SimpleType;
280 
281   static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
282     return &*Node;
283   }
284 };
285 
286 
287 //===----------------------------------------------------------------------===//
288 //
289 /// iplist - The subset of list functionality that can safely be used on nodes
290 /// of polymorphic types, i.e. a heterogeneous list with a common base class that
291 /// holds the next/prev pointers.  The only state of the list itself is a single
292 /// pointer to the head of the list.
293 ///
294 /// This list can be in one of three interesting states:
295 /// 1. The list may be completely unconstructed.  In this case, the head
296 ///    pointer is null.  When in this form, any query for an iterator (e.g.
297 ///    begin() or end()) causes the list to transparently change to state #2.
298 /// 2. The list may be empty, but contain a sentinel for the end iterator. This
299 ///    sentinel is created by the Traits::createSentinel method and is a link
300 ///    in the list.  When the list is empty, the pointer in the iplist points
301 ///    to the sentinel.  Once the sentinel is constructed, it
302 ///    is not destroyed until the list is.
303 /// 3. The list may contain actual objects in it, which are stored as a doubly
304 ///    linked list of nodes.  One invariant of the list is that the predecessor
305 ///    of the first node in the list always points to the last node in the list,
306 ///    and the successor pointer for the sentinel (which always stays at the
307 ///    end of the list) is always null.
308 ///
309 template<typename NodeTy, typename Traits=ilist_traits<NodeTy> >
310 class iplist : public Traits {
311   mutable NodeTy *Head;
312 
313   // Use the prev node pointer of 'head' as the tail pointer.  This is really a
314   // circularly linked list where we snip the 'next' link from the sentinel node
315   // back to the first node in the list (to preserve assertions about going off
316   // the end of the list).
317   NodeTy *getTail() { return this->ensureHead(Head); }
318   const NodeTy *getTail() const { return this->ensureHead(Head); }
319   void setTail(NodeTy *N) const { this->noteHead(Head, N); }
320 
321   /// CreateLazySentinel - This method verifies whether the sentinel for the
322   /// list has been created and lazily makes it if not.
323   void CreateLazySentinel() const {
324     this->ensureHead(Head);
325   }
326 
327   static bool op_less(NodeTy &L, NodeTy &R) { return L < R; }
328   static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; }
329 
330   // No fundamental reason why iplist can't be copyable, but the default
331   // copy/copy-assign won't do.
332   iplist(const iplist &) = delete;
333   void operator=(const iplist &) = delete;
334 
335 public:
336   typedef NodeTy *pointer;
337   typedef const NodeTy *const_pointer;
338   typedef NodeTy &reference;
339   typedef const NodeTy &const_reference;
340   typedef NodeTy value_type;
341   typedef ilist_iterator<NodeTy> iterator;
342   typedef ilist_iterator<const NodeTy> const_iterator;
343   typedef size_t size_type;
344   typedef ptrdiff_t difference_type;
345   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
346   typedef std::reverse_iterator<iterator>  reverse_iterator;
347 
348   iplist() : Head(this->provideInitialHead()) {}
349   ~iplist() {
350     if (!Head) return;
351     clear();
352     Traits::destroySentinel(getTail());
353   }
354 
355   // Iterator creation methods.
356   iterator begin() {
357     CreateLazySentinel();
358     return iterator(Head);
359   }
360   const_iterator begin() const {
361     CreateLazySentinel();
362     return const_iterator(Head);
363   }
364   iterator end() {
365     CreateLazySentinel();
366     return iterator(getTail());
367   }
368   const_iterator end() const {
369     CreateLazySentinel();
370     return const_iterator(getTail());
371   }
372 
373   // reverse iterator creation methods.
374   reverse_iterator rbegin()            { return reverse_iterator(end()); }
375   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
376   reverse_iterator rend()              { return reverse_iterator(begin()); }
377   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
378 
379 
380   // Miscellaneous inspection routines.
381   size_type max_size() const { return size_type(-1); }
382   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
383     return !Head || Head == getTail();
384   }
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 iterator(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.reset(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, nullptr);
452     this->setPrev(Node, nullptr);
453     return Node;
454   }
455 
456   NodeTy *remove(const iterator &IT) {
457     iterator MutIt = IT;
458     return remove(MutIt);
459   }
460 
461   NodeTy *remove(NodeTy *IT) { return remove(iterator(IT)); }
462   NodeTy *remove(NodeTy &IT) { return remove(iterator(IT)); }
463 
464   // erase - remove a node from the controlled sequence... and delete it.
465   iterator erase(iterator where) {
466     this->deleteNode(remove(where));
467     return where;
468   }
469 
470   iterator erase(NodeTy *IT) { return erase(iterator(IT)); }
471   iterator erase(NodeTy &IT) { return erase(iterator(IT)); }
472 
473   /// Remove all nodes from the list like clear(), but do not call
474   /// removeNodeFromList() or deleteNode().
475   ///
476   /// This should only be used immediately before freeing nodes in bulk to
477   /// avoid traversing the list and bringing all the nodes into cache.
478   void clearAndLeakNodesUnsafely() {
479     if (Head) {
480       Head = getTail();
481       this->setPrev(Head, Head);
482     }
483   }
484 
485 private:
486   // transfer - The heart of the splice function.  Move linked list nodes from
487   // [first, last) into position.
488   //
489   void transfer(iterator position, iplist &L2, iterator first, iterator last) {
490     assert(first != last && "Should be checked by callers");
491     // Position cannot be contained in the range to be transferred.
492     // Check for the most common mistake.
493     assert(position != first &&
494            "Insertion point can't be one of the transferred nodes");
495 
496     if (position != last) {
497       // Note: we have to be careful about the case when we move the first node
498       // in the list.  This node is the list sentinel node and we can't move it.
499       NodeTy *ThisSentinel = getTail();
500       setTail(nullptr);
501       NodeTy *L2Sentinel = L2.getTail();
502       L2.setTail(nullptr);
503 
504       // Remove [first, last) from its old position.
505       NodeTy *First = &*first, *Prev = this->getPrev(First);
506       NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next);
507       if (Prev)
508         this->setNext(Prev, Next);
509       else
510         L2.Head = Next;
511       this->setPrev(Next, Prev);
512 
513       // Splice [first, last) into its new position.
514       NodeTy *PosNext = position.getNodePtrUnchecked();
515       NodeTy *PosPrev = this->getPrev(PosNext);
516 
517       // Fix head of list...
518       if (PosPrev)
519         this->setNext(PosPrev, First);
520       else
521         Head = First;
522       this->setPrev(First, PosPrev);
523 
524       // Fix end of list...
525       this->setNext(Last, PosNext);
526       this->setPrev(PosNext, Last);
527 
528       this->transferNodesFromList(L2, iterator(First), iterator(PosNext));
529 
530       // Now that everything is set, restore the pointers to the list sentinels.
531       L2.setTail(L2Sentinel);
532       setTail(ThisSentinel);
533     }
534   }
535 
536 public:
537 
538   //===----------------------------------------------------------------------===
539   // Functionality derived from other functions defined above...
540   //
541 
542   size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const {
543     if (!Head) return 0; // Don't require construction of sentinel if empty.
544     return std::distance(begin(), end());
545   }
546 
547   iterator erase(iterator first, iterator last) {
548     while (first != last)
549       first = erase(first);
550     return last;
551   }
552 
553   void clear() { if (Head) erase(begin(), end()); }
554 
555   // Front and back inserters...
556   void push_front(NodeTy *val) { insert(begin(), val); }
557   void push_back(NodeTy *val) { insert(end(), val); }
558   void pop_front() {
559     assert(!empty() && "pop_front() on empty list!");
560     erase(begin());
561   }
562   void pop_back() {
563     assert(!empty() && "pop_back() on empty list!");
564     iterator t = end(); erase(--t);
565   }
566 
567   // Special forms of insert...
568   template<class InIt> void insert(iterator where, InIt first, InIt last) {
569     for (; first != last; ++first) insert(where, *first);
570   }
571 
572   // Splice members - defined in terms of transfer...
573   void splice(iterator where, iplist &L2) {
574     if (!L2.empty())
575       transfer(where, L2, L2.begin(), L2.end());
576   }
577   void splice(iterator where, iplist &L2, iterator first) {
578     iterator last = first; ++last;
579     if (where == first || where == last) return; // No change
580     transfer(where, L2, first, last);
581   }
582   void splice(iterator where, iplist &L2, iterator first, iterator last) {
583     if (first != last) transfer(where, L2, first, last);
584   }
585   void splice(iterator where, iplist &L2, NodeTy &N) {
586     splice(where, L2, iterator(N));
587   }
588   void splice(iterator where, iplist &L2, NodeTy *N) {
589     splice(where, L2, iterator(N));
590   }
591 
592   template <class Compare>
593   void merge(iplist &Right, Compare comp) {
594     if (this == &Right)
595       return;
596     iterator First1 = begin(), Last1 = end();
597     iterator First2 = Right.begin(), Last2 = Right.end();
598     while (First1 != Last1 && First2 != Last2) {
599       if (comp(*First2, *First1)) {
600         iterator Next = First2;
601         transfer(First1, Right, First2, ++Next);
602         First2 = Next;
603       } else {
604         ++First1;
605       }
606     }
607     if (First2 != Last2)
608       transfer(Last1, Right, First2, Last2);
609   }
610   void merge(iplist &Right) { return merge(Right, op_less); }
611 
612   template <class Compare>
613   void sort(Compare comp) {
614     // The list is empty, vacuously sorted.
615     if (empty())
616       return;
617     // The list has a single element, vacuously sorted.
618     if (std::next(begin()) == end())
619       return;
620     // Find the split point for the list.
621     iterator Center = begin(), End = begin();
622     while (End != end() && std::next(End) != end()) {
623       Center = std::next(Center);
624       End = std::next(std::next(End));
625     }
626     // Split the list into two.
627     iplist RightHalf;
628     RightHalf.splice(RightHalf.begin(), *this, Center, end());
629 
630     // Sort the two sublists.
631     sort(comp);
632     RightHalf.sort(comp);
633 
634     // Merge the two sublists back together.
635     merge(RightHalf, comp);
636   }
637   void sort() { sort(op_less); }
638 
639   /// \brief Get the previous node, or \c nullptr for the list head.
640   NodeTy *getPrevNode(NodeTy &N) const {
641     auto I = N.getIterator();
642     if (I == begin())
643       return nullptr;
644     return &*std::prev(I);
645   }
646   /// \brief Get the previous node, or \c nullptr for the list head.
647   const NodeTy *getPrevNode(const NodeTy &N) const {
648     return getPrevNode(const_cast<NodeTy &>(N));
649   }
650 
651   /// \brief Get the next node, or \c nullptr for the list tail.
652   NodeTy *getNextNode(NodeTy &N) const {
653     auto Next = std::next(N.getIterator());
654     if (Next == end())
655       return nullptr;
656     return &*Next;
657   }
658   /// \brief Get the next node, or \c nullptr for the list tail.
659   const NodeTy *getNextNode(const NodeTy &N) const {
660     return getNextNode(const_cast<NodeTy &>(N));
661   }
662 };
663 
664 
665 template<typename NodeTy>
666 struct ilist : public iplist<NodeTy> {
667   typedef typename iplist<NodeTy>::size_type size_type;
668   typedef typename iplist<NodeTy>::iterator iterator;
669 
670   ilist() {}
671   ilist(const ilist &right) {
672     insert(this->begin(), right.begin(), right.end());
673   }
674   explicit ilist(size_type count) {
675     insert(this->begin(), count, NodeTy());
676   }
677   ilist(size_type count, const NodeTy &val) {
678     insert(this->begin(), count, val);
679   }
680   template<class InIt> ilist(InIt first, InIt last) {
681     insert(this->begin(), first, last);
682   }
683 
684   // bring hidden functions into scope
685   using iplist<NodeTy>::insert;
686   using iplist<NodeTy>::push_front;
687   using iplist<NodeTy>::push_back;
688 
689   // Main implementation here - Insert for a node passed by value...
690   iterator insert(iterator where, const NodeTy &val) {
691     return insert(where, this->createNode(val));
692   }
693 
694 
695   // Front and back inserters...
696   void push_front(const NodeTy &val) { insert(this->begin(), val); }
697   void push_back(const NodeTy &val) { insert(this->end(), val); }
698 
699   void insert(iterator where, size_type count, const NodeTy &val) {
700     for (; count != 0; --count) insert(where, val);
701   }
702 
703   // Assign special forms...
704   void assign(size_type count, const NodeTy &val) {
705     iterator I = this->begin();
706     for (; I != this->end() && count != 0; ++I, --count)
707       *I = val;
708     if (count != 0)
709       insert(this->end(), val, val);
710     else
711       erase(I, this->end());
712   }
713   template<class InIt> void assign(InIt first1, InIt last1) {
714     iterator first2 = this->begin(), last2 = this->end();
715     for ( ; first1 != last1 && first2 != last2; ++first1, ++first2)
716       *first1 = *first2;
717     if (first2 == last2)
718       erase(first1, last1);
719     else
720       insert(last1, first2, last2);
721   }
722 
723 
724   // Resize members...
725   void resize(size_type newsize, NodeTy val) {
726     iterator i = this->begin();
727     size_type len = 0;
728     for ( ; i != this->end() && len < newsize; ++i, ++len) /* empty*/ ;
729 
730     if (len == newsize)
731       erase(i, this->end());
732     else                                          // i == end()
733       insert(this->end(), newsize - len, val);
734   }
735   void resize(size_type newsize) { resize(newsize, NodeTy()); }
736 };
737 
738 } // End llvm namespace
739 
740 namespace std {
741   // Ensure that swap uses the fast list swap...
742   template<class Ty>
743   void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
744     Left.swap(Right);
745   }
746 }  // End 'std' extensions...
747 
748 #endif // LLVM_ADT_ILIST_H
749