From 4ebd5e5ecd8f59c9800c3191750328aa54f9d60c Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 21 Apr 2016 23:31:04 +0300 Subject: [PATCH] Migrated BronsonAVLTreeMap unit tests to gtest --- projects/Win/vc14/gtest-tree.vcxproj | 12 + projects/Win/vc14/gtest-tree.vcxproj.filters | 30 +- test/unit/tree/CMakeLists.txt | 5 + .../unit/tree/bronson_avltree_map_rcu_gpb.cpp | 41 + .../unit/tree/bronson_avltree_map_rcu_gpi.cpp | 41 + .../unit/tree/bronson_avltree_map_rcu_gpt.cpp | 41 + .../unit/tree/bronson_avltree_map_rcu_shb.cpp | 45 ++ .../unit/tree/bronson_avltree_map_rcu_sht.cpp | 45 ++ test/unit/tree/test_bronson_avltree_map.h | 752 ++++++++++++++++++ 9 files changed, 1006 insertions(+), 6 deletions(-) create mode 100644 test/unit/tree/bronson_avltree_map_rcu_gpb.cpp create mode 100644 test/unit/tree/bronson_avltree_map_rcu_gpi.cpp create mode 100644 test/unit/tree/bronson_avltree_map_rcu_gpt.cpp create mode 100644 test/unit/tree/bronson_avltree_map_rcu_shb.cpp create mode 100644 test/unit/tree/bronson_avltree_map_rcu_sht.cpp create mode 100644 test/unit/tree/test_bronson_avltree_map.h diff --git a/projects/Win/vc14/gtest-tree.vcxproj b/projects/Win/vc14/gtest-tree.vcxproj index d2bba82b..89aa7224 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj +++ b/projects/Win/vc14/gtest-tree.vcxproj @@ -33,6 +33,11 @@ + + + + + @@ -120,6 +125,7 @@ + @@ -246,6 +252,7 @@ Disabled _ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) Console @@ -261,6 +268,7 @@ Disabled _ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) Console @@ -276,6 +284,7 @@ Disabled _ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) Console @@ -291,6 +300,7 @@ Disabled _ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) Console @@ -308,6 +318,7 @@ true _ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) Console @@ -327,6 +338,7 @@ true _ENABLE_ATOMIC_ALIGNMENT_FIX;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) Console diff --git a/projects/Win/vc14/gtest-tree.vcxproj.filters b/projects/Win/vc14/gtest-tree.vcxproj.filters index c9f2b83e..fabcd1c4 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj.filters +++ b/projects/Win/vc14/gtest-tree.vcxproj.filters @@ -22,7 +22,7 @@ {5e8e3c4d-563e-41fd-91ed-52f61f4b7d24} - + {431d0150-603d-4108-810d-de9ac3be3534} @@ -97,19 +97,34 @@ Source Files\EllenBinTreeMap - Source Files\BronsonAVLTree_ptr + Source Files\BronsonAVLTree - Source Files\BronsonAVLTree_ptr + Source Files\BronsonAVLTree - Source Files\BronsonAVLTree_ptr + Source Files\BronsonAVLTree - Source Files\BronsonAVLTree_ptr + Source Files\BronsonAVLTree - Source Files\BronsonAVLTree_ptr + Source Files\BronsonAVLTree + + + Source Files\BronsonAVLTree + + + Source Files\BronsonAVLTree + + + Source Files\BronsonAVLTree + + + Source Files\BronsonAVLTree + + + Source Files\BronsonAVLTree @@ -158,5 +173,8 @@ Header Files + + Header Files + \ No newline at end of file diff --git a/test/unit/tree/CMakeLists.txt b/test/unit/tree/CMakeLists.txt index aa7c0aaf..c332e770 100644 --- a/test/unit/tree/CMakeLists.txt +++ b/test/unit/tree/CMakeLists.txt @@ -4,6 +4,11 @@ set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-invalid-offsetof") set(CDSGTEST_TREE_SOURCES ../main.cpp + bronson_avltree_map_rcu_gpb.cpp + bronson_avltree_map_rcu_gpi.cpp + bronson_avltree_map_rcu_gpt.cpp + bronson_avltree_map_rcu_shb.cpp + bronson_avltree_map_rcu_sht.cpp bronson_avltree_map_ptr_rcu_gpb.cpp bronson_avltree_map_ptr_rcu_gpi.cpp bronson_avltree_map_ptr_rcu_gpt.cpp diff --git a/test/unit/tree/bronson_avltree_map_rcu_gpb.cpp b/test/unit/tree/bronson_avltree_map_rcu_gpb.cpp new file mode 100644 index 00000000..c0e4e20b --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_rcu_gpb.cpp @@ -0,0 +1,41 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include + +#include "test_bronson_avltree_map.h" + +namespace { + + typedef cds::urcu::general_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPB, BronsonAVLTreeMap, rcu_implementation ); diff --git a/test/unit/tree/bronson_avltree_map_rcu_gpi.cpp b/test/unit/tree/bronson_avltree_map_rcu_gpi.cpp new file mode 100644 index 00000000..d855e1a6 --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_rcu_gpi.cpp @@ -0,0 +1,41 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include + +#include "test_bronson_avltree_map.h" + +namespace { + + typedef cds::urcu::general_instant<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPI, BronsonAVLTreeMap, rcu_implementation ); diff --git a/test/unit/tree/bronson_avltree_map_rcu_gpt.cpp b/test/unit/tree/bronson_avltree_map_rcu_gpt.cpp new file mode 100644 index 00000000..373460c8 --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_rcu_gpt.cpp @@ -0,0 +1,41 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include + +#include "test_bronson_avltree_map.h" + +namespace { + + typedef cds::urcu::general_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPT, BronsonAVLTreeMap, rcu_implementation ); diff --git a/test/unit/tree/bronson_avltree_map_rcu_shb.cpp b/test/unit/tree/bronson_avltree_map_rcu_shb.cpp new file mode 100644 index 00000000..f73f505f --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_rcu_shb.cpp @@ -0,0 +1,45 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include + +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + +#include "test_bronson_avltree_map.h" + +namespace { + + typedef cds::urcu::signal_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHB, BronsonAVLTreeMap, rcu_implementation ); + +#endif diff --git a/test/unit/tree/bronson_avltree_map_rcu_sht.cpp b/test/unit/tree/bronson_avltree_map_rcu_sht.cpp new file mode 100644 index 00000000..4900cc12 --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_rcu_sht.cpp @@ -0,0 +1,45 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include + +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + +#include "test_bronson_avltree_map.h" + +namespace { + + typedef cds::urcu::signal_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHT, BronsonAVLTreeMap, rcu_implementation ); + +#endif diff --git a/test/unit/tree/test_bronson_avltree_map.h b/test/unit/tree/test_bronson_avltree_map.h new file mode 100644 index 00000000..46ebc838 --- /dev/null +++ b/test/unit/tree/test_bronson_avltree_map.h @@ -0,0 +1,752 @@ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_H +#define CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_H + +#include "test_tree_map_data.h" +#include +#include +#include + +namespace { + + namespace cc = cds::container; + + class bronson_avltree_map: public cds_test::tree_map_fixture + { + public: + static size_t const kSize = 1000; + + protected: + template + void test( Map& m ) + { + // Precondition: map is empty + // Postcondition: map is empty + + ASSERT_TRUE( m.empty()); + ASSERT_CONTAINER_SIZE( m, 0 ); + + size_t const kkSize = kSize; + + std::vector arrKeys; + for ( int i = 0; i < static_cast(kkSize); ++i ) + arrKeys.push_back( key_type( i )); + shuffle( arrKeys.begin(), arrKeys.end()); + + std::vector< value_type > arrVals; + for ( size_t i = 0; i < kkSize; ++i ) { + value_type val; + val.nVal = static_cast( i ); + val.strVal = std::to_string( i ); + arrVals.push_back( val ); + } + + // insert/find + for ( auto const& i : arrKeys ) { + value_type const& val( arrVals.at( i.nKey )); + + ASSERT_FALSE( m.contains( i.nKey )); + ASSERT_FALSE( m.contains( i )); + ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less())); + ASSERT_FALSE( m.find( i, []( key_type const&, value_type& ) { + ASSERT_TRUE( false ); + } )); + ASSERT_FALSE( m.find( i.nKey, []( key_type const&, value_type& ) { + EXPECT_TRUE( false ); + } )); + ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const&, value_type& ) { + EXPECT_TRUE( false ); + } )); + + std::pair< bool, bool > updResult; + + switch ( i.nKey % 16 ) { + case 0: + ASSERT_TRUE( m.insert( i )); + ASSERT_FALSE( m.insert( i )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + break; + case 1: + ASSERT_TRUE( m.insert( i.nKey )); + ASSERT_FALSE( m.insert( i.nKey )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + break; + case 2: + ASSERT_TRUE( m.insert( std::to_string( i.nKey ))); + ASSERT_FALSE( m.insert( std::to_string( i.nKey ))); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + break; + case 3: + ASSERT_TRUE( m.insert( i, val )); + ASSERT_FALSE( m.insert( i, val )); + break; + case 4: + ASSERT_TRUE( m.insert( i.nKey, val.strVal )); + ASSERT_FALSE( m.insert( i.nKey, val.strVal )); + break; + case 5: + ASSERT_TRUE( m.insert( val.strVal, i.nKey )); + ASSERT_FALSE( m.insert( val.strVal, i.nKey )); + break; + case 6: + ASSERT_TRUE( m.insert_with( i, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + ASSERT_FALSE( m.insert_with( i, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + break; + case 7: + ASSERT_TRUE( m.insert_with( i.nKey, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + ASSERT_FALSE( m.insert_with( i.nKey, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + break; + case 8: + ASSERT_TRUE( m.insert_with( val.strVal, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + ASSERT_FALSE( m.insert_with( val.strVal, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + break; + case 9: + updResult = m.update( i.nKey, []( bool, key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + }, false ); + ASSERT_FALSE( updResult.first ); + ASSERT_FALSE( updResult.second ); + + updResult = m.update( i.nKey, []( bool bNew, key_type const& key, value_type& val ) { + EXPECT_TRUE( bNew ); + val.nVal = key.nKey; + }); + ASSERT_TRUE( updResult.first ); + ASSERT_TRUE( updResult.second ); + + updResult = m.update( i.nKey, []( bool bNew, key_type const& key, value_type& val ) { + EXPECT_FALSE( bNew ); + EXPECT_EQ( key.nKey, val.nVal ); + val.strVal = std::to_string( val.nVal ); + } ); + ASSERT_TRUE( updResult.first ); + ASSERT_FALSE( updResult.second ); + break; + case 10: + updResult = m.update( i, []( bool, key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + }, false ); + ASSERT_FALSE( updResult.first ); + ASSERT_FALSE( updResult.second ); + + updResult = m.update( i, []( bool bNew, key_type const& key, value_type& val ) { + EXPECT_TRUE( bNew ); + val.nVal = key.nKey; + }); + ASSERT_TRUE( updResult.first ); + ASSERT_TRUE( updResult.second ); + + updResult = m.update( i, []( bool bNew, key_type const& key, value_type& val ) { + EXPECT_FALSE( bNew ); + EXPECT_EQ( key.nKey, val.nVal ); + val.strVal = std::to_string( val.nVal ); + } ); + ASSERT_TRUE( updResult.first ); + ASSERT_FALSE( updResult.second ); + break; + case 11: + updResult = m.update( val.strVal, []( bool, key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + }, false ); + ASSERT_FALSE( updResult.first ); + ASSERT_FALSE( updResult.second ); + + updResult = m.update( val.strVal, []( bool bNew, key_type const& key, value_type& val ) { + EXPECT_TRUE( bNew ); + val.nVal = key.nKey; + }); + ASSERT_TRUE( updResult.first ); + ASSERT_TRUE( updResult.second ); + + updResult = m.update( val.strVal, []( bool bNew, key_type const& key, value_type& val ) { + EXPECT_FALSE( bNew ); + EXPECT_EQ( key.nKey, val.nVal ); + val.strVal = std::to_string( val.nVal ); + } ); + ASSERT_TRUE( updResult.first ); + ASSERT_FALSE( updResult.second ); + break; + case 12: + ASSERT_TRUE( m.emplace( i.nKey )); + ASSERT_FALSE( m.emplace( i.nKey )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + break; + case 13: + ASSERT_TRUE( m.emplace( i, i.nKey )); + ASSERT_FALSE( m.emplace( i, i.nKey )); + break; + case 14: + { + std::string str = val.strVal; + ASSERT_TRUE( m.emplace( i, std::move( str ))); + ASSERT_TRUE( str.empty()); + str = val.strVal; + ASSERT_FALSE( m.emplace( i, std::move( str ))); + ASSERT_TRUE( str.empty()); + } + break; + case 15: + { + std::string str = val.strVal; + ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str ))); + ASSERT_TRUE( str.empty()); + str = val.strVal; + ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str ))); + ASSERT_TRUE( str.empty()); + } + break; + } + + ASSERT_TRUE( m.contains( i.nKey )); + ASSERT_TRUE( m.contains( i )); + ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less())); + ASSERT_TRUE( m.find( i, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + } )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + } )); + ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + } )); + } + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + + ASSERT_TRUE( m.check_consistency()); + + shuffle( arrKeys.begin(), arrKeys.end() ); + + // erase/find + for ( auto const& i : arrKeys ) { + value_type const& val( arrVals.at( i.nKey ) ); + + ASSERT_TRUE( m.contains( i.nKey )); + ASSERT_TRUE( m.contains( val.strVal ) ); + ASSERT_TRUE( m.contains( i )); + ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less())); + ASSERT_TRUE( m.find( i, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + } )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + } )); + ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + } )); + + + switch ( i.nKey % 8 ) { + case 0: + ASSERT_TRUE( m.erase( i )); + ASSERT_FALSE( m.erase( i )); + break; + case 1: + ASSERT_TRUE( m.erase( i.nKey )); + ASSERT_FALSE( m.erase( i.nKey )); + break; + case 2: + ASSERT_TRUE( m.erase( val.strVal )); + ASSERT_FALSE( m.erase( val.strVal )); + break; + case 3: + ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less())); + ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less())); + break; + case 4: + ASSERT_TRUE( m.erase( i, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + })); + ASSERT_FALSE( m.erase( i, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + })); + break; + case 5: + ASSERT_TRUE( m.erase( i.nKey, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + })); + ASSERT_FALSE( m.erase( i.nKey, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + })); + break; + case 6: + ASSERT_TRUE( m.erase( val.strVal, []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + })); + ASSERT_FALSE( m.erase( val.strVal, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + })); + break; + case 7: + ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& key, value_type& val ) { + EXPECT_EQ( key.nKey, val.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), val.strVal ); + })); + ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + })); + break; + } + + ASSERT_FALSE( m.contains( i.nKey )); + ASSERT_FALSE( m.contains( i )); + ASSERT_FALSE( m.contains( val.strVal )); + ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less())); + ASSERT_FALSE( m.find( i, []( key_type const& /*key*/, value_type& /*val*/ ) { + ASSERT_TRUE( false ); + } )); + ASSERT_FALSE( m.find( i.nKey, []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, value_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + } + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + // clear + for ( auto const& i : arrKeys ) + ASSERT_TRUE( m.insert( i )); + + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + + m.clear(); + + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + + for ( auto const& i : arrKeys ) + ASSERT_TRUE( m.insert( i, arrVals[ i.nKey ] )); + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + + typedef typename Map::exempt_ptr exempt_ptr; + + // extract + shuffle( arrKeys.begin(), arrKeys.end() ); + + exempt_ptr xp; + for ( auto const& i : arrKeys ) { + value_type const& val = arrVals.at( i.nKey ); + + ASSERT_TRUE( m.contains( i.nKey ) ); + + switch ( i.nKey % 4 ) { + case 0: + xp = m.extract( i.nKey ); + break; + case 1: + xp = m.extract( i ); + break; + case 2: + xp = m.extract( val.strVal ); + break; + case 3: + xp = m.extract_with( other_item( i.nKey ), other_less() ); + break; + } + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->nVal, i.nKey ); + + ASSERT_FALSE( m.contains( i.nKey ) ); + + switch ( i.nKey % 4 ) { + case 0: + xp = m.extract( i.nKey ); + break; + case 1: + xp = m.extract( i ); + break; + case 2: + xp = m.extract( val.strVal ); + break; + case 3: + xp = m.extract_with( other_item( i.nKey ), other_less() ); + break; + } + EXPECT_TRUE( !xp ); + } + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + + // extract_min + shuffle( arrKeys.begin(), arrKeys.end() ); + for ( auto const& i : arrKeys ) + ASSERT_TRUE( m.insert( i, arrVals[ i.nKey ] )); + + size_t nCount = 0; + int nKey = -1; + while ( !m.empty() ) { + switch ( nCount % 3 ) { + case 0: + xp = m.extract_min(); + break; + case 1: + xp = m.extract_min( [nKey]( key_type const& key ) { + EXPECT_EQ( nKey + 1, key.nKey ); + }); + break; + case 2: + { + key_type key; + xp = m.extract_min_key( key ); + EXPECT_EQ( nKey + 1, key.nKey ); + } + break; + } + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->nVal, nKey + 1 ); + nKey = xp->nVal; + ++nCount; + } + xp = m.extract_min(); + ASSERT_TRUE( !xp ); + EXPECT_EQ( kkSize, nCount ); + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + // extract_max + shuffle( arrKeys.begin(), arrKeys.end() ); + for ( auto const& i : arrKeys ) + ASSERT_TRUE( m.insert( i, arrVals[ i.nKey ] )); + + nKey = kkSize; + nCount = 0; + while ( !m.empty() ) { + switch ( nCount % 3 ) { + case 0: + xp = m.extract_max(); + break; + case 1: + xp = m.extract_max( [nKey]( key_type const& key ) { + EXPECT_EQ( nKey - 1, key.nKey ); + } ); + break; + case 2: + { + key_type key; + xp = m.extract_max_key( key ); + EXPECT_EQ( nKey - 1, key.nKey ); + } + break; + } + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->nVal, nKey - 1 ); + nKey = xp->nVal; + ++nCount; + } + + xp = m.extract_max(); + ASSERT_TRUE( !xp ); + EXPECT_EQ( kkSize, nCount ); + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + } + }; + + + template + class BronsonAVLTreeMap: public bronson_avltree_map + { + typedef bronson_avltree_map base_class; + public: + typedef cds::urcu::gc rcu_type; + + protected: + void SetUp() + { + RCU::Construct(); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + RCU::Destruct(); + } + }; + + TYPED_TEST_CASE_P( BronsonAVLTreeMap ); + + TYPED_TEST_P( BronsonAVLTreeMap, compare ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, + typename cc::bronson_avltree::make_traits< + cds::opt::compare< typename TestFixture::cmp > + >::type + > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, less ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, + typename cc::bronson_avltree::make_traits< + cds::opt::less< typename TestFixture::less > + >::type + > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, cmpmix ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, + typename cc::bronson_avltree::make_traits< + cds::opt::less< typename TestFixture::less > + , cds::opt::compare< typename TestFixture::cmp > + >::type + > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, stat ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::less less; + typedef cc::bronson_avltree::stat<> stat; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, item_counting ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + struct bronson_relaxed_insert_traits: public cc::bronson_avltree::traits + { + static bool const relaxed_insert = true; + }; + + TYPED_TEST_P( BronsonAVLTreeMap, relaxed_insert ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public bronson_relaxed_insert_traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, seq_cst ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, sync_monitor ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::sync::pool_monitor< cds::memory::vyukov_queue_pool< std::mutex >> sync_monitor; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, lazy_sync_monitor ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::sync::pool_monitor< cds::memory::lazy_vyukov_queue_pool< std::mutex >> sync_monitor; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, rcu_check_deadlock ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::sync::pool_monitor< cds::memory::vyukov_queue_pool< std::mutex >> sync_monitor; + typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMap, rcu_no_check_deadlock ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::bronson_avltree::traits + { + typedef typename TestFixture::cmp compare; + typedef cds::atomicity::item_counter item_counter; + typedef cds::sync::pool_monitor< cds::memory::lazy_vyukov_queue_pool< std::mutex >> sync_monitor; + typedef cds::opt::v::rcu_no_check_deadlock rcu_check_deadlock; + }; + + typedef cc::BronsonAVLTreeMap< rcu_type, key_type, value_type, map_traits > map_type; + + map_type m; + this->test( m ); + } + + REGISTER_TYPED_TEST_CASE_P( BronsonAVLTreeMap, + compare, less, cmpmix, stat, item_counting, relaxed_insert, seq_cst, sync_monitor, lazy_sync_monitor, rcu_check_deadlock, rcu_no_check_deadlock + ); + +} // namespace + +#endif // #ifndef CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_H -- 2.34.1