summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog-99b11
-rw-r--r--README1
-rw-r--r--ace/RB_Tree.cpp44
3 files changed, 42 insertions, 14 deletions
diff --git a/ChangeLog-99b b/ChangeLog-99b
index f5a319f34b8..b314e2f47ca 100644
--- a/ChangeLog-99b
+++ b/ChangeLog-99b
@@ -1,3 +1,14 @@
+Mon May 03 09:35:00 1999 Chris Gill <cdgill@cs.wustl.edu>
+
+ * ace/RB_Tree.cpp: fixed bug in ACE_RB_Tree::RB_delete_fixup in which
+ a null pointer was dereferenced while trying to determine the color
+ of the node that was being pointed to. Per the RB Tree discussion
+ in Cormen Lieserson and Rivest's "Introduction to Algorithms", after
+ which this implementation is modeled, a nil node is implicity
+ treated as having been colored BLACK. Thanks to Long Hoang
+ <LHoang@hwdcsaws.cahwnet.gov> for reporting the problem and
+ providing a test program that showed the bug.
+
Mon May 03 15:53:15 1999 David L. Levine <levine@cs.wustl.edu>
* include/makeinclude/platform_vxworks5.x_g++.GNU,
diff --git a/README b/README
index ff9ed830f2c..39b62fae95a 100644
--- a/README
+++ b/README
@@ -828,6 +828,7 @@ Brian Wallis <Brian.Wallis@sr.com.au>
Sandeep Goyal <sagoyal@hss.hns.com>
englishmalc@my-dejanew.com
Frank O'Dwyer <fod@brd.ie>
+Long Hoang <LHoang@hwdcsaws.cahwnet.gov>
I would particularly like to thank Paul Stephenson, who worked with me
at Ericsson and is now at ObjectSpace. Paul devised the recursive
diff --git a/ace/RB_Tree.cpp b/ace/RB_Tree.cpp
index 5b619313e6d..2c2196366e3 100644
--- a/ace/RB_Tree.cpp
+++ b/ace/RB_Tree.cpp
@@ -315,7 +315,8 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::remove (const KEY &k)
z->key () = y->key ();
z->item () = y->item ();
}
- if (y->color () == ACE_RB_Tree_Node_Base::BLACK)
+ // CLR pp. 263 says that nil nodes are implicitly colored BLACK
+ if (!y || y->color () == ACE_RB_Tree_Node_Base::BLACK)
{
RB_delete_fixup (x);
}
@@ -434,27 +435,36 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<KE
template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void
ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x)
{
- while ((x) && (x->parent ()) && (x->color () == ACE_RB_Tree_Node_Base::BLACK))
+ while (x &&
+ x->parent () &&
+ x->color () == ACE_RB_Tree_Node_Base::BLACK)
{
if (x == x->parent ()->left ())
{
ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->right ();
- if (w->color () == ACE_RB_Tree_Node_Base::RED)
+ if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
{
w->color (ACE_RB_Tree_Node_Base::BLACK);
x->parent ()->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_left (x->parent ());
w = x->parent ()->right ();
}
- if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
- (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
+ // CLR pp. 263 says that nil nodes are implicitly colored BLACK
+ if ((w) &&
+ (!w->left () ||
+ w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
+ (!w->right () ||
+ w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
{
w->color (ACE_RB_Tree_Node_Base::RED);
x = x->parent ();
}
else
{
- if (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)
+ // CLR pp. 263 says that nil nodes are implicitly colored BLACK
+ if (w &&
+ (!w->right () ||
+ w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
{
w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
w->color (ACE_RB_Tree_Node_Base::RED);
@@ -471,22 +481,27 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<K
else
{
ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->left ();
- if (w->color () == ACE_RB_Tree_Node_Base::RED)
+ if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
{
w->color (ACE_RB_Tree_Node_Base::BLACK);
x->parent ()->color (ACE_RB_Tree_Node_Base::RED);
RB_rotate_right (x->parent ());
w = x->parent ()->left ();
}
- if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
- (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
+ // CLR pp. 263 says that nil nodes are implicitly colored BLACK
+ if ((!w->left () ||
+ w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) &&
+ (!w->right () ||
+ w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
{
w->color (ACE_RB_Tree_Node_Base::RED);
x = x->parent ();
}
else
{
- if (w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
+ // CLR pp. 263 says that nil nodes are implicitly colored BLACK
+ if (!w->left () ||
+ w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
{
w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
w->color (ACE_RB_Tree_Node_Base::RED);
@@ -569,8 +584,9 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY,
{
ACE_RB_Tree_Node<KEY, T> *y = 0;
- while ((x) && (x->parent ())
- && (x->parent ()->color () == ACE_RB_Tree_Node_Base::RED))
+ while (x &&
+ x->parent () &&
+ x->parent ()->color () == ACE_RB_Tree_Node_Base::RED)
{
if (! x->parent ()->parent ())
{
@@ -584,7 +600,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY,
if (x->parent () == x->parent ()->parent ()->left ())
{
y = x->parent ()->parent ()->right ();
- if (y && (y->color () == ACE_RB_Tree_Node_Base::RED))
+ if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
{
// Handle case 1 (see CLR book, pp. 269).
x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
@@ -610,7 +626,7 @@ ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY,
else
{
y = x->parent ()->parent ()->left ();
- if (y && (y->color () == ACE_RB_Tree_Node_Base::RED))
+ if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
{
// Handle case 1 (see CLR book, pp. 269).
x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
View Lorry Controller Status