development/Win32/vld/src/tree.h

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