145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include "util.h" 245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include <stdlib.h> 445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include <stdio.h> 545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include <limits.h> 645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include <math.h> 745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include "coretype.h" 845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include "inttree.h" 945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define VERIFY(condition) \ 1145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgif (!(condition)) { \ 1245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgfprintf(stderr, "Assumption \"%s\"\nFailed in file %s: at line:%i\n", \ 1345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#condition,__FILE__,__LINE__); \ 1445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgabort();} 1545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/*#define DEBUG_ASSERT 1*/ 1745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef DEBUG_ASSERT 1945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void Assert(int assertion, const char *error) 2045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 2145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!assertion) { 2245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org fprintf(stderr, "Assertion Failed: %s\n", error); 2345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org abort(); 2445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 2545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 2645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 2745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 2845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* If the symbol CHECK_INTERVAL_TREE_ASSUMPTIONS is defined then the 2945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * code does a lot of extra checking to make sure certain assumptions 3045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * are satisfied. This only needs to be done if you suspect bugs are 3145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * present or if you make significant changes and want to make sure 3245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * your changes didn't mess anything up. 3345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 3445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/*#define CHECK_INTERVAL_TREE_ASSUMPTIONS 1*/ 3545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic IntervalTreeNode *ITN_create(long low, long high, void *data); 3745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void LeftRotate(IntervalTree *, IntervalTreeNode *); 3945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void RightRotate(IntervalTree *, IntervalTreeNode *); 4045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void TreeInsertHelp(IntervalTree *, IntervalTreeNode *); 4145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void TreePrintHelper(const IntervalTree *, IntervalTreeNode *); 4245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void FixUpMaxHigh(IntervalTree *, IntervalTreeNode *); 4345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void DeleteFixUp(IntervalTree *, IntervalTreeNode *); 4445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 4545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void CheckMaxHighFields(const IntervalTree *, IntervalTreeNode *); 4645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic int CheckMaxHighFieldsHelper(const IntervalTree *, IntervalTreeNode *y, 4745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org const int currentHigh, int match); 4845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void IT_CheckAssumptions(const IntervalTree *); 4945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 5045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 5145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* define a function to find the maximum of two objects. */ 5245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define ITMax(a, b) ( (a > b) ? a : b ) 5345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 5445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode * 5545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgITN_create(long low, long high, void *data) 5645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 5745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *itn = yasm_xmalloc(sizeof(IntervalTreeNode)); 5845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org itn->data = data; 5945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (low < high) { 6045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org itn->low = low; 6145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org itn->high = high; 6245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 6345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org itn->low = high; 6445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org itn->high = low; 6545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 6645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org itn->maxHigh = high; 6745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return itn; 6845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 6945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 7045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTree * 7145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_create(void) 7245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 7345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTree *it = yasm_xmalloc(sizeof(IntervalTree)); 7445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 7545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->nil = ITN_create(LONG_MIN, LONG_MIN, NULL); 7645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->nil->left = it->nil; 7745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->nil->right = it->nil; 7845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->nil->parent = it->nil; 7945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->nil->red = 0; 8045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 8145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root = ITN_create(LONG_MAX, LONG_MAX, NULL); 8245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root->left = it->nil; 8345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root->right = it->nil; 8445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root->parent = it->nil; 8545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root->red = 0; 8645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 8745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* the following are used for the Enumerate function */ 8845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStackSize = 128; 8945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack = (it_recursion_node *) 9045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xmalloc(it->recursionNodeStackSize*sizeof(it_recursion_node)); 9145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStackTop = 1; 9245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack[0].start_node = NULL; 9345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 9445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return it; 9545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 9645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 9745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 9845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: LeftRotate */ 9945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 10045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: the node to rotate on */ 10145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 10245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: None */ 10345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 10445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: this, x */ 10545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 10645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ 10745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ 10845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* makes the parent of x be to the left of x, x the parent of */ 10945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* its parent before the rotation and fixes other pointers */ 11045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* accordingly. Also updates the maxHigh fields of x and y */ 11145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* after rotation. */ 11245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 11345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 11445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 11545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgLeftRotate(IntervalTree *it, IntervalTreeNode *x) 11645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 11745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *y; 11845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 11945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* I originally wrote this function to use the sentinel for 12045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * nil to avoid checking for nil. However this introduces a 12145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * very subtle bug because sometimes this function modifies 12245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * the parent pointer of nil. This can be a problem if a 12345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * function which calls LeftRotate also uses the nil sentinel 12445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * and expects the nil sentinel's parent pointer to be unchanged 12545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * after calling this function. For example, when DeleteFixUP 12645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * calls LeftRotate it expects the parent pointer of nil to be 12745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * unchanged. 12845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 12945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 13045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=x->right; 13145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->right=y->left; 13245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 13345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y->left != it->nil) 13445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->left->parent=x; /* used to use sentinel here */ 13545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* and do an unconditional assignment instead of testing for nil */ 13645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 13745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent=x->parent; 13845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 13945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* Instead of checking if x->parent is the root as in the book, we 14045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * count on the root sentinel to implicitly take care of this case 14145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 14245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x == x->parent->left) 14345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->left=y; 14445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 14545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->right=y; 14645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->left=x; 14745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent=y; 14845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 14945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->maxHigh=ITMax(x->left->maxHigh,ITMax(x->right->maxHigh,x->high)); 15045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->maxHigh=ITMax(x->maxHigh,ITMax(y->right->maxHigh,y->high)); 15145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 15245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 15345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#elif defined(DEBUG_ASSERT) 15445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not red in ITLeftRotate"); 15545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=LONG_MIN), 15645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "nil->maxHigh != LONG_MIN in ITLeftRotate"); 15745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 15845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 15945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 16045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 16145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 16245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: RightRotate */ 16345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 16445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: node to rotate on */ 16545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 16645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: None */ 16745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 16845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input?: this, y */ 16945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 17045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ 17145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ 17245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* makes the parent of x be to the left of x, x the parent of */ 17345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* its parent before the rotation and fixes other pointers */ 17445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* accordingly. Also updates the maxHigh fields of x and y */ 17545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* after rotation. */ 17645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 17745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 17845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 17945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 18045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgRightRotate(IntervalTree *it, IntervalTreeNode *y) 18145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 18245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *x; 18345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 18445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* I originally wrote this function to use the sentinel for 18545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * nil to avoid checking for nil. However this introduces a 18645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * very subtle bug because sometimes this function modifies 18745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * the parent pointer of nil. This can be a problem if a 18845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * function which calls LeftRotate also uses the nil sentinel 18945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * and expects the nil sentinel's parent pointer to be unchanged 19045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * after calling this function. For example, when DeleteFixUP 19145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * calls LeftRotate it expects the parent pointer of nil to be 19245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * unchanged. 19345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 19445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 19545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=y->left; 19645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->left=x->right; 19745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 19845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (it->nil != x->right) 19945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->right->parent=y; /*used to use sentinel here */ 20045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* and do an unconditional assignment instead of testing for nil */ 20145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 20245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* Instead of checking if x->parent is the root as in the book, we 20345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * count on the root sentinel to implicitly take care of this case 20445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 20545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent=y->parent; 20645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y == y->parent->left) 20745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent->left=x; 20845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 20945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent->right=x; 21045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->right=y; 21145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent=x; 21245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 21345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->maxHigh=ITMax(y->left->maxHigh,ITMax(y->right->maxHigh,y->high)); 21445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->maxHigh=ITMax(x->left->maxHigh,ITMax(y->maxHigh,x->high)); 21545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 21645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 21745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#elif defined(DEBUG_ASSERT) 21845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not red in ITRightRotate"); 21945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=LONG_MIN), 22045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "nil->maxHigh != LONG_MIN in ITRightRotate"); 22145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 22245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 22345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 22445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 22545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: TreeInsertHelp */ 22645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 22745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: z is the node to insert */ 22845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 22945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: none */ 23045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 23145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: this, z */ 23245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 23345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECTS: Inserts z into the tree as if it were a regular binary tree */ 23445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* using the algorithm described in _Introduction_To_Algorithms_ */ 23545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* by Cormen et al. This funciton is only intended to be called */ 23645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* by the InsertTree function and not by the user */ 23745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 23845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 23945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 24045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgTreeInsertHelp(IntervalTree *it, IntervalTreeNode *z) 24145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 24245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* This function should only be called by InsertITTree (see above) */ 24345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode* x; 24445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode* y; 24545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 24645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org z->left=z->right=it->nil; 24745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=it->root; 24845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=it->root->left; 24945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while( x != it->nil) { 25045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=x; 25145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x->low > z->low) 25245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->left; 25345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else /* x->low <= z->low */ 25445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->right; 25545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 25645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org z->parent=y; 25745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((y == it->root) || (y->low > z->low)) 25845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->left=z; 25945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 26045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->right=z; 26145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 26245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#if defined(DEBUG_ASSERT) 26345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not red in ITTreeInsertHelp"); 26445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=INT_MIN), 26545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "nil->maxHigh != INT_MIN in ITTreeInsertHelp"); 26645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 26745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 26845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 26945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 27045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 27145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: FixUpMaxHigh */ 27245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 27345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: x is the node to start from*/ 27445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 27545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: none */ 27645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 27745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: this */ 27845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 27945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECTS: Travels up to the root fixing the maxHigh fields after */ 28045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* an insertion or deletion */ 28145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 28245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 28345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 28445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgFixUpMaxHigh(IntervalTree *it, IntervalTreeNode *x) 28545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 28645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while(x != it->root) { 28745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->maxHigh=ITMax(x->high,ITMax(x->left->maxHigh,x->right->maxHigh)); 28845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent; 28945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 29045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 29145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 29245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 29345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 29445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 29545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Before calling InsertNode the node x should have its key set */ 29645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 29745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 29845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: InsertNode */ 29945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 30045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: newInterval is the interval to insert*/ 30145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 30245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: This function returns a pointer to the newly inserted node */ 30345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* which is guarunteed to be valid until this node is deleted. */ 30445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* What this means is if another data structure stores this */ 30545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* pointer then the tree does not need to be searched when this */ 30645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* is to be deleted. */ 30745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 30845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: tree */ 30945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 31045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECTS: Creates a node node which contains the appropriate key and */ 31145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* info pointers and inserts it into the tree. */ 31245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 31345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 31445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode * 31545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_insert(IntervalTree *it, long low, long high, void *data) 31645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 31745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *x, *y, *newNode; 31845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 31945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x = ITN_create(low, high, data); 32045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TreeInsertHelp(it, x); 32145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org FixUpMaxHigh(it, x->parent); 32245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org newNode = x; 32345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->red=1; 32445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while(x->parent->red) { /* use sentinel instead of checking for root */ 32545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x->parent == x->parent->parent->left) { 32645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=x->parent->parent->right; 32745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y->red) { 32845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=0; 32945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->red=0; 33045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->parent->red=1; 33145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent->parent; 33245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 33345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x == x->parent->right) { 33445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent; 33545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LeftRotate(it, x); 33645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 33745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=0; 33845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->parent->red=1; 33945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org RightRotate(it, x->parent->parent); 34045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 34145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { /* case for x->parent == x->parent->parent->right */ 34245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* this part is just like the section above with */ 34345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* left and right interchanged */ 34445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=x->parent->parent->left; 34545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y->red) { 34645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=0; 34745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->red=0; 34845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->parent->red=1; 34945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent->parent; 35045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 35145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x == x->parent->left) { 35245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent; 35345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org RightRotate(it, x); 35445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 35545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=0; 35645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->parent->red=1; 35745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LeftRotate(it, x->parent->parent); 35845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 35945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 36045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 36145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root->left->red=0; 36245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 36345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 36445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 36545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#elif defined(DEBUG_ASSERT) 36645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not red in ITTreeInsert"); 36745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->root->red,"root not red in ITTreeInsert"); 36845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=LONG_MIN), 36945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "nil->maxHigh != LONG_MIN in ITTreeInsert"); 37045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 37145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return newNode; 37245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 37345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 37445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 37545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: GetSuccessorOf */ 37645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 37745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: x is the node we want the succesor of */ 37845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 37945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: This function returns the successor of x or NULL if no */ 38045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* successor exists. */ 38145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 38245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: none */ 38345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 38445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ 38545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 38645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 38745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode * 38845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_get_successor(const IntervalTree *it, IntervalTreeNode *x) 38945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 39045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *y; 39145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 39245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (it->nil != (y = x->right)) { /* assignment to y is intentional */ 39345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while(y->left != it->nil) /* returns the minium of the right subtree of x */ 39445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=y->left; 39545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return y; 39645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 39745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=x->parent; 39845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while(x == y->right) { /* sentinel used instead of checking for nil */ 39945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=y; 40045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=y->parent; 40145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 40245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y == it->root) 40345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return(it->nil); 40445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return y; 40545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 40645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 40745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 40845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 40945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: GetPredecessorOf */ 41045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 41145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: x is the node to get predecessor of */ 41245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 41345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: This function returns the predecessor of x or NULL if no */ 41445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* predecessor exists. */ 41545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 41645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: none */ 41745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 41845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Note: uses the algorithm in _Introduction_To_Algorithms_ */ 41945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 42045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 42145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIntervalTreeNode * 42245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_get_predecessor(const IntervalTree *it, IntervalTreeNode *x) 42345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 42445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *y; 42545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 42645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (it->nil != (y = x->left)) { /* assignment to y is intentional */ 42745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while(y->right != it->nil) /* returns the maximum of the left subtree of x */ 42845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=y->right; 42945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return y; 43045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 43145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=x->parent; 43245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while(x == y->left) { 43345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y == it->root) 43445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return(it->nil); 43545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=y; 43645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y=y->parent; 43745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 43845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return y; 43945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 44045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 44145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 44245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 44345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: Print */ 44445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 44545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: none */ 44645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 44745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: none */ 44845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 44945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECTS: This function recursively prints the nodes of the tree */ 45045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* inorder. */ 45145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 45245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: none */ 45345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 45445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Note: This function should only be called from ITTreePrint */ 45545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 45645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 45745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 45845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgITN_print(const IntervalTreeNode *itn, IntervalTreeNode *nil, 45945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *root) 46045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 46145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf(", l=%li, h=%li, mH=%li", itn->low, itn->high, itn->maxHigh); 46245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf(" l->low="); 46345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (itn->left == nil) 46445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf("NULL"); 46545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 46645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf("%li", itn->left->low); 46745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf(" r->low="); 46845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (itn->right == nil) 46945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf("NULL"); 47045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 47145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf("%li", itn->right->low); 47245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf(" p->low="); 47345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (itn->parent == root) 47445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf("NULL"); 47545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 47645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf("%li", itn->parent->low); 47745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org printf(" red=%i\n", itn->red); 47845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 47945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 48045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 48145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgTreePrintHelper(const IntervalTree *it, IntervalTreeNode *x) 48245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 48345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x != it->nil) { 48445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TreePrintHelper(it, x->left); 48545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org ITN_print(x, it->nil, it->root); 48645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TreePrintHelper(it, x->right); 48745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 48845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 48945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 49045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid 49145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_destroy(IntervalTree *it) 49245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 49345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *x = it->root->left; 494a1b5233e6d340f45f4846131fec9d0b92e203ce4hbono@chromium.org SLIST_HEAD(node_head, nodeent) 495a1b5233e6d340f45f4846131fec9d0b92e203ce4hbono@chromium.org stuffToFree = SLIST_HEAD_INITIALIZER(stuffToFree); 49645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct nodeent { 49745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_ENTRY(nodeent) link; 49845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct IntervalTreeNode *node; 49945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } *np; 50045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 50145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x != it->nil) { 50245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x->left != it->nil) { 50345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np = yasm_xmalloc(sizeof(struct nodeent)); 50445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np->node = x->left; 50545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_INSERT_HEAD(&stuffToFree, np, link); 50645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 50745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x->right != it->nil) { 50845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np = yasm_xmalloc(sizeof(struct nodeent)); 50945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np->node = x->right; 51045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_INSERT_HEAD(&stuffToFree, np, link); 51145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 51245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(x); 51345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (!SLIST_EMPTY(&stuffToFree)) { 51445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np = SLIST_FIRST(&stuffToFree); 51545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x = np->node; 51645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_REMOVE_HEAD(&stuffToFree, link); 51745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(np); 51845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 51945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x->left != it->nil) { 52045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np = yasm_xmalloc(sizeof(struct nodeent)); 52145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np->node = x->left; 52245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_INSERT_HEAD(&stuffToFree, np, link); 52345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 52445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x->right != it->nil) { 52545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np = yasm_xmalloc(sizeof(struct nodeent)); 52645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org np->node = x->right; 52745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_INSERT_HEAD(&stuffToFree, np, link); 52845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 52945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(x); 53045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 53145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 53245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 53345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(it->nil); 53445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(it->root); 53545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(it->recursionNodeStack); 53645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(it); 53745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 53845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 53945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 54045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 54145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: Print */ 54245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 54345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: none */ 54445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 54545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: none */ 54645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 54745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECT: This function recursively prints the nodes of the tree */ 54845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* inorder. */ 54945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 55045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: none */ 55145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 55245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 55345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 55445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid 55545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_print(const IntervalTree *it) 55645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 55745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TreePrintHelper(it, it->root->left); 55845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 55945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 56045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 56145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: DeleteFixUp */ 56245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 56345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: x is the child of the spliced */ 56445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* out node in DeleteNode. */ 56545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 56645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: none */ 56745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 56845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECT: Performs rotations and changes colors to restore red-black */ 56945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* properties after a node is deleted */ 57045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 57145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: this, x */ 57245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 57345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* The algorithm from this function is from _Introduction_To_Algorithms_ */ 57445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 57545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 57645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 57745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgDeleteFixUp(IntervalTree *it, IntervalTreeNode *x) 57845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 57945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *w; 58045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *rootLeft = it->root->left; 58145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 58245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while ((!x->red) && (rootLeft != x)) { 58345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x == x->parent->left) { 58445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w=x->parent->right; 58545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (w->red) { 58645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=0; 58745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=1; 58845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LeftRotate(it, x->parent); 58945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w=x->parent->right; 59045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 59145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ( (!w->right->red) && (!w->left->red) ) { 59245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=1; 59345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent; 59445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 59545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!w->right->red) { 59645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->left->red=0; 59745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=1; 59845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org RightRotate(it, w); 59945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w=x->parent->right; 60045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 60145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=x->parent->red; 60245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=0; 60345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->right->red=0; 60445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LeftRotate(it, x->parent); 60545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=rootLeft; /* this is to exit while loop */ 60645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 60745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { /* the code below is has left and right switched from above */ 60845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w=x->parent->left; 60945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (w->red) { 61045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=0; 61145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=1; 61245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org RightRotate(it, x->parent); 61345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w=x->parent->left; 61445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 61545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((!w->right->red) && (!w->left->red)) { 61645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=1; 61745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=x->parent; 61845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 61945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!w->left->red) { 62045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->right->red=0; 62145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=1; 62245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LeftRotate(it, w); 62345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w=x->parent->left; 62445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 62545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->red=x->parent->red; 62645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->parent->red=0; 62745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org w->left->red=0; 62845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org RightRotate(it, x->parent); 62945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=rootLeft; /* this is to exit while loop */ 63045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 63145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 63245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 63345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x->red=0; 63445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 63545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 63645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 63745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#elif defined(DEBUG_ASSERT) 63845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not black in ITDeleteFixUp"); 63945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=LONG_MIN), 64045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "nil->maxHigh != LONG_MIN in ITDeleteFixUp"); 64145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 64245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 64345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 64445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 64545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 64645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: DeleteNode */ 64745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 64845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: tree is the tree to delete node z from */ 64945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 65045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: returns the Interval stored at deleted node */ 65145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 65245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECT: Deletes z from tree and but don't call destructor */ 65345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Then calls FixUpMaxHigh to fix maxHigh fields then calls */ 65445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* ITDeleteFixUp to restore red-black properties */ 65545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 65645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: z */ 65745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 65845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* The algorithm from this function is from _Introduction_To_Algorithms_ */ 65945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 66045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 66145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid * 66245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_delete_node(IntervalTree *it, IntervalTreeNode *z, long *low, long *high) 66345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 66445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *x, *y; 66545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org void *returnValue = z->data; 66645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (low) 66745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *low = z->low; 66845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (high) 66945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *high = z->high; 67045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 67145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y= ((z->left == it->nil) || (z->right == it->nil)) ? 67245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org z : IT_get_successor(it, z); 67345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x= (y->left == it->nil) ? y->right : y->left; 67445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (it->root == (x->parent = y->parent)) 67545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* assignment of y->p to x->p is intentional */ 67645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->root->left=x; 67745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else { 67845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y == y->parent->left) 67945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent->left=x; 68045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 68145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent->right=x; 68245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 68345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y != z) { /* y should not be nil in this case */ 68445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 68545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef DEBUG_ASSERT 68645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert( (y!=it->nil),"y is nil in DeleteNode \n"); 68745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 68845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* y is the node to splice out and x is its child */ 68945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 69045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->maxHigh = INT_MIN; 69145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->left=z->left; 69245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->right=z->right; 69345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->parent=z->parent; 69445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org z->left->parent=z->right->parent=y; 69545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (z == z->parent->left) 69645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org z->parent->left=y; 69745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 69845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org z->parent->right=y; 69945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org FixUpMaxHigh(it, x->parent); 70045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!(y->red)) { 70145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->red = z->red; 70245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org DeleteFixUp(it, x); 70345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else 70445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org y->red = z->red; 70545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(z); 70645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 70745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 70845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#elif defined(DEBUG_ASSERT) 70945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not black in ITDelete"); 71045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=LONG_MIN),"nil->maxHigh != LONG_MIN in ITDelete"); 71145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 71245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 71345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org FixUpMaxHigh(it, x->parent); 71445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!(y->red)) 71545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org DeleteFixUp(it, x); 71645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xfree(y); 71745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 71845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IT_CheckAssumptions(it); 71945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#elif defined(DEBUG_ASSERT) 72045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert(!it->nil->red,"nil not black in ITDelete"); 72145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->nil->maxHigh=LONG_MIN),"nil->maxHigh != LONG_MIN in ITDelete"); 72245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 72345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 72445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return returnValue; 72545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 72645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 72745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 72845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 72945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: Overlap */ 73045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 73145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: [a1,a2] and [b1,b2] are the low and high endpoints of two */ 73245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* closed intervals. */ 73345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 73445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: stack containing pointers to the nodes between [low,high] */ 73545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 73645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: none */ 73745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 73845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECT: returns 1 if the intervals overlap, and 0 otherwise */ 73945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 74045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 74145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic int 74245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgOverlap(int a1, int a2, int b1, int b2) 74345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 74445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (a1 <= b1) 74545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return (b1 <= a2); 74645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else 74745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return (a1 <= b2); 74845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 74945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 75045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 75145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 75245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* FUNCTION: Enumerate */ 75345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 75445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* INPUTS: tree is the tree to look for intervals overlapping the */ 75545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* closed interval [low,high] */ 75645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 75745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* OUTPUT: stack containing pointers to the nodes overlapping */ 75845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* [low,high] */ 75945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 76045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modifies Input: none */ 76145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 76245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* EFFECT: Returns a stack containing pointers to nodes containing */ 76345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* intervals which overlap [low,high] in O(max(N,k*log(N))) */ 76445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* where N is the number of intervals in the tree and k is */ 76545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* the number of overlapping intervals */ 76645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/**/ 76745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Note: This basic idea for this function comes from the */ 76845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* _Introduction_To_Algorithms_ book by Cormen et al, but */ 76945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* modifications were made to return all overlapping intervals */ 77045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* instead of just the first overlapping interval as in the */ 77145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* book. The natural way to do this would require recursive */ 77245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* calls of a basic search function. I translated the */ 77345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* recursive version into an interative version with a stack */ 77445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* as described below. */ 77545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/***********************************************************************/ 77645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 77745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 77845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 77945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* The basic idea for the function below is to take the IntervalSearch 78045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * function from the book and modify to find all overlapping intervals 78145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * instead of just one. This means that any time we take the left 78245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * branch down the tree we must also check the right branch if and only if 78345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * we find an overlapping interval in that left branch. Note this is a 78445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * recursive condition because if we go left at the root then go left 78545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * again at the first left child and find an overlap in the left subtree 78645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * of the left child of root we must recursively check the right subtree 78745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * of the left child of root as well as the right child of root. 78845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 78945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid 79045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_enumerate(IntervalTree *it, long low, long high, void *cbd, 79145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org void (*callback) (IntervalTreeNode *node, void *cbd)) 79245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 79345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org IntervalTreeNode *x=it->root->left; 79445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org int stuffToDo = (x != it->nil); 79545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 79645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* Possible speed up: add min field to prune right searches */ 79745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 79845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef DEBUG_ASSERT 79945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->recursionNodeStackTop == 1), 80045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "recursionStack not empty when entering IntervalTree::Enumerate"); 80145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 80245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->currentParent = 0; 80345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 80445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (stuffToDo) { 80545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (Overlap(low,high,x->low,x->high) ) { 80645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org callback(x, cbd); 80745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack[it->currentParent].tryRightBranch=1; 80845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 80945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if(x->left->maxHigh >= low) { /* implies x != nil */ 81045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (it->recursionNodeStackTop == it->recursionNodeStackSize) { 81145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStackSize *= 2; 81245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack = (it_recursion_node *) 81345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org yasm_xrealloc(it->recursionNodeStack, 81445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStackSize * sizeof(it_recursion_node)); 81545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 81645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack[it->recursionNodeStackTop].start_node = x; 81745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack[it->recursionNodeStackTop].tryRightBranch = 0; 81845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack[it->recursionNodeStackTop].parentIndex = it->currentParent; 81945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->currentParent = it->recursionNodeStackTop++; 82045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x = x->left; 82145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } else { 82245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x = x->right; 82345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 82445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org stuffToDo = (x != it->nil); 82545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (!stuffToDo && (it->recursionNodeStackTop > 1)) { 82645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (it->recursionNodeStack[--it->recursionNodeStackTop].tryRightBranch) { 82745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org x=it->recursionNodeStack[it->recursionNodeStackTop].start_node->right; 82845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->currentParent=it->recursionNodeStack[it->recursionNodeStackTop].parentIndex; 82945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org it->recursionNodeStack[it->currentParent].tryRightBranch=1; 83045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org stuffToDo = (x != it->nil); 83145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 83245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 83345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 83445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef DEBUG_ASSERT 83545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Assert((it->recursionNodeStackTop == 1), 83645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org "recursionStack not empty when exiting IntervalTree::Enumerate"); 83745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 83845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 83945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 84045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS 84145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 84245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic int 84345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgCheckMaxHighFieldsHelper(const IntervalTree *it, IntervalTreeNode *y, 84445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org int currentHigh, int match) 84545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 84645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y != it->nil) { 84745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org match = CheckMaxHighFieldsHelper(it, y->left, currentHigh, match) ? 84845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1 : match; 84945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(y->high <= currentHigh); 85045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (y->high == currentHigh) 85145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org match = 1; 85245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org match = CheckMaxHighFieldsHelper(it, y->right, currentHigh, match) ? 85345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1 : match; 85445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 85545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return match; 85645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 85745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 85845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 85945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 86045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Make sure the maxHigh fields for everything makes sense. * 86145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * If something is wrong, print a warning and exit */ 86245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 86345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgCheckMaxHighFields(const IntervalTree *it, IntervalTreeNode *x) 86445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 86545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (x != it->nil) { 86645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org CheckMaxHighFields(it, x->left); 86745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if(!(CheckMaxHighFieldsHelper(it, x, x->maxHigh, 0) > 0)) { 86845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org fprintf(stderr, "error found in CheckMaxHighFields.\n"); 86945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org abort(); 87045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 87145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org CheckMaxHighFields(it, x->right); 87245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 87345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 87445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 87545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstatic void 87645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIT_CheckAssumptions(const IntervalTree *it) 87745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 87845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->nil->low == INT_MIN); 87945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->nil->high == INT_MIN); 88045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->nil->maxHigh == INT_MIN); 88145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->root->low == INT_MAX); 88245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->root->high == INT_MAX); 88345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->root->maxHigh == INT_MAX); 88445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->nil->data == NULL); 88545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->root->data == NULL); 88645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->nil->red == 0); 88745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org VERIFY(it->root->red == 0); 88845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org CheckMaxHighFields(it, it->root->left); 88945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 89045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 89145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 892