1
//===-- llvm/ADT/GraphTraits.h - Graph traits template ----------*- C++ -*-===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file defines the little GraphTraits<X> template class that should be
11
// specialized by classes that want to be iteratable by generic graph iterators.
13
// This file also defines the marker class Inverse that is used to iterate over
14
// graphs in a graph defined, inverse ordering...
16
//===----------------------------------------------------------------------===//
18
#ifndef LLVM_ADT_GRAPHTRAITS_H
19
#define LLVM_ADT_GRAPHTRAITS_H
23
// GraphTraits - This class should be specialized by different graph types...
24
// which is why the default version is empty.
26
template<class GraphType>
28
// Elements to provide:
30
// typedef NodeType - Type of Node in the graph
31
// typedef ChildIteratorType - Type used to iterate over children in graph
33
// static NodeType *getEntryNode(const GraphType &)
34
// Return the entry node of the graph
36
// static ChildIteratorType child_begin(NodeType *)
37
// static ChildIteratorType child_end (NodeType *)
38
// Return iterators that point to the beginning and ending of the child
39
// node list for the specified node.
43
// typedef ...iterator nodes_iterator;
44
// static nodes_iterator nodes_begin(GraphType *G)
45
// static nodes_iterator nodes_end (GraphType *G)
47
// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
50
// If anyone tries to use this class without having an appropriate
51
// specialization, make an error. If you get this error, it's because you
52
// need to include the appropriate specialization of GraphTraits<> for your
53
// graph, or you need to define it for a new graph type. Either that or
54
// your argument to XXX_begin(...) is unknown or needs to have the proper .h
57
typedef typename GraphType::UnknownGraphTypeError NodeType;
61
// Inverse - This class is used as a little marker class to tell the graph
62
// iterator to iterate over the graph in a graph defined "Inverse" ordering.
63
// Not all graphs define an inverse ordering, and if they do, it depends on
64
// the graph exactly what that is. Here's an example of usage with the
67
// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
68
// for (; I != E; ++I) { ... }
70
// Which is equivalent to:
71
// df_iterator<Inverse<Method*> > I = idf_begin(M), E = idf_end(M);
72
// for (; I != E; ++I) { ... }
74
template <class GraphType>
76
const GraphType &Graph;
78
inline Inverse(const GraphType &G) : Graph(G) {}
81
// Provide a partial specialization of GraphTraits so that the inverse of an
82
// inverse falls back to the original graph.
84
struct GraphTraits<Inverse<Inverse<T> > > {
85
typedef typename GraphTraits<T>::NodeType NodeType;
86
typedef typename GraphTraits<T>::ChildIteratorType ChildIteratorType;
88
static NodeType *getEntryNode(Inverse<Inverse<T> > *G) {
89
return GraphTraits<T>::getEntryNode(G->Graph.Graph);
92
static ChildIteratorType child_begin(NodeType* N) {
93
return GraphTraits<T>::child_begin(N);
96
static ChildIteratorType child_end(NodeType* N) {
97
return GraphTraits<T>::child_end(N);
101
} // End llvm namespace