Update copyright to LGPL on all files
[dyninst.git] / common / src / Graph.C
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 implementation
33
34 #include "Graph.h"
35 #include "Edge.h"
36 #include "Node.h"
37 #include <assert.h>
38
39 #include "NodeIterator.h"
40
41 using namespace Dyninst;
42
43 const Dyninst::Address Graph::INITIAL_ADDR = (Address) -1;
44
45 void Graph::entryNodes(NodeIterator &begin, NodeIterator &end) {
46     begin = NodeIterator(new NodeIteratorSet(entryNodes_.begin()));
47     end = NodeIterator(new NodeIteratorSet(entryNodes_.end()));
48     return;
49 }
50
51 void Graph::exitNodes(NodeIterator &begin, NodeIterator &end) {
52     begin = NodeIterator(new NodeIteratorSet(exitNodes_.begin()));
53     end = NodeIterator(new NodeIteratorSet(exitNodes_.end()));
54     return;
55 }
56
57 void Graph::allNodes(NodeIterator &begin, NodeIterator &end) {
58     begin = NodeIterator(new NodeIteratorSet(nodes_.begin()));
59     end = NodeIterator(new NodeIteratorSet(nodes_.end()));
60     return;
61 }
62
63 bool Graph::find(Address addr, NodeIterator &begin, NodeIterator &end) {
64     NodeMap::iterator iter = nodesByAddr_.find(addr);
65     if (iter == nodesByAddr_.end()) return false;
66
67     begin = NodeIterator(new NodeIteratorSet(iter->second.begin()));
68     end = NodeIterator(new NodeIteratorSet(iter->second.end()));
69     return true;
70 }
71
72 Graph::Graph() {};
73
74 Graph::Ptr Graph::createGraph() {
75     return Graph::Ptr(new Graph());
76 }
77
78 void Graph::insertPair(NodePtr source, NodePtr target) {
79     // TODO handle parameter edge types.
80
81     Edge::Ptr e = Edge::createEdge(source, target);
82
83     addNode(source);
84     addNode(target);
85
86     source->addOutEdge(e);
87     target->addInEdge(e);
88 }
89
90 void Graph::insertEntryNode(NodePtr entry) {
91     addNode(entry);
92     entryNodes_.insert(entry);
93 }
94
95 void Graph::insertExitNode(NodePtr exit) {
96     addNode(exit);
97     exitNodes_.insert(exit);
98 }
99
100 void Graph::addNode(Node::Ptr node) {
101     if (node->hasInEdges() || node->hasOutEdges()) return;
102     nodes_.insert(node);
103     if (!node->isVirtual()) {
104         nodesByAddr_[node->addr()].insert(node);
105     }        
106 }
107
108
109 // Fancy-shmancy predicate based search methods...
110
111 bool Graph::find(NodePredicate::Ptr pred, NodeIterator &begin, NodeIterator &end) {
112     // We could try to be lazy here, but you have a hard time determining if you're
113     // done a priori. So instead we pre-look-up and hand that set into a copy-based
114     // set iterator. 
115     NodeIterator allBegin, allEnd;
116     allNodes(allBegin, allEnd);
117     begin = NodeIterator(new NodeIteratorPredicateObj(pred, allBegin, allEnd));
118     end = NodeIterator(new NodeIteratorPredicateObj(pred, allEnd, allEnd));
119     return (begin != end);
120 }
121                          
122 bool Graph::find(NodePredicateFunc pred, void *user_arg, NodeIterator &begin, NodeIterator &end) {
123     // We could try to be lazy here, but you have a hard time determining if you're
124     // done a priori. So instead we pre-look-up and hand that set into a copy-based
125     // set iterator. 
126     NodeIterator allBegin, allEnd;
127     allNodes(allBegin, allEnd);
128     begin = NodeIterator(new NodeIteratorPredicateFunc(pred, user_arg, allBegin, allEnd));
129     end = NodeIterator(new NodeIteratorPredicateFunc(pred, user_arg, allEnd, allEnd));
130     return (begin != end);
131 }
132
133