1 ////////////////////////////////////////////////////////////////////////////////
3 // Visual Leak Detector - Red-black Tree Template
4 // Copyright (c) 2005-2006 Dan Moulding
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.
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.
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
20 // See COPYING.txt for the full terms of the GNU Lesser General Public License.
22 ////////////////////////////////////////////////////////////////////////////////
28 "This header should only be included by Visual Leak Detector when building it from source. \
29 Applications should never include this header."
32 #include "vldheap.h" // Provides internal new and delete operators.
34 #define TREE_DEFAULT_RESERVE 32 // By default, trees reserve enough space, in advance, for this many nodes.
36 ////////////////////////////////////////////////////////////////////////////////
38 // The Tree Template Class
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.
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.
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
57 // This is a red-black tree.
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.
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.
71 struct node_s *parent; // The node's parent.
72 struct node_s *right; // The node's right child.
75 // Reserve capacity for the tree is allocated in large chunks with room for
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.
86 InitializeCriticalSection(&m_lock);
90 m_nil.parent = &m_nil;
92 m_reserve = TREE_DEFAULT_RESERVE;
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)
102 assert(FALSE); // Do not make copies of trees!
111 // Free all the chunks in the chunk list.
112 EnterCriticalSection(&m_lock);
114 while (cur != NULL) {
117 delete [] temp->nodes;
120 LeaveCriticalSection(&m_lock);
121 DeleteCriticalSection(&m_lock);
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.
129 Tree<T>& operator = (const Tree<T> &other)
131 // Don't make copies of Trees!
136 // begin - Obtains a pointer to the first node (the node with the smallest
137 // key value) in the tree.
141 // Returns a pointer to the first node in the tree.
143 typename Tree::node_t* begin () const
147 EnterCriticalSection(&m_lock);
148 if (m_root == &m_nil) {
149 LeaveCriticalSection(&m_lock);
154 while (cur->left != &m_nil) {
157 LeaveCriticalSection(&m_lock);
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.
167 // - node (IN): Pointer to the node to erase from the tree.
173 VOID erase (typename Tree::node_t *node)
180 EnterCriticalSection(&m_lock);
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.
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;
198 // Select the child node which will replace the node to be erased.
199 if (erasure->left != &m_nil) {
200 child = erasure->left;
203 child = erasure->right;
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.
213 if (erasure == erasure->parent->left) {
214 erasure->parent->left = child;
217 erasure->parent->right = child;
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;
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.
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;
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;
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;
256 sibling->color = cur->parent->color;
257 cur->parent->color = black;
258 sibling->right->color = black;
259 _rotateleft(cur->parent);
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;
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;
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;
286 sibling->color = cur->parent->color;
287 cur->parent->color = black;
288 sibling->left->color = black;
289 _rotateright(cur->parent);
297 // Put the erased node onto the free list.
298 erasure->next = m_freelist;
299 m_freelist = erasure;
301 LeaveCriticalSection(&m_lock);
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.
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.
317 VOID erase (const T &key)
321 // Find the node to erase.
322 EnterCriticalSection(&m_lock);
324 while (node != &m_nil) {
325 if (node->key < key) {
329 else if (key < node->key) {
336 LeaveCriticalSection(&m_lock);
340 LeaveCriticalSection(&m_lock);
342 // 'key' is not in the tree.
346 // find - Obtains a pointer to the node corresponding to the specified key.
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.
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.
357 typename Tree::node_t* find (const T &key) const
361 EnterCriticalSection(&m_lock);
363 while (cur != &m_nil) {
364 if (cur->key < key) {
368 else if (key < cur->key) {
374 LeaveCriticalSection(&m_lock);
378 LeaveCriticalSection(&m_lock);
380 // 'key' is not in the tree.
384 // insert - Inserts a new key into the tree.
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.
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.
396 typename Tree::node_t* insert (const T &key)
403 EnterCriticalSection(&m_lock);
405 // Find the location where the new node should be inserted..
408 while (cur != &m_nil) {
410 if (cur->key < key) {
414 else if (key < cur->key) {
419 // Keys in the tree must be unique.
420 LeaveCriticalSection(&m_lock);
425 // Obtain a new node from the free list.
426 if (m_freelist == NULL) {
427 // Allocate additional storage.
431 m_freelist = m_freelist->next;
433 // Initialize the new node and insert it.
437 node->parent = parent;
438 node->right = &m_nil;
439 if (parent == &m_nil) {
440 // The tree is empty. The new node becomes root.
444 if (parent->key < key) {
445 // New node is a right child.
446 parent->right = node;
449 // New node is a left child.
454 // Rebalance and/or adjust the tree, if necessary.
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;
469 // Uncle is black. Restructure.
470 if (cur == cur->parent->right) {
474 cur->parent->color = black;
475 cur->parent->parent->color = red;
476 _rotateright(cur->parent->parent);
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;
490 // Uncle is black. Restructure.
491 if (cur == cur->parent->left) {
495 cur->parent->color = black;
496 cur->parent->parent->color = red;
497 _rotateleft(cur->parent->parent);
502 // The root node is always colored black.
503 m_root->color = black;
505 LeaveCriticalSection(&m_lock);
510 // next - Obtains a pointer to the in-order successor of the specified
513 // - node (IN): Pointer to the node whose in-order successor to retrieve.
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.
521 typename Tree::node_t* next (typename Tree::node_t *node) const
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.
534 while (cur->left != &m_nil) {
537 LeaveCriticalSection(&m_lock);
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);
548 // 'node' is a right child.
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) {
557 LeaveCriticalSection(&m_lock);
562 // There is no parent greater than 'node'. 'node' is the
564 LeaveCriticalSection(&m_lock);
569 // 'node' is root and root is the maximum node.
570 LeaveCriticalSection(&m_lock);
575 // prev - Obtains a pointer to the in-order predecessor of the specified
578 // - node (IN): Pointer to the node whose in-order predecessor to retrieve.
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.
586 typename Tree::node_t* prev (typename Tree::node_t *node) const
594 EnterCriticalSection(&m_lock);
595 if (node->left != &m_nil) {
596 // 'node' has left child. Predecessor is the far right node in the
599 while (cur->right != &m_nil) {
602 LeaveCriticalSection(&m_lock);
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);
613 // 'node is a left child.
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) {
622 LeaveCriticalSection(&m_lock);
627 // There is no parent less than 'node'. 'node' is the minimum
629 LeaveCriticalSection(&m_lock);
634 // 'node' is root and root is the minimum node.
635 LeaveCriticalSection(&m_lock);
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.
650 // - count (IN): The number of individual nodes' worth of storage to
655 // Returns the previously defined reserve value.
657 UINT32 reserve (UINT32 count)
661 UINT32 oldreserve = m_reserve;
663 if (count != m_reserve) {
665 // Minimum reserve size is 1.
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];
680 if (m_store == NULL) {
684 m_storetail->next = chunk;
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];
692 chunk->nodes[index].next = NULL;
693 m_freelist = chunk->nodes;
695 LeaveCriticalSection(&m_lock);
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.
704 // - parent (IN): Pointer to the parent to rotate about.
710 VOID _rotateleft (typename Tree::node_t *parent)
712 node_t *child = parent->right;
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;
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.
727 // Point the grandparent at the child.
728 if (parent == parent->parent->left) {
729 parent->parent->left = child;
732 parent->parent->right = child;
735 child->left = parent;
736 parent->parent = child;
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.
742 // - parent (IN): Pointer to the parent to rotate about.
748 VOID _rotateright (typename Tree::node_t *parent)
750 node_t *child = parent->left;
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;
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.
765 // Point the grandparent at the child.
766 if (parent == parent->parent->left) {
767 parent->parent->left = child;
770 parent->parent->right = child;
773 child->right = parent;
774 parent->parent = child;
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.