Updated copyright string
[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.3 2004/03/23 01:12:02 eli 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
52 trampTemplate *codeRange::is_basetramp() {
53    return dynamic_cast<trampTemplate *>(this);
54 }
55
56 miniTrampHandle *codeRange::is_minitramp() {
57    return dynamic_cast<miniTrampHandle *>(this);
58 }
59
60 pd_Function *codeRange::is_pd_Function() {
61    return dynamic_cast<pd_Function *>(this);
62 }
63
64 image *codeRange::is_image() {
65    return dynamic_cast<image *>(this);
66 }
67
68 shared_object *codeRange::is_shared_object() {
69    return dynamic_cast<shared_object *>(this);
70 }
71
72 relocatedFuncInfo *codeRange::is_relocated_func() {
73    return dynamic_cast<relocatedFuncInfo *>(this);
74 }
75
76 void codeRangeTree::leftRotate(entry* pivot){
77         if(!pivot || (pivot == nil))
78                 return;
79         entry* y = pivot->right;
80         if(y == nil)
81                 return;
82         pivot->right = y->left;
83         if(y->left != nil)
84                 y->left->parent = pivot;
85         y->parent = pivot->parent;
86         if(!pivot->parent)
87                 setData = y;
88         else if(pivot == pivot->parent->left)
89                 pivot->parent->left = y;
90         else
91                 pivot->parent->right = y;
92         y->left = pivot;
93         pivot->parent = y;
94 }
95
96
97 void codeRangeTree::rightRotate(entry* pivot){
98         if(!pivot || (pivot == nil))
99                 return;
100         entry* x = pivot->left;
101         if(x == nil)
102                 return;
103         pivot->left = x->right;
104         if(x->right != nil)
105                 x->right->parent = pivot;
106         x->parent = pivot->parent;
107         if(!pivot->parent)
108                 setData = x;
109         else if(pivot == pivot->parent->left)
110                 pivot->parent->left = x;
111         else
112                 pivot->parent->right = x;
113         x->right = pivot;
114         pivot->parent = x;
115 }
116
117
118 void codeRangeTree::deleteFixup(entry* x){
119         while((x != setData) && 
120               (x->color == TREE_BLACK))
121         {
122                 if(x == x->parent->left){
123                         entry* w = x->parent->right;
124                         if(w->color == TREE_RED){
125                                 w->color = TREE_BLACK;
126                                 x->parent->color = TREE_RED;
127                                 leftRotate(x->parent);
128                                 w = x->parent->right;
129                         }
130                         if((w->left->color == TREE_BLACK) &&
131                            (w->right->color == TREE_BLACK)){
132                                 w->color = TREE_RED;
133                                 x = x->parent;
134                         }
135                         else{
136                                 if(w->right->color == TREE_BLACK){
137                                         w->left->color = TREE_BLACK;
138                                         w->color = TREE_RED;
139                                         rightRotate(w);
140                                         w = x->parent->right;
141                                 }
142                                 w->color = x->parent->color;
143                                 x->parent->color = TREE_BLACK;
144                                 w->right->color = TREE_BLACK;
145                                 leftRotate(x->parent);
146                                 x = setData;
147                         }
148                 }
149                 else{
150                         entry* w = x->parent->left;
151                         if(w->color == TREE_RED){
152                                 w->color = TREE_BLACK;
153                                 x->parent->color = TREE_RED;
154                                 rightRotate(x->parent);
155                                 w = x->parent->left;
156                         }
157                         if((w->right->color == TREE_BLACK) &&
158                            (w->left->color == TREE_BLACK)){
159                                 w->color = TREE_RED;
160                                 x = x->parent;
161                         }
162                         else{
163                                 if(w->left->color == TREE_BLACK){
164                                         w->right->color = TREE_BLACK;
165                                         w->color = TREE_RED;
166                                         leftRotate(w);
167                                         w = x->parent->left;
168                                 }
169                                 w->color = x->parent->color;
170                                 x->parent->color = TREE_BLACK;
171                                 w->left->color = TREE_BLACK;
172                                 rightRotate(x->parent);
173                                 x = setData;
174                         }
175                 }
176         }
177         x->color = TREE_BLACK;
178 }
179
180
181 codeRangeTree::entry *codeRangeTree::treeInsert(Address key, codeRange *value)
182 {
183         entry* y = NULL;
184         entry* x = setData;
185         while(x != nil){
186                 y = x;
187         if (key < x->key) 
188                         x = x->left;
189                 else if(key > x->key)
190                         x = x->right;
191                 else
192                         return NULL;
193         }       
194         entry* z = new entry(key, value, nil);
195         z->parent = y;
196         if(!y)
197                 setData = z;
198         else {
199         if (key < y->key)
200             y->left = z;
201                 else if (key > y->key)
202                         y->right = z;
203         }
204         setSize++;
205         return z;
206 }
207
208 /** finds the minimum value node when x is being deleted */
209
210 codeRangeTree::entry *codeRangeTree::treeSuccessor(entry* x) const{
211         if(!x || (x == nil))
212                 return NULL;
213         if(x->right != nil){
214                 entry* z = x->right;
215                 while(z->left != nil) z = z->left;
216                 return z;
217         }
218         entry* y = x->parent;
219         while(y && (x == y->right)){
220                 x = y;
221                 y = y->parent;
222         }
223         return y;
224 }
225
226
227 codeRangeTree::entry *codeRangeTree::find_internal(Address element) const{
228         entry* x = setData;
229         while(x != nil){
230         if (element < x->key)
231             x = x->left;
232         else if (element > x->key)
233             x = x->right;
234         else
235             return x;
236         }       
237         return NULL;
238 }
239
240
241 void codeRangeTree::traverse(codeRange ** all, entry* node, int& n) const{
242         if(node == nil)
243                 return;
244         if(node->left != nil)
245                 traverse(all,node->left,n);
246         if(all)
247                 all[n++] = node->value;
248         if(node->right != nil)
249                 traverse(all,node->right,n);
250 }
251
252 //////////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
253
254  void codeRangeTree::insert(Address key, codeRange *value) {
255         entry* x = treeInsert(key, value);
256         if(!x) return;
257         x->color = TREE_RED;
258         while((x != setData) && (x->parent->color == TREE_RED)){
259                 if(x->parent == x->parent->parent->left){
260                         entry* y = x->parent->parent->right;
261                         if(y->color == TREE_RED){
262                                 x->parent->color = TREE_BLACK;
263                                 y->color = TREE_BLACK;
264                                 x->parent->parent->color = TREE_RED;
265                                 x = x->parent->parent;
266                         }
267                         else{
268                                 if(x == x->parent->right){
269                                         x = x->parent;
270                                         leftRotate(x);
271                                 }
272                                 x->parent->color = TREE_BLACK;
273                                 x->parent->parent->color = TREE_RED;
274                                 rightRotate(x->parent->parent);
275                         }
276                 }
277                 else{
278                         entry* y = x->parent->parent->left;
279                         if(y->color == TREE_RED){
280                                 x->parent->color = TREE_BLACK;
281                                 y->color = TREE_BLACK;
282                                 x->parent->parent->color = TREE_RED;
283                                 x = x->parent->parent;
284                         }
285                         else{
286                                 if(x == x->parent->left){
287                                         x = x->parent;
288                                         rightRotate(x);
289                                 }
290                                 x->parent->color = TREE_BLACK;
291                                 x->parent->parent->color = TREE_RED;
292                                 leftRotate(x->parent->parent);
293                         }
294                 }
295         }
296         setData->color = TREE_BLACK;
297 }
298
299  void codeRangeTree::remove(Address key){
300         entry* z = find_internal(key);
301         if(!z)
302                 return;
303         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
304         entry* x=(y->left != nil) ? y->left : y->right;
305         x->parent = y->parent;
306         if(!y->parent)
307                 setData = x;
308         else if(y == y->parent->left)
309                 y->parent->left = x;
310         else
311                 y->parent->right = x;
312         if(y != z) {
313                 z->value = y->value;
314         z->key = y->key;
315     }
316         if(y->color == TREE_BLACK)
317                 deleteFixup(x);
318         setSize--;
319         delete y;
320 }
321
322
323
324
325 void codeRangeTree::destroy(entry* node){
326         if(!node || (node == nil))
327                 return;
328         if(node->left != nil)
329                 destroy(node->left);
330         if(node->right != nil)
331                 destroy(node->right);
332         delete node;
333 }
334
335 bool codeRangeTree::find(Address key, codeRange *& value) const{
336         entry* x = find_internal(key);
337    if (!x) return false;
338    value = x->value;
339    return true;
340 }
341
342 bool codeRangeTree::precessor(Address key, codeRange * &value) const{
343     entry *x = setData;
344     entry *last = nil;
345     while (x != nil) {
346         assert(x != NULL);
347         if (x->key == key) {
348             value = x->value;
349             return true;
350         }
351         else if (key < x->key) {
352             x = x->left;
353         }
354         else { // key > x->key
355             last = x;
356             x = x->right;
357         }
358     }
359     if (x == nil) {
360         // Ran out of tree to search... get the parent
361         assert(last != NULL);
362         
363         if (last != nil) {
364             value = last->value;
365             return true;
366         }
367         else return false;
368     }
369     // Should never hit here
370     assert(0);
371     return false;
372 }
373
374 bool codeRangeTree::successor(Address key, codeRange * &value) const{
375     entry *x = setData;
376     entry *last = nil;
377     while (x != nil) {
378         if (x->key == key) {
379             value = x->value;
380             return true;
381         }
382         else if (key > x->key) {
383             x = x->right;
384         }
385         else { // key < x->key
386             last = x;
387             x = x->left;
388         }
389     }
390     if (x == nil) {
391         // Ran out of tree to search... get the parent
392         if (last != nil) {
393             value = last->value;
394             return true;
395         }
396         else return false;
397     }
398     // Should never reach this point
399     assert(0);
400     return false;
401 }
402
403 codeRange ** codeRangeTree::elements(codeRange ** buffer) const{
404         if(setData == nil) return NULL;
405         if(!buffer) return NULL;
406         int tmp = 0;
407         traverse(buffer,setData,tmp);   
408         return buffer;
409 }
410
411
412 codeRangeTree::entry *codeRangeTree::replicateTree(entry* node,entry* parent,
413                                                    entry* oldNil,entry* newNil)
414 {
415         if(node == oldNil)
416                 return newNil;  
417
418         entry* newNode = new entry(*node);
419         newNode->parent = parent; 
420         newNode->left = replicateTree(node->left,newNode,oldNil,newNil);
421         newNode->right = replicateTree(node->right,newNode,oldNil,newNil);
422         return newNode; 
423 }
424
425
426
427