1193323Sed//===-- llvm/ADT/GraphTraits.h - Graph traits template ----------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the little GraphTraits<X> template class that should be 11193323Sed// specialized by classes that want to be iteratable by generic graph iterators. 12193323Sed// 13193323Sed// This file also defines the marker class Inverse that is used to iterate over 14193323Sed// graphs in a graph defined, inverse ordering... 15193323Sed// 16193323Sed//===----------------------------------------------------------------------===// 17193323Sed 18193323Sed#ifndef LLVM_ADT_GRAPHTRAITS_H 19193323Sed#define LLVM_ADT_GRAPHTRAITS_H 20193323Sed 21193323Sednamespace llvm { 22193323Sed 23193323Sed// GraphTraits - This class should be specialized by different graph types... 24193323Sed// which is why the default version is empty. 25193323Sed// 26193323Sedtemplate<class GraphType> 27193323Sedstruct GraphTraits { 28193323Sed // Elements to provide: 29193323Sed 30193323Sed // typedef NodeType - Type of Node in the graph 31193323Sed // typedef ChildIteratorType - Type used to iterate over children in graph 32193323Sed 33199481Srdivacky // static NodeType *getEntryNode(const GraphType &) 34193323Sed // Return the entry node of the graph 35193323Sed 36193323Sed // static ChildIteratorType child_begin(NodeType *) 37193323Sed // static ChildIteratorType child_end (NodeType *) 38193323Sed // Return iterators that point to the beginning and ending of the child 39193323Sed // node list for the specified node. 40193323Sed // 41193323Sed 42193323Sed 43193323Sed // typedef ...iterator nodes_iterator; 44193323Sed // static nodes_iterator nodes_begin(GraphType *G) 45193323Sed // static nodes_iterator nodes_end (GraphType *G) 46193323Sed // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 47193323Sed 48234353Sdim // static unsigned size (GraphType *G) 49234353Sdim // Return total number of nodes in the graph 50234353Sdim // 51193323Sed 52234353Sdim 53193323Sed // If anyone tries to use this class without having an appropriate 54193323Sed // specialization, make an error. If you get this error, it's because you 55193323Sed // need to include the appropriate specialization of GraphTraits<> for your 56193323Sed // graph, or you need to define it for a new graph type. Either that or 57193323Sed // your argument to XXX_begin(...) is unknown or needs to have the proper .h 58193323Sed // file #include'd. 59193323Sed // 60193323Sed typedef typename GraphType::UnknownGraphTypeError NodeType; 61193323Sed}; 62193323Sed 63193323Sed 64193323Sed// Inverse - This class is used as a little marker class to tell the graph 65193323Sed// iterator to iterate over the graph in a graph defined "Inverse" ordering. 66193323Sed// Not all graphs define an inverse ordering, and if they do, it depends on 67193323Sed// the graph exactly what that is. Here's an example of usage with the 68193323Sed// df_iterator: 69193323Sed// 70193323Sed// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M); 71193323Sed// for (; I != E; ++I) { ... } 72193323Sed// 73193323Sed// Which is equivalent to: 74193323Sed// df_iterator<Inverse<Method*> > I = idf_begin(M), E = idf_end(M); 75193323Sed// for (; I != E; ++I) { ... } 76193323Sed// 77193323Sedtemplate <class GraphType> 78193323Sedstruct Inverse { 79193323Sed const GraphType &Graph; 80193323Sed 81193323Sed inline Inverse(const GraphType &G) : Graph(G) {} 82193323Sed}; 83193323Sed 84193323Sed// Provide a partial specialization of GraphTraits so that the inverse of an 85193323Sed// inverse falls back to the original graph. 86193323Sedtemplate<class T> 87193323Sedstruct GraphTraits<Inverse<Inverse<T> > > { 88193323Sed typedef typename GraphTraits<T>::NodeType NodeType; 89193323Sed typedef typename GraphTraits<T>::ChildIteratorType ChildIteratorType; 90193323Sed 91193323Sed static NodeType *getEntryNode(Inverse<Inverse<T> > *G) { 92193323Sed return GraphTraits<T>::getEntryNode(G->Graph.Graph); 93193323Sed } 94193323Sed 95193323Sed static ChildIteratorType child_begin(NodeType* N) { 96193323Sed return GraphTraits<T>::child_begin(N); 97193323Sed } 98193323Sed 99193323Sed static ChildIteratorType child_end(NodeType* N) { 100193323Sed return GraphTraits<T>::child_end(N); 101193323Sed } 102193323Sed}; 103193323Sed 104193323Sed} // End llvm namespace 105193323Sed 106193323Sed#endif 107