Update copyright to LGPL on all files
[dyninst.git] / common / h / addrRange.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 #ifndef _addrRange_h_
33 #define _addrRange_h_
34
35 /*******************************************************/
36 /*      Templated header file                               */
37 /*******************************************************/
38
39 #include <assert.h>
40 #include <stdlib.h>
41 #include <vector>
42 #include "common/h/Types.h"
43 #include "common/h/Vector.h"
44 #include "common/h/std_namesp.h"
45
46 /** template class for addrRangeTree. The implementation is based on red black
47  * tree implementation for efficiency concerns and for getting sorted
48  * elements easier.
49  * There are two template types, K (key) and V (value).
50  */
51
52 /* Note: this is a near copy of BPatch_Set. That class didn't do what I needed,
53    so... -- bernat, 10OCT03 */
54
55 typedef enum { TREE_RED, TREE_BLACK } color_t;
56
57 class addrRange {
58  public:
59    virtual Address get_address() const = 0;
60    virtual unsigned long get_size() const = 0;
61    virtual std::string get_name() const {
62       return std::string("UNNAMED");
63    }
64    virtual ~addrRange() {
65    };
66 };
67
68 /** 
69  * T should inherit from addrRange
70  **/
71 template <class T>
72 class addrRangeTree {
73
74    /** tree implementation structure. Used to implement the RB tree */
75    typedef struct entry {
76       Address key;
77       T *value;
78       color_t color;    /* color of the node */
79       struct entry* left; /* left child */
80       struct entry* right; /* right child */
81       struct entry* parent; /* parent of the node */
82
83       /** constructor for structure */
84       entry() 
85          : color(TREE_BLACK),left(NULL),right(NULL),parent(NULL) 
86       {
87       }
88
89       /** constructor used for non-nil elements 
90        * @param e nil entry
91        */         
92       entry(entry* e) //constructor with nil entry 
93          : color(TREE_RED), left(e), right(e), parent(NULL) 
94       {
95       }
96
97       /** constructor
98        * @param d data element
99        * @param e nill entry 
100        */
101       entry(Address key_, T *value_, entry* e) 
102          : key(key_), value(value_), color(TREE_RED), left(e),
103            right(e), parent(NULL) 
104       {
105       }
106
107       /** constructor 
108        * @param e the entry structure that will be copied 
109        */
110       entry(const entry& e) : key(e.key),value(e.value),color(e.color),
111                               left(NULL),right(NULL),parent(NULL) 
112       {
113       }
114    } entry;
115
116    /** pointer to define the nil element of the tree NULL is not used
117     * since some operations need sentinel nil which may have non-nil
118     * parent.
119     */
120    entry* nil;
121
122    /** size of the tree */
123    int setSize;
124
125    /** pointer to the tree structure */
126    entry* setData;
127
128    // method that implements left rotation used by RB tree for balanced
129    // tree construction and keeps the RBtree properties.
130    void leftRotate(entry* pivot)
131    {
132       if(!pivot || (pivot == nil))
133          return;
134       entry* y = pivot->right;
135       if(y == nil)
136          return;
137       pivot->right = y->left;
138       if(y->left != nil)
139          y->left->parent = pivot;
140       y->parent = pivot->parent;
141       if(!pivot->parent) {
142          setData = y;
143       }
144       else if(pivot == pivot->parent->left)
145          pivot->parent->left = y;
146       else
147          pivot->parent->right = y;
148       y->left = pivot;
149       pivot->parent = y;
150    }
151
152    // method that implements right rotattion used by RB tree for balanced
153    // tree construction and keeps the RBtree properties.
154    void rightRotate(entry *pivot)
155    {
156       if(!pivot || (pivot == nil))
157          return;
158       entry* x = pivot->left;
159       if(x == nil)
160          return;
161       pivot->left = x->right;
162       if(x->right != nil)
163          x->right->parent = pivot;
164       x->parent = pivot->parent;
165       if(!pivot->parent) {
166          setData = x;
167       }
168       else if(pivot == pivot->parent->left)
169          pivot->parent->left = x;
170       else
171          pivot->parent->right = x;
172       x->right = pivot;
173       pivot->parent = x;
174    }
175
176    // method that modifies the tree structure after deletion for keeping
177    // the RBtree properties.
178    void deleteFixup(entry *x)
179    {
180       while((x != setData) && 
181             (x->color == TREE_BLACK))
182       {
183          if(x == x->parent->left){
184             entry* w = x->parent->right;
185             if(w->color == TREE_RED){
186                w->color = TREE_BLACK;
187                x->parent->color = TREE_RED;
188                leftRotate(x->parent);
189                w = x->parent->right;
190             }
191             if((w->left->color == TREE_BLACK) &&
192                (w->right->color == TREE_BLACK)){
193                w->color = TREE_RED;
194                x = x->parent;
195             }
196             else{
197                if(w->right->color == TREE_BLACK){
198                   w->left->color = TREE_BLACK;
199                   w->color = TREE_RED;
200                   rightRotate(w);
201                   w = x->parent->right;
202                }
203                w->color = x->parent->color;
204                x->parent->color = TREE_BLACK;
205                w->right->color = TREE_BLACK;
206                leftRotate(x->parent);
207                x = setData;
208             }
209          }
210          else{
211             entry* w = x->parent->left;
212             if(w->color == TREE_RED){
213                w->color = TREE_BLACK;
214                x->parent->color = TREE_RED;
215                rightRotate(x->parent);
216                w = x->parent->left;
217             }
218             if((w->right->color == TREE_BLACK) &&
219                (w->left->color == TREE_BLACK)){
220                w->color = TREE_RED;
221                x = x->parent;
222             }
223             else{
224                if(w->left->color == TREE_BLACK){
225                   w->right->color = TREE_BLACK;
226                   w->color = TREE_RED;
227                   leftRotate(w);
228                   w = x->parent->left;
229                }
230                w->color = x->parent->color;
231                x->parent->color = TREE_BLACK;
232                w->left->color = TREE_BLACK;
233                rightRotate(x->parent);
234                x = setData;
235             }
236          }
237       }
238       x->color = TREE_BLACK;
239    }
240
241
242    // insertion to a binary search tree. It returns the new element pointer
243    // that is inserted. If element is already there it returns NULL
244    entry* treeInsert(Address key, T *value)
245    {
246       entry* y = NULL;
247       entry* x = setData;
248       while(x != nil){
249          y = x;
250          if (key < x->key) 
251             x = x->left;
252          else if(key > x->key)
253             x = x->right;
254          else
255             return NULL;
256       } 
257       entry* z = new entry(key, value, nil);
258       z->parent = y;
259       if(!y) {
260          setData = z;
261       }
262       else {
263          if (key < y->key)
264             y->left = z;
265          else if (key > y->key)
266             y->right = z;
267       }
268       setSize++;
269       return z;
270    }
271
272
273    // finds the elemnts in the tree that will be replaced with the element
274    // being deleted in the  deletion. That is the element with the largest
275    // smallest value than the element being deleted. 
276    entry* treeSuccessor(entry *x) const
277    {
278       if(!x || (x == nil))
279          return NULL;
280       if(x->right != nil){
281          entry* z = x->right;
282          while(z->left != nil) z = z->left;
283          return z;
284       }
285       entry* y = x->parent;
286       while(y && (x == y->right)){
287          x = y;
288          y = y->parent;
289       }
290       return y;
291    }
292
293    // method that returns the entry pointer for the element that is searched
294    //for. If the entry is not found then it retuns NULL
295    entry* find_internal(Address element) const
296    {
297       entry* x = setData;
298       while(x != nil){
299          if (element < x->key) {
300             x = x->left;
301          }
302          else if (element > x->key) {
303             x = x->right;
304          }
305          else
306             return x;
307       } 
308       return NULL;
309    }
310
311
312    // infix traverse of the RB tree. It traverses the tree in ascending order
313    void traverse(T **all, entry *node, int &n) const
314    {
315       if(node == nil)
316          return;
317       if(node->left != nil)
318          traverse(all,node->left,n);
319       if(all)
320          all[n++] = node->value;
321       if(node->right != nil)
322          traverse(all,node->right,n);
323    }
324
325
326    // Vector version of above
327    // infix traverse of the RB tree. It traverses the tree in ascending order
328    void traverse(pdvector<T *> &all, entry*node) const
329    {
330       if(node == nil)
331          return;
332       if(node->left != nil)
333          traverse(all,node->left);
334       all.push_back(node->value);
335       if(node->right != nil)
336          traverse(all,node->right);
337    }
338
339
340    // deletes the tree structure for deconstructor.
341    void destroy(entry *node)
342    {
343       if(!node || (node == nil))
344          return;
345       if(node->left != nil)
346          destroy(node->left);
347       if(node->right != nil)
348          destroy(node->right);
349       delete node;
350    }
351
352    /** copy constructor */
353    addrRangeTree(const addrRangeTree &/* y */) 
354    {
355    }
356
357    // Similar to precessor, but returns an entry
358    bool precessor_internal(Address key, entry * &value) const
359    {
360       entry *x = setData;
361       entry *last = nil;
362       while (x != nil) {
363          assert(x != NULL);
364          if (x->key == key) {
365             value = x;
366             return true;
367          }
368          else if (key < x->key) {
369             x = x->left;
370          }
371          else { // key > x->key
372             last = x;
373             x = x->right;
374          }
375       }
376       if (x == nil) {
377          // Ran out of tree to search... get the parent
378          assert(last != NULL);
379          if (last != nil) {
380             value = last;
381             return true;
382          }
383          else return false;
384       }
385       // Should never hit here
386       assert(0);
387       return false;
388    }
389
390
391    // Similar to successor, but returns an entry
392    bool successor_internal(Address key, entry * &value) const
393    {
394       entry *x = setData;
395       entry *last = nil;
396       while (x != nil) {
397          if (x->key == key) {
398             value = x;
399             return true;
400          }
401          else if (key > x->key) {
402             x = x->right;
403          }
404          else { // key < x->key
405             last = x;
406             x = x->left;
407          }
408       }
409       if (x == nil) {
410          // Ran out of tree to search... get the parent
411          if (last != nil) {
412             value = last;
413             return true;
414          }
415          else return false;
416       }
417       // Should never reach this point
418       assert(0);
419       return false;
420    }
421
422
423  public:
424
425    /** constructor. The default comparison structure is used */
426    addrRangeTree() : 
427       setSize(0) 
428    { 
429       nil = new entry;
430       setData = nil;
431    }
432     
433       /** destructor which deletes all tree structure and allocated entries */
434       virtual ~addrRangeTree()
435       {
436          destroy(setData);
437          delete nil;
438       }
439
440       /** returns the cardinality of the tree , number of elements */
441       int size() const 
442       { 
443          return setSize; 
444       }
445     
446       /** returns true if tree is empty */
447       bool empty() const 
448       { 
449          return (setData == nil); 
450       }
451
452       /** inserts the element in the tree 
453        * @param 1 element that will be inserted
454        */
455       void insert(T *value)
456       {
457          entry* x = treeInsert(value->get_address(), value);
458          if(!x) {
459             // We're done.
460             return;
461          }
462          x->color = TREE_RED;
463          while((x != setData) && (x->parent->color == TREE_RED)){
464             if(x->parent == x->parent->parent->left){
465                entry* y = x->parent->parent->right;
466                if(y->color == TREE_RED){
467                   x->parent->color = TREE_BLACK;
468                   y->color = TREE_BLACK;
469                   x->parent->parent->color = TREE_RED;
470                   x = x->parent->parent;
471                }
472                else{
473                   if(x == x->parent->right){
474                      x = x->parent;
475                      leftRotate(x);
476                   }
477                   x->parent->color = TREE_BLACK;
478                   x->parent->parent->color = TREE_RED;
479                   rightRotate(x->parent->parent);
480                }
481             }
482             else{
483                entry* y = x->parent->parent->left;
484                if(y->color == TREE_RED){
485                   x->parent->color = TREE_BLACK;
486                   y->color = TREE_BLACK;
487                   x->parent->parent->color = TREE_RED;
488                   x = x->parent->parent;
489                }
490                else{
491                   if(x == x->parent->left){
492                      x = x->parent;
493                      rightRotate(x);
494                   }
495                   x->parent->color = TREE_BLACK;
496                   x->parent->parent->color = TREE_RED;
497                   leftRotate(x->parent->parent);
498                }
499             }
500          }
501          setData->color = TREE_BLACK;
502       }
503
504       /** removes the element in the tree 
505        * @param 1 element that will be removed  
506        */
507       void remove(Address key)
508       {
509          entry* z = find_internal(key);
510          if(!z)
511             return;
512          if (z->key != key)
513             return;
514
515          entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
516          entry* x=(y->left != nil) ? y->left : y->right;
517          x->parent = y->parent;
518          if(!y->parent) {
519             setData = x;
520          }
521          else if(y == y->parent->left)
522             y->parent->left = x;
523          else
524             y->parent->right = x;
525          if(y != z) {
526             z->value = y->value;
527             z->key = y->key;
528          }
529          if(y->color == TREE_BLACK)
530             deleteFixup(x);
531          setSize--;
532          delete y;
533       }
534
535
536       /** returns true if the argument is member of the addrRangeTree
537        * @param e the element that will be searched for
538        */
539       virtual bool find(Address key, T *& value) const
540       {
541          value = NULL;
542          if (!precessor(key, value))
543             return false;
544          // Check to see if the range works
545          if (!value->get_size()) {
546             if(key > value->get_address())
547                return false;
548          }
549          else if(key >= (value->get_address() + value->get_size())) {
550             return false;
551          }
552          // We can also underflow
553          if (key < value->get_address())
554             return false;
555          return true;
556       }
557
558
559       /** Fills in the vector with all address ranges that overlap
560        * with the address range defined by (start, end]
561        */
562       virtual bool find(Address start, Address end, 
563                         std::vector<T *> &ranges) const
564       {
565          entry *cur;
566          bool result = precessor_internal(start, cur);
567          if (!result || cur == nil)
568             result = successor_internal(start, cur);
569          if (!result || cur == nil)
570             return false;
571          assert(cur);
572    
573          if (cur->key + cur->value->get_size() < start)
574             cur = treeSuccessor(cur);
575          while (cur != NULL && cur != nil && cur->key < end)
576          {
577             ranges.push_back(cur->value);
578             cur = treeSuccessor(cur);
579          }
580    
581          return (ranges.size() != 0);
582       }
583
584
585       /** Returns the largest value less than or equal to the
586        * key given
587        */
588       virtual bool precessor(Address key, T *& value) const
589       {
590          entry *val;
591          bool result = precessor_internal(key, val);
592          if (!result)
593             return false;
594          value = val->value;
595          return true;
596       }
597
598
599       /** Returns the smallest value greater than or equal to the
600        * key given
601        */
602       virtual bool successor(Address key, T *& value) const
603       {
604          entry *val;
605          bool result = successor_internal(key, val);
606          if (!result)
607             return false;
608          value = val->value;
609          return true;
610       }
611
612       /** fill an buffer array with the sorted
613        * elements of the addrRangeTree in ascending order according to comparison function
614        * if the addrRangeTree is empty it retuns NULL, other wise it returns 
615        * the input argument.
616        */
617       T ** elements(T ** buffer) const
618       {
619          if(setData == nil) return NULL;
620          if(!buffer) return NULL;
621          int tmp = 0;
622          traverse(buffer,setData,tmp);  
623          return buffer;
624       }
625
626
627       // And vector-style
628       bool elements(pdvector<T *> &buffer) const
629       {
630          if(setData == nil) return false;
631          traverse(buffer,setData);      
632          return true;
633       }
634
635       // Remove all entries in the tree
636       void clear()
637       {
638          if (setData == nil) return;
639          destroy(setData);
640          setData = nil;
641          setSize = 0;
642       }
643
644 };
645
646 #endif /* _addrRange_h_ */
647