1#include "util.h" 2 3#include <stdlib.h> 4#include <stdio.h> 5#include <limits.h> 6#include <math.h> 7#include "coretype.h" 8#include "inttree.h" 9 10#define VERIFY(condition) \ 11if (!(condition)) { \ 12fprintf(stderr, "Assumption \"%s\"\nFailed in file %s: at line:%i\n", \ 13#condition,__FILE__,__LINE__); \ 14abort();} 15 16/*#define DEBUG_ASSERT 1*/ 17 18#ifdef DEBUG_ASSERT 19static void Assert(int assertion, const char *error) 20{ 21 if (!assertion) { 22 fprintf(stderr, "Assertion Failed: %s\n", error); 23 abort(); 24 } 25} 26#endif 27 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. 33 */ 34/*#define CHECK_INTERVAL_TREE_ASSUMPTIONS 1*/ 35 36static IntervalTreeNode *ITN_create(long low, long high, void *data); 37 38static void LeftRotate(IntervalTree *, IntervalTreeNode *); 39static void RightRotate(IntervalTree *, IntervalTreeNode *); 40static void TreeInsertHelp(IntervalTree *, IntervalTreeNode *); 41static void TreePrintHelper(const IntervalTree *, IntervalTreeNode *); 42static void FixUpMaxHigh(IntervalTree *, IntervalTreeNode *); 43static void DeleteFixUp(IntervalTree *, IntervalTreeNode *); 44#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 45static void CheckMaxHighFields(const IntervalTree *, IntervalTreeNode *); 46static int CheckMaxHighFieldsHelper(const IntervalTree *, IntervalTreeNode *y, 47 const int currentHigh, int match); 48static void IT_CheckAssumptions(const IntervalTree *); 49#endif 50 51/* define a function to find the maximum of two objects. */ 52#define ITMax(a, b) ( (a > b) ? a : b ) 53 54IntervalTreeNode * 55ITN_create(long low, long high, void *data) 56{ 57 IntervalTreeNode *itn = yasm_xmalloc(sizeof(IntervalTreeNode)); 58 itn->data = data; 59 if (low < high) { 60 itn->low = low; 61 itn->high = high; 62 } else { 63 itn->low = high; 64 itn->high = low; 65 } 66 itn->maxHigh = high; 67 return itn; 68} 69 70IntervalTree * 71IT_create(void) 72{ 73 IntervalTree *it = yasm_xmalloc(sizeof(IntervalTree)); 74 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; 79 it->nil->red = 0; 80 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; 85 it->root->red = 0; 86 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; 93 94 return it; 95} 96 97/***********************************************************************/ 98/* FUNCTION: LeftRotate */ 99/**/ 100/* INPUTS: the node to rotate on */ 101/**/ 102/* OUTPUT: None */ 103/**/ 104/* Modifies Input: this, x */ 105/**/ 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/***********************************************************************/ 113 114static void 115LeftRotate(IntervalTree *it, IntervalTreeNode *x) 116{ 117 IntervalTreeNode *y; 118 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 127 * unchanged. 128 */ 129 130 y=x->right; 131 x->right=y->left; 132 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 */ 136 137 y->parent=x->parent; 138 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 141 */ 142 if (x == x->parent->left) 143 x->parent->left=y; 144 else 145 x->parent->right=y; 146 y->left=x; 147 x->parent=y; 148 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"); 157#endif 158} 159 160 161/***********************************************************************/ 162/* FUNCTION: RightRotate */ 163/**/ 164/* INPUTS: node to rotate on */ 165/**/ 166/* OUTPUT: None */ 167/**/ 168/* Modifies Input?: this, y */ 169/**/ 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/***********************************************************************/ 177 178 179static void 180RightRotate(IntervalTree *it, IntervalTreeNode *y) 181{ 182 IntervalTreeNode *x; 183 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 192 * unchanged. 193 */ 194 195 x=y->left; 196 y->left=x->right; 197 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 */ 201 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 204 */ 205 x->parent=y->parent; 206 if (y == y->parent->left) 207 y->parent->left=x; 208 else 209 y->parent->right=x; 210 x->right=y; 211 y->parent=x; 212 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"); 221#endif 222} 223 224/***********************************************************************/ 225/* FUNCTION: TreeInsertHelp */ 226/**/ 227/* INPUTS: z is the node to insert */ 228/**/ 229/* OUTPUT: none */ 230/**/ 231/* Modifies Input: this, z */ 232/**/ 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/***********************************************************************/ 238 239static void 240TreeInsertHelp(IntervalTree *it, IntervalTreeNode *z) 241{ 242 /* This function should only be called by InsertITTree (see above) */ 243 IntervalTreeNode* x; 244 IntervalTreeNode* y; 245 246 z->left=z->right=it->nil; 247 y=it->root; 248 x=it->root->left; 249 while( x != it->nil) { 250 y=x; 251 if (x->low > z->low) 252 x=x->left; 253 else /* x->low <= z->low */ 254 x=x->right; 255 } 256 z->parent=y; 257 if ((y == it->root) || (y->low > z->low)) 258 y->left=z; 259 else 260 y->right=z; 261 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"); 266#endif 267} 268 269 270/***********************************************************************/ 271/* FUNCTION: FixUpMaxHigh */ 272/**/ 273/* INPUTS: x is the node to start from*/ 274/**/ 275/* OUTPUT: none */ 276/**/ 277/* Modifies Input: this */ 278/**/ 279/* EFFECTS: Travels up to the root fixing the maxHigh fields after */ 280/* an insertion or deletion */ 281/***********************************************************************/ 282 283static void 284FixUpMaxHigh(IntervalTree *it, IntervalTreeNode *x) 285{ 286 while(x != it->root) { 287 x->maxHigh=ITMax(x->high,ITMax(x->left->maxHigh,x->right->maxHigh)); 288 x=x->parent; 289 } 290#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 291 IT_CheckAssumptions(it); 292#endif 293} 294 295/* Before calling InsertNode the node x should have its key set */ 296 297/***********************************************************************/ 298/* FUNCTION: InsertNode */ 299/**/ 300/* INPUTS: newInterval is the interval to insert*/ 301/**/ 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. */ 307/**/ 308/* Modifies Input: tree */ 309/**/ 310/* EFFECTS: Creates a node node which contains the appropriate key and */ 311/* info pointers and inserts it into the tree. */ 312/***********************************************************************/ 313 314IntervalTreeNode * 315IT_insert(IntervalTree *it, long low, long high, void *data) 316{ 317 IntervalTreeNode *x, *y, *newNode; 318 319 x = ITN_create(low, high, data); 320 TreeInsertHelp(it, x); 321 FixUpMaxHigh(it, x->parent); 322 newNode = x; 323 x->red=1; 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; 327 if (y->red) { 328 x->parent->red=0; 329 y->red=0; 330 x->parent->parent->red=1; 331 x=x->parent->parent; 332 } else { 333 if (x == x->parent->right) { 334 x=x->parent; 335 LeftRotate(it, x); 336 } 337 x->parent->red=0; 338 x->parent->parent->red=1; 339 RightRotate(it, x->parent->parent); 340 } 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; 345 if (y->red) { 346 x->parent->red=0; 347 y->red=0; 348 x->parent->parent->red=1; 349 x=x->parent->parent; 350 } else { 351 if (x == x->parent->left) { 352 x=x->parent; 353 RightRotate(it, x); 354 } 355 x->parent->red=0; 356 x->parent->parent->red=1; 357 LeftRotate(it, x->parent->parent); 358 } 359 } 360 } 361 it->root->left->red=0; 362 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"); 370#endif 371 return newNode; 372} 373 374/***********************************************************************/ 375/* FUNCTION: GetSuccessorOf */ 376/**/ 377/* INPUTS: x is the node we want the succesor of */ 378/**/ 379/* OUTPUT: This function returns the successor of x or NULL if no */ 380/* successor exists. */ 381/**/ 382/* Modifies Input: none */ 383/**/ 384/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ 385/***********************************************************************/ 386 387IntervalTreeNode * 388IT_get_successor(const IntervalTree *it, IntervalTreeNode *x) 389{ 390 IntervalTreeNode *y; 391 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 */ 394 y=y->left; 395 return y; 396 } else { 397 y=x->parent; 398 while(x == y->right) { /* sentinel used instead of checking for nil */ 399 x=y; 400 y=y->parent; 401 } 402 if (y == it->root) 403 return(it->nil); 404 return y; 405 } 406} 407 408/***********************************************************************/ 409/* FUNCTION: GetPredecessorOf */ 410/**/ 411/* INPUTS: x is the node to get predecessor of */ 412/**/ 413/* OUTPUT: This function returns the predecessor of x or NULL if no */ 414/* predecessor exists. */ 415/**/ 416/* Modifies Input: none */ 417/**/ 418/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ 419/***********************************************************************/ 420 421IntervalTreeNode * 422IT_get_predecessor(const IntervalTree *it, IntervalTreeNode *x) 423{ 424 IntervalTreeNode *y; 425 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 */ 428 y=y->right; 429 return y; 430 } else { 431 y=x->parent; 432 while(x == y->left) { 433 if (y == it->root) 434 return(it->nil); 435 x=y; 436 y=y->parent; 437 } 438 return y; 439 } 440} 441 442/***********************************************************************/ 443/* FUNCTION: Print */ 444/**/ 445/* INPUTS: none */ 446/**/ 447/* OUTPUT: none */ 448/**/ 449/* EFFECTS: This function recursively prints the nodes of the tree */ 450/* inorder. */ 451/**/ 452/* Modifies Input: none */ 453/**/ 454/* Note: This function should only be called from ITTreePrint */ 455/***********************************************************************/ 456 457static void 458ITN_print(const IntervalTreeNode *itn, IntervalTreeNode *nil, 459 IntervalTreeNode *root) 460{ 461 printf(", l=%li, h=%li, mH=%li", itn->low, itn->high, itn->maxHigh); 462 printf(" l->low="); 463 if (itn->left == nil) 464 printf("NULL"); 465 else 466 printf("%li", itn->left->low); 467 printf(" r->low="); 468 if (itn->right == nil) 469 printf("NULL"); 470 else 471 printf("%li", itn->right->low); 472 printf(" p->low="); 473 if (itn->parent == root) 474 printf("NULL"); 475 else 476 printf("%li", itn->parent->low); 477 printf(" red=%i\n", itn->red); 478} 479 480static void 481TreePrintHelper(const IntervalTree *it, IntervalTreeNode *x) 482{ 483 if (x != it->nil) { 484 TreePrintHelper(it, x->left); 485 ITN_print(x, it->nil, it->root); 486 TreePrintHelper(it, x->right); 487 } 488} 489 490void 491IT_destroy(IntervalTree *it) 492{ 493 IntervalTreeNode *x = it->root->left; 494 SLIST_HEAD(node_head, nodeent) 495 stuffToFree = SLIST_HEAD_INITIALIZER(stuffToFree); 496 struct nodeent { 497 SLIST_ENTRY(nodeent) link; 498 struct IntervalTreeNode *node; 499 } *np; 500 501 if (x != it->nil) { 502 if (x->left != it->nil) { 503 np = yasm_xmalloc(sizeof(struct nodeent)); 504 np->node = x->left; 505 SLIST_INSERT_HEAD(&stuffToFree, np, link); 506 } 507 if (x->right != it->nil) { 508 np = yasm_xmalloc(sizeof(struct nodeent)); 509 np->node = x->right; 510 SLIST_INSERT_HEAD(&stuffToFree, np, link); 511 } 512 yasm_xfree(x); 513 while (!SLIST_EMPTY(&stuffToFree)) { 514 np = SLIST_FIRST(&stuffToFree); 515 x = np->node; 516 SLIST_REMOVE_HEAD(&stuffToFree, link); 517 yasm_xfree(np); 518 519 if (x->left != it->nil) { 520 np = yasm_xmalloc(sizeof(struct nodeent)); 521 np->node = x->left; 522 SLIST_INSERT_HEAD(&stuffToFree, np, link); 523 } 524 if (x->right != it->nil) { 525 np = yasm_xmalloc(sizeof(struct nodeent)); 526 np->node = x->right; 527 SLIST_INSERT_HEAD(&stuffToFree, np, link); 528 } 529 yasm_xfree(x); 530 } 531 } 532 533 yasm_xfree(it->nil); 534 yasm_xfree(it->root); 535 yasm_xfree(it->recursionNodeStack); 536 yasm_xfree(it); 537} 538 539 540/***********************************************************************/ 541/* FUNCTION: Print */ 542/**/ 543/* INPUTS: none */ 544/**/ 545/* OUTPUT: none */ 546/**/ 547/* EFFECT: This function recursively prints the nodes of the tree */ 548/* inorder. */ 549/**/ 550/* Modifies Input: none */ 551/**/ 552/***********************************************************************/ 553 554void 555IT_print(const IntervalTree *it) 556{ 557 TreePrintHelper(it, it->root->left); 558} 559 560/***********************************************************************/ 561/* FUNCTION: DeleteFixUp */ 562/**/ 563/* INPUTS: x is the child of the spliced */ 564/* out node in DeleteNode. */ 565/**/ 566/* OUTPUT: none */ 567/**/ 568/* EFFECT: Performs rotations and changes colors to restore red-black */ 569/* properties after a node is deleted */ 570/**/ 571/* Modifies Input: this, x */ 572/**/ 573/* The algorithm from this function is from _Introduction_To_Algorithms_ */ 574/***********************************************************************/ 575 576static void 577DeleteFixUp(IntervalTree *it, IntervalTreeNode *x) 578{ 579 IntervalTreeNode *w; 580 IntervalTreeNode *rootLeft = it->root->left; 581 582 while ((!x->red) && (rootLeft != x)) { 583 if (x == x->parent->left) { 584 w=x->parent->right; 585 if (w->red) { 586 w->red=0; 587 x->parent->red=1; 588 LeftRotate(it, x->parent); 589 w=x->parent->right; 590 } 591 if ( (!w->right->red) && (!w->left->red) ) { 592 w->red=1; 593 x=x->parent; 594 } else { 595 if (!w->right->red) { 596 w->left->red=0; 597 w->red=1; 598 RightRotate(it, w); 599 w=x->parent->right; 600 } 601 w->red=x->parent->red; 602 x->parent->red=0; 603 w->right->red=0; 604 LeftRotate(it, x->parent); 605 x=rootLeft; /* this is to exit while loop */ 606 } 607 } else { /* the code below is has left and right switched from above */ 608 w=x->parent->left; 609 if (w->red) { 610 w->red=0; 611 x->parent->red=1; 612 RightRotate(it, x->parent); 613 w=x->parent->left; 614 } 615 if ((!w->right->red) && (!w->left->red)) { 616 w->red=1; 617 x=x->parent; 618 } else { 619 if (!w->left->red) { 620 w->right->red=0; 621 w->red=1; 622 LeftRotate(it, w); 623 w=x->parent->left; 624 } 625 w->red=x->parent->red; 626 x->parent->red=0; 627 w->left->red=0; 628 RightRotate(it, x->parent); 629 x=rootLeft; /* this is to exit while loop */ 630 } 631 } 632 } 633 x->red=0; 634 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"); 641#endif 642} 643 644 645/***********************************************************************/ 646/* FUNCTION: DeleteNode */ 647/**/ 648/* INPUTS: tree is the tree to delete node z from */ 649/**/ 650/* OUTPUT: returns the Interval stored at deleted node */ 651/**/ 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 */ 655/**/ 656/* Modifies Input: z */ 657/**/ 658/* The algorithm from this function is from _Introduction_To_Algorithms_ */ 659/***********************************************************************/ 660 661void * 662IT_delete_node(IntervalTree *it, IntervalTreeNode *z, long *low, long *high) 663{ 664 IntervalTreeNode *x, *y; 665 void *returnValue = z->data; 666 if (low) 667 *low = z->low; 668 if (high) 669 *high = z->high; 670 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 */ 676 it->root->left=x; 677 else { 678 if (y == y->parent->left) 679 y->parent->left=x; 680 else 681 y->parent->right=x; 682 } 683 if (y != z) { /* y should not be nil in this case */ 684 685#ifdef DEBUG_ASSERT 686 Assert( (y!=it->nil),"y is nil in DeleteNode \n"); 687#endif 688 /* y is the node to splice out and x is its child */ 689 690 y->maxHigh = INT_MIN; 691 y->left=z->left; 692 y->right=z->right; 693 y->parent=z->parent; 694 z->left->parent=z->right->parent=y; 695 if (z == z->parent->left) 696 z->parent->left=y; 697 else 698 z->parent->right=y; 699 FixUpMaxHigh(it, x->parent); 700 if (!(y->red)) { 701 y->red = z->red; 702 DeleteFixUp(it, x); 703 } else 704 y->red = z->red; 705 yasm_xfree(z); 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"); 711#endif 712 } else { 713 FixUpMaxHigh(it, x->parent); 714 if (!(y->red)) 715 DeleteFixUp(it, x); 716 yasm_xfree(y); 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"); 722#endif 723 } 724 return returnValue; 725} 726 727 728/***********************************************************************/ 729/* FUNCTION: Overlap */ 730/**/ 731/* INPUTS: [a1,a2] and [b1,b2] are the low and high endpoints of two */ 732/* closed intervals. */ 733/**/ 734/* OUTPUT: stack containing pointers to the nodes between [low,high] */ 735/**/ 736/* Modifies Input: none */ 737/**/ 738/* EFFECT: returns 1 if the intervals overlap, and 0 otherwise */ 739/***********************************************************************/ 740 741static int 742Overlap(int a1, int a2, int b1, int b2) 743{ 744 if (a1 <= b1) 745 return (b1 <= a2); 746 else 747 return (a1 <= b2); 748} 749 750 751/***********************************************************************/ 752/* FUNCTION: Enumerate */ 753/**/ 754/* INPUTS: tree is the tree to look for intervals overlapping the */ 755/* closed interval [low,high] */ 756/**/ 757/* OUTPUT: stack containing pointers to the nodes overlapping */ 758/* [low,high] */ 759/**/ 760/* Modifies Input: none */ 761/**/ 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 */ 766/**/ 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/***********************************************************************/ 776 777 778 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. 788 */ 789void 790IT_enumerate(IntervalTree *it, long low, long high, void *cbd, 791 void (*callback) (IntervalTreeNode *node, void *cbd)) 792{ 793 IntervalTreeNode *x=it->root->left; 794 int stuffToDo = (x != it->nil); 795 796 /* Possible speed up: add min field to prune right searches */ 797 798#ifdef DEBUG_ASSERT 799 Assert((it->recursionNodeStackTop == 1), 800 "recursionStack not empty when entering IntervalTree::Enumerate"); 801#endif 802 it->currentParent = 0; 803 804 while (stuffToDo) { 805 if (Overlap(low,high,x->low,x->high) ) { 806 callback(x, cbd); 807 it->recursionNodeStack[it->currentParent].tryRightBranch=1; 808 } 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)); 815 } 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++; 820 x = x->left; 821 } else { 822 x = x->right; 823 } 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); 831 } 832 } 833 } 834#ifdef DEBUG_ASSERT 835 Assert((it->recursionNodeStackTop == 1), 836 "recursionStack not empty when exiting IntervalTree::Enumerate"); 837#endif 838} 839 840#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 841 842static int 843CheckMaxHighFieldsHelper(const IntervalTree *it, IntervalTreeNode *y, 844 int currentHigh, int match) 845{ 846 if (y != it->nil) { 847 match = CheckMaxHighFieldsHelper(it, y->left, currentHigh, match) ? 848 1 : match; 849 VERIFY(y->high <= currentHigh); 850 if (y->high == currentHigh) 851 match = 1; 852 match = CheckMaxHighFieldsHelper(it, y->right, currentHigh, match) ? 853 1 : match; 854 } 855 return match; 856} 857 858 859 860/* Make sure the maxHigh fields for everything makes sense. * 861 * If something is wrong, print a warning and exit */ 862static void 863CheckMaxHighFields(const IntervalTree *it, IntervalTreeNode *x) 864{ 865 if (x != it->nil) { 866 CheckMaxHighFields(it, x->left); 867 if(!(CheckMaxHighFieldsHelper(it, x, x->maxHigh, 0) > 0)) { 868 fprintf(stderr, "error found in CheckMaxHighFields.\n"); 869 abort(); 870 } 871 CheckMaxHighFields(it, x->right); 872 } 873} 874 875static void 876IT_CheckAssumptions(const IntervalTree *it) 877{ 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); 889} 890#endif 891 892