From c6e21c5e4b79756aceceb8f33a6a5847a2d9cc16 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 13 Apr 2016 18:01:26 +0300 Subject: [PATCH] Migrated intrusive EllenBinTree to gtest --- projects/Win/vc14/gtest-tree.vcxproj | 28 ++ projects/Win/vc14/gtest-tree.vcxproj.filters | 21 + test/unit/tree/CMakeLists.txt | 5 + .../tree/intrusive_ellenbintree_rcu_gpb.cpp | 41 ++ .../tree/intrusive_ellenbintree_rcu_gpi.cpp | 41 ++ .../tree/intrusive_ellenbintree_rcu_gpt.cpp | 41 ++ .../tree/intrusive_ellenbintree_rcu_shb.cpp | 45 ++ .../tree/intrusive_ellenbintree_rcu_sht.cpp | 45 ++ .../tree/test_intrusive_ellen_bintree_rcu.h | 439 ++++++++++++++++++ test/unit/tree/test_intrusive_tree_rcu.h | 227 +++++++++ 10 files changed, 933 insertions(+) create mode 100644 test/unit/tree/intrusive_ellenbintree_rcu_gpb.cpp create mode 100644 test/unit/tree/intrusive_ellenbintree_rcu_gpi.cpp create mode 100644 test/unit/tree/intrusive_ellenbintree_rcu_gpt.cpp create mode 100644 test/unit/tree/intrusive_ellenbintree_rcu_shb.cpp create mode 100644 test/unit/tree/intrusive_ellenbintree_rcu_sht.cpp create mode 100644 test/unit/tree/test_intrusive_ellen_bintree_rcu.h create mode 100644 test/unit/tree/test_intrusive_tree_rcu.h diff --git a/projects/Win/vc14/gtest-tree.vcxproj b/projects/Win/vc14/gtest-tree.vcxproj index 758664db..838c00fd 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj +++ b/projects/Win/vc14/gtest-tree.vcxproj @@ -30,10 +30,38 @@ + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + + + + + {2ABD6A2E-BEA7-4c8c-982B-A609F83D2DCB} diff --git a/projects/Win/vc14/gtest-tree.vcxproj.filters b/projects/Win/vc14/gtest-tree.vcxproj.filters index 8d91cb0d..6cda2263 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj.filters +++ b/projects/Win/vc14/gtest-tree.vcxproj.filters @@ -24,6 +24,21 @@ Source Files + + Source Files + + + Source Files + + + Source Files + + + Source Files + + + Source Files + @@ -32,5 +47,11 @@ Header Files + + 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 7488df23..5cf4ed0c 100644 --- a/test/unit/tree/CMakeLists.txt +++ b/test/unit/tree/CMakeLists.txt @@ -6,6 +6,11 @@ set(CDSGTEST_TREE_SOURCES ../main.cpp intrusive_ellenbintree_hp.cpp intrusive_ellenbintree_dhp.cpp + intrusive_ellenbintree_rcu_gpb.cpp + intrusive_ellenbintree_rcu_gpi.cpp + intrusive_ellenbintree_rcu_gpt.cpp + intrusive_ellenbintree_rcu_shb.cpp + intrusive_ellenbintree_rcu_sht.cpp ) include_directories( diff --git a/test/unit/tree/intrusive_ellenbintree_rcu_gpb.cpp b/test/unit/tree/intrusive_ellenbintree_rcu_gpb.cpp new file mode 100644 index 00000000..865f22db --- /dev/null +++ b/test/unit/tree/intrusive_ellenbintree_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_intrusive_ellen_bintree_rcu.h" + +namespace { + + typedef cds::urcu::general_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPB, IntrusiveEllenBinTree, rcu_implementation ); diff --git a/test/unit/tree/intrusive_ellenbintree_rcu_gpi.cpp b/test/unit/tree/intrusive_ellenbintree_rcu_gpi.cpp new file mode 100644 index 00000000..d8e9ce22 --- /dev/null +++ b/test/unit/tree/intrusive_ellenbintree_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_intrusive_ellen_bintree_rcu.h" + +namespace { + + typedef cds::urcu::general_instant<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPI, IntrusiveEllenBinTree, rcu_implementation ); diff --git a/test/unit/tree/intrusive_ellenbintree_rcu_gpt.cpp b/test/unit/tree/intrusive_ellenbintree_rcu_gpt.cpp new file mode 100644 index 00000000..6f66c1cb --- /dev/null +++ b/test/unit/tree/intrusive_ellenbintree_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_intrusive_ellen_bintree_rcu.h" + +namespace { + + typedef cds::urcu::general_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPT, IntrusiveEllenBinTree, rcu_implementation ); diff --git a/test/unit/tree/intrusive_ellenbintree_rcu_shb.cpp b/test/unit/tree/intrusive_ellenbintree_rcu_shb.cpp new file mode 100644 index 00000000..413134d1 --- /dev/null +++ b/test/unit/tree/intrusive_ellenbintree_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_intrusive_ellen_bintree_rcu.h" + +namespace { + + typedef cds::urcu::signal_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHB, IntrusiveEllenBinTree, rcu_implementation ); + +#endif // #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED diff --git a/test/unit/tree/intrusive_ellenbintree_rcu_sht.cpp b/test/unit/tree/intrusive_ellenbintree_rcu_sht.cpp new file mode 100644 index 00000000..6cea39f4 --- /dev/null +++ b/test/unit/tree/intrusive_ellenbintree_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_intrusive_ellen_bintree_rcu.h" + +namespace { + + typedef cds::urcu::signal_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHT, IntrusiveEllenBinTree, rcu_implementation ); + +#endif // #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED diff --git a/test/unit/tree/test_intrusive_ellen_bintree_rcu.h b/test/unit/tree/test_intrusive_ellen_bintree_rcu.h new file mode 100644 index 00000000..b5fdd2e9 --- /dev/null +++ b/test/unit/tree/test_intrusive_ellen_bintree_rcu.h @@ -0,0 +1,439 @@ +/* + 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_INTRUSIVE_ELLEN_BINTREE_RCU_H +#define CDSUNIT_TREE_TEST_INTRUSIVE_ELLEN_BINTREE_RCU_H + +#include "test_intrusive_tree_rcu.h" + +#include +#include +#include + + +// forward declaration +namespace cds { namespace intrusive {}} + +namespace { + + namespace ci = cds::intrusive; + + template + class IntrusiveEllenBinTree: public cds_test::intrusive_tree_rcu + { + typedef cds_test::intrusive_tree_rcu base_class; + + public: + typedef cds::urcu::gc rcu_type; + + typedef base_class::key_type key_type; + + typedef typename base_class::base_int_item< ci::ellen_bintree::node> base_item_type; + typedef ci::ellen_bintree::internal_node< key_type, base_item_type > internal_base_node; + typedef ci::ellen_bintree::update_desc< base_item_type, internal_base_node > update_base_desc; + + typedef typename base_class::member_int_item< ci::ellen_bintree::node> member_item_type; + typedef ci::ellen_bintree::internal_node< key_type, member_item_type > internal_member_node; + typedef ci::ellen_bintree::update_desc< member_item_type, internal_member_node > update_member_desc; + + // update_desc pools + struct pool_traits: public cds::memory::vyukov_queue_pool_traits + { + typedef cds::opt::v::static_buffer< update_base_desc, 256 > buffer; + }; + typedef cds::memory::vyukov_queue_pool< update_base_desc, pool_traits > pool_type; + typedef cds::memory::lazy_vyukov_queue_pool< update_base_desc, pool_traits > lazy_pool_type; + + static pool_type * s_Pool; + static lazy_pool_type * s_LazyPool; + + struct pool_accessor + { + typedef typename pool_type::value_type value_type; + + pool_type& operator()() const + { + return *s_Pool; + } + }; + + struct lazy_pool_accessor + { + typedef typename lazy_pool_type::value_type value_type; + + lazy_pool_type& operator()() const + { + return *s_LazyPool; + } + }; + + static void SetUpTestCase() + { + ASSERT_TRUE( s_Pool == nullptr ); + ASSERT_TRUE( s_LazyPool == nullptr ); + s_Pool = new pool_type; + s_LazyPool = new lazy_pool_type; + } + + static void TearDownTestCase() + { + ASSERT_TRUE( s_Pool != nullptr ); + ASSERT_TRUE( s_LazyPool != nullptr ); + delete s_LazyPool; + delete s_Pool; + + s_LazyPool = nullptr; + s_Pool = nullptr; + } + + struct generic_traits: public ci::ellen_bintree::traits + { + typedef base_class::key_extractor key_extractor; + typedef mock_disposer disposer; + }; + + protected: + void SetUp() + { + RCU::Construct(); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + RCU::Destruct(); + } + }; + + /*static*/ template typename IntrusiveEllenBinTree::pool_type * IntrusiveEllenBinTree::s_Pool = nullptr; + /*static*/ template typename IntrusiveEllenBinTree::lazy_pool_type * IntrusiveEllenBinTree::s_LazyPool = nullptr; + + TYPED_TEST_CASE_P( IntrusiveEllenBinTree ); + + + TYPED_TEST_P( IntrusiveEllenBinTree, base_cmp ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, + ci::ellen_bintree::make_traits< + ci::opt::type_traits< generic_traits > + , ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >>> + , ci::opt::compare< typename TestFixture::template cmp> + >::type + > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, base_less ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, + ci::ellen_bintree::make_traits< + ci::opt::type_traits< generic_traits > + , ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >>> + , ci::opt::less< typename TestFixture::template less> + >::type + > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, base_item_counter ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, + ci::ellen_bintree::make_traits< + ci::opt::type_traits< generic_traits > + , ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >>> + , ci::opt::compare< typename TestFixture::template cmp> + , ci::opt::item_counter< typename TestFixture::simple_item_counter > + >::type + > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, base_backoff ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template cmp compare; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, base_seq_cst ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template cmp compare; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::pause back_off; + typedef ci::opt::v::sequential_consistent memory_model; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, base_update_desc_pool ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator< typename TestFixture::update_base_desc, typename TestFixture::pool_accessor> update_desc_allocator; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, base_update_desc_lazy_pool ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::base_item_type base_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator< typename TestFixture::update_base_desc, typename TestFixture::lazy_pool_accessor> update_desc_allocator; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + // member hook + TYPED_TEST_P( IntrusiveEllenBinTree, member_cmp ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, + ci::ellen_bintree::make_traits< + ci::opt::type_traits< generic_traits > + , ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >>> + , ci::opt::compare< typename TestFixture::template cmp> + >::type + > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, member_less ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, + ci::ellen_bintree::make_traits< + ci::opt::type_traits< generic_traits > + , ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >>> + , ci::opt::less< typename TestFixture::template less> + >::type + > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, member_item_counter ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, + ci::ellen_bintree::make_traits< + ci::opt::type_traits< generic_traits > + , ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >>> + , ci::opt::compare< typename TestFixture::template cmp> + , ci::opt::item_counter< typename TestFixture::simple_item_counter > + >::type + > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, member_backoff ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template cmp compare; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, member_seq_cst ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template cmp compare; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::pause back_off; + typedef ci::opt::v::sequential_consistent memory_model; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, member_update_desc_pool ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator< typename TestFixture::update_member_desc, typename TestFixture::pool_accessor> update_desc_allocator; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + TYPED_TEST_P( IntrusiveEllenBinTree, member_update_desc_lazy_pool ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type key_type; + typedef typename TestFixture::member_item_type member_item_type; + typedef typename TestFixture::generic_traits generic_traits; + + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook; + typedef typename TestFixture::template less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator< typename TestFixture::update_member_desc, typename TestFixture::lazy_pool_accessor> update_desc_allocator; + }; + + typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type; + + tree_type t; + this->test( t ); + } + + REGISTER_TYPED_TEST_CASE_P( IntrusiveEllenBinTree, + base_cmp, base_less, base_item_counter, base_backoff, base_seq_cst, base_update_desc_pool, base_update_desc_lazy_pool, member_cmp, member_less, member_item_counter, member_backoff, member_seq_cst, member_update_desc_pool, member_update_desc_lazy_pool + ); + +} // namespace + +#endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_ELLEN_BINTREE_RCU_H diff --git a/test/unit/tree/test_intrusive_tree_rcu.h b/test/unit/tree/test_intrusive_tree_rcu.h new file mode 100644 index 00000000..ceca126d --- /dev/null +++ b/test/unit/tree/test_intrusive_tree_rcu.h @@ -0,0 +1,227 @@ +/* + 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_INTRUSIVE_TREE_RCU_H +#define CDSUNIT_TREE_TEST_INTRUSIVE_TREE_RCU_H + +#include "test_intrusive_tree.h" + + +// forward declaration +namespace cds { namespace intrusive {}} + +namespace cds_test { + + namespace ci = cds::intrusive; + + class intrusive_tree_rcu: public intrusive_tree + { + typedef intrusive_tree base_class; + + protected: + + + template + void test( Tree& t ) + { + // Precondition: tree is empty + // Postcondition: tree is empty + + base_class::test( t ); + + ASSERT_TRUE( t.empty() ); + ASSERT_CONTAINER_SIZE( t, 0 ); + + typedef typename Tree::value_type value_type; + typedef typename Tree::rcu_lock rcu_lock; + + std::vector< value_type > data; + std::vector< size_t> indices; + data.reserve( kSize ); + indices.reserve( kSize ); + for ( size_t key = 0; key < kSize; ++key ) { + data.push_back( value_type( static_cast(key) ) ); + indices.push_back( key ); + } + shuffle( indices.begin(), indices.end() ); + + typename Tree::exempt_ptr xp; + + // get/extract from empty tree + for ( auto idx : indices ) { + auto& i = data[idx]; + + { + rcu_lock l; + value_type * p = t.get( i ); + ASSERT_TRUE( p == nullptr ); + p = t.get( i.key() ); + ASSERT_TRUE( !p ); + p = t.get_with( other_item( i.key() ), other_less() ); + ASSERT_TRUE( p == nullptr ); + } + + xp = t.extract( i ); + ASSERT_TRUE( !xp ); + xp = t.extract( i.key()); + ASSERT_TRUE( !xp ); + xp = t.extract_with( other_item( i.key()), other_less()); + ASSERT_TRUE( !xp ); + + xp = t.extract_min(); + ASSERT_TRUE( !xp ); + xp = t.extract_max(); + ASSERT_TRUE( !xp ); + } + + // fill tree + for ( auto idx : indices ) { + auto& i = data[idx]; + i.nDisposeCount = 0; + ASSERT_TRUE( t.insert( i ) ); + } + + // get/extract + for ( auto idx : indices ) { + auto& i = data[idx]; + + { + rcu_lock l; + + value_type * p; + EXPECT_EQ( i.nFindCount, 0 ); + p = t.get( i ); + ASSERT_FALSE( !p ); + ++p->nFindCount; + EXPECT_EQ( i.nFindCount, 1 ); + + p = t.get( i.key() ); + ASSERT_FALSE( !p ); + ++p->nFindCount; + EXPECT_EQ( i.nFindCount, 2 ); + + p = t.get_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !p ); + ++p->nFindCount; + EXPECT_EQ( i.nFindCount, 3 ); + } + + EXPECT_EQ( i.nEraseCount, 0 ); + switch ( i.key() % 3 ) { + case 0: + xp = t.extract( i.key()); + break; + case 1: + xp = t.extract( i ); + break; + case 2: + xp = t.extract_with( other_item( i.key() ), other_less() ); + break; + } + ASSERT_FALSE( !xp ); + ++xp->nEraseCount; + EXPECT_EQ( i.nEraseCount, 1 ); + + xp = t.extract( i ); + ASSERT_TRUE( !xp ); + xp = t.extract( i.key() ); + ASSERT_TRUE( !xp ); + xp = t.extract_with( other_item( i.key() ), other_less() ); + ASSERT_TRUE( !xp ); + } + + ASSERT_TRUE( t.empty() ); + ASSERT_CONTAINER_SIZE( t, 0 ); + + // Force retiring cycle + Tree::gc::force_dispose(); + for ( auto& i : data ) { + EXPECT_EQ( i.nDisposeCount, 1 ); + } + + // extract_min + for ( auto idx : indices ) { + auto& i = data[idx]; + i.nDisposeCount = 0; + ASSERT_TRUE( t.insert( i ) ); + } + + size_t nCount = 0; + int nKey = -1; + while ( !t.empty() ) { + xp = t.extract_min(); + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->key(), nKey + 1 ); + ++nCount; + nKey = xp->key(); + } + xp.release(); + ASSERT_TRUE( t.empty() ); + ASSERT_CONTAINER_SIZE( t, 0 ); + EXPECT_EQ( nCount, data.size() ); + + // Force retiring cycle + Tree::gc::force_dispose(); + for ( auto& i : data ) { + EXPECT_EQ( i.nDisposeCount, 1 ); + } + + // extract_max + for ( auto idx : indices ) { + auto& i = data[idx]; + i.nDisposeCount = 0; + ASSERT_TRUE( t.insert( i ) ); + } + + nCount = 0; + nKey = static_cast( data.size()); + while ( !t.empty() ) { + xp = t.extract_max(); + ASSERT_FALSE( !xp ); + EXPECT_EQ( xp->key(), nKey - 1 ); + ++nCount; + nKey = xp->key(); + } + xp.release(); + ASSERT_TRUE( t.empty() ); + ASSERT_CONTAINER_SIZE( t, 0 ); + EXPECT_EQ( nCount, data.size() ); + + // Force retiring cycle + Tree::gc::force_dispose(); + for ( auto& i : data ) { + EXPECT_EQ( i.nDisposeCount, 1 ); + } + } + }; + +} // namespace cds_test + +#endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_RCU_H -- 2.34.1