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