LLVM API Documentation

DepthFirstIterator.h

Go to the documentation of this file.
00001 //===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file builds on the ADT/GraphTraits.h file to build generic depth
00011 // first graph iterator.  This file exposes the following functions/types:
00012 //
00013 // df_begin/df_end/df_iterator
00014 //   * Normal depth-first iteration - visit a node and then all of its children.
00015 //
00016 // idf_begin/idf_end/idf_iterator
00017 //   * Depth-first iteration on the 'inverse' graph.
00018 //
00019 // df_ext_begin/df_ext_end/df_ext_iterator
00020 //   * Normal depth-first iteration - visit a node and then all of its children.
00021 //     This iterator stores the 'visited' set in an external set, which allows
00022 //     it to be more efficient, and allows external clients to use the set for
00023 //     other purposes.
00024 //
00025 // idf_ext_begin/idf_ext_end/idf_ext_iterator
00026 //   * Depth-first iteration on the 'inverse' graph.
00027 //     This iterator stores the 'visited' set in an external set, which allows
00028 //     it to be more efficient, and allows external clients to use the set for
00029 //     other purposes.
00030 //
00031 //===----------------------------------------------------------------------===//
00032 
00033 #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H
00034 #define LLVM_ADT_DEPTHFIRSTITERATOR_H
00035 
00036 #include "llvm/ADT/GraphTraits.h"
00037 #include "llvm/ADT/iterator"
00038 #include <vector>
00039 #include <set>
00040 
00041 namespace llvm {
00042 
00043 // df_iterator_storage - A private class which is used to figure out where to
00044 // store the visited set.
00045 template<class SetType, bool External>   // Non-external set
00046 class df_iterator_storage {
00047 public:
00048   SetType Visited;
00049 };
00050 
00051 template<class SetType>
00052 class df_iterator_storage<SetType, true> {
00053 public:
00054   df_iterator_storage(SetType &VSet) : Visited(VSet) {}
00055   df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {}
00056   SetType &Visited;
00057 };
00058 
00059 
00060 // Generic Depth First Iterator
00061 template<class GraphT, class SetType =
00062                             std::set<typename GraphTraits<GraphT>::NodeType*>,
00063          bool ExtStorage = false, class GT = GraphTraits<GraphT> >
00064 class df_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>,
00065                     public df_iterator_storage<SetType, ExtStorage> {
00066   typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
00067 
00068   typedef typename GT::NodeType          NodeType;
00069   typedef typename GT::ChildIteratorType ChildItTy;
00070 
00071   // VisitStack - Used to maintain the ordering.  Top = current block
00072   // First element is node pointer, second is the 'next child' to visit
00073   std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
00074 private:
00075   inline df_iterator(NodeType *Node) {
00076     this->Visited.insert(Node);
00077     VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
00078   }
00079   inline df_iterator() { /* End is when stack is empty */ }
00080 
00081   inline df_iterator(NodeType *Node, SetType &S)
00082     : df_iterator_storage<SetType, ExtStorage>(S) {
00083     if (!S.count(Node)) {
00084       this->Visited.insert(Node);
00085       VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node)));
00086     }
00087   }
00088   inline df_iterator(SetType &S)
00089     : df_iterator_storage<SetType, ExtStorage>(S) {
00090     // End is when stack is empty
00091   }
00092 
00093 public:
00094   typedef typename super::pointer pointer;
00095   typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self;
00096 
00097   // Provide static begin and end methods as our public "constructors"
00098   static inline _Self begin(GraphT G) {
00099     return _Self(GT::getEntryNode(G));
00100   }
00101   static inline _Self end(GraphT G) { return _Self(); }
00102 
00103   // Static begin and end methods as our public ctors for external iterators
00104   static inline _Self begin(GraphT G, SetType &S) {
00105     return _Self(GT::getEntryNode(G), S);
00106   }
00107   static inline _Self end(GraphT G, SetType &S) { return _Self(S); }
00108 
00109   inline bool operator==(const _Self& x) const {
00110     return VisitStack.size() == x.VisitStack.size() &&
00111            VisitStack == x.VisitStack;
00112   }
00113   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00114 
00115   inline pointer operator*() const {
00116     return VisitStack.back().first;
00117   }
00118 
00119   // This is a nonstandard operator-> that dereferences the pointer an extra
00120   // time... so that you can actually call methods ON the Node, because
00121   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
00122   //
00123   inline NodeType *operator->() const { return operator*(); }
00124 
00125   inline _Self& operator++() {   // Preincrement
00126     do {
00127       std::pair<NodeType *, ChildItTy> &Top = VisitStack.back();
00128       NodeType *Node = Top.first;
00129       ChildItTy &It  = Top.second;
00130 
00131       while (It != GT::child_end(Node)) {
00132         NodeType *Next = *It++;
00133         if (!this->Visited.count(Next)) {  // Has our next sibling been visited?
00134           // No, do it now.
00135           this->Visited.insert(Next);
00136           VisitStack.push_back(std::make_pair(Next, GT::child_begin(Next)));
00137           return *this;
00138         }
00139       }
00140 
00141       // Oops, ran out of successors... go up a level on the stack.
00142       VisitStack.pop_back();
00143     } while (!VisitStack.empty());
00144     return *this;
00145   }
00146 
00147   inline _Self operator++(int) { // Postincrement
00148     _Self tmp = *this; ++*this; return tmp;
00149   }
00150 
00151   // nodeVisited - return true if this iterator has already visited the
00152   // specified node.  This is public, and will probably be used to iterate over
00153   // nodes that a depth first iteration did not find: ie unreachable nodes.
00154   //
00155   inline bool nodeVisited(NodeType *Node) const {
00156     return this->Visited.count(Node) != 0;
00157   }
00158 };
00159 
00160 
00161 // Provide global constructors that automatically figure out correct types...
00162 //
00163 template <class T>
00164 df_iterator<T> df_begin(T G) {
00165   return df_iterator<T>::begin(G);
00166 }
00167 
00168 template <class T>
00169 df_iterator<T> df_end(T G) {
00170   return df_iterator<T>::end(G);
00171 }
00172 
00173 // Provide global definitions of external depth first iterators...
00174 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
00175 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
00176   df_ext_iterator(const df_iterator<T, SetTy, true> &V)
00177     : df_iterator<T, SetTy, true>(V) {}
00178 };
00179 
00180 template <class T, class SetTy>
00181 df_ext_iterator<T, SetTy> df_ext_begin(T G, SetTy &S) {
00182   return df_ext_iterator<T, SetTy>::begin(G, S);
00183 }
00184 
00185 template <class T, class SetTy>
00186 df_ext_iterator<T, SetTy> df_ext_end(T G, SetTy &S) {
00187   return df_ext_iterator<T, SetTy>::end(G, S);
00188 }
00189 
00190 
00191 // Provide global definitions of inverse depth first iterators...
00192 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*>,
00193           bool External = false>
00194 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
00195   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
00196     : df_iterator<Inverse<T>, SetTy, External>(V) {}
00197 };
00198 
00199 template <class T>
00200 idf_iterator<T> idf_begin(T G) {
00201   return idf_iterator<T>::begin(G);
00202 }
00203 
00204 template <class T>
00205 idf_iterator<T> idf_end(T G){
00206   return idf_iterator<T>::end(G);
00207 }
00208 
00209 // Provide global definitions of external inverse depth first iterators...
00210 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
00211 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
00212   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
00213     : idf_iterator<T, SetTy, true>(V) {}
00214   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
00215     : idf_iterator<T, SetTy, true>(V) {}
00216 };
00217 
00218 template <class T, class SetTy>
00219 idf_ext_iterator<T, SetTy> idf_ext_begin(T G, SetTy &S) {
00220   return idf_ext_iterator<T, SetTy>::begin(G, S);
00221 }
00222 
00223 template <class T, class SetTy>
00224 idf_ext_iterator<T, SetTy> idf_ext_end(T G, SetTy &S) {
00225   return idf_ext_iterator<T, SetTy>::end(G, S);
00226 }
00227 
00228 } // End llvm namespace
00229 
00230 #endif