Potential fixes needed for relocating libraries (#754)
[dyninst.git] / common / src / Graph.C
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 implementation
32
33 #include "Graph.h"
34 #include "Edge.h"
35 #include "Node.h"
36 #include <assert.h>
37
38 #include "NodeIterator.h"
39 #include <iostream>
40
41 using namespace Dyninst;
42
43 const Dyninst::Address Graph::INITIAL_ADDR = (Address) -1;
44
45
46
47 void Graph::entryNodes(NodeIterator &begin, NodeIterator &end) {
48     begin = NodeIterator(new NodeIteratorSet(entryNodes_.begin()));
49     end = NodeIterator(new NodeIteratorSet(entryNodes_.end()));
50     return;
51 }
52
53 void Graph::exitNodes(NodeIterator &begin, NodeIterator &end) {
54         // std::cerr << "exitNodes called: " << exitNodes_.size() << " nodes" << std::endl;
55     begin = NodeIterator(new NodeIteratorSet(exitNodes_.begin()));
56     end = NodeIterator(new NodeIteratorSet(exitNodes_.end()));
57     return;
58 }
59
60 void Graph::allNodes(NodeIterator &begin, NodeIterator &end) {
61     // std::cerr << "AllNodes called: " << nodes_.size() << " nodes" << std::endl;
62     begin = NodeIterator(new NodeIteratorSet(nodes_.begin()));
63         end = NodeIterator(new NodeIteratorSet(nodes_.end()));
64         return;
65 }
66
67 bool Graph::find(Address addr, NodeIterator &begin, NodeIterator &end) {
68     NodeMap::iterator iter = nodesByAddr_.find(addr);
69     if (iter == nodesByAddr_.end()) return false;
70
71     begin = NodeIterator(new NodeIteratorSet(iter->second.begin()));
72     end = NodeIterator(new NodeIteratorSet(iter->second.end()));
73     return true;
74 }
75
76 Graph::Graph() {};
77
78 Graph::Ptr Graph::createGraph() {
79     return Graph::Ptr(new Graph());
80 }
81
82 void Graph::insertPair(NodePtr source, NodePtr target, EdgePtr e) {
83     // TODO handle parameter edge types.
84    if (!e) {
85       e = Edge::createEdge(source, target);
86    }
87    else {
88       e->setSource(source);
89       e->setTarget(target);
90    }
91    
92    source->addOutEdge(e);
93    target->addInEdge(e);
94    
95    addNode(source);
96    addNode(target);
97 }
98
99 void Graph::insertEntryNode(NodePtr entry) {
100     addNode(entry);
101     entryNodes_.insert(entry);
102 }
103
104 void Graph::insertExitNode(NodePtr exit) {
105     addNode(exit);
106     exitNodes_.insert(exit);
107 }
108
109 void Graph::markAsEntryNode(NodePtr entry) {
110     entryNodes_.insert(entry);
111 }
112
113 void Graph::markAsExitNode(NodePtr exit) {
114     exitNodes_.insert(exit);
115 }
116
117 void Graph::addNode(Node::Ptr node) {
118   //if (node->hasInEdges() || node->hasOutEdges()) return;
119     nodes_.insert(node);
120     if (!node->isVirtual()) {
121         nodesByAddr_[node->addr()].insert(node);
122     }        
123     // std::cerr << "\t\t After addNode: " << nodes_.size() << " nodes" << std::endl;
124     // std::cerr << "\t\t\t adding " << node << std::endl;
125 }
126
127 void Graph::clearEntryNodes() {
128     entryNodes_.clear();
129 }
130
131 void Graph::clearExitNodes() {
132     exitNodes_.clear();
133 }
134 // Fancy-shmancy predicate based search methods...
135
136 bool Graph::find(NodePredicate::Ptr pred, NodeIterator &begin, NodeIterator &end) {
137     // We could try to be lazy here, but you have a hard time determining if you're
138     // done a priori. So instead we pre-look-up and hand that set into a copy-based
139     // set iterator. 
140     NodeIterator allBegin, allEnd;
141     allNodes(allBegin, allEnd);
142     begin = NodeIterator(new NodeIteratorPredicateObj(pred, allBegin, allEnd));
143     end = NodeIterator(new NodeIteratorPredicateObj(pred, allEnd, allEnd));
144     return (begin != end);
145 }
146                          
147 bool Graph::find(NodePredicateFunc pred, void *user_arg, NodeIterator &begin, NodeIterator &end) {
148     // We could try to be lazy here, but you have a hard time determining if you're
149     // done a priori. So instead we pre-look-up and hand that set into a copy-based
150     // set iterator. 
151     NodeIterator allBegin, allEnd;
152     allNodes(allBegin, allEnd);
153     begin = NodeIterator(new NodeIteratorPredicateFunc(pred, user_arg, allBegin, allEnd));
154     end = NodeIterator(new NodeIteratorPredicateFunc(pred, user_arg, allEnd, allEnd));
155     return (begin != end);
156 }
157
158 void Graph::deleteNode(NodePtr node) {
159   //std::cerr << "Deleting node " << node << std::endl;
160   // Remove from the graph map
161   // Remove from any edges that point to this one
162
163   nodes_.erase(node);
164
165   NodeMap::iterator iter2 = nodesByAddr_.find(node->addr());
166   if (iter2 != nodesByAddr_.end()) {
167     iter2->second.erase(node);
168   }
169
170   entryNodes_.erase(node);
171   exitNodes_.erase(node);
172
173   EdgeIterator e1, e2;
174   node->ins(e1, e2);
175   for (; e1 != e2; ++e1) {
176     (*e1)->source()->deleteOutEdge(e1);
177   }
178
179   node->outs(e1, e2);
180   for (; e1 != e2; ++e1) {
181     (*e1)->target()->deleteInEdge(e1);
182   }
183 }
184     
185 bool Graph::isEntryNode(NodePtr node) {
186   return (entryNodes_.find(node) != entryNodes_.end());
187 }
188
189
190 bool Graph::isExitNode(NodePtr node) {
191   return (exitNodes_.find(node) != exitNodes_.end());
192 }
193
194 unsigned Graph::size() const {
195    return nodes_.size();
196 }
197
198 void Graph::adjustEntryAndExitNodes() {
199     entryNodes_.clear();
200     exitNodes_.clear();
201     NodeIterator gbegin, gend;
202     allNodes(gbegin, gend);
203     for (; gbegin != gend; ++gbegin) {
204         Node::Ptr ptr = *gbegin;
205         if (!ptr->hasInEdges()) insertEntryNode(ptr);
206         if (!ptr->hasOutEdges()) insertExitNode(ptr);
207     }
208
209 }