Update copyright to LGPL on all files
[dyninst.git] / dynutil / h / Node.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 #if !defined(NODE_H)
33 #define NODE_H
34
35 #include "dyn_detail/boost/shared_ptr.hpp"
36 #include <set>
37 #include <string>
38 #include "Annotatable.h"
39
40 #include "dyntypes.h"
41
42
43 class BPatch_function;
44 class BPatch_basicBlock;
45
46 namespace Dyninst {
47
48 class Edge;
49 class Graph;
50 class NodeIterator;
51 class EdgeIterator;
52
53 class Node : public AnnotatableSparse {
54     friend class Edge;
55     friend class Graph;
56     
57     typedef dyn_detail::boost::shared_ptr<Edge> EdgePtr;
58     typedef dyn_detail::boost::shared_ptr<Graph> GraphPtr;
59     typedef std::set<EdgePtr> EdgeSet;
60
61  public:
62     typedef dyn_detail::boost::shared_ptr<Node> Ptr;
63
64     void ins(EdgeIterator &begin, EdgeIterator &end);
65     void outs(EdgeIterator &begin, EdgeIterator &end);
66
67     void ins(NodeIterator &begin, NodeIterator &end);
68     void outs(NodeIterator &begin, NodeIterator &end);
69
70     bool hasInEdges(); 
71     bool hasOutEdges();
72
73     void forwardClosure(NodeIterator &begin, NodeIterator &end);
74     void backwardClosure(NodeIterator &begin, NodeIterator &end);
75
76     GraphPtr forwardSubgraph();
77     GraphPtr backwardSubgraph();
78     
79     virtual Address addr() const { return INVALID_ADDR; }
80     
81     virtual std::string format() const = 0;
82
83     virtual Node::Ptr copy() = 0;
84     
85     virtual bool isVirtual() const = 0;
86     
87     virtual ~Node() {};
88
89     // DOT output methods...
90     virtual std::string DOTshape() const;
91     virtual std::string DOTrank() const;
92     virtual std::string DOTname() const;
93     virtual bool DOTinclude() const { return true; }
94
95  protected:
96     Node() {};
97
98     EdgeSet ins_;
99     EdgeSet outs_;
100     
101     void addInEdge(const EdgePtr in) { ins_.insert(in); }
102     void addOutEdge(const EdgePtr out) { outs_.insert(out); }
103
104     static const Address INVALID_ADDR;
105 };
106  
107 class PhysicalNode : public Node {
108 public:
109     typedef dyn_detail::boost::shared_ptr<PhysicalNode> Ptr;
110      
111     static Node::Ptr createNode(Address addr);
112     
113     virtual Address addr() const { return addr_; }
114     
115     virtual std::string format() const;
116     
117     virtual bool isVirtual() const { return false; }
118     
119     virtual ~PhysicalNode() {};
120     
121     virtual Node::Ptr copy();
122
123  protected:
124     PhysicalNode(Address addr) : addr_(addr) {};
125     
126     Address addr_; 
127 };
128
129 class VirtualNode : public Node {
130     friend class Edge;
131     friend class Graph;
132
133  public:
134     typedef dyn_detail::boost::shared_ptr<VirtualNode> Ptr;
135     
136     static Node::Ptr createNode();
137     static Node::Ptr createNode(std::string name); 
138
139     virtual std::string format() const;
140     virtual Node::Ptr copy();
141     
142     virtual bool isVirtual() const { return true; }
143     
144     virtual ~VirtualNode() {};
145
146     VirtualNode(std::string name) : name_(name) {};
147     VirtualNode() : name_(defaultName) {};
148
149     static std::string defaultName;
150
151     // DOT output methods...
152     virtual std::string DOTshape() const;
153  private:
154     std::string name_;
155 };
156
157  class NodeIteratorImpl;
158
159 class NodeIterator {
160     friend class Node;
161     friend class Graph;
162     friend class Edge;
163
164  public:
165
166     NodeIterator &operator++();
167     NodeIterator operator++(int);
168
169     NodeIterator &operator--();
170     NodeIterator operator--(int);
171
172     Node::Ptr operator*() const;
173
174     bool operator==(const NodeIterator &rhs) const;
175     bool operator!=(const NodeIterator &rhs) const;
176
177     NodeIterator &operator=(const NodeIterator &rhs);
178
179
180     // For code such as:
181     // NodeIterator begin, end;
182     // graph->entryNodes(begin, end);
183     NodeIterator();
184
185     // Main constructor
186     // The iter parameter becomes owned by the iterator and will be destroyed
187     // when the iterator is destroyed.
188     NodeIterator(NodeIteratorImpl *iter);
189
190     // Aaaand let's _really_ not forget the copy constructor
191     NodeIterator(const NodeIterator &rhs);
192
193     ~NodeIterator();
194
195  protected:
196
197     // We hide the internal iteration behavior behind a pointer. 
198     // This allows us to override (yay for virtual functions).
199     NodeIteratorImpl *iter_;
200
201     NodeIteratorImpl *copy() const;
202
203 };
204
205 }
206 #endif