Relocation and loop instrumentation - - - - - - - - - - - - - - - - - -
[dyninst.git] / dyninstAPI / src / codeRange.C
1 /*
2  * Copyright (c) 1996-2004 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // $Id: codeRange.C,v 1.8 2005/03/01 23:07:41 bernat Exp $
43
44 #include <stdio.h>
45 #include "codeRange.h"
46
47 #include "dyninstAPI/src/symtab.h"
48 #include "dyninstAPI/src/trampTemplate.h"
49 #include "dyninstAPI/src/miniTrampHandle.h"
50 #include "dyninstAPI/src/sharedobject.h"
51 #include "dyninstAPI/src/function.h"
52 #include "dyninstAPI/src/func-reloc.h"
53 #include "dyninstAPI/src/edgeTrampTemplate.h"
54
55 multitrampTemplate *codeRange::is_multitramp() {
56    return dynamic_cast<multitrampTemplate *>(this);
57 }
58
59 trampTemplate *codeRange::is_basetramp() {
60    return dynamic_cast<trampTemplate *>(this);
61 }
62
63 miniTrampHandle *codeRange::is_minitramp() {
64    return dynamic_cast<miniTrampHandle *>(this);
65 }
66
67 int_function *codeRange::is_function() {
68    return dynamic_cast<int_function *>(this);
69 }
70
71 image *codeRange::is_image() {
72    return dynamic_cast<image *>(this);
73 }
74
75 shared_object *codeRange::is_shared_object() {
76    return dynamic_cast<shared_object *>(this);
77 }
78
79 relocatedFuncInfo *codeRange::is_relocated_func() {
80    return dynamic_cast<relocatedFuncInfo *>(this);
81 }
82
83 edgeTrampTemplate *codeRange::is_edge_tramp() {
84    return dynamic_cast<edgeTrampTemplate *>(this);
85 }
86
87 void codeRangeTree::leftRotate(entry* pivot){
88         if(!pivot || (pivot == nil))
89                 return;
90         entry* y = pivot->right;
91         if(y == nil)
92                 return;
93         pivot->right = y->left;
94         if(y->left != nil)
95                 y->left->parent = pivot;
96         y->parent = pivot->parent;
97         if(!pivot->parent)
98                 setData = y;
99         else if(pivot == pivot->parent->left)
100                 pivot->parent->left = y;
101         else
102                 pivot->parent->right = y;
103         y->left = pivot;
104         pivot->parent = y;
105 }
106
107
108 void codeRangeTree::rightRotate(entry* pivot){
109         if(!pivot || (pivot == nil))
110                 return;
111         entry* x = pivot->left;
112         if(x == nil)
113                 return;
114         pivot->left = x->right;
115         if(x->right != nil)
116                 x->right->parent = pivot;
117         x->parent = pivot->parent;
118         if(!pivot->parent)
119                 setData = x;
120         else if(pivot == pivot->parent->left)
121                 pivot->parent->left = x;
122         else
123                 pivot->parent->right = x;
124         x->right = pivot;
125         pivot->parent = x;
126 }
127
128
129 void codeRangeTree::deleteFixup(entry* x){
130         while((x != setData) && 
131               (x->color == TREE_BLACK))
132         {
133                 if(x == x->parent->left){
134                         entry* w = x->parent->right;
135                         if(w->color == TREE_RED){
136                                 w->color = TREE_BLACK;
137                                 x->parent->color = TREE_RED;
138                                 leftRotate(x->parent);
139                                 w = x->parent->right;
140                         }
141                         if((w->left->color == TREE_BLACK) &&
142                            (w->right->color == TREE_BLACK)){
143                                 w->color = TREE_RED;
144                                 x = x->parent;
145                         }
146                         else{
147                                 if(w->right->color == TREE_BLACK){
148                                         w->left->color = TREE_BLACK;
149                                         w->color = TREE_RED;
150                                         rightRotate(w);
151                                         w = x->parent->right;
152                                 }
153                                 w->color = x->parent->color;
154                                 x->parent->color = TREE_BLACK;
155                                 w->right->color = TREE_BLACK;
156                                 leftRotate(x->parent);
157                                 x = setData;
158                         }
159                 }
160                 else{
161                         entry* w = x->parent->left;
162                         if(w->color == TREE_RED){
163                                 w->color = TREE_BLACK;
164                                 x->parent->color = TREE_RED;
165                                 rightRotate(x->parent);
166                                 w = x->parent->left;
167                         }
168                         if((w->right->color == TREE_BLACK) &&
169                            (w->left->color == TREE_BLACK)){
170                                 w->color = TREE_RED;
171                                 x = x->parent;
172                         }
173                         else{
174                                 if(w->left->color == TREE_BLACK){
175                                         w->right->color = TREE_BLACK;
176                                         w->color = TREE_RED;
177                                         leftRotate(w);
178                                         w = x->parent->left;
179                                 }
180                                 w->color = x->parent->color;
181                                 x->parent->color = TREE_BLACK;
182                                 w->left->color = TREE_BLACK;
183                                 rightRotate(x->parent);
184                                 x = setData;
185                         }
186                 }
187         }
188         x->color = TREE_BLACK;
189 }
190
191
192 codeRangeTree::entry *codeRangeTree::treeInsert(Address key, codeRange *value)
193 {
194         entry* y = NULL;
195         entry* x = setData;
196         while(x != nil){
197                 y = x;
198         if (key < x->key) 
199                         x = x->left;
200                 else if(key > x->key)
201                         x = x->right;
202                 else
203                         return NULL;
204         }       
205         entry* z = new entry(key, value, nil);
206         z->parent = y;
207         if(!y)
208                 setData = z;
209         else {
210         if (key < y->key)
211             y->left = z;
212                 else if (key > y->key)
213                         y->right = z;
214         }
215         setSize++;
216         return z;
217 }
218
219 /** finds the minimum value node when x is being deleted */
220
221 codeRangeTree::entry *codeRangeTree::treeSuccessor(entry* x) const{
222         if(!x || (x == nil))
223                 return NULL;
224         if(x->right != nil){
225                 entry* z = x->right;
226                 while(z->left != nil) z = z->left;
227                 return z;
228         }
229         entry* y = x->parent;
230         while(y && (x == y->right)){
231                 x = y;
232                 y = y->parent;
233         }
234         return y;
235 }
236
237
238 codeRangeTree::entry *codeRangeTree::find_internal(Address element) const{
239         entry* x = setData;
240         while(x != nil){
241         if (element < x->key)
242             x = x->left;
243         else if (element > x->key)
244             x = x->right;
245         else
246             return x;
247         }       
248         return NULL;
249 }
250
251
252 void codeRangeTree::traverse(codeRange ** all, entry* node, int& n) const{
253         if(node == nil)
254                 return;
255         if(node->left != nil)
256                 traverse(all,node->left,n);
257         if(all)
258                 all[n++] = node->value;
259         if(node->right != nil)
260                 traverse(all,node->right,n);
261 }
262
263 //////////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
264
265  void codeRangeTree::insert(Address key, codeRange *value) {
266         entry* x = treeInsert(key, value);
267         if(!x) return;
268         x->color = TREE_RED;
269         while((x != setData) && (x->parent->color == TREE_RED)){
270                 if(x->parent == x->parent->parent->left){
271                         entry* y = x->parent->parent->right;
272                         if(y->color == TREE_RED){
273                                 x->parent->color = TREE_BLACK;
274                                 y->color = TREE_BLACK;
275                                 x->parent->parent->color = TREE_RED;
276                                 x = x->parent->parent;
277                         }
278                         else{
279                                 if(x == x->parent->right){
280                                         x = x->parent;
281                                         leftRotate(x);
282                                 }
283                                 x->parent->color = TREE_BLACK;
284                                 x->parent->parent->color = TREE_RED;
285                                 rightRotate(x->parent->parent);
286                         }
287                 }
288                 else{
289                         entry* y = x->parent->parent->left;
290                         if(y->color == TREE_RED){
291                                 x->parent->color = TREE_BLACK;
292                                 y->color = TREE_BLACK;
293                                 x->parent->parent->color = TREE_RED;
294                                 x = x->parent->parent;
295                         }
296                         else{
297                                 if(x == x->parent->left){
298                                         x = x->parent;
299                                         rightRotate(x);
300                                 }
301                                 x->parent->color = TREE_BLACK;
302                                 x->parent->parent->color = TREE_RED;
303                                 leftRotate(x->parent->parent);
304                         }
305                 }
306         }
307         setData->color = TREE_BLACK;
308 }
309
310  void codeRangeTree::remove(Address key){
311         entry* z = find_internal(key);
312         if(!z)
313                 return;
314         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
315         entry* x=(y->left != nil) ? y->left : y->right;
316         x->parent = y->parent;
317         if(!y->parent)
318                 setData = x;
319         else if(y == y->parent->left)
320                 y->parent->left = x;
321         else
322                 y->parent->right = x;
323         if(y != z) {
324                 z->value = y->value;
325         z->key = y->key;
326     }
327         if(y->color == TREE_BLACK)
328                 deleteFixup(x);
329         setSize--;
330         delete y;
331 }
332
333
334
335
336 void codeRangeTree::destroy(entry* node){
337         if(!node || (node == nil))
338                 return;
339         if(node->left != nil)
340                 destroy(node->left);
341         if(node->right != nil)
342                 destroy(node->right);
343         delete node;
344 }
345
346 bool codeRangeTree::find(Address key, codeRange *& value) const{
347         entry* x = find_internal(key);
348    if (!x) return false;
349    value = x->value;
350    return true;
351 }
352
353 bool codeRangeTree::precessor(Address key, codeRange * &value) const{
354     entry *x = setData;
355     entry *last = nil;
356     while (x != nil) {
357         assert(x != NULL);
358         if (x->key == key) {
359             value = x->value;
360             return true;
361         }
362         else if (key < x->key) {
363             x = x->left;
364         }
365         else { // key > x->key
366             last = x;
367             x = x->right;
368         }
369     }
370     if (x == nil) {
371         // Ran out of tree to search... get the parent
372         assert(last != NULL);
373         
374         if (last != nil) {
375             value = last->value;
376             return true;
377         }
378         else return false;
379     }
380     // Should never hit here
381     assert(0);
382     return false;
383 }
384
385 bool codeRangeTree::successor(Address key, codeRange * &value) const{
386     entry *x = setData;
387     entry *last = nil;
388     while (x != nil) {
389         if (x->key == key) {
390             value = x->value;
391             return true;
392         }
393         else if (key > x->key) {
394             x = x->right;
395         }
396         else { // key < x->key
397             last = x;
398             x = x->left;
399         }
400     }
401     if (x == nil) {
402         // Ran out of tree to search... get the parent
403         if (last != nil) {
404             value = last->value;
405             return true;
406         }
407         else return false;
408     }
409     // Should never reach this point
410     assert(0);
411     return false;
412 }
413
414 codeRange ** codeRangeTree::elements(codeRange ** buffer) const{
415         if(setData == nil) return NULL;
416         if(!buffer) return NULL;
417         int tmp = 0;
418         traverse(buffer,setData,tmp);   
419         return buffer;
420 }
421
422
423 codeRangeTree::entry *codeRangeTree::replicateTree(entry* node,entry* parent,
424                                                    entry* oldNil,entry* newNil)
425 {
426         if(node == oldNil)
427                 return newNil;  
428
429         entry* newNode = new entry(*node);
430         newNode->value = newNode->value->copy();
431
432         newNode->parent = parent; 
433         newNode->left = replicateTree(node->left,newNode,oldNil,newNil);
434         newNode->right = replicateTree(node->right,newNode,oldNil,newNil);
435         return newNode; 
436 }