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