GraphTraits.h revision 551ccae044b0ff658fe629dd67edd5ffe75d10e8
1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===-- llvm/ADT/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 18551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_GRAPHTRAITS_H 19551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_GRAPHTRAITS_H 207461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 22d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 237461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// GraphTraits - This class should be specialized by different graph types... 247461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// which is why the default version is empty. 257461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 267461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate<class GraphType> 277461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerstruct GraphTraits { 287461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Elements to provide: 297461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 307461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // typedef NodeType - Type of Node in the graph 317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // typedef ChildIteratorType - Type used to iterate over children in graph 327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // static NodeType *getEntryNode(GraphType *) 347461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Return the entry node of the graph 357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 367461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // static ChildIteratorType child_begin(NodeType *) 377461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // static ChildIteratorType child_end (NodeType *) 387461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Return iterators that point to the beginning and ending of the child 397461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // node list for the specified node. 407461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 417461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 427461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 43b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // typedef ...iterator nodes_iterator; 44b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // static nodes_iterator nodes_begin(GraphType *G) 45b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // static nodes_iterator nodes_end (GraphType *G) 46b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // 47b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 48b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner 49b38e4fd8b0228feb1fb8376d2266b7f99a9b0913Chris Lattner 507461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // If anyone tries to use this class without having an appropriate 516bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // specialization, make an error. If you get this error, it's because you 527461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // need to include the appropriate specialization of GraphTraits<> for your 536bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // graph, or you need to define it for a new graph type. Either that or 546bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // your argument to XXX_begin(...) is unknown or needs to have the proper .h 556bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner // file #include'd. 567461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 577461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GraphType::UnknownGraphTypeError NodeType; 587461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 597461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 607461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 617461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Inverse - This class is used as a little marker class to tell the graph 627461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// iterator to iterate over the graph in a graph defined "Inverse" ordering. 637461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Not all graphs define an inverse ordering, and if they do, it depends on 647461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// the graph exactly what that is. Here's an example of usage with the 657461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// df_iterator: 667461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 676bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M); 686bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// for (; I != E; ++I) { ... } 696bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// 706bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// Which is equivalent to: 716bad546c2a4eac51eabc6ac398861dcf7d5f18bbChris Lattner// df_iterator<Inverse<Method*> > I = idf_begin(M), E = idf_end(M); 727461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// for (; I != E; ++I) { ... } 737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 747461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class GraphType> 757461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerstruct Inverse { 767461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner GraphType &Graph; 777461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 787461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline Inverse(GraphType &G) : Graph(G) {} 797461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 807461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 81d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 82d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 837461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#endif 84