Compilation fixes for gcc 3.1, MSVC 6.0 & 7.0
[dyninst.git] / dyninstAPI / h / BPatch_Set.h
1 #ifndef _BPatch_Set_h_
2 #define _BPatch_Set_h_
3
4 //ifdef this to nothing if it bothers old broken compilers
5 #define TYPENAME typename
6
7 #if defined(external_templates)
8 #pragma interface
9 #endif
10
11 /*******************************************************/
12 /*              header files                           */
13 /*******************************************************/
14
15 #include <assert.h>
16 #include <stdlib.h>
17 #include "BPatch_dll.h"
18
19 #if !defined(DO_INLINE_P)
20 #define DO_INLINE_P
21 #endif
22
23 #if !defined(DO_INLINE_F)
24 #define DO_INLINE_F
25 #endif
26
27 /** template struct that will be used for default compare 
28   * class for BPatch_Set operations.
29   */
30
31 // VG: shouldn't this be a dll export?
32 template<class T>
33 struct comparison {
34         /** default comparison operator
35           * returns -1 if the first arg < second arg
36           * returns 1 if the first arg > second arg
37           * returns 0 if the first arg == second arg
38           * @param x first argument to be compared 
39           * @param y second argument to be compared
40           */
41         int operator()(const T& x, const T& y) const {
42                 if(x<y) return -1;
43                 if(x>y) return 1;
44                 return 0;
45         }
46 };
47
48 /** template class for BPatch_Set. The implementation is based on red black
49   * tree implementation for efficiency concerns and for getting sorted
50   * elements easier. The template depends on two types. The first one is the
51   * the type of the elements in the BPatch_Set and the second one is the template
52   * structure that is used to compare the elements of the BPatch_Set. The template
53   * structure has to overload () for comparison of two elements as explained above
54   */
55
56 #if defined i386_unknown_nt4_0 || defined mips_unknown_ce2_11 //ccw 6 apr 2001
57
58 static const bool RED = true;
59 static const bool BLACK = false;
60
61 #endif
62
63 template<class T,class Compare = comparison<T> >
64 class BPATCH_DLL_EXPORT BPatch_Set {
65 private:
66
67 #if ! (defined i386_unknown_nt4_0 || defined mips_unknown_ce2_11) //ccw 6 apr 2001
68         /** color variable used for red-black tree */
69         static const bool RED = true;
70
71         /** color variable used for red-black tree */
72         static const bool BLACK = false;
73 #endif
74
75         /** tree implementation structure. Used to implement the RB tree */
76         typedef struct entry {
77                 T data;         /* data  element */
78                 bool color;     /* color of the node true=red,false=blue*/
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(BLACK),left(NULL),right(NULL),parent(NULL) {}
86
87                 /** constructor used for non-nil elements 
88                   * @param e nil entry
89                   */      
90                 entry(entry* e) //constructor with nil entry 
91                         : color(RED),left(e),right(e),parent(NULL) {}
92
93                 /** constructor
94                   * @param d data element
95                   * @param e nill entry 
96                   */
97                 entry(const T& d,entry* e) 
98                         : data(d),color(RED),left(e),right(e),parent(NULL){}
99
100                 /** constrcutor 
101                   * @param e the entry structure that will be copied 
102                   */
103                 entry(const entry& e) : data(e.data),color(e.color),
104                         left(NULL),right(NULL),parent(NULL) {}
105         } entry;
106
107         /** pointer to define the nil element of the tree NULL is not used
108           * since some operations need sentinel nil which may have non-nil
109           * parent.
110           */
111         entry* nil;
112
113         /** size of the BPatch_Set */
114         int setSize;
115         
116         /** pointer to the tree structure */
117         entry* setData;
118
119         /** the structure that will be used for comparisons. Default is the
120           * the comparsion structure explained above */
121         Compare compareFunc;
122
123         // method that replicates the tree structure of this tree
124         DO_INLINE_P entry* replicateTree(entry*,entry*,entry*,entry*);
125
126         // method that implements left rotattion used by RB tree for balanced
127         // tree construction and keeps the RBtree properties.
128         DO_INLINE_P void leftRotate(entry*);
129
130         // method that implements right rotattion used by RB tree for balanced
131         // tree construction and keeps the RBtree properties.
132         DO_INLINE_P void rightRotate(entry*);
133
134         // method that modifies the tree structure after deletion for keeping
135         // the RBtree properties.
136         DO_INLINE_P void deleteFixup(entry*);
137
138         // insertion to a binary search tree. It returns the new element pointer
139         // that is inserted. If element is already there it returns NULL
140         DO_INLINE_P entry* treeInsert(const T&);
141
142         // finds the elemnts in the tree that will be replaced with the element
143         // being deleted in the  deletion. That is the element with the largets
144         // smallest value than the element being deleted. 
145         DO_INLINE_P entry* treeSuccessor(entry* ) const;
146
147         // method that returns the entry pointer for the element that is searched
148         //for. If the entry is not found then it retuns NULL
149         DO_INLINE_P entry* find(const T&) const;
150
151         // infix traverse of the RB tree. It traverses the tree in ascending order
152         DO_INLINE_P void traverse(T*,entry*,int&) const;
153
154         // deletes the tree structure for deconstructor.
155         DO_INLINE_P void destroy(entry*);
156
157 public:
158
159         /** constructor. The default comparison structure is used */
160         DO_INLINE_F BPatch_Set() : setSize(0) 
161         { 
162                 nil = new entry;
163                 setData = nil;
164                 compareFunc = Compare();
165         }
166
167         /** copy constructor.
168           * @param newBPatch_Set the BPatch_Set which will be copied
169           */
170         DO_INLINE_F BPatch_Set(const BPatch_Set<T,Compare>& newBPatch_Set){
171                 nil = new entry;
172                 compareFunc = newBPatch_Set.compareFunc;
173                 setSize = newBPatch_Set.setSize;
174                 setData = replicateTree(newBPatch_Set.setData,NULL,newBPatch_Set.nil,nil);
175         } 
176
177         /** destructor which deletes all tree structure and allocated entries */
178         DO_INLINE_F ~BPatch_Set() 
179         {
180                 destroy(setData);
181                 delete nil;
182         }
183
184         /** returns the cardinality of the tree , number of elements */
185         DO_INLINE_F int size() const { return setSize; }
186
187         /** returns true if tree is empty */
188         DO_INLINE_F bool empty() const { return (setData == nil); }
189
190         /** inserts the element in the tree 
191           * @param 1 element that will be inserted
192           */
193         DO_INLINE_F void insert(const T&);
194
195         /** removes the element in the tree 
196           * @param 1 element that will be removed  
197           */
198         DO_INLINE_F void remove(const T&);
199
200         /** returns true if the argument is member of the BPatch_Set
201           * @param e the element that will be searched for
202           */
203         DO_INLINE_F bool contains(const T&) const;
204
205         /** fill an buffer array with the sorted
206           * elements of the BPatch_Set in ascending order according to comparison function
207           * if the BPatch_Set is empty it retuns NULL, other wise it returns 
208           * the input argument.
209           */
210         DO_INLINE_F T* elements(T*) const;
211
212         /** returns the minimum valued member in the BPatch_Set according to the 
213           * comparison function supplied. If the BPatch_Set is empty it retuns 
214           * any number. Not safe to use for empty sets 
215           */
216         DO_INLINE_F T minimum() const;
217
218         /** returns the maximum valued member in the BPatch_Set according to the 
219           * comparison function supplied. If the BPatch_Set is empty it retuns 
220           * any number. Not safe to use for empty sets 
221           */
222         DO_INLINE_F T maximum() const;
223         
224         /** assignment operator for BPatch_Set. It replicate sthe tree 
225           * structure into the new BPatch_Set.
226           * @param 1 BPatch_Set that will be used in assignment
227           */
228         DO_INLINE_F BPatch_Set<T,Compare>& operator= (const BPatch_Set<T,Compare>&);
229
230         /** equality comparison for the BPatch_Set
231           * @param 1 BPatch_Set that will be used equality check
232           */
233         DO_INLINE_F bool operator== (const BPatch_Set<T,Compare>&) const;
234
235         /** inequality comparison for the BPatch_Set
236           * @param 1 BPatch_Set that will be used inequality check
237           */
238         DO_INLINE_F bool operator!= (const BPatch_Set<T,Compare>&) const;
239
240         /** insertion in to the BPatch_Set 
241           * @param 1 element that will be inserted 
242           */
243         DO_INLINE_F BPatch_Set<T,Compare>& operator+= (const T&);
244
245         /** union operation with this BPatch_Set 
246           * @param 1 BPatch_Set that will be used in union operation
247           */
248         DO_INLINE_F BPatch_Set<T,Compare>& operator|= (const BPatch_Set<T,Compare>&);
249
250         /** intersection operation with this BPatch_Set 
251           * @param 1 BPatch_Set that will be used in intersection operation
252           */
253         DO_INLINE_F BPatch_Set<T,Compare>& operator&= (const BPatch_Set<T,Compare>&);
254
255         /** difference operation with this BPatch_Set 
256           * @param 1 BPatch_Set that will be used in difference operation
257           */
258         DO_INLINE_F BPatch_Set<T,Compare>& operator-= (const BPatch_Set<T,Compare>&);
259
260         /** union operation 
261           * @param 1 BPatch_Set that will be used in union operation
262           */
263         DO_INLINE_F BPatch_Set<T,Compare> operator| (const BPatch_Set<T,Compare>&) const;
264
265         /** intersection operation 
266           * @param 1 BPatch_Set that will be used in intersection operation
267           */
268         DO_INLINE_F BPatch_Set<T,Compare> operator& (const BPatch_Set<T,Compare>&) const;
269
270         /** difference operation 
271           * @param 1 BPatch_Set that will be used in difference operation
272           */
273         DO_INLINE_F BPatch_Set<T,Compare> operator- (const BPatch_Set<T,Compare>&) const;
274
275         /** removes the element in the root of the tree 
276           * if the BPatch_Set is empty it return false
277           * @param e refernce to the element that the value of removed
278           * element will be copied.
279           */
280         DO_INLINE_F bool extract(T&);
281
282 };
283
284 // VG(06/15/02): VC.NET doesn't like definitions for dll imports
285 #ifndef BPATCH_DLL_IMPORT
286
287 template <class T,class Compare>
288 DO_INLINE_P
289 TYPENAME BPatch_Set<T,Compare>::entry*
290 BPatch_Set<T,Compare>::replicateTree(entry* node,entry* parent,
291                                      entry* oldNil,entry* newNil)
292 {
293         if(node == oldNil)
294                 return newNil;  
295
296         entry* newNode = new entry(*node);
297         newNode->parent = parent; 
298         newNode->left = replicateTree(node->left,newNode,oldNil,newNil);
299         newNode->right = replicateTree(node->right,newNode,oldNil,newNil);
300         return newNode; 
301 }
302
303 template <class T,class Compare>
304 DO_INLINE_P
305 void BPatch_Set<T,Compare>::destroy(entry* node){
306         if(!node || (node == nil))
307                 return;
308         if(node->left != nil)
309                 destroy(node->left);
310         if(node->right != nil)
311                 destroy(node->right);
312         delete node;
313 }
314         
315 template <class T,class Compare>
316 DO_INLINE_P
317 void BPatch_Set<T,Compare>::traverse(T* all,entry* node,int& n) const{
318         if(node == nil)
319                 return;
320         if(node->left != nil)
321                 traverse(all,node->left,n);
322         if(all)
323                 all[n++] = node->data;
324         if(node->right != nil)
325                 traverse(all,node->right,n);
326 }
327 template <class T,class Compare>
328 DO_INLINE_F T BPatch_Set<T,Compare>::minimum() const{
329         if(setData == nil)
330                 return nil->data;
331         entry* node = setData;
332         while(node->left != nil)
333                 node = node->left;
334         return node->data;
335 }
336
337 template <class T,class Compare>
338 DO_INLINE_F T BPatch_Set<T,Compare>::maximum() const{
339         if(setData == nil)
340                 return nil->data;
341         entry* node = setData;
342         while(node->right != nil)
343                 node = node->right;
344         return node->data;
345 }
346 template <class T,class Compare>
347 DO_INLINE_F T* BPatch_Set<T,Compare>::elements(T* buffer) const{
348         if(setData == nil) return NULL;
349         if(!buffer) return NULL;
350         int tmp = 0;
351         traverse(buffer,setData,tmp);   
352         return buffer;
353 }
354 template <class T,class Compare>
355 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator= (const BPatch_Set<T,Compare>& newBPatch_Set){
356         if(this == &newBPatch_Set)
357                 return *this;
358         destroy(setData);
359         compareFunc = newBPatch_Set.compareFunc;
360         setSize = newBPatch_Set.setSize;
361         nil->parent = NULL;
362         setData = replicateTree(newBPatch_Set.setData,NULL,newBPatch_Set.nil,nil);
363         return *this;
364 }
365 template <class T,class Compare>
366 DO_INLINE_F bool BPatch_Set<T,Compare>::operator== (const BPatch_Set<T,Compare>& newBPatch_Set) const{
367         int i;
368         if(this == &newBPatch_Set)
369                 return true;
370         T* all = new T[newBPatch_Set.size()];
371         newBPatch_Set.elements(all);
372         for(i=0;i<newBPatch_Set.size();i++)
373                 if(!contains(all[i]))
374                         return false;
375         delete[] all;
376         all = new T[setSize];
377         elements(all);
378         for(i=0;i<setSize;i++)
379                 if(!newBPatch_Set.contains(all[i]))
380                         return false;
381         delete[] all;
382         return true;
383 }
384 template <class T,class Compare>
385 DO_INLINE_F bool BPatch_Set<T,Compare>::operator!= (const BPatch_Set<T,Compare>& newBPatch_Set) const{
386         return !(*this == newBPatch_Set);
387 }
388 template <class T,class Compare>
389 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator+= (const T& element){
390         insert(element);
391         return *this;
392 }
393 template <class T,class Compare>
394 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator|= (const BPatch_Set<T,Compare>& newBPatch_Set){
395         if(this == &newBPatch_Set)
396                 return *this;
397         T* all = new T[newBPatch_Set.size()];
398         newBPatch_Set.elements(all);
399         for(int i=0;i<newBPatch_Set.size();i++)
400                 insert(all[i]); 
401         delete[] all;
402         return *this;
403
404 template <class T,class Compare>
405 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator&= (const BPatch_Set<T,Compare>& newBPatch_Set){
406         if(this == &newBPatch_Set)
407                 return *this;
408         T* all = new T[setSize];
409         elements(all);
410         int s = setSize;
411         for(int i=0;i<s;i++)
412                 if(!newBPatch_Set.contains(all[i]))
413                         remove(all[i]);
414         delete[] all;
415         return *this;
416 }
417 template <class T,class Compare>
418 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator-= (const BPatch_Set<T,Compare>& newBPatch_Set){
419         T* all = new T[setSize];
420         elements(all);
421         int s = setSize;
422         for(int i=0;i<s;i++)
423                 if(newBPatch_Set.contains(all[i]))
424                         remove(all[i]);
425         delete[] all;
426         return *this;
427 }
428 template <class T,class Compare>
429 DO_INLINE_F BPatch_Set<T,Compare> BPatch_Set<T,Compare>::operator| (const BPatch_Set<T,Compare>& newBPatch_Set) const{
430         BPatch_Set<T,Compare> ret;
431         ret |= newBPatch_Set;
432         ret |= *this;
433         return ret;
434 }
435 template <class T,class Compare>
436 DO_INLINE_F BPatch_Set<T,Compare> BPatch_Set<T,Compare>::operator& (const BPatch_Set<T,Compare>& newBPatch_Set) const{
437         BPatch_Set<T,Compare> ret;
438         ret |= newBPatch_Set;
439         ret &= *this;
440         return ret;
441 }
442 template <class T,class Compare>
443 DO_INLINE_F BPatch_Set<T,Compare> BPatch_Set<T,Compare>::operator- (const BPatch_Set<T,Compare>& newBPatch_Set) const{
444         BPatch_Set<T,Compare> ret;
445         ret |= *this;
446         ret -= newBPatch_Set;
447         return ret;
448 }
449
450 template <class T,class Compare>
451 DO_INLINE_P
452 void BPatch_Set<T,Compare>::leftRotate(entry* pivot){
453         if(!pivot || (pivot == nil))
454                 return;
455         entry* y = pivot->right;
456         if(y == nil)
457                 return;
458         pivot->right = y->left;
459         if(y->left != nil)
460                 y->left->parent = pivot;
461         y->parent = pivot->parent;
462         if(!pivot->parent)
463                 setData = y;
464         else if(pivot == pivot->parent->left)
465                 pivot->parent->left = y;
466         else
467                 pivot->parent->right = y;
468         y->left = pivot;
469         pivot->parent = y;
470 }
471 template <class T,class Compare>
472 DO_INLINE_P
473 void BPatch_Set<T,Compare>::rightRotate(entry* pivot){
474         if(!pivot || (pivot == nil))
475                 return;
476         entry* x = pivot->left;
477         if(x == nil)
478                 return;
479         pivot->left = x->right;
480         if(x->right != nil)
481                 x->right->parent = pivot;
482         x->parent = pivot->parent;
483         if(!pivot->parent)
484                 setData = x;
485         else if(pivot == pivot->parent->left)
486                 pivot->parent->left = x;
487         else
488                 pivot->parent->right = x;
489         x->right = pivot;
490         pivot->parent = x;
491 }
492
493 template <class T,class Compare>
494 DO_INLINE_P
495 TYPENAME BPatch_Set<T,Compare>::entry*
496 BPatch_Set<T,Compare>::find(const T& element) const{
497         entry* x = setData;
498         while(x != nil){
499                 int check = compareFunc(element,x->data);
500                 if(check < 0)
501                         x = x->left;
502                 else if(check > 0)
503                         x = x->right;
504                 else
505                         return x;
506         }       
507         return NULL;
508 }
509 template <class T,class Compare>
510 DO_INLINE_F bool BPatch_Set<T,Compare>::contains(const T& element) const{
511         entry* x = setData;
512         while(x != nil){
513                 int check = compareFunc(element,x->data);
514                 if(check < 0)
515                         x = x->left;
516                 else if(check > 0)
517                         x = x->right;
518                 else
519                         return true;
520         }       
521         return false;
522 }
523 /** return pointer if the node is inserted, returns NULL if thevalue is 
524   * already there
525   */
526 template <class T,class Compare>
527 DO_INLINE_P
528 TYPENAME BPatch_Set<T,Compare>::entry*
529 BPatch_Set<T,Compare>::treeInsert(const T& element){
530         entry* y = NULL;
531         entry* x = setData;
532         while(x != nil){
533                 y = x;
534                 int check = compareFunc(element,x->data);
535                 if(check < 0)
536                         x = x->left;
537                 else if(check > 0)
538                         x = x->right;
539                 else
540                         return NULL;
541         }       
542         entry* z = new entry(element,nil);
543         z->parent = y;
544         if(!y)
545                 setData = z;
546         else {
547                 int check = compareFunc(element,y->data);
548                 if(check < 0)
549                         y->left = z;
550                 else if(check > 0)
551                         y->right = z;
552         }
553         setSize++;
554         return z;
555 }
556 /** finds the minimum value node when x is being deleted */
557 template <class T,class Compare>
558 DO_INLINE_P
559 TYPENAME BPatch_Set<T,Compare>::entry*
560 BPatch_Set<T,Compare>::treeSuccessor(entry* x) const{
561         if(!x || (x == nil))
562                 return NULL;
563         if(x->right != nil){
564                 entry* z = x->right;
565                 while(z->left != nil) z = z->left;
566                 return z;
567         }
568         entry* y = x->parent;
569         while(y && (x == y->right)){
570                 x = y;
571                 y = y->parent;
572         }
573         return y;
574 }
575 template <class T,class Compare>
576 DO_INLINE_P
577 void BPatch_Set<T,Compare>::deleteFixup(entry* x){
578         while((x != setData) && 
579               (x->color == BLACK))
580         {
581                 if(x == x->parent->left){
582                         entry* w = x->parent->right;
583                         if(w->color == RED){
584                                 w->color = BLACK;
585                                 x->parent->color = RED;
586                                 leftRotate(x->parent);
587                                 w = x->parent->right;
588                         }
589                         if((w->left->color == BLACK) &&
590                            (w->right->color == BLACK)){
591                                 w->color = RED;
592                                 x = x->parent;
593                         }
594                         else{
595                                 if(w->right->color == BLACK){
596                                         w->left->color = BLACK;
597                                         w->color = RED;
598                                         rightRotate(w);
599                                         w = x->parent->right;
600                                 }
601                                 w->color = x->parent->color;
602                                 x->parent->color = BLACK;
603                                 w->right->color = BLACK;
604                                 leftRotate(x->parent);
605                                 x = setData;
606                         }
607                 }
608                 else{
609                         entry* w = x->parent->left;
610                         if(w->color == RED){
611                                 w->color = BLACK;
612                                 x->parent->color = RED;
613                                 rightRotate(x->parent);
614                                 w = x->parent->left;
615                         }
616                         if((w->right->color == BLACK) &&
617                            (w->left->color == BLACK)){
618                                 w->color = RED;
619                                 x = x->parent;
620                         }
621                         else{
622                                 if(w->left->color == BLACK){
623                                         w->right->color = BLACK;
624                                         w->color = RED;
625                                         leftRotate(w);
626                                         w = x->parent->left;
627                                 }
628                                 w->color = x->parent->color;
629                                 x->parent->color = BLACK;
630                                 w->left->color = BLACK;
631                                 rightRotate(x->parent);
632                                 x = setData;
633                         }
634                 }
635         }
636         x->color = BLACK;
637 }
638
639 template <class T,class Compare>
640 DO_INLINE_F void BPatch_Set<T,Compare>::insert(const T& element){
641         entry* x = treeInsert(element);
642         if(!x) return;
643         x->color = RED;
644         while((x != setData) && (x->parent->color == RED)){
645                 if(x->parent == x->parent->parent->left){
646                         entry* y = x->parent->parent->right;
647                         if(y->color == RED){
648                                 x->parent->color = BLACK;
649                                 y->color = BLACK;
650                                 x->parent->parent->color = RED;
651                                 x = x->parent->parent;
652                         }
653                         else{
654                                 if(x == x->parent->right){
655                                         x = x->parent;
656                                         leftRotate(x);
657                                 }
658                                 x->parent->color = BLACK;
659                                 x->parent->parent->color = RED;
660                                 rightRotate(x->parent->parent);
661                         }
662                 }
663                 else{
664                         entry* y = x->parent->parent->left;
665                         if(y->color == RED){
666                                 x->parent->color = BLACK;
667                                 y->color = BLACK;
668                                 x->parent->parent->color = RED;
669                                 x = x->parent->parent;
670                         }
671                         else{
672                                 if(x == x->parent->left){
673                                         x = x->parent;
674                                         rightRotate(x);
675                                 }
676                                 x->parent->color = BLACK;
677                                 x->parent->parent->color = RED;
678                                 leftRotate(x->parent->parent);
679                         }
680                 }
681         }
682         setData->color = BLACK;
683 }
684 template <class T,class Compare>
685 DO_INLINE_F void BPatch_Set<T,Compare>::remove(const T& element){
686         entry* z = find(element);
687         if(!z)
688                 return;
689         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
690         entry* x=(y->left != nil) ? y->left : y->right;
691         x->parent = y->parent;
692         if(!y->parent)
693                 setData = x;
694         else if(y == y->parent->left)
695                 y->parent->left = x;
696         else
697                 y->parent->right = x;
698         if(y != z)
699                 z->data = y->data;
700         if(y->color == BLACK)
701                 deleteFixup(x);
702         setSize--;
703         delete y;
704 }
705 template <class T,class Compare>
706 DO_INLINE_F 
707 bool BPatch_Set<T,Compare>::extract(T& element){
708         element = setData->data;
709         if(setData == nil)
710                 return false;
711         remove(element);
712         return true;
713 }
714
715 #endif /* BPATCH_DLL_IMPORT */
716 #endif /* _BPatch_Set_h_ */
717