diff options
author | cdgill <cdgill@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 2000-12-30 21:24:39 +0000 |
---|---|---|
committer | cdgill <cdgill@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 2000-12-30 21:24:39 +0000 |
commit | fba08b4b1dbd9c680c0f682a4828e275a5e55a6c (patch) | |
tree | 1d376aaa7c63e708b5bc1f87c38ec07061015342 /tests/RB_Tree_Test.cpp | |
parent | d8e89071ddff39aedca5ac3203c2024dd6dfc906 (diff) | |
download | ATCD-fba08b4b1dbd9c680c0f682a4828e275a5e55a6c.tar.gz |
fixed bug in delete fixup function, added stress test from Klaus Wolf
Diffstat (limited to 'tests/RB_Tree_Test.cpp')
-rw-r--r-- | tests/RB_Tree_Test.cpp | 291 |
1 files changed, 291 insertions, 0 deletions
diff --git a/tests/RB_Tree_Test.cpp b/tests/RB_Tree_Test.cpp index 06d810ad26e..df5b182942e 100644 --- a/tests/RB_Tree_Test.cpp +++ b/tests/RB_Tree_Test.cpp @@ -28,6 +28,8 @@ #include "test_config.h" /* Include first to enable ACE_ASSERT. */ #include "ace/RB_Tree.h" +#include "ace/SString.h" + #include "RB_Tree_Test.h" ACE_RCSID(tests, RB_Tree_Test, "$Id$") @@ -62,6 +64,7 @@ static int int_str_index [] = {7, 6, 5, 4, 3, 2, 1, 0}; // RL inorder static int str_int_index [] = {4, 6, 2, 7, 5, 3, 1, 0}; // RL BFS static int str_str_index [] = {4, 2, 1, 0, 3, 6, 5, 7}; // LR preorder + int main (int, ACE_TCHAR *[]) { @@ -93,6 +96,282 @@ main (int, ACE_TCHAR *[]) str_int_test.run_test (); str_str_test.run_test (); +// ======= Stress Test contributed by Klaus H. Wolf <hw@cyland.com> ================== + + ACE_RB_Tree<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex> tree; + + tree.bind (ACE_CString ("51"), 1); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("13"), 2); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("36"), 3); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("15"), 4); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("22"), 5); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("25"), 6); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("42"), 7); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("48"), 8); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("03"), 9); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("56"), 10); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("28"), 11); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("55"), 12); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("21"), 13); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("62"), 14); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("18"), 15); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("20"), 16); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("26"), 17); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("29"), 18); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("50"), 19); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("05"), 20); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("59"), 21); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("65"), 22); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("66"), 23); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("45"), 24); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("34"), 25); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("27"), 26); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("40"), 27); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("30"), 28); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("64"), 29); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("11"), 30); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("16"), 31); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("47"), 32); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("10"), 33); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("37"), 34); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("09"), 35); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("54"), 36); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("23"), 37); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("44"), 38); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("19"), 39); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("00"), 40); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("04"), 41); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("63"), 42); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("08"), 43); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("39"), 44); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("31"), 45); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("02"), 46); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("33"), 47); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("60"), 48); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("61"), 49); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("57"), 50); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("43"), 51); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("46"), 52); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("38"), 53); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("01"), 54); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("12"), 55); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("24"), 56); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("52"), 57); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("07"), 58); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("14"), 59); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("06"), 60); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("58"), 61); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("49"), 62); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("17"), 63); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("53"), 64); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("32"), 65); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("35"), 66); + ACE_ASSERT (tree.test_invariant () == 0); + tree.bind (ACE_CString ("41"), 67); + ACE_ASSERT (tree.test_invariant () == 0); + + tree.unbind (ACE_CString ("51")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("13")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("36")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("15")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("22")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("25")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("42")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("48")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("03")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("56")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("28")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("55")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("21")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("62")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("18")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("20")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("26")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("29")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("50")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("05")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("59")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("65")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("66")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("45")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("34")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("27")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("40")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("30")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("64")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("11")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("16")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("47")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("10")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("37")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("09")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("54")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("23")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("44")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("19")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("00")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("04")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("63")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("08")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("39")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("31")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("02")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("33")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("60")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("61")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("57")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("43")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("46")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("38")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("01")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("12")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("24")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("52")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("07")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("14")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("06")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("58")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("49")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("17")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("53")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("32")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("35")); + ACE_ASSERT (tree.test_invariant () == 0); + tree.unbind (ACE_CString ("41")); + ACE_ASSERT (tree.test_invariant () == 0); + +// ======== End Stress Test =================== + ACE_END_TEST; return 0; } @@ -280,6 +559,11 @@ ACE_RB_Tree_Test<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_post_deletion_ite #if defined (ACE_HAS_EXPLICIT_TEMPLATE_INSTANTIATION) +template class ACE_RB_Tree<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex>; +template class ACE_RB_Tree_Node<ACE_CString, int>; +template class ACE_RB_Tree_Iterator_Base<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex>; +template class ACE_RB_Tree_Iterator<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex>; +template class ACE_RB_Tree_Reverse_Iterator<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex>; template class ACE_RB_Tree_Test<int, int, ACE_Less_Than<int>, ACE_Null_Mutex>; template class ACE_RB_Tree<int, int, ACE_Less_Than<int>, ACE_Null_Mutex>; template class ACE_RB_Tree_Node<int, int>; @@ -305,9 +589,15 @@ template class ACE_RB_Tree_Iterator_Base<const char *, const char *, ACE_Less_Th template class ACE_RB_Tree_Iterator<const char *, const char *, ACE_Less_Than<const char *>, ACE_Null_Mutex>; template class ACE_RB_Tree_Reverse_Iterator<const char *, const char *, ACE_Less_Than<const char *>, ACE_Null_Mutex>; template class ACE_Less_Than<int>; +template class ACE_Less_Than<ACE_CString>; #elif defined (ACE_HAS_TEMPLATE_INSTANTIATION_PRAGMA) +#pragma instantiate ACE_RB_Tree<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex> +#pragma instantiate ACE_RB_Tree_Node<ACE_CString, int> +#pragma instantiate ACE_RB_Tree_Iterator_Base<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex> +#pragma instantiate ACE_RB_Tree_Iterator<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex> +#pragma instantiate ACE_RB_Tree_Reverse_Iterator<ACE_CString, int, ACE_Less_Than<ACE_CString>, ACE_Null_Mutex> #pragma instantiate ACE_RB_Tree_Test<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> #pragma instantiate ACE_RB_Tree<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> #pragma instantiate ACE_RB_Tree_Node<int, int> @@ -333,5 +623,6 @@ template class ACE_Less_Than<int>; #pragma instantiate ACE_RB_Tree_Iterator<const char *, const char *, ACE_Less_Than<const char *>, ACE_Null_Mutex> #pragma instantiate ACE_RB_Tree_Reverse_Iterator<const char *, const char *, ACE_Less_Than<const char *>, ACE_Null_Mutex> #pragma instantiate ACE_Less_Than<int> +#pragma instantiate ACE_Less_Than<ACE_CString> #endif /* ACE_HAS_EXPLICIT_TEMPLATE_INSTANTIATION */ |