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