LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

GraphTraits.h

Go to the documentation of this file.
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