From 5f79570e0dc3b68bc09e784c27f46ec3958abfe7 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 20 Apr 2016 23:10:54 +0300 Subject: [PATCH] Added unit tests for BronsonAVLTree --- projects/Win/vc14/cds.sln | 8 +- projects/Win/vc14/gtest-tree.vcxproj | 6 + projects/Win/vc14/gtest-tree.vcxproj.filters | 21 + test/unit/tree/CMakeLists.txt | 5 + .../tree/bronson_avltree_map_ptr_rcu_gpb.cpp | 41 + .../tree/bronson_avltree_map_ptr_rcu_gpi.cpp | 41 + .../tree/bronson_avltree_map_ptr_rcu_gpt.cpp | 41 + .../tree/bronson_avltree_map_ptr_rcu_shb.cpp | 45 ++ .../tree/bronson_avltree_map_ptr_rcu_sht.cpp | 45 ++ test/unit/tree/test_bronson_avltree_map_ptr.h | 727 ++++++++++++++++++ 10 files changed, 979 insertions(+), 1 deletion(-) create mode 100644 test/unit/tree/bronson_avltree_map_ptr_rcu_gpb.cpp create mode 100644 test/unit/tree/bronson_avltree_map_ptr_rcu_gpi.cpp create mode 100644 test/unit/tree/bronson_avltree_map_ptr_rcu_gpt.cpp create mode 100644 test/unit/tree/bronson_avltree_map_ptr_rcu_shb.cpp create mode 100644 test/unit/tree/bronson_avltree_map_ptr_rcu_sht.cpp create mode 100644 test/unit/tree/test_bronson_avltree_map_ptr.h diff --git a/projects/Win/vc14/cds.sln b/projects/Win/vc14/cds.sln index 20e21be1..c670b5a2 100644 --- a/projects/Win/vc14/cds.sln +++ b/projects/Win/vc14/cds.sln @@ -1,6 +1,6 @@ Microsoft Visual Studio Solution File, Format Version 12.00 # Visual Studio 14 -VisualStudioVersion = 14.0.24720.0 +VisualStudioVersion = 14.0.25123.0 MinimumVisualStudioVersion = 10.0.40219.1 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "cds", "cds.vcxproj", "{408FE9BC-44F0-4E6A-89FA-D6F952584239}" EndProject @@ -186,6 +186,9 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-queue", "stress-queu EndProjectSection EndProject Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-pqueue", "stress-pqueue.vcxproj", "{51AC349E-B365-4FCF-8778-17A1534E4584}" + ProjectSection(ProjectDependencies) = postProject + {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239} + EndProjectSection EndProject Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "gtest-set", "gtest-set.vcxproj", "{A589D3F1-A749-4268-ADEC-D0CE13D1E359}" ProjectSection(ProjectDependencies) = postProject @@ -213,6 +216,9 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "gtest-striped-map", "gtest- EndProjectSection EndProject Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "gtest-tree", "gtest-tree.vcxproj", "{2ABD6A2E-BEA7-4C8C-982B-A609F83D2DCB}" + ProjectSection(ProjectDependencies) = postProject + {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239} + EndProjectSection EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution diff --git a/projects/Win/vc14/gtest-tree.vcxproj b/projects/Win/vc14/gtest-tree.vcxproj index 74b78383..d2bba82b 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj +++ b/projects/Win/vc14/gtest-tree.vcxproj @@ -28,6 +28,11 @@ + + + + + @@ -115,6 +120,7 @@ + diff --git a/projects/Win/vc14/gtest-tree.vcxproj.filters b/projects/Win/vc14/gtest-tree.vcxproj.filters index 04681082..c9f2b83e 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj.filters +++ b/projects/Win/vc14/gtest-tree.vcxproj.filters @@ -22,6 +22,9 @@ {5e8e3c4d-563e-41fd-91ed-52f61f4b7d24} + + {431d0150-603d-4108-810d-de9ac3be3534} + @@ -93,6 +96,21 @@ Source Files\EllenBinTreeMap + + Source Files\BronsonAVLTree_ptr + + + Source Files\BronsonAVLTree_ptr + + + Source Files\BronsonAVLTree_ptr + + + Source Files\BronsonAVLTree_ptr + + + Source Files\BronsonAVLTree_ptr + @@ -137,5 +155,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 c1c066d9..aa7c0aaf 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_ptr_rcu_gpb.cpp + bronson_avltree_map_ptr_rcu_gpi.cpp + bronson_avltree_map_ptr_rcu_gpt.cpp + bronson_avltree_map_ptr_rcu_shb.cpp + bronson_avltree_map_ptr_rcu_sht.cpp ellen_bintree_update_desc_pool.cpp ellen_bintree_map_hp.cpp ellen_bintree_map_dhp.cpp diff --git a/test/unit/tree/bronson_avltree_map_ptr_rcu_gpb.cpp b/test/unit/tree/bronson_avltree_map_ptr_rcu_gpb.cpp new file mode 100644 index 00000000..1146fac4 --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_ptr_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_ptr.h" + +namespace { + + typedef cds::urcu::general_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPB, BronsonAVLTreeMapPtr, rcu_implementation ); diff --git a/test/unit/tree/bronson_avltree_map_ptr_rcu_gpi.cpp b/test/unit/tree/bronson_avltree_map_ptr_rcu_gpi.cpp new file mode 100644 index 00000000..a075a63b --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_ptr_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_ptr.h" + +namespace { + + typedef cds::urcu::general_instant<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPI, BronsonAVLTreeMapPtr, rcu_implementation ); diff --git a/test/unit/tree/bronson_avltree_map_ptr_rcu_gpt.cpp b/test/unit/tree/bronson_avltree_map_ptr_rcu_gpt.cpp new file mode 100644 index 00000000..deefc7ff --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_ptr_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_ptr.h" + +namespace { + + typedef cds::urcu::general_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPT, BronsonAVLTreeMapPtr, rcu_implementation ); diff --git a/test/unit/tree/bronson_avltree_map_ptr_rcu_shb.cpp b/test/unit/tree/bronson_avltree_map_ptr_rcu_shb.cpp new file mode 100644 index 00000000..3aa15698 --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_ptr_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_ptr.h" + +namespace { + + typedef cds::urcu::signal_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHB, BronsonAVLTreeMapPtr, rcu_implementation ); + +#endif diff --git a/test/unit/tree/bronson_avltree_map_ptr_rcu_sht.cpp b/test/unit/tree/bronson_avltree_map_ptr_rcu_sht.cpp new file mode 100644 index 00000000..5c8a1c3d --- /dev/null +++ b/test/unit/tree/bronson_avltree_map_ptr_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_ptr.h" + +namespace { + + typedef cds::urcu::signal_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHT, BronsonAVLTreeMapPtr, rcu_implementation ); + +#endif diff --git a/test/unit/tree/test_bronson_avltree_map_ptr.h b/test/unit/tree/test_bronson_avltree_map_ptr.h new file mode 100644 index 00000000..6a302d46 --- /dev/null +++ b/test/unit/tree/test_bronson_avltree_map_ptr.h @@ -0,0 +1,727 @@ +/* + 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_PTR_H +#define CDSUNIT_TREE_TEST_BRONSON_AVLTREE_MAP_PTR_H + +#include "test_tree_map_data.h" +#include +#include +#include + +namespace { + + namespace cc = cds::container; + + class bronson_avltree_map_ptr: public cds_test::tree_map_fixture + { + public: + static size_t const kSize = 1000; + + struct value_type: public cds_test::tree_map_fixture::value_type + { + typedef cds_test::tree_map_fixture::value_type base_class; + + size_t nDisposeCount = 0; + + // Inheriting constructors + using base_class::value_type; + }; + + struct mock_disposer + { + void operator()( value_type * val ) const + { + ++val->nDisposeCount; + } + }; + + protected: + template + void test( Map& m ) + { + // Precondition: map is empty + // Postcondition: map is empty + + ASSERT_TRUE( m.empty()); + ASSERT_CONTAINER_SIZE( m, 0 ); + + typedef typename Map::key_type key_type; + typedef typename std::remove_pointer< typename Map::mapped_type >::type mapped_type; + 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& 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&, mapped_type& ) { + ASSERT_TRUE( false ); + } )); + ASSERT_FALSE( m.find( i.nKey, []( key_type const&, mapped_type& ) { + EXPECT_TRUE( false ); + } )); + ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const&, mapped_type& ) { + EXPECT_TRUE( false ); + } )); + + std::pair< bool, bool > updResult; + + switch ( i.nKey % 6 ) { + case 0: + ASSERT_TRUE( m.insert( i, &val )); + ASSERT_FALSE( m.insert( i, &val )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + break; + case 1: + ASSERT_TRUE( m.insert( i.nKey, &val )); + ASSERT_FALSE( m.insert( i.nKey, &val )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_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 ), &val )); + ASSERT_FALSE( m.insert( std::to_string( i.nKey ), &val )); + ASSERT_TRUE( m.find( i.nKey, []( key_type const& key, mapped_type& val ) { + val.nVal = key.nKey; + val.strVal = std::to_string( key.nKey ); + } )); + break; + case 3: + updResult = m.update( i.nKey, &val, false ); + ASSERT_FALSE( updResult.first ); + ASSERT_FALSE( updResult.second ); + + updResult = m.update( i.nKey, &val ); + ASSERT_TRUE( updResult.first ); + ASSERT_TRUE( updResult.second ); + + updResult = m.update( i.nKey, &val ); + ASSERT_TRUE( updResult.first ); + ASSERT_FALSE( updResult.second ); + break; + case 4: + updResult = m.update( i, &val, false ); + ASSERT_FALSE( updResult.first ); + ASSERT_FALSE( updResult.second ); + + updResult = m.update( i, &val ); + ASSERT_TRUE( updResult.first ); + ASSERT_TRUE( updResult.second ); + + updResult = m.update( i, &val ); + ASSERT_TRUE( updResult.first ); + ASSERT_FALSE( updResult.second ); + break; + case 5: + updResult = m.update( val.strVal, &val, false ); + ASSERT_FALSE( updResult.first ); + ASSERT_FALSE( updResult.second ); + + updResult = m.update( val.strVal, &val ); + ASSERT_TRUE( updResult.first ); + ASSERT_TRUE( updResult.second ); + + updResult = m.update( val.strVal, &val ); + ASSERT_TRUE( updResult.first ); + ASSERT_FALSE( updResult.second ); + 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, mapped_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, mapped_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, mapped_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, mapped_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, mapped_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, mapped_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, mapped_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*/, mapped_type& /*val*/ ) { + EXPECT_TRUE( false ); + })); + break; + case 5: + ASSERT_TRUE( m.erase( i.nKey, []( key_type const& key, mapped_type& v ) { + EXPECT_EQ( key.nKey, v.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), v.strVal ); + })); + ASSERT_FALSE( m.erase( i.nKey, []( key_type const&, mapped_type& ) { + EXPECT_TRUE( false ); + })); + break; + case 6: + ASSERT_TRUE( m.erase( val.strVal, []( key_type const& key, mapped_type& v ) { + EXPECT_EQ( key.nKey, v.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), v.strVal ); + })); + ASSERT_FALSE( m.erase( val.strVal, []( key_type const&, mapped_type& ) { + EXPECT_TRUE( false ); + })); + break; + case 7: + ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& key, mapped_type& v ) { + EXPECT_EQ( key.nKey, v.nVal ); + EXPECT_EQ( std::to_string( key.nKey ), v.strVal ); + })); + ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( key_type const& key, mapped_type& v ) { + 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*/, mapped_type& /*val*/ ) { + ASSERT_TRUE( false ); + } )); + ASSERT_FALSE( m.find( i.nKey, []( key_type const& /*key*/, mapped_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( key_type const& /*key*/, mapped_type& /*val*/ ) { + EXPECT_TRUE( false ); + } )); + } + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + Map::gc::force_dispose(); + for ( auto const& item: arrVals ) { + EXPECT_EQ( item.nDisposeCount, 1 ); + } + + // clear + for ( auto const& i : arrKeys ) { + value_type& val( arrVals.at( i.nKey ) ); + ASSERT_TRUE( m.insert( i, &val )); + } + + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + + m.clear(); + + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + + Map::gc::force_dispose(); + for ( auto const& item : arrVals ) { + EXPECT_EQ( item.nDisposeCount, 2 ); + } + + ASSERT_TRUE( m.check_consistency() ); + + + // RCU-specific test related to exempt_ptr + typedef typename Map::exempt_ptr exempt_ptr; + exempt_ptr xp; + + // extract + for ( auto const& i : arrKeys ) { + value_type& val( arrVals.at( i.nKey ) ); + ASSERT_TRUE( m.insert( i, &val ) ); + } + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + + for ( auto const& i : arrKeys ) { + value_type const& val = arrVals.at( i.nKey ); + + EXPECT_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 ); + + EXPECT_FALSE( m.contains( i.nKey ) ); + } + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + xp.release(); + + Map::gc::force_dispose(); + for ( auto const& item : arrVals ) { + EXPECT_EQ( item.nDisposeCount, 3 ); + } + + // extract_min + shuffle( arrKeys.begin(), arrKeys.end() ); + for ( auto const& i : arrKeys ) { + value_type& val( arrVals.at( i.nKey ) ); + ASSERT_TRUE( m.insert( i, &val ) ); + } + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + ASSERT_TRUE( m.check_consistency() ); + + int nPrevKey = -1; + size_t nCount = 0; + while ( !m.empty() ) { + switch ( nCount % 3 ) { + case 0: + xp = m.extract_min(); + break; + case 1: + xp = m.extract_min( [nPrevKey]( key_type const& k ) { + EXPECT_EQ( k.nKey, nPrevKey + 1 ); + } ); + break; + case 2: + { + key_type key; + xp = m.extract_min_key( key ); + EXPECT_EQ( key.nKey, nPrevKey + 1 ); + } + break; + } + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->nVal, nPrevKey + 1 ); + + nPrevKey = xp->nVal; + ++nCount; + } + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + EXPECT_EQ( nCount, kkSize ); + xp.release(); + + Map::gc::force_dispose(); + for ( auto const& item : arrVals ) { + EXPECT_EQ( item.nDisposeCount, 4 ); + } + + // extract_max + shuffle( arrKeys.begin(), arrKeys.end() ); + for ( auto const& i : arrKeys ) { + value_type& val( arrVals.at( i.nKey ) ); + ASSERT_TRUE( m.insert( i, &val ) ); + } + ASSERT_FALSE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, kkSize ); + ASSERT_TRUE( m.check_consistency() ); + + nPrevKey = static_cast(kkSize); + nCount = 0; + while ( !m.empty() ) { + switch ( nCount % 3 ) { + case 0: + xp = m.extract_max(); + break; + case 1: + xp = m.extract_max( [nPrevKey]( key_type const& k ) { + EXPECT_EQ( k.nKey, nPrevKey - 1 ); + } ); + break; + case 2: + { + key_type key; + xp = m.extract_max_key( key ); + EXPECT_EQ( key.nKey, nPrevKey - 1 ); + } + break; + } + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->nVal, nPrevKey - 1 ); + + nPrevKey = xp->nVal; + ++nCount; + } + ASSERT_TRUE( m.empty() ); + ASSERT_CONTAINER_SIZE( m, 0 ); + EXPECT_EQ( nCount, kkSize ); + xp.release(); + + Map::gc::force_dispose(); + for ( auto const& item : arrVals ) { + EXPECT_EQ( item.nDisposeCount, 5 ); + } + + // extract min/max on empty map + xp = m.extract_min(); + EXPECT_TRUE( !xp ); + xp = m.extract_min( []( key_type const& ) { EXPECT_FALSE( true ); } ); + EXPECT_TRUE( !xp ); + xp = m.extract_max(); + EXPECT_TRUE( !xp ); + xp = m.extract_max( []( key_type const& ) { EXPECT_FALSE( true ); } ); + EXPECT_TRUE( !xp ); + { + key_type key; + key.nKey = -100; + xp = m.extract_min_key( key ); + EXPECT_TRUE( !xp ); + EXPECT_EQ( key.nKey, -100 ); + xp = m.extract_max_key( key ); + EXPECT_TRUE( !xp ); + EXPECT_EQ( key.nKey, -100 ); + } + + // checking empty map + ASSERT_TRUE( m.check_consistency() ); + } + }; + + template + class BronsonAVLTreeMapPtr: public bronson_avltree_map_ptr + { + typedef bronson_avltree_map_ptr 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(); + } + }; + + struct bronson_traits: public cds::container::bronson_avltree::traits + { + typedef bronson_avltree_map_ptr::mock_disposer disposer; + }; + + TYPED_TEST_CASE_P( BronsonAVLTreeMapPtr ); + + TYPED_TEST_P( BronsonAVLTreeMapPtr, 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 > + ,cds::intrusive::opt::disposer< bronson_avltree_map_ptr::mock_disposer > + >::type + > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMapPtr, 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 > + , cds::intrusive::opt::disposer< bronson_avltree_map_ptr::mock_disposer > + >::type + > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMapPtr, 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 > + , cds::intrusive::opt::disposer< bronson_avltree_map_ptr::mock_disposer > + >::type + > map_type; + + map_type m; + this->test( m ); + } + + TYPED_TEST_P( BronsonAVLTreeMapPtr, 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 bronson_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( BronsonAVLTreeMapPtr, 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 bronson_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 bronson_traits + { + static bool const relaxed_insert = true; + }; + + TYPED_TEST_P( BronsonAVLTreeMapPtr, 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( BronsonAVLTreeMapPtr, 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 bronson_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( BronsonAVLTreeMapPtr, 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 bronson_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( BronsonAVLTreeMapPtr, 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 bronson_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( BronsonAVLTreeMapPtr, 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 bronson_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( BronsonAVLTreeMapPtr, 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 bronson_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( BronsonAVLTreeMapPtr, + 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_PTR_H -- 2.34.1