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