1 #ifndef ACE_RB_TREE_CPP
2 #define ACE_RB_TREE_CPP
4 #include "ace/Global_Macros.h"
5 #include "ace/RB_Tree.h"
6 #include "ace/SString.h"
8 #if !defined (ACE_LACKS_PRAGMA_ONCE)
10 #endif /* ACE_LACKS_PRAGMA_ONCE */
12 #if !defined (__ACE_INLINE__)
13 #include "ace/RB_Tree.inl"
14 #endif /* __ACE_INLINE__ */
16 #include "ace/Log_Category.h"
18 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
20 ACE_ALLOC_HOOK_DEFINE_Tc4(ACE_RB_Tree
)
21 ACE_ALLOC_HOOK_DEFINE_Tc4(ACE_RB_Tree_Iterator_Base
)
22 ACE_ALLOC_HOOK_DEFINE_Tc4(ACE_RB_Tree_Iterator
)
23 ACE_ALLOC_HOOK_DEFINE_Tc4(ACE_RB_Tree_Reverse_Iterator
)
26 template <class EXT_ID
, class INT_ID
>
27 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>::ACE_RB_Tree_Node (const EXT_ID
&k
, const INT_ID
&t
)
35 ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)");
41 template <class EXT_ID
, class INT_ID
>
42 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>::~ACE_RB_Tree_Node ()
44 ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node");
49 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
50 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree (ACE_Allocator
*alloc
)
54 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (ACE_Allocator *alloc)");
56 if (this->open (alloc
) == -1)
57 ACELIB_ERROR ((LM_ERROR
,
58 ACE_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n")));
63 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
64 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &rbt
)
68 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)");
69 ACE_WRITE_GUARD (ACE_LOCK
, ace_mon
, this->lock_
);
70 allocator_
= rbt
.allocator_
;
72 // Make a deep copy of the passed tree.
73 ACE_RB_Tree_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> iter(rbt
);
77 iter
.is_done () == 0; iter
.next ())
78 insert_i (*(iter
.key ()),
82 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
83 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree (
88 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (void *, ACE_Allocator *)");
93 this->current_size_
= 0;
96 this->allocator_
= alloc
;
100 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
101 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::~ACE_RB_Tree ()
103 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree");
105 // Use the locked public method, to be totally safe, as the class
106 // can be used with an allocator and placement new.
110 // Assignment operator.
112 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
113 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::operator = (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &rbt
)
115 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator =");
116 ACE_WRITE_GUARD (ACE_LOCK
, ace_mon
, this->lock_
);
120 // Clear out the existing tree.
123 // Make a deep copy of the passed tree.
124 ACE_RB_Tree_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> iter(rbt
);
127 iter
.is_done () == 0;
129 insert_i (*(iter
.key ()),
132 // Use the same allocator as the rhs.
133 allocator_
= rbt
.allocator_
;
136 // Less than comparison function for keys, default functor
137 // implementation returns 1 if k1 < k2, 0 otherwise.
139 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
140 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::lessthan (const EXT_ID
&k1
, const EXT_ID
&k2
)
142 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan");
143 return this->compare_keys_ (k1
, k2
);
146 // Method for right rotation of the tree about a given node.
148 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
149 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_rotate_right (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
)
151 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right");
154 ACELIB_ERROR ((LM_ERROR
,
156 ACE_TEXT ("\nerror: x is a null pointer in ")
157 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
158 else if (! (x
->left()))
159 ACELIB_ERROR ((LM_ERROR
,
161 ACE_TEXT ("\nerror: x->left () is a null pointer in ")
162 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
165 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> * y
;
167 x
->left (y
->right ());
169 y
->right ()->parent (x
);
170 y
->parent (x
->parent ());
173 if (x
== x
->parent ()->right ())
174 x
->parent ()->right (y
);
176 x
->parent ()->left (y
);
185 // Method for left rotation of the tree about a given node.
187 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
188 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_rotate_left (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> * x
)
190 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left");
193 ACELIB_ERROR ((LM_ERROR
,
195 ACE_TEXT ("\nerror: x is a null pointer in ")
196 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
197 else if (! (x
->right()))
198 ACELIB_ERROR ((LM_ERROR
,
200 ACE_TEXT ("\nerror: x->right () is a null pointer ")
201 ACE_TEXT ("in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
204 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> * y
;
206 x
->right (y
->left ());
208 y
->left ()->parent (x
);
209 y
->parent (x
->parent ());
212 if (x
== x
->parent ()->left ())
213 x
->parent ()->left (y
);
215 x
->parent ()->right (y
);
224 // Method for restoring Red-Black properties after a specific deletion case.
226 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
227 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::
228 RB_delete_fixup (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
,
229 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *parent
)
231 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup");
233 while (x
!= this->root_
235 || x
->color () == ACE_RB_Tree_Node_Base::BLACK
))
237 if (x
== parent
->left ())
239 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *w
= parent
->right ();
240 if (w
&& w
->color () == ACE_RB_Tree_Node_Base::RED
)
242 w
->color (ACE_RB_Tree_Node_Base::BLACK
);
243 parent
->color (ACE_RB_Tree_Node_Base::RED
);
244 RB_rotate_left (parent
);
245 w
= parent
->right ();
247 // CLR pp. 263 says that nil nodes are implicitly colored BLACK
250 || w
->left ()->color () == ACE_RB_Tree_Node_Base::BLACK
)
252 || w
->right ()->color () == ACE_RB_Tree_Node_Base::BLACK
))
254 w
->color (ACE_RB_Tree_Node_Base::RED
);
256 parent
= x
->parent ();
260 // CLR pp. 263 says that nil nodes are implicitly colored BLACK
263 || w
->right ()->color () == ACE_RB_Tree_Node_Base::BLACK
))
266 w
->left ()->color (ACE_RB_Tree_Node_Base::BLACK
);
267 w
->color (ACE_RB_Tree_Node_Base::RED
);
269 w
= parent
->right ();
273 w
->color (parent
->color ());
275 w
->right ()->color (ACE_RB_Tree_Node_Base::BLACK
);
277 parent
->color (ACE_RB_Tree_Node_Base::BLACK
);
278 RB_rotate_left (parent
);
284 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *w
= parent
->left ();
285 if (w
&& w
->color () == ACE_RB_Tree_Node_Base::RED
)
287 w
->color (ACE_RB_Tree_Node_Base::BLACK
);
288 parent
->color (ACE_RB_Tree_Node_Base::RED
);
289 RB_rotate_right (parent
);
292 // CLR pp. 263 says that nil nodes are implicitly colored BLACK
295 || w
->left ()->color () == ACE_RB_Tree_Node_Base::BLACK
)
297 || w
->right ()->color () == ACE_RB_Tree_Node_Base::BLACK
))
299 w
->color (ACE_RB_Tree_Node_Base::RED
);
301 parent
= x
->parent ();
305 // CLR pp. 263 says that nil nodes are implicitly colored BLACK
308 || w
->left ()->color () == ACE_RB_Tree_Node_Base::BLACK
))
310 w
->color (ACE_RB_Tree_Node_Base::RED
);
312 w
->right ()->color (ACE_RB_Tree_Node_Base::BLACK
);
318 w
->color (parent
->color ());
320 w
->left ()->color (ACE_RB_Tree_Node_Base::BLACK
);
322 parent
->color (ACE_RB_Tree_Node_Base::BLACK
);
323 RB_rotate_right (parent
);
330 x
->color (ACE_RB_Tree_Node_Base::BLACK
);
333 // Return a pointer to a matching node if there is one, a pointer to
334 // the node under which to insert the item if the tree is not empty
335 // and there is no such match, or 0 if the tree is empty.
337 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *
338 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::find_node (const EXT_ID
&k
, ACE_RB_Tree_Base::RB_SearchResult
&result
)
340 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node");
342 // Start at the root.
343 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *current
= root_
;
347 // While there are more nodes to examine.
348 if (this->lessthan (current
->key (), k
))
350 // If the search key is greater than the current node's key.
351 if (current
->right ())
352 // If the right subtree is not empty, search to the right.
353 current
= current
->right ();
356 // If the right subtree is empty, we're done searching,
357 // and are positioned to the left of the insertion point.
362 else if (this->lessthan (k
, current
->key ()))
364 // Else if the search key is less than the current node's key.
365 if (current
->left ())
366 // If the left subtree is not empty, search to the left.
367 current
= current
->left ();
370 // If the left subtree is empty, we're done searching,
371 // and are positioned to the right of the insertion point.
378 // If the keys match exactly, we're done as well.
387 // Rebalance the tree after insertion of a node.
389 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
390 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_rebalance (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> * x
)
392 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance");
394 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *y
= 0;
398 && x
->parent ()->color () == ACE_RB_Tree_Node_Base::RED
)
400 if (! x
->parent ()->parent ())
402 // If we got here, something is drastically wrong!
403 ACELIB_ERROR ((LM_ERROR
,
405 ACE_TEXT ("\nerror: parent's parent is null in ")
406 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n")));
410 if (x
->parent () == x
->parent ()->parent ()->left ())
412 y
= x
->parent ()->parent ()->right ();
413 if (y
&& y
->color () == ACE_RB_Tree_Node_Base::RED
)
415 // Handle case 1 (see CLR book, pp. 269).
416 x
->parent ()->color (ACE_RB_Tree_Node_Base::BLACK
);
417 y
->color (ACE_RB_Tree_Node_Base::BLACK
);
418 x
->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED
);
419 x
= x
->parent ()->parent ();
423 if (x
== x
->parent ()->right ())
425 // Transform case 2 into case 3 (see CLR book, pp. 269).
430 // Handle case 3 (see CLR book, pp. 269).
431 x
->parent ()->color (ACE_RB_Tree_Node_Base::BLACK
);
432 x
->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED
);
433 RB_rotate_right (x
->parent ()->parent ());
438 y
= x
->parent ()->parent ()->left ();
439 if (y
&& y
->color () == ACE_RB_Tree_Node_Base::RED
)
441 // Handle case 1 (see CLR book, pp. 269).
442 x
->parent ()->color (ACE_RB_Tree_Node_Base::BLACK
);
443 y
->color (ACE_RB_Tree_Node_Base::BLACK
);
444 x
->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED
);
445 x
= x
->parent ()->parent ();
449 if (x
== x
->parent ()->left ())
451 // Transform case 2 into case 3 (see CLR book, pp. 269).
456 // Handle case 3 (see CLR book, pp. 269).
457 x
->parent ()->color (ACE_RB_Tree_Node_Base::BLACK
);
458 x
->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED
);
459 RB_rotate_left (x
->parent ()->parent ());
465 // Method to find the successor node of the given node in the tree.
467 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *
468 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_tree_successor (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
) const
470 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor");
476 return RB_tree_minimum (x
->right ());
478 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *y
= x
->parent ();
479 while ((y
) && (x
== y
->right ()))
488 // Method to find the predecessor node of the given node in the tree.
490 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *
491 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_tree_predecessor (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
) const
493 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor");
498 return RB_tree_maximum (x
->left ());
500 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *y
= x
->parent ();
502 while ((y
) && (x
== y
->left ()))
511 // Method to find the minimum node of the subtree rooted at the given node.
513 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *
514 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_tree_minimum (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
) const
516 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum");
518 while ((x
) && (x
->left ()))
524 // Method to find the maximum node of the subtree rooted at the given node.
526 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *
527 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::RB_tree_maximum (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
) const
529 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum");
531 while ((x
) && (x
->right ()))
537 // Delete children (left and right) of the node. Must be called with
539 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
540 void ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::delete_children_i
541 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *parent
)
545 this->delete_children_i (parent
->left ());
546 this->delete_children_i (parent
->right ());
547 ACE_DES_FREE_TEMPLATE2
549 this->allocator_
->free
,
552 ACE_DES_FREE_TEMPLATE2
554 this->allocator_
->free
,
563 // Close down an RB_Tree. this method should only be called with
564 // locks already held.
566 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
567 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::close_i ()
569 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i");
571 this->delete_children_i (this->root_
);
572 ACE_DES_FREE_TEMPLATE2 (this->root_
,
573 this->allocator()->free
,
576 this->current_size_
= 0;
581 // Returns a pointer to the item corresponding to the given key, or 0
582 // if it cannot find the key in the tree. This method should only be
583 // called with locks already held.
585 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
586 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::find_i (const EXT_ID
&k
,
587 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>* &entry
, int find_exact
)
589 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i");
591 // Try to find a match.
592 RB_SearchResult result
= LEFT
;
593 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *current
= find_node (k
, result
);
598 if (!find_exact
|| result
== EXACT
)
599 entry
= current
; // Assign the entry for any match.
600 return (result
== EXACT
? 0 : -1);
603 // The node is not there.
607 // Inserts a *copy* of the key and the item into the tree: both the
608 // key type EXT_ID and the item type INT_ID must have well defined
609 // semantics for copy construction and < comparison. This method
610 // returns a pointer to the inserted item copy, or 0 if an error
611 // occurred. NOTE: if an identical key already exists in the tree, no
612 // new item is created, and the returned pointer addresses the
613 // existing item associated with the existing key. This method should
614 // only be called with locks already held.
616 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> INT_ID
*
617 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::insert_i (const EXT_ID
&k
, const INT_ID
&t
)
619 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)");
621 // Find the closest matching node, if there is one.
622 RB_SearchResult result
= LEFT
;
623 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *current
= find_node (k
, result
);
626 // If the keys match, just return a pointer to the node's item.
628 return ¤t
->item ();
630 // Otherwise if we're to the left of the insertion point, insert
631 // into the right subtree.
632 else if (result
== LEFT
)
634 if (current
->right ())
636 // If there is already a right subtree, complain.
637 ACELIB_ERROR_RETURN ((LM_ERROR
,
639 ACE_TEXT ("\nright subtree already present in ")
640 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
645 // The right subtree is empty: insert new node there.
646 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *tmp
= 0;
648 ACE_NEW_MALLOC_RETURN
650 (reinterpret_cast<ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>*>
651 (this->allocator_
->malloc (sizeof (*tmp
)))),
652 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>) (k
, t
),
654 current
->right (tmp
);
656 // If the node was successfully inserted, set its
657 // parent, rebalance the tree, color the root black, and
658 // return a pointer to the inserted item.
659 INT_ID
*item
= &(current
->right ()->item ());
660 current
->right ()->parent (current
);
661 RB_rebalance (current
->right ());
662 root_
->color (ACE_RB_Tree_Node_Base::BLACK
);
667 // Otherwise, we're to the right of the insertion point, so
668 // insert into the left subtree.
669 else // (result == RIGHT)
671 if (current
->left ())
672 // If there is already a left subtree, complain.
673 ACELIB_ERROR_RETURN ((LM_ERROR
,
675 ACE_TEXT ("\nleft subtree already present in ")
676 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
680 // The left subtree is empty: insert new node there.
681 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *tmp
= 0;
682 ACE_NEW_MALLOC_RETURN
684 (reinterpret_cast<ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>*>
685 (this->allocator_
->malloc (sizeof (*tmp
)))),
686 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>) (k
, t
),
690 // If the node was successfully inserted, set its
691 // parent, rebalance the tree, color the root black, and
692 // return a pointer to the inserted item.
693 INT_ID
*item
= ¤t
->left ()->item ();
694 current
->left ()->parent (current
);
695 RB_rebalance (current
->left ());
696 root_
->color (ACE_RB_Tree_Node_Base::BLACK
);
704 // The tree is empty: insert at the root and color the root
706 ACE_NEW_MALLOC_RETURN
708 (reinterpret_cast<ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>*>
709 (this->allocator_
->malloc (sizeof (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>)))),
710 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>) (k
, t
),
712 this->root_
->color (ACE_RB_Tree_Node_Base::BLACK
);
714 return &this->root_
->item ();
718 // Inserts a *copy* of the key and the item into the tree: both the
719 // key type EXT_ID and the item type INT_ID must have well defined
720 // semantics for copy construction. The default implementation also
721 // requires that the key type support well defined < semantics. This
722 // method passes back a pointer to the inserted (or existing) node,
723 // and the search status. If the node already exists, the method
724 // returns 1. If the node does not exist, and a new one is
725 // successfully created, and the method returns 0. If there was an
726 // error, the method returns -1.
728 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
729 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::insert_i (const EXT_ID
&k
,
731 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *&entry
)
733 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i");
735 // Find the closest matching node, if there is one.
736 RB_SearchResult result
= LEFT
;
737 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *current
= find_node (k
, result
);
740 // If the keys match, just return a pointer to the node's item.
746 // Otherwise if we're to the left of the insertion
747 // point, insert into the right subtree.
748 else if (result
== LEFT
)
750 if (current
->right ())
752 // If there is already a right subtree, complain.
753 ACELIB_ERROR_RETURN ((LM_ERROR
,
755 ACE_TEXT ("\nright subtree already present in ")
756 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
761 // The right subtree is empty: insert new node there.
762 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *tmp
= 0;
763 ACE_NEW_MALLOC_RETURN
765 (reinterpret_cast<ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>*>
766 (this->allocator_
->malloc (sizeof (*tmp
)))),
767 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>) (k
, t
),
769 current
->right (tmp
);
771 // If the node was successfully inserted, set its parent, rebalance
772 // the tree, color the root black, and return a pointer to the
774 entry
= current
->right ();
775 current
->right ()->parent (current
);
776 RB_rebalance (current
->right ());
777 this->root_
->color (ACE_RB_Tree_Node_Base::BLACK
);
778 ++this->current_size_
;
782 // Otherwise, we're to the right of the insertion point, so
783 // insert into the left subtree.
784 else // (result == RIGHT)
786 if (current
->left ())
787 // If there is already a left subtree, complain.
788 ACELIB_ERROR_RETURN ((LM_ERROR
,
790 ACE_TEXT ("\nleft subtree already present in ")
791 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
795 // The left subtree is empty: insert new node there.
796 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *tmp
= 0;
797 ACE_NEW_MALLOC_RETURN
799 (reinterpret_cast<ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>*>
800 (this->allocator_
->malloc (sizeof (*tmp
)))),
801 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>) (k
, t
),
804 // If the node was successfully inserted, set its
805 // parent, rebalance the tree, color the root black, and
806 // return a pointer to the inserted item.
807 entry
= current
->left ();
808 current
->left ()->parent (current
);
809 RB_rebalance (current
->left ());
810 this->root_
->color (ACE_RB_Tree_Node_Base::BLACK
);
811 ++this->current_size_
;
818 // The tree is empty: insert at the root and color the root black.
819 ACE_NEW_MALLOC_RETURN
821 (reinterpret_cast<ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>*>
822 (this->allocator_
->malloc (sizeof (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>)))),
823 (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>) (k
, t
),
825 this->root_
->color (ACE_RB_Tree_Node_Base::BLACK
);
826 ++this->current_size_
;
832 // Removes the item associated with the given key from the tree and
833 // destroys it. Returns 1 if it found the item and successfully
834 // destroyed it, 0 if it did not find the item, or -1 if an error
835 // occurred. This method should only be called with locks already
838 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
839 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::remove_i (const EXT_ID
&k
, INT_ID
&i
)
841 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)");
843 // Find a matching node, if there is one.
844 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *z
;
845 RB_SearchResult result
= LEFT
;
846 z
= find_node (k
, result
);
848 // If there is a matching node: remove and destroy it.
849 if (z
&& result
== EXACT
)
851 // Return the internal id stored in the deleted node.
853 return -1 == this->remove_i (z
) ? -1 : 1;
856 // No matching node was found: return 0.
860 /// Recursive function to dump the state of an object.
861 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
862 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::
863 dump_i (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *node
) const
865 #if defined (ACE_HAS_DUMP)
870 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("\ndown left\n")));
871 this->dump_i (node
->left ());
872 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("\nup left\n")));
874 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("\ndown right\n")));
875 this->dump_i (node
->right ());
876 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("\nup right\n")));
880 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("\nNULL POINTER (BLACK)\n")));
882 #else /* !ACE_HAS_DUMP */
883 ACE_UNUSED_ARG (node
);
884 #endif /* ACE_HAS_DUMP */
887 /// Function to dump node itself. Does not show parameterized node contents
888 /// in its basic form, but template specialization can be used to
889 /// provide definitions for various EXT_ID and INT_ID types.
891 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
892 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::
893 dump_node_i (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> &node
) const
895 #if defined (ACE_HAS_DUMP)
896 const char * color_str
= (node
.color () == ACE_RB_Tree_Node_Base::RED
)
899 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT (" color=[%s]\n"), color_str
));
900 #else /* !ACE_HAS_DUMP */
901 ACE_UNUSED_ARG (node
);
902 #endif /* ACE_HAS_DUMP */
905 /// Tests the red-black invariant(s) throughout the whole tree.
907 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
908 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::test_invariant ()
910 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant");
911 ACE_READ_GUARD_RETURN (ACE_LOCK
, ace_mon
, this->lock_
, -1);
913 // Recurse from the root, starting with the measured black height at
914 // 0, and the expected black height at -1, which will cause the
915 // count from first measured path to a leaf to be used as the
916 // expected one from that point onward (the key is to check
918 int expected_black_height
= -1;
919 if (this->test_invariant_recurse (this->root_
, expected_black_height
, 0) == 0)
921 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("invariant holds\n")));
928 /// Recursive function to test the red-black invariant(s) at all nodes in a subtree.
930 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
931 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::test_invariant_recurse (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
,
932 int & expected_black_height
,
933 int measured_black_height
)
935 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse");
939 // Count each leaf (zero pointer) as a black node (per CLR algorithm description).
940 ++measured_black_height
;
942 if (expected_black_height
== -1)
944 expected_black_height
= measured_black_height
;
946 else if (expected_black_height
!= measured_black_height
)
948 ACELIB_ERROR_RETURN ((LM_ERROR
,
949 ACE_TEXT ("\nexpected_black_height = %d but ")
950 ACE_TEXT ("\nmeasured_black_height = %d in ")
951 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n"),
952 expected_black_height
, measured_black_height
),
959 // Check the invariant that a red node cannot have a red child.
960 if (x
->color () == ACE_RB_Tree_Node_Base::RED
)
962 if (x
->left () && x
->left ()->color () == ACE_RB_Tree_Node_Base::RED
)
964 ACELIB_ERROR_RETURN ((LM_ERROR
,
966 ACE_TEXT ("\nRED parent has RED left child in ")
967 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
971 if (x
->right () && x
->right ()->color () == ACE_RB_Tree_Node_Base::RED
)
973 ACELIB_ERROR_RETURN ((LM_ERROR
,
975 ACE_TEXT ("\nRED parent has RED right child in ")
976 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
982 // Count each black node traversed.
983 ++measured_black_height
;
986 return (test_invariant_recurse (x
->left (), expected_black_height
, measured_black_height
) == 0)
987 ? test_invariant_recurse (x
->right (), expected_black_height
, measured_black_height
)
991 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> int
992 ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::remove_i (ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *z
)
994 ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)");
996 // Delete the node and reorganize the tree to satisfy the Red-Black
999 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *x
;
1000 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *y
;
1001 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *parent
;
1003 if (z
->left () && z
->right ())
1004 y
= RB_tree_successor (z
);
1016 parent
= y
->parent ();
1024 if (y
== parent
->left ())
1034 // Replace node z with node y, since y's pointer may well be
1035 // held externally, and be linked with y's key and item.
1036 // We will end up deleting the old unlinked, node z.
1038 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *zParent
= z
->parent ();
1039 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *zLeftChild
= z
->left ();
1040 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
> *zRightChild
= z
->right ();
1044 if (z
== zParent
->left ())
1057 y
->parent (zParent
);
1061 zLeftChild
->parent (y
);
1063 y
->left (zLeftChild
);
1067 zRightChild
->parent (y
);
1069 y
->right (zRightChild
);
1076 ACE_RB_Tree_Node_Base::RB_Tree_Node_Color yColor
= y
->color ();
1077 y
->color (z
->color ());
1080 //Reassign the y pointer to z because the node that y points to will be
1085 // CLR pp. 263 says that nil nodes are implicitly colored BLACK
1086 if (!y
|| y
->color () == ACE_RB_Tree_Node_Base::BLACK
)
1087 RB_delete_fixup (x
, parent
);
1092 ACE_DES_FREE_TEMPLATE2 (y
,
1093 this->allocator_
->free
,
1096 --this->current_size_
;
1103 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1104 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
, int set_first
)
1105 : tree_ (&tree
), node_ (0)
1107 ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree, int)");
1109 // Position the iterator at the first (or last) node in the tree.
1111 node_
= tree_
->RB_tree_minimum (tree_
->root_
);
1113 node_
= tree_
->RB_tree_maximum (tree_
->root_
);
1116 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1117 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
, ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>* entry
)
1118 : tree_ (&tree
), node_ (0)
1120 ACE_TRACE ("ACE_RB_Tree_Iterator_Base(const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, ACE_RB_Tree_Node<EXT_ID, INT_ID>* entry)");
1124 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1125 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator_Base (const EXT_ID
& key
,ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
)
1126 : tree_ (&tree
), node_ (0)
1128 ACE_TRACE("ACE_RB_Tree_Iterator_Base (ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, const EXT_ID& key)");
1129 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>* entry
= 0;
1130 tree
.find_i(key
, entry
);
1134 // Copy constructor.
1136 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1137 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &iter
)
1138 : tree_ (iter
.tree_
),
1141 ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree_Iterator_Base)");
1144 // Assignment operator.
1146 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
> void
1147 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::operator= (const ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &iter
)
1149 ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator=");
1159 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1160 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::~ACE_RB_Tree_Iterator_Base ()
1162 ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base");
1165 // Dump the state of an object.
1167 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1169 ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::dump_i () const
1171 ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump_i");
1173 ACELIB_DEBUG ((LM_DEBUG
, ACE_BEGIN_DUMP
, this));
1174 ACELIB_DEBUG ((LM_DEBUG
, ACE_TEXT ("\nnode_ = %x\n"), this->node_
));
1175 ACELIB_DEBUG ((LM_DEBUG
, ACE_END_DUMP
));
1181 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1182 ACE_RB_Tree_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
,
1184 : ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> (tree
, set_first
)
1186 ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
1189 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1190 ACE_RB_Tree_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
,
1191 ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>* entry
)
1192 : ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> (tree
,entry
)
1194 ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
1197 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1198 ACE_RB_Tree_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Iterator (const EXT_ID
& key
,ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
)
1199 : ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>(key
,tree
)
1201 ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator");
1206 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1207 ACE_RB_Tree_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::~ACE_RB_Tree_Iterator ()
1209 ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator");
1215 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1216 ACE_RB_Tree_Reverse_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
, int set_last
)
1217 : ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> (tree
, set_last
? 0 : 1)
1219 ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
1222 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1223 ACE_RB_Tree_Reverse_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
, ACE_RB_Tree_Node
<EXT_ID
, INT_ID
>* entry
)
1224 : ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> (tree
,entry
)
1226 ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
1229 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1230 ACE_RB_Tree_Reverse_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::ACE_RB_Tree_Reverse_Iterator (const EXT_ID
& key
,ACE_RB_Tree
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
> &tree
)
1231 : ACE_RB_Tree_Iterator_Base
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>(key
,tree
)
1233 ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator");
1238 template <class EXT_ID
, class INT_ID
, class COMPARE_KEYS
, class ACE_LOCK
>
1239 ACE_RB_Tree_Reverse_Iterator
<EXT_ID
, INT_ID
, COMPARE_KEYS
, ACE_LOCK
>::~ACE_RB_Tree_Reverse_Iterator ()
1241 ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator");
1244 ACE_END_VERSIONED_NAMESPACE_DECL
1246 #endif /* !ACE_RB_TREE_CPP */