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