Update copyright to LGPL on all files
[dyninst.git] / common / h / IBSTree.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // $Id$
33
34 #ifndef _IBSTree_h_
35 #define _IBSTree_h_
36
37 /*******************************************************/
38 /*              header files                           */
39 /*******************************************************/
40
41 #include <assert.h>
42 #include <stdlib.h>
43 #include "common/h/Types.h"
44 #include "common/h/Vector.h"
45 #include "common/h/std_namesp.h"
46 #include "stats.h"
47
48 #include <set>
49 #include <limits.h>
50
51 using namespace std;
52
53 /** Templape class for Interval Binary Search Tree. The implementation is
54   * based on a red-black tree (derived from our codeRange implementation)
55   * to control the tree height and thus insertion and search cost.
56   *
57   * Unlike our codeRangeTree, this data structure can represent overlapping
58   * intervals. It is useful for executing stabbing queries and more
59   * generally for finding invervals that overlap a particular interval.
60   * A stabbing query requires O(log(N) + L) time in the worst case, where
61   * L is the number of overlapping intervals, and insertion requires
62   * O(log^2(N)) time (compare to O(log(N)) for a standard RB-tree).
63   *
64   * This class requires a worst case storage O(N log(N))
65   *
66   * For more information:
67   *
68   * @TECHREPORT{Hanson90theibs-tree:,
69   *     author = {Eric N. Hanson and Moez Chaabouni},
70   *     title = {The IBS-tree: A data structure for finding all intervals that overlap a point},
71   *     institution = {},
72   *     year = {1990}
73   * }
74   **/
75
76 /** EXTREMELY IMPORTANT XXX: Assuming that all intervals have lower bound
77     predicate <= and upper bound predicate > ; that is, intervals are 
78     (a,b] **/
79
80 typedef enum { TREE_RED, TREE_BLACK } color_t;
81
82 class interval {
83   public:
84     interval() { }
85     virtual ~interval() { }
86
87     virtual int low() const = 0;
88     virtual int high() const = 0;
89 };
90
91 class SimpleInterval : interval {
92   public:
93     SimpleInterval( interval & i, void * id ) {
94         low_ = i.low();
95         high_ = i.high();
96         id_ = id;
97     }
98     SimpleInterval(int low, int high, void * id) {
99         low_ = low;
100         high_ = high;
101         id_ = id;
102     }
103         
104   private:
105     int low_;
106     int high_;
107     void * id_; // some arbitrary unique identifier
108 };
109
110 template<class ITYPE>
111 class IBSTree;
112
113 template<class ITYPE = interval>
114 class IBSNode {
115     friend class IBSTree<ITYPE>;
116   public:
117     IBSNode() : 
118         color(TREE_BLACK),
119         left(NULL),
120         right(NULL),
121         parent(NULL) { }
122
123     /** constructor for non-nil elements **/
124     IBSNode(int value, IBSNode *n) :
125         val_(value),
126         left(n),
127         right(n),
128         parent(NULL) { }
129
130     ~IBSNode() { }
131
132     int value() const { return val_; };
133
134   private: 
135     /* The endpoint of an interval range */
136     int val_;
137
138     /* Intervals indexed by this node */
139     set<ITYPE *> less;
140     set<ITYPE *> greater;
141     set<ITYPE *> equal;
142
143     color_t color;
144
145     IBSNode<ITYPE> *left;
146     IBSNode<ITYPE> *right;
147     IBSNode<ITYPE> *parent;
148 };
149
150 template<class ITYPE = interval>
151 class IBSTree {
152
153     IBSNode<ITYPE> *nil;
154
155     /** size of tree **/
156     int treeSize;
157
158     /** pointer to the tree root **/
159     IBSNode<ITYPE> *root;
160
161     /** RB-tree left rotation with modification to enforce IBS invariants **/
162     void leftRotate(IBSNode<ITYPE> *);
163
164     /** RB-tree right rotation with modification to enforce IBS invariants **/
165     void rightRotate(IBSNode<ITYPE> *);
166
167     /** Node deletion **/
168     void deleteFixup(IBSNode<ITYPE> *);
169
170     void removeInterval(IBSNode<ITYPE> *R, ITYPE *range);
171
172     /** Insertion operations: insert the left or right endpoint of
173         an interval into the tree (may or may not add a node **/
174     IBSNode<ITYPE>* addLeft(ITYPE *I, IBSNode<ITYPE> *R, IBSNode<ITYPE> *parent);
175     IBSNode<ITYPE>* addRight(ITYPE *I, IBSNode<ITYPE> *R, IBSNode<ITYPE> *parent);
176
177     /** Find the lowest valued ancestor of node R that has R in its
178         left subtree -- used in addLeft to determine whether all of
179         the values in R's right subtree are covered by an interval **/
180     int rightUp(IBSNode<ITYPE> *R);
181     int rightUpAux(IBSNode<ITYPE> *parent, IBSNode<ITYPE> *child, int cur);
182
183     /** Symmetric to rightUp **/
184     int leftUp(IBSNode<ITYPE> *R);
185     int leftUpAux(IBSNode<ITYPE> *parent, IBSNode<ITYPE> *child, int cur);
186
187     /** Tree-balancing algorithm on insertion **/
188     void insertFixup(IBSNode<ITYPE> *x);
189
190     /** Finds the precessor of the node; this node will have its value
191         copied to the target node of a deletion and will itself be deleted **/
192     //IBSNode* treePredecessor(IBSNode *);
193
194     /** Find a node with the provided value (interval endpoint) **/
195     //IBSNode* findNode(int) const;
196
197     /** Delete all nodes in the subtree rooted at the parameter **/
198     void destroy(IBSNode<ITYPE> *);
199
200     void findIntervals(int X, IBSNode<ITYPE> *R, set<ITYPE *> &S) const;
201     void findIntervals(ITYPE *I, IBSNode<ITYPE> *R, set<ITYPE *> &S) const;
202
203     void PrintPreorder(IBSNode<ITYPE> *n);
204
205     int height(IBSNode<ITYPE> *n);
206     int CountMarks(IBSNode<ITYPE> *R) const;
207
208     const unsigned MemUse() const;
209
210   public:
211
212     /** public for debugging purposes **/
213     StatContainer stats_;
214
215     IBSTree() : treeSize(0) {
216         nil = new IBSNode<ITYPE>;
217         root = nil;
218         stats_.add("insert",TimerStat);
219         stats_.add("remove",TimerStat);
220     }     
221
222     ~IBSTree() {
223         destroy(root);
224         delete nil;
225     }
226
227     int size() const { return treeSize; }
228     int CountMarks() const;
229     
230     bool empty() const { return (root == nil); }
231
232     void insert(ITYPE *);
233
234     void remove(ITYPE *);
235
236     /** Find all intervals that overlap the provided point. Returns
237         the number of intervals found **/  
238     int find(int, set<ITYPE *> &) const;
239     int find(ITYPE *I, set<ITYPE *> &) const;
240
241     /** Delete all entries in the tree **/
242     void clear();
243
244     void PrintPreorder() { PrintPreorder(root); }
245 };
246
247 // XXX XXX HOW I HATE YOU GCC! XXX XXX
248
249 template<class ITYPE>
250 void IBSTree<ITYPE>::rightRotate(IBSNode<ITYPE> *pivot)
251 {
252     if(!pivot || (pivot == nil))
253         return;
254
255     IBSNode<ITYPE> *y = pivot->left;
256     if(y == nil)
257         return;
258     pivot->left = y->right;
259     if(y->right != nil)
260         y->right->parent = pivot;
261     y->parent = pivot->parent;
262     if(!pivot->parent) {
263         root = y;
264     }
265     else if(pivot == pivot->parent->left)
266         pivot->parent->left = y;
267     else
268         pivot->parent->right = y;
269     y->right = pivot;
270     pivot->parent = y;
271
272     /* Maintain the IBS annotation invariants */
273     
274     // 1. Copy all marks from the < slot of the pivot (old subtree root)
275     //    to the < and = slots of y (new subtree root). Maintains containment.
276     y->less.insert(pivot->less.begin(), pivot->less.end());
277     y->equal.insert(pivot->less.begin(), pivot->less.end());
278
279     // 2. For each mark in y's > slot, if it was not in pivot's >,
280     //    *move* it to pivot's <. Maintains containment and maximality,
281     //    because it ensures that nodes under y->right covered by
282     //    the mark before rotation are now (which are now under pivot->left)
283     //    are still covered by the mark (if y > can't cover them still)
284     
285     // 3. Simultaneously, if the mark in in y's > slot AND pivot's > slot 
286     //    (before rotation), remove the mark from pivot's > and = slots
287     //    (preserving maximality).
288
289     typename set< ITYPE * >::iterator it = y->greater.begin();
290     while( it != y->greater.end() )
291     {
292         ITYPE *tmp = *it;
293     
294         typename set< ITYPE *>::iterator pit = pivot->greater.find( tmp );
295         if(pit == pivot->greater.end()) {
296             // Case 2
297             pivot->less.insert( tmp );
298             // remove from y's >. This invalidates the iterator, so
299             // update first
300             typename set< ITYPE * >::iterator del = it;
301             ++it;
302             y->greater.erase( del );
303         } else {
304             // Case 3
305             // remove from pivot's >
306             pivot->greater.erase( pit );
307             pit = pivot->equal.find( tmp );
308             if(pit != pivot->equal.end())
309                 pivot->equal.erase( pit );
310     
311             ++it;
312         }
313     }
314 }
315
316 template<class ITYPE>
317 void IBSTree<ITYPE>::leftRotate(IBSNode<ITYPE> *pivot)
318 {
319     if(!pivot || (pivot == nil))
320         return;
321
322     IBSNode<ITYPE> *y = pivot->right;
323
324     if(y == nil)
325         return;
326
327     pivot->right = y->left;
328     if(y->left != nil)
329         y->left->parent = pivot;
330     y->parent = pivot->parent;
331     if(!pivot->parent) {
332         root = y;
333     }
334     else if(pivot == pivot->parent->left)
335         pivot->parent->left = y;
336     else
337         pivot->parent->right = y;
338     y->left = pivot;
339     pivot->parent = y;
340
341     /* Fix up the IBS annotations. These are exactly opposeite of the
342        rules for right rotation */
343     
344     y->greater.insert(pivot->greater.begin(),pivot->greater.end());
345     y->equal.insert(pivot->greater.begin(),pivot->greater.end());
346
347     typename set< ITYPE * >::iterator it = y->less.begin();
348     while( it != y->less.end() )
349     {
350         ITYPE *tmp = *it;
351     
352         typename set< ITYPE *>::iterator pit = pivot->less.find( tmp );
353         if(pit == pivot->less.end()) {
354             // Case 2
355             pivot->greater.insert( tmp );
356             // remove from y's <. This invalidates the iterator, so
357             // update first
358             typename set< ITYPE * >::iterator del = it;
359             ++it;
360             y->less.erase( del );
361         } else {
362             // Case 3
363             // remove from pivot's < and =
364             pivot->less.erase( pit );
365             pit = pivot->equal.find( tmp );
366             if(pit != pivot->equal.end())
367                 pivot->equal.erase( pit );
368     
369             ++it;
370         }
371     }
372 }
373
374 template<class ITYPE>
375 IBSNode<ITYPE>* 
376 IBSTree<ITYPE>::addLeft(ITYPE *I, IBSNode<ITYPE> *R, IBSNode<ITYPE> *parent)
377 {
378     bool created = false;
379     if(R == nil) {
380         // create a new node
381         IBSNode<ITYPE> *tmp = new IBSNode<ITYPE>( I->low(), nil );
382         treeSize++;
383         created = true;
384        
385         if(parent == NULL)  // must be the root
386         {
387             root = tmp;
388         } 
389         else {
390             tmp->parent = parent;
391             if(tmp->value() < parent->value()) {
392                 parent->left = tmp;
393             } else if(tmp->value() > parent->value()) {
394                 parent->right = tmp;
395             } else {
396                 assert(0); // can't get here
397             }
398         }
399
400         R = tmp;
401     }
402
403     if(R->value() == I->low()) {
404         if( rightUp(R) <= I->high() ) {
405             R->greater.insert( I );
406         }
407         R->equal.insert( I );   // assumes closed lower bound
408
409         if(created)
410             return R;
411         else
412             return NULL;
413     }
414     else if(R->value() < I->low()) {
415         return addLeft(I,R->right, R);
416     }
417     else if(R->value() > I->low()) {
418         if(R->value() < I->high()) {
419             R->equal.insert( I );
420         }
421         if( rightUp(R) <= I->high() ) {
422             R->greater.insert( I );
423         }
424         return addLeft(I, R->left, R);
425     } else {
426         assert(0);  // can't get here, but gcc whines
427         return NULL;
428     }
429 }
430
431 template<class ITYPE>
432 IBSNode<ITYPE> * 
433 IBSTree<ITYPE>::addRight(ITYPE *I, IBSNode<ITYPE> *R, IBSNode<ITYPE> *parent)
434 {
435     bool created = false;
436     if(R == nil) {
437         IBSNode<ITYPE> *tmp = new IBSNode<ITYPE>(I->high(), nil);
438         treeSize++;
439         created = true;
440         if(parent == NULL)  // must be the root
441         {
442             root = tmp;
443         } 
444         else {
445             tmp->parent = parent;
446             if(tmp->value() < parent->value()) {
447                 parent->left = tmp;
448             } else if(tmp->value() > parent->value()) {
449                 parent->right = tmp;
450             } else {
451                 assert(0); // can't get here
452             }
453         }
454
455         R = tmp;
456     }
457
458     if(R->value() == I->high()) {
459         // if everything in R's left subtree will be
460         // within the interval (that is, if the nearest ancestor
461         // node that has R in its right subtree (that R is greater than)
462         // is equal to or exceeds the low bound of I
463         if( leftUp(R) >= I->low() ) {
464             R->less.insert( I );
465         }
466         // the upper bound of the interval is open, so we don't add to r.equals
467     
468         if(created)
469             return R;
470         else
471             return NULL;
472     }
473     else if(R->value() < I->high()) {
474         if(R->value() > I->low()) {
475             // R is in the interval
476             R->equal.insert( I ); 
477         }
478         if( leftUp(R) >= I->low() ) {
479             // Everything to the left of R is within the interval
480             R->less.insert( I );
481         }
482         return addRight(I, R->right, R);
483     }
484     else if(R->value() > I->high()) {
485         // R not in the interval
486         return addRight(I, R->left, R);
487     }
488     else {
489         assert(0);
490         return NULL;
491     }
492 }
493
494 /* Traverse upward in the tree, looking for the nearest ancestor
495    that has R in its left subtree and return that value. Since this
496    routine is used to compute an upper bound on an interval, failure
497    to find a node should return +infinity */
498 template<class ITYPE>
499 int IBSTree<ITYPE>::rightUp(IBSNode<ITYPE> *R)
500 {
501     return rightUpAux(R->parent, R, INT_MAX);
502 }
503 // FIXME don't need cur; maintain the defaults within the code
504
505 template<class ITYPE>
506 int IBSTree<ITYPE>::rightUpAux(IBSNode<ITYPE> *parent, IBSNode<ITYPE> *child, int cur)
507 {
508     if(parent == NULL) {
509         return cur;
510     }
511
512     // Return value only if our traverse is up the left
513     // path of the parent's children
514     if(parent->left == child)
515         return parent->value();
516     else
517         return rightUpAux(parent->parent,parent,cur);
518 }
519
520 /* Same as rightUp, only looking for the nearest ancestor node that
521    has R in its RIGHT subtree, returning NEGATIVE infinity upon failure */
522 template<class ITYPE>
523 int IBSTree<ITYPE>::leftUp(IBSNode<ITYPE> *R)
524 {
525     return leftUpAux(R->parent,R,-INT_MAX - 1);    
526 }
527
528 template<class ITYPE>
529 int IBSTree<ITYPE>::leftUpAux(IBSNode<ITYPE> *parent, IBSNode<ITYPE> *child, int cur)
530 {
531     if(parent == NULL)
532         return cur;
533
534     if(parent->right == child)
535         return parent->value();
536     else 
537         return leftUpAux(parent->parent,parent,cur);
538 }
539
540 /* Restore RB-tree invariants after node insertion */
541 template<class ITYPE>
542 void IBSTree<ITYPE>::insertFixup(IBSNode<ITYPE> *x)
543 {
544     x->color = TREE_RED;
545     while((x != root) && (x->parent->color == TREE_RED)) {
546         if(x->parent == x->parent->parent->left) {
547             IBSNode<ITYPE>* y = x->parent->parent->right;
548             if(y->color == TREE_RED) {
549                 x->parent->color = TREE_BLACK;
550                 y->color = TREE_BLACK;
551                 x->parent->parent->color = TREE_RED;
552                 x = x->parent->parent;
553             }
554             else {
555                 if(x == x->parent->right) {
556                     x = x->parent;
557                     leftRotate(x);
558                 }
559                 x->parent->color = TREE_BLACK;
560                 x->parent->parent->color = TREE_RED;
561                 rightRotate(x->parent->parent);
562             }
563         }
564         else {
565             IBSNode<ITYPE> *y = x->parent->parent->left;
566             if(y->color == TREE_RED) {
567                 x->parent->color = TREE_BLACK;
568                 y->color = TREE_BLACK;
569                 x->parent->parent->color = TREE_RED;
570                 x = x->parent->parent;
571             }
572             else {
573                 if(x == x->parent->left) {
574                     x = x->parent;
575                     rightRotate(x);
576                 }
577                 x->parent->color = TREE_BLACK;
578                 x->parent->parent->color = TREE_RED;
579                 leftRotate(x->parent->parent);
580             }
581         }
582     }
583     root->color = TREE_BLACK;
584 }
585
586 template<class ITYPE>
587 void IBSTree<ITYPE>::destroy(IBSNode<ITYPE> *n)
588 {
589     if(!n || (n == nil))
590         return;
591     if(n->left != nil)
592         destroy(n->left);
593     if(n->right != nil)
594         destroy(n->right);
595     delete n;
596 }
597
598
599 /* void deleteFixup(IBSNode<ITYPE> *)
600 {
601     // XXX not implemented
602     assert(0);
603 }*/
604
605 template<class ITYPE>
606 void IBSTree<ITYPE>::findIntervals(int X, IBSNode<ITYPE> *R, set<ITYPE *> &S) const
607 {
608     if(R == nil) return;
609     
610     if(X == R->value()) {
611         S.insert(R->equal.begin(),R->equal.end());
612         return;
613     }
614     else if(X < R->value()) {
615         S.insert(R->less.begin(),R->less.end());
616         findIntervals(X,R->left,S);
617     } else {
618         S.insert(R->greater.begin(),R->greater.end());
619         findIntervals(X,R->right,S);
620     }
621 }
622
623 /* Find all intervals that intersect an interval:
624
625    If low is < a node, take the < set (any interval in < contains low)
626    If low or high are > a node, take the > set
627    If low <= a node and high > a node, take the = set
628 */
629 template<class ITYPE>
630 void IBSTree<ITYPE>::findIntervals(ITYPE * I, IBSNode<ITYPE> *R, set<ITYPE *> &S) const
631 {
632     if(R == nil) return;
633
634     int low = I->low();
635     int high = I->high();    
636
637     if(low < R->value()) {
638         S.insert(R->less.begin(),R->less.end());
639         findIntervals(I,R->left,S);
640     }
641     if(low > R->value() || high > R->value()) {
642         S.insert(R->greater.begin(),R->greater.end());
643         findIntervals(I,R->right,S);
644     }
645     if(low <= R->value() && high > R->value()) {
646         S.insert(R->equal.begin(),R->equal.end());
647     }
648 }
649
650 template<class ITYPE>
651 void IBSTree<ITYPE>::removeInterval(IBSNode<ITYPE> *R, ITYPE *range)
652 {
653     if(R == nil) return;
654
655     R->less.erase(range);
656     R->greater.erase(range);
657     R->equal.erase(range);
658
659     removeInterval(R->left,range);
660     removeInterval(R->right,range);
661 }
662
663 template<class ITYPE>
664 int IBSTree<ITYPE>::CountMarks(IBSNode<ITYPE> *R) const
665 {
666     if(R == nil) return 0;
667
668     return (R->less.size() + R->greater.size() + R->equal.size()) +
669         CountMarks(R->left) + CountMarks(R->right);
670 }
671
672 /***************** Public methods *****************/
673
674 template<class ITYPE>
675 void IBSTree<ITYPE>::insert(ITYPE *range)
676 {
677     stats_.startTimer("insert");
678
679     // Insert the endpoints of the range, rebalancing if new
680     // nodes were created
681     IBSNode<ITYPE> *x = addLeft(range,root,NULL);
682     if(x) {
683         insertFixup(x);
684     }
685     x = addRight(range,root,NULL);
686     if(x) {
687         insertFixup(x);
688     }
689
690     stats_.stopTimer("insert");
691 }
692
693 template<class ITYPE>
694 void IBSTree<ITYPE>::remove(ITYPE * range)
695 {
696     stats_.startTimer("remove");
697
698     // 1. Remove all interval markers corresponding to range from the tree,
699     //    using the reverse of the insertion procedure.
700
701     // 2. If no other intervals use the endpoints of this interval
702     //    (find this how?), remove their endpoints (complex) and fix
703     //    up the tree.
704
705     // XXX FIXME XXX
706     // Currently being very lazy and inefficient: only removing interval
707     // markers (not end nodes even if they end up unused), and also removing
708     // elements from each of the <, >, and = sets of each node (following
709     // the tests of the insertion procedures would avoid many of these
710     // O(log n) lookups
711
712     removeInterval(root,range);
713    
714     stats_.startTimer("remove"); 
715 }
716
717 template<class ITYPE>
718 int IBSTree<ITYPE>::find(int X, set<ITYPE *> &out) const
719 {
720     set<ITYPE *> tmp; 
721     findIntervals(X,root,tmp);
722
723     out.insert(tmp.begin(),tmp.end());
724
725     return tmp.size();
726 }
727
728 template<class ITYPE>
729 int IBSTree<ITYPE>::find(ITYPE * I, set<ITYPE *> &out) const
730 {
731     set<ITYPE *> tmp;
732     findIntervals(I,root,tmp);
733
734     out.insert(tmp.begin(),tmp.end());
735     
736     return tmp.size();
737 }
738
739 template<class ITYPE>
740 void IBSTree<ITYPE>::clear() {
741     if(root == nil) return;
742     destroy(root);
743     root = nil;
744     treeSize = 0;
745 }
746
747 template<class ITYPE>
748 int IBSTree<ITYPE>::height(IBSNode<ITYPE> *n)
749 {
750     if(!n)
751         return 0;
752     
753     int leftHeight = 1 + height(n->left);
754     int rightHeight = 1 + height(n->right);
755
756     if(leftHeight > rightHeight)
757         return leftHeight;
758     else
759         return rightHeight;
760 }
761
762 template<class ITYPE>
763 void IBSTree<ITYPE>::PrintPreorder(IBSNode<ITYPE> *n)
764 {
765     if(n == nil) return;
766
767     PrintPreorder(n->left);
768     printf(" %d\n",n->value());
769     PrintPreorder(n->right);
770
771     if(n == root) {
772         int h = height(root);
773         printf(" tree height: %d\n", h);
774     }
775 }
776
777 template<class ITYPE>
778 int IBSTree<ITYPE>::CountMarks() const
779 {
780     return CountMarks(root);
781 }
782 #endif
783