123root = NIL; 371Debug.Assert(page._slots[slotId]._leftId == NIL, "node not cleared"); 372Debug.Assert(page._slots[slotId]._rightId == NIL, "node not cleared"); 373Debug.Assert(page._slots[slotId]._parentId == NIL, "node not cleared"); 374Debug.Assert(page._slots[slotId]._nextId == NIL, "node not cleared"); 383if (Right(x_id) != NIL) 387while (y_id != NIL && x_id == Right(y_id)) 397if (NIL == nodeId) 400mainTreeNodeId = NIL; 406if ((NIL == nodeId) && (NIL != mainTreeNodeId)) 409mainTreeNodeId = NIL; 412if (NIL != nodeId) 414if (NIL != Next(nodeId)) 416if (NIL != mainTreeNodeId) 432while (Left(x_id) != NIL) 450if (Left(y_id) != NIL) 456if (Parent(x_id) == NIL) 458if (root_id == NIL) 482if (x_id != NIL) 484SetSubTreeSize(x_id, (SubTreeSize(Left(x_id)) + SubTreeSize(Right(x_id)) + (Next(x_id) == NIL ? 1 : SubTreeSize(Next(x_id))))); 487if (y_id != NIL) 489SetSubTreeSize(y_id, (SubTreeSize(Left(y_id)) + SubTreeSize(Right(y_id)) + (Next(y_id) == NIL ? 1 : SubTreeSize(Next(y_id))))); 505if (Right(y_id) != NIL) 511if (Parent(x_id) == NIL) 513if (root_id == NIL) 533if (x_id != NIL) 535SetSubTreeSize(x_id, (SubTreeSize(Left(x_id)) + SubTreeSize(Right(x_id)) + (Next(x_id) == NIL ? 1 : SubTreeSize(Next(x_id))))); 538if (y_id != NIL) 540SetSubTreeSize(y_id, (SubTreeSize(Left(y_id)) + SubTreeSize(Right(y_id)) + (Next(y_id) == NIL ? 1 : SubTreeSize(Next(y_id))))); 550Debug.Assert(NIL != x_id, "nil left"); 551Debug.Assert(NIL != z_id, "nil right"); 552return (root_id == NIL) ? CompareNode(Key(x_id), Key(z_id)) : CompareSatelliteTreeNode(Key(x_id), Key(z_id)); 575int y_id = NIL; 576int z_id = (root_id == NIL) ? root : root_id; //if non NIL, then use the specifid root_id as tree's root. 581while (z_id != NIL) // in-order traverse and find node with a NILL left or right child 586int c = (root_id == NIL) ? CompareNode(Key(x_id), Key(z_id)) : CompareSatelliteTreeNode(Key(x_id), Key(z_id)); 591Debug.Assert((NIL == Left(z_id)) || (0 > Compare(root_id, Left(z_id), z_id)), "Left is not left"); 598Debug.Assert((NIL == Right(z_id)) || (0 < Compare(root_id, Right(z_id), z_id)), "Right is not right"); 605if (root_id != NIL) 609if (Next(z_id) != NIL) 619int newMainTreeNodeId = NIL; 639if (Left(z_id) != NIL) 641if (Right(z_id) != NIL) 649SetParent(z_id, NIL); 650SetLeft(z_id, NIL); 651SetRight(z_id, NIL); 674while (z_id != NIL) // in-order traverse and find node with a NILL left or right child 690if (z_id != NIL) 703if (y_id == NIL) 705if (root_id == NIL) 725c = (root_id == NIL) ? CompareNode(Key(x_id), Key(y_id)) : CompareSatelliteTreeNode(Key(x_id), Key(y_id)); 739SetLeft(x_id, NIL); 740SetRight(x_id, NIL); 795if (root_id == NIL) 811if (Parent(x_id._nodeID) == NIL && x_id._nodeID != root) //determine if x_id is a satellite root. 834RBDeleteX(NIL, x_id._nodeID, x_id._mainTreeNodeID); 842return RBDeleteX(NIL, z_id, NIL); 866int x_id = NIL; // used for holding spliced node (y_id's) child 874if (Next(z_id) != NIL) 881if (Next(mNode) != NIL) 891if (Left(z_id) == NIL || Right(z_id) == NIL) 896if (Left(y_id) != NIL) 902if (x_id != NIL) 905if (py_id == NIL) // if the spliced node is the root. 908if (root_id == NIL) 930if (Next(mNode) != NIL) 934if (root_id == NIL && z_id != mNode) 940if (root_id != NIL) 950while (tmp_py_id != NIL) 958if (root_id != NIL) 962while (nodeId != NIL) 975if (mNode == NIL || SubTreeSize(Next(mNode)) != 1) 985if (Parent(mNode) != NIL) 999if (Left(mNode) != NIL) 1003if (Right(mNode) != NIL) 1013mNode = NIL; 1015else if (Next(mNode) != NIL) 1018if (root_id == NIL && z_id != mNode) 1023if (root_id != NIL) 1038if (Parent(z_id) != NIL) 1052SetParent(y_id, NIL); 1056if (Left(z_id) != NIL) 1060if (Right(z_id) != NIL) 1074if (mNode != NIL && Next(mNode) == z_id) 1099if (x_id == NIL && px_id == NIL) 1101return NIL; //case of satellite tree root being deleted. 1104while (((root_id == NIL ? root : root_id) != x_id) && color(x_id) == NodeColor.black) 1108if ((x_id != NIL && x_id == Left(Parent(x_id))) || (x_id == NIL && Left(px_id) == NIL)) 1112w_id = (x_id == NIL) ? Right(px_id) : Right(Parent(x_id)); // w is x's right sibling and it cannot be NIL 1114if (w_id == NIL) 1124w_id = (x_id == NIL) ? Right(px_id) : Right(Parent(x_id)); 1140w_id = (x_id == NIL) ? Right(px_id) : Right(Parent(x_id)); 1148x_id = (root_id == NIL) ? root : root_id; 1158if (x_id != NIL) 1162w_id = (x_id == NIL) ? Left(px_id) : Left(Parent(x_id)); 1170w_id = (x_id == NIL) ? Left(px_id) : Left(Parent(x_id)); 1172if (w_id == NIL) 1192w_id = (x_id == NIL) ? Left(px_id) : Left(Parent(x_id)); 1200x_id = (root_id == NIL) ? root : root_id; 1212if (root_id != NIL && _accessMethod != TreeAccessMethod.KEY_SEARCH_AND_INDEX) 1217int x_id = (root_id == NIL) ? root : root_id; 1219while (x_id != NIL) 1221c = (root_id == NIL) ? CompareNode(key, Key(x_id)) : CompareSatelliteTreeNode(key, Key(x_id)); 1229Debug.Assert((NIL == Left(x_id)) || (0 > Compare(root_id, Left(x_id), x_id)), "Search duplicate Left is not left"); 1236Debug.Assert((NIL == Right(x_id)) || (0 < Compare(root_id, Right(x_id), x_id)), "Search duplicate Right is not right"); 1249while (x_id != NIL) 1259Debug.Assert((NIL == Left(x_id)) || (0 > Compare(NIL, Left(x_id), x_id)), "Search Left is not left"); 1266Debug.Assert((NIL == Right(x_id)) || (0 < Compare(NIL, Right(x_id), x_id)), "Search Right is not right"); 1294int nodeId = SearchSubTree(NIL, key); 1295if (Next(nodeId) != NIL) 1301nodeId = NIL; 1303return new NodePath(nodeId, NIL); 1314if (nodeId._nodeID != NIL) 1347Debug.Assert(NIL != node, "GetIndexByNode(NIL)"); 1353else if (NIL != Next(node)) 1362int mainTreeNodeId = SearchSubTree(NIL, Key(node)); 1392else if (NIL == path._mainTreeNodeID) 1409while (nodeId != NIL) 1430while (nodeId != NIL) 1435myRank += (SubTreeSize(Left(parent)) + ((Next(parent) == NIL) ? 1 : SubTreeSize(Next(parent)))); 1455satelliteRootId = NIL; 1462if (x_id == NIL) 1479satelliteRootId = NIL; 1483while (x_id != NIL && !(((rank = SubTreeSize(Left(x_id)) + 1) == index) && Next(x_id) == NIL)) 1489else if (Next(x_id) != NIL && index >= rank && index <= rank + SubTreeSize(Next(x_id)) - 1) 1498if (Next(x_id) == NIL) 1511while (x_id != NIL) 1513Debug.Assert(NIL == Next(x_id), "has unexpected satellite tree"); 1538if (curNodeId != NIL) 1540if (Next(curNodeId) != NIL) 1555RBInsert(NIL, nodeId, NIL, -1, false); 1564RBInsert(NIL, nodeId, NIL, -1, false); 1581if (nodeId != NIL) 1609RBInsert(NIL, nodeId, NIL, position, append); 1698Debug.Assert(nodeId != NIL, " in SetParent nodeId == NIL"); 1709Debug.Assert(nodeId != NIL, " in SetColor nodeId == NIL"); 1740Debug.Assert(nodeId != NIL && 1741(size != 0 || _pageTable[nodeId >> 16]!._slots[nodeId & 0xFFFF]._selfId == NIL) && 1742(size != 1 || _pageTable[nodeId >> 16]!._slots[nodeId & 0xFFFF]._nextId == NIL), "SetSize"); 1762int myCorrectSize = SubTreeSize(Left(nodeId)) + SubTreeSize(Right(nodeId)) + (Next(nodeId) == NIL ? 1 : SubTreeSize(Next(nodeId))); 1785int myCorrectSize = SubTreeSize(Left(nodeId)) + SubTreeSize(Right(nodeId)) + (Next(nodeId) == NIL ? 1 : SubTreeSize(Next(nodeId))); 1908Debug.Assert((NIL == _nodeID && NIL == _mainTreeNodeID) || (NIL != _nodeID), "MainTreeNodeID is not NIL"); 1910if (NIL != _mainTreeNodeID) 1912Debug.Assert(NIL != tree.Next(_mainTreeNodeID), "MainTreeNodeID should have a Next"); 1914while (NIL != tree.Parent(node)) 1920if (NIL != _nodeID) 1922Debug.Assert(NIL == tree.Next(_nodeID), "NodeID should not have a Next"); 1924if (NIL == _mainTreeNodeID) 1926while (NIL != tree.Parent(node)) 1933while (NIL != tree.Parent(node)) 1935Debug.Assert(NIL == tree.Next(node), "duplicate node should not have a next"); 1939Debug.Assert((NIL == _mainTreeNodeID && tree.root == node) || 2051_index = NIL; 2062_index = NIL; 2068if (NIL == _index) 2116_index = NIL;

510if (nodeId != IndexTree.NIL) 519if (IndexTree.NIL != nodeId) 529if (IndexTree.NIL != nodeId) 545if (IndexTree.NIL != x) 554while (IndexTree.NIL != x) 564while (IndexTree.NIL != x) 586if (IndexTree.NIL != x) 597while (IndexTree.NIL != x) 612if (IndexTree.NIL != x) 616while (IndexTree.NIL != x) 633while (IndexTree.NIL != x) 648if (IndexTree.NIL == nodeId) 654if (_records.Next(nodeId) == IndexTree.NIL) 823return (IndexTree.NIL != x_id); 829return (IndexTree.NIL != x_id); 835return (IndexTree.NIL != x_id); 1011if (curNodeId != IndexTree.NIL)