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) \
11 if (!(condition)) { \
12 fprintf(stderr, "Assumption \"%s\"\nFailed in file %s: at line:%i\n", \
13 #condition,__FILE__,__LINE__); \
14 abort();}
15
16 /*#define DEBUG_ASSERT 1*/
17
18 #ifdef DEBUG_ASSERT
Assert(int assertion,const char * error)19 static 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
36 static IntervalTreeNode *ITN_create(long low, long high, void *data);
37
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 *);
49 #endif
50
51 /* define a function to find the maximum of two objects. */
52 #define ITMax(a, b) ( (a > b) ? a : b )
53
54 IntervalTreeNode *
ITN_create(long low,long high,void * data)55 ITN_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
70 IntervalTree *
IT_create(void)71 IT_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
114 static void
LeftRotate(IntervalTree * it,IntervalTreeNode * x)115 LeftRotate(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
179 static void
RightRotate(IntervalTree * it,IntervalTreeNode * y)180 RightRotate(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
239 static void
TreeInsertHelp(IntervalTree * it,IntervalTreeNode * z)240 TreeInsertHelp(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
283 static void
FixUpMaxHigh(IntervalTree * it,IntervalTreeNode * x)284 FixUpMaxHigh(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
314 IntervalTreeNode *
IT_insert(IntervalTree * it,long low,long high,void * data)315 IT_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
387 IntervalTreeNode *
IT_get_successor(const IntervalTree * it,IntervalTreeNode * x)388 IT_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
421 IntervalTreeNode *
IT_get_predecessor(const IntervalTree * it,IntervalTreeNode * x)422 IT_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
457 static void
ITN_print(const IntervalTreeNode * itn,IntervalTreeNode * nil,IntervalTreeNode * root)458 ITN_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
480 static void
TreePrintHelper(const IntervalTree * it,IntervalTreeNode * x)481 TreePrintHelper(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
490 void
IT_destroy(IntervalTree * it)491 IT_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
554 void
IT_print(const IntervalTree * it)555 IT_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
576 static void
DeleteFixUp(IntervalTree * it,IntervalTreeNode * x)577 DeleteFixUp(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
661 void *
IT_delete_node(IntervalTree * it,IntervalTreeNode * z,long * low,long * high)662 IT_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
741 static int
Overlap(int a1,int a2,int b1,int b2)742 Overlap(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 */
789 void
IT_enumerate(IntervalTree * it,long low,long high,void * cbd,void (* callback)(IntervalTreeNode * node,void * cbd))790 IT_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
842 static int
CheckMaxHighFieldsHelper(const IntervalTree * it,IntervalTreeNode * y,int currentHigh,int match)843 CheckMaxHighFieldsHelper(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 */
862 static void
CheckMaxHighFields(const IntervalTree * it,IntervalTreeNode * x)863 CheckMaxHighFields(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
875 static void
IT_CheckAssumptions(const IntervalTree * it)876 IT_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