LLVM API Documentation
00001 //===-- llvm/ADT/GraphTraits.h - Graph traits template ----------*- 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 defines the little GraphTraits<X> template class that should be 00011 // specialized by classes that want to be iteratable by generic graph iterators. 00012 // 00013 // This file also defines the marker class Inverse that is used to iterate over 00014 // graphs in a graph defined, inverse ordering... 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #ifndef LLVM_ADT_GRAPHTRAITS_H 00019 #define LLVM_ADT_GRAPHTRAITS_H 00020 00021 namespace llvm { 00022 00023 // GraphTraits - This class should be specialized by different graph types... 00024 // which is why the default version is empty. 00025 // 00026 template<class GraphType> 00027 struct GraphTraits { 00028 // Elements to provide: 00029 00030 // typedef NodeType - Type of Node in the graph 00031 // typedef ChildIteratorType - Type used to iterate over children in graph 00032 00033 // static NodeType *getEntryNode(GraphType *) 00034 // Return the entry node of the graph 00035 00036 // static ChildIteratorType child_begin(NodeType *) 00037 // static ChildIteratorType child_end (NodeType *) 00038 // Return iterators that point to the beginning and ending of the child 00039 // node list for the specified node. 00040 // 00041 00042 00043 // typedef ...iterator nodes_iterator; 00044 // static nodes_iterator nodes_begin(GraphType *G) 00045 // static nodes_iterator nodes_end (GraphType *G) 00046 // 00047 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00048 00049 00050 // If anyone tries to use this class without having an appropriate 00051 // specialization, make an error. If you get this error, it's because you 00052 // need to include the appropriate specialization of GraphTraits<> for your 00053 // graph, or you need to define it for a new graph type. Either that or 00054 // your argument to XXX_begin(...) is unknown or needs to have the proper .h 00055 // file #include'd. 00056 // 00057 typedef typename GraphType::UnknownGraphTypeError NodeType; 00058 }; 00059 00060 00061 // Inverse - This class is used as a little marker class to tell the graph 00062 // iterator to iterate over the graph in a graph defined "Inverse" ordering. 00063 // Not all graphs define an inverse ordering, and if they do, it depends on 00064 // the graph exactly what that is. Here's an example of usage with the 00065 // df_iterator: 00066 // 00067 // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M); 00068 // for (; I != E; ++I) { ... } 00069 // 00070 // Which is equivalent to: 00071 // df_iterator<Inverse<Method*> > I = idf_begin(M), E = idf_end(M); 00072 // for (; I != E; ++I) { ... } 00073 // 00074 template <class GraphType> 00075 struct Inverse { 00076 GraphType &Graph; 00077 00078 inline Inverse(GraphType &G) : Graph(G) {} 00079 }; 00080 00081 } // End llvm namespace 00082 00083 #endif