More switches to unordered_set and unordered_map
[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 #include <unordered_set>
44 #include <unordered_map>
45
46 #include "Annotatable.h"
47 #include "Node.h"
48
49 #if defined(_MSC_VER)
50 #pragma warning(disable:4251)
51 #endif
52
53 namespace Dyninst {
54 class Edge;
55 class Graph;
56 class Node;
57 class NodeIterator;
58 class EdgeIterator;
59     
60 class COMMON_EXPORT Graph : public AnnotatableSparse {
61     friend class Edge;
62     friend class Node;
63     friend class Creator;
64     friend class Iterator;
65     
66  protected:
67
68     typedef boost::shared_ptr<Node> NodePtr;
69     typedef boost::shared_ptr<Edge> EdgePtr;
70
71     typedef std::unordered_set<NodePtr, Node::NodePtrHasher> NodeSet;
72     typedef std::unordered_map<Address, NodeSet> NodeMap;
73
74  public:    
75     typedef boost::shared_ptr<Graph> Ptr;
76
77     // Interface class for predicate-based searches. Users
78     // can inherit this class to specify the functor to use
79     // as a predicate...
80     class NodePredicate {
81
82     public:
83         typedef boost::shared_ptr<NodePredicate> Ptr;
84         virtual ~NodePredicate() {};
85         virtual bool predicate(const NodePtr &node) = 0;
86         static Ptr getPtr(NodePredicate *p) { 
87             return Ptr(p);
88         }
89     };
90
91     typedef bool (*NodePredicateFunc)(const NodePtr &node, void *user_arg);
92     
93     // If you want to traverse the graph start here.
94     virtual void entryNodes(NodeIterator &begin, NodeIterator &end);
95
96     // If you want to traverse the graph backwards start here.
97     virtual void exitNodes(NodeIterator &begin, NodeIterator &end);
98     
99     // Get all nodes in the graph
100     virtual void allNodes(NodeIterator &begin, NodeIterator &end);
101
102     // Get all nodes with a provided address
103     virtual bool find(Address addr, NodeIterator &begin, NodeIterator &end);
104
105     // Get all nodes that satisfy the provided predicate
106     virtual bool find(NodePredicate::Ptr, NodeIterator &begin, NodeIterator &end);
107     virtual bool find(NodePredicateFunc, void *user_arg, NodeIterator &begin, NodeIterator &end);
108
109     bool printDOT(const std::string& fileName);
110
111     virtual ~Graph() {};
112     
113     // We create an empty graph and then add nodes and edges.
114     static Ptr createGraph();
115     
116     void insertPair(NodePtr source, NodePtr target, EdgePtr edge = EdgePtr());
117
118     virtual void insertEntryNode(NodePtr entry);
119     virtual void insertExitNode(NodePtr exit);
120
121     virtual void markAsEntryNode(NodePtr entry);
122     virtual void markAsExitNode(NodePtr exit);
123
124     void deleteNode(NodePtr node);
125
126     void addNode(NodePtr node);
127
128     virtual void removeAnnotation() {};
129
130     bool isEntryNode(NodePtr node);
131     bool isExitNode(NodePtr node);
132
133     void clearEntryNodes();
134     void clearExitNodes();
135
136     unsigned size() const;
137
138  protected:
139      
140     static const Address INITIAL_ADDR;
141     
142     // Create graph, add nodes.
143     Graph();
144     
145     // We also need to point to all Nodes to keep them alive; we can't 
146     // pervasively use shared_ptr within the graph because we're likely
147     // to have cycles.
148     NodeSet nodes_;
149     
150     NodeMap nodesByAddr_;
151
152     // May be overridden by children; don't assume it exists.
153     // Arguably should be removed entirely.
154     NodeSet entryNodes_;
155
156     // See the above ;)
157     NodeSet exitNodes_;
158 };
159
160 }
161 #endif
162