Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / codeRange.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 // $Id: codeRange.h,v 1.18 2008/01/16 22:01:52 legendre Exp $
33
34
35 #ifndef _codeRangeTree_h_
36 #define _codeRangeTree_h_
37
38 /*******************************************************/
39 /*              header files                           */
40 /*******************************************************/
41
42 #include <assert.h>
43 #include <stdlib.h>
44 #include "common/h/Types.h"
45 #include "common/h/Vector.h"
46 #include "common/h/std_namesp.h"
47
48 #include "dyninstAPI/src/patch.h"
49
50 /** template class for codeRangeTree. The implementation is based on red black
51   * tree implementation for efficiency concerns and for getting sorted
52   * elements easier.
53   * There are two template types, K (key) and V (value).
54   */
55
56 /* Note: this is a near copy of BPatch_Set. That class didn't do what I needed,
57    so... -- bernat, 10OCT03 */
58
59 typedef enum { TREE_RED, TREE_BLACK } color_t;
60
61 class int_function;
62 class int_basicBlock;
63 class bblInstance;
64 class image;
65 class mapped_object;
66 class multiTramp;
67 class baseTrampInstance;
68 class miniTrampInstance;
69 class image_func;
70 class signal_handler_location;
71 class functionReplacement;
72 class replacedFunctionCall;
73 class inferiorRPCinProgress;
74 class image_basicBlock;
75
76 class codeRange : public patchTarget {
77   public:
78     codeRange() { }
79     virtual ~codeRange() { }
80
81     //These are now inherited from relocTarget
82     //virtual Address get_address() const = 0;
83     //virtual unsigned get_size() const = 0;
84
85     virtual void *getPtrToInstruction(Address) const { assert(0); return NULL; }
86
87     // This returns a local pointer to the "beginning" of the
88     // code range - as opposed to get_address, which returns
89     // the "remote" address.
90     virtual void *get_local_ptr() const { 
91         assert(0); return NULL; }
92
93
94     // returns NULL if not of type
95     // so some people who don't like dynamic_cast don't have to be troubled
96     // by it's use
97     
98     // Don't use this; baseTramps aren't top-level members in the
99     //process codeRangeByAddr tree. Instead, use multiTramp and
100     //getBaseTrampInstance.
101     baseTrampInstance *is_basetramp_multi();
102     
103     miniTrampInstance *is_minitramp();
104
105     // This is actually a fake; we don't have int_functions as
106     // code ranges. However, there are many times we want to know
107     // if we're in a function, and this suffices. We actually do a
108     // basic block lookup, then transform that into a function.
109     int_function *is_function();
110     int_basicBlock *is_basicBlock();
111     bblInstance *is_basicBlockInstance();
112
113     image *is_image();
114     mapped_object *is_mapped_object();
115     multiTramp *is_multitramp();
116     image_func *is_image_func();
117     image_basicBlock *is_image_basicBlock();
118     replacedFunctionCall *is_replaced_call();
119     functionReplacement *is_function_replacement();
120     signal_handler_location *is_signal_handler_location();
121     inferiorRPCinProgress *is_inferior_rpc();
122
123     //Prints codeRange info to stderr.  
124     void print_range(Address addr = 0);
125
126     friend ostream &operator<<(ostream &s, const codeRange &c);
127 };
128
129 class codeRangeTree {
130
131     /** tree implementation structure. Used to implement the RB tree */
132     typedef struct entry {
133         Address key;
134         codeRange *value;
135         color_t color;  /* color of the node */
136         struct entry* left; /* left child */
137         struct entry* right; /* right child */
138         struct entry* parent; /* parent of the node */
139
140         /** constructor for structure */
141         entry() 
142             : color(TREE_BLACK),left(NULL),right(NULL),parent(NULL) {}
143
144         /** constructor used for non-nil elements 
145          * @param e nil entry
146          */       
147         entry(entry* e) //constructor with nil entry 
148             : color(TREE_RED), left(e), right(e), parent(NULL) {}
149
150         /** constructor
151          * @param d data element
152          * @param e nill entry 
153          */
154         entry(Address key_, codeRange *value_, entry* e) 
155             : key(key_), value(value_), color(TREE_RED), left(e),
156             right(e), parent(NULL) {}
157
158         /** constructor 
159          * @param e the entry structure that will be copied 
160          */
161         entry(const entry& e) : key(e.key),value(e.value),color(e.color),
162             left(NULL),right(NULL),parent(NULL) {}
163     } entry;
164
165     /** pointer to define the nil element of the tree NULL is not used
166      * since some operations need sentinel nil which may have non-nil
167      * parent.
168      */
169     entry* nil;
170
171     /** size of the tree */
172     int setSize;
173
174     /** pointer to the tree structure */
175     entry* setData;
176
177     // method that implements left rotation used by RB tree for balanced
178     // tree construction and keeps the RBtree properties.
179     void leftRotate(entry*);
180
181     // method that implements right rotattion used by RB tree for balanced
182     // tree construction and keeps the RBtree properties.
183     void rightRotate(entry*);
184
185     // method that modifies the tree structure after deletion for keeping
186     // the RBtree properties.
187     void deleteFixup(entry*);
188
189     // insertion to a binary search tree. It returns the new element pointer
190     // that is inserted. If element is already there it returns NULL
191     entry* treeInsert(Address, codeRange *);
192
193     // finds the elemnts in the tree that will be replaced with the element
194     // being deleted in the  deletion. That is the element with the largest
195     // smallest value than the element being deleted. 
196     entry* treeSuccessor(entry* ) const;
197
198     // method that returns the entry pointer for the element that is searched
199     //for. If the entry is not found then it retuns NULL
200     entry* find_internal(Address) const;
201
202     // infix traverse of the RB tree. It traverses the tree in ascending order
203     void traverse(codeRange **,entry*,int&) const;
204
205     // Vector version of above
206     // infix traverse of the RB tree. It traverses the tree in ascending order
207     void traverse(pdvector<codeRange *> &all, entry*) const;
208
209     // deletes the tree structure for deconstructor.
210     void destroy(entry*);
211
212     /** copy constructor */
213     codeRangeTree(const codeRangeTree &/* y */) {};
214
215   public:
216
217     /** constructor. The default comparison structure is used */
218     codeRangeTree() : setSize(0) { 
219         nil = new entry;
220         setData = nil;
221     }
222
223     
224     /** destructor which deletes all tree structure and allocated entries */
225     ~codeRangeTree() {
226         destroy(setData);
227         delete nil;
228     }
229
230     /** returns the cardinality of the tree , number of elements */
231     int size() const { return setSize; }
232     
233     /** returns true if tree is empty */
234     bool empty() const { return (setData == nil); }
235
236     /** inserts the element in the tree 
237      * @param 1 element that will be inserted
238      */
239     void insert(codeRange *);
240
241     /** removes the element in the tree 
242      * @param 1 element that will be removed  
243      */
244     void remove(Address);
245
246     /** returns true if the argument is member of the codeRangeTree
247      * @param e the element that will be searched for
248      */
249     bool find(Address, codeRange *&) const;
250
251     /** Returns the largest value less than or equal to the
252      * key given
253      */
254     bool precessor(Address, codeRange *&) const;
255
256     /** Returns the smallest value greater than or equal to the
257      * key given
258      */
259     bool successor(Address, codeRange *&) const;
260
261     /** fill an buffer array with the sorted
262      * elements of the codeRangeTree in ascending order according to comparison function
263      * if the codeRangeTree is empty it retuns NULL, other wise it returns 
264      * the input argument.
265      */
266     codeRange ** elements(codeRange **) const;
267
268     // And vector-style
269     bool elements(pdvector<codeRange *> &) const;
270
271     // method that replicates the tree structure of this tree
272     entry* replicateTree(entry*,entry*,entry*,entry*);
273
274     // Remove all entries in the tree
275     void clear();
276 };
277
278 #endif /* _codeRangeTree_h_ */
279