include/llvm/ADT/DepthFirstIterator.h

   1 //===- Support/DepthFirstIterator.h - Depth First iterator ------*- C++ -*-===//
   2 //
   3 // This file builds on the Support/GraphTraits.h file to build generic depth
   4 // first graph iterator.  This file exposes the following functions/types:
   5 //
   6 // df_begin/df_end/df_iterator
   7 //   * Normal depth-first iteration - visit a node and then all of its children.
   8 //
   9 // idf_begin/idf_end/idf_iterator
  10 //   * Depth-first iteration on the 'inverse' graph.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef SUPPORT_DEPTHFIRSTITERATOR_H
  15 #define SUPPORT_DEPTHFIRSTITERATOR_H
  16
  17 #include "Support/GraphTraits.h"
  18 #include "Support/iterator"
  19 #include <vector>
  20 #include <set>
  21
  22 // Generic Depth First Iterator
  23 template<class GraphT, class GT = GraphTraits<GraphT> >
  24 class df_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t> {
  25   typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
  26
  27   typedef typename GT::NodeType          NodeType;
  28   typedef typename GT::ChildIteratorType ChildItTy;
  29
  30   std::set<NodeType *> Visited;    // All of the blocks visited so far...
  31   // VisitStack - Used to maintain the ordering.  Top = current block
  32   // First element is node pointer, second is the 'next child' to visit
  33   std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
  34 private:
  35   inline df_iterator(NodeType *Node) {
  36     Visited.insert(Node);
  37     VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
  38   }
  39   inline df_iterator() { /* End is when stack is empty */ }
  40
  41 public:
  42   typedef typename super::pointer pointer;
  43   typedef df_iterator<GraphT, GT> _Self;
  44
  45   // Provide static begin and end methods as our public "constructors"
  46   static inline _Self begin(GraphT G) {
  47     return _Self(GT::getEntryNode(G));
  48   }
  49   static inline _Self end(GraphT G) { return _Self(); }
  50
  51
  52   inline bool operator==(const _Self& x) const {
  53     return VisitStack.size() == x.VisitStack.size() &&
  54            VisitStack == x.VisitStack;
  55   }
  56   inline bool operator!=(const _Self& x) const { return !operator==(x); }
  57
  58   inline pointer operator*() const {
  59     return VisitStack.back().first;
  60   }
  61
  62   // This is a nonstandard operator-> that dereferences the pointer an extra
  63   // time... so that you can actually call methods ON the Node, because
  64   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
  65   //
  66   inline NodeType *operator->() const { return operator*(); }
  67
  68   inline _Self& operator++() {   // Preincrement
  69     do {
  70       std::pair<NodeType *, ChildItTy> &Top = VisitStack.back();
  71       NodeType *Node = Top.first;
  72       ChildItTy &It  = Top.second;
  73
  74       while (It != GT::child_end(Node)) {
  75         NodeType *Next = *It++;
  76         if (!Visited.count(Next)) {  // Has our next sibling been visited?
  77           // No, do it now.
  78           Visited.insert(Next);
  79           VisitStack.push_back(std::make_pair(Next, GT::child_begin(Next)));
  80           return *this;
  81         }
  82       }
  83
  84       // Oops, ran out of successors... go up a level on the stack.
  85       VisitStack.pop_back();
  86     } while (!VisitStack.empty());
  87     return *this;
  88   }
  89
  90   inline _Self operator++(int) { // Postincrement
  91     _Self tmp = *this; ++*this; return tmp;
  92   }
  93
  94   // nodeVisited - return true if this iterator has already visited the
  95   // specified node.  This is public, and will probably be used to iterate over
  96   // nodes that a depth first iteration did not find: ie unreachable nodes.
  97   //
  98   inline bool nodeVisited(NodeType *Node) const {
  99     return Visited.count(Node) != 0;
 100   }
 101 };
 102
 103
 104 // Provide global constructors that automatically figure out correct types...
 105 //
 106 template <class T>
 107 df_iterator<T> df_begin(T G) {
 108   return df_iterator<T>::begin(G);
 109 }
 110
 111 template <class T>
 112 df_iterator<T> df_end(T G) {
 113   return df_iterator<T>::end(G);
 114 }
 115
 116 // Provide global definitions of inverse depth first iterators...
 117 template <class T>
 118 struct idf_iterator : public df_iterator<Inverse<T> > {
 119   idf_iterator(const df_iterator<Inverse<T> > &V) :df_iterator<Inverse<T> >(V){}
 120 };
 121
 122 template <class T>
 123 idf_iterator<T> idf_begin(T G) {
 124   return idf_iterator<T>::begin(G);
 125 }
 126
 127 template <class T>
 128 idf_iterator<T> idf_end(T G){
 129   return idf_iterator<T>::end(G);
 130 }
 131
 132 #endif