Update copyright to LGPL on all files
[dyninst.git] / dynutil / h / Graph.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // Graph class
33
34
35 #if !defined(GRAPH_H)
36 #define GRAPH_H
37
38 #include "dyn_detail/boost/shared_ptr.hpp"
39 #include <set>
40 #include <list>
41 #include <queue>
42
43 #include "Annotatable.h"
44 #include "Node.h"
45
46 namespace Dyninst {
47 class Edge;
48 class Graph;
49 class Node;
50 class NodeIterator;
51 class EdgeIterator;
52     
53 class Graph : public AnnotatableSparse {
54     friend class Edge;
55     friend class Node;
56     friend class Creator;
57     friend class Iterator;
58     
59  protected:
60
61     typedef dyn_detail::boost::shared_ptr<Node> NodePtr;
62     typedef dyn_detail::boost::shared_ptr<Edge> EdgePtr;
63
64     typedef std::set<NodePtr> NodeSet;
65     typedef std::map<Address, NodeSet> NodeMap;
66
67  public:    
68     typedef dyn_detail::boost::shared_ptr<Graph> Ptr;
69
70     // Interface class for predicate-based searches. Users
71     // can inherit this class to specify the functor to use
72     // as a predicate...
73     class NodePredicate {
74
75     public:
76         typedef dyn_detail::boost::shared_ptr<NodePredicate> Ptr;
77         virtual ~NodePredicate() {};
78         virtual bool predicate(const NodePtr &node) = 0;
79         static Ptr getPtr(NodePredicate *p) { 
80             return Ptr(p);
81         }
82     };
83
84     typedef bool (*NodePredicateFunc)(const NodePtr &node, void *user_arg);
85     
86     // If you want to traverse the graph start here.
87     virtual void entryNodes(NodeIterator &begin, NodeIterator &end);
88
89     // If you want to traverse the graph backwards start here.
90     virtual void exitNodes(NodeIterator &begin, NodeIterator &end);
91     
92     // Get all nodes in the graph
93     virtual void allNodes(NodeIterator &begin, NodeIterator &end);
94
95     // Get all nodes with a provided address
96     virtual bool find(Address addr, NodeIterator &begin, NodeIterator &end);
97
98     // Get all nodes that satisfy the provided predicate
99     virtual bool find(NodePredicate::Ptr, NodeIterator &begin, NodeIterator &end);
100     virtual bool find(NodePredicateFunc, void *user_arg, NodeIterator &begin, NodeIterator &end);
101
102     bool printDOT(const std::string fileName);
103
104     virtual ~Graph() {};
105     
106     // We create an empty graph and then add nodes and edges.
107     static Ptr createGraph();
108     
109     // We effectively build the graph by specifying all edges,
110     // since it is meaningless to have a disconnected node. 
111     void insertPair(NodePtr source, NodePtr target);
112     
113     virtual void insertEntryNode(NodePtr entry);
114     virtual void insertExitNode(NodePtr exit);
115     
116
117     void addNode(NodePtr node);
118
119     virtual void removeAnnotation() {};
120
121  protected:
122      
123     static const Address INITIAL_ADDR;
124     
125     // Create graph, add nodes.
126     Graph();
127     
128     // We also need to point to all Nodes to keep them alive; we can't 
129     // pervasively use shared_ptr within the graph because we're likely
130     // to have cycles.
131     NodeSet nodes_;
132     
133     NodeMap nodesByAddr_;
134
135     // May be overridden by children; don't assume it exists.
136     // Arguably should be removed entirely.
137     NodeSet entryNodes_;
138
139     // See the above ;)
140     NodeSet exitNodes_;
141 };
142
143 }
144 #endif
145