development/Win32/vld/src/tree.h

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  Visual Leak Detector - Red-black Tree Template
   4 //  Copyright (c) 2005-2006 Dan Moulding
   5 //
   6 //  This library is free software; you can redistribute it and/or
   7 //  modify it under the terms of the GNU Lesser General Public
   8 //  License as published by the Free Software Foundation; either
   9 //  version 2.1 of the License, or (at your option) any later version.
  10 //
  11 //  This library is distributed in the hope that it will be useful,
  12 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 //  Lesser General Public License for more details.
  15 //
  16 //  You should have received a copy of the GNU Lesser General Public
  17 //  License along with this library; if not, write to the Free Software
  18 //  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19 //
  20 //  See COPYING.txt for the full terms of the GNU Lesser General Public License.
  21 //
  22 ////////////////////////////////////////////////////////////////////////////////
  23
  24 #pragma once
  25
  26 #ifndef VLDBUILD
  27 #error \
  28 "This header should only be included by Visual Leak Detector when building it from source. \
  29 Applications should never include this header."
  30 #endif
  31
  32 #include "vldheap.h" // Provides internal new and delete operators.
  33
  34 #define TREE_DEFAULT_RESERVE 32 // By default, trees reserve enough space, in advance, for this many nodes.
  35
  36 ////////////////////////////////////////////////////////////////////////////////
  37 //
  38 //  The Tree Template Class
  39 //
  40 //    This data structure is the internal data structure behind the lightweight
  41 //    STL-like container classes. This is a red-black tree which provides for
  42 //    fast insert, find, and erase operations.
  43 //
  44 //    The binary tree nodes are overlaid on top of larger chunks of allocated
  45 //    memory (called chunks) which are arranged in a simple linked list. This
  46 //    allows the tree to grow (add nodes) dynamically without incurring a heap
  47 //    hit each time a new node is added.
  48 //
  49 //    The Tree class provides member functions which make it easily adaptable to
  50 //    an STL-like interface so that it can be used as the backend for STL-like
  51 //    container classes.
  52 //
  53 template <typename T>
  54 class Tree
  55 {
  56 public:
  57     // This is a red-black tree.
  58     enum color_e {
  59         red,
  60         black
  61     };
  62
  63     // The node is the basic data structure which the tree is built from.
  64     typedef struct node_s {
  65         color_e            color;  // The node's color.
  66         T                  key;    // The node's value, by which nodes are sorted.
  67         union {
  68             struct node_s *left;   // For nodes in the tree, the node's left child.
  69             struct node_s *next;   // For nodes in the free list, the next node on the free list.
  70         };
  71         struct node_s     *parent; // The node's parent.
  72         struct node_s     *right;  // The node's right child.
  73     } node_t;
  74
  75     // Reserve capacity for the tree is allocated in large chunks with room for
  76     // many nodes.
  77     typedef struct chunk_s {
  78         struct chunk_s *next;  // Pointer to the next node in the chunk list.
  79         node_t         *nodes; // Pointer to an array (of variable size) where nodes are stored.
  80     } chunk_t;
  81
  82     // Constructor
  83     Tree ()
  84     {
  85         m_freelist   = NULL;
  86         InitializeCriticalSection(&m_lock);
  87         m_nil.color  = black;
  88         m_nil.key    = T();
  89         m_nil.left   = &m_nil;
  90         m_nil.parent = &m_nil;
  91         m_nil.right  = &m_nil;
  92         m_reserve    = TREE_DEFAULT_RESERVE;
  93         m_root       = &m_nil;
  94         m_store      = NULL;
  95         m_storetail  = NULL;
  96     }
  97
  98     // Copy constructor - The sole purpose of this constructor's existence is
  99     //   to ensure that trees are not being inadvertently copied.
 100     Tree (const Tree& source)
 101     {
 102         assert(FALSE); // Do not make copies of trees!
 103     }
 104
 105     // Destructor
 106     ~Tree ()
 107     {
 108         chunk_t *cur;
 109         chunk_t *temp;
 110
 111         // Free all the chunks in the chunk list.
 112         EnterCriticalSection(&m_lock);
 113         cur = m_store;
 114         while (cur != NULL) {
 115             temp = cur;
 116             cur = cur->next;
 117             delete [] temp->nodes;
 118             delete temp;
 119         }
 120         LeaveCriticalSection(&m_lock);
 121         DeleteCriticalSection(&m_lock);
 122     }
 123
 124     // operator = - Assignment operator. For efficiency, we want to avoid ever
 125     //   making copies of Trees (only pointer passing or reference passing
 126     //   should be performed). The sole purpose of this assignment operator is
 127     //   to ensure that no copying is being done inadvertently.
 128     //
 129     Tree<T>& operator = (const Tree<T> &other)
 130     {
 131         // Don't make copies of Trees!
 132         assert(FALSE);
 133         return *this;
 134     }
 135
 136     // begin - Obtains a pointer to the first node (the node with the smallest
 137     //   key value) in the tree.
 138     //
 139     //  Return Value:
 140     //
 141     //    Returns a pointer to the first node in the tree.
 142     //
 143     typename Tree::node_t* begin () const
 144     {
 145         node_t *cur;
 146
 147         EnterCriticalSection(&m_lock);
 148         if (m_root == &m_nil) {
 149             LeaveCriticalSection(&m_lock);
 150             return NULL;
 151         }
 152
 153         cur = m_root;
 154         while (cur->left != &m_nil) {
 155             cur = cur->left;
 156         }
 157         LeaveCriticalSection(&m_lock);
 158
 159         return cur;
 160     }
 161
 162     // erase - Erases the specified node from the tree. Note that this does
 163     //   not cause the key associated with the erased node to be freed. The
 164     //   caller is responsible for freeing any dynamically allocated memory
 165     //   associated with the key.
 166     //
 167     //  - node (IN): Pointer to the node to erase from the tree.
 168     //
 169     //  Return Value:
 170     //
 171     //    None.
 172     //
 173     VOID erase (typename Tree::node_t *node)
 174     {
 175         node_t *child;
 176         node_t *cur;
 177         node_t *erasure;
 178         node_t *sibling;
 179
 180         EnterCriticalSection(&m_lock);
 181
 182         if ((node->left == &m_nil) || (node->right == &m_nil)) {
 183             // The node to be erased has less than two children. It can be directly
 184             // removed from the tree.
 185             erasure = node;
 186         }
 187         else {
 188             // The node to be erased has two children. It can only be removed
 189             // indirectly. The actual node will stay where it is, but it's contents
 190             // will be replaced by it's in-order successor's contents. The successor
 191             // node will then be erased. Find the successor.
 192             erasure = node->right;
 193             while (erasure->left != &m_nil) {
 194                 erasure = erasure->left;
 195             }
 196         }
 197
 198         // Select the child node which will replace the node to be erased.
 199         if (erasure->left != &m_nil) {
 200             child = erasure->left;
 201         }
 202         else {
 203             child = erasure->right;
 204         }
 205
 206         // Replace the node to be erased with the selected child.
 207         child->parent = erasure->parent;
 208         if (child->parent == &m_nil) {
 209             // The root of the tree is being erased. The child becomes root.
 210             m_root = child;
 211         }
 212         else {
 213             if (erasure == erasure->parent->left) {
 214                 erasure->parent->left = child;
 215             }
 216             else {
 217                 erasure->parent->right = child;
 218             }
 219         }
 220
 221         if (erasure != node) {
 222             // The node being erased from the tree is the successor of the actual
 223             // node to be erased. Replace the contents of the node to be erased
 224             // with the successor's contents.
 225             node->key  = erasure->key;
 226         }
 227
 228         if (erasure->color == black) {
 229             // The node being erased from the tree is black. Restructuring of the
 230             // tree may be needed so that black-height is maintained.
 231             cur = child;
 232             while ((cur != m_root) && (cur->color == black)) {
 233                 if (cur == cur->parent->left) {
 234                     // Current node is a left child.
 235                     sibling = cur->parent->right;
 236                     if (sibling->color == red) {
 237                         // Sibling is red. Rotate sibling up and color it black.
 238                         sibling->color = black;
 239                         cur->parent->color = red;
 240                         _rotateleft(cur->parent);
 241                         sibling = cur->parent->right;
 242                     }
 243                     if ((sibling->left->color == black) && (sibling->right->color == black)) {
 244                         // Both of sibling's children are black. Color sibling red.
 245                         sibling->color = red;
 246                         cur = cur->parent;
 247                     }
 248                     else {
 249                         // At least one of sibling's children is red.
 250                         if (sibling->right->color == black) {
 251                             sibling->left->color = black;
 252                             sibling->color = red;
 253                             _rotateright(sibling);
 254                             sibling = cur->parent->right;
 255                         }
 256                         sibling->color = cur->parent->color;
 257                         cur->parent->color = black;
 258                         sibling->right->color = black;
 259                         _rotateleft(cur->parent);
 260                         cur = m_root;
 261                     }
 262                 }
 263                 else {
 264                     // Current node is a right child.
 265                     sibling = cur->parent->left;
 266                     if (sibling->color == red) {
 267                         // Sibling is red. Rotate sibling up and color it black.
 268                         sibling->color = black;
 269                         cur->parent->color = red;
 270                         _rotateright(cur->parent);
 271                         sibling = cur->parent->left;
 272                     }
 273                     if ((sibling->left->color == black) && (sibling->right->color == black)) {
 274                         // Both of sibling's children are black. Color sibling red.
 275                         sibling->color = red;
 276                         cur = cur->parent;
 277                     }
 278                     else {
 279                         // At least one of sibling's children is red.
 280                         if (sibling->left->color == black) {
 281                             sibling->right->color = black;
 282                             sibling->color = red;
 283                             _rotateleft(sibling);
 284                             sibling = cur->parent->left;
 285                         }
 286                         sibling->color = cur->parent->color;
 287                         cur->parent->color = black;
 288                         sibling->left->color = black;
 289                         _rotateright(cur->parent);
 290                         cur = m_root;
 291                     }
 292                 }
 293             }
 294             cur->color = black;
 295         }
 296
 297         // Put the erased node onto the free list.
 298         erasure->next = m_freelist;
 299         m_freelist = erasure;
 300
 301         LeaveCriticalSection(&m_lock);
 302     }
 303
 304     // erase - Erases the specified key from the tree. Note that this does
 305     //   not cause the key associated with the erased node to be freed. The
 306     //   caller is responsible for freeing any dynamically allocated memory
 307     //   associated with the key.
 308     //
 309     //  - key (IN): The key to erase from the tree. This value is treated as
 310     //      the key for sorting within the tree. It must therefore be of a type
 311     //      which supports the "<" operator.
 312     //
 313     //  Return Value:
 314     //
 315     //    None.
 316     //
 317     VOID erase (const T &key)
 318     {
 319         node_t *node;
 320
 321         // Find the node to erase.
 322         EnterCriticalSection(&m_lock);
 323         node = m_root;
 324         while (node != &m_nil) {
 325             if (node->key < key) {
 326                 // Go right.
 327                 node = node->right;
 328             }
 329             else if (key < node->key) {
 330                 // Go left.
 331                 node = node->left;
 332             }
 333             else {
 334                 // Found it.
 335                 erase(node);
 336                 LeaveCriticalSection(&m_lock);
 337                 return;
 338             }
 339         }
 340         LeaveCriticalSection(&m_lock);
 341
 342         // 'key' is not in the tree.
 343         return;
 344     }
 345
 346     // find - Obtains a pointer to the node corresponding to the specified key.
 347     //
 348     //  - key (IN): The value to search for in the tree. This value is treated
 349     //      as the key for sorting within the tree. It must therefore be of a
 350     //      type which supports the "<" operator.
 351     //
 352     //  Return Value:
 353     //
 354     //    Returns a pointer to the node corresponding to the specified key. If
 355     //    the key is not in the tree, then "find" returns NULL.
 356     //
 357     typename Tree::node_t* find (const T &key) const
 358     {
 359         node_t *cur;
 360
 361         EnterCriticalSection(&m_lock);
 362         cur = m_root;
 363         while (cur != &m_nil) {
 364             if (cur->key < key) {
 365                 // Go right.
 366                 cur = cur->right;
 367             }
 368             else if (key < cur->key) {
 369                 // Go left.
 370                 cur = cur->left;
 371             }
 372             else {
 373                 // Found it.
 374                 LeaveCriticalSection(&m_lock);
 375                 return cur;
 376             }
 377         }
 378         LeaveCriticalSection(&m_lock);
 379
 380         // 'key' is not in the tree.
 381         return NULL;
 382     }
 383
 384     // insert - Inserts a new key into the tree.
 385     //
 386     //  - key (IN): The key to insert into the tree. This value is treated as
 387     //      the key for sorting within the tree. It must therefore be of a type
 388     //      which supports the "<" operator.
 389     //
 390     //  Return Value:
 391     //
 392     //    Returns a pointer to the node corresponding to the newly inserted
 393     //    key. If an attempt is made to insert a key which is already in the
 394     //    tree, then NULL is returned and the new key is not inserted.
 395     //
 396     typename Tree::node_t* insert (const T &key)
 397     {
 398         node_t  *cur;
 399         node_t  *node;
 400         node_t  *parent;
 401         node_t  *uncle;
 402
 403         EnterCriticalSection(&m_lock);
 404
 405         // Find the location where the new node should be inserted..
 406         cur = m_root;
 407         parent = &m_nil;
 408         while (cur != &m_nil) {
 409             parent = cur;
 410             if (cur->key < key) {
 411                 // Go right.
 412                 cur = cur->right;
 413             }
 414             else if (key < cur->key) {
 415                 // Go left.
 416                 cur = cur->left;
 417             }
 418             else {
 419                 // Keys in the tree must be unique.
 420                 LeaveCriticalSection(&m_lock);
 421                 return NULL;
 422             }
 423         }
 424
 425         // Obtain a new node from the free list.
 426         if (m_freelist == NULL) {
 427             // Allocate additional storage.
 428             reserve(m_reserve);
 429         }
 430         node = m_freelist;
 431         m_freelist = m_freelist->next;
 432
 433         // Initialize the new node and insert it.
 434         node->color  = red;
 435         node->key    = key;
 436         node->left   = &m_nil;
 437         node->parent = parent;
 438         node->right  = &m_nil;
 439         if (parent == &m_nil) {
 440             // The tree is empty. The new node becomes root.
 441             m_root = node;
 442         }
 443         else {
 444             if (parent->key < key) {
 445                 // New node is a right child.
 446                 parent->right = node;
 447             }
 448             else {
 449                 // New node is a left child.
 450                 parent->left = node;
 451             }
 452         }
 453
 454         // Rebalance and/or adjust the tree, if necessary.
 455         cur = node;
 456         while (cur->parent->color == red) {
 457             // Double-red violation. Rebalancing/adjustment needed.
 458             if (cur->parent == cur->parent->parent->left) {
 459                 // Parent is the left child. Uncle is the right child.
 460                 uncle = cur->parent->parent->right;
 461                 if (uncle->color == red) {
 462                     // Uncle is red. Recolor.
 463                     cur->parent->parent->color = red;
 464                     cur->parent->color = black;
 465                     uncle->color = black;
 466                     cur = cur->parent->parent;
 467                 }
 468                 else {
 469                     // Uncle is black. Restructure.
 470                     if (cur == cur->parent->right) {
 471                         cur = cur->parent;
 472                         _rotateleft(cur);
 473                     }
 474                     cur->parent->color = black;
 475                     cur->parent->parent->color = red;
 476                     _rotateright(cur->parent->parent);
 477                 }
 478             }
 479             else {
 480                 // Parent is the right child. Uncle is the left child.
 481                 uncle = cur->parent->parent->left;
 482                 if (uncle->color == red) {
 483                     // Uncle is red. Recolor.
 484                     cur->parent->parent->color = red;
 485                     cur->parent->color = black;
 486                     uncle->color = black;
 487                     cur = cur->parent->parent;
 488                 }
 489                 else {
 490                     // Uncle is black. Restructure.
 491                     if (cur == cur->parent->left) {
 492                         cur = cur->parent;
 493                         _rotateright(cur);
 494                     }
 495                     cur->parent->color = black;
 496                     cur->parent->parent->color = red;
 497                     _rotateleft(cur->parent->parent);
 498                 }
 499             }
 500         }
 501
 502         // The root node is always colored black.
 503         m_root->color = black;
 504
 505         LeaveCriticalSection(&m_lock);
 506
 507         return node;
 508     }
 509
 510     // next - Obtains a pointer to the in-order successor of the specified
 511     //   node.
 512     //
 513     //  - node (IN): Pointer to the node whose in-order successor to retrieve.
 514     //
 515     //  Return Value:
 516     //
 517     //    Returns a pointer to the node's in-order successor. If the specified
 518     //    node corresponds to the largest value in the tree, then the specified
 519     //    node has no successor and "next" will return NULL.
 520     //
 521     typename Tree::node_t* next (typename Tree::node_t *node) const
 522     {
 523         node_t* cur;
 524
 525         if (node == NULL) {
 526             return NULL;
 527         }
 528
 529         EnterCriticalSection(&m_lock);
 530         if (node->right != &m_nil) {
 531             // 'node' has a right child. Successor is the far left node in
 532             // the right subtree.
 533             cur = node->right;
 534             while (cur->left != &m_nil) {
 535                 cur = cur->left;
 536             }
 537             LeaveCriticalSection(&m_lock);
 538             return cur;
 539         }
 540         else if (node->parent != &m_nil) {
 541             // 'node' has no right child, but does have a parent.
 542             if (node == node->parent->left) {
 543                 // 'node' is a left child; node's parent is successor.
 544                 LeaveCriticalSection(&m_lock);
 545                 return node->parent;
 546             }
 547             else {
 548                 // 'node' is a right child.
 549                 cur = node;
 550                 // Go up the tree until we find a parent to the right.
 551                 while (cur->parent != &m_nil) {
 552                     if (cur == cur->parent->right) {
 553                         cur = cur->parent;
 554                         continue;
 555                     }
 556                     else {
 557                         LeaveCriticalSection(&m_lock);
 558                         return cur->parent;
 559                     }
 560                 }
 561
 562                 // There is no parent greater than 'node'. 'node' is the
 563                 // maximum node.
 564                 LeaveCriticalSection(&m_lock);
 565                 return NULL;
 566             }
 567         }
 568         else {
 569             // 'node' is root and root is the maximum node.
 570             LeaveCriticalSection(&m_lock);
 571             return NULL;
 572         }
 573     }
 574
 575     // prev - Obtains a pointer to the in-order predecessor of the specified
 576     //   node.
 577     //
 578     //  - node (IN): Pointer to the node whose in-order predecessor to retrieve.
 579     //
 580     //  Return Value:
 581     //
 582     //    Returns a pointer to the node's in-order predecessor. If the specified
 583     //    node corresponds to the smallest value in the tree, then the specified
 584     //    node has no predecessor and "prev" will return NULL.
 585     //
 586     typename Tree::node_t* prev (typename Tree::node_t *node) const
 587     {
 588         node_t* cur;
 589
 590         if (node == NULL) {
 591             return NULL;
 592         }
 593
 594         EnterCriticalSection(&m_lock);
 595         if (node->left != &m_nil) {
 596             // 'node' has left child. Predecessor is the far right node in the
 597             // left subtree.
 598             cur = node->left;
 599             while (cur->right != &m_nil) {
 600                 cur = cur->right;
 601             }
 602             LeaveCriticalSection(&m_lock);
 603             return cur;
 604         }
 605         else if (node->parent != & m_nil) {
 606             // 'node' has no left child, but does have a parent.
 607             if (node == node->parent->right) {
 608                 // 'node' is a right child; node's parent is predecessor.
 609                 LeaveCriticalSection(&m_lock);
 610                 return node->parent;
 611             }
 612             else {
 613                 // 'node is a left child.
 614                 cur = node;
 615                 // Go up the tree until we find a parent to the left.
 616                 while (cur->parent != &m_nil) {
 617                     if (cur == cur->parent->left) {
 618                         cur = cur->parent;
 619                         continue;
 620                     }
 621                     else {
 622                         LeaveCriticalSection(&m_lock);
 623                         return cur->parent;
 624                     }
 625                 }
 626
 627                 // There is no parent less than 'node'. 'node' is the minimum
 628                 // node.
 629                 LeaveCriticalSection(&m_lock);
 630                 return NULL;
 631             }
 632         }
 633         else {
 634             // 'node' is root and root is the minimum node.
 635             LeaveCriticalSection(&m_lock);
 636             return NULL;
 637         }
 638     }
 639
 640     // reserve - Reserves storage for a number of nodes in advance and/or sets
 641     //   the number of nodes for which the tree will automatically reserve
 642     //   storage when the tree needs to "grow" to accomodate new values being
 643     //   inserted into the tree. If this function is not called to set the
 644     //   reserve size to a specific value, then a pre-determined default value
 645     //   will be used. If this function is called when the tree currently has
 646     //   no reserve storage, then in addition to setting the tree's reserve
 647     //   value, it will also cause the tree to immediately reserve the
 648     //   specified amount of storage.
 649     //
 650     //  - count (IN): The number of individual nodes' worth of storage to
 651     //      reserve.
 652     //
 653     //  Return Value:
 654     //
 655     //    Returns the previously defined reserve value.
 656     //
 657     UINT32 reserve (UINT32 count)
 658     {
 659         chunk_t *chunk;
 660         UINT32   index;
 661         UINT32   oldreserve = m_reserve;
 662
 663         if (count != m_reserve) {
 664             if (count < 1) {
 665                 // Minimum reserve size is 1.
 666                 m_reserve = 1;
 667             }
 668             else {
 669                 m_reserve = count;
 670             }
 671         }
 672
 673         EnterCriticalSection(&m_lock);
 674         if (m_freelist == NULL) {
 675             // Allocate additional storage.
 676             // Link a new chunk into the chunk list.
 677             chunk = new Tree::chunk_t;
 678             chunk->nodes = new Tree::node_s [m_reserve];
 679             chunk->next = NULL;
 680             if (m_store == NULL) {
 681                 m_store = chunk;
 682             }
 683             else {
 684                 m_storetail->next = chunk;
 685             }
 686             m_storetail = chunk;
 687
 688             // Link the individual nodes together to form a new free list.
 689             for (index = 0; index < m_reserve - 1; index++) {
 690                 chunk->nodes[index].next = &chunk->nodes[index + 1];
 691             }
 692             chunk->nodes[index].next = NULL;
 693             m_freelist = chunk->nodes;
 694         }
 695         LeaveCriticalSection(&m_lock);
 696
 697         return oldreserve;
 698     }
 699
 700 private:
 701     // _rotateleft: Rotates a pair of nodes counter-clockwise so that the parent
 702     //   node becomes the left child and the right child becomes the parent.
 703     //
 704     //  - parent (IN): Pointer to the parent to rotate about.
 705     //
 706     //  Return Value:
 707     //
 708     //    None.
 709     //
 710     VOID _rotateleft (typename Tree::node_t *parent)
 711     {
 712         node_t *child = parent->right;
 713
 714         // Reassign the child's left subtree to the parent.
 715         parent->right = child->left;
 716         if (child->left != &m_nil) {
 717             child->left->parent = parent;
 718         }
 719
 720         // Reassign the child/parent relationship.
 721         child->parent = parent->parent;
 722         if (parent->parent == &m_nil) {
 723             // The child becomes the new root node.
 724             m_root = child;
 725         }
 726         else {
 727             // Point the grandparent at the child.
 728             if (parent == parent->parent->left) {
 729                 parent->parent->left = child;
 730             }
 731             else {
 732                 parent->parent->right = child;
 733             }
 734         }
 735         child->left = parent;
 736         parent->parent = child;
 737     }
 738
 739     // _rotateright - Rotates a pair of nodes clockwise so that the parent node
 740     //   becomes the right child and the left child becomes the parent.
 741     //
 742     //  - parent (IN): Pointer to the parent to rotate about.
 743     //
 744     //  Return Value:
 745     //
 746     //    None.
 747     //
 748     VOID _rotateright (typename Tree::node_t *parent)
 749     {
 750         node_t *child = parent->left;
 751
 752         // Reassign the child's right subtree to the parent.
 753         parent->left = child->right;
 754         if (child->right != &m_nil) {
 755             child->right->parent = parent;
 756         }
 757
 758         // Reassign the child/parent relationship.
 759         child->parent = parent->parent;
 760         if (parent->parent == &m_nil) {
 761             // The child becomes the new root node.
 762             m_root = child;
 763         }
 764         else {
 765             // Point the grandparent at the child.
 766             if (parent == parent->parent->left) {
 767                 parent->parent->left = child;
 768             }
 769             else {
 770                 parent->parent->right = child;
 771             }
 772         }
 773         child->right = parent;
 774         parent->parent = child;
 775     }
 776
 777     // Private data members.
 778     node_t                   *m_freelist;  // Pointer to the list of free nodes (reserve storage).
 779     mutable CRITICAL_SECTION  m_lock;      // Protects the tree's integrity against concurrent accesses.
 780     node_t                    m_nil;       // The tree's nil node. All leaf nodes point to this.
 781     UINT32                    m_reserve;   // The size (in nodes) of the chunks of reserve storage.
 782     node_t                   *m_root;      // Pointer to the tree's root node.
 783     chunk_t                  *m_store;     // Pointer to the start of the chunk list.
 784     chunk_t                  *m_storetail; // Pointer to the end of the chunk list.
 785 };