ChangeLogTag: Wed May 28 08:10:00 UTC 2008 Simon Massey <sma at prismtech dot com>

5 files changed, 213 insertions, 0 deletions

diff --git a/ACE/ChangeLog b/ACE/ChangeLog
index f792f111f87..19392ec282e 100644
--- a/ACE/ChangeLog
+++ b/ACE/ChangeLog
@@ -1,3 +1,13 @@
+Wed May 28 08:10:00 UTC 2008  Simon Massey  <sma at prismtech dot com>
+
+        * tests/Bug_3332_Regression_Test.cpp:
+        * tests/Bug_3332_Regression_Test.txt:
+        * tests/run_test.lst:
+        * tests/tests.mpc:
+
+          Regression test for the change of:
+          Fri May 23 12:45:00 UTC 2008 * ace/RB_Tree.cpp.
+
 Tue May 27 23:10:33 UTC 2008  J.T. Conklin  <jtc@acorntoolworks.com>
 
         * ace/Makefile.am:
diff --git a/ACE/tests/Bug_3332_Regression_Test.cpp b/ACE/tests/Bug_3332_Regression_Test.cpp
new file mode 100644
index 00000000000..8f0711ec7b6
--- /dev/null
+++ b/ACE/tests/Bug_3332_Regression_Test.cpp
@@ -0,0 +1,145 @@
+// $Id$
+
+// ============================================================================
+//
+// = LIBRARY
+//    tests
+//
+// = FILENAME
+//    RB_3332_Regression_Test.cpp
+//
+// = DESCRIPTION
+//    This is a test to verify the node unbind/remove stability.
+//    Originally the deletion of a node from the rb_tree would cause some nodes
+//    to be "swapped" and the node being deleted to be reused to hold data still
+//    in the rb_tree, whilst the original "still in the tree" data node would be
+//    unbound instead. This caused externally held pointers to existing data that
+//    should still be in the tree to become invalidated unnecessarily. This test
+//    ensures that the node NOT being deleted always keep their original enteries
+//    (and thus only the deleted node is actually unbound and released).
+//
+// = AUTHOR
+//    Simon Massey <sma@prismtech.com>
+//
+// ============================================================================
+
+#include "test_config.h" /* Include first to enable ACE_ASSERT. */
+#include "ace/RB_Tree.h"
+#include "ace/Null_Mutex.h"
+
+namespace
+{
+  struct Nodes
+  {
+    char key;
+    int  value;
+    ACE_RB_Tree_Node<char, int> *node;
+  } nodes[] = {{'a',  1, 0},
+               {'f',  6, 0},
+               {'c',  3, 0},
+               {'e',  5, 0},
+               {'g',  7, 0},
+               {'b',  2, 0},
+               {'h',  8, 0},
+               {'d',  4, 0},
+               {'i',  9, 0},
+               {'l', 12, 0},
+               {'j', 10, 0},
+               {'k', 11, 0},
+               {'m', 13, 0}};
+}
+
+int
+run_main (int, ACE_TCHAR *[])
+{
+  int result = 0;
+  ACE_START_TEST (ACE_TEXT ("Bug_3332_Regression_Test"));
+
+  ACE_RB_Tree<char, int, ACE_Less_Than<char>, ACE_Null_Mutex> tree;
+
+  ACE_DEBUG ((LM_DEBUG, "Creating Tree\n"));
+  {for (int i= 0; i < sizeof(nodes)/sizeof(Nodes); ++i)
+  {
+    if (0 != tree.bind (nodes[i].key, nodes[i].value, nodes[i].node))
+    {
+      ACE_DEBUG ((LM_ERROR, ": Binding failed for %c=%d\n", nodes[i].key, nodes[i].value));
+      result = 1;
+    }
+  }}
+
+  if (!result)
+  {
+    ACE_DEBUG ((LM_DEBUG, "Validating Tree\n"));
+    {for (int i= 0; i < sizeof(nodes)/sizeof(Nodes); ++i)
+    {
+      ACE_RB_Tree_Node<char, int> *node;
+
+      if (tree.find (nodes[i].key, node))
+      {
+        ACE_DEBUG ((LM_ERROR, ": Can't find key %c in tree\n", nodes[i].key));
+        result = 2;
+      }
+      else if (nodes[i].node != node)
+      {
+        ACE_DEBUG ((LM_ERROR, ": entry %c=%d has ALREADY moved from %@ to %@\n", nodes[i].key, nodes[i].value, nodes[i].node, node));
+        result = 3;
+      }
+      else for (int j= i+1; j < sizeof(nodes)/sizeof(Nodes); ++j)
+      {
+        if (nodes[i].node == nodes[j].node)
+        {
+          ACE_DEBUG ((LM_ERROR, ": Duplicate Binding (%@) for %c=%d and %c=%d\n", nodes[i].node, nodes[i].key, nodes[i].value, nodes[j].key, nodes[j].value));
+          result = 4;
+       }
+      }
+    }}
+
+    if (!result)
+    {
+      {for (int i= 0; i < sizeof(nodes)/sizeof(Nodes); ++i)
+      {
+        ACE_DEBUG ((LM_DEBUG, "Deleting node %c=%d @ %@\n", nodes[i].key, nodes[i].value, nodes[i].node));
+        if (tree.unbind (nodes[i].key))
+        {
+          ACE_DEBUG ((LM_ERROR, ": Can't unbind key %c from tree\n", nodes[i].key));
+          result = 5;
+        }
+        else
+        {
+          ACE_RB_Tree_Node<char, int> *node;
+
+          if (0 == tree.find (nodes[i].key, node))
+          {
+            ACE_DEBUG ((LM_ERROR, ": Found %c=%d @ %@ in tree\n", node->key(), node->item(), node));
+            result = 6;
+          }
+          else {for (int j= i+1; j < sizeof(nodes)/sizeof(Nodes); ++j)
+          {
+            if (tree.find (nodes[j].key, node))
+            {
+              ACE_DEBUG ((LM_ERROR, ": Can't find key %c in tree\n", nodes[j].key));
+              result = 7;
+            }
+            else if (nodes[j].node != node)
+            {
+              ACE_DEBUG ((LM_ERROR, ": entry %c=%d has moved from %@ to %@\n", nodes[j].key, nodes[j].value, nodes[j].node, node));
+              nodes[j].node = node;  // Don't keep reporting this same issue on further deletions.
+              result = 8;
+            }
+            else if (nodes[j].key != node->key() || nodes[j].value != node->item())
+            {
+              ACE_DEBUG ((LM_ERROR, ": entry %c=%d has changed to %c=%d\n", nodes[j].key, nodes[j].value, node->key(), node->item()));
+              nodes[j].key= node->key(); // Don't keep reporting this problem on further deletions.
+              nodes[j].value = node->item();
+              result = 9;
+            }
+          }}
+        }
+      }}
+    }
+  }
+
+  ACE_DEBUG ((LM_DEBUG, "Finished\n"));
+  ACE_END_TEST;
+  return result;
+}
diff --git a/ACE/tests/Bug_3332_Regression_Test.txt b/ACE/tests/Bug_3332_Regression_Test.txt
new file mode 100644
index 00000000000..964530cf477
--- /dev/null
+++ b/ACE/tests/Bug_3332_Regression_Test.txt
@@ -0,0 +1,50 @@
+// $Id$
+
+Bug_3332_Regression_Test: (RB_Tree nodes are swapped and "in use" nodes
+are deleted instead of the dropped node being unbound). This is an example
+of the tests output when the problem occurs:
+
+May 27 16:41:50.843 2008@LM_DEBUG@(976|2568) Starting Bug_3332_Regression_Test test at Tue May 27 2008 16:41:50.843000
+May 27 16:41:50.843 2008@LM_DEBUG@Creating Tree
+May 27 16:41:50.843 2008@LM_DEBUG@Validating Tree
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node a=1 @ 0098F1A0
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node f=6 @ 0098F1E8
+May 27 16:41:50.843 2008@LM_ERROR@: entry g=7 has moved from 0098F2C0 to 0098F1E8
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node c=3 @ 0098F230
+May 27 16:41:50.843 2008@LM_ERROR@: entry d=4 has moved from 0098F398 to 0098F230
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node e=5 @ 0098F278
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node g=7 @ 0098F1E8
+May 27 16:41:50.843 2008@LM_ERROR@: entry h=8 has moved from 0098F350 to 0098F1E8
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node b=2 @ 0098F308
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node h=8 @ 0098F1E8
+May 27 16:41:50.843 2008@LM_ERROR@: entry i=9 has moved from 0098F3E0 to 0098F1E8
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node d=4 @ 0098F230
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node i=9 @ 0098F1E8
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node l=12 @ 0098F428
+May 27 16:41:50.843 2008@LM_ERROR@: entry m=13 has moved from 0098F500 to 0098F428
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node j=10 @ 0098F470
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node k=11 @ 0098F4B8
+May 27 16:41:50.843 2008@LM_DEBUG@Deleting node m=13 @ 0098F428
+May 27 16:41:50.843 2008@LM_DEBUG@Finished
+May 27 16:41:50.843 2008@LM_DEBUG@(976|2568) Ending Bug_3332_Regression_Test test at Tue May 27 2008 16:41:50.843000
+
+and this is what it looks like when it passes the test:
+
+May 28 09:04:11.239 2008@LM_DEBUG@(4012|2900) Starting Bug_3332_Regression_Test test at Wed May 28 2008 09:04:11.239000
+May 28 09:04:11.239 2008@LM_DEBUG@Creating Tree
+May 28 09:04:11.239 2008@LM_DEBUG@Validating Tree
+May 28 09:04:11.239 2008@LM_DEBUG@Deleting node a=1 @ 0098F1B8
+May 28 09:04:11.239 2008@LM_DEBUG@Deleting node f=6 @ 0098F200
+May 28 09:04:11.239 2008@LM_DEBUG@Deleting node c=3 @ 0098F248
+May 28 09:04:11.239 2008@LM_DEBUG@Deleting node e=5 @ 0098F290
+May 28 09:04:11.239 2008@LM_DEBUG@Deleting node g=7 @ 0098F2D8
+May 28 09:04:11.239 2008@LM_DEBUG@Deleting node b=2 @ 0098F320
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node h=8 @ 0098F368
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node d=4 @ 0098F3B0
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node i=9 @ 0098F3F8
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node l=12 @ 0098F440
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node j=10 @ 0098F488
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node k=11 @ 0098F4D0
+May 28 09:04:11.255 2008@LM_DEBUG@Deleting node m=13 @ 0098F518
+May 28 09:04:11.255 2008@LM_DEBUG@Finished
+May 28 09:04:11.255 2008@LM_DEBUG@(4012|2900) Ending Bug_3332_Regression_Test test at Wed May 28 2008 09:04:11.255000
diff --git a/ACE/tests/run_test.lst b/ACE/tests/run_test.lst
index a28e956f735..35a5191d6fc 100644
--- a/ACE/tests/run_test.lst
+++ b/ACE/tests/run_test.lst
@@ -126,6 +126,7 @@ Process_Manual_Event_Test: !HPUX !VxWorks !ACE_FOR_TAO !PHARLAP
 Process_Mutex_Test: !VxWorks !ACE_FOR_TAO !PHARLAP
 Process_Semaphore_Test: !VxWorks !ACE_FOR_TAO !PHARLAP
 RB_Tree_Test
+Bug_3332_Regression_Test
 Reactor_Dispatch_Order_Test
 Reactor_Exceptions_Test
 Reactor_Notify_Test: !ST !ACE_FOR_TAO
diff --git a/ACE/tests/tests.mpc b/ACE/tests/tests.mpc
index df29bc237b7..b5f6b3eef5a 100644
--- a/ACE/tests/tests.mpc
+++ b/ACE/tests/tests.mpc
@@ -873,6 +873,13 @@ project(RB Tree Test) : acetest {
   }
 }
 
+project(Bug_3332_Regression_Test) : acetest {
+  exename = Bug_3332_Regression_Test
+  Source_Files {
+    Bug_3332_Regression_Test.cpp
+  }
+}
+
 project(Reactors Test) : acetest {
   exename = Reactors_Test
   Source_Files {