From a8e2b827ac369f56546b7a5593c210cb356a754c Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 8 Apr 2016 09:06:25 +0300 Subject: [PATCH] Migrated intrusive EllenBinTree unit test to gtest --- projects/Win/vc14/gtest-tree.vcxproj | 1 + projects/Win/vc14/gtest-tree.vcxproj.filters | 3 + test/unit/tree/CMakeLists.txt | 1 + test/unit/tree/intrusive_ellenbintree_hp.cpp | 161 +++++++++++++++++++ test/unit/tree/test_intrusive_tree.h | 46 +++++- test/unit/tree/test_intrusive_tree_hp.h | 9 +- 6 files changed, 212 insertions(+), 9 deletions(-) create mode 100644 test/unit/tree/intrusive_ellenbintree_hp.cpp diff --git a/projects/Win/vc14/gtest-tree.vcxproj b/projects/Win/vc14/gtest-tree.vcxproj index da809c9f..df2a8b97 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj +++ b/projects/Win/vc14/gtest-tree.vcxproj @@ -28,6 +28,7 @@ + diff --git a/projects/Win/vc14/gtest-tree.vcxproj.filters b/projects/Win/vc14/gtest-tree.vcxproj.filters index 71e1f6c0..77abf64a 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj.filters +++ b/projects/Win/vc14/gtest-tree.vcxproj.filters @@ -18,6 +18,9 @@ Source Files + + Source Files + diff --git a/test/unit/tree/CMakeLists.txt b/test/unit/tree/CMakeLists.txt index b569e8e7..d64b4f46 100644 --- a/test/unit/tree/CMakeLists.txt +++ b/test/unit/tree/CMakeLists.txt @@ -2,6 +2,7 @@ set(PACKAGE_NAME unit-tree) set(CDSGTEST_TREE_SOURCES ../main.cpp + intrusive_ellenbintree_hp.cpp ) include_directories( diff --git a/test/unit/tree/intrusive_ellenbintree_hp.cpp b/test/unit/tree/intrusive_ellenbintree_hp.cpp new file mode 100644 index 00000000..b55ed62e --- /dev/null +++ b/test/unit/tree/intrusive_ellenbintree_hp.cpp @@ -0,0 +1,161 @@ +/* + 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 "test_intrusive_tree_hp.h" + +#include + +namespace { + namespace ci = cds::intrusive; + typedef cds::gc::HP gc_type; + + class IntrusiveEllenBinTree_HP : public cds_test::intrusive_tree_hp + { + protected: + typedef cds_test::intrusive_tree_hp base_class; + + protected: + 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; + + void SetUp() + { + struct list_traits : public ci::ellen_bintree::traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc> hook; + }; + typedef ci::EllenBinTree< gc_type, key_type, base_item_type > set_type; + + // +1 - for guarded_ptr + cds::gc::hp::GarbageCollector::Construct( set_type::c_nHazardPtrCount + 1, 1, 16 ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct( true ); + } + + struct generic_traits: public ci::ellen_bintree::traits + { + typedef base_class::key_extractor key_extractor; + typedef mock_disposer disposer; + }; + }; + + + TEST_F( IntrusiveEllenBinTree_HP, base_cmp ) + { + typedef ci::EllenBinTree< gc_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< gc_type >>> + ,ci::opt::compare< cmp> + >::type + > tree_type; + + tree_type t; + test( t ); + } + + TEST_F( IntrusiveEllenBinTree_HP, base_less ) + { + typedef ci::EllenBinTree< gc_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< gc_type >>> + ,ci::opt::less< less> + >::type + > tree_type; + + tree_type t; + test( t ); + } + + TEST_F( IntrusiveEllenBinTree_HP, base_item_counter ) + { + typedef ci::EllenBinTree< gc_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< gc_type >>> + ,ci::opt::compare< cmp> + ,ci::opt::item_counter< simple_item_counter > + >::type + > tree_type; + + tree_type t; + test( t ); + } + + TEST_F( IntrusiveEllenBinTree_HP, base_backoff ) + { + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook; + typedef cmp compare; + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + }; + + typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type; + + tree_type t; + test( t ); + } + + TEST_F( IntrusiveEllenBinTree_HP, base_seq_cst ) + { + struct tree_traits: public generic_traits + { + typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook; + typedef cmp compare; + typedef base_class::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< gc_type, key_type, base_item_type, tree_traits > tree_type; + + tree_type t; + test( t ); + } + + +} // namespace diff --git a/test/unit/tree/test_intrusive_tree.h b/test/unit/tree/test_intrusive_tree.h index ea1016cb..3359e81f 100644 --- a/test/unit/tree/test_intrusive_tree.h +++ b/test/unit/tree/test_intrusive_tree.h @@ -66,6 +66,8 @@ namespace cds_test { } }; + typedef int key_type; + template struct base_int_item : public Node @@ -136,6 +138,15 @@ namespace cds_test { } }; + struct key_extractor + { + template + void operator()( key_type& key, T const& val ) const + { + key = val.key(); + } + }; + struct simple_item_counter { size_t m_nCount; @@ -182,6 +193,11 @@ namespace cds_test { { return lhs < rhs.key(); } + + bool operator()( int lhs, int rhs ) const + { + return lhs < rhs; + } }; template @@ -194,19 +210,26 @@ namespace cds_test { return v1.key() > v2.key() ? 1 : 0; } - bool operator()( T const& lhs, int rhs ) const + int operator()( T const& lhs, int rhs ) const { if ( lhs.key() < rhs ) return -1; return lhs.key() > rhs ? 1 : 0; } - bool operator()( int lhs, T const& rhs ) const + int operator()( int lhs, T const& rhs ) const { if ( lhs < rhs.key() ) return -1; return lhs > rhs.key() ? 1 : 0; } + + int operator()( int lhs, int rhs ) const + { + if ( lhs < rhs ) + return -1; + return lhs > rhs ? 1 : 0; + } }; struct other_item { @@ -228,6 +251,18 @@ namespace cds_test { { return lhs.key() < rhs.key(); } + + template + bool operator()( Q const& lhs, int rhs ) const + { + return lhs.key() < rhs; + } + + template + bool operator()( int lhs, T const& rhs ) const + { + return lhs < rhs.key(); + } }; struct mock_disposer @@ -329,7 +364,7 @@ namespace cds_test { ++val.nUpdateCount; }, false ); EXPECT_TRUE( updResult.first ); - EXPECT_TRUE( updResult.second ); + EXPECT_FALSE( updResult.second ); EXPECT_EQ( i.nUpdateCount, 1 ); i.nUpdateCount = 0; @@ -418,7 +453,8 @@ namespace cds_test { } // clear - for ( auto& i : data ) { + for ( auto idx : indices ) { + auto& i = data[idx]; i.clear_stat(); ASSERT_TRUE( t.insert( i )); } @@ -430,8 +466,6 @@ namespace cds_test { ASSERT_TRUE( t.empty()); ASSERT_CONTAINER_SIZE( t, 0 ); - ASSERT_TRUE( t.begin() == t.end() ); - ASSERT_TRUE( t.cbegin() == t.cend() ); // Force retiring cycle Tree::gc::force_dispose(); diff --git a/test/unit/tree/test_intrusive_tree_hp.h b/test/unit/tree/test_intrusive_tree_hp.h index 8a5835d1..0b350c97 100644 --- a/test/unit/tree/test_intrusive_tree_hp.h +++ b/test/unit/tree/test_intrusive_tree_hp.h @@ -96,7 +96,8 @@ namespace cds_test { } // fill tree - for ( auto& i : data ) { + for ( auto idx : indices ) { + auto& i = data[idx]; i.nDisposeCount = 0; ASSERT_TRUE( t.insert( i ) ); } @@ -157,7 +158,8 @@ namespace cds_test { } // extract_min - for ( auto& i : data ) { + for ( auto idx : indices ) { + auto& i = data[idx]; i.nDisposeCount = 0; ASSERT_TRUE( t.insert( i ) ); } @@ -183,7 +185,8 @@ namespace cds_test { } // extract_max - for ( auto& i : data ) { + for ( auto idx : indices ) { + auto& i = data[idx]; i.nDisposeCount = 0; ASSERT_TRUE( t.insert( i ) ); } -- 2.34.1