Home | History | Annotate | Download | only in ADT
      1 //===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- 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 builds on the ADT/GraphTraits.h file to build generic depth
     11 // first graph iterator.  This file exposes the following functions/types:
     12 //
     13 // df_begin/df_end/df_iterator
     14 //   * Normal depth-first iteration - visit a node and then all of its children.
     15 //
     16 // idf_begin/idf_end/idf_iterator
     17 //   * Depth-first iteration on the 'inverse' graph.
     18 //
     19 // df_ext_begin/df_ext_end/df_ext_iterator
     20 //   * Normal depth-first iteration - visit a node and then all of its children.
     21 //     This iterator stores the 'visited' set in an external set, which allows
     22 //     it to be more efficient, and allows external clients to use the set for
     23 //     other purposes.
     24 //
     25 // idf_ext_begin/idf_ext_end/idf_ext_iterator
     26 //   * Depth-first iteration on the 'inverse' graph.
     27 //     This iterator stores the 'visited' set in an external set, which allows
     28 //     it to be more efficient, and allows external clients to use the set for
     29 //     other purposes.
     30 //
     31 //===----------------------------------------------------------------------===//
     32 
     33 #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H
     34 #define LLVM_ADT_DEPTHFIRSTITERATOR_H
     35 
     36 #include "llvm/ADT/GraphTraits.h"
     37 #include "llvm/ADT/PointerIntPair.h"
     38 #include "llvm/ADT/SmallPtrSet.h"
     39 #include <set>
     40 #include <vector>
     41 
     42 namespace llvm {
     43 
     44 // df_iterator_storage - A private class which is used to figure out where to
     45 // store the visited set.
     46 template<class SetType, bool External>   // Non-external set
     47 class df_iterator_storage {
     48 public:
     49   SetType Visited;
     50 };
     51 
     52 template<class SetType>
     53 class df_iterator_storage<SetType, true> {
     54 public:
     55   df_iterator_storage(SetType &VSet) : Visited(VSet) {}
     56   df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {}
     57   SetType &Visited;
     58 };
     59 
     60 
     61 // Generic Depth First Iterator
     62 template<class GraphT,
     63 class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
     64          bool ExtStorage = false, class GT = GraphTraits<GraphT> >
     65 class df_iterator : public std::iterator<std::forward_iterator_tag,
     66                                          typename GT::NodeType, ptrdiff_t>,
     67                     public df_iterator_storage<SetType, ExtStorage> {
     68   typedef std::iterator<std::forward_iterator_tag,
     69                         typename GT::NodeType, ptrdiff_t> super;
     70 
     71   typedef typename GT::NodeType          NodeType;
     72   typedef typename GT::ChildIteratorType ChildItTy;
     73   typedef PointerIntPair<NodeType*, 1>   PointerIntTy;
     74 
     75   // VisitStack - Used to maintain the ordering.  Top = current block
     76   // First element is node pointer, second is the 'next child' to visit
     77   // if the int in PointerIntTy is 0, the 'next child' to visit is invalid
     78   std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack;
     79 private:
     80   inline df_iterator(NodeType *Node) {
     81     this->Visited.insert(Node);
     82     VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0),
     83                                         GT::child_begin(Node)));
     84   }
     85   inline df_iterator() {
     86     // End is when stack is empty
     87   }
     88   inline df_iterator(NodeType *Node, SetType &S)
     89     : df_iterator_storage<SetType, ExtStorage>(S) {
     90     if (!S.count(Node)) {
     91       VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0),
     92                                           GT::child_begin(Node)));
     93       this->Visited.insert(Node);
     94     }
     95   }
     96   inline df_iterator(SetType &S)
     97     : df_iterator_storage<SetType, ExtStorage>(S) {
     98     // End is when stack is empty
     99   }
    100 
    101   inline void toNext() {
    102     do {
    103       std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back();
    104       NodeType *Node = Top.first.getPointer();
    105       ChildItTy &It  = Top.second;
    106       if (!Top.first.getInt()) {
    107         // now retrieve the real begin of the children before we dive in
    108         It = GT::child_begin(Node);
    109         Top.first.setInt(1);
    110       }
    111 
    112       while (It != GT::child_end(Node)) {
    113         NodeType *Next = *It++;
    114         // Has our next sibling been visited?
    115         if (Next && !this->Visited.count(Next)) {
    116           // No, do it now.
    117           this->Visited.insert(Next);
    118           VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0),
    119                                               GT::child_begin(Next)));
    120           return;
    121         }
    122       }
    123 
    124       // Oops, ran out of successors... go up a level on the stack.
    125       VisitStack.pop_back();
    126     } while (!VisitStack.empty());
    127   }
    128 
    129 public:
    130   typedef typename super::pointer pointer;
    131   typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self;
    132 
    133   // Provide static begin and end methods as our public "constructors"
    134   static inline _Self begin(const GraphT& G) {
    135     return _Self(GT::getEntryNode(G));
    136   }
    137   static inline _Self end(const GraphT& G) { return _Self(); }
    138 
    139   // Static begin and end methods as our public ctors for external iterators
    140   static inline _Self begin(const GraphT& G, SetType &S) {
    141     return _Self(GT::getEntryNode(G), S);
    142   }
    143   static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); }
    144 
    145   inline bool operator==(const _Self& x) const {
    146     return VisitStack == x.VisitStack;
    147   }
    148   inline bool operator!=(const _Self& x) const { return !operator==(x); }
    149 
    150   inline pointer operator*() const {
    151     return VisitStack.back().first.getPointer();
    152   }
    153 
    154   // This is a nonstandard operator-> that dereferences the pointer an extra
    155   // time... so that you can actually call methods ON the Node, because
    156   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
    157   //
    158   inline NodeType *operator->() const { return operator*(); }
    159 
    160   inline _Self& operator++() {   // Preincrement
    161     toNext();
    162     return *this;
    163   }
    164 
    165   // skips all children of the current node and traverses to next node
    166   //
    167   inline _Self& skipChildren() {
    168     VisitStack.pop_back();
    169     if (!VisitStack.empty())
    170       toNext();
    171     return *this;
    172   }
    173 
    174   inline _Self operator++(int) { // Postincrement
    175     _Self tmp = *this; ++*this; return tmp;
    176   }
    177 
    178   // nodeVisited - return true if this iterator has already visited the
    179   // specified node.  This is public, and will probably be used to iterate over
    180   // nodes that a depth first iteration did not find: ie unreachable nodes.
    181   //
    182   inline bool nodeVisited(NodeType *Node) const {
    183     return this->Visited.count(Node) != 0;
    184   }
    185 
    186   /// getPathLength - Return the length of the path from the entry node to the
    187   /// current node, counting both nodes.
    188   unsigned getPathLength() const { return VisitStack.size(); }
    189 
    190   /// getPath - Return the n'th node in the path from the entry node to the
    191   /// current node.
    192   NodeType *getPath(unsigned n) const {
    193     return VisitStack[n].first.getPointer();
    194   }
    195 };
    196 
    197 
    198 // Provide global constructors that automatically figure out correct types...
    199 //
    200 template <class T>
    201 df_iterator<T> df_begin(const T& G) {
    202   return df_iterator<T>::begin(G);
    203 }
    204 
    205 template <class T>
    206 df_iterator<T> df_end(const T& G) {
    207   return df_iterator<T>::end(G);
    208 }
    209 
    210 // Provide global definitions of external depth first iterators...
    211 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
    212 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
    213   df_ext_iterator(const df_iterator<T, SetTy, true> &V)
    214     : df_iterator<T, SetTy, true>(V) {}
    215 };
    216 
    217 template <class T, class SetTy>
    218 df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
    219   return df_ext_iterator<T, SetTy>::begin(G, S);
    220 }
    221 
    222 template <class T, class SetTy>
    223 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
    224   return df_ext_iterator<T, SetTy>::end(G, S);
    225 }
    226 
    227 
    228 // Provide global definitions of inverse depth first iterators...
    229 template <class T,
    230   class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>,
    231           bool External = false>
    232 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
    233   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
    234     : df_iterator<Inverse<T>, SetTy, External>(V) {}
    235 };
    236 
    237 template <class T>
    238 idf_iterator<T> idf_begin(const T& G) {
    239   return idf_iterator<T>::begin(Inverse<T>(G));
    240 }
    241 
    242 template <class T>
    243 idf_iterator<T> idf_end(const T& G){
    244   return idf_iterator<T>::end(Inverse<T>(G));
    245 }
    246 
    247 // Provide global definitions of external inverse depth first iterators...
    248 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
    249 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
    250   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
    251     : idf_iterator<T, SetTy, true>(V) {}
    252   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
    253     : idf_iterator<T, SetTy, true>(V) {}
    254 };
    255 
    256 template <class T, class SetTy>
    257 idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) {
    258   return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S);
    259 }
    260 
    261 template <class T, class SetTy>
    262 idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
    263   return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
    264 }
    265 
    266 } // End llvm namespace
    267 
    268 #endif
    269