GraphTraits.h revision b2109ce97881269a610fa4afbcbca350e975174d
148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===-- Support/GraphTraits.h - Graph traits template -----------*- C++ -*-===// 2b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 3b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// The LLVM Compiler Infrastructure 4b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 5b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 8b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell//===----------------------------------------------------------------------===// 97461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 107461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This file defines the little GraphTraits<X> template class that should be 117461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// specialized by classes that want to be iteratable by generic graph iterators. 127461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 137461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This file also defines the marker class Inverse that is used to iterate over 147461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// graphs in a graph defined, inverse ordering... 157461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 167461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===----------------------------------------------------------------------===// 177461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 18a9f6e4ae0eaea69949755807b7207177f256eaceBrian Gaeke#ifndef SUPPORT_GRAPHTRAITS_H 19a9f6e4ae0eaea69949755807b7207177f256eaceBrian Gaeke#define SUPPORT_GRAPHTRAITS_H 207461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 217461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// GraphTraits - This class should be specialized by different graph types... 227461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// which is why the default version is empty. 237461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 247461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate<class GraphType> 257461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerstruct GraphTraits { 267461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Elements to provide: 277461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 287461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // typedef NodeType - Type of Node in the graph 297461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // typedef ChildIteratorType - Type used to iterate over children in graph 307461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // static NodeType *getEntryNode(GraphType *) 327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Return the entry node of the graph 337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 347461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // static ChildIteratorType child_begin(NodeType *) 357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // static ChildIteratorType child_end (NodeType *) 367461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Return iterators that point to the beginning and ending of the child 377461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // node list for the specified node. 387461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 397461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 407461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 41b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // typedef ...iterator nodes_iterator; 42b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // static nodes_iterator nodes_begin(GraphType *G) 43b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // static nodes_iterator nodes_end (GraphType *G) 44b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // 45b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 46b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner 47b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner 487461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // If anyone tries to use this class without having an appropriate 496bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // specialization, make an error. If you get this error, it's because you 507461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // need to include the appropriate specialization of GraphTraits<> for your 516bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // graph, or you need to define it for a new graph type. Either that or 526bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // your argument to XXX_begin(...) is unknown or needs to have the proper .h 536bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // file #include'd. 547461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 557461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GraphType::UnknownGraphTypeError NodeType; 567461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 577461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 587461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 597461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Inverse - This class is used as a little marker class to tell the graph 607461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// iterator to iterate over the graph in a graph defined "Inverse" ordering. 617461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Not all graphs define an inverse ordering, and if they do, it depends on 627461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// the graph exactly what that is. Here's an example of usage with the 637461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// df_iterator: 647461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 656bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M); 666bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// for (; I != E; ++I) { ... } 676bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// 686bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// Which is equivalent to: 696bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// df_iterator<Inverse<Method*> > I = idf_begin(M), E = idf_end(M); 707461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// for (; I != E; ++I) { ... } 717461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 727461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class GraphType> 737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerstruct Inverse { 747461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner GraphType &Graph; 757461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 767461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline Inverse(GraphType &G) : Graph(G) {} 777461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 787461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 797461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#endif 80