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