Doesn't compile! Added accessor function for memEmulator
[dyninst.git] / dynutil / 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 <stdio.h>
44 #include "dyntypes.h"
45
46 #include <set>
47 #include <limits>
48
49 using namespace std;
50
51 /** Templape class for Interval Binary Search Tree. The implementation is
52   * based on a red-black tree (derived from our codeRange implementation)
53   * to control the tree height and thus insertion and search cost.
54   *
55   * Unlike our codeRangeTree, this data structure can represent overlapping
56   * intervals. It is useful for executing stabbing queries and more
57   * generally for finding invervals that overlap a particular interval.
58   * A stabbing query requires O(log(N) + L) time in the worst case, where
59   * L is the number of overlapping intervals, and insertion requires
60   * O(log^2(N)) time (compare to O(log(N)) for a standard RB-tree).
61   *
62   * This class requires a worst case storage O(N log(N))
63   *
64   * For more information:
65   *
66   * @TECHREPORT{Hanson90theibs-tree:,
67   *     author = {Eric N. Hanson and Moez Chaabouni},
68   *     title = {The IBS-tree: A data structure for finding all intervals that overlap a point},
69   *     institution = {},
70   *     year = {1990}
71   * }
72   **/
73
74 /** EXTREMELY IMPORTANT XXX: Assuming that all intervals have lower bound
75     predicate <= and upper bound predicate > ; that is, intervals are 
76     [a,b) **/
77
78 // windows.h defines min(), max() macros that interfere with numeric_limits
79 #undef min
80 #undef max
81
82 namespace Dyninst {
83
84 namespace IBS {
85 typedef enum { TREE_RED, TREE_BLACK } color_t;
86 };
87
88 template<class T = unsigned long>
89 class interval {
90   public:
91     interval() { }
92     virtual ~interval() { }
93
94     virtual T low() const = 0;
95     virtual T high() const = 0;
96
97     typedef T type;
98 };
99
100 class SimpleInterval : interval<int> {
101   public:
102     SimpleInterval( interval<int> & i, void * id ) {
103         low_ = i.low();
104         high_ = i.high();
105         id_ = id;
106     }
107     SimpleInterval(int low, int high, void * id) {
108         low_ = low;
109         high_ = high;
110         id_ = id;
111     }
112         
113   private:
114     int low_;
115     int high_;
116     void * id_; // some arbitrary unique identifier
117 };
118
119 template<class ITYPE>
120 class IBSTree;
121
122 template<class ITYPE = interval<> >
123 class IBSNode {
124     friend class IBSTree<ITYPE>;
125     typedef typename ITYPE::type interval_type;
126   public:
127     IBSNode() : 
128         color(IBS::TREE_BLACK),
129         left(NULL),
130         right(NULL),
131         parent(NULL) { }
132
133     /** constructor for non-nil elements **/
134     IBSNode(interval_type value, IBSNode *n) :
135         val_(value),
136         left(n),
137         right(n),
138         parent(NULL) { }
139
140     ~IBSNode() { }
141
142     interval_type value() const { return val_; };
143
144   private: 
145     /* The endpoint of an interval range */
146     interval_type val_;
147
148     /* Intervals indexed by this node */
149     set<ITYPE *> less;
150     set<ITYPE *> greater;
151     set<ITYPE *> equal;
152
153     IBS::color_t color;
154
155     IBSNode<ITYPE> *left;
156     IBSNode<ITYPE> *right;
157     IBSNode<ITYPE> *parent;
158 };
159
160 template<class ITYPE = interval<> >
161 class IBSTree {
162     typedef typename ITYPE::type interval_type;
163
164     IBSNode<ITYPE> *nil;
165
166     /** size of tree **/
167     int treeSize;
168
169     /** pointer to the tree root **/
170     IBSNode<ITYPE> *root;
171
172     /** RB-tree left rotation with modification to enforce IBS invariants **/
173     void leftRotate(IBSNode<ITYPE> *);
174
175     /** RB-tree right rotation with modification to enforce IBS invariants **/
176     void rightRotate(IBSNode<ITYPE> *);
177
178     /** Node deletion **/
179     void deleteFixup(IBSNode<ITYPE> *);
180
181     void removeInterval(IBSNode<ITYPE> *R, ITYPE *range);
182
183     /** Insertion operations: insert the left or right endpoint of
184         an interval into the tree (may or may not add a node **/
185     IBSNode<ITYPE>* addLeft(ITYPE *I, IBSNode<ITYPE> *R);
186     IBSNode<ITYPE>* addRight(ITYPE *I, IBSNode<ITYPE> *R);
187
188     /** Find the lowest valued ancestor of node R that has R in its
189         left subtree -- used in addLeft to determine whether all of
190         the values in R's right subtree are covered by an interval **/
191     interval_type rightUp(IBSNode<ITYPE> *R);
192
193     /** Symmetric to rightUp **/
194     interval_type leftUp(IBSNode<ITYPE> *R);
195
196     /** Tree-balancing algorithm on insertion **/
197     void insertFixup(IBSNode<ITYPE> *x);
198
199     /** Finds the precessor of the node; this node will have its value
200         copied to the target node of a deletion and will itself be deleted **/
201     //IBSNode* treePredecessor(IBSNode *);
202
203     /** Find a node with the provided value (interval endpoint) **/
204     //IBSNode* findNode(int) const;
205
206     /** Delete all nodes in the subtree rooted at the parameter **/
207     void destroy(IBSNode<ITYPE> *);
208
209     void findIntervals(interval_type X, IBSNode<ITYPE> *R, set<ITYPE *> &S) const;
210     void findIntervals(ITYPE *I, IBSNode<ITYPE> *R, set<ITYPE *> &S) const;
211
212     void PrintPreorder(IBSNode<ITYPE> *n);
213
214     int height(IBSNode<ITYPE> *n);
215     int CountMarks(IBSNode<ITYPE> *R) const;
216
217     unsigned MemUse() const;
218
219   public:
220
221     /** public for debugging purposes **/
222     //StatContainer stats_;
223
224     IBSTree() : treeSize(0) {
225         nil = new IBSNode<ITYPE>;
226         root = nil;
227         //stats_.add("insert",TimerStat);
228         //stats_.add("remove",TimerStat);
229     }     
230
231     ~IBSTree() {
232         destroy(root);
233         delete nil;
234     }
235
236     int size() const { return treeSize; }
237     int CountMarks() const;
238     
239     bool empty() const { return (root == nil); }
240
241     void insert(ITYPE *);
242
243     void remove(ITYPE *);
244
245     /** Find all intervals that overlap the provided point. Returns
246         the number of intervals found **/  
247     int find(interval_type, set<ITYPE *> &) const;
248     int find(ITYPE *I, set<ITYPE *> &) const;
249
250     /** Finds the very next interval(s) with left endpoint
251         = supremum(X) **/
252     void successor(interval_type X, set<ITYPE *> &) const; 
253     /** Use only when no two intervals share the same lower bound **/
254     ITYPE * successor(interval_type X) const;
255
256     /** Delete all entries in the tree **/
257     void clear();
258
259     void PrintPreorder() { PrintPreorder(root); }
260 };
261
262 template<class ITYPE>
263 void IBSTree<ITYPE>::rightRotate(IBSNode<ITYPE> *pivot)
264 {
265     if(!pivot || (pivot == nil))
266         return;
267
268     IBSNode<ITYPE> *y = pivot->left;
269     if(y == nil)
270         return;
271     pivot->left = y->right;
272     if(y->right != nil)
273         y->right->parent = pivot;
274     y->parent = pivot->parent;
275     if(!pivot->parent) {
276         root = y;
277     }
278     else if(pivot == pivot->parent->left)
279         pivot->parent->left = y;
280     else
281         pivot->parent->right = y;
282     y->right = pivot;
283     pivot->parent = y;
284
285     /* Maintain the IBS annotation invariants */
286     
287     // 1. Copy all marks from the < slot of the pivot (old subtree root)
288     //    to the < and = slots of y (new subtree root). Maintains containment.
289     y->less.insert(pivot->less.begin(), pivot->less.end());
290     y->equal.insert(pivot->less.begin(), pivot->less.end());
291
292     // 2. For each mark in y's > slot, if it was not in pivot's >,
293     //    *move* it to pivot's <. Maintains containment and maximality,
294     //    because it ensures that nodes under y->right covered by
295     //    the mark before rotation are now (which are now under pivot->left)
296     //    are still covered by the mark (if y > can't cover them still)
297     
298     // 3. Simultaneously, if the mark in in y's > slot AND pivot's > slot 
299     //    (before rotation), remove the mark from pivot's > and = slots
300     //    (preserving maximality).
301
302     typename set< ITYPE * >::iterator it = y->greater.begin();
303     while( it != y->greater.end() )
304     {
305         ITYPE *tmp = *it;
306     
307         typename set< ITYPE *>::iterator pit = pivot->greater.find( tmp );
308         if(pit == pivot->greater.end()) {
309             // Case 2
310             pivot->less.insert( tmp );
311             // remove from y's >. This invalidates the iterator, so
312             // update first
313             typename set< ITYPE * >::iterator del = it;
314             ++it;
315             y->greater.erase( del );
316         } else {
317             // Case 3
318             // remove from pivot's >
319             pivot->greater.erase( pit );
320             pit = pivot->equal.find( tmp );
321             if(pit != pivot->equal.end())
322                 pivot->equal.erase( pit );
323     
324             ++it;
325         }
326     }
327 }
328
329 template<class ITYPE>
330 void IBSTree<ITYPE>::leftRotate(IBSNode<ITYPE> *pivot)
331 {
332     if(!pivot || (pivot == nil))
333         return;
334
335     IBSNode<ITYPE> *y = pivot->right;
336
337     if(y == nil)
338         return;
339
340     pivot->right = y->left;
341     if(y->left != nil)
342         y->left->parent = pivot;
343     y->parent = pivot->parent;
344     if(!pivot->parent) {
345         root = y;
346     }
347     else if(pivot == pivot->parent->left)
348         pivot->parent->left = y;
349     else
350         pivot->parent->right = y;
351     y->left = pivot;
352     pivot->parent = y;
353
354     /* Fix up the IBS annotations. These are exactly opposeite of the
355        rules for right rotation */
356     
357     y->greater.insert(pivot->greater.begin(),pivot->greater.end());
358     y->equal.insert(pivot->greater.begin(),pivot->greater.end());
359
360     typename set< ITYPE * >::iterator it = y->less.begin();
361     while( it != y->less.end() )
362     {
363         ITYPE *tmp = *it;
364     
365         typename set< ITYPE *>::iterator pit = pivot->less.find( tmp );
366         if(pit == pivot->less.end()) {
367             // Case 2
368             pivot->greater.insert( tmp );
369             // remove from y's <. This invalidates the iterator, so
370             // update first
371             typename set< ITYPE * >::iterator del = it;
372             ++it;
373             y->less.erase( del );
374         } else {
375             // Case 3
376             // remove from pivot's < and =
377             pivot->less.erase( pit );
378             pit = pivot->equal.find( tmp );
379             if(pit != pivot->equal.end())
380                 pivot->equal.erase( pit );
381     
382             ++it;
383         }
384     }
385 }
386
387 template<class ITYPE>
388 IBSNode<ITYPE>* 
389 IBSTree<ITYPE>::addLeft(ITYPE *I, IBSNode<ITYPE> *R)
390 {
391     IBSNode<ITYPE> *parent = NULL;
392
393     // these calls can't be inlined as they're to virtuals
394     interval_type ilow = I->low();
395     interval_type ihigh = I->high();
396
397     while(1) {
398         bool created = false;
399         if(R == nil) {
400             // create a new node
401             IBSNode<ITYPE> *tmp = new IBSNode<ITYPE>( ilow, nil );
402             treeSize++;
403             created = true;
404            
405             if(parent == NULL)  // must be the root
406                 root = tmp;
407             else {
408                 tmp->parent = parent;
409                 if(tmp->value() < parent->value()) {
410                     parent->left = tmp;
411                 } else if(tmp->value() > parent->value()) {
412                     parent->right = tmp;
413                 } else {
414                     assert(0); // can't get here
415                 }
416             }
417             R = tmp;
418         }
419
420         interval_type rval = R->value();
421     
422         if(rval == ilow) {
423             if( rightUp(R) <= ihigh ) {
424                 R->greater.insert( I );
425             }
426             R->equal.insert( I );   // assumes closed lower bound
427     
428             if(created)
429                 return R;
430             else
431                 return NULL;
432         }
433         else if(rval < ilow) {
434             parent = R;
435             R = R->right;
436             continue;
437         }
438         else if(rval > ilow) {
439             if(rval < ihigh) {
440                 R->equal.insert( I );
441             }
442             if( rightUp(R) <= ihigh ) {
443                 R->greater.insert( I );
444             }
445             parent = R;
446             R = R->left;
447             continue;
448         } else {
449             assert(0);  // can't get here, but gcc whines
450             return NULL;
451         }
452     }
453
454     assert(0);
455     return NULL;    // make GCC happy
456 }
457
458 template<class ITYPE>
459 IBSNode<ITYPE> *
460 IBSTree<ITYPE>::addRight(ITYPE *I, IBSNode<ITYPE> *R)
461 {
462     IBSNode<ITYPE> *parent = NULL;
463
464     // these calls can't be inlined as they're to virtuals
465     interval_type ilow = I->low();
466     interval_type ihigh = I->high();
467
468     while(1)
469     {
470         bool created = false;
471         if(R == nil) {
472             IBSNode<ITYPE> *tmp = new IBSNode<ITYPE>(ihigh,nil);
473             ++treeSize;
474             created = true;
475             if(parent == NULL) // must be the root
476                 root = tmp;
477             else {
478                 tmp->parent = parent;
479                 if(tmp->value() < parent->value())
480                     parent->left = tmp;
481                 else if(tmp->value() > parent->value())
482                     parent->right = tmp;
483                 else 
484                     assert(0); // can't get here
485             }
486             R = tmp;
487         }
488
489         interval_type rval = R->value();
490
491         if(rval == ihigh) {
492             // Case 1. Everything in R's left subtree will be
493             // within the interval (that is, the nearest ancestor
494             // node that has R in its right subtree [leftUp(R)]
495             // has a value equal to or exceeding the low bound of I
496             //
497             // NB the upper bound of the interval is open, so don't 
498             // add to r.equals here. Compare addLeft
499             if(leftUp(R) >= ilow)
500                 R->less.insert(I);
501
502             if(created)
503                 return R; 
504             else
505                 return NULL;
506         }
507         else if(rval < ihigh) {
508             if(rval > ilow) {
509                 // R is in the interval
510                 R->equal.insert( I ); 
511             }
512             if( leftUp(R) >= ilow ) {
513                 // Everything to the left of R is within the interval
514                 R->less.insert( I );
515             }
516
517             parent = R;
518             R = R->right;
519             continue;
520         }
521         else if(rval > ihigh) {
522             // R not in the interval
523             parent = R;
524             R = R->left;
525             continue;
526         }
527         else {
528             assert(0);
529             return NULL;
530         }
531     }
532
533     assert(0);
534     return NULL; // make GCC happy
535 }
536
537 /* Traverse upward in the tree, looking for the nearest ancestor
538    that has R in its left subtree and return that value. Since this
539    routine is used to compute an upper bound on an interval, failure
540    to find a node should return +infinity */
541 template<class ITYPE>
542 typename ITYPE::type
543 IBSTree<ITYPE>::rightUp(IBSNode<ITYPE> *R)
544 {
545     while(NULL != R->parent) {
546         if(R->parent->left == R)
547             return R->parent->value();
548         R = R->parent; 
549     }
550     return numeric_limits<interval_type>::max();
551 }
552
553 /* Same as rightUp, only looking for the nearest ancestor node that
554    has R in its RIGHT subtree, returning NEGATIVE infinity upon failure */
555 template<class ITYPE>
556 typename ITYPE::type
557 IBSTree<ITYPE>::leftUp(IBSNode<ITYPE> *R)
558 {
559     while(NULL != R->parent) {
560         if(R->parent->right == R)
561             return R->parent->value();
562         R = R->parent;
563     }
564     // XXX is this right? for unsigned values, min() is a possible value
565     return numeric_limits<interval_type>::min();
566 }
567
568 /* Restore RB-tree invariants after node insertion */
569 template<class ITYPE>
570 void IBSTree<ITYPE>::insertFixup(IBSNode<ITYPE> *x)
571 {
572     x->color = IBS::TREE_RED;
573     while((x != root) && (x->parent->color == IBS::TREE_RED)) {
574         if(x->parent == x->parent->parent->left) {
575             IBSNode<ITYPE>* y = x->parent->parent->right;
576             if(y->color == IBS::TREE_RED) {
577                 x->parent->color = IBS::TREE_BLACK;
578                 y->color = IBS::TREE_BLACK;
579                 x->parent->parent->color = IBS::TREE_RED;
580                 x = x->parent->parent;
581             }
582             else {
583                 if(x == x->parent->right) {
584                     x = x->parent;
585                     leftRotate(x);
586                 }
587                 x->parent->color = IBS::TREE_BLACK;
588                 x->parent->parent->color = IBS::TREE_RED;
589                 rightRotate(x->parent->parent);
590             }
591         }
592         else {
593             IBSNode<ITYPE> *y = x->parent->parent->left;
594             if(y->color == IBS::TREE_RED) {
595                 x->parent->color = IBS::TREE_BLACK;
596                 y->color = IBS::TREE_BLACK;
597                 x->parent->parent->color = IBS::TREE_RED;
598                 x = x->parent->parent;
599             }
600             else {
601                 if(x == x->parent->left) {
602                     x = x->parent;
603                     rightRotate(x);
604                 }
605                 x->parent->color = IBS::TREE_BLACK;
606                 x->parent->parent->color = IBS::TREE_RED;
607                 leftRotate(x->parent->parent);
608             }
609         }
610     }
611     root->color = IBS::TREE_BLACK;
612 }
613
614 template<class ITYPE>
615 void IBSTree<ITYPE>::destroy(IBSNode<ITYPE> *n)
616 {
617     if(!n || (n == nil))
618         return;
619     if(n->left != nil)
620         destroy(n->left);
621     if(n->right != nil)
622         destroy(n->right);
623     delete n;
624 }
625
626
627 /* void deleteFixup(IBSNode<ITYPE> *)
628 {
629     // XXX not implemented
630     assert(0);
631 }*/
632
633 template<class ITYPE>
634 void IBSTree<ITYPE>::findIntervals(interval_type X, IBSNode<ITYPE> *R, set<ITYPE *> &S) const
635 {
636     while(R != nil) {
637         if(X == R->value()) {
638             S.insert(R->equal.begin(),R->equal.end());
639             return;
640         }
641         else if(X < R->value()) {
642             S.insert(R->less.begin(),R->less.end());
643             R = R->left;
644         } else {
645             S.insert(R->greater.begin(),R->greater.end());
646             R = R->right;
647         }
648     }
649 }
650
651 /* Find all intervals that intersect an interval:
652
653    If low is < a node, take the < set (any interval in < contains low)
654    If low or high are > a node, take the > set
655    If low <= a node and high > a node, take the = set
656
657    NB Because this traversal may go both directions in the tree,
658       it remains a recursive operation and is less efficient
659       than a pointwise stabbing query.
660 */
661 template<class ITYPE>
662 void IBSTree<ITYPE>::findIntervals(ITYPE * I, IBSNode<ITYPE> *R, set<ITYPE *> &S) const
663 {
664     if(R == nil) return;
665
666     interval_type low = I->low();
667     interval_type high = I->high();    
668
669     if(low < R->value()) {
670         S.insert(R->less.begin(),R->less.end());
671         findIntervals(I,R->left,S);
672     }
673     if(low > R->value() || high > R->value()) {
674         S.insert(R->greater.begin(),R->greater.end());
675         findIntervals(I,R->right,S);
676     }
677     if(low <= R->value() && high > R->value()) {
678         S.insert(R->equal.begin(),R->equal.end());
679     } 
680     else if(low == R->value() && high == R->value()) {
681         // XXX explicitly allow zero-length intervals
682         //     to `match' the starting value
683         S.insert(R->equal.begin(),R->equal.end());
684     }
685 }
686
687 template<class ITYPE>
688 void IBSTree<ITYPE>::removeInterval(IBSNode<ITYPE> *R, ITYPE *range)
689 {
690     if(R == nil) return;
691
692     interval_type low = range->low();
693     interval_type high = range->high();    
694
695     // FIXME this doesn't use maximality and containment to minimize the
696     // number of set::erase calls
697     if(low < R->value()) {
698         R->less.erase(range);
699         removeInterval(R->left,range);
700     }
701     if(low > R->value() || high > R->value()) {
702         R->greater.erase(range);
703         removeInterval(R->right,range);
704     }
705     if(low <= R->value() && high > R->value()) {
706         R->equal.erase(range);
707     }
708     else if(low == R->value() && high == R->value()) {
709         // XXX explicitly allow zero-length intervals
710         //     to `match' the starting value
711         R->equal.erase(range);
712     }
713 }
714
715 template<class ITYPE>
716 int IBSTree<ITYPE>::CountMarks(IBSNode<ITYPE> *R) const
717 {
718     if(R == nil) return 0;
719
720     return (R->less.size() + R->greater.size() + R->equal.size()) +
721         CountMarks(R->left) + CountMarks(R->right);
722 }
723
724 /***************** Public methods *****************/
725
726 template<class ITYPE>
727 void IBSTree<ITYPE>::insert(ITYPE *range)
728 {
729     //stats_.startTimer("insert");
730
731     // Insert the endpoints of the range, rebalancing if new
732     // nodes were created
733     IBSNode<ITYPE> *x = addLeft(range,root);
734     if(x) {
735         insertFixup(x);
736     }
737     x = addRight(range,root);
738     if(x) {
739         insertFixup(x);
740     }
741
742     //stats_.stopTimer("insert");
743 }
744
745 template<class ITYPE>
746 void IBSTree<ITYPE>::remove(ITYPE * range)
747 {
748     //stats_.startTimer("remove");
749
750     // 1. Remove all interval markers corresponding to range from the tree,
751     //    using the reverse of the insertion procedure.
752
753     // 2. If no other intervals use the endpoints of this interval
754     //    (find this how?), remove their endpoints (complex) and fix
755     //    up the tree.
756
757     // XXX FIXME XXX
758     // Currently being very lazy and inefficient: only removing interval
759     // markers (not end nodes even if they end up unused), and also removing
760     // elements from each of the <, >, and = sets of each node (following
761     // the tests of the insertion procedures would avoid many of these
762     // O(log n) lookups
763
764     removeInterval(root,range);
765    
766     //stats_.startTimer("remove"); 
767 }
768
769 template<class ITYPE>
770 int IBSTree<ITYPE>::find(interval_type X, set<ITYPE *> &out) const
771 {
772     unsigned size = out.size();
773     findIntervals(X,root,out);
774     return out.size() - size;
775 }
776
777 template<class ITYPE>
778 int IBSTree<ITYPE>::find(ITYPE * I, set<ITYPE *> &out) const
779 {
780     unsigned size = out.size();
781     findIntervals(I,root,out);
782     return out.size() - size;
783 }
784
785 template<class ITYPE>
786 void IBSTree<ITYPE>::successor(interval_type X, set<ITYPE *> &out) const
787 {
788     IBSNode<ITYPE> *n = root;
789     IBSNode<ITYPE> *last = nil;
790
791     std::vector< IBSNode<ITYPE>* > stack;
792
793     /* last will hold the node immediately greater than X */
794     while(1) {
795         if(n == nil) {
796             if(last != nil) {
797                 typename set<ITYPE *>::iterator sit = last->equal.begin();
798                 for( ; sit != last->equal.end(); ++sit) {
799                    if((*sit)->low() == last->value()) out.insert(*sit);
800                 }
801                 if(!out.empty())
802                     break;
803                 else {
804                     // have missed out. pop back up to the last node where
805                     // we went left and then advance down its right path
806                     n = last->right;
807                     if(!stack.empty()) {
808                         last = stack.back();
809                         stack.pop_back();
810                     } else {
811                         last = nil;
812                     }
813                     continue;
814                 } 
815             } else 
816                 break;
817         }
818
819         if(X >= n->value()) {
820             n = n->right;
821         } else {
822             if(last != nil)
823                 stack.push_back(last);
824             last = n;
825             n = n->left;
826         }
827     }
828 }
829
830 template<class ITYPE>
831 ITYPE * IBSTree<ITYPE>::successor(interval_type X) const
832 {
833     set<ITYPE *> out;
834     successor(X,out);
835     assert( out.size() <= 1 );
836     if(!out.empty())
837         return *out.begin();
838     else
839         return NULL;
840 }
841
842 template<class ITYPE>
843 void IBSTree<ITYPE>::clear() {
844     if(root == nil) return;
845     destroy(root);
846     root = nil;
847     treeSize = 0;
848 }
849
850 template<class ITYPE>
851 int IBSTree<ITYPE>::height(IBSNode<ITYPE> *n)
852 {
853     if(!n)
854         return 0;
855     
856     int leftHeight = 1 + height(n->left);
857     int rightHeight = 1 + height(n->right);
858
859     if(leftHeight > rightHeight)
860         return leftHeight;
861     else
862         return rightHeight;
863 }
864
865 template<class ITYPE>
866 void IBSTree<ITYPE>::PrintPreorder(IBSNode<ITYPE> *n)
867 {
868     if(n == nil) return;
869
870     PrintPreorder(n->left);
871     printf(" %d\n",n->value());
872     PrintPreorder(n->right);
873
874     if(n == root) {
875         int h = height(root);
876         printf(" tree height: %d\n", h);
877     }
878 }
879
880 template<class ITYPE>
881 int IBSTree<ITYPE>::CountMarks() const
882 {
883     return CountMarks(root);
884 }
885 } /* Dyninst */
886 #endif
887