ACE/tests/Bug_3332_Regression_Test.cpp

   1 // ============================================================================
   2 //
   3 // = LIBRARY
   4 //    tests
   5 //
   6 // = FILENAME
   7 //    Bug_3332_Regression_Test.cpp
   8 //
   9 // = DESCRIPTION
  10 //    This is a test to verify the node unbind/remove stability.
  11 //    Originally the deletion of a node from the rb_tree would cause some nodes
  12 //    to be "swapped" and the node being deleted to be reused to hold data still
  13 //    in the rb_tree, whilst the original "still in the tree" data node would be
  14 //    unbound instead. This caused externally held pointers to existing data that
  15 //    should still be in the tree to become invalidated unnecessarily. This test
  16 //    ensures that the node NOT being deleted always keep their original enteries
  17 //    (and thus only the deleted node is actually unbound and released).
  18 //
  19 // = AUTHOR
  20 //    Simon Massey <sma@prismtech.com>
  21 //
  22 // ============================================================================
  23
  24 #include "test_config.h" /* Include first to enable ACE_TEST_ASSERT. */
  25 #include "ace/RB_Tree.h"
  26 #include "ace/Null_Mutex.h"
  27
  28 namespace
  29 {
  30   struct Nodes
  31   {
  32     char key;
  33     int  value;
  34     ACE_RB_Tree_Node<char, int> *node;
  35   } nodes[] = {{'a',  1, 0},
  36                {'f',  6, 0},
  37                {'c',  3, 0},
  38                {'e',  5, 0},
  39                {'g',  7, 0},
  40                {'b',  2, 0},
  41                {'h',  8, 0},
  42                {'d',  4, 0},
  43                {'i',  9, 0},
  44                {'l', 12, 0},
  45                {'j', 10, 0},
  46                {'k', 11, 0},
  47                {'m', 13, 0}};
  48 }
  49
  50 int
  51 run_main (int, ACE_TCHAR *[])
  52 {
  53   int result = 0;
  54   ACE_START_TEST (ACE_TEXT ("Bug_3332_Regression_Test"));
  55
  56   ACE_RB_Tree<char, int, ACE_Less_Than<char>, ACE_Null_Mutex> tree;
  57
  58   ACE_DEBUG ((LM_DEBUG, "Creating Tree\n"));
  59   {for (size_t i= 0u; i < sizeof(nodes)/sizeof(Nodes); ++i)
  60   {
  61     if (0 != tree.bind (nodes[i].key, nodes[i].value, nodes[i].node))
  62     {
  63       ACE_DEBUG ((LM_ERROR, ": Binding failed for %c=%d\n", nodes[i].key, nodes[i].value));
  64       result = 1;
  65     }
  66   }}
  67
  68   if (!result)
  69   {
  70     ACE_DEBUG ((LM_DEBUG, "Validating Tree\n"));
  71     {for (size_t i= 0u; i < sizeof(nodes)/sizeof(Nodes); ++i)
  72     {
  73       ACE_RB_Tree_Node<char, int> *node = 0;
  74
  75       if (tree.find (nodes[i].key, node))
  76       {
  77         ACE_DEBUG ((LM_ERROR, ": Can't find key %c in tree\n", nodes[i].key));
  78         result = 2;
  79       }
  80       else if (nodes[i].node != node)
  81       {
  82         ACE_DEBUG ((LM_ERROR, ": entry %c=%d has ALREADY moved from %@ to %@\n", nodes[i].key, nodes[i].value, nodes[i].node, node));
  83         result = 3;
  84       }
  85       else for (size_t j= i+1u; j < sizeof(nodes)/sizeof(Nodes); ++j)
  86       {
  87         if (nodes[i].node == nodes[j].node)
  88         {
  89           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));
  90           result = 4;
  91        }
  92       }
  93     }}
  94
  95     if (!result)
  96     {
  97       {for (size_t i= 0u; i < sizeof(nodes)/sizeof(Nodes); ++i)
  98       {
  99         ACE_DEBUG ((LM_DEBUG, "Deleting node %c=%d @ %@\n", nodes[i].key, nodes[i].value, nodes[i].node));
 100         if (tree.unbind (nodes[i].key))
 101         {
 102           ACE_DEBUG ((LM_ERROR, ": Can't unbind key %c from tree\n", nodes[i].key));
 103           result = 5;
 104         }
 105         else
 106         {
 107           ACE_RB_Tree_Node<char, int> *node = 0;
 108
 109           if (0 == tree.find (nodes[i].key, node))
 110           {
 111             ACE_DEBUG ((LM_ERROR, ": Found %c=%d @ %@ in tree\n", node->key(), node->item(), node));
 112             result = 6;
 113           }
 114           else {for (size_t j= i+1u; j < sizeof(nodes)/sizeof(Nodes); ++j)
 115           {
 116             if (tree.find (nodes[j].key, node))
 117             {
 118               ACE_DEBUG ((LM_ERROR, ": Can't find key %c in tree\n", nodes[j].key));
 119               result = 7;
 120             }
 121             else if (nodes[j].node != node)
 122             {
 123               ACE_DEBUG ((LM_ERROR, ": entry %c=%d has moved from %@ to %@\n", nodes[j].key, nodes[j].value, nodes[j].node, node));
 124               nodes[j].node = node;  // Don't keep reporting this same issue on further deletions.
 125               result = 8;
 126             }
 127             else if (nodes[j].key != node->key() || nodes[j].value != node->item())
 128             {
 129               ACE_DEBUG ((LM_ERROR, ": entry %c=%d has changed to %c=%d\n", nodes[j].key, nodes[j].value, node->key(), node->item()));
 130               nodes[j].key= node->key(); // Don't keep reporting this problem on further deletions.
 131               nodes[j].value = node->item();
 132               result = 9;
 133             }
 134           }}
 135         }
 136       }}
 137     }
 138   }
 139
 140   ACE_DEBUG ((LM_DEBUG, "Finished\n"));
 141   ACE_END_TEST;
 142   return result;
 143 }