121root = NIL; 367Debug.Assert(page.Slots[slotId].leftId == NIL, "node not cleared"); 368Debug.Assert(page.Slots[slotId].rightId == NIL, "node not cleared"); 369Debug.Assert(page.Slots[slotId].parentId == NIL, "node not cleared"); 370Debug.Assert(page.Slots[slotId].nextId == NIL, "node not cleared"); 379if (Right (x_id) != NIL) 383while (y_id != NIL && x_id == Right (y_id)) 393if (NIL == nodeId) 396mainTreeNodeId = NIL; 402if ((NIL == nodeId) && (NIL != mainTreeNodeId)) 405mainTreeNodeId = NIL; 408if (NIL != nodeId) 410if (NIL != Next(nodeId)) 412if (NIL != mainTreeNodeId) 428while (Left (x_id) != NIL) { 445if (Left (y_id) != NIL) { 450if (Parent (x_id) == NIL) { 451if (root_id == NIL) { 471if (x_id != NIL) { 472SetSubTreeSize(x_id, (SubTreeSize(Left(x_id)) + SubTreeSize(Right(x_id)) + (Next(x_id) == NIL ? 1 : SubTreeSize(Next(x_id))))); 475if (y_id != NIL) { 476SetSubTreeSize(y_id, (SubTreeSize(Left(y_id)) + SubTreeSize(Right(y_id)) + (Next(y_id) == NIL ? 1 : SubTreeSize(Next(y_id))))); 492if (Right (y_id) != NIL) { 497if (Parent (x_id) == NIL) { 498if (root_id == NIL) { 516if (x_id != NIL) { 517SetSubTreeSize(x_id, (SubTreeSize(Left(x_id)) + SubTreeSize(Right(x_id)) + (Next(x_id) == NIL ? 1 : SubTreeSize(Next(x_id))))); 520if (y_id != NIL) { 521SetSubTreeSize(y_id, (SubTreeSize(Left(y_id)) + SubTreeSize(Right(y_id)) + (Next(y_id) == NIL ? 1 : SubTreeSize(Next(y_id))))); 555int y_id = NIL; 556int z_id = (root_id == NIL) ? root : root_id; //if non NIL, then use the specifid root_id as tree's root. 561while (z_id != NIL) // in-order traverse and find node with a NILL left or right child 566int c = (root_id == NIL) ? CompareNode (Key (x_id), Key (z_id)) : CompareSateliteTreeNode (Key (x_id), Key (z_id)); 582if (root_id != NIL) { 585if (Next(z_id) != NIL) { 593int newMainTreeNodeId = NIL; 613if (Left(z_id) != NIL) 615if (Right(z_id) != NIL) 623SetParent(z_id, NIL); 624SetLeft(z_id, NIL); 625SetRight(z_id, NIL); 647while (z_id != NIL) // in-order traverse and find node with a NILL left or right child 661if (z_id != NIL) { 672if (y_id == NIL) 674if (root_id == NIL) { 693c = (root_id == NIL) ? CompareNode (Key(x_id), Key(y_id)) : CompareSateliteTreeNode (Key (x_id), Key (y_id)); 706SetLeft (x_id, NIL); 707SetRight (x_id, NIL); 762if (root_id == NIL) 778if (Parent(x_id.NodeID) == NIL && x_id.NodeID != root) //determine if x_id is a satellite root. 801RBDeleteX(NIL, x_id.NodeID, x_id.MainTreeNodeID); 809return RBDeleteX (NIL, z_id, NIL); 833int x_id = NIL; // used for holding spliced node (y_id's) child 841if (Next (z_id) != NIL) 848if (Next (mNode) != NIL) 857if (Left (z_id) == NIL || Right (z_id) == NIL) 862if (Left (y_id) != NIL) 868if (x_id != NIL) 871if (py_id == NIL) // if the spliced node is the root. 874if (root_id == NIL) 896if (Next(mNode) != NIL) 900if (root_id == NIL && z_id != mNode) { 905if (root_id != NIL) 915while (tmp_py_id != NIL) 923if (root_id != NIL) 927while (nodeId != NIL) 940if (mNode == NIL || SubTreeSize(Next(mNode)) != 1) { 949if (Parent(mNode) != NIL) 961if (Left(mNode) != NIL) { 964if (Right(mNode) != NIL) { 972mNode = NIL; 974else if (Next(mNode) != NIL) 977if (root_id == NIL && z_id != mNode) { //if mNode being deleted, its OK for root_id (it should be) NIL. 981if (root_id != NIL) 997if (Parent(z_id) != NIL) 1008SetParent(y_id, NIL); 1012if (Left(z_id) != NIL) { 1015if (Right(z_id) != NIL) { 1026if (mNode != NIL && Next(mNode) == z_id) { 1050if (x_id == NIL && px_id == NIL) { 1051return NIL; //case of satelite tree root being deleted. 1054while (((root_id == NIL ? root : root_id) != x_id) && color (x_id) == NodeColor.black) 1058if ((x_id != NIL && x_id == Left (Parent (x_id))) || (x_id == NIL && Left (px_id) == NIL)) 1062w_id = (x_id == NIL) ? Right (px_id) : Right (Parent (x_id)); // w is x's right sibling and it cannot be NIL 1064if (w_id == NIL) { 1073w_id = (x_id == NIL) ? Right (px_id) : Right (Parent (x_id)); 1089w_id = (x_id == NIL) ? Right (px_id) : Right (Parent (x_id)); 1097x_id = (root_id == NIL) ? root : root_id; 1107if (x_id != NIL) { 1110w_id = (x_id == NIL) ? Left (px_id) : Left (Parent (x_id)); 1117w_id = (x_id == NIL) ? Left (px_id) : Left (Parent (x_id)); 1119if (w_id == NIL) { 1136w_id = (x_id == NIL) ? Left (px_id) : Left (Parent (x_id)); 1139if (x_id != NIL) 1146x_id = (root_id == NIL) ? root : root_id; 1156x_id = (root_id == NIL) ? root : root_id; 1169if (root_id != NIL && _accessMethod!=TreeAccessMethod.KEY_SEARCH_AND_INDEX) { 1173int x_id = (root_id == NIL) ? root : root_id; 1175while (x_id != NIL) 1177c = (root_id == NIL) ? CompareNode (key, Key (x_id)) : CompareSateliteTreeNode (key, Key (x_id)); 1202while (x_id != NIL) 1244int nodeId = SearchSubTree(NIL, key); 1245if (Next (nodeId) != NIL) { 1249nodeId = NIL; 1251return new NodePath(nodeId, NIL); 1262if (nodeId.NodeID != NIL) { 1294Debug.Assert(NIL != node, "GetIndexByNode(NIL)"); 1300else if (NIL != Next(node)) 1309int mainTreeNodeId = SearchSubTree(NIL, Key(node)); 1339else if (NIL == path.MainTreeNodeID) 1355while (nodeId != NIL) 1375while (nodeId != NIL) 1380myRank += (SubTreeSize(Left(parent)) + ((Next(parent) == NIL) ? 1 : SubTreeSize(Next(parent)))); 1399satelliteRootId = NIL; 1405if (x_id == NIL) { 1419satelliteRootId = NIL; 1423while (x_id != NIL && !(((rank = SubTreeSize (Left (x_id)) + 1) == index) && Next (x_id) == NIL)) 1428else if (Next (x_id) != NIL && index >= rank && index <= rank + SubTreeSize (Next (x_id)) - 1) 1437if (Next (x_id) == NIL) 1449while (x_id != NIL) { 1450Debug.Assert(NIL == Next(x_id), "has unexpected satellite tree"); 1489RBInsert (NIL, nodeId, NIL, -1, false); 1498RBInsert(NIL, nodeId, NIL, -1, false); 1514if (nodeId != NIL) 1539RBInsert (NIL, nodeId, NIL, position, append); 1617Debug.Assert(nodeId != NIL, " in SetParent nodeId == NIL"); 1628Debug.Assert(nodeId != NIL, " in SetColor nodeId == NIL"); 1659Debug.Assert(nodeId != NIL && 1660(size != 0 || _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].selfId == NIL) && 1661(size != 1 || _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].nextId == NIL), "SetSize"); 1681int myCorrectSize = SubTreeSize (Left (nodeId)) + SubTreeSize (Right (nodeId)) + (Next (nodeId) == NIL ? 1 : SubTreeSize (Next (nodeId))); 1703int myCorrectSize = SubTreeSize(Left(nodeId)) + SubTreeSize(Right(nodeId)) + (Next(nodeId) == NIL ? 1 : SubTreeSize(Next(nodeId))); 1965index = NIL; 1976index = NIL; 1982if (NIL == index) 2020index = NIL;

507if (nodeId!=IndexTree.NIL) 515if (IndexTree.NIL != nodeId) { 523if (IndexTree.NIL != nodeId) { 536if (IndexTree.NIL != x) { // otherwise storage may not exist 542while (IndexTree.NIL != x) { 550while (IndexTree.NIL != x) { 569if (IndexTree.NIL != x) { // otherwise storage may not exist 577while (IndexTree.NIL != x) { 590if (IndexTree.NIL != x) { // otherwise storage may not exist 592while (IndexTree.NIL != x) { 609while (IndexTree.NIL != x) 624if (IndexTree.NIL == nodeId) { 629if (records.Next (nodeId) == IndexTree.NIL) 780return (IndexTree.NIL != x_id); 785return (IndexTree.NIL != x_id); 790return (IndexTree.NIL != x_id); 942if (curNodeId != IndexTree.NIL) {