mcs/class/referencesource/System.Data/System/Data/RbTree.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="Selection.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 // <owner current="true" primary="false">Microsoft</owner>
   7 //------------------------------------------------------------------------------
   8
   9 #if DEBUG
  10 //#define VerifyIndex
  11 #define VerifyPath
  12 #define VerifySort
  13 #endif
  14
  15 namespace System.Data
  16 {
  17     using System;
  18     using System.Collections;
  19     using System.Data.Common;
  20     using System.Diagnostics;
  21
  22     internal enum RBTreeError {
  23         InvalidPageSize                             =  1,
  24 //      InvalidCompareDelegate                      =  2,
  25         PagePositionInSlotInUse                     =  3,
  26         NoFreeSlots                                 =  4,
  27         InvalidStateinInsert                        =  5,
  28 //      InvalidStateinEndInsert                     =  6,
  29         InvalidNextSizeInDelete                     =  7,
  30         InvalidStateinDelete                        =  8,
  31         InvalidNodeSizeinDelete                     =  9,
  32         InvalidStateinEndDelete                     = 10,
  33         CannotRotateInvalidsuccessorNodeinDelete    = 11,
  34 //      IndexOutOfRange                             = 12,
  35         IndexOutOFRangeinGetNodeByIndex             = 13,
  36         RBDeleteFixup                               = 14,
  37         UnsupportedAccessMethod1                    = 15,
  38         UnsupportedAccessMethod2                    = 16,
  39         UnsupportedAccessMethodInNonNillRootSubtree = 17,
  40         AttachedNodeWithZerorbTreeNodeId            = 18, // DataRowCollection
  41         CompareNodeInDataRowTree                    = 19, // DataRowCollection
  42         CompareSateliteTreeNodeInDataRowTree        = 20, // DataRowCollection
  43         NestedSatelliteTreeEnumerator               = 21,
  44     }
  45
  46     internal enum TreeAccessMethod{
  47         KEY_SEARCH_AND_INDEX = 1,
  48         INDEX_ONLY           = 2,
  49     }
  50
  51     // an index represents location the tree
  52     // a tree has an array of pages (max 2^16) (top 16 bits)
  53     // a page has an array of nodes (max 2^16) (bottom 16 bits)
  54     // nodes are indexed by RBTree.PageTable[index>>16].Slots[index&0xFFFF]
  55
  56     // a tree has an PageTableBitmap to indicate which allocated pages have free nodes
  57     // a page has a SlotBitmap to indicate which slots are free
  58
  59     // intial page allocation (assuming no deletes)
  60     //          #page  * #slot =     #total, #cumulative
  61     // (            4) *    32 =        128,           127 (subtract 1 for NIL node)
  62     // (   32 -     4) *   256 =       7168,         7,295
  63     // (  128 -    32) *  1024 =      98304,       105,599
  64     // ( 4096 -   128) *  4096 =   16252928,    16,358,527
  65     // (32768 -  4096) *  8192 =  234881024,   251,239,551
  66     // (65535 - 32768) * 65536 = 2147418112, 2,398,657,663 (excess nodes 251,174,016 > Int32.MaxValue)
  67
  68     // tree page size is GetIntValueFromBitMap(inUsePageCount) // return highest bit in array
  69     //private static readonly int[] PageSize = new int[17] { // nobit + 16 bits == 17 position
  70     //       32,   32,   32,              // inUsePageCount <      4           0,    1,     2,
  71     //      256,  256,  256,              // inUsePageCount <     32           4,    8,    16,
  72     //     1024, 1024,                    // inUsePageCount <    128          32,   64,
  73     //     4096, 4096, 4096, 4096, 4096,  // inUsePageCount <   4096         128,  256,   512, 1024, 2048,
  74     //     8192, 8192, 8192,              // inUsePageCount <  32768        4096, 8192, 16384
  75     //    65535                           // inUsePageCount <= 65535
  76     //};
  77
  78     // the in-ordering of nodes in the tree  (the second graph has duplicate nodes)
  79     // for the satellite tree, the main tree node is the clone, GetNodeByIndex always returns the satelliteRootid
  80     //      4       |           4
  81     //    /   \     |     /          \
  82     //   2     6    |    3  -   3     7
  83     //  / \   / \   |   / \    / \   / \
  84     // 1   3 5   7  |  1   5  2   4 8   9
  85
  86     // PageTable (starting at 32) doubles in size on demand (^16 - ^5 = 11 grows to reach max PageTable size)
  87
  88     // if a page has no allocated slots, it will be dropped
  89     // worst case scenario is to repeatedly add/remove on a boundary condition
  90
  91     // the primary change to support Index using Predicate<DataRow> or Comparison<DataRow> was to eliminate all
  92     // unnecessary searching for the node in the main tree when operating on a node in the satellite branch
  93     // in all cases except GetNodeByKey(K)& GetIndexByNode(int), we know what that mainTreeNodeID is and can avoid searching
  94
  95     internal abstract class RBTree<K> : System.Collections.IEnumerable {
  96         // 2^16 #pages * 2^n == total number of nodes.  512 = 32 million, 1024 = 64 million, 2048 = 128m, 4096=256m, 8192=512m, 16284=1 billion
  97         // 32K=2 billion.
  98         internal const int DefaultPageSize = 32; /* 512 = 2^9 32 million nodes*/
  99         internal const int NIL = 0;                  // 0th page, 0th slot for each tree till CLR static & generics issue is fixed
 100
 101         private TreePage[] _pageTable;          // initial size 4, then doubles (grows) - it never shrinks
 102         private Int32[] _pageTableMap;
 103         private int _inUsePageCount = 0;    // contains count of allocated pages per tree, its <= the capacity of  pageTable
 104         private int nextFreePageLine;   // used for keeping track of position of last used free page in pageTable
 105         public  int root;
 106         private int _version;
 107
 108         private int _inUseNodeCount = 0; // total number of nodes currently in use by this tree.
 109         private int _inUseSatelliteTreeCount = 0; // total number of satellite associated with this tree.
 110         private readonly TreeAccessMethod _accessMethod;
 111
 112         protected abstract int CompareNode (K record1, K record2);
 113         protected abstract int CompareSateliteTreeNode (K record1, K record2);
 114
 115         protected RBTree (TreeAccessMethod accessMethod) {
 116             _accessMethod = accessMethod;
 117             InitTree();
 118         }
 119
 120         private void InitTree() {
 121             root = NIL;
 122             _pageTable = new TreePage[1 * TreePage.slotLineSize];
 123             _pageTableMap = new Int32[(_pageTable.Length + TreePage.slotLineSize - 1) / TreePage.slotLineSize]; // Ceiling(size)
 124             _inUsePageCount = 0;
 125             nextFreePageLine = 0;
 126             AllocPage (DefaultPageSize);
 127
 128             // alloc storage for reserved NIL node. segment 0, slot 0; Initialize NIL
 129             _pageTable[0].Slots[0].nodeColor = NodeColor.black;
 130             _pageTable[0].SlotMap[0]         = 0x1;
 131             _pageTable[0].InUseCount         = 1;
 132
 133             _inUseNodeCount = 1;
 134             _inUseSatelliteTreeCount = 0; // total number of satellite associated with this tree.
 135         }
 136
 137         private void FreePage (TreePage page)
 138         {
 139             MarkPageFree (page);
 140             _pageTable[page.PageId] = null;
 141             _inUsePageCount--;
 142         }
 143
 144         /* AllocPage()
 145          *  size : Allocates a page of the specified size.
 146          *
 147          * Look for an unallocated page entry.
 148          *   (1) If entry for an unallocated page exists in current pageTable - use it
 149          *   (2) else extend pageTable
 150          */
 151         private TreePage AllocPage (int size)
 152         {
 153             int freePageIndex = GetIndexOfPageWithFreeSlot (false);
 154
 155             if (freePageIndex != -1)
 156             {
 157                 _pageTable[freePageIndex] = new TreePage (size);
 158                 nextFreePageLine = freePageIndex / TreePage.slotLineSize;
 159             }
 160             else
 161             {
 162                 // no free position found, increase pageTable size
 163                 TreePage[] newPageTable = new TreePage[_pageTable.Length * 2];
 164                 System.Array.Copy (_pageTable, 0, newPageTable, 0, _pageTable.Length);
 165                 Int32[] newPageTableMap = new Int32[(newPageTable.Length + TreePage.slotLineSize - 1) / TreePage.slotLineSize];
 166                 System.Array.Copy (_pageTableMap, 0, newPageTableMap, 0, _pageTableMap.Length);
 167
 168                 nextFreePageLine = _pageTableMap.Length;
 169                 freePageIndex = _pageTable.Length;
 170                 _pageTable = newPageTable;
 171                 _pageTableMap = newPageTableMap;
 172                 _pageTable[freePageIndex] = new TreePage (size);
 173             }
 174             _pageTable[freePageIndex].PageId = freePageIndex;
 175             _inUsePageCount++;
 176             return _pageTable[freePageIndex];
 177         }
 178
 179         /* MarkPageFull()
 180          * Mark the specified page "Full" as all its slots aer in use
 181          */
 182         private void MarkPageFull (TreePage page)
 183         {
 184             // set bit associated with page to mark it as full
 185             /*
 186             int pageTableMapIndex = (page.PageId / TreePage.slotLineSize);
 187             int pageTableMapOffset = (page.PageId % TreePage.slotLineSize);
 188             Int32 pageBitMask = ((Int32)1) << pageTableMapOffset;
 189             _pageTableMap[pageTableMapIndex] |= (pageBitMask);
 190             */
 191             _pageTableMap[page.PageId / TreePage.slotLineSize] |= (1 << (page.PageId % TreePage.slotLineSize));
 192         }
 193
 194         /* MarkPageFree()
 195          * Mark the specified page as "Free". It has atleast 1 available slot.
 196          */
 197         private void MarkPageFree (TreePage page)
 198         {
 199             // set bit associated with page to mark it as free
 200             /*
 201             int pageTableMapIndex = (page.PageId / TreePage.slotLineSize);
 202             int pageTableMapOffset = (page.PageId % TreePage.slotLineSize);
 203             Int32 pageBitMask = ((Int32)1) << pageTableMapOffset;
 204             _pageTableMap[pageTableMapIndex] &= ~(pageBitMask);
 205             */
 206             _pageTableMap[page.PageId / TreePage.slotLineSize] &= ~(1 << (page.PageId % TreePage.slotLineSize));
 207         }
 208
 209         private static int GetIntValueFromBitMap (UInt32 bitMap)
 210         {
 211             Int32 value = 0; // 0 based slot position
 212
 213             /*
 214              * Assumption: bitMap can have max, exactly 1 bit set.
 215              * convert bitMap to int value giving number of 0's to its right
 216              * return value between 0 and 31
 217              */
 218             if ((bitMap & 0xFFFF0000) != 0)
 219             {
 220                 value += 16;
 221                 bitMap >>=16;
 222             }
 223             if ((bitMap & 0x0000FF00) != 0)
 224             {
 225                 value += 8;
 226                 bitMap >>=8;
 227             }
 228             if ((bitMap & 0x000000F0) != 0)
 229             {
 230                 value += 4;
 231                 bitMap >>=4;
 232             }
 233             if ((bitMap & 0x0000000C) != 0)
 234             {
 235                 value += 2;
 236                 bitMap >>=2;
 237             }
 238             if ((bitMap & 0x00000002) != 0)
 239                 value += 1;
 240             return value;
 241         }
 242
 243         /*
 244          * FreeNode()
 245          * nodeId: The nodeId of the node to be freed
 246          */
 247         private void FreeNode (int nodeId)
 248         {
 249             TreePage page = _pageTable[nodeId >> 16];
 250             int slotIndex = nodeId & 0xFFFF;
 251
 252             page.Slots[slotIndex] = default(Node);
 253
 254             // clear slotMap entry associated with nodeId
 255             page.SlotMap[slotIndex / TreePage.slotLineSize] &= ~( ((Int32)1) << (int)(slotIndex % TreePage.slotLineSize));
 256             page.InUseCount--;
 257             _inUseNodeCount--;
 258             if (page.InUseCount == 0)
 259                 FreePage (page);
 260             else if (page.InUseCount == page.Slots.Length - 1)
 261                 MarkPageFree (page); // With freeing of a node, a previous full page has a free slot.
 262         }
 263
 264         /*
 265          * GetIndexOfPageWithFreeSlot()
 266          * allocatedPage: If true, look for an allocatedPage with free slot else look for an unallocated page entry in pageTable
 267          * return: if allocatedPage is true, return index of a page with at least 1 free slot
 268          *            else return index of an unallocated page, pageTable[index] is empty.
 269          */
 270         private int GetIndexOfPageWithFreeSlot (bool allocatedPage)
 271         {
 272             int pageTableMapPos = nextFreePageLine;
 273             int pageIndex = -1;
 274
 275             while (pageTableMapPos < _pageTableMap.Length)
 276             {
 277                 if (((UInt32)_pageTableMap[pageTableMapPos]) < 0xFFFFFFFF)
 278                 {
 279                     UInt32 pageSegmentMap = (UInt32)_pageTableMap[pageTableMapPos];
 280                     while ((pageSegmentMap ^ (0xFFFFFFFF)) != 0)         //atleast one "0" is there (same as <0xFFFFFFFF)
 281                     {
 282                         UInt32 pageWithFreeSlot = (UInt32)((~(pageSegmentMap)) & (pageSegmentMap + 1));
 283
 284                         //
 285                         if ((_pageTableMap[pageTableMapPos] & pageWithFreeSlot) != 0) //paranoia check
 286                             throw ExceptionBuilder.InternalRBTreeError(RBTreeError.PagePositionInSlotInUse);
 287
 288                         pageIndex = (pageTableMapPos * TreePage.slotLineSize) + GetIntValueFromBitMap (pageWithFreeSlot); // segment + offset
 289                         if (allocatedPage)
 290                         {
 291                             if (_pageTable[pageIndex] != null)
 292                                 return pageIndex;
 293                         }
 294                         else
 295                         {
 296                             if (_pageTable[pageIndex] == null)
 297                                 return pageIndex;           // pageIndex points to an unallocated Page
 298                         }
 299                         pageIndex = -1;
 300                         pageSegmentMap |= pageWithFreeSlot; // found "reset bit", but unallocated page, mark it as unavaiable and continue search
 301                     }
 302                 }
 303
 304                 pageTableMapPos++;
 305             }
 306
 307             if (nextFreePageLine != 0)
 308             {
 309                 //Try one more time, starting from 0th page segment position to locate a page with free slots
 310                 nextFreePageLine = 0;
 311                 pageIndex = GetIndexOfPageWithFreeSlot (allocatedPage);
 312             }
 313             return pageIndex;
 314         }
 315
 316         public int Count {
 317             get {
 318                 Debug.Assert(_inUseNodeCount-1 == SubTreeSize(root), "count mismatch");
 319                 return (_inUseNodeCount-1);
 320             }
 321         }
 322
 323         public bool HasDuplicates {
 324             get {
 325                 return (0 != _inUseSatelliteTreeCount);
 326             }
 327         }
 328
 329         /*
 330          * GetNewNode()
 331          * Allocate storage for a new node and assign in the specified key.
 332          *
 333          * Find a page with free slots or allocate a new page.
 334          * Use bitmap associated with page to allocate a slot.
 335          * mark the slot as used and return its index.
 336          */
 337         private int GetNewNode (K key)
 338         {
 339             // find page with free slots, if none, allocate a new page
 340             TreePage page = null;
 341
 342             int freePageIndex = GetIndexOfPageWithFreeSlot (true);
 343             if (freePageIndex != -1)
 344                 page = _pageTable[freePageIndex];
 345             else if (_inUsePageCount < (4))
 346                 page = AllocPage (DefaultPageSize);  // First 128 slots
 347             else if (_inUsePageCount < (32))
 348                 page = AllocPage (256);
 349             else if (_inUsePageCount < (128))
 350                 page = AllocPage (1024);
 351             else if (_inUsePageCount < (4096))
 352                 page = AllocPage (4096);
 353             else if (_inUsePageCount < (32*1024))
 354                 page = AllocPage (8192);              // approximately First 16 million slots (2^24)
 355             else
 356                 page = AllocPage (64*1024);          // Page size to accomodate more than 16 million slots (Max 2 Billion and 16 million slots)
 357
 358             // page contains atleast 1 free slot.
 359             int slotId = page.AllocSlot (this);
 360
 361             //
 362             if (slotId == -1)
 363                 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.NoFreeSlots);
 364
 365             // NodeId: Upper 16 bits pageId, lower bits slotId
 366             page.Slots[slotId].selfId = (int)(((UInt32)page.PageId) << 16) | slotId;
 367             Debug.Assert(page.Slots[slotId].leftId == NIL, "node not cleared");
 368             Debug.Assert(page.Slots[slotId].rightId == NIL, "node not cleared");
 369             Debug.Assert(page.Slots[slotId].parentId == NIL, "node not cleared");
 370             Debug.Assert(page.Slots[slotId].nextId == NIL, "node not cleared");
 371             page.Slots[slotId].subTreeSize = 1;     // new Nodes have size 1.
 372             page.Slots[slotId].keyOfNode = key;
 373             Debug.Assert(page.Slots[slotId].nodeColor == NodeColor.red, "node not cleared");
 374             return page.Slots[slotId].selfId;
 375         }
 376
 377         private int Successor (int x_id)
 378         {
 379             if (Right (x_id) != NIL)
 380                 return Minimum (Right (x_id)); //return left most node in right sub-tree.
 381             int y_id = Parent (x_id);
 382
 383             while (y_id != NIL && x_id == Right (y_id))
 384             {
 385                 x_id = y_id;
 386                 y_id = Parent (y_id);
 387             }
 388             return y_id;
 389         }
 390
 391         private bool Successor(ref int nodeId, ref int mainTreeNodeId)
 392         {
 393             if (NIL == nodeId)
 394             {   // find first node, using branchNodeId as the root
 395                 nodeId = Minimum(mainTreeNodeId);
 396                 mainTreeNodeId = NIL;
 397             }
 398             else
 399             {   // find next node
 400                 nodeId = Successor(nodeId);
 401
 402                 if ((NIL == nodeId) && (NIL != mainTreeNodeId))
 403                 {   // done with satellite branch, move back to main tree
 404                     nodeId = Successor(mainTreeNodeId);
 405                     mainTreeNodeId = NIL;
 406                 }
 407             }
 408             if (NIL != nodeId)
 409             {   // test for satellite branch
 410                 if (NIL != Next(nodeId))
 411                 {   // find first node of satellite branch
 412                     if (NIL != mainTreeNodeId)
 413                     {   // satellite branch has satellite branch - very bad
 414                         throw ExceptionBuilder.InternalRBTreeError(RBTreeError.NestedSatelliteTreeEnumerator);
 415                     }
 416                     mainTreeNodeId = nodeId;
 417                     nodeId = Minimum(Next(nodeId));
 418                 }
 419                 // has value
 420                 return true;
 421             }
 422             // else no value, done with main tree
 423             return false;
 424         }
 425
 426         private int Minimum (int x_id)
 427         {
 428             while (Left (x_id) != NIL) {
 429                 x_id = Left (x_id);
 430             }
 431             return x_id;
 432         }
 433
 434         /*
 435          * LeftRotate()
 436          *
 437          * It returns the node id for the root of the rotated tree
 438          */
 439         private int LeftRotate (int root_id, int x_id, int mainTreeNode)
 440         {
 441             int y_id = Right (x_id);
 442
 443             // Turn y's left subtree into x's right subtree
 444             SetRight (x_id, Left (y_id));
 445             if (Left (y_id) != NIL) {
 446                 SetParent (Left (y_id), x_id);
 447             }
 448
 449             SetParent (y_id, Parent (x_id));
 450             if (Parent (x_id) == NIL) {
 451                 if (root_id == NIL) {
 452                     root = y_id;
 453                 }
 454                 else {
 455                     SetNext (mainTreeNode, y_id);
 456                     SetKey (mainTreeNode, Key (y_id));
 457                     root_id = y_id;
 458                 }
 459             }
 460             else if (x_id == Left (Parent (x_id))) {  // x is left child of its parent
 461                 SetLeft (Parent (x_id), y_id);
 462             }
 463             else {
 464                 SetRight (Parent (x_id), y_id);
 465             }
 466
 467             SetLeft (y_id, x_id);
 468             SetParent (x_id, y_id);
 469
 470             //maintain size:  y_id = parent & x_id == child
 471             if (x_id != NIL) {
 472                 SetSubTreeSize(x_id, (SubTreeSize(Left(x_id)) + SubTreeSize(Right(x_id)) + (Next(x_id) == NIL ? 1 : SubTreeSize(Next(x_id)))));
 473             }
 474
 475             if (y_id != NIL) {
 476                 SetSubTreeSize(y_id, (SubTreeSize(Left(y_id)) + SubTreeSize(Right(y_id)) + (Next(y_id) == NIL ? 1 : SubTreeSize(Next(y_id)))));
 477             }
 478             return root_id;
 479         }
 480
 481
 482         /*
 483          * RightRotate()
 484          *
 485          * It returns the node id for the root of the rotated tree
 486          */
 487         private int RightRotate (int root_id, int x_id, int mainTreeNode)
 488         {
 489             int y_id = Left (x_id);
 490
 491             SetLeft (x_id, Right (y_id));       // Turn y's right subtree into x's left subtree
 492             if (Right (y_id) != NIL) {
 493                 SetParent (Right (y_id), x_id);
 494             }
 495
 496             SetParent (y_id, Parent (x_id));
 497             if (Parent (x_id) == NIL) {
 498                 if (root_id == NIL) {
 499                     root = y_id;
 500                 }
 501                 else {
 502                     SetNext (mainTreeNode, y_id);
 503                     SetKey (mainTreeNode, Key (y_id));
 504                     root_id = y_id;
 505                 }
 506             }
 507             else if (x_id == Left (Parent (x_id))) // x is left child of its parent
 508                 SetLeft (Parent (x_id), y_id);
 509             else
 510                 SetRight (Parent (x_id), y_id);
 511
 512             SetRight (y_id, x_id);
 513             SetParent (x_id, y_id);
 514
 515             //maintain size: y_id == parent && x_id == child.
 516             if (x_id != NIL) {
 517                 SetSubTreeSize(x_id, (SubTreeSize(Left(x_id)) + SubTreeSize(Right(x_id)) + (Next(x_id) == NIL ? 1 : SubTreeSize(Next(x_id)))));
 518             }
 519
 520             if (y_id != NIL) {
 521                 SetSubTreeSize(y_id, (SubTreeSize(Left(y_id)) + SubTreeSize(Right(y_id)) + (Next(y_id) == NIL ? 1 : SubTreeSize(Next(y_id)))));
 522             }
 523             return root_id;
 524         }
 525
 526 #if VerifySort
 527         // This helps validate the sorting of the tree to help catch instances of corruption much sooner.
 528         // corruption happens when the data changes without telling the tree or when multi-threads do simultanous write operations
 529         private int Compare(int root_id, int x_id, int z_id) {
 530             Debug.Assert(NIL != x_id, "nil left");
 531             Debug.Assert(NIL != z_id, "nil right");
 532             return (root_id == NIL) ? CompareNode (Key (x_id), Key (z_id)) : CompareSateliteTreeNode (Key (x_id), Key (z_id));
 533         }
 534 #endif
 535
 536         /*
 537          * RBInsert()
 538          * root_id: root_id of the tree to which a node has to be inserted. it is NIL for inserting to Main tree.
 539          * x_id    : node_id of node to be inserted
 540          *
 541          * returns: The root of the tree to which the specified node was added. its NIL if the node was added to Main RBTree.
 542          *
 543          * if root_id is NIL -> use CompareNode else use CompareSateliteTreeNode
 544          *
 545          * Satelite tree creation:
 546          * First Duplicate value encountered. Create a *new* tree whose root will have the same key value as the current node.
 547          * The Duplicate tree nodes have same key when used with CompareRecords but distinct record ids.
 548          * The current record at all times will have the same *key* as the duplicate tree root.
 549          */
 550         private int RBInsert (int root_id, int x_id, int mainTreeNodeID, int position, bool append)
 551         {
 552             unchecked{_version++;}
 553
 554             // Insert Node x at the appropriate position
 555             int y_id = NIL;
 556             int z_id = (root_id == NIL) ? root : root_id;  //if non NIL, then use the specifid root_id as tree's root.
 557
 558             if (_accessMethod == TreeAccessMethod.KEY_SEARCH_AND_INDEX && !append)
 559             {
 560                 Debug.Assert(-1 == position, "KEY_SEARCH_AND_INDEX with bad position");
 561                 while (z_id != NIL)  // in-order traverse and find node with a NILL left or right child
 562                 {
 563                     IncreaseSize (z_id);
 564                     y_id = z_id;            // y_id set to the proposed parent of x_id
 565
 566                     int c = (root_id == NIL) ? CompareNode (Key (x_id), Key (z_id)) : CompareSateliteTreeNode (Key (x_id), Key (z_id));
 567
 568                     if (c < 0) {
 569 #if VerifySort
 570                         Debug.Assert((NIL == Left(z_id)) || (0 > Compare(root_id, Left(z_id), z_id)), "Left is not left");
 571 #endif
 572                         z_id = Left (z_id);
 573                     }
 574                     else if (c > 0) {
 575 #if VerifySort
 576                         Debug.Assert((NIL == Right(z_id)) || (0 < Compare(root_id, Right(z_id), z_id)), "Right is not right");
 577 #endif
 578                         z_id = Right (z_id);
 579                     }
 580                     else {
 581                         // Multiple records with same key - insert it to the duplicate record tree associated with current node
 582                         if (root_id != NIL) {
 583                             throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidStateinInsert);
 584                         }
 585                         if (Next(z_id) != NIL) {
 586                             root_id = RBInsert (Next (z_id), x_id, z_id, -1, false); // z_id is existing mainTreeNodeID
 587                             SetKey (z_id, Key (Next (z_id)));
 588 #if VerifyPath
 589                             (new NodePath(x_id, z_id)).VerifyPath(this); // verify x_id after its been added
 590 #endif
 591                         }
 592                         else {
 593                             int newMainTreeNodeId = NIL;
 594                             // The existing node is pushed into the Satellite Tree and a new Node
 595                             // is created in the main tree, whose's next points to satellite root.
 596                             newMainTreeNodeId = GetNewNode (Key (z_id));
 597                             _inUseSatelliteTreeCount++;
 598
 599                             // copy contents of z_id to dupRootId (main tree node).
 600                             SetNext(newMainTreeNodeId, z_id);
 601                             SetColor(newMainTreeNodeId, color(z_id));
 602                             SetParent(newMainTreeNodeId, Parent(z_id));
 603                             SetLeft(newMainTreeNodeId, Left(z_id));
 604                             SetRight(newMainTreeNodeId, Right(z_id));
 605
 606                             // Update z_id's non-nil parent
 607                             if( Left(Parent(z_id))==z_id)
 608                               SetLeft(Parent(z_id), newMainTreeNodeId);
 609                             else if (Right(Parent(z_id))==z_id)
 610                               SetRight(Parent(z_id), newMainTreeNodeId);
 611
 612                             // update children.
 613                             if (Left(z_id) != NIL)
 614                                 SetParent(Left(z_id), newMainTreeNodeId);
 615                             if (Right(z_id) != NIL)
 616                                 SetParent(Right(z_id), newMainTreeNodeId);
 617
 618                             if (root == z_id)
 619                                 root = newMainTreeNodeId;
 620
 621                             // Reset z_id's pointers to NIL. It will start as the satellite tree's root.
 622                             SetColor(z_id, NodeColor.black);
 623                             SetParent(z_id, NIL);
 624                             SetLeft(z_id, NIL);
 625                             SetRight(z_id, NIL);
 626
 627                             int savedSize = SubTreeSize(z_id);
 628                             SetSubTreeSize(z_id, 1);
 629                             // With z_id as satellite root, insert x_id
 630                             root_id = RBInsert (z_id, x_id, newMainTreeNodeId, -1, false);
 631
 632                             SetSubTreeSize(newMainTreeNodeId, savedSize);
 633 #if VerifyPath
 634                             (new NodePath(x_id, newMainTreeNodeId)).VerifyPath(this); // verify x_id after its been added
 635 #endif
 636                         }
 637                         return root_id;
 638                     }
 639                 }
 640             }
 641             else if (_accessMethod == TreeAccessMethod.INDEX_ONLY || append)
 642             {
 643                 if (position == -1) {
 644                     position = SubTreeSize(root);   // append
 645                 }
 646
 647                 while (z_id != NIL)    // in-order traverse and find node with a NILL left or right child
 648                 {
 649                     IncreaseSize (z_id);
 650                     y_id = z_id;            // y_id set to the proposed parent of x_id
 651
 652                     //int c = (SubTreeSize(y_id)-(position)); // Actually it should be: SubTreeSize(y_id)+1 - (position + 1)
 653                     int c = (position) - (SubTreeSize(Left(y_id)));
 654
 655                     if (c <= 0) {
 656                         z_id = Left (z_id);
 657                     }
 658                     else {
 659                         //position = position - SubTreeSize(z_id);
 660                         z_id = Right (z_id);
 661                         if (z_id != NIL) {
 662                             position = c-1;    //skip computation of position for leaf node
 663                         }
 664                     }
 665                 }
 666             }
 667             else {
 668                 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.UnsupportedAccessMethod1);
 669             }
 670
 671             SetParent (x_id, y_id);
 672             if (y_id == NIL)
 673             {
 674                 if (root_id == NIL) {
 675                     root = x_id;
 676                 }
 677                 else
 678                 {
 679                     // technically we should never come here. Satellite tree always has a root and atleast 1 child.
 680                     // if it has only root as it's node, then the satellite tree gets collapsed into the main tree.
 681 #if VerifyPath
 682                     (new NodePath(x_id, mainTreeNodeID)).VerifyPath(this); // verify x_id after its been added
 683 #endif
 684                     SetNext(mainTreeNodeID, x_id);
 685                     SetKey(mainTreeNodeID, Key(x_id));
 686                     root_id = x_id;
 687                 }
 688             }
 689             else
 690             {
 691                 int c=0;
 692                 if (_accessMethod == TreeAccessMethod.KEY_SEARCH_AND_INDEX)
 693                     c = (root_id == NIL) ? CompareNode (Key(x_id), Key(y_id)) : CompareSateliteTreeNode (Key (x_id), Key (y_id));
 694                 else if (_accessMethod == TreeAccessMethod.INDEX_ONLY)
 695                     c = (position <= 0) ? -1 : 1;
 696                 else {
 697                     throw ExceptionBuilder.InternalRBTreeError(RBTreeError.UnsupportedAccessMethod2);
 698                 }
 699
 700                 if (c < 0)
 701                     SetLeft (y_id, x_id);
 702                 else
 703                     SetRight (y_id, x_id);
 704             }
 705
 706             SetLeft (x_id, NIL);
 707             SetRight (x_id, NIL);
 708             SetColor (x_id, NodeColor.red);
 709             z_id = x_id; // for verification later
 710
 711             // fix the tree
 712             while (color (Parent (x_id)) == NodeColor.red)
 713             {
 714                 if (Parent (x_id) == Left (Parent (Parent (x_id))))     // if x.parent is a left child
 715                 {
 716                     y_id = Right (Parent (Parent (x_id)));              // x.parent.parent.right;
 717                     if (color (y_id) == NodeColor.red)              // my right uncle is red
 718                     {
 719                         SetColor (Parent (x_id), NodeColor.black);      // x.parent.color = Color.black;
 720                         SetColor (y_id, NodeColor.black);
 721                         SetColor (Parent (Parent (x_id)), NodeColor.red);   // x.parent.parent.color = Color.red;
 722                         x_id = Parent (Parent (x_id));                     // x = x.parent.parent;
 723                     }
 724                     else
 725                     {     // my right uncle is black
 726                         if (x_id == Right (Parent (x_id)))
 727                         {
 728                             x_id = Parent (x_id);
 729                             root_id = LeftRotate (root_id, x_id, mainTreeNodeID);
 730                         }
 731
 732                         SetColor (Parent (x_id), NodeColor.black);                           // x.parent.color = Color.black;
 733                         SetColor (Parent (Parent (x_id)), NodeColor.red);                 //    x.parent.parent.color = Color.red;
 734                         root_id = RightRotate (root_id, Parent (Parent (x_id)), mainTreeNodeID);   //    RightRotate (x.parent.parent);
 735                     }
 736                 }
 737                 else
 738                 {     // x.parent is a right child
 739                     y_id = Left (Parent (Parent (x_id)));          // y = x.parent.parent.left;
 740                     if (color (y_id) == NodeColor.red)      // if (y.color == Color.red)    // my right uncle is red
 741                     {
 742                         SetColor (Parent (x_id), NodeColor.black);
 743                         SetColor (y_id, NodeColor.black);
 744                         SetColor (Parent (Parent (x_id)), NodeColor.red);   // x.parent.parent.color = Color.red;
 745                         x_id = Parent (Parent (x_id));
 746                     }
 747                     else
 748                     {// my right uncle is black
 749                         if (x_id == Left (Parent (x_id)))
 750                         {
 751                             x_id = Parent (x_id);
 752                             root_id = RightRotate (root_id, x_id, mainTreeNodeID);
 753                         }
 754
 755                         SetColor (Parent (x_id), NodeColor.black);             // x.parent.color = Color.black;
 756                         SetColor (Parent (Parent (x_id)), NodeColor.red);   // x.parent.parent.color = Color.red;
 757                         root_id = LeftRotate (root_id, Parent (Parent (x_id)), mainTreeNodeID);
 758                     }
 759                 }
 760             }
 761
 762             if (root_id == NIL)
 763                 SetColor (root, NodeColor.black);
 764             else
 765                 SetColor (root_id, NodeColor.black);
 766
 767 #if VerifyPath
 768             (new NodePath(z_id, mainTreeNodeID)).VerifyPath(this); // verify x_id after its been added
 769 #endif
 770             return root_id;
 771         } //Insert
 772
 773         public void UpdateNodeKey(K currentKey, K newKey)
 774         {
 775             // swap oldRecord with NewRecord in nodeId associated with oldRecord
 776             // if the matched node is a satellite root then also change the key in the associated main tree node.
 777             NodePath x_id = GetNodeByKey (currentKey);
 778             if (Parent(x_id.NodeID) == NIL && x_id.NodeID != root) //determine if x_id is a satellite root.
 779             {
 780 #if VerifyPath
 781                 x_id.VerifyPath(this);
 782 #endif
 783                 SetKey(x_id.MainTreeNodeID, newKey);
 784             }
 785             SetKey (x_id.NodeID, newKey);
 786         }
 787
 788         public K DeleteByIndex(int i)
 789         {
 790             // This check was not correct, it should have been ((uint)this.Count <= (uint)i)
 791             // Even then, the index will be checked by GetNodebyIndex which will throw either
 792             // using RowOutOfRange or InternalRBTreeError depending on _accessMethod
 793             //
 794             //if (i >= (_inUseNodeCount - 1)) {
 795             //    throw ExceptionBuilder.InternalRBTreeError(RBTreeError.IndexOutOfRange);
 796             //}
 797
 798             K key;
 799             NodePath x_id = GetNodeByIndex(i); // it'l throw if corresponding node does not exist
 800             key = Key(x_id.NodeID);
 801             RBDeleteX(NIL, x_id.NodeID, x_id.MainTreeNodeID);
 802             return key;
 803         }
 804
 805         public int RBDelete (int z_id)
 806         {
 807             // always perform delete operation on the main tree
 808             Debug.Assert(_accessMethod == TreeAccessMethod.INDEX_ONLY, "not expecting anything else");
 809             return RBDeleteX (NIL, z_id, NIL);
 810         }
 811
 812
 813         /*
 814          * RBDelete()
 815          *  root_id: root_id of the tree. it is NIL for Main tree.
 816          *  z_id    : node_id of node to be deleted
 817          *
 818          * returns: The id of the spliced node
 819          *
 820          * Case 1: Node is in main tree only        (decrease size in main tree)
 821          * Case 2: Node's key is shared with a main tree node whose next is non-NIL
 822          *                                       (decrease size in both trees)
 823          * Case 3: special case of case 2: After deletion, node leaves satelite tree with only 1 node (only root),
 824          *             it should collapse the satelite tree - go to case 4. (decrease size in both trees)
 825          * Case 4: (1) Node is in Main tree and is a satelite tree root AND
 826          *             (2) It is the only node in Satelite tree
 827          *                   (Do not decrease size in any tree, as its a collpase operation)
 828          *
 829          */
 830
 831         private int RBDeleteX(int root_id, int z_id, int mainTreeNodeID)
 832         {
 833             int x_id = NIL; // used for holding spliced node (y_id's) child
 834             int y_id;                // the spliced node
 835             int py_id;           // for holding spliced node (y_id's) parent
 836
 837 #if VerifyPath
 838             // by knowing the NodePath, when z_id is in a satellite branch we don't have to Search for mainTreeNodeID
 839             (new NodePath(z_id, mainTreeNodeID)).VerifyPath(this);
 840 #endif
 841             if (Next (z_id) != NIL)
 842                 return RBDeleteX(Next(z_id), Next(z_id), z_id); // delete root of satelite tree.
 843
 844             // if we we reach here, we are guaranteed z_id.next is NIL.
 845             bool isCase3 = false;
 846             int mNode = ((_accessMethod == TreeAccessMethod.KEY_SEARCH_AND_INDEX) ? mainTreeNodeID : z_id);
 847
 848             if (Next (mNode) != NIL)
 849                 root_id = Next (mNode);
 850
 851             if (SubTreeSize (Next (mNode)) == 2) // Next(mNode) == root_id
 852                 isCase3 = true;
 853             else if (SubTreeSize (Next (mNode)) == 1) {
 854                 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidNextSizeInDelete);
 855             }
 856
 857             if (Left (z_id) == NIL || Right (z_id) == NIL)
 858                 y_id = z_id;
 859             else
 860                 y_id = Successor (z_id);
 861
 862             if (Left (y_id) != NIL)
 863                 x_id = Left (y_id);
 864             else
 865                 x_id = Right (y_id);
 866
 867             py_id = Parent(y_id);
 868             if (x_id != NIL)
 869                 SetParent (x_id, py_id);
 870
 871             if (py_id == NIL) // if the spliced node is the root.
 872             {
 873                 // check for main tree or Satellite tree root
 874                 if (root_id == NIL)
 875                     root = x_id;
 876                 else
 877                 {
 878                     // spliced node is root of satellite tree
 879                     root_id = x_id;
 880                 }
 881             }
 882             else if (y_id == Left (py_id))    // update y's parent to point to X as its child
 883                 SetLeft (py_id, x_id);
 884             else
 885                 SetRight (py_id, x_id);
 886
 887             if (y_id != z_id)
 888             {
 889                 // assign all values from y (spliced node) to z (node containing key to be deleted)
 890                 // -----------
 891
 892                 SetKey (z_id, Key (y_id));      // assign all values from y to z
 893                 SetNext (z_id, Next (y_id));    //z.value = y.value;
 894             }
 895
 896             if (Next(mNode) != NIL)
 897             {
 898                 // update mNode to point to satellite tree root and have the same key value.
 899                 // mNode will have to be patched again after RBDeleteFixup as root_id can again change
 900                 if (root_id == NIL && z_id != mNode) {
 901                     throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidStateinDelete);
 902                 }
 903                 // -- it's possible for Next(mNode) to be != NIL and root_id == NIL when, the spliced node is a mNode of some
 904                 // -- satellite tree and its "next" gets assigned to mNode
 905                 if (root_id != NIL)
 906                 {
 907                     SetNext (mNode, root_id);
 908                     SetKey (mNode, Key (root_id));
 909                 }
 910             }
 911
 912             // traverse from y_id's parent to root and decrement size by 1
 913             int tmp_py_id = py_id;
 914             // case: 1, 2, 3
 915             while (tmp_py_id != NIL)
 916             {
 917                 //DecreaseSize (py_id, (Next(y_id)==NIL)?1:Size(Next(y_id)));
 918                 RecomputeSize (tmp_py_id);
 919                 tmp_py_id = Parent (tmp_py_id);
 920             }
 921
 922             //if satelite tree node deleted, decrease size in main tree as well.
 923             if (root_id != NIL)
 924             {
 925                 // case 2, 3
 926                 int nodeId = mNode;
 927                 while (nodeId != NIL)
 928                 {
 929                     DecreaseSize (nodeId);
 930                     nodeId = Parent (nodeId);
 931                 }
 932             }
 933
 934             if (color (y_id) == NodeColor.black)
 935                 root_id = RBDeleteFixup (root_id, x_id, py_id, mainTreeNodeID); // passing x.parent as y.parent, to handle x=Node.NIL case.
 936
 937             if (isCase3)
 938             {
 939                 // Collpase satelite tree, by swapping it with the main tree counterpart and freeing the main tree node
 940                 if (mNode == NIL || SubTreeSize(Next(mNode)) != 1) {
 941                     throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidNodeSizeinDelete);
 942                 }
 943                 _inUseSatelliteTreeCount--;
 944                 int satelliteRootId = Next(mNode);
 945                 SetLeft(satelliteRootId, Left(mNode));
 946                 SetRight(satelliteRootId, Right(mNode));
 947                 SetSubTreeSize(satelliteRootId, SubTreeSize(mNode));
 948                 SetColor(satelliteRootId, color(mNode));  // Next of satelliteRootId is already NIL
 949                 if (Parent(mNode) != NIL)
 950                 {
 951                     SetParent(satelliteRootId, Parent(mNode));
 952                     if (Left(Parent(mNode)) == mNode) {
 953                         SetLeft(Parent(mNode), satelliteRootId);
 954                     }
 955                     else {
 956                         SetRight(Parent(mNode), satelliteRootId);
 957                     }
 958                 }
 959
 960                 // update mNode's children.
 961                 if (Left(mNode) != NIL) {
 962                     SetParent(Left(mNode), satelliteRootId);
 963                 }
 964                 if (Right(mNode) != NIL) {
 965                     SetParent(Right(mNode), satelliteRootId);
 966                 }
 967                 if (root == mNode) {
 968                     root = satelliteRootId;
 969                 }
 970
 971                 FreeNode (mNode);
 972                 mNode = NIL;
 973             }
 974             else if (Next(mNode) != NIL)
 975             {
 976                 // update mNode to point to satellite tree root and have the same key value
 977                 if (root_id == NIL && z_id != mNode) { //if mNode being deleted, its OK for root_id (it should be) NIL.
 978                     throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidStateinEndDelete);
 979                 }
 980
 981                 if (root_id != NIL)
 982                 {
 983                     SetNext (mNode, root_id);
 984                     SetKey (mNode, Key (root_id));
 985                 }
 986
 987             }
 988
 989             // In order to pin a key to it's node, free deleted z_id instead of the spliced y_id
 990             if (y_id != z_id)
 991             {
 992                 // we know that key, next and value are same for z_id and y_id
 993                 SetLeft (y_id, Left (z_id));
 994                 SetRight (y_id, Right (z_id));
 995                 SetColor (y_id, color (z_id));
 996                 SetSubTreeSize (y_id, SubTreeSize(z_id));
 997                 if (Parent(z_id) != NIL)
 998                 {
 999                     SetParent(y_id, Parent(z_id));
1000                     if (Left(Parent(z_id)) == z_id) {
1001                         SetLeft(Parent(z_id), y_id);
1002                     }
1003                     else {
1004                         SetRight(Parent(z_id), y_id);
1005                     }
1006                 }
1007                 else {
1008                     SetParent(y_id, NIL);
1009                 }
1010
1011                 // update children.
1012                 if (Left(z_id) != NIL) {
1013                     SetParent(Left(z_id), y_id);
1014                 }
1015                 if (Right(z_id) != NIL) {
1016                     SetParent(Right(z_id), y_id);
1017                 }
1018
1019                 if (root == z_id) {
1020                     root = y_id;
1021                 }
1022                 else if (root_id == z_id) {
1023                     root_id = y_id;
1024                 }
1025                 // update a next reference to z_id (if any)
1026                 if (mNode != NIL && Next(mNode) == z_id) {
1027                     SetNext(mNode, y_id);
1028                 }
1029             }
1030             FreeNode (z_id);
1031             unchecked{_version++;}
1032             return z_id;
1033         }
1034
1035         /*
1036          * RBDeleteFixup()
1037          * Fix the specified tree for RedBlack properties
1038          *
1039          * returns: The id of the root
1040          */
1041         private int RBDeleteFixup (int root_id, int x_id, int px_id /* px is parent of x */, int mainTreeNodeID)
1042         {    //x is successor's non nil child or nil if both children are nil
1043             int w_id;
1044
1045 #if VerifyPath
1046             // by knowing the NodePath, when z_id is in a satellite branch we don't have to Search for mainTreeNodeID
1047             (new NodePath(root_id, mainTreeNodeID)).VerifyPath(this);
1048 #endif
1049
1050             if (x_id == NIL && px_id == NIL) {
1051                 return NIL; //case of satelite tree root being deleted.
1052             }
1053
1054             while (((root_id == NIL ? root : root_id) != x_id) && color (x_id) == NodeColor.black)
1055             {
1056                 // (1) x's parent should have aleast 1 non-NIL child.
1057                 // (2) check if x is a NIL left child or a non NIL left child
1058                 if ((x_id != NIL && x_id == Left (Parent (x_id))) || (x_id == NIL && Left (px_id) == NIL))
1059                 {
1060                   // we have from DELETE, then x cannot be NIL and be a right child of its parent
1061                   // also from DELETE, if x is non nil, it will be a left child.
1062                     w_id = (x_id == NIL) ? Right (px_id) : Right (Parent (x_id));     // w is x's right sibling and it cannot be NIL
1063
1064                     if (w_id == NIL) {
1065                         throw ExceptionBuilder.InternalRBTreeError(RBTreeError.RBDeleteFixup);
1066                     }
1067
1068                     if (color (w_id) == NodeColor.red)
1069                     {
1070                         SetColor (w_id, NodeColor.black);
1071                         SetColor (px_id, NodeColor.red);
1072                         root_id = LeftRotate (root_id, px_id, mainTreeNodeID);
1073                         w_id = (x_id == NIL) ? Right (px_id) : Right (Parent (x_id));
1074                     }
1075
1076                     if (color (Left (w_id)) == NodeColor.black && color (Right (w_id)) == NodeColor.black)
1077                     {
1078                         SetColor (w_id, NodeColor.red);
1079                         x_id = px_id;
1080                         px_id = Parent (px_id); //maintain px_id
1081                     }
1082                     else
1083                     {
1084                         if (color (Right (w_id)) == NodeColor.black)
1085                         {
1086                             SetColor (Left (w_id), NodeColor.black);
1087                             SetColor (w_id, NodeColor.red);
1088                             root_id = RightRotate (root_id, w_id, mainTreeNodeID);
1089                             w_id = (x_id == NIL) ? Right (px_id) : Right (Parent (x_id));
1090                         }
1091
1092                         SetColor (w_id, color (px_id));
1093                         SetColor (px_id, NodeColor.black);
1094                         SetColor (Right (w_id), NodeColor.black);
1095                         root_id = LeftRotate (root_id, px_id, mainTreeNodeID);
1096
1097                         x_id = (root_id == NIL) ? root : root_id;
1098                         px_id = Parent (x_id);
1099                     }
1100                 }
1101                 else
1102                 {  //x is a right child or it is NIL
1103                     w_id = Left (px_id);
1104                     if (color (w_id) == NodeColor.red)
1105                     {   // x_id is y's (the spliced node) sole non-NIL child or NIL if y had no children
1106                         SetColor (w_id, NodeColor.black);
1107                         if (x_id != NIL) {
1108                             SetColor (px_id, NodeColor.red);
1109                             root_id = RightRotate (root_id, px_id, mainTreeNodeID);
1110                             w_id = (x_id == NIL) ? Left (px_id) : Left (Parent (x_id));
1111                         }
1112                         else {
1113                             //we have from DELETE, then x cannot be NIL and be a right child of its parent
1114                             // w_id cannot be nil.
1115                             SetColor (px_id, NodeColor.red);
1116                             root_id = RightRotate (root_id, px_id, mainTreeNodeID);
1117                             w_id = (x_id == NIL) ? Left (px_id) : Left (Parent (x_id));
1118
1119                             if (w_id == NIL) {
1120                                 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.CannotRotateInvalidsuccessorNodeinDelete);
1121                             }
1122                         }
1123                     }
1124
1125                     if (color (Right (w_id)) == NodeColor.black && color (Left (w_id)) == NodeColor.black) {
1126                         SetColor (w_id, NodeColor.red);
1127                         x_id = px_id;
1128                         px_id = Parent (px_id);
1129                     }
1130                     else {
1131                         if (color (Left (w_id)) == NodeColor.black)
1132                         {
1133                             SetColor (Right (w_id), NodeColor.black);
1134                             SetColor (w_id, NodeColor.red);
1135                             root_id = LeftRotate (root_id, w_id, mainTreeNodeID);
1136                             w_id = (x_id == NIL) ? Left (px_id) : Left (Parent (x_id));
1137                         }
1138
1139                         if (x_id != NIL)
1140                         {
1141                             SetColor (w_id, color (px_id));
1142                             SetColor (px_id, NodeColor.black);
1143                             SetColor (Left (w_id), NodeColor.black);
1144                             root_id = RightRotate (root_id, px_id, mainTreeNodeID);
1145
1146                             x_id = (root_id == NIL) ? root : root_id;
1147                             px_id = Parent (x_id);
1148                         }
1149                         else
1150                         {
1151                             SetColor (w_id, color (px_id));
1152                             SetColor (px_id, NodeColor.black);
1153                             SetColor (Left (w_id), NodeColor.black);
1154                             root_id = RightRotate (root_id, px_id, mainTreeNodeID);
1155
1156                             x_id = (root_id == NIL) ? root : root_id;
1157                             px_id = Parent (x_id);
1158                         }
1159                     }
1160                 }
1161             }
1162
1163             SetColor (x_id, NodeColor.black);
1164             return root_id;
1165         }
1166
1167         private int SearchSubTree (int root_id, K key)
1168         {
1169             if (root_id != NIL &&  _accessMethod!=TreeAccessMethod.KEY_SEARCH_AND_INDEX) {
1170                 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.UnsupportedAccessMethodInNonNillRootSubtree);
1171             }
1172
1173             int x_id = (root_id == NIL) ? root : root_id;
1174             int c;
1175             while (x_id != NIL)
1176             {
1177                 c = (root_id == NIL) ? CompareNode (key, Key (x_id)) : CompareSateliteTreeNode (key, Key (x_id));
1178                 if (c == 0) {
1179                     break;
1180                 }
1181                 if (c < 0) {
1182 #if VerifySort
1183                     Debug.Assert((NIL == Left(x_id)) || (0 > Compare(root_id, Left(x_id), x_id)), "Search duplicate Left is not left");
1184 #endif
1185                     x_id = Left (x_id);
1186                 }
1187                 else {
1188 #if VerifySort
1189                     Debug.Assert((NIL == Right(x_id)) || (0 < Compare(root_id, Right(x_id), x_id)), "Search duplicate Right is not right");
1190 #endif
1191                     x_id = Right (x_id);
1192                 }
1193             }
1194             return x_id;
1195         }
1196
1197         // only works on the main tree - does not work with satelite tree
1198         public int Search (K key)
1199         {   // for performance reasons, written as a while loop instead of a recursive method
1200             int x_id = root;
1201             int c;
1202             while (x_id != NIL)
1203             {
1204                 c = CompareNode (key, Key (x_id));
1205                 if (c == 0) {
1206                     break;
1207                 }
1208                 if (c < 0) {
1209 #if VerifySort
1210                     Debug.Assert((NIL == Left(x_id)) || (0 > Compare(NIL, Left(x_id), x_id)), "Search Left is not left");
1211 #endif
1212                     x_id = Left (x_id);
1213                 }
1214                 else {
1215 #if VerifySort
1216                     Debug.Assert((NIL == Right(x_id)) || (0 < Compare(NIL, Right(x_id), x_id)), "Search Right is not right");
1217 #endif
1218                     x_id = Right (x_id);
1219                 }
1220             }
1221             return x_id;
1222         }
1223
1224         // To simulate direct access for records[index]= record
1225         /// <summary>
1226         ///  return key associated with the specified value. Specifically, return record for specified index/value
1227         ///  indexer
1228         /// </summary>
1229         /// <exception cref="IndexOutOfRangeException"></exception>
1230         // return record i.e key at specified index
1231         public K this[int index]
1232         {
1233             get
1234             {
1235                 return Key(GetNodeByIndex(index).NodeID);
1236             }
1237         }
1238
1239         // Get Record(s) having same key value as that of specified record. Then scan the matched nodes
1240         // and return the node with the matching record
1241         /// <returns>Determine node and the branch it took to get there.</returns>
1242         private NodePath GetNodeByKey(K key) //i.e. GetNodeByKey
1243         {
1244             int nodeId = SearchSubTree(NIL, key);
1245             if (Next (nodeId) != NIL) {
1246                 return new NodePath(SearchSubTree(Next(nodeId), key), nodeId);
1247             }
1248             else if (!Key(nodeId).Equals(key)) {
1249                 nodeId = NIL;
1250             }
1251             return new NodePath(nodeId, NIL);
1252         }
1253
1254         /*
1255          * GetIndexByRecord()
1256          * Gets index of the specified record. returns (-1) if specified record is not found.
1257          */
1258         public int GetIndexByKey (K key)
1259         {
1260             int nodeIndex = -1;
1261             NodePath nodeId = GetNodeByKey (key);
1262             if (nodeId.NodeID != NIL) {
1263                 nodeIndex = GetIndexByNodePath (nodeId);
1264             }
1265             return nodeIndex;
1266         }
1267
1268
1269         /*
1270
1271          * GetIndexByNode()
1272          *
1273          * If I am right child then size=my size + size of left child of my parent + 1
1274          * go up till root, if right child keep adding to the size.
1275          * (1) compute rank in main tree.
1276          * (2) if node member of a satelite tree, add to rank its relative rank in that tree.
1277          *
1278          * Rank:
1279          * Case 1: Node is in Main RBTree only
1280          *         Its rank/index is its main tree index
1281          * Case 2: Node is in a Satelite tree only
1282          *         Its rank/index is its satelite tree index
1283          * Case 3: Nodes is in both Main and Satelite RBTree (a main tree node can be a satelite tree root)
1284          *         Its rank/index is its main tree index + its satelite tree index - 1
1285          * Returns the index of the specified node.
1286          * returns -1, if the specified Node is tree.NIL.
1287          *
1288          * Assumption: The specified node always exist in the tree.
1289          */
1290         // SQLBU 428961: Serious performance issue when creating DataView
1291         // this improves performance when used heavily, like with the default view (creating before rows added)
1292         public int GetIndexByNode (int node)
1293         {
1294             Debug.Assert(NIL != node, "GetIndexByNode(NIL)");
1295
1296             if (0 == _inUseSatelliteTreeCount)
1297             {   // compute from the main tree when no satellite branches exist
1298                 return ComputeIndexByNode(node);
1299             }
1300             else if (NIL != Next(node))
1301             {   // node is a main tree node
1302 #if VerifyIndex && VerifyPath
1303                 (new NodePath(Next(node), node)).VerifyPath(this);
1304 #endif
1305                 return ComputeIndexWithSatelliteByNode(node);
1306             }
1307             else
1308             {
1309                 int mainTreeNodeId = SearchSubTree(NIL, Key(node));
1310                 if (mainTreeNodeId == node)
1311                 {   // node is a main tree node
1312 #if VerifyIndex && VerifyPath
1313                     (new NodePath(node, NIL)).VerifyPath(this);
1314 #endif
1315                     return ComputeIndexWithSatelliteByNode(node);
1316                 }
1317                 else
1318                 {   //compute the main tree rank + satellite branch rank
1319 #if VerifyIndex && VerifyPath
1320                     (new NodePath(node, mainTreeNodeId)).VerifyPath(this);
1321 #endif
1322                     return ComputeIndexWithSatelliteByNode(mainTreeNodeId) +
1323                            ComputeIndexByNode(node);
1324                 }
1325             }
1326         }
1327
1328         /// <summary>Determine tree index position from node path.</summary>
1329         /// <remarks>This differs from GetIndexByNode which would search for the main tree node instead of just knowing it</remarks>
1330         private int GetIndexByNodePath(NodePath path)
1331         {
1332 #if VerifyIndex && VerifyPath
1333             path.VerifyPath(this);
1334 #endif
1335             if (0 == _inUseSatelliteTreeCount)
1336             {   // compute from the main tree when no satellite branches exist
1337                 return ComputeIndexByNode(path.NodeID);
1338             }
1339             else if (NIL == path.MainTreeNodeID)
1340             {   // compute from the main tree accounting for satellite branches
1341                 return ComputeIndexWithSatelliteByNode(path.NodeID);
1342             }
1343             else
1344             {   //compute the main tree rank + satellite branch rank
1345                 return ComputeIndexWithSatelliteByNode(path.MainTreeNodeID) +
1346                        ComputeIndexByNode(path.NodeID);
1347             }
1348         }
1349
1350         private int ComputeIndexByNode(int nodeId) {
1351 #if VerifyIndex
1352             Debug.Assert(NIL != nodeId, "ComputeIndexByNode(NIL)");
1353 #endif
1354             int myRank = SubTreeSize(Left(nodeId));
1355             while (nodeId != NIL)
1356             {
1357 #if VerifyIndex && VerifyPath
1358                 Debug.Assert(NIL == Next(nodeId), "Next not NIL");
1359 #endif
1360                 int parent = Parent(nodeId);
1361                 if (nodeId == Right(parent))
1362                 {
1363                     myRank += (SubTreeSize(Left(parent)) + 1);
1364                 }
1365                 nodeId = parent;
1366             }
1367             return myRank;
1368         }
1369
1370         private int ComputeIndexWithSatelliteByNode(int nodeId) {
1371 #if VerifyIndex
1372             Debug.Assert(NIL != nodeId, "ComputeIndexWithSatelliteByNode(NIL)");
1373 #endif
1374             int myRank = SubTreeSize(Left(nodeId));
1375             while (nodeId != NIL)
1376             {
1377                 int parent = Parent(nodeId);
1378                 if (nodeId == Right(parent))
1379                 {
1380                     myRank += (SubTreeSize(Left(parent)) + ((Next(parent) == NIL) ? 1 : SubTreeSize(Next(parent))));
1381                 }
1382                 nodeId = parent;
1383             }
1384             return myRank;
1385         }
1386
1387         /// <returns>Determine node and the branch it took to get there.</returns>
1388         /// <exception cref="IndexOutOfRangeException"></exception>
1389         private NodePath GetNodeByIndex(int userIndex)
1390         {
1391             int x_id, satelliteRootId;
1392             if (0 == _inUseSatelliteTreeCount) {
1393                 // if rows were only contigously append, then using (userIndex -= _pageTable[i].InUseCount) would
1394                 // be faster for the first 12 pages (about 5248) nodes before (log2 of Count) becomes faster again.
1395                 // the additional complexity was deemed not worthy for the possible perf gain
1396
1397                 // computation cost is (log2 of Count)
1398                 x_id = ComputeNodeByIndex(root, unchecked(userIndex + 1));
1399                 satelliteRootId = NIL;
1400             }
1401             else {
1402                 // computation cost is ((log2 of Distinct Count) + (log2 of Duplicate Count))
1403                 x_id = ComputeNodeByIndex(userIndex, out satelliteRootId);
1404             }
1405             if (x_id == NIL) {
1406                 if (TreeAccessMethod.INDEX_ONLY == _accessMethod) {
1407                     throw ExceptionBuilder.RowOutOfRange(userIndex);
1408                 }
1409                 else {
1410                     throw ExceptionBuilder.InternalRBTreeError(RBTreeError.IndexOutOFRangeinGetNodeByIndex);
1411                 }
1412             }
1413             return new NodePath(x_id, satelliteRootId);
1414         }
1415
1416         private int ComputeNodeByIndex(int index, out int satelliteRootId)
1417         {
1418             index  = unchecked(index + 1); // index is 0 based, while size is 1 based.
1419             satelliteRootId = NIL;
1420             int x_id = root;
1421
1422             int rank = -1;
1423             while (x_id != NIL && !(((rank = SubTreeSize (Left (x_id)) + 1) == index) && Next (x_id) == NIL))
1424             {
1425                 if (index < rank) {
1426                     x_id = Left (x_id);
1427                 }
1428                 else if (Next (x_id) != NIL && index >= rank && index <= rank + SubTreeSize (Next (x_id)) - 1)
1429                 {
1430                     // node with matching index is in the associated satellite tree. continue searching for index in satellite tree.
1431                     satelliteRootId = x_id;
1432                     index = index - rank + 1; // rank is SubTreeSize(Node.left)+1, we do +1 here to offset +1 done in rank. index -= rank;
1433                     return ComputeNodeByIndex(Next(x_id), index); //satellite tree root
1434                 }
1435                 else
1436                 {
1437                     if (Next (x_id) == NIL)
1438                         index -= rank;
1439                     else
1440                         index -= rank + SubTreeSize (Next (x_id)) - 1;
1441
1442                     x_id = Right (x_id);
1443                 }
1444             }
1445             return x_id;
1446         }
1447
1448         private int ComputeNodeByIndex(int x_id, int index) {
1449             while (x_id != NIL) {
1450                 Debug.Assert(NIL == Next(x_id), "has unexpected satellite tree");
1451
1452                 int y_id = Left(x_id);
1453                 int rank = SubTreeSize(y_id) + 1;
1454                 if (index < rank) {
1455                     x_id = y_id;
1456                 }
1457                 else if (rank < index) {
1458                     x_id = Right(x_id);
1459                     index -= rank;
1460                 }
1461                 else {
1462                     break;
1463                 }
1464             }
1465             return x_id;
1466         }
1467
1468 #if DEBUG
1469         // return true if all nodes are unique; i.e. no satelite trees.
1470         public bool CheckUnique (int curNodeId)
1471         {
1472             if (curNodeId != NIL)
1473             {
1474                 if (Next (curNodeId) != NIL)
1475                     return false;    // atleast 1 duplicate found
1476
1477                 if (!CheckUnique (Left (curNodeId)) || !CheckUnique (Right (curNodeId)))
1478                     return false;
1479             }
1480
1481             return true;
1482         }
1483 #endif
1484
1485         public int Insert (K item)
1486         {
1487             int nodeId = GetNewNode(item);
1488
1489             RBInsert (NIL, nodeId, NIL, -1, false);
1490             return nodeId;
1491         }
1492
1493         // Begin: List of methods for making it easy to work with ArrayList
1494
1495         public int Add(K item) //Insert (int record)
1496         {
1497             int nodeId = GetNewNode (item);
1498             RBInsert(NIL, nodeId, NIL, -1, false);
1499             return nodeId;
1500         }
1501
1502         public IEnumerator GetEnumerator() {
1503             return new RBTreeEnumerator(this);
1504         }
1505
1506         // *****BruteForceImplementation*****
1507         //
1508         // iterate over all nodes, InOrder and return index of node with the specified Item
1509         // For the short term use a recursive method, later re-write it based on a stack data structure (if needed)
1510         public int IndexOf (int nodeId, K item)
1511         {
1512             int index = -1;
1513             // BIG ASSUMPTION: There is not satellite tree, this is INDEX_ONLY.
1514             if (nodeId != NIL)
1515             {
1516                 if ( (Object) Key(nodeId) == (Object)item) {
1517                     return GetIndexByNode(nodeId);
1518                 }
1519                 if ( (index=IndexOf(Left(nodeId), item)) != -1) {
1520                     return index;
1521                 }
1522                 if ( (index=IndexOf(Right(nodeId), item)) != -1) {
1523                     return index;
1524                 }
1525             }
1526
1527             return index;
1528         }
1529
1530         public int Insert(int position, K item) //Insert (int record)
1531         {
1532             return InsertAt(position, item, false);
1533         }
1534
1535
1536         public int InsertAt(int position, K item, bool append)
1537         {
1538             int nodeId = GetNewNode (item);
1539             RBInsert (NIL, nodeId, NIL, position, append);
1540             return nodeId;
1541         }
1542
1543         public void RemoveAt(int position)
1544         {
1545             DeleteByIndex(position);
1546         }
1547
1548         public void Clear()
1549         {
1550             InitTree();
1551             unchecked{_version++;}
1552         }
1553
1554         public void CopyTo(Array array, int index) {
1555             if (array==null) {
1556                 throw ExceptionBuilder.ArgumentNull("array");
1557             }
1558             if (index < 0) {
1559                 throw ExceptionBuilder.ArgumentOutOfRange("index");
1560             }
1561
1562             int count = Count;
1563             if (array.Length - index < Count) {
1564                 throw ExceptionBuilder.InvalidOffsetLength();
1565             }
1566
1567             int x_id = Minimum(root);
1568             for(int i = 0; i < count; ++i) {
1569                 array.SetValue(Key(x_id), index + i);
1570                 x_id = Successor(x_id);
1571             }
1572         }
1573
1574         public void CopyTo(K[] array, int index) {
1575             if (array==null) {
1576                 throw ExceptionBuilder.ArgumentNull("array");
1577             }
1578             if (index < 0) {
1579                 throw ExceptionBuilder.ArgumentOutOfRange("index");
1580             }
1581             int count = Count;
1582             if (array.Length - index < Count) {
1583                 throw ExceptionBuilder.InvalidOffsetLength();
1584             }
1585
1586             int x_id = Minimum(root);
1587             for(int i = 0; i < count; ++i) {
1588                 array[index + i] = Key(x_id);
1589                 x_id = Successor(x_id);
1590             }
1591         }
1592
1593         // End: List of methods for making it easy to work with ArrayList
1594
1595         private void SetRight (int nodeId, int rightNodeId)
1596         {
1597             /*
1598             TreePage page = _pageTable[nodeId >> 16];
1599             int slotIndex = nodeId & 0xFFFF;
1600             page.Slots[slotIndex].rightId = rightNodeId;
1601             */
1602             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].rightId = rightNodeId;
1603         }
1604
1605         private void SetLeft (int nodeId, int leftNodeId)
1606         {
1607             /*
1608             TreePage page = _pageTable[nodeId >> 16];
1609             int slotIndex = nodeId & 0xFFFF;
1610             page.Slots[slotIndex].leftId = leftNodeId;
1611             */
1612             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].leftId = leftNodeId;
1613         }
1614
1615         private void SetParent (int nodeId, int parentNodeId)
1616         {
1617             Debug.Assert(nodeId != NIL, " in SetParent  nodeId == NIL");
1618             /*
1619             TreePage page = _pageTable[nodeId >> 16];
1620             int slotIndex = nodeId & 0xFFFF;
1621             page.Slots[slotIndex].parentId = parentNodeId;
1622             */
1623             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].parentId = parentNodeId;
1624         }
1625
1626         private void SetColor (int nodeId, NodeColor color)
1627         {
1628             Debug.Assert(nodeId != NIL, " in SetColor  nodeId == NIL");
1629             /*
1630             TreePage page = _pageTable[nodeId >> 16];
1631             int slotIndex = nodeId & 0xFFFF;
1632             page.Slots[slotIndex].nodeColor = color;
1633             */
1634             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].nodeColor = color;
1635         }
1636
1637         private void SetKey (int nodeId, K key)
1638         {
1639             /*
1640             TreePage page = _pageTable[nodeId >> 16];
1641             int slotIndex = nodeId & 0xFFFF;
1642             page.Slots[slotIndex].keyOfNode = key;
1643             */
1644             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].keyOfNode = key;
1645         }
1646
1647         private void SetNext (int nodeId, int nextNodeId)
1648         {
1649             /*
1650             TreePage page = _pageTable[nodeId >> 16];
1651             int slotIndex = nodeId & 0xFFFF;
1652             page.Slots[slotIndex].nextId = nextNodeId;
1653             */
1654             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].nextId = nextNodeId;
1655         }
1656
1657         private void SetSubTreeSize (int nodeId, int size)
1658         {
1659             Debug.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");
1662             // SQLBU 428961: Serious performance issue when creating DataView
1663             // this improves performance by reducing the impact of this heavily used method
1664             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].subTreeSize = size;
1665             VerifySize(nodeId, size);
1666         }
1667
1668         private void IncreaseSize (int nodeId)
1669         {
1670             /*
1671             TreePage page = _pageTable[nodeId >> 16];
1672             int slotIndex = nodeId & 0xFFFF;
1673             page.Slots[slotIndex].subTreeSize += 1;
1674             */
1675             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].subTreeSize += 1;
1676         }
1677
1678
1679         private void RecomputeSize(int nodeId)
1680         {
1681             int myCorrectSize = SubTreeSize (Left (nodeId)) + SubTreeSize (Right (nodeId)) + (Next (nodeId) == NIL ? 1 : SubTreeSize (Next (nodeId)));
1682             /*
1683             TreePage page = _pageTable[nodeId >> 16];
1684             int slotIndex = nodeId & 0xFFFF;
1685             page.Slots[slotIndex].subTreeSize = myCorrectSize;
1686             */
1687             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].subTreeSize = myCorrectSize;
1688         }
1689
1690         private void DecreaseSize (int nodeId)
1691         {
1692             /*
1693             TreePage page = _pageTable[nodeId >> 16];
1694             int slotIndex = nodeId & 0xFFFF;
1695             page.Slots[slotIndex].subTreeSize -= 1;
1696             */
1697             _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].subTreeSize -= 1;
1698             VerifySize(nodeId, _pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].subTreeSize);
1699         }
1700
1701         [ConditionalAttribute("DEBUG")]
1702         private void VerifySize(int nodeId, int size) {
1703             int myCorrectSize = SubTreeSize(Left(nodeId)) + SubTreeSize(Right(nodeId)) + (Next(nodeId) == NIL ? 1 : SubTreeSize(Next(nodeId)));
1704             Debug.Assert(myCorrectSize == size, "VerifySize");
1705         }
1706
1707         public int Right (int nodeId)
1708         {
1709             /*
1710             TreePage page = _pageTable[nodeId >> 16];
1711             int slotIndex = nodeId & 0xFFFF;
1712             int rightId = page.Slots[slotIndex].rightId;
1713             return rightId;
1714             */
1715             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].rightId);
1716         }
1717
1718         public int Left (int nodeId)
1719         {
1720             /*
1721             TreePage page = _pageTable[nodeId >> 16];
1722             int slotIndex = nodeId & 0xFFFF;
1723             int leftId = page.Slots[slotIndex].leftId;
1724             return leftId;
1725             */
1726             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].leftId);
1727         }
1728
1729         public int Parent (int nodeId)
1730         {
1731             /*
1732             TreePage page = _pageTable[nodeId >> 16];
1733             int slotIndex = nodeId & 0xFFFF;
1734             int parentId = page.Slots[slotIndex].parentId;
1735             return parentId;
1736             */
1737             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].parentId);
1738         }
1739
1740         private NodeColor color (int nodeId)
1741         {
1742             /*
1743             TreePage page = _pageTable[nodeId >> 16];
1744             int slotIndex = nodeId & 0xFFFF;
1745             NodeColor col = page.Slots[slotIndex].nodeColor;
1746             return col;
1747             */
1748             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].nodeColor);
1749         }
1750
1751         public int Next (int nodeId)
1752         {
1753             /*
1754             TreePage page = _pageTable[nodeId >> 16];
1755             int slotIndex = nodeId & 0xFFFF;
1756             int nextId = page.Slots[slotIndex].nextId;
1757             return nextId;
1758             */
1759             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].nextId);
1760         }
1761
1762         public int SubTreeSize (int nodeId)
1763         {
1764             /*
1765             TreePage page = _pageTable[nodeId >> 16];
1766             int slotIndex = nodeId & 0xFFFF;
1767             int size = page.Slots[slotIndex].subTreeSize;
1768             return size;
1769             */
1770             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].subTreeSize);
1771         }
1772
1773         public K Key (int nodeId)
1774         {
1775             /*
1776             TreePage page = _pageTable[nodeId >> 16];
1777             int slotIndex = nodeId & 0xFFFF;
1778             K key = page.Slots[slotIndex].keyOfNode;
1779             return key;
1780             */
1781             return (_pageTable[nodeId >> 16].Slots[nodeId & 0xFFFF].keyOfNode);
1782         }
1783
1784         private enum NodeColor {
1785             red   = 0,
1786             black = 1,
1787         };
1788
1789         private struct Node
1790         {
1791             internal int selfId;
1792             internal int leftId;
1793             internal int rightId;
1794             internal int parentId;
1795             internal int nextId;      // multiple records associated with same key
1796             internal int subTreeSize;     // number of nodes in subtree rooted at the current node
1797             internal K keyOfNode;
1798             internal NodeColor nodeColor;
1799         }
1800
1801
1802         /// <summary>Represents the node in the tree and the satellite branch it took to get there.</summary>
1803         private struct NodePath
1804         {
1805             /// <summary>Represents the node in the tree</summary>
1806             internal readonly int NodeID;
1807
1808             /// <summary>
1809             /// When not NIL, it represents the fact NodeID is has duplicate values in the tree.
1810             /// This is the 'fake' node in the main tree that redirects to the root of the satellite tree.
1811             /// By tracking this value, we don't have to repeatedly search for this node.
1812             /// </summary>
1813             internal readonly int MainTreeNodeID;
1814
1815             internal NodePath(int nodeID, int mainTreeNodeID)
1816             {
1817                 NodeID = nodeID;
1818                 MainTreeNodeID = mainTreeNodeID;
1819             }
1820
1821 #if VerifyPath
1822             internal void VerifyPath(RBTree<K> tree)
1823             {
1824                 Debug.Assert(null != tree, "null tree");
1825                 Debug.Assert((NIL == NodeID && NIL == MainTreeNodeID) || (NIL != NodeID), "MainTreeNodeID is not NIL");
1826
1827                 if (NIL != MainTreeNodeID)
1828                 {
1829                     Debug.Assert(NIL != tree.Next(MainTreeNodeID), "MainTreeNodeID should have a Next");
1830                     int node = MainTreeNodeID;
1831                     while (NIL != tree.Parent(node))
1832                     {
1833                         node = tree.Parent(node);
1834                     }
1835                     Debug.Assert(tree.root == node, "MainTreeNodeID parent change doesn't align");
1836                 }
1837                 if (NIL != NodeID)
1838                 {
1839                     Debug.Assert(NIL == tree.Next(NodeID), "NodeID should not have a Next");
1840                     int node = NodeID;
1841                     if (NIL == MainTreeNodeID) {
1842                         while (NIL != tree.Parent(node))
1843                         {
1844                             node = tree.Parent(node);
1845                         }
1846                     }
1847                     else {
1848                         while (NIL != tree.Parent(node))
1849                         {
1850                             Debug.Assert(NIL == tree.Next(node), "duplicate node should not have a next");
1851                             node = tree.Parent(node);
1852                         }
1853                     }
1854                     Debug.Assert((NIL == MainTreeNodeID && tree.root == node) ||
1855                                  (tree.Next(MainTreeNodeID) == node), "NodeID parent change doesn't align");
1856                 }
1857             }
1858 #endif
1859         }
1860
1861         private sealed class TreePage {
1862             public  const Int32 slotLineSize = 32;
1863
1864             internal readonly Node[] Slots;             // List of slots
1865             internal readonly Int32[] SlotMap;          // CEILING(slots.size/slotLineSize)
1866             private Int32 _inUseCount;          // 0 to _slots.size
1867             private Int32 _pageId;              // Page's Id
1868             private Int32 _nextFreeSlotLine;    // o based position of next free slot line
1869
1870             /*
1871              * size: number of slots per page. Maximum allowed is 64K
1872              */
1873             internal TreePage (int size)
1874             {
1875                 if (size > 64 * 1024) {
1876                     throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidPageSize);
1877                 }
1878                 Slots = new Node[size];
1879                 SlotMap = new Int32[(size + slotLineSize - 1) / slotLineSize];
1880             }
1881
1882             /*
1883              * Allocate a free slot from the current page belonging to the specified tree.
1884              * return the Id of the allocated slot, or -1 if the current page does not have any free slots.
1885              */
1886             internal int AllocSlot (RBTree<K> tree)
1887             {
1888                 int segmentPos = 0;  // index into _SlotMap
1889                 Int32 freeSlot = 0;  // Uint, slot offset within the segment
1890                 int freeSlotId = -1; // 0 based slot position
1891
1892                 if (_inUseCount < Slots.Length)
1893                 {
1894                     segmentPos = _nextFreeSlotLine;
1895                     while (segmentPos < SlotMap.Length)
1896                     {
1897                         if (((UInt32)SlotMap[segmentPos]) < 0xFFFFFFFF)
1898                         {
1899                             freeSlotId = 0;
1900                             freeSlot = (~(SlotMap[segmentPos])) & (SlotMap[segmentPos] + 1);
1901
1902                             // avoid string concat to allow debug code to run faster
1903                             Debug.Assert((SlotMap[segmentPos] & freeSlot) == 0,"Slot position segment[segmentPos ]: [freeSlot] is in use. Expected to be empty");
1904
1905                             SlotMap[segmentPos] |= freeSlot; //mark free slot as used.
1906                             _inUseCount++;
1907                             if (_inUseCount == Slots.Length) // mark page as full
1908                                 tree.MarkPageFull (this);
1909                             tree._inUseNodeCount++;
1910
1911                             // convert freeSlotPos to int value giving number of 0's to its right i.e. freeSlotId
1912                             freeSlotId = GetIntValueFromBitMap((uint)freeSlot);
1913
1914                             _nextFreeSlotLine = segmentPos;
1915                             freeSlotId = (segmentPos * TreePage.slotLineSize) + freeSlotId;
1916                             break;
1917                         }
1918                         else
1919                         {
1920                             segmentPos++;
1921                         }
1922                     }
1923
1924                     if (freeSlotId == -1 && _nextFreeSlotLine != 0)
1925                     {
1926                         //Try one more time, starting from 0th segment position to locate a free slot.
1927                         _nextFreeSlotLine = 0;
1928                         freeSlotId = AllocSlot (tree);
1929                     }
1930                 }
1931
1932                 return freeSlotId; // 0 based slot position
1933             }
1934
1935             internal Int32 InUseCount
1936             {
1937                 get {return _inUseCount;}
1938                 set {_inUseCount = value;}
1939             }
1940
1941             internal Int32 PageId
1942             {
1943                 get { return _pageId; }
1944                 set { _pageId = value; }
1945             }
1946         }
1947
1948
1949         // SQLBU 428961: Serious performance issue when creating DataView
1950         // this improves performance allowing to iterating of the index instead of computing record by index
1951         // changes are required to handle satellite nodes which do not exist in DataRowCollection
1952         // enumerator over index will not be handed to the user, only used internally
1953
1954         // instance of this enumerator will be handed to the user via DataRowCollection.GetEnumerator()
1955         internal struct RBTreeEnumerator : System.Collections.Generic.IEnumerator<K>, System.Collections.IEnumerator
1956         {
1957             private readonly RBTree<K> tree;
1958             private readonly int version;
1959             private int index, mainTreeNodeId;
1960             private K current;
1961
1962             internal RBTreeEnumerator(RBTree<K> tree) {
1963                 this.tree = tree;
1964                 version = tree._version;
1965                 index = NIL;
1966                 mainTreeNodeId = tree.root;
1967                 current = default(K);
1968             }
1969
1970             internal RBTreeEnumerator(RBTree<K> tree, int position)
1971             {
1972                 this.tree = tree;
1973                 version = tree._version;
1974                 if (0 == position)
1975                 {
1976                     index = NIL;
1977                     mainTreeNodeId = tree.root;
1978                 }
1979                 else
1980                 {
1981                     index = tree.ComputeNodeByIndex(position-1, out mainTreeNodeId);
1982                     if (NIL == index)
1983                     {
1984                         throw ExceptionBuilder.InternalRBTreeError(RBTreeError.IndexOutOFRangeinGetNodeByIndex);
1985                     }
1986                 }
1987                 current = default(K);
1988             }
1989
1990             public void Dispose() {
1991             }
1992
1993             public bool MoveNext() {
1994                 if (version != tree._version) {
1995                     throw ExceptionBuilder.EnumeratorModified();
1996                 }
1997
1998                 bool hasCurrent = tree.Successor(ref index, ref mainTreeNodeId);
1999                 current = tree.Key(index);
2000                 return hasCurrent;
2001             }
2002
2003             public K Current {
2004                 get {
2005                     return current;
2006                 }
2007             }
2008
2009             Object System.Collections.IEnumerator.Current {
2010                 get {
2011                     return Current;
2012                 }
2013             }
2014
2015             void System.Collections.IEnumerator.Reset() {
2016                 if (version != tree._version) {
2017                     throw ExceptionBuilder.EnumeratorModified();
2018                 }
2019
2020                 index = NIL;
2021                 mainTreeNodeId = tree.root;
2022                 current = default(K);
2023             }
2024         }
2025     }
2026 }