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