ACE/tests/RB_Tree_Test.cpp

   1
   2 //=============================================================================
   3 /**
   4  *  @file    RB_Tree_Test.cpp
   5  *
   6  *  This is a test to verify and illustrate the use of the
   7  *  <ACE_RB_Tree ACE_RB_Tree_Iterator> and
   8  *  <ACE_RB_Tree_Reverse_Iterator> classes.  Two different key and
   9  *  item types are used in order to demonstrate specialization of
  10  *  the <ACE_Less_Than> comparison function object template: int
  11  *  (for which the native < operator is sufficient), and const char
  12  *  * (for which < operator semantics must be replaced by strcmp
  13  *  semantics).  An RB tree for each of the four possible type
  14  *  parameter permutations over int and const char * is constructed
  15  *  and filled in, and the resulting order is checked via an
  16  *  iterator over each.
  17  *
  18  *  @author Chris Gill <cdgill@cs.wustl.edu>
  19  */
  20 //=============================================================================
  21
  22 #include "test_config.h" /* Include first to enable ACE_TEST_ASSERT. */
  23 #include "ace/RB_Tree.h"
  24 #include "ace/SString.h"
  25 #include "ace/Null_Mutex.h"
  26 #include "RB_Tree_Test.h"
  27
  28 // Type definitions for the four distinct parameterizations of the
  29 // test.
  30
  31 typedef ACE_RB_Tree_Test<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> INT_INT_RB_TREE_TEST;
  32 typedef ACE_RB_Tree_Test<int, const char *, ACE_Less_Than<int>, ACE_Null_Mutex> INT_STR_RB_TREE_TEST;
  33 typedef ACE_RB_Tree_Test<const char *, int, ACE_Less_Than<const char *>, ACE_Null_Mutex> STR_INT_RB_TREE_TEST;
  34 typedef ACE_RB_Tree_Test<const char *, const char *, ACE_Less_Than<const char *>, ACE_Null_Mutex> STR_STR_RB_TREE_TEST;
  35
  36 // Number of entries placed in each tree.
  37 static int RB_TREE_TEST_ENTRIES = 8;
  38
  39 // These arrays of numbers as ints and character strings are used to
  40 // instantiate key and item arrays in the tests.
  41 static const char *number_strings [] =
  42 {
  43   "10", "20", "30", "40", "50", "60", "70", "80"
  44 };
  45
  46 static int number_integers [] =
  47 {
  48   10, 20, 30, 40, 50, 60, 70, 80
  49 };
  50
  51 // These arrays of ints are used to shuffle the order of insertion and
  52 // deletaion of keys and items for the various tests.
  53 static int int_int_index [] = {0, 1, 2, 3, 4, 5, 6, 7}; // LR inorder
  54 static int int_str_index [] = {7, 6, 5, 4, 3, 2, 1, 0}; // RL inorder
  55 static int str_int_index [] = {4, 6, 2, 7, 5, 3, 1, 0}; // RL BFS
  56 static int str_str_index [] = {4, 2, 1, 0, 3, 6, 5, 7}; // LR preorder
  57
  58
  59 int
  60 run_main (int, ACE_TCHAR *[])
  61 {
  62   ACE_START_TEST (ACE_TEXT ("RB_Tree_Test"));
  63
  64   // Construct and run four distinctly parameterized tests.  Note that
  65   // specialization of the ACE_Less_Than template for character
  66   // strings performs strcmp style string comparisons rather than <
  67   // operator comparison of the const char * pointers themselves.
  68
  69   INT_INT_RB_TREE_TEST int_int_test (RB_TREE_TEST_ENTRIES,
  70                                      number_integers,
  71                                      number_integers,
  72                                      int_int_index);
  73   INT_STR_RB_TREE_TEST int_str_test (RB_TREE_TEST_ENTRIES,
  74                                      number_integers,
  75                                      number_strings,
  76                                      int_str_index);
  77   STR_INT_RB_TREE_TEST str_int_test (RB_TREE_TEST_ENTRIES,
  78                                      number_strings,
  79                                      number_integers,
  80                                      str_int_index);
  81   STR_STR_RB_TREE_TEST str_str_test (RB_TREE_TEST_ENTRIES,
  82                                      number_strings,
  83                                      number_strings,
  84                                      str_str_index);
  85   int_int_test.run_test ();
  86   int_str_test.run_test ();
  87   str_int_test.run_test ();
  88   str_str_test.run_test ();
  89
  90 // ======= Stress Test contributed by Klaus H. Wolf <hw@cyland.com> =========
  91
  92   ACE_RB_Tree<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex> tree;
  93
  94   tree.bind (ACE_CString ("51"),  1);
  95   if (0 != tree.test_invariant ())
  96     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
  97   tree.bind (ACE_CString ("13"),  2);
  98   if (0 != tree.test_invariant ())
  99     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 100   tree.bind (ACE_CString ("36"),  3);
 101   if (0 != tree.test_invariant ())
 102     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 103   tree.bind (ACE_CString ("15"),  4);
 104   if (0 != tree.test_invariant ())
 105     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 106   tree.bind (ACE_CString ("22"),  5);
 107   if (0 != tree.test_invariant ())
 108     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 109   tree.bind (ACE_CString ("25"),  6);
 110   if (0 != tree.test_invariant ())
 111     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 112   tree.bind (ACE_CString ("42"),  7);
 113   if (0 != tree.test_invariant ())
 114     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 115   tree.bind (ACE_CString ("48"),  8);
 116   if (0 != tree.test_invariant ())
 117     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 118   tree.bind (ACE_CString ("03"),  9);
 119   if (0 != tree.test_invariant ())
 120     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 121   tree.bind (ACE_CString ("56"), 10);
 122   if (0 != tree.test_invariant ())
 123     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 124   tree.bind (ACE_CString ("28"), 11);
 125   if (0 != tree.test_invariant ())
 126     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 127   tree.bind (ACE_CString ("55"), 12);
 128   if (0 != tree.test_invariant ())
 129     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 130   tree.bind (ACE_CString ("21"), 13);
 131   if (0 != tree.test_invariant ())
 132     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 133   tree.bind (ACE_CString ("62"), 14);
 134   if (0 != tree.test_invariant ())
 135     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 136   tree.bind (ACE_CString ("18"), 15);
 137   if (0 != tree.test_invariant ())
 138     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 139   tree.bind (ACE_CString ("20"), 16);
 140   if (0 != tree.test_invariant ())
 141     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 142   tree.bind (ACE_CString ("26"), 17);
 143   if (0 != tree.test_invariant ())
 144     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 145   tree.bind (ACE_CString ("29"), 18);
 146   if (0 != tree.test_invariant ())
 147     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 148   tree.bind (ACE_CString ("50"), 19);
 149   if (0 != tree.test_invariant ())
 150     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 151   tree.bind (ACE_CString ("05"), 20);
 152   if (0 != tree.test_invariant ())
 153     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 154   tree.bind (ACE_CString ("59"), 21);
 155   if (0 != tree.test_invariant ())
 156     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 157   tree.bind (ACE_CString ("65"), 22);
 158   if (0 != tree.test_invariant ())
 159     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 160   tree.bind (ACE_CString ("66"), 23);
 161   if (0 != tree.test_invariant ())
 162     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 163   tree.bind (ACE_CString ("45"), 24);
 164   if (0 != tree.test_invariant ())
 165     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 166   tree.bind (ACE_CString ("34"), 25);
 167   if (0 != tree.test_invariant ())
 168     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 169   tree.bind (ACE_CString ("27"), 26);
 170   if (0 != tree.test_invariant ())
 171     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 172   tree.bind (ACE_CString ("40"), 27);
 173   if (0 != tree.test_invariant ())
 174     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 175   tree.bind (ACE_CString ("30"), 28);
 176   if (0 != tree.test_invariant ())
 177     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 178   tree.bind (ACE_CString ("64"), 29);
 179   if (0 != tree.test_invariant ())
 180     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 181   tree.bind (ACE_CString ("11"), 30);
 182   if (0 != tree.test_invariant ())
 183     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 184   tree.bind (ACE_CString ("16"), 31);
 185   if (0 != tree.test_invariant ())
 186     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 187   tree.bind (ACE_CString ("47"), 32);
 188   if (0 != tree.test_invariant ())
 189     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 190   tree.bind (ACE_CString ("10"), 33);
 191   if (0 != tree.test_invariant ())
 192     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 193   tree.bind (ACE_CString ("37"), 34);
 194   if (0 != tree.test_invariant ())
 195     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 196   tree.bind (ACE_CString ("09"), 35);
 197   if (0 != tree.test_invariant ())
 198     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 199   tree.bind (ACE_CString ("54"), 36);
 200   if (0 != tree.test_invariant ())
 201     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 202   tree.bind (ACE_CString ("23"), 37);
 203   if (0 != tree.test_invariant ())
 204     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 205   tree.bind (ACE_CString ("44"), 38);
 206   if (0 != tree.test_invariant ())
 207     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 208   tree.bind (ACE_CString ("19"), 39);
 209   if (0 != tree.test_invariant ())
 210     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 211   tree.bind (ACE_CString ("00"), 40);
 212   if (0 != tree.test_invariant ())
 213     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 214   tree.bind (ACE_CString ("04"), 41);
 215   if (0 != tree.test_invariant ())
 216     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 217   tree.bind (ACE_CString ("63"), 42);
 218   if (0 != tree.test_invariant ())
 219     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 220   tree.bind (ACE_CString ("08"), 43);
 221   if (0 != tree.test_invariant ())
 222     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 223   tree.bind (ACE_CString ("39"), 44);
 224   if (0 != tree.test_invariant ())
 225     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 226   tree.bind (ACE_CString ("31"), 45);
 227   if (0 != tree.test_invariant ())
 228     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 229   tree.bind (ACE_CString ("02"), 46);
 230   if (0 != tree.test_invariant ())
 231     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 232   tree.bind (ACE_CString ("33"), 47);
 233   if (0 != tree.test_invariant ())
 234     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 235   tree.bind (ACE_CString ("60"), 48);
 236   if (0 != tree.test_invariant ())
 237     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 238   tree.bind (ACE_CString ("61"), 49);
 239   if (0 != tree.test_invariant ())
 240     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 241   tree.bind (ACE_CString ("57"), 50);
 242   if (0 != tree.test_invariant ())
 243     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 244   tree.bind (ACE_CString ("43"), 51);
 245   if (0 != tree.test_invariant ())
 246     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 247   tree.bind (ACE_CString ("46"), 52);
 248   if (0 != tree.test_invariant ())
 249     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 250   tree.bind (ACE_CString ("38"), 53);
 251   if (0 != tree.test_invariant ())
 252     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 253   tree.bind (ACE_CString ("01"), 54);
 254   if (0 != tree.test_invariant ())
 255     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 256   tree.bind (ACE_CString ("12"), 55);
 257   if (0 != tree.test_invariant ())
 258     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 259   tree.bind (ACE_CString ("24"), 56);
 260   if (0 != tree.test_invariant ())
 261     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 262   tree.bind (ACE_CString ("52"), 57);
 263   if (0 != tree.test_invariant ())
 264     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 265   tree.bind (ACE_CString ("07"), 58);
 266   if (0 != tree.test_invariant ())
 267     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 268   tree.bind (ACE_CString ("14"), 59);
 269   if (0 != tree.test_invariant ())
 270     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 271   tree.bind (ACE_CString ("06"), 60);
 272   if (0 != tree.test_invariant ())
 273     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 274   tree.bind (ACE_CString ("58"), 61);
 275   if (0 != tree.test_invariant ())
 276     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 277   tree.bind (ACE_CString ("49"), 62);
 278   if (0 != tree.test_invariant ())
 279     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 280   tree.bind (ACE_CString ("17"), 63);
 281   if (0 != tree.test_invariant ())
 282     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 283   tree.bind (ACE_CString ("53"), 64);
 284   if (0 != tree.test_invariant ())
 285     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 286   tree.bind (ACE_CString ("32"), 65);
 287   if (0 != tree.test_invariant ())
 288     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 289   tree.bind (ACE_CString ("35"), 66);
 290   if (0 != tree.test_invariant ())
 291     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 292   tree.bind (ACE_CString ("41"), 67);
 293   if (0 != tree.test_invariant ())
 294     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 295
 296   tree.unbind (ACE_CString ("51"));
 297   if (0 != tree.test_invariant ())
 298     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 299   tree.unbind (ACE_CString ("13"));
 300   if (0 != tree.test_invariant ())
 301     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 302   tree.unbind (ACE_CString ("36"));
 303   if (0 != tree.test_invariant ())
 304     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 305   tree.unbind (ACE_CString ("15"));
 306   if (0 != tree.test_invariant ())
 307     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 308   tree.unbind (ACE_CString ("22"));
 309   if (0 != tree.test_invariant ())
 310     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 311   tree.unbind (ACE_CString ("25"));
 312   if (0 != tree.test_invariant ())
 313     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 314   tree.unbind (ACE_CString ("42"));
 315   if (0 != tree.test_invariant ())
 316     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 317   tree.unbind (ACE_CString ("48"));
 318   if (0 != tree.test_invariant ())
 319     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 320   tree.unbind (ACE_CString ("03"));
 321   if (0 != tree.test_invariant ())
 322     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 323   tree.unbind (ACE_CString ("56"));
 324   if (0 != tree.test_invariant ())
 325     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 326   tree.unbind (ACE_CString ("28"));
 327   if (0 != tree.test_invariant ())
 328     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 329   tree.unbind (ACE_CString ("55"));
 330   if (0 != tree.test_invariant ())
 331     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 332   tree.unbind (ACE_CString ("21"));
 333   if (0 != tree.test_invariant ())
 334     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 335   tree.unbind (ACE_CString ("62"));
 336   if (0 != tree.test_invariant ())
 337     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 338   tree.unbind (ACE_CString ("18"));
 339   if (0 != tree.test_invariant ())
 340     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 341   tree.unbind (ACE_CString ("20"));
 342   if (0 != tree.test_invariant ())
 343     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 344   tree.unbind (ACE_CString ("26"));
 345   if (0 != tree.test_invariant ())
 346     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 347   tree.unbind (ACE_CString ("29"));
 348   if (0 != tree.test_invariant ())
 349     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 350   tree.unbind (ACE_CString ("50"));
 351   if (0 != tree.test_invariant ())
 352     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 353   tree.unbind (ACE_CString ("05"));
 354   if (0 != tree.test_invariant ())
 355     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 356   tree.unbind (ACE_CString ("59"));
 357   if (0 != tree.test_invariant ())
 358     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 359   tree.unbind (ACE_CString ("65"));
 360   if (0 != tree.test_invariant ())
 361     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 362   tree.unbind (ACE_CString ("66"));
 363   if (0 != tree.test_invariant ())
 364     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 365   tree.unbind (ACE_CString ("45"));
 366   if (0 != tree.test_invariant ())
 367     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 368   tree.unbind (ACE_CString ("34"));
 369   if (0 != tree.test_invariant ())
 370     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 371   tree.unbind (ACE_CString ("27"));
 372   if (0 != tree.test_invariant ())
 373     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 374   tree.unbind (ACE_CString ("40"));
 375   if (0 != tree.test_invariant ())
 376     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 377   tree.unbind (ACE_CString ("30"));
 378   if (0 != tree.test_invariant ())
 379     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 380   tree.unbind (ACE_CString ("64"));
 381   if (0 != tree.test_invariant ())
 382     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 383   tree.unbind (ACE_CString ("11"));
 384   if (0 != tree.test_invariant ())
 385     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 386   tree.unbind (ACE_CString ("16"));
 387   if (0 != tree.test_invariant ())
 388     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 389   tree.unbind (ACE_CString ("47"));
 390   if (0 != tree.test_invariant ())
 391     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 392   tree.unbind (ACE_CString ("10"));
 393   if (0 != tree.test_invariant ())
 394     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 395   tree.unbind (ACE_CString ("37"));
 396   if (0 != tree.test_invariant ())
 397     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 398   tree.unbind (ACE_CString ("09"));
 399   if (0 != tree.test_invariant ())
 400     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 401   tree.unbind (ACE_CString ("54"));
 402   if (0 != tree.test_invariant ())
 403     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 404   tree.unbind (ACE_CString ("23"));
 405   if (0 != tree.test_invariant ())
 406     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 407   tree.unbind (ACE_CString ("44"));
 408   if (0 != tree.test_invariant ())
 409     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 410   tree.unbind (ACE_CString ("19"));
 411   if (0 != tree.test_invariant ())
 412     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 413   tree.unbind (ACE_CString ("00"));
 414   if (0 != tree.test_invariant ())
 415     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 416   tree.unbind (ACE_CString ("04"));
 417   if (0 != tree.test_invariant ())
 418     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 419   tree.unbind (ACE_CString ("63"));
 420   if (0 != tree.test_invariant ())
 421     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 422   tree.unbind (ACE_CString ("08"));
 423   if (0 != tree.test_invariant ())
 424     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 425   tree.unbind (ACE_CString ("39"));
 426   if (0 != tree.test_invariant ())
 427     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 428   tree.unbind (ACE_CString ("31"));
 429   if (0 != tree.test_invariant ())
 430     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 431   tree.unbind (ACE_CString ("02"));
 432   if (0 != tree.test_invariant ())
 433     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 434   tree.unbind (ACE_CString ("33"));
 435   if (0 != tree.test_invariant ())
 436     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 437   tree.unbind (ACE_CString ("60"));
 438   if (0 != tree.test_invariant ())
 439     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 440   tree.unbind (ACE_CString ("61"));
 441   if (0 != tree.test_invariant ())
 442     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 443   tree.unbind (ACE_CString ("57"));
 444   if (0 != tree.test_invariant ())
 445     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 446   tree.unbind (ACE_CString ("43"));
 447   if (0 != tree.test_invariant ())
 448     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 449   tree.unbind (ACE_CString ("46"));
 450   if (0 != tree.test_invariant ())
 451     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 452   tree.unbind (ACE_CString ("38"));
 453   if (0 != tree.test_invariant ())
 454     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 455   tree.unbind (ACE_CString ("01"));
 456   if (0 != tree.test_invariant ())
 457     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 458   tree.unbind (ACE_CString ("12"));
 459   if (0 != tree.test_invariant ())
 460     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 461   tree.unbind (ACE_CString ("24"));
 462   if (0 != tree.test_invariant ())
 463     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 464   tree.unbind (ACE_CString ("52"));
 465   if (0 != tree.test_invariant ())
 466     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 467   tree.unbind (ACE_CString ("07"));
 468   if (0 != tree.test_invariant ())
 469     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 470   tree.unbind (ACE_CString ("14"));
 471   if (0 != tree.test_invariant ())
 472     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 473   tree.unbind (ACE_CString ("06"));
 474   if (0 != tree.test_invariant ())
 475     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 476   tree.unbind (ACE_CString ("58"));
 477   if (0 != tree.test_invariant ())
 478     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 479   tree.unbind (ACE_CString ("49"));
 480   if (0 != tree.test_invariant ())
 481     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 482   tree.unbind (ACE_CString ("17"));
 483   if (0 != tree.test_invariant ())
 484     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 485   tree.unbind (ACE_CString ("53"));
 486   if (0 != tree.test_invariant ())
 487     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 488   tree.unbind (ACE_CString ("32"));
 489   if (0 != tree.test_invariant ())
 490     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 491   tree.unbind (ACE_CString ("35"));
 492   if (0 != tree.test_invariant ())
 493     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 494   tree.unbind (ACE_CString ("41"));
 495   if (0 != tree.test_invariant ())
 496     ACE_ERROR ((LM_ERROR, ACE_TEXT ("Invariant failure at line %l\n")));
 497
 498 // ======== End Stress Test ===================
 499
 500   ACE_END_TEST;
 501   return 0;
 502 }
 503
 504 // Constructor.
 505
 506 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 507 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Test
 508   (int entry_count,
 509    EXT_ID key_array [],
 510    INT_ID item_array [],
 511    int order_index [])
 512   : stable_fwd_iter_ (stable_tree_),
 513     stable_rev_iter_ (stable_tree_),
 514     deprecated_fwd_iter_ (deprecated_tree_),
 515     deprecated_rev_iter_ (deprecated_tree_),
 516     entry_count_ (entry_count),
 517     key_array_ (key_array),
 518     item_array_ (item_array),
 519     order_index_ (order_index)
 520 {
 521 }
 522
 523 // Destructor.
 524
 525 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
 526 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Test (void)
 527 {
 528 }
 529
 530 // Run the interface and iteration tests.
 531
 532 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 533 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::run_test (void)
 534 {
 535   // Run the individual portions of the test, in order.
 536
 537   test_tree_insertion ();
 538   test_post_insertion_iteration ();
 539   test_partial_iteration();
 540   test_tree_deletion ();
 541   test_post_deletion_iteration ();
 542 }
 543
 544
 545 // Tests stable and deprecated insertion interfaces.
 546
 547 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 548 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_tree_insertion (void)
 549 {
 550   // Fill in each tree with the key and item from the appropriate
 551   // arrays, using the shuffle index to create the appropriate
 552   // insertion orders.  Then, make sure the inserted item can be found
 553   // using the insertion key.
 554
 555   for (int i = 0; i < entry_count_; ++i)
 556     {
 557       INT_ID item;
 558       int k = order_index_ [i];
 559       if (!(k >= 0 && k < entry_count_))
 560         ACE_ERROR ((LM_ERROR, ACE_TEXT ("Assert failure at line %l\n")));
 561
 562       // Test the new stable ACE_Hash_Map_Manager_Ex compliant interface.
 563       if (0 != stable_tree_.bind (key_array_ [k], item_array_ [k]))
 564         ACE_ERROR ((LM_ERROR,
 565                     ACE_TEXT ("Stable bind %p\n"),
 566                     ACE_TEXT ("failure")));
 567
 568       if (0 != stable_tree_.find (key_array_ [k], item) ||
 569           item != item_array_ [k])
 570         ACE_ERROR ((LM_ERROR,
 571                     ACE_TEXT ("Stable find %p\n"),
 572                     ACE_TEXT ("failure")));
 573
 574       // Test the deprecated interface.
 575       if (0 == deprecated_tree_.insert (key_array_ [k], item_array_ [k]))
 576         ACE_ERROR ((LM_ERROR,
 577                     ACE_TEXT ("Deprecated insert %p\n"),
 578                     ACE_TEXT ("failure")));
 579
 580       if (0 == deprecated_tree_.find (key_array_ [k]) ||
 581           *deprecated_tree_.find (key_array_ [k]) != item_array_ [k])
 582         ACE_ERROR ((LM_ERROR,
 583                     ACE_TEXT ("Deprecated find %p\n"),
 584                     ACE_TEXT ("failure")));
 585    }
 586 }
 587
 588 // Tests forward and reverse iteration after insertion in both trees.
 589
 590 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 591 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_post_insertion_iteration (void)
 592 {
 593   // Reset iterators.
 594
 595   stable_fwd_iter_ = stable_tree_.begin ();
 596   stable_rev_iter_ = stable_tree_.rbegin ();
 597   deprecated_fwd_iter_ = deprecated_tree_.begin ();
 598   deprecated_rev_iter_ = deprecated_tree_.rbegin ();
 599
 600   // Iterate over each of the trees, making sure their entries are in
 601   // the same relative order (i.e., the integers and strings represent
 602   // the same values at each respective position in the tree).
 603   for (int i = 0; i < entry_count_; ++i)
 604     {
 605       INT_ID item;
 606
 607       item = (*stable_fwd_iter_).item ();
 608       if (item != item_array_ [i])
 609         ACE_ERROR ((LM_ERROR,
 610                     ACE_TEXT ("Stable fwd iter, pass %d %p\n"),
 611                     i,
 612                     ACE_TEXT ("failure")));
 613
 614       item = (*stable_rev_iter_).item ();
 615       if (item != item_array_ [entry_count_ - i - 1])
 616         ACE_ERROR ((LM_ERROR,
 617                     ACE_TEXT ("Stable rev iter, pass %d %p\n"),
 618                     i,
 619                     ACE_TEXT ("failure")));
 620
 621       item = (*deprecated_fwd_iter_).item ();
 622       if (item != item_array_ [i])
 623         ACE_ERROR ((LM_ERROR,
 624                     ACE_TEXT ("Deprecated fwd iter, pass %d %p\n"),
 625                     i,
 626                     ACE_TEXT ("failure")));
 627
 628       item = (*deprecated_rev_iter_).item ();
 629       if (item != item_array_ [entry_count_ - i - 1])
 630         ACE_ERROR ((LM_ERROR,
 631                     ACE_TEXT ("Deprecated rev iter, pass %d %p\n"),
 632                     i,
 633                     ACE_TEXT ("failure")));
 634
 635       // Advance each iterator.
 636       ++stable_fwd_iter_;
 637       ++stable_rev_iter_;
 638       ++deprecated_fwd_iter_;
 639       ++deprecated_rev_iter_;
 640     }
 641
 642   // Advance each iterator again - should be a no-op.
 643   ++stable_fwd_iter_;
 644   ++stable_rev_iter_;
 645   ++deprecated_fwd_iter_;
 646   ++deprecated_rev_iter_;
 647
 648
 649   // Make sure each item in each tree has been visited
 650   if (stable_fwd_iter_.done () != 1)
 651     ACE_ERROR ((LM_ERROR,
 652                 ACE_TEXT ("Stable fwd iter not done but should be\n")));
 653   if (stable_rev_iter_.done () != 1)
 654     ACE_ERROR ((LM_ERROR,
 655                 ACE_TEXT ("Stable fwd iter not done but should be\n")));
 656   if (deprecated_fwd_iter_.done () != 1)
 657     ACE_ERROR ((LM_ERROR,
 658                 ACE_TEXT ("Stable fwd iter not done but should be\n")));
 659   if (deprecated_rev_iter_.done () != 1)
 660     ACE_ERROR ((LM_ERROR,
 661                 ACE_TEXT ("Stable fwd iter not done but should be\n")));
 662 }
 663
 664 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 665 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_partial_iteration(void)
 666 {
 667   ACE_RB_Tree_Node<EXT_ID, INT_ID> *tree_node = 0;
 668
 669   stable_tree_.find(key_array_ [2], tree_node);
 670   part_rev_iter_ = ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (stable_tree_, tree_node);
 671   for (int i=2; i >= 0 ; --i)
 672     {
 673       INT_ID item;
 674
 675       item = (*part_rev_iter_).item ();
 676       if (item != item_array_ [i])
 677         ACE_ERROR ((LM_ERROR,
 678                     ACE_TEXT ("Partial rev iter, pass %d %p\n"),
 679                     i,
 680                     ACE_TEXT ("failure")));
 681       part_rev_iter_++;
 682     }
 683
 684   part_fwd_iter_ = ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (key_array_ [5], stable_tree_);
 685   for (int k = 5; k < entry_count_; ++k)
 686     {
 687       INT_ID item;
 688
 689       item = (*part_fwd_iter_).item ();
 690       if (item != item_array_ [k])
 691         ACE_ERROR ((LM_ERROR,
 692                     ACE_TEXT ("Partial fwd iter, pass %d %p\n"),
 693                     k,
 694                     ACE_TEXT ("failure")));
 695       part_fwd_iter_++;
 696     }
 697 }
 698
 699 // Tests stable and deprecated deletion interfaces.
 700
 701 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 702 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_tree_deletion (void)
 703 {
 704   // Remove the even numbered entries from each of the trees.
 705
 706   for (int i = 0; i < entry_count_; i += 2)
 707     {
 708       // Test the new stable ACE_Hash_Map_Manager_Ex compliant
 709       // interface.
 710       if (stable_tree_.unbind (key_array_ [i]) != 0)
 711         ACE_ERROR ((LM_ERROR,
 712                     ACE_TEXT ("Stable tree, failure pass %d %p\n"),
 713                     i,
 714                     ACE_TEXT ("unbind")));
 715
 716       // Test the deprecated interface.
 717       if (deprecated_tree_.remove (key_array_ [i]) != 1)
 718         ACE_ERROR ((LM_ERROR,
 719                     ACE_TEXT ("Deprecated tree, failure pass %d %p\n"),
 720                     i,
 721                     ACE_TEXT ("remove")));
 722     }
 723 }
 724
 725 // Tests forward and reverse iteration after deletions in both trees.
 726
 727 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void
 728 ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_post_deletion_iteration (void)
 729 {
 730   // Reset iterators
 731
 732   stable_fwd_iter_ = stable_tree_.begin ();
 733   stable_rev_iter_ = stable_tree_.rbegin ();
 734   deprecated_fwd_iter_ = deprecated_tree_.begin ();
 735   deprecated_rev_iter_ = deprecated_tree_.rbegin ();
 736
 737   // Iterate over each of the trees, making sure their entries are
 738   // still in the same relative order (i.e., the integers and strings
 739   // represent the same values at each respective position in the
 740   // tree).
 741   for (int i = 1; i < entry_count_; i += 2)
 742     {
 743       INT_ID item;
 744
 745       item = (*stable_fwd_iter_).item ();
 746       if (item != item_array_ [i])
 747         ACE_ERROR ((LM_ERROR,
 748                     ACE_TEXT ("Stable fwd iter, pass %d %p\n"),
 749                     i,
 750                     ACE_TEXT ("failure")));
 751
 752       item = (*stable_rev_iter_).item ();
 753       if (item != item_array_ [entry_count_ - i])
 754         ACE_ERROR ((LM_ERROR,
 755                     ACE_TEXT ("Stable rev iter, pass %d %p\n"),
 756                     i,
 757                     ACE_TEXT ("failure")));
 758
 759       item = (*deprecated_fwd_iter_).item ();
 760       if (item != item_array_ [i])
 761         ACE_ERROR ((LM_ERROR,
 762                     ACE_TEXT ("Deprecated fwd iter, pass %d %p\n"),
 763                     i,
 764                     ACE_TEXT ("failure")));
 765
 766       item = (*deprecated_rev_iter_).item ();
 767       if (item != item_array_ [entry_count_ - i])
 768         ACE_ERROR ((LM_ERROR,
 769                     ACE_TEXT ("Deprecated rev iter, pass %d %p\n"),
 770                     i,
 771                     ACE_TEXT ("failure")));
 772
 773       // Advance each iterator via postfix increment.
 774       stable_fwd_iter_++;
 775       stable_rev_iter_++;
 776       deprecated_fwd_iter_++;
 777       deprecated_rev_iter_++;
 778     }
 779
 780   // Make sure each item in each tree has been visited a second time.
 781   if (stable_fwd_iter_.done () != 1)
 782     ACE_ERROR ((LM_ERROR,
 783                 ACE_TEXT ("Stable fwd iter not done but should be\n")));
 784   if (stable_rev_iter_.done () != 1)
 785     ACE_ERROR ((LM_ERROR,
 786                 ACE_TEXT ("Stable rev iter not done but should be\n")));
 787   if (deprecated_fwd_iter_.done () != 1)
 788     ACE_ERROR ((LM_ERROR,
 789                 ACE_TEXT ("Deprecated fwd iter not done but should be\n")));
 790   if (deprecated_rev_iter_.done () != 1)
 791     ACE_ERROR ((LM_ERROR,
 792                 ACE_TEXT ("Deprecated rev iter not done but should be\n")));
 793 }
 794
 795