10 #define VERIFY(condition) \
12 fprintf(stderr, "Assumption \"%s\"\nFailed in file %s: at line:%i\n", \
13 #condition,__FILE__,__LINE__); \
16 /*#define DEBUG_ASSERT 1*/
19 static void Assert(int assertion, const char *error)
22 fprintf(stderr, "Assertion Failed: %s\n", error);
28 /* If the symbol CHECK_INTERVAL_TREE_ASSUMPTIONS is defined then the
29 * code does a lot of extra checking to make sure certain assumptions
30 * are satisfied. This only needs to be done if you suspect bugs are
31 * present or if you make significant changes and want to make sure
32 * your changes didn't mess anything up.
34 /*#define CHECK_INTERVAL_TREE_ASSUMPTIONS 1*/
36 static IntervalTreeNode *ITN_create(long low, long high, void *data);
38 static void LeftRotate(IntervalTree *, IntervalTreeNode *);
39 static void RightRotate(IntervalTree *, IntervalTreeNode *);
40 static void TreeInsertHelp(IntervalTree *, IntervalTreeNode *);
41 static void TreePrintHelper(const IntervalTree *, IntervalTreeNode *);
42 static void FixUpMaxHigh(IntervalTree *, IntervalTreeNode *);
43 static void DeleteFixUp(IntervalTree *, IntervalTreeNode *);
44 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
45 static void CheckMaxHighFields(const IntervalTree *, IntervalTreeNode *);
46 static int CheckMaxHighFieldsHelper(const IntervalTree *, IntervalTreeNode *y,
47 const int currentHigh, int match);
48 static void IT_CheckAssumptions(const IntervalTree *);
51 /* define a function to find the maximum of two objects. */
52 #define ITMax(a, b) ( (a > b) ? a : b )
55 ITN_create(long low, long high, void *data)
57 IntervalTreeNode *itn = yasm_xmalloc(sizeof(IntervalTreeNode));
73 IntervalTree *it = yasm_xmalloc(sizeof(IntervalTree));
75 it->nil = ITN_create(LONG_MIN, LONG_MIN, NULL);
76 it->nil->left = it->nil;
77 it->nil->right = it->nil;
78 it->nil->parent = it->nil;
81 it->root = ITN_create(LONG_MAX, LONG_MAX, NULL);
82 it->root->left = it->nil;
83 it->root->right = it->nil;
84 it->root->parent = it->nil;
87 /* the following are used for the Enumerate function */
88 it->recursionNodeStackSize = 128;
89 it->recursionNodeStack = (it_recursion_node *)
90 yasm_xmalloc(it->recursionNodeStackSize*sizeof(it_recursion_node));
91 it->recursionNodeStackTop = 1;
92 it->recursionNodeStack[0].start_node = NULL;
97 /***********************************************************************/
98 /* FUNCTION: LeftRotate */
100 /* INPUTS: the node to rotate on */
104 /* Modifies Input: this, x */
106 /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
107 /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
108 /* makes the parent of x be to the left of x, x the parent of */
109 /* its parent before the rotation and fixes other pointers */
110 /* accordingly. Also updates the maxHigh fields of x and y */
111 /* after rotation. */
112 /***********************************************************************/
115 LeftRotate(IntervalTree *it, IntervalTreeNode *x)
119 /* I originally wrote this function to use the sentinel for
120 * nil to avoid checking for nil. However this introduces a
121 * very subtle bug because sometimes this function modifies
122 * the parent pointer of nil. This can be a problem if a
123 * function which calls LeftRotate also uses the nil sentinel
124 * and expects the nil sentinel's parent pointer to be unchanged
125 * after calling this function. For example, when DeleteFixUP
126 * calls LeftRotate it expects the parent pointer of nil to be
133 if (y->left != it->nil)
134 y->left->parent=x; /* used to use sentinel here */
135 /* and do an unconditional assignment instead of testing for nil */
139 /* Instead of checking if x->parent is the root as in the book, we
140 * count on the root sentinel to implicitly take care of this case
142 if (x == x->parent->left)
149 x->maxHigh=ITMax(x->left->maxHigh,ITMax(x->right->maxHigh,x->high));
150 y->maxHigh=ITMax(x->maxHigh,ITMax(y->right->maxHigh,y->high));
151 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
152 IT_CheckAssumptions(it);
153 #elif defined(DEBUG_ASSERT)
154 Assert(!it->nil->red,"nil not red in ITLeftRotate");
155 Assert((it->nil->maxHigh=LONG_MIN),
156 "nil->maxHigh != LONG_MIN in ITLeftRotate");
161 /***********************************************************************/
162 /* FUNCTION: RightRotate */
164 /* INPUTS: node to rotate on */
168 /* Modifies Input?: this, y */
170 /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
171 /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
172 /* makes the parent of x be to the left of x, x the parent of */
173 /* its parent before the rotation and fixes other pointers */
174 /* accordingly. Also updates the maxHigh fields of x and y */
175 /* after rotation. */
176 /***********************************************************************/
180 RightRotate(IntervalTree *it, IntervalTreeNode *y)
184 /* I originally wrote this function to use the sentinel for
185 * nil to avoid checking for nil. However this introduces a
186 * very subtle bug because sometimes this function modifies
187 * the parent pointer of nil. This can be a problem if a
188 * function which calls LeftRotate also uses the nil sentinel
189 * and expects the nil sentinel's parent pointer to be unchanged
190 * after calling this function. For example, when DeleteFixUP
191 * calls LeftRotate it expects the parent pointer of nil to be
198 if (it->nil != x->right)
199 x->right->parent=y; /*used to use sentinel here */
200 /* and do an unconditional assignment instead of testing for nil */
202 /* Instead of checking if x->parent is the root as in the book, we
203 * count on the root sentinel to implicitly take care of this case
206 if (y == y->parent->left)
213 y->maxHigh=ITMax(y->left->maxHigh,ITMax(y->right->maxHigh,y->high));
214 x->maxHigh=ITMax(x->left->maxHigh,ITMax(y->maxHigh,x->high));
215 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
216 IT_CheckAssumptions(it);
217 #elif defined(DEBUG_ASSERT)
218 Assert(!it->nil->red,"nil not red in ITRightRotate");
219 Assert((it->nil->maxHigh=LONG_MIN),
220 "nil->maxHigh != LONG_MIN in ITRightRotate");
224 /***********************************************************************/
225 /* FUNCTION: TreeInsertHelp */
227 /* INPUTS: z is the node to insert */
231 /* Modifies Input: this, z */
233 /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
234 /* using the algorithm described in _Introduction_To_Algorithms_ */
235 /* by Cormen et al. This funciton is only intended to be called */
236 /* by the InsertTree function and not by the user */
237 /***********************************************************************/
240 TreeInsertHelp(IntervalTree *it, IntervalTreeNode *z)
242 /* This function should only be called by InsertITTree (see above) */
246 z->left=z->right=it->nil;
249 while( x != it->nil) {
253 else /* x->low <= z->low */
257 if ((y == it->root) || (y->low > z->low))
262 #if defined(DEBUG_ASSERT)
263 Assert(!it->nil->red,"nil not red in ITTreeInsertHelp");
264 Assert((it->nil->maxHigh=INT_MIN),
265 "nil->maxHigh != INT_MIN in ITTreeInsertHelp");
270 /***********************************************************************/
271 /* FUNCTION: FixUpMaxHigh */
273 /* INPUTS: x is the node to start from*/
277 /* Modifies Input: this */
279 /* EFFECTS: Travels up to the root fixing the maxHigh fields after */
280 /* an insertion or deletion */
281 /***********************************************************************/
284 FixUpMaxHigh(IntervalTree *it, IntervalTreeNode *x)
286 while(x != it->root) {
287 x->maxHigh=ITMax(x->high,ITMax(x->left->maxHigh,x->right->maxHigh));
290 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
291 IT_CheckAssumptions(it);
295 /* Before calling InsertNode the node x should have its key set */
297 /***********************************************************************/
298 /* FUNCTION: InsertNode */
300 /* INPUTS: newInterval is the interval to insert*/
302 /* OUTPUT: This function returns a pointer to the newly inserted node */
303 /* which is guarunteed to be valid until this node is deleted. */
304 /* What this means is if another data structure stores this */
305 /* pointer then the tree does not need to be searched when this */
306 /* is to be deleted. */
308 /* Modifies Input: tree */
310 /* EFFECTS: Creates a node node which contains the appropriate key and */
311 /* info pointers and inserts it into the tree. */
312 /***********************************************************************/
315 IT_insert(IntervalTree *it, long low, long high, void *data)
317 IntervalTreeNode *x, *y, *newNode;
319 x = ITN_create(low, high, data);
320 TreeInsertHelp(it, x);
321 FixUpMaxHigh(it, x->parent);
324 while(x->parent->red) { /* use sentinel instead of checking for root */
325 if (x->parent == x->parent->parent->left) {
326 y=x->parent->parent->right;
330 x->parent->parent->red=1;
333 if (x == x->parent->right) {
338 x->parent->parent->red=1;
339 RightRotate(it, x->parent->parent);
341 } else { /* case for x->parent == x->parent->parent->right */
342 /* this part is just like the section above with */
343 /* left and right interchanged */
344 y=x->parent->parent->left;
348 x->parent->parent->red=1;
351 if (x == x->parent->left) {
356 x->parent->parent->red=1;
357 LeftRotate(it, x->parent->parent);
361 it->root->left->red=0;
363 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
364 IT_CheckAssumptions(it);
365 #elif defined(DEBUG_ASSERT)
366 Assert(!it->nil->red,"nil not red in ITTreeInsert");
367 Assert(!it->root->red,"root not red in ITTreeInsert");
368 Assert((it->nil->maxHigh=LONG_MIN),
369 "nil->maxHigh != LONG_MIN in ITTreeInsert");
374 /***********************************************************************/
375 /* FUNCTION: GetSuccessorOf */
377 /* INPUTS: x is the node we want the succesor of */
379 /* OUTPUT: This function returns the successor of x or NULL if no */
380 /* successor exists. */
382 /* Modifies Input: none */
384 /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
385 /***********************************************************************/
388 IT_get_successor(const IntervalTree *it, IntervalTreeNode *x)
392 if (it->nil != (y = x->right)) { /* assignment to y is intentional */
393 while(y->left != it->nil) /* returns the minium of the right subtree of x */
398 while(x == y->right) { /* sentinel used instead of checking for nil */
408 /***********************************************************************/
409 /* FUNCTION: GetPredecessorOf */
411 /* INPUTS: x is the node to get predecessor of */
413 /* OUTPUT: This function returns the predecessor of x or NULL if no */
414 /* predecessor exists. */
416 /* Modifies Input: none */
418 /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
419 /***********************************************************************/
422 IT_get_predecessor(const IntervalTree *it, IntervalTreeNode *x)
426 if (it->nil != (y = x->left)) { /* assignment to y is intentional */
427 while(y->right != it->nil) /* returns the maximum of the left subtree of x */
432 while(x == y->left) {
442 /***********************************************************************/
443 /* FUNCTION: Print */
449 /* EFFECTS: This function recursively prints the nodes of the tree */
452 /* Modifies Input: none */
454 /* Note: This function should only be called from ITTreePrint */
455 /***********************************************************************/
458 ITN_print(const IntervalTreeNode *itn, IntervalTreeNode *nil,
459 IntervalTreeNode *root)
461 printf(", l=%li, h=%li, mH=%li", itn->low, itn->high, itn->maxHigh);
463 if (itn->left == nil)
466 printf("%li", itn->left->low);
468 if (itn->right == nil)
471 printf("%li", itn->right->low);
473 if (itn->parent == root)
476 printf("%li", itn->parent->low);
477 printf(" red=%i\n", itn->red);
481 TreePrintHelper(const IntervalTree *it, IntervalTreeNode *x)
484 TreePrintHelper(it, x->left);
485 ITN_print(x, it->nil, it->root);
486 TreePrintHelper(it, x->right);
491 IT_destroy(IntervalTree *it)
493 IntervalTreeNode *x = it->root->left;
494 SLIST_HEAD(node_head, nodeent)
495 stuffToFree = SLIST_HEAD_INITIALIZER(stuffToFree);
497 SLIST_ENTRY(nodeent) link;
498 struct IntervalTreeNode *node;
502 if (x->left != it->nil) {
503 np = yasm_xmalloc(sizeof(struct nodeent));
505 SLIST_INSERT_HEAD(&stuffToFree, np, link);
507 if (x->right != it->nil) {
508 np = yasm_xmalloc(sizeof(struct nodeent));
510 SLIST_INSERT_HEAD(&stuffToFree, np, link);
513 while (!SLIST_EMPTY(&stuffToFree)) {
514 np = SLIST_FIRST(&stuffToFree);
516 SLIST_REMOVE_HEAD(&stuffToFree, link);
519 if (x->left != it->nil) {
520 np = yasm_xmalloc(sizeof(struct nodeent));
522 SLIST_INSERT_HEAD(&stuffToFree, np, link);
524 if (x->right != it->nil) {
525 np = yasm_xmalloc(sizeof(struct nodeent));
527 SLIST_INSERT_HEAD(&stuffToFree, np, link);
534 yasm_xfree(it->root);
535 yasm_xfree(it->recursionNodeStack);
540 /***********************************************************************/
541 /* FUNCTION: Print */
547 /* EFFECT: This function recursively prints the nodes of the tree */
550 /* Modifies Input: none */
552 /***********************************************************************/
555 IT_print(const IntervalTree *it)
557 TreePrintHelper(it, it->root->left);
560 /***********************************************************************/
561 /* FUNCTION: DeleteFixUp */
563 /* INPUTS: x is the child of the spliced */
564 /* out node in DeleteNode. */
568 /* EFFECT: Performs rotations and changes colors to restore red-black */
569 /* properties after a node is deleted */
571 /* Modifies Input: this, x */
573 /* The algorithm from this function is from _Introduction_To_Algorithms_ */
574 /***********************************************************************/
577 DeleteFixUp(IntervalTree *it, IntervalTreeNode *x)
580 IntervalTreeNode *rootLeft = it->root->left;
582 while ((!x->red) && (rootLeft != x)) {
583 if (x == x->parent->left) {
588 LeftRotate(it, x->parent);
591 if ( (!w->right->red) && (!w->left->red) ) {
595 if (!w->right->red) {
601 w->red=x->parent->red;
604 LeftRotate(it, x->parent);
605 x=rootLeft; /* this is to exit while loop */
607 } else { /* the code below is has left and right switched from above */
612 RightRotate(it, x->parent);
615 if ((!w->right->red) && (!w->left->red)) {
625 w->red=x->parent->red;
628 RightRotate(it, x->parent);
629 x=rootLeft; /* this is to exit while loop */
635 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
636 IT_CheckAssumptions(it);
637 #elif defined(DEBUG_ASSERT)
638 Assert(!it->nil->red,"nil not black in ITDeleteFixUp");
639 Assert((it->nil->maxHigh=LONG_MIN),
640 "nil->maxHigh != LONG_MIN in ITDeleteFixUp");
645 /***********************************************************************/
646 /* FUNCTION: DeleteNode */
648 /* INPUTS: tree is the tree to delete node z from */
650 /* OUTPUT: returns the Interval stored at deleted node */
652 /* EFFECT: Deletes z from tree and but don't call destructor */
653 /* Then calls FixUpMaxHigh to fix maxHigh fields then calls */
654 /* ITDeleteFixUp to restore red-black properties */
656 /* Modifies Input: z */
658 /* The algorithm from this function is from _Introduction_To_Algorithms_ */
659 /***********************************************************************/
662 IT_delete_node(IntervalTree *it, IntervalTreeNode *z, long *low, long *high)
664 IntervalTreeNode *x, *y;
665 void *returnValue = z->data;
671 y= ((z->left == it->nil) || (z->right == it->nil)) ?
672 z : IT_get_successor(it, z);
673 x= (y->left == it->nil) ? y->right : y->left;
674 if (it->root == (x->parent = y->parent))
675 /* assignment of y->p to x->p is intentional */
678 if (y == y->parent->left)
683 if (y != z) { /* y should not be nil in this case */
686 Assert( (y!=it->nil),"y is nil in DeleteNode \n");
688 /* y is the node to splice out and x is its child */
690 y->maxHigh = INT_MIN;
694 z->left->parent=z->right->parent=y;
695 if (z == z->parent->left)
699 FixUpMaxHigh(it, x->parent);
706 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
707 IT_CheckAssumptions(it);
708 #elif defined(DEBUG_ASSERT)
709 Assert(!it->nil->red,"nil not black in ITDelete");
710 Assert((it->nil->maxHigh=LONG_MIN),"nil->maxHigh != LONG_MIN in ITDelete");
713 FixUpMaxHigh(it, x->parent);
717 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
718 IT_CheckAssumptions(it);
719 #elif defined(DEBUG_ASSERT)
720 Assert(!it->nil->red,"nil not black in ITDelete");
721 Assert((it->nil->maxHigh=LONG_MIN),"nil->maxHigh != LONG_MIN in ITDelete");
728 /***********************************************************************/
729 /* FUNCTION: Overlap */
731 /* INPUTS: [a1,a2] and [b1,b2] are the low and high endpoints of two */
732 /* closed intervals. */
734 /* OUTPUT: stack containing pointers to the nodes between [low,high] */
736 /* Modifies Input: none */
738 /* EFFECT: returns 1 if the intervals overlap, and 0 otherwise */
739 /***********************************************************************/
742 Overlap(int a1, int a2, int b1, int b2)
751 /***********************************************************************/
752 /* FUNCTION: Enumerate */
754 /* INPUTS: tree is the tree to look for intervals overlapping the */
755 /* closed interval [low,high] */
757 /* OUTPUT: stack containing pointers to the nodes overlapping */
760 /* Modifies Input: none */
762 /* EFFECT: Returns a stack containing pointers to nodes containing */
763 /* intervals which overlap [low,high] in O(max(N,k*log(N))) */
764 /* where N is the number of intervals in the tree and k is */
765 /* the number of overlapping intervals */
767 /* Note: This basic idea for this function comes from the */
768 /* _Introduction_To_Algorithms_ book by Cormen et al, but */
769 /* modifications were made to return all overlapping intervals */
770 /* instead of just the first overlapping interval as in the */
771 /* book. The natural way to do this would require recursive */
772 /* calls of a basic search function. I translated the */
773 /* recursive version into an interative version with a stack */
774 /* as described below. */
775 /***********************************************************************/
779 /* The basic idea for the function below is to take the IntervalSearch
780 * function from the book and modify to find all overlapping intervals
781 * instead of just one. This means that any time we take the left
782 * branch down the tree we must also check the right branch if and only if
783 * we find an overlapping interval in that left branch. Note this is a
784 * recursive condition because if we go left at the root then go left
785 * again at the first left child and find an overlap in the left subtree
786 * of the left child of root we must recursively check the right subtree
787 * of the left child of root as well as the right child of root.
790 IT_enumerate(IntervalTree *it, long low, long high, void *cbd,
791 void (*callback) (IntervalTreeNode *node, void *cbd))
793 IntervalTreeNode *x=it->root->left;
794 int stuffToDo = (x != it->nil);
796 /* Possible speed up: add min field to prune right searches */
799 Assert((it->recursionNodeStackTop == 1),
800 "recursionStack not empty when entering IntervalTree::Enumerate");
802 it->currentParent = 0;
805 if (Overlap(low,high,x->low,x->high) ) {
807 it->recursionNodeStack[it->currentParent].tryRightBranch=1;
809 if(x->left->maxHigh >= low) { /* implies x != nil */
810 if (it->recursionNodeStackTop == it->recursionNodeStackSize) {
811 it->recursionNodeStackSize *= 2;
812 it->recursionNodeStack = (it_recursion_node *)
813 yasm_xrealloc(it->recursionNodeStack,
814 it->recursionNodeStackSize * sizeof(it_recursion_node));
816 it->recursionNodeStack[it->recursionNodeStackTop].start_node = x;
817 it->recursionNodeStack[it->recursionNodeStackTop].tryRightBranch = 0;
818 it->recursionNodeStack[it->recursionNodeStackTop].parentIndex = it->currentParent;
819 it->currentParent = it->recursionNodeStackTop++;
824 stuffToDo = (x != it->nil);
825 while (!stuffToDo && (it->recursionNodeStackTop > 1)) {
826 if (it->recursionNodeStack[--it->recursionNodeStackTop].tryRightBranch) {
827 x=it->recursionNodeStack[it->recursionNodeStackTop].start_node->right;
828 it->currentParent=it->recursionNodeStack[it->recursionNodeStackTop].parentIndex;
829 it->recursionNodeStack[it->currentParent].tryRightBranch=1;
830 stuffToDo = (x != it->nil);
835 Assert((it->recursionNodeStackTop == 1),
836 "recursionStack not empty when exiting IntervalTree::Enumerate");
840 #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
843 CheckMaxHighFieldsHelper(const IntervalTree *it, IntervalTreeNode *y,
844 int currentHigh, int match)
847 match = CheckMaxHighFieldsHelper(it, y->left, currentHigh, match) ?
849 VERIFY(y->high <= currentHigh);
850 if (y->high == currentHigh)
852 match = CheckMaxHighFieldsHelper(it, y->right, currentHigh, match) ?
860 /* Make sure the maxHigh fields for everything makes sense. *
861 * If something is wrong, print a warning and exit */
863 CheckMaxHighFields(const IntervalTree *it, IntervalTreeNode *x)
866 CheckMaxHighFields(it, x->left);
867 if(!(CheckMaxHighFieldsHelper(it, x, x->maxHigh, 0) > 0)) {
868 fprintf(stderr, "error found in CheckMaxHighFields.\n");
871 CheckMaxHighFields(it, x->right);
876 IT_CheckAssumptions(const IntervalTree *it)
878 VERIFY(it->nil->low == INT_MIN);
879 VERIFY(it->nil->high == INT_MIN);
880 VERIFY(it->nil->maxHigh == INT_MIN);
881 VERIFY(it->root->low == INT_MAX);
882 VERIFY(it->root->high == INT_MAX);
883 VERIFY(it->root->maxHigh == INT_MAX);
884 VERIFY(it->nil->data == NULL);
885 VERIFY(it->root->data == NULL);
886 VERIFY(it->nil->red == 0);
887 VERIFY(it->root->red == 0);
888 CheckMaxHighFields(it, it->root->left);